Class: Merkle::Proof

Inherits:
Object
  • Object
show all
Includes:
Util
Defined in:
lib/merkle/proof.rb

Constant Summary collapse

MAX_SIBLINGS =

Upper bound on the number of siblings, i.e. the depth of the tree the proof came from. A proof longer than this cannot correspond to any realistic tree, so it is rejected rather than hashed. It matches the deepest tree the library will build, which is also the deepest a BIP341 script tree can be: a control block carries at most 128 path elements.

MAX_DEPTH

Constants included from Util

Util::HASH_SIZE, Util::MAX_DEPTH

Instance Attribute Summary collapse

Instance Method Summary collapse

Methods included from Util

#bin_to_hex, #combine_sorted, #decode_hash, #hex_string?, #node_hash?, #normalize_hash

Constructor Details

#initialize(config:, root:, leaf:, siblings:, directions: []) ⇒ Proof

Constructor. only required if sort_hashes is false in config.

Parameters:

  • config (Merkle::Config)
  • root (String)
  • leaf (String)
  • siblings (Array) —

    An array of sibling hashes(64-character hex strings).

  • directions (Array) (defaults to: []) —

    Array of positions at each level(0: left, 1: right),

Raises:

  • (ArgumentError) 


20
21
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
 
# File 'lib/merkle/proof.rb', line 20

def initialize(config:, root:, leaf:, siblings:, directions: [])
  raise ArgumentError, 'config must be a Merkle::Config' unless config.is_a?(Merkle::Config)
  raise ArgumentError, 'root must be string' unless root.is_a?(String)
  raise ArgumentError, "root must be a #{HASH_SIZE * 2}-character hex string" unless node_hash?(root)
  raise ArgumentError, 'leaf must be string' unless leaf.is_a?(String)
  raise ArgumentError, "leaf must be a #{HASH_SIZE * 2}-character hex string" unless node_hash?(leaf)
  raise ArgumentError, 'siblings must be an Array' unless siblings.is_a?(Array)
  raise ArgumentError, "siblings must not exceed #{MAX_SIBLINGS} elements" if siblings.length > MAX_SIBLINGS
  siblings.each do |sibling|
    raise ArgumentError, 'sibling must be string' unless sibling.is_a?(String)
    raise ArgumentError, "sibling must be a #{HASH_SIZE * 2}-character hex string" unless node_hash?(sibling)
  end
  raise ArgumentError, 'directions must be an Array' unless directions.is_a?(Array)
  raise ArgumentError, 'No directions are required because sorted_hash is enabled' if config.sort_hashes && !directions.empty?
  unless config.sort_hashes
    raise ArgumentError, 'directions must have the same length as siblings' unless directions.length == siblings.length
    raise ArgumentError, 'direction must be 0 or 1' unless directions.all? { |direction| direction == 0 || direction == 1 }
  end
  @config = config
  # Normalize and freeze. The checks above only bind if the arrays cannot grow afterwards:
  # a caller holding the array it passed in could otherwise append past MAX_SIBLINGS, or
  # shorten directions until #valid? reads nil and folds as if the sibling were on the right.
  @root = normalize_hash(root)
  @leaf = normalize_hash(leaf)
  @siblings = siblings.map { |sibling| normalize_hash(sibling) }.freeze
  @directions = directions.dup.freeze
end

Instance Attribute Details

#config ⇒ Object (readonly)

Returns the value of attribute config.



11
12
13
 
# File 'lib/merkle/proof.rb', line 11

def config
  @config
end

#directions ⇒ Object (readonly)

Returns the value of attribute directions.



11
12
13
 
# File 'lib/merkle/proof.rb', line 11

def directions
  @directions
end

#leaf ⇒ Object (readonly)

Returns the value of attribute leaf.



11
12
13
 
# File 'lib/merkle/proof.rb', line 11

def leaf
  @leaf
end

#root ⇒ Object (readonly)

Returns the value of attribute root.



11
12
13
 
# File 'lib/merkle/proof.rb', line 11

def root
  @root
end

#siblings ⇒ Object (readonly)

Returns the value of attribute siblings.



11
12
13
 
# File 'lib/merkle/proof.rb', line 11

def siblings
  @siblings
end

Instance Method Details

#valid? ⇒ Boolean

Verify the proof.

Returns:

  • (Boolean) —

    true if the proof is valid, false otherwise.



50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
 
# File 'lib/merkle/proof.rb', line 50

def valid?
  current = decode_hash(leaf)

  siblings.each_with_index do |sibling, index|
    sibling_bin = decode_hash(sibling)
    
    if config.sort_hashes
      # Sort lexicographically when combining
      combined = combine_sorted(config, current, sibling_bin)
    else
      # Use direction to determine order
      direction = directions[index]
      combined = direction == 0 ? sibling_bin + current : current + sibling_bin
    end
    
    current = config.tagged_hash(combined)
  end

  # Compare the decoded bytes. Comparing the hex would make the result depend on the case
  # the caller happened to write +root+ in, even though both spell the same hash.
  current == decode_hash(root)
end