Class: BSV::Transaction::MerklePath

Inherits:
Object
  • Object
show all
Defined in:
lib/bsv/transaction/merkle_path.rb

Overview

A BRC-74 merkle path (BUMP — Bitcoin Unified Merkle Path).

Encodes the proof that a transaction is included in a block by storing the minimum set of intermediate hashes needed to recompute the block’s merkle root from a given transaction ID.

Examples:

Parse a BUMP from hex and compute the merkle root

mp = BSV::Transaction::MerklePath.from_hex(bump_hex)
root_hex = mp.compute_root_hex(txid_hex)

Defined Under Namespace

Classes: PathElement

Instance Attribute Summary collapse

Class Method Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(block_height:, path:) ⇒ MerklePath

Returns a new instance of MerklePath.

Parameters:

  • block_height (Integer) —

    the block height

  • path (Array<Array<PathElement>>) —

    tree levels

Raises:

  • (ArgumentError) —

    if block_height is negative, path is empty, any level is not an Array, or level 0 has no txid-flagged leaf



52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
 
# File 'lib/bsv/transaction/merkle_path.rb', line 52

def initialize(block_height:, path:)
  # F5.10: construction-time invariant checks
  raise ArgumentError, 'block_height must be non-negative' if block_height.negative?
  raise ArgumentError, 'path must be non-empty' if path.empty?

  path.each_with_index do |level, i|
    raise ArgumentError, "path[#{i}] must be an Array" unless level.is_a?(Array)

    level.each_with_index do |elem, j|
      raise ArgumentError, "path[#{i}][#{j}] must be a PathElement" unless elem.is_a?(PathElement)
    end
  end

  raise ArgumentError, 'level 0 of path must contain at least one txid-flagged element' unless path[0].any?(&:txid)

  @block_height = block_height
  @path = path
end

Instance Attribute Details

#block_height ⇒ Integer (readonly)

Returns the block height this merkle path belongs to.

Returns:

  • (Integer) —

    the block height this merkle path belongs to



43
44
45
 
# File 'lib/bsv/transaction/merkle_path.rb', line 43

def block_height
  @block_height
end

#path ⇒ Array<Array<PathElement>> (readonly)

Returns tree levels, each an array of leaves.

Returns:

  • (Array<Array<PathElement>>) —

    tree levels, each an array of leaves



46
47
48
 
# File 'lib/bsv/transaction/merkle_path.rb', line 46

def path
  @path
end

Class Method Details

.from_binary(data, offset = 0) ⇒ Array(MerklePath, Integer)

Deserialise a merkle path from BRC-74 binary format.

Parameters:

  • data (String) —

    binary data

  • offset (Integer) (defaults to: 0) —

    byte offset to start reading from

Returns:

  • (Array(MerklePath, Integer)) —

    the merkle path and bytes consumed



91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
 
# File 'lib/bsv/transaction/merkle_path.rb', line 91

def self.from_binary(data, offset = 0)
  start = offset

  block_height, vi_size = VarInt.decode(data, offset)
  offset += vi_size

  tree_height = data.getbyte(offset)
  offset += 1

  path = Array.new(tree_height) do
    num_leaves, vi_size = VarInt.decode(data, offset)
    offset += vi_size

    leaves = Array.new(num_leaves) do
      leaf_offset, vi_size = VarInt.decode(data, offset)
      offset += vi_size

      flags = data.getbyte(offset)
      offset += 1

      dup = flags.anybits?(0x01)
      is_txid = flags.anybits?(0x02)

      leaf_hash = nil
      unless dup
        leaf_hash = data.byteslice(offset, 32).b
        offset += 32
      end

      PathElement.new(offset: leaf_offset, hash: leaf_hash, txid: is_txid, duplicate: dup)
    end

    leaves.sort_by(&:offset)
  end

  [new(block_height: block_height, path: path), offset - start]
end

.from_hex(hex) ⇒ MerklePath

