Module: Merkle::Algorithm

Defined in:
lib/algorithm.rb

Class Method Summary collapse

Class Method Details

.audit_proof(array, index, digest = nil) ⇒ Object 



30
31
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
 
# File 'lib/algorithm.rb', line 30

def audit_proof(array, index, digest = nil)
  audit_proof_path = Array.new
  element = array[index]

  # This block is inside case with two elements.
  # We have to handle pairs only with our element and add neibour of our element to the path
  # Then we have to update our element
  merkle_tree(array, digest) do |pair_of_elements|
    if pair_of_elements.include?(element)
      audit_proof_path << begin 
        if pair_of_elements.first == element 
          {
             position: 'right',
             value: pair_of_elements.last
          }
        else
          {
            position: 'left',
            value: pair_of_elements.first
          }
        end
      end
  
      element = node_hash(digest, pair_of_elements.first, pair_of_elements.last)
    end
  end
  
  audit_proof_path
end

.audit_proof_build_head(audit_proof_path, element, digest = nil) ⇒ Object

Culculate a head of tree using audit_proof path By this method we can verify is the element a part of the tree or not depends on returned head



69
70
71
72
73
74
75
76
77
78
 
# File 'lib/algorithm.rb', line 69

def audit_proof_build_head(audit_proof_path, element, digest = nil) 
  audit_proof_path.inject(element) do |element, node|
    case node[:position]
    when 'right'
      node_hash(digest, element, node[:value])
    when 'left'
      node_hash(digest, node[:value], element)
    end
  end
end

.consistency_proof(array, index, digest = nil) ⇒ Object

Culculate a head of tree using audit_proof path



61
62
63
64
65
 
# File 'lib/algorithm.rb', line 61

def consistency_proof(array, index, digest = nil)
  sub_array = array[0..index]

  audit_proof(sub_array, index, digest).map{ |e| e[:value] }
end

.consistency_proof_build_head(consistency_proof_path, digest = nil) ⇒ Object

Culculate a head of sub-tree using consistency_proof path By this method we can verify is the tree includes sub-tree



82
83
84
85
86
 
# File 'lib/algorithm.rb', line 82

def consistency_proof_build_head(consistency_proof_path, digest = nil) 
  consistency_proof_path.inject('') do |result, consistency_path_element|
    node_hash(digest, consistency_path_element, result)
  end
end

.merkle_tree(array, digest, &block) ⇒ Object 



4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
 
# File 'lib/algorithm.rb', line 4

def merkle_tree(array, digest, &block)
  # Define it here since we have to add &block and digest params to every method call (DRY..)
  merkle_tree_method = -> (arg) { merkle_tree(arg, digest, &block) }

  case array.size
  when 1
    return array.first
  when 2
    # This yeild for define audit_proof method. To build audit_proof_elements
    # we have to know pair of <searching> elements, so case array.size = 2 is what actually need.
    # Basicly we just need to handle this case and we will have a new audit_proof algorithm!
    yield(array) if block_given?

    return node_hash(digest, array.first, array.last)
  else
    cons = array.size.even? ? 2 : 1

    merkle_tree_method.call(
      [
        merkle_tree_method.call(array[0...(array.size - cons)]),
        merkle_tree_method.call(array[(array.size - cons)..])
      ]
    )
  end
end