Class: Bitcoin::GCSFilter

Inherits:
Object
  • 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

Constant Summary collapse

MAX_ELEMENTS_SIZE =

2**32

4294967296

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.



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
50
51
 
# File 'lib/bitcoin/gcs_filter.rb', line 24

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 >= MAX_ELEMENTS_SIZE
    @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.



15
16
17
 
# File 'lib/bitcoin/gcs_filter.rb', line 15

def encoded
  @encoded
end

#key ⇒ Object (readonly)

SipHash key



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

def key
  @key
end

#m ⇒ Object (readonly)

Inverse false positive rate



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

def m
  @m
end

#n ⇒ Object (readonly)

Number of elements in the filter



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

def n
  @n
end

#p ⇒ Object (readonly)

Golomb-Rice coding parameter



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

def p
  @p
end

Instance Method Details

#f ⇒ Object

Range of element hashes, F = N * M



54
55
56
 
# File 'lib/bitcoin/gcs_filter.rb', line 54

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:



61
62
63
64
 
# File 'lib/bitcoin/gcs_filter.rb', line 61

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.



69
70
71
72
 
# File 'lib/bitcoin/gcs_filter.rb', line 69

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.



78
79
80
81
 
# File 'lib/bitcoin/gcs_filter.rb', line 78

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