Deserialise a merkle path from a BRC-74 hex string.

Parameters:

  • hex (String) —

    hex-encoded BUMP data

Returns:



133
134
135
 
# File 'lib/bsv/transaction/merkle_path.rb', line 133

def self.from_hex(hex)
  from_binary(BSV::Primitives::Hex.decode(hex, name: 'merkle path hex')).first
end

.from_tsc(txid:, index:, nodes:, block_height:) ⇒ MerklePath

Construct a MerklePath from a TSC (Bitcoin SV “Transaction Status Check”) merkle proof, as returned by the WhatsOnChain /tx/{txid}/proof/tsc endpoint.

The TSC format gives a flat list of sibling hashes (leaf-to-root order), one per tree level. BRC-74 (BUMP) requires a multi-level structure with explicit tree positions. This method does the conversion. Getting it wrong (e.g. flat array in a single level) produces a BUMP that ARC rejects.

Examples:

Convert a WoC TSC proof

tsc = JSON.parse(woc_response).first
mp = BSV::Transaction::MerklePath.from_tsc(
  txid:         tsc['txOrId'],
  index:        tsc['index'],
  nodes:        tsc['nodes'],
  block_height: 612_251
)
mp.compute_root_hex(tsc['txOrId']) #=> the block's merkle root

Parameters:

  • txid (String) —

    hex-encoded transaction ID in display byte order

  • index (Integer) —

    the transaction’s position in the block

  • nodes (Array<String>) —

    sibling hashes leaf-to-root, each a 32-byte hex string in display byte order, or “*” for a duplicate node

  • block_height (Integer) —

    the block’s height (TSC carries the block hash; the caller must look up the height separately)

Returns:

  • (MerklePath) —

    a BRC-74 merkle path equivalent to the TSC proof



164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
 
# File 'lib/bsv/transaction/merkle_path.rb', line 164

def self.from_tsc(txid:, index:, nodes:, block_height:)
  txid_bytes = [txid].pack('H*').reverse

  # Level 0 always contains the txid leaf.
  level0 = [PathElement.new(offset: index, hash: txid_bytes, txid: true)]

  # A single-tx block has no siblings — the txid IS the merkle root.
  return new(block_height: block_height, path: [level0]) if nodes.empty?

  # Add the txid's direct sibling at level 0.
  level0 << tsc_path_element(nodes[0], index ^ 1)
  level0.sort_by!(&:offset)

  # Levels 1..N-1 each contain one sibling (the BRC-74 minimum).
  upper_levels = nodes[1..].each_with_index.map do |node, i|
    height = i + 1
    [tsc_path_element(node, (index >> height) ^ 1)]
  end

  new(block_height: block_height, path: [level0] + upper_levels)
end

.merkle_tree_parent(left, right) ⇒ String

Compute the parent hash of two sibling nodes.

Parameters:

  • left (String) —

    32-byte left child hash

  • right (String) —

    32-byte right child hash

Returns:

  • (String) —

    32-byte parent hash (double-SHA-256 of concatenation)



237
238
239
 
# File 'lib/bsv/transaction/merkle_path.rb', line 237

def self.merkle_tree_parent(left, right)
  BSV::Primitives::Digest.sha256d(left + right)
end

Instance Method Details

#combine(other) ⇒ self

Merge another merkle path into this one.

Both paths must share the same block height and merkle root. After combining, this path contains the union of all leaves, trimmed to the minimum set required to prove every txid-flagged leaf. The trim matches the TS SDK’s combine behaviour and prevents accumulation of unnecessary sibling hashes across repeated merges.

Parameters:

Returns:

  • (self) —

    for chaining

Raises:

  • (ArgumentError) —

    if block heights or merkle roots differ



347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
 
# File 'lib/bsv/transaction/merkle_path.rb', line 347

