BRC-58

Merkle Path JSON format

A lightweight client asking a service for proof that a transaction is in a block needs that proof in a form it can read over an ordinary web request. This gives it a plain readable shape rather than raw bytes.

Darren Kellenschwiler27 Apr 2023changed 8 Sept 20233 min read

Why: An earlier format for proving a transaction is in a block mixed several conflicting ideas into one structure, making it ambiguous to implement or trust.
What: BRC-58 defines a clean JSON structure, called a Merkle Path, for the list of sibling hashes and index needed to recompute a block's merkle root from a transaction id.
How: A service keys the object by the transaction's 32 byte hex id and returns an index number plus a path array of hex encoded sibling hashes, which a client hashes upward pairwise, using the index bits to decide left or right at each step, to arrive at the merkle root.

What this lets you do

Request a compact merkle path for a given transaction id from a lookup service
Recompute a block's merkle root client side from the index and path array
Look up a block header using the recomputed root
Attach block header data separately to form a full merkle proof when needed
Avoid the ambiguous field names used in the older TSC merkle proof format

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-58 accurately, including what it depends on.

The specification

Read the original

Abstract

We present a data model and JSON format for a Merkle Path which will be passed from a Transaction Lookup service to a Lite Client via web API.

Motivation

BRC-10 otherwise known as the TSC Merkle Proof Standardized Format has a few competing ideas baked into it rather than it being a clear standard to be used in one way only. This has lead to an ugly solution which can be ambiguous. This JSON format is a simple recommendation for how we might use a prettier structure in future to clarify the intended use.

The name Merkle Proof suggests that it can on its own prove something. I don't think this is the case as a blockheader is required to validate. Therefore the suggested name is a "Merkle Path".

Specification

A Merkle Path needs to indicate the txid of the transaction in question, but this is assumed to be the key of the object rather than contained within the object itself. Also needed is an index number which indicates position with a block.

The proposed JSON is:

// filename or key is a 32 byte txid in hex

{ 
   "index": 12, // JSON Number - technically has no MAX size
   "path": [
      "...leaf of the merkle path", // hex string 32 bytes
      "...leaf of the merkle path",
      "...leaf of the merkle path",
      "...leaf of the merkle path"
   ]
}

Use

The idea is to use the Merkle Path like so:

Convert all hex string into reverse bytes, txid and all leaves.
Calculate the Merkle root by hashing the txid with each element in the path.
1. Checking the last bit of the index number, if it's 1 then the txid should be on the right workingHash = sha256d([...leaf, ...txid]) else other way around workingHash = sha256d([...txid, ...leaf])
2. Right shift the index number
3. Check the new last bit, if it's 1 then the workingHash should be on the right workingHash = sha256d([...leaf, ...workingHash]) else other way round workingHash = sha256d([...workingHash, ...leaf])
Once all leaves are accumulated into a single hash with the above method - we have the Merkle root which we reverse and convert back into a hex string.
This root can be used to look up a block header.
If the blockheader is part of the longest chain of work then we have a "Merkle Proof" that the tx is included in that block.

Merkle Proof JSON

You would only likely see a Merkle Proof when you are in a position where you have to present evidence to a court for dispute resolution or something to that effect. In day to day use the Merkle Path format detailed above is all that need be kept within the transaction store, the block header information can be kept separately.

// fake data example merkle proof
{
   "txid": "cefffc5415620292081f7e941bb74d11a3188144312c4d7550c462b2a151c64d", 
   "index": 657813,
   "path": [
	"6cf512411d03ab9b61643515e7aa9afd005bf29e1052ade95410b3475f02820c",
	"cd73c0c6bb645581816fa960fd2f1636062fcbf23cb57981074ab8d708a76e3b",
	"b4c8d919190a090e77b73ffcd52b85babaaeeb62da000473102aca7f070facef",
	"3470d882cf556a4b943639eba15dc795dffdbebdc98b9a98e3637fda96e3811e"
   ]
   "block": {
      "header": {
         "version": 536870912,
         "prevBlockHash": "0000000000000000005d2328b618e043d80d0e5cd33f79b8351965305482cb6b",
         "merkleRoot": "d66e56fb408763e36e8622eb56a8a1072ccc606476fe9e0765cca0dff95949b1",
         "creationTimestamp": 1534851560,
         "difficultyTarget": 402787433,
         "nonce": 3785175761,
      },
      "hash": "000000000000000001fc2f61db1087c820da44599a82bda8ede1f3c82f67098c",
      "work": 2305305885491475308752,
      "height": 544379
   }

Discussion

The main difference between this and the TSC Merkle Proof Standard Format is renaming a few labels:

Labels

txOrId is dropped in favor of txid because the ambiguity is unnecessary, and full transactions have their own format considerations to focus on, hence separation of concerns.
nodes are renamed to path because this more accurately describes the specific hashes we are referring to as those without children in a Merkle tree, and also disambiguates between these and bitcoin nodes or network nodes in general. Citing the original Merkle Tree patent we see this referred to as "path", with no mention of nodes anywhere.

Order

The order of items in the JSON is not strict but does imply a better general understanding. As a sentence: This transaction in this block is at index 12 with path... etc.

Was this helpful?

Summary