Class: Merkle::CustomTree

Inherits:
AbstractTree show all
Defined in:
lib/merkle/custom_tree.rb

Overview

Custom Merkle tree implementation that allows specifying the tree structure Example: [leaf_A, [leaf_B, leaf_C], [leaf_D, leaf_E], leaf_F]

Constant Summary

Constants included from Util

Util::HASH_SIZE, Util::MAX_DEPTH

Instance Attribute Summary

Attributes inherited from AbstractTree

#config, #leaves

Class Method 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:, leaves:) ⇒ CustomTree

Constructor

Parameters:

  • config (Merkle::Config) —

    Configuration for merkle tree.

  • leaves (Array) —

    A nested array representing the tree structure. Each element can be a leaf hash (hex string) or an array of child nodes.



10
11
12
 
# File 'lib/merkle/custom_tree.rb', line 10

def initialize(config:, leaves:)
  super(config: config, leaves: leaves)
end

Class Method Details

.from_elements(config:, elements:) ⇒ Object

Create tree from elements with custom structure The tag used for the leaf hash comes from config.leaf_tag.

Parameters:

  • config (Merkle::Config) —

    Configuration for merkle tree.

  • elements (Array) —

    A nested array of elements that will be hashed to become leaves.

Raises:

  • (ArgumentError) 


18
19
20
21
22
23
24
25
26
27
 
# File 'lib/merkle/custom_tree.rb', line 18

def self.from_elements(config:, elements:)
  raise ArgumentError, 'config must be Merkle::Config' unless config.is_a?(Merkle::Config)
  raise ArgumentError, 'elements must be Array' unless elements.is_a?(Array)

  # Convert elements to hashes while preserving structure. This walks the input before the
  # constructor gets to check it, so it has to enforce the depth limit itself.
  hashed_structure = convert_elements_to_hashes(elements, config)

  self.new(config: config, leaves: hashed_structure)
end

Instance Method Details

#compute_root ⇒ String

Compute merkle root using custom structure

Returns:

  • (String) —

    merkle root

Raises:



31
32
33
34
35
36
37
38
39
 
# File 'lib/merkle/custom_tree.rb', line 31

def compute_root
  # Re-check here rather than trusting the constructor. +leaves+ is readable and its arrays
  # are mutable, so a structure that was rejected at construction can be assembled afterwards.
  validate_leaves!
  all_leaves = extract_leaves(@leaves)
  raise Error, 'leaves is empty' if all_leaves.empty?
  result = compute_node_hash(@leaves)
  result.unpack1('H*')
end

#generate_proof(leaf_index) ⇒ Object

Override generate_proof to work with nested structure

Raises:

  • (ArgumentError) 


85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
 
# File 'lib/merkle/custom_tree.rb', line 85

def generate_proof(leaf_index)
  # Walking the structure before checking it would hit the recursion limit on a structure
  # assembled after construction, and SystemStackError escapes the caller's rescue.
  validate_leaves!
  all_leaves = extract_leaves(@leaves)
  raise ArgumentError, 'leaf_index must be Integer' unless leaf_index.is_a?(Integer)
  raise ArgumentError, 'leaf_index out of range' if leaf_index < 0 || all_leaves.length <= leaf_index

  siblings, directions = siblings_with_directions(leaf_index)
  siblings = siblings.map { |sibling| bin_to_hex(sibling) }
  directions = [] if config.sort_hashes

  Proof.new(
    config: config,
    root: compute_root,
    leaf: all_leaves[leaf_index],
    siblings: siblings,
    directions: directions
  )
end