def combine(other)
  raise ArgumentError, 'block heights differ' unless @block_height == other.block_height

  root1 = compute_root
  root2 = other.compute_root
  raise ArgumentError, 'merkle roots differ' unless root1 == root2

  max_levels = [@path.length, other.path.length].max
  max_levels.times do |h|
    @path << [] if h >= @path.length
    next if h >= other.path.length

    existing = @path[h].to_h { |e| [e.offset, e] }
    other.path[h].each do |elem|
      # Preserve txid flag when combining: if the incoming leaf is
      # flagged, never downgrade an existing entry.
      if existing.key?(elem.offset)
        existing_elem = existing[elem.offset]
        if elem.txid && !existing_elem.txid
          existing[elem.offset] = PathElement.new(
            offset: existing_elem.offset,
            hash: existing_elem.hash,
            txid: true,
            duplicate: existing_elem.duplicate
          )
        end
      else
        existing[elem.offset] = elem
      end
    end
    @path[h] = existing.values.sort_by(&:offset)
  end

  trim
  self
end

#compute_root(txid = nil) ⇒ String

Recompute the merkle root from this path and a transaction ID.

Parameters:

  • txid (String, nil) (defaults to: nil) —

    32-byte txid in internal byte order (auto-detected if nil)

Returns:

  • (String) —

    32-byte merkle root in internal byte order

Raises:

  • (ArgumentError) —

    if the txid is not found in the path



246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
 
# File 'lib/bsv/transaction/merkle_path.rb', line 246

def compute_root(txid = nil)
  txid ||= @path[0].find(&:hash)&.hash
  return txid if @path.length == 1 && @path[0].length == 1

  indexed = build_indexed_path

  tx_leaf = @path[0].find { |l| l.hash == txid }
  raise ArgumentError, 'the BUMP does not contain the txid' unless tx_leaf

  working = tx_leaf.hash
  index = tx_leaf.offset

  # F5.2: for compound paths where all txids are at level 0 (path.length == 1
  # or upper levels are empty/trimmed), compute up to the height implied by the
  # highest offset present in path[0]. This matches the TS SDK computeRoot logic.
  max_offset = @path[0].map(&:offset).max || 0
  tree_height = [@path.length, max_offset.bit_length].max

  tree_height.times do |height|
    sibling_offset = (index >> height) ^ 1
    sibling = offset_leaf(indexed, height, sibling_offset)

    if sibling.nil?
      # F5.2: single-level path — the sibling may be beyond the tree because
      # this is the last odd node at this height. Bitcoin Merkle duplicates it.
      if @path.length == 1 && (index >> height) == (max_offset >> height)
        working = self.class.merkle_tree_parent(working, working)
        next
      end
      raise ArgumentError, "missing hash at height #{height}"
    end

    working = if sibling.duplicate
                self.class.merkle_tree_parent(working, working)
              elsif sibling_offset.odd?
                self.class.merkle_tree_parent(working, sibling.hash)
              else
                self.class.merkle_tree_parent(sibling.hash, working)
              end
  end

  working
end

#compute_root_hex(txid_hex = nil) ⇒ String

Recompute the merkle root and return it as a hex string.

Parameters:

  • txid_hex (String, nil) (defaults to: nil) —

    hex-encoded txid (display order)

Returns:

  • (String) —

    hex-encoded merkle root (display order)



294
295
296
297
 
# File 'lib/bsv/transaction/merkle_path.rb', line 294

def compute_root_hex(txid_hex = nil)
  txid = txid_hex ? [txid_hex].pack('H*').reverse : nil
  compute_root(txid).reverse.unpack1('H*')
end

#extract(txid_hashes) ⇒ MerklePath

Extract a minimal compound MerklePath covering only the specified transaction IDs.

Given a compound path (e.g. one merged from multiple single-leaf proofs in the same block), this method reconstructs the minimum set of sibling hashes at each tree level for every requested txid, assembles them into a new trimmed compound path, and verifies that the extracted path computes the same merkle root as the source.

