Class: Bitcoin::PartialTree

Inherits:
Object
  • Object
show all
Defined in:
lib/bitcoin/partial_tree.rb

Overview

A class for recovering partial from merkleblock message. For a complete Merkle tree implementation, migrate to the merkle gem.

Defined Under Namespace

Classes: Node

Constant Summary collapse

MAX_TX_COUNT =

The maximum number of transactions a block can contain, so the maximum tx_count a valid merkleblock message can commit to.

MAX_BLOCK_WEIGHT / MIN_TRANSACTION_WEIGHT

Instance Attribute Summary collapse

Class Method Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(root = nil) ⇒ PartialTree

Returns a new instance of PartialTree.



13
14
15
 
# File 'lib/bitcoin/partial_tree.rb', line 13

def initialize(root = nil)
  @root = root
end

Instance Attribute Details

#root ⇒ Object

Returns the value of attribute root.



11
12
13
 
# File 'lib/bitcoin/partial_tree.rb', line 11

def root
  @root
end

Class Method Details

.build(tx_count, hashes, flags) ⇒ Bitcoin::PartialTree

https://bitcoin.org/en/developer-reference#creating-a-merkleblock-message

Parameters:

  • tx_count (Integer) —

    The number of transactions in the block.

  • hashes (Array) —

    Array of hash values with hex format.

  • flags (String) —

    The sequence of bits, a string of '0' and '1'.

Returns:

Raises:

  • (ArgumentError) —

    If the given parameters are out of range or inconsistent.



27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
 
# File 'lib/bitcoin/partial_tree.rb', line 27

def self.build(tx_count, hashes, flags)
  validate!(tx_count, hashes, flags)
  flags = flags.each_char.map(&:to_i)
  root = build_initial_tree( Array.new(tx_count) { Node.new })
  current_node = root
  hash_index = 0
  flags.each do |f|
    current_node.flag = f
    if f.zero? || current_node.leaf?
      current_node.value = hashes[hash_index]
      hash_index += 1
    end
    current_node = current_node.next_partial
    if hash_index == hashes.size
      if current_node&.leaf?
        current_node.value = hashes.last
      end
      break
    end
  end
  new(root)
end

.build_initial_tree(nodes) ⇒ Object

Raises:

  • (ArgumentError) 


64
65
66
67
68
69
70
71
72
73
74
75
 
# File 'lib/bitcoin/partial_tree.rb', line 64

def self.build_initial_tree(nodes)
  raise ArgumentError, 'nodes must not be empty.' if nodes.empty?
  while nodes.size != 1
    nodes = nodes.each_slice(2).map { |m|
      parent = Node.new
      parent.left = m[0]
      parent.right = m[1] ? m[1] : m[0].dup
      parent
    }
  end
  nodes.first
end

.validate!(tx_count, hashes, flags) ⇒ Object

Validate the parameters of a partial merkle tree. A merkleblock message is received from an untrusted peer, so these bounds are required to stop it from making #build allocate an unbounded number of nodes or loop forever. See Bitcoin Core's CPartialMerkleTree::ExtractMatches.

Raises:

  • (ArgumentError) 


55
56
57
58
59
60
61
62
 
# File 'lib/bitcoin/partial_tree.rb', line 55

def self.validate!(tx_count, hashes, flags)
  raise ArgumentError, 'tx_count must be greater than 0.' unless tx_count.is_a?(Integer) && tx_count > 0
  raise ArgumentError, "tx_count must be less than or equal to #{MAX_TX_COUNT}." if tx_count > MAX_TX_COUNT
  # There can never be more hashes provided than one for every txid.
  raise ArgumentError, 'hashes must not be greater than tx_count.' if hashes.size > tx_count
  # There must be at least one bit per node in the partial tree, and at least one node per hash.
  raise ArgumentError, 'flags must have at least one bit per hash.' if flags.size < hashes.size
end

Instance Method Details

#find_node(value) ⇒ Object 



77
78
79
 
# File 'lib/bitcoin/partial_tree.rb', line 77

def find_node(value)
  root.find_node(value)
end

#merkle_root ⇒ Object 



17
18
19
 
# File 'lib/bitcoin/partial_tree.rb', line 17

def merkle_root
  root.value
end