Class: Bitcoin::GCSFilter

Inherits:
Object show all
Defined in:
lib/bitcoin/gcs_filter.rb

Overview

Golomb-coded set filter see github.com/bitcoin/bips/blob/master/bip-0158.mediawiki

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(key, p, m, elements: nil, encoded_filter: nil) ⇒ Bitcoin::GCSFilter

initialize Filter object.

Parameters:

  • key (String) —

    the 128-bit key used to randomize the SipHash outputs.

  • p (Integer) —

    the bit parameter of the Golomb-Rice coding.

  • m (Integer) —

    which determines the false positive rate.

  • elements (Array) (defaults to: nil) —

    the filter elements.

  • encoded_filter (String) (defaults to: nil) —

    encoded filter with hex format.



22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
 
# File 'lib/bitcoin/gcs_filter.rb', line 22

def initialize(key, p, m, elements: nil, encoded_filter: nil)
  raise 'specify either elements or encoded_filter.' if elements.nil? && encoded_filter.nil?
  raise 'p must be <= 32' if p > 32
  @key = key
  @p = p
  @m = m
  if elements
    raise 'elements size must be < 2**32.' if elements.size >= (2**32)
    @n = elements.size
    encoded = Bitcoin.pack_var_int(@n)
    bit_writer = Bitcoin::BitStreamWriter.new
    unless elements.empty?
      last_value = 0
      hashed_set = elements.map{|e| hash_to_range(e) }.sort
      hashed_set.each do |v|
        delta = v - last_value
        golomb_rice_encode(bit_writer, p, delta)
        last_value = v
      end
    end
    bit_writer.flush
    encoded << bit_writer.stream
    @encoded = encoded.bth
  else
    @encoded = encoded_filter
    @n, payload = Bitcoin.unpack_var_int(encoded_filter.htb)
  end
end

Instance Attribute Details

#encoded ⇒ Object (readonly)

encoded filter with hex format.



13
14
15
 
# File 'lib/bitcoin/gcs_filter.rb', line 13

def encoded
  @encoded
end

#key ⇒ Object (readonly)

SipHash key



12
13
14
 
# File 'lib/bitcoin/gcs_filter.rb', line 12

def key
  @key
end

#m ⇒ Object (readonly)

Inverse false positive rate



10
11
12
 
# File 'lib/bitcoin/gcs_filter.rb', line 10

def m
  @m
end

#n ⇒ Object (readonly)

Number of elements in the filter



11
12
13
 
# File 'lib/bitcoin/gcs_filter.rb', line 11

def n
  @n
end

#p ⇒ Object (readonly)

Golomb-Rice coding parameter



9
10
11
 
# File 'lib/bitcoin/gcs_filter.rb', line 9

def p
  @p
end

Instance Method Details

#f ⇒ Object

Range of element hashes, F = N * M



52
53
54
 
# File 'lib/bitcoin/gcs_filter.rb', line 52

def f
  n * m
end

#hash_to_range(element) ⇒ Integer

Hash a data element to an integer in the range [0, F).

Parameters:

  • element (String) —

    with binary format.

Returns:



59
60
61
62
 
# File 'lib/bitcoin/gcs_filter.rb', line 59

def hash_to_range(element)
  hash = SipHash.digest(key, element)
  map_into_range(hash, f)
end

#match?(element) ⇒ Boolean

Checks if the element may be in the set. False positives are possible with probability 1/M.

Parameters:

  • element (String) —

    with binary format

Returns:

  • (Boolean) —

    whether element in set.



67
68
69
70
 
# File 'lib/bitcoin/gcs_filter.rb', line 67

def match?(element)
  query = hash_to_range(element)
  match_internal?([query], 1)
end

#match_any?(elements) ⇒ Boolean

Checks if any of the given elements may be in the set. False positives are possible with probability 1/M per element checked. This is more efficient that checking Match on multiple elements separately.

Parameters:

  • elements (Array) —

    list of elements with binary format.

Returns:

  • (Boolean) —

    whether element in set.



76
77
78
79
 
# File 'lib/bitcoin/gcs_filter.rb', line 76

def match_any?(elements)
  queries = elements.map{|e| hash_to_range(e) }.sort
  match_internal?(queries, queries.size)
end