The primary use case is Transaction#to_beef: when a BUMP loaded from a proof store carries txid: true flags for transactions that are not part of the current BEEF bundle, extracting only the bundled txids strips the phantom flags (and the now-unneeded sibling nodes) from the serialised output. See issue #302 for background.

Matches the TS SDK’s MerklePath.extract behaviour.

Parameters:

  • txid_hashes (Array<String>) —

    32-byte txids in internal byte order (reverse of display order). To pass hex strings, use txid_hexes.map { |h| [h].pack(‘H*’).reverse }.

Returns:

  • (MerklePath) —

    a new trimmed compound path proving only the requested txids

Raises:

  • (ArgumentError) —

    if txid_hashes is empty, any requested txid is not present in the source path’s level 0, or the extracted path’s root does not match the source root



456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
 
# File 'lib/bsv/transaction/merkle_path.rb', line 456

def extract(txid_hashes)
  raise ArgumentError, 'at least one txid must be provided to extract' if txid_hashes.empty?

  original_root = compute_root
  indexed = build_indexed_path

  # Build a level-0 hash → offset lookup
  txid_to_offset = {}
  @path[0].each do |leaf|
    txid_to_offset[leaf.hash] = leaf.offset if leaf.hash
  end

  max_offset = @path[0].map(&:offset).max || 0
  tree_height = [@path.length, max_offset.bit_length].max

  needed = Array.new(tree_height) { {} }

  txid_hashes.each do |txid|
    tx_offset = txid_to_offset[txid]
    if tx_offset.nil?
      raise ArgumentError,
            "transaction ID #{txid.reverse.unpack1('H*')} not found in the Merkle Path"
    end

    # Level 0: the txid leaf itself + its tree sibling
    needed[0][tx_offset] = PathElement.new(offset: tx_offset, hash: txid, txid: true)
    sib0_offset = tx_offset ^ 1
    unless needed[0].key?(sib0_offset)
      sib = offset_leaf(indexed, 0, sib0_offset)
      needed[0][sib0_offset] = sib if sib
    end

    # Higher levels: just the sibling at each height
    (1...tree_height).each do |h|
      sib_offset = (tx_offset >> h) ^ 1
      next if needed[h].key?(sib_offset)

      sib = offset_leaf(indexed, h, sib_offset)
      if sib
        needed[h][sib_offset] = sib
      elsif (tx_offset >> h) == (max_offset >> h)
        # Rightmost path in a tree whose last leaf has no real sibling —
        # BRC-74 represents this as a duplicate marker.
        needed[h][sib_offset] = PathElement.new(offset: sib_offset, duplicate: true)
      end
    end
  end

  compound_path = needed.map { |level| level.values.sort_by(&:offset) }
  compound = self.class.new(block_height: @block_height, path: compound_path)
  compound.trim

  extracted_root = compound.compute_root
  unless extracted_root == original_root
    raise ArgumentError,
          "extracted path root #{extracted_root.reverse.unpack1('H*')} " \
          "does not match source root #{original_root.reverse.unpack1('H*')}"
  end

  compound
end

#initialize_copy(source) ⇒ void

This method returns an undefined value.

