Skip to content

Latest commit

 

History

History
86 lines (66 loc) · 4.52 KB

0058.md

File metadata and controls

86 lines (66 loc) · 4.52 KB
Raw

BRC-58: Merkle Path Data Model

Deggen ([email protected])

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:

  1. Convert all hex string into reverse bytes, txid and all leaves.
  2. 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])
  3. 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.
  4. This root can be used to look up a block header.
  5. 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.