BRC-71

Merkle Path Binary Format

Storing a proof in a database means keeping it small and quick to read back. This defines a compact binary shape for a single transaction's proof, aimed at storage rather than transmission.

Darren Kellenschwiler31 Aug 2023changed 8 Sept 20231 min read

Why: A JSON merkle proof is verbose and wastes space when many proofs need to be stored, so a tighter binary layout was needed.
What: BRC-71 defines a compact binary encoding for a single merkle path: a transaction index followed by the count and list of 32-byte hashes needed to verify inclusion in a block.
How: A developer writes the transaction's index as a VarInt, then a VarInt count of hash leaves, then each 32-byte leaf hash in order, and reverses the byte order back to hex when reading it out.

What this lets you do

Encode a single merkle path into a small binary buffer
Decode that buffer back into the index and leaf hashes
Store many merkle proofs compactly in a key-value database
Convert between the BRC-58 JSON merkle path format and this binary form

Written by claude-sonnet-5 from the specification text. Where the two differ, the original is correct.

Reference for an AI

Everything an assistant needs to answer questions about BRC-71 accurately, including what it depends on.

The specification

Read the original

Abstract

We propose a binary format for a Single Merkle Path optimized for storage in a key value database.

Copyright

This BRC is licensed under the Open BSV license.

Motivation

The TSC format includes oddities in it for future extensions which are no longer necessary since they are covered by the compound merkle path format defined in BRC-61. So now we attempt to specify the smallest possible encoding of a simple merkle path.

Specification

We take the JSON version from BRC-58 eg.


{ 
   "index": 136,
   "path": [
	"6cf512411d03ab9b61643515e7aa9afd005bf29e1052ade95410b3475f02820c",
	"cd73c0c6bb645581816fa960fd2f1636062fcbf23cb57981074ab8d708a76e3b",
	"b4c8d919190a090e77b73ffcd52b85babaaeeb62da000473102aca7f070facef",
	"3470d882cf556a4b943639eba15dc795dffdbebdc98b9a98e3637fda96e3811e"
    ]
}

Encoding in bytes we start with a VarInt for index, followed by nPath being the number of leaves to follow, followed by 32 byte leaves.

Data Types

Field	Description	Size
index	`VarInt` tx index number from within a block	1-9 bytes
nLeaves	`VarInt` number of leaves which follow	1-9 bytes
leaf	Each leaf of the path is a 32 byte hash	32 bytes x nLeaves

Example

Hex

88040c82025f47b31054e9ad52109ef25b00fd9aaae7153564619bab031d4112f56c3b6ea708d7b84a078179b53cf2cb2f0636162ffd60a96f81815564bbc6c073cdefac0f077fca2a10730400da62ebaebaba852bd5fc3fb7770e090a1919d9c8b41e81e396da7f63e3989a8bc9bdbefddf95c75da1eb3936944b6a55cf82d87034

Bytewise Breakdown

88 // index VarInt
04 // nLeaves
0c82025f47b31054e9ad52109ef25b00fd9aaae7153564619bab031d4112f56c // leaf
3b6ea708d7b84a078179b53cf2cb2f0636162ffd60a96f81815564bbc6c073cd // etc.
efac0f077fca2a10730400da62ebaebaba852bd5fc3fb7770e090a1919d9c8b4
1e81e396da7f63e3989a8bc9bdbefddf95c75da1eb3936944b6a55cf82d87034

Implementation

Let's start by dumping this format as hex into a Buffer and parsing it into an object with a Buffer Reader. Then we construct an object

const { Br } = require('bsv')
const reader = new Br()
reader.buf = Buffer.from('88040c82025f47b31054e9ad52109ef25b00fd9aaae7153564619bab031d4112f56c3b6ea708d7b84a078179b53cf2cb2f0636162ffd60a96f81815564bbc6c073cdefac0f077fca2a10730400da62ebaebaba852bd5fc3fb7770e090a1919d9c8b41e81e396da7f63e3989a8bc9bdbefddf95c75da1eb3936944b6a55cf82d87034', 'hex')

let merklePath = { path: [] }
merklePath.index = reader.readVarIntNum()
let nLeaves = reader.readVarIntNum()
for (x = 0;x < nLeaves; x++) {
  const leaf = reader.read(32).reverse().toString('hex')
  merklePath.path.push(leaf)
}

	
console.log({ merklePath })

Was this helpful?

Summary