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]

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, #hex_string?, #hex_to_bin

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
13
14
 
# File 'lib/merkle/custom_tree.rb', line 10

def initialize(config:, leaves:)
  super(config: config, leaves: leaves)
  # Validate nested structure before calling super
  validate_leaves!(extract_leaves(leaves))
end

Class Method Details

.convert_elements_to_hashes(node, config, leaf_tag) ⇒ Object

Convert nested elements to nested hashes



41
42
43
44
45
46
47
48
 
# File 'lib/merkle/custom_tree.rb', line 41

def self.convert_elements_to_hashes(node, config, leaf_tag)
  if node.is_a?(Array)
    node.map { |child| convert_elements_to_hashes(child, config, leaf_tag) }
  else
    # This is a leaf element, hash it and convert to hex
    config.tagged_hash(node, leaf_tag).unpack1('H*')
  end
end

.from_elements(config:, elements:, leaf_tag: '') ⇒ Object

Create tree from elements with custom structure

Parameters:

  • config (Merkle::Config) —

    Configuration for merkle tree.

  • elements (Array) —

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

  • leaf_tag (String) (defaults to: '') —

    An optional tag to use when computing the leaf hash.

Raises:

  • (ArgumentError) 


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

def self.from_elements(config:, elements:, leaf_tag: '')
  raise ArgumentError, 'config must be Merkle::Config' unless config.is_a?(Merkle::Config)
  raise ArgumentError, 'elements must be Array' unless elements.is_a?(Array)
  raise ArgumentError, 'leaf_tag must be string' unless leaf_tag.is_a?(String)
  
  # Convert elements to hashes while preserving structure
  hashed_structure = convert_elements_to_hashes(elements, config, leaf_tag)
  
  self.new(config: config, leaves: hashed_structure)
end

Instance Method Details

#compute_node_hash(node) ⇒ Object

Compute hash for a node in the structure (binary tree only)



51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
 
# File 'lib/merkle/custom_tree.rb', line 51

def compute_node_hash(node)
  if node.is_a?(Array)
    case node.length
    when 1
      # Single child - just return its hash
      compute_node_hash(node[0])
    when 2
      # Binary node: compute hash of left and right children
      left_hash = compute_node_hash(node[0])
      right_hash = compute_node_hash(node[1])
      
      # Combine hashes according to sort_hashes config
      combined = if config.sort_hashes
        [left_hash, right_hash].sort.join
      else
        left_hash + right_hash
      end
      
      config.tagged_hash(combined)
    else
      raise ArgumentError, "Binary tree nodes must have 1 or 2 children, got #{node.length}"
    end
  else
    # Leaf node: already a hash, convert to binary
    hex_to_bin(node)
  end
end

#compute_root ⇒ String

Compute merkle root using custom structure

Returns:

  • (String) —

    merkle root

Raises:



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

def compute_root
  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) 


80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
 
# File 'lib/merkle/custom_tree.rb', line 80

def generate_proof(leaf_index)
  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