Class: Immudb::HTree

Inherits:
Object
  • Object
show all
Defined in:
lib/immudb/htree.rb

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(max_width) ⇒ HTree

Returns a new instance of HTree.



17
18
19
20
21
22
23
24
25
26
27
28
29
30
 
# File 'lib/immudb/htree.rb', line 17

def initialize(max_width)
  return if max_width < 1

  @max_width = max_width
  lw = 1
  while lw < max_width
    lw = lw << 1
  end
  height = (max_width - 1).bit_length + 1
  @levels = [nil] * height
  height.times do |l|
    @levels[l] = [nil] * (lw >> l)
  end
end

Instance Attribute Details

#root ⇒ Object (readonly)

Returns the value of attribute root.



15
16
17
 
# File 'lib/immudb/htree.rb', line 15

def root
  @root
end

Instance Method Details

#build_with(digests) ⇒ Object 



32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
 
# File 'lib/immudb/htree.rb', line 32

def build_with(digests)
  if digests.length > @max_width
    raise ArgumentError, "Max width exceeded"
  end
  if digests.length == 0
    raise ArgumentError, "Illegal arguments"
  end
  digests.length.times do |i|
    leaf = LEAF_PREFIX + digests[i]
    @levels[0][i] = Digest::SHA256.digest(leaf)
  end
  l = 0
  w = digests.length
  while w > 1
    wn = 0
    i = 0
    while i + 1 < w
      b = NODE_PREFIX + @levels[l][i] + @levels[l][i + 1]
      @levels[l + 1][wn] = Digest::SHA256.digest(b)
      wn = wn + 1
      i = i + 2
    end
    if w % 2 == 1
      @levels[l + 1][wn] = @levels[l][w - 1]
      wn = wn + 1
    end
    l += 1
    w = wn
  end
  @width = digests.length
  @root = @levels[l][0]
end

#inclusion_proof(i) ⇒ Object 



65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
 
# File 'lib/immudb/htree.rb', line 65

def inclusion_proof(i)
  if i >= @width
    raise ArgumentError, "Illegal arguments"
  end
  m = i
  n = @width
  offset = 0
  proof = InclusionProof.new
  proof.leaf = i
  proof.width = @width
  if @width == 1
    return proof
  end
  loop do
    d = (n - 1).bit_length
    k = 1 << (d - 1)
    if m < k
      l, r = offset + k, offset + n - 1
      n = k
    else
      l, r = offset, offset + k - 1
      m = m - k
      n = n - k
      offset = offset + k
    end
    layer = (r - l).bit_length
    index = (l / (1 << layer)).to_i
    proof.terms = @levels[layer][index] + proof.terms
    if n < 1 || (n == 1 && m == 0)
      return proof
    end
  end
end