Class: Merkle::AbstractTree

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

Overview

Base class for Merkle tree implementations

Direct Known Subclasses

AdaptiveTree, BinaryTree, CustomTree

Constant Summary

Constants included from Util

Util::HASH_SIZE, Util::MAX_DEPTH

Instance Attribute Summary collapse

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:) ⇒ AbstractTree

Constructor

Parameters:

  • config (Merkle::Config) —

    Configuration for merkle tree.

  • leaves (Array) —

    An array of leaves.

Raises:

  • (ArgumentError) 


14
15
16
17
18
19
20
21
 
# File 'lib/merkle/abstract_tree.rb', line 14

def initialize(config:, leaves: )
  raise ArgumentError, 'config must be Merkle::Config' unless config.is_a?(Merkle::Config)
  raise ArgumentError, 'leaves must be Array' unless leaves.is_a?(Array)
  @config = config
  # Copy, so that the array the caller keeps cannot change this tree's root behind its back.
  @leaves = leaves.dup
  validate_leaves!
end

Instance Attribute Details

#config ⇒ Object (readonly)

Returns the value of attribute config.



8
9
10
 
# File 'lib/merkle/abstract_tree.rb', line 8

def config
  @config
end

#leaves ⇒ Object (readonly)

Returns the value of attribute leaves.



8
9
10
 
# File 'lib/merkle/abstract_tree.rb', line 8

def leaves
  @leaves
end

Class Method Details

.from_elements(config:, elements:) ⇒ Object

Create tree from elements. For each element in elements, we compute a tagged hash, which becomes the leaf value. The resulting leaves are hex strings, the same representation as leaves passed to #initialize. The tag used for the leaf hash comes from config.leaf_tag.

Parameters:

  • config (Merkle::Config) —

    Configuration for merkle tree.

  • elements (Array) —

    An array of element that will be hashed to become leaves.

Raises:

  • (ArgumentError) 


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

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)
  leaves = elements.map do |element|
    config.tagged_hash(config.encode_element(element), config.leaf_tag).unpack1('H*')
  end
  self.new(config: config, leaves: leaves)
end

Instance Method Details

#compute_root ⇒ String

Compute merkle root.

Returns:

  • (String) —

    merkle root (hex value). For Bitcoin, the endianness of this value must be reversed.

Raises:



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

def compute_root
  raise Error, 'leaves is empty' if leaves.empty?
  nodes = leaves.map {|leaf| decode_hash(leaf) }
  while nodes.length > 1
    nodes = build_next_level(nodes)
  end
  root = nodes.first
  root.unpack1('H*')
end

#generate_proof(leaf_index) ⇒ Merkle::Proof

Generates a merkle proof for the specified leaf_index.

Parameters:

  • leaf_index (Integer) —

    The leaf index.

Returns:

Raises:

  • (ArgumentError) —

    If invalid leaf_index specified.



55
56
57
58
59
60
61
62
63
 
# File 'lib/merkle/abstract_tree.rb', line 55

def generate_proof(leaf_index)
  raise ArgumentError, 'leaf_index must be Integer' unless leaf_index.is_a?(Integer)
  raise ArgumentError, 'leaf_index out of range' if leaf_index < 0 || 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: leaves[leaf_index], siblings: siblings, directions: directions)
end