Merkle Path Binary Format

Deggen ([email protected])

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 })