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

Instance Attribute Summary collapse

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

Constructor

Parameters:

  • config (Merkle::Config) —

    Configuration for merkle tree.

  • leaves (Array) —

    An array of leaves.

Raises:

  • (ArgumentError) 


14
15
16
17
18
19
 
# 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
  @leaves = 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:, leaf_tag: '') ⇒ Object

Create tree from elements. For each element in elements, we compute a tagged hash, which becomes the leaf value.

Parameters:

  • config (Merkle::Config) —

    Configuration for merkle tree.

  • elements (Array) —

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

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

    An optional tag to use when computing the leaf hash.

Raises:

  • (ArgumentError) 


26
27
28
29
30
31
32
33
34
 
# File 'lib/merkle/abstract_tree.rb', line 26

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)
  leaves = elements.map do |element|
    config.tagged_hash(element, leaf_tag)
  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:



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

def compute_root
  raise Error, 'leaves is empty' if leaves.empty?
  # nodes = leaves
  nodes = leaves.map {|leaf| hex_to_bin(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.



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

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