Produce an independent copy: a new MerklePath whose outer path array and each inner level array can be mutated (via #combine, #trim, #extract) without affecting the original. PathElements themselves are immutable and are shared between the original and the copy.

Parameters:

  • source (MerklePath) —

    the MerklePath being copied from



79
80
81
82
 
# File 'lib/bsv/transaction/merkle_path.rb', line 79

def initialize_copy(source)
  super
  @path = source.path.map(&:dup)
end

#to_binary ⇒ String

Serialise the merkle path to BRC-74 binary format.

Returns:

  • (String) —

    binary BUMP data



204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
 
# File 'lib/bsv/transaction/merkle_path.rb', line 204

def to_binary
  buf = VarInt.encode(@block_height)
  buf << [@path.length].pack('C')

  @path.each do |level|
    buf << VarInt.encode(level.length)
    level.each do |leaf|
      buf << VarInt.encode(leaf.offset)
      flags = 0
      flags |= 0x01 if leaf.duplicate
      flags |= 0x02 if leaf.txid
      buf << [flags].pack('C')
      buf << leaf.hash unless leaf.duplicate
    end
  end

  buf
end

#to_hex ⇒ String

Serialise the merkle path to a BRC-74 hex string.

Returns:

  • (String) —

    hex-encoded BUMP data



226
227
228
 
# File 'lib/bsv/transaction/merkle_path.rb', line 226

def to_hex
  to_binary.unpack1('H*')
end

#trim ⇒ self

Remove all internal nodes that are not required by level zero txid-flagged leaves. Assumes the path has at least the minimum set of sibling hashes needed to prove every txid leaf. Leaves each level sorted by increasing offset.

This is the Ruby port of the TypeScript SDK’s MerklePath.trim. It is called implicitly by #combine and #extract and rarely needs to be invoked directly.

Returns:

  • (self) —

    for chaining



396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
 
# File 'lib/bsv/transaction/merkle_path.rb', line 396

def trim
  @path.each { |level| level.sort_by!(&:offset) }

  computed_offsets = []
  drop_offsets = []

  @path[0].each_with_index do |node, i|
    if node.txid
      # level 0 must enable computing level 1 for every txid node
      trim_push_if_new(computed_offsets, node.offset >> 1)
    else
      # Array-index peer — works for well-formed compound BUMPs
      # where level 0 is a sequence of adjacent (txid, sibling) pairs.
      peer_index = node.offset.odd? ? i - 1 : i + 1
      peer = @path[0][peer_index] if peer_index.between?(0, @path[0].length - 1)
      # Drop non-txid level 0 nodes whose peer is also non-txid
      trim_push_if_new(drop_offsets, peer.offset) if peer && !peer.txid
    end
  end

  trim_drop_offsets_from_level(drop_offsets, 0)

  (1...@path.length).each do |h|
    drop_offsets = computed_offsets
    computed_offsets = trim_next_computed_offsets(computed_offsets)
    trim_drop_offsets_from_level(drop_offsets, h)
  end

  self
end

#verify(txid_hex, chain_tracker) ⇒ Boolean

Verify that this merkle path is valid for a given transaction.

Computes the merkle root from the path and txid, then checks it against the blockchain via the provided chain tracker.

For coinbase transactions (offset 0 in the merkle tree), an additional maturity check is performed: the coinbase must have at least 100 confirmations before it is considered spendable/valid.

NOTE: The TS SDK has an inverted coinbase maturity check at MerklePath.ts:378 (‘this.blockHeight + 100 < height`), which rejects mature coinbase transactions and accepts immature ones — the opposite of the intended behaviour. The correct logic is: reject when `current_height - block_height < 100` (immature).

Parameters:

  • txid_hex (String) —

    hex-encoded transaction ID (display order)

  • chain_tracker (ChainTracker) —

    chain tracker to verify the root against

Returns:

  • (Boolean) —

    true if the computed root matches the block at this height



318
319
320
321
322
323
324
325
326
327
328
329
330
331
 
# File 'lib/bsv/transaction/merkle_path.rb', line 318

def verify(txid_hex, chain_tracker)
  txid_bytes = [txid_hex].pack('H*').reverse
  txid_leaf = @path[0].find { |l| l.hash == txid_bytes }

  # Offset 0 in a block's merkle tree is always the coinbase transaction —
  # a Bitcoin protocol invariant. Apply the 100-block maturity check.
  if txid_leaf&.offset&.zero?
    current = chain_tracker.current_height
    return false if current - @block_height < 100
  end

  root_hex = compute_root_hex(txid_hex)
  chain_tracker.valid_root_for_height?(root_hex, @block_height)
end