Class: Bitcoin::BloomFilter

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

Constant Summary collapse

LN2_SQUARED =

log(2) ** 2

0.4804530139182014246671025263266649717305529515945455
LN2 =

log(2)

0.6931471805599453094172321214581765680755001343602552
MAX_BLOOM_FILTER_SIZE =

bytes

36_000
MAX_HASH_FUNCS = 
50

Instance Attribute Summary collapse

Class Method Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(filter, hash_funcs, tweak) ⇒ BloomFilter

Returns a new instance of BloomFilter.



12
13
14
15
16
 
# File 'lib/bitcoin/bloom_filter.rb', line 12

def initialize(filter, hash_funcs, tweak)
  @filter = filter
  @hash_funcs = hash_funcs
  @tweak = tweak
end

Instance Attribute Details

#filter ⇒ Object (readonly)

Returns the value of attribute filter.



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

def filter
  @filter
end

#hash_funcs ⇒ Object (readonly)

Returns the value of attribute hash_funcs.



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

def hash_funcs
  @hash_funcs
end

#tweak ⇒ Object (readonly)

Returns the value of attribute tweak.



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

def tweak
  @tweak
end

Class Method Details

.create_filter(elements_length, fp_rate, tweak = 0) ⇒ Object

Create a new bloom filter.

Parameters:

  • elements_length (Integer) —

    the number of elements

  • fp_rate (Float) —

    the false positive rate chosen by the client

  • tweak (Integer) (defaults to: 0) —

    A random value to add to the seed value in the hash function used by the bloom filter



22
23
24
25
26
27
28
29
 
# File 'lib/bitcoin/bloom_filter.rb', line 22

def self.create_filter(elements_length, fp_rate, tweak = 0)
  # The size S of the filter in bytes is given by (-1 / pow(log(2), 2) * N * log(P)) / 8
  len = [[(-elements_length * Math.log(fp_rate) / (LN2_SQUARED * 8)).to_i, MAX_BLOOM_FILTER_SIZE].min, 1].max
  filter = Array.new(len, 0)
  # The number of hash functions required is given by S * 8 / N * log(2)
  hash_funcs = [[(filter.size * 8 * LN2 / elements_length).to_i, MAX_HASH_FUNCS].min, 1].max
  BloomFilter.new(filter, hash_funcs, tweak)
end

Instance Method Details

#add(data) ⇒ Object

Parameters:

  • data (String) —

    The data element to add to the current filter.



32
33
34
35
36
37
38
 
# File 'lib/bitcoin/bloom_filter.rb', line 32

def add(data)
  return if full?
  hash_funcs.times do |i|
    hash = to_hash(data, i)
    set_bit(hash)
  end
end

#clear ⇒ Object 



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

def clear
  filter.fill(0)
  @full = false
end

#contains?(data) ⇒ Boolean

Returns true if the given data matches the filter

Parameters:

  • data (String) —

    The data to check the current filter

Returns:

  • (Boolean) —

    true if the given data matches the filter



43
44
45
46
47
48
49
50
 
# File 'lib/bitcoin/bloom_filter.rb', line 43

def contains?(data)
  return true if full?
  hash_funcs.times do |i|
    hash = to_hash(data, i)
    return false unless check_bit(hash)
  end
  true
end

#to_a ⇒ Object 



57
58
59
 
# File 'lib/bitcoin/bloom_filter.rb', line 57

def to_a
  filter
end