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



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

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



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

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



49
50
51
 
# File 'lib/bsv/transaction/merkle_path.rb', line 49

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



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
128
129
130
 
# File 'lib/bsv/transaction/merkle_path.rb', line 94

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:



136
137
138
 
# File 'lib/bsv/transaction/merkle_path.rb', line 136

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

.from_tsc(dtxid_hex:, 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(
  dtxid_hex:    tsc['txOrId'],
  index:        tsc['index'],
  nodes:        tsc['nodes'],
  block_height: 612_251
)
mp.compute_root_hex(tsc['txOrId']) #=> the block's merkle root

Parameters:

  • dtxid_hex (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



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

def self.from_tsc(dtxid_hex:, index:, nodes:, block_height:)
  BSV::Primitives::Hex.validate_dtxid_hex!(dtxid_hex, name: 'dtxid_hex')
  wtxid = [dtxid_hex].pack('H*').reverse

  # Level 0 always contains the txid leaf.
  level0 = [PathElement.new(offset: index, hash: wtxid, 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)



242
243
244
 
# File 'lib/bsv/transaction/merkle_path.rb', line 242

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



363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
 
# File 'lib/bsv/transaction/merkle_path.rb', line 363

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(wtxid = nil) ⇒ String

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

Parameters:

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

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

Returns:

  • (String) —

    32-byte merkle root in wire byte order

Raises:

  • (ArgumentError) —

    if the wtxid is not found in the path



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
289
290
291
292
293
294
295
296
297
298
 
# File 'lib/bsv/transaction/merkle_path.rb', line 251

def compute_root(wtxid = nil)
  wtxid ||= @path[0].find(&:hash)&.hash
  BSV::Primitives::Hex.validate_wtxid!(wtxid, name: 'wtxid') if wtxid
  BSV.logger&.debug do
    dtxid = wtxid&.reverse&.unpack1('H*')
    "[MerklePath] compute_root: dtxid=#{dtxid} block_height=#{@block_height} levels=#{@path.length}"
  end
  return wtxid if @path.length == 1 && @path[0].length == 1

  indexed = build_indexed_path

  tx_leaf = @path[0].find { |l| l.hash == wtxid }
  raise ArgumentError, 'the BUMP does not contain the given wtxid' 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(dtxid_hex = nil) ⇒ String

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

Parameters:

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

    hex-encoded txid (display order)

Returns:

  • (String) —

    hex-encoded merkle root (display order)



304
305
306
307
308
 
# File 'lib/bsv/transaction/merkle_path.rb', line 304

def compute_root_hex(dtxid_hex = nil)
  BSV::Primitives::Hex.validate_dtxid_hex!(dtxid_hex, name: 'compute_root_hex dtxid_hex') if dtxid_hex
  wtxid = dtxid_hex ? [dtxid_hex].pack('H*').reverse : nil
  compute_root(wtxid).reverse.unpack1('H*')
end

#extract(wtxid_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:

  • wtxid_hashes (Array<String>) —

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

Returns:

  • (MerklePath) —

    a new trimmed compound path proving only the requested txids

Raises:

  • (ArgumentError) —

    if wtxid_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



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
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
 
# File 'lib/bsv/transaction/merkle_path.rb', line 472

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

  original_root = compute_root
  indexed = build_indexed_path

  # Build a level-0 hash → offset lookup
  wtxid_to_offset = {}
  @path[0].each do |leaf|
    wtxid_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) { {} }

  wtxid_hashes.each do |wtxid_hash|
    tx_offset = wtxid_to_offset[wtxid_hash]
    if tx_offset.nil?
      raise ArgumentError,
            "wtxid #{wtxid_hash.reverse.unpack1('H*')} not found in the Merkle Path"
    end

    # Level 0: the transaction leaf itself + its tree sibling
    needed[0][tx_offset] = PathElement.new(offset: tx_offset, hash: wtxid_hash, 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



82
83
84
85
 
# File 'lib/bsv/transaction/merkle_path.rb', line 82

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



209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
 
# File 'lib/bsv/transaction/merkle_path.rb', line 209

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



231
232
233
 
# File 'lib/bsv/transaction/merkle_path.rb', line 231

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



412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
 
# File 'lib/bsv/transaction/merkle_path.rb', line 412

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(dtxid_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:

  • dtxid_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



329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
 
# File 'lib/bsv/transaction/merkle_path.rb', line 329

def verify(dtxid_hex, chain_tracker)
  BSV::Primitives::Hex.validate_dtxid_hex!(dtxid_hex, name: 'dtxid_hex')
  wtxid = [dtxid_hex].pack('H*').reverse
  tx_leaf = @path[0].find { |l| l.hash == wtxid }

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

  root_hex = compute_root_hex(dtxid_hex)
  valid = chain_tracker.valid_root_for_height?(root_hex, @block_height)
  BSV.logger&.debug do
    "[MerklePath] verify: dtxid=#{dtxid_hex} height=#{@block_height} root=#{root_hex} valid=#{valid}"
  end
  valid
end