Module: Merkle::Util

Included in:
AbstractTree, Config, Proof
Defined in:
lib/merkle/util.rb

Constant Summary collapse

HASH_SIZE =

Size of a node hash in bytes. Leaves, siblings and internal nodes are all this size.

32
MAX_DEPTH =

Deepest tree accepted. A tree deeper than this cannot be walked without risking a SystemStackError, which is not a StandardError and so escapes a caller's rescue. 128 is also the deepest a BIP341 script tree can be.

128

Instance Method Summary collapse

Instance Method Details

#bin_to_hex(data) ⇒ String

Convert binary string data to hex string.

Parameters:

  • data (String)

Returns:

  • (String)

Raises:

  • (ArgumentError) 


65
66
67
68
 
# File 'lib/merkle/util.rb', line 65

def bin_to_hex(data)
  raise ArgumentError, 'data must be string' unless data.is_a?(String)
  data.unpack1('H*')
end

#combine_sorted(config, left, right) ⇒ String

Combine two elements(+left+ and right) with sort configuration.

Parameters:

  • config (Merkle::Config)
  • left (String) —

    Left element(binary format).

  • right (String) —

    Right element(binary format).

Returns:

  • (String) —

    Combined string.

Raises:

  • (ArgumentError) 


76
77
78
79
80
81
82
83
84
85
86
87
 
# File 'lib/merkle/util.rb', line 76

def combine_sorted(config, left, right)
  raise ArgumentError, "config must be Merkle::Config" unless config.is_a?(Merkle::Config)
  raise ArgumentError, "left must be string" unless left.is_a?(String)
  raise ArgumentError, "right must be string" unless right.is_a?(String)
  if config.sort_hashes
    lh = left.unpack1('H*')
    rh = right.unpack1('H*')
    lh < rh ? left + right : right + left
  else
    left + right
  end
end

#decode_hash(hex) ⇒ String

Convert a node hash from its hex representation to binary. Node hashes are always HASH_SIZE bytes written as hex, so anything else is rejected rather than guessed at. Accepting arbitrary lengths here would make the concatenation in an internal node ambiguous: ['aa', 'bbcc'] and ['aabb', 'cc'] would hash alike.

Parameters:

  • hex (String)

Returns:

  • (String) —

    Binary format hash.

Raises:

  • (ArgumentError) 


45
46
47
48
49
 
# File 'lib/merkle/util.rb', line 45

def decode_hash(hex)
  raise ArgumentError, 'hash must be string' unless hex.is_a?(String)
  raise ArgumentError, "hash must be a #{HASH_SIZE * 2}-character hex string" unless node_hash?(hex)
  [hex].pack('H*')
end

#hex_string?(data) ⇒ Boolean

Check whether data is hex string or not. An odd-length string is not a hex string. Treating it as one would let pack('H*') pad the missing nibble with zero, so 'abc' and 'abc0' would collide.

Parameters:

  • data (String)

Returns:

  • (Boolean)

Raises:

  • (ArgumentError) 


19
20
21
22
23
24
25
 
# File 'lib/merkle/util.rb', line 19

def hex_string?(data)
  raise ArgumentError, 'data must be string' unless data.is_a?(String)
  # Match on the bytes. Matching the string itself raises Encoding::CompatibilityError for a
  # UTF-16 string and ArgumentError for invalid UTF-8, neither of which the caller expects.
  bytes = data.b
  bytes.bytesize.even? && bytes.match?(/\A[0-9a-fA-F]+\z/)
end

#node_hash?(hex) ⇒ Boolean

Check whether hex is the hex representation of a node hash.

Parameters:

  • hex (String)

Returns:

  • (Boolean) 


30
31
32
33
34
35
36
 
# File 'lib/merkle/util.rb', line 30

def node_hash?(hex)
  return false unless hex.is_a?(String)
  # Match on the bytes. Matching the string itself raises on a value that claims to be UTF-8
  # but holds invalid bytes, which would surface as an unrelated ArgumentError.
  bytes = hex.b
  bytes.bytesize == HASH_SIZE * 2 && bytes.match?(/\A[0-9a-fA-F]+\z/)
end

#normalize_hash(hex) ⇒ String

Rewrite a node hash in the one spelling the library uses: lower case hex. Upper case names the same hash, so returning it verbatim would let a caller that matches leaves as strings miss a leaf whose proof verifies.

Parameters:

  • hex (String)

Returns:

  • (String) —

    Frozen lower case hex.

Raises:

  • (ArgumentError) 


57
58
59
 
# File 'lib/merkle/util.rb', line 57

def normalize_hash(hex)
  bin_to_hex(decode_hash(hex)).freeze
end