Merkle proof standardised format
by Steve Shadders on 19 November 2020
Category
Expiry date
Licence
Licensing terms to be announced
Applies to
Miners, Wallets, Service Providers
Standard Stage
0 Draft 0 Internal Review 1 Public Review 0 Published 0 Recommended 0 Withdrawn
Overview

TSC Submission : Merkle proof standardised format.

AttributeDescription
Version0.4
AuthorSteve Shadders
ReviewersJerry Chan, Will Devine, Alex Fauvel, Nithin Mani, Di Qiu, Roger Taylor
Publication Date25/11/2020
Risk Categoriesn/a
Copyright2020, Bitcoin Association
IP GenerationGB2009798.6 – Merkle Proof Standardized Format
Known ImplementationsBitcoin SV Node, mAPI v1.2
Applies ToMiners, Wallets, Service Providers
BRFC IDn/a
Acknowledgementsn/a
StatusPublic Review
VisibilityPUBLIC

Merkle proof standardised format

Background

The Merkle proof is fundamental to the Simplified Payment Verification (SPV) model that underpins bitcoin scaling. For SPV wallets to make use of them, they need to be provided to wallets by miners or other actors who download full blocks. As there is likely to be a wide variety of implementations transmitting and receiving Merkle proofs for various reasons, it simplifies implementations if a standard format is adopted.

Problem Statement

Current prior art is embodied in FilteredBlock p2p messages which make use of a bitvector and a list of hashes. This arrangement is unnecessarily confusing, requiring validation of the proof in reverse, and does not provide an easy mechanism to calculate the positional index of a transaction in the Merkle tree. Additionally, this p2p message is likely to be deprecated in favour of other mechanisms due to the inherent scalability problems of using bloom filters for SPV clients.

To determine the validity of the proof, we will provide a description of the following:

  • a binary and JSON form of the proposed data structure
  • the algorithm.

Methods and Concepts

Composite proofs

It is possible through forward compatible extensions to this data format, to provide multiple proofs in a consolidated form. In the case where two transactions are very close to each other in a block, many of the provided hash nodes are likely to be duplicated. In some cases, it may even be more efficient to provide the base layer of a Merkle sub-tree with a branch connecting the root of that sub-tree to the root of the complete tree. It is arguable that a more efficient consolidated format should be provided that enables normalization of this duplicate data.

We note the following points with respect to this design decision:

  1. The algorithm for validating composite proofs is significantly more complex.
  2. It is expected that most of the use cases will be single proofs.
  3. The current expectation is that most transfers will occur in the context of JSON over REST where it is expected that GZIP compression will be enabled by default
  4. Tests on heavily duplicated proofs have shown negligible differences in sizes after compression for de-duplicated composite data structures and structure where multiple simple proofs are included.

GZIP tests

In this example of a Merkle proof for a 1 terabyte block with an expected 4 billion transactions and an approximate tree depth of 32 layers, we show the resultant size for two proofs where 16 layers overlap.

hashes: 32 * 32 bytes hashes as JSONArray, hashesDup: hashes + hashes
original bytes len - hashes: 1024, hashesDup: 2048
raw bytes len      - hashes: 2178, hashesDup: 4354 // JSON stringified
gzip bytes len     - hashes: 1241, hashesDup: 1274 // JSON stringified then gzipped

As we can see, the difference between the duplicate hashes after GZIP, compared to a single list of non-duplicated hashes, is negligible.

Scope

Simple proofs only

When we take the above into account and note that even in some cases where a small number of proofs are required together that multiple instances of the simple proof are negligibly larger than a single consolidated proof, this specification only addresses the simple case. It does, however, make some design decisions with a view to being able to accommodate a composite proof using the same format with extensions.

Note: The details of the composite proof will be provided as a separate standards document.

Conventions

In this document, we will describe Merkle trees in the context that they are used in Bitcoin, namely, as a tree formed from the list of transaction IDs included in a Bitcoin block, with a Merkle root for that tree included in the block header.

We refer to the layers of Merkle tree from the bottom up, with the layer containing transaction IDs as layer 0.

We index transactions in the tree starting from 0, which represents the coinbase transaction. In the example below, the element is the 5th in the tree with an index of 4.

We designate the nodes c and p with a layer index, i.e., c[n] such that c[0] is the calculated node in layer 0.

c = calculated
p = provided in proof
root is both calculated and provided from block header
tx hash in layer 0 is calculated from transaction

4:              root
            /           \
3:        c               p
       /     \         /     \
2:    p       c       o       o
     / \     / \     / \     / \
1:  o   o   c   p   o   o   o   o
   /\  /\  /\  /\  /\  /\  /\  /\
0: o o o o c p o o o o o o o o o o
           ^
           |
           tx

Execution algorithm

The outcome of the algorithm is proof that a given transaction ID is included in a given block specified by its block header. We do not address the validity of the block header itself in this standard, only whether the proof of inclusion is valid for that header.

By convention we use:

  • n to designate the layer of the tree beginning at n == 0 for the bottom layer containing transaction IDs.
  • i to designate the index of a node in its layer such that the first element in layer n is at i == 0.

Beginning with the candidate transaction:

  1. Calculate the transaction ID: c[0] = sha256d(transaction).
  2. If no pair is provided, we assume that c[0] is the Merkle root and compare it to the root provided in the block header.
  3. If a pair (p[0]) is provided, we must concatenate and hash c[0] and p[0] together to obtain the parent node (c[1]) in the next layer up.
    1. The order is determined by the positional index of c[0].
    2. If indexOf(c[0]) mod 2 == 0 it is an even indexed node in the layer and is a left hand node.
      1. Thus: c[1] = sha256d(concat(c[0], p[0])).
    3. Otherwise it is a right hand node.
      1. Thus: c[1] = sha256d(concat(p[0], c[0])).
  4. Continue this process for each layer (n) of the Merkle tree:
    1. If indexOf(c[n]) mod 2 == 0 it is an even indexed node in the layer and is a left hand node.
      1. Thus: c[n + 1] = sha256d(concat(c[n], p[n])).
    2. Otherwise it is a right hand node.
      1. Thus: c[n + 1] = sha256d(concat(p[n], c[n])).
  5. Upon reaching the final layer, we have calculated the Merkle root and compared it to ensure that it is equal to the provided Merkle root, usually obtained from a Bitcoin block header.
  6. If the calculated Merkle root matches the expected Merkle root, we have proven that the transaction ID c[0] is included in the Merkle tree designated by the provided Merkle root. By extension, if the Merkle root is contained in a block header with a valid proof of work for a chain of blocks we accept as the longest, then we have proven that the transaction is included in that block chain.

Note that in some cases, the provided pair will be identical to the calculated pair. This is expected behaviour when the transaction exists near the right hand edge of the Merkle tree and a corresponding right hand element does not exist. However, if the elements are equal, it should be confirmed that the calculated element c[n] is a left hand node, i.e., indexOf(c[n]) mod 2 == 0.

The alternative condition cannot happen in a Bitcoin Merkle tree. This check guards against the case where the node is near the right hand edge of an incomplete tree where the Merkle proof for a left and right hand node can be the same. This check ensures that the proof fails if the index is not correctly given.

Depth attacks

We note that step 1 is a vital part of the proof process. Without validating that the SHA256 hash is actually derived from a bitcoin transaction, it is possible to send a partial Merkle proof for any node higher up in the tree that will validate correctly.

Required data

We can see from the above description that the following data is required to calculate the Merkle proof:

  1. The transaction that is being proven as included.
  2. The Merkle root of the tree that it is included in, such that it can be compared to the calculated root.
  3. A list of pairs [p[0], ... , p[n]] to the calculated nodes.
  4. Whether each pair is a left or right hand node.
    1. Note that this can be be explicitly provided for each pair, or calculated from the index of the transaction ID in the Merkle tree.

Extension to proof of positional index

We note that if providing the positional index of c[0] is the mechanism used to determine the left/right ordering that if the proof is successful it will also hold as proof of the positional index in the tree with the following additional check, as long as this check never fails:

  • if (indexOf(c[n]) mod 2 == 1) then c[n] != p[n]

Then we can assume that the provided index is correct.

Extension to proof of last element

Extending with an additional check, we can also confirm if c[0] is the last element of the Merkle tree by exploiting the fact that where no right hand pair exists, a copy of the left hand pair is used in its place. The following check will always hold true if the element is last in the tree but will always fail at least once if it is not:

  • if (indexOf(c[n]) mod 2 == 0) then c[n] == p[n];

This effectively serves as a proof of the number of transactions in the block where indexOf(c[0]) == len(layer[0])

Merkle proof data structure

The proposed structure itself generally consists of a flags byte, followed by the positional index of the transaction in the Merkle tree, and a list of 32 bytes hashes. Optionally, we use special encoding for hashes where they are a copy of the matching calculated node. It begins at the bottom of the tree and each additional element is in the next layer up, representing the counterpart pair to the parent of the previous layer. Finally, we reach the root of the Merkle tree.

Binary

  • varint is defined as a Bitcoin varint which is compact for cases where values in the range of 0 – 253 are commonly expected.

node

type: byte, // 0 == hash (byte[32]), 1 == duplicate (byte[0]), 2 == index (varint)
value: byte[32] or varint or byte[0] //determined by type

Note: Type 2 is reserved for use in an extension format. The duplicate type could have been omitted, allowing us to eliminate the type byte entirely from this standard. However, its inclusion does have some potential space benefits whilst making the proposed extension standard fully backward compatible.

merkle_proof

flags: byte,
index: varint,
txLength: varint, //omitted if flag bit 0 == 0 as it's a fixed length transaction ID
txOrId: byte[32 or variable length],
target: byte[32 or 80], //determined by flag bits 1 and 2
nodeCount: varint,
nodes: node[]

JSON

For JSON, we propose simply breaking the elements up into an array of hex values.

// simple version where only a single path is specified

{
   "flags": 0,
   "index": 4,

   "txOrId": "bytes", // hex bytes, 32 if ID, otherwise interpret as full transaction
   "target": "merkleroot_or_blockhash_or_blockheader" // which one is specified by flag bits 1 and 2

   // contains the provided pair nodes to the calculated nodes in the proof.
   // "hash" is a simple hash node
   // integer is an index to a subtree or subpath - only used in extension
   // "*" is a copy of the calculated node e.g. parent = hash (left | left)
   "nodes": ["hash", "hash", "*", ... "hash"],
}

Nodes and duplicated indexes

The standard specifies that hashes and potentially block headers are encoded as hex strings. We use the special string "*" as a marker to indicate that hash is a duplicated node where p[n] hash should be assumed to be a copy of c[n]. We choose this special marker string rather than null for the following reasons:

  1. The encoding is shorter than encoding null but slightly longer than encoding an empty string.
  2. To avoid ambiguity in error cases, it is common for software bugs to produce unexpected null or empty string results. By making null an unexpected result, these errors are easier to detect.

Fields

Flags

There are several choices to be made in a Merkle proof format.

  1. Transaction of TxId: Whether to include the original transaction given that in most cases it will already be known or just the transaction ID.
  2. Target type: Whether the final element should be the Merkle root, the entire block header, the block hash of the block it contains, or omitted completely. In some cases, the Merkle proof may be provided in the context of an envelope data structure (e.g. an SPV envelope) that already contains the missing elements.
  3. Proof type: Whether it is a branch or a tree. The tree option is only used in an extension to this standard but the flag bit is reserved for that purpose.
  4. Composite proof: Whether this proof is part of a set of proofs and contains references to other proofs in the set. This option is only used in an extension to this standard but the flag bit is reserved for that purpose.

The following bits are reserved for each purpose, counted from the right most (least significant) bit:

Transaction or TxId (bit 0)

Corresponds to: (flags & 0x01)

Where value equals:

0: The `txOrId` field contains a transaction ID
1: The `txOrId` field contains a full transaction

Target type (bits 1 and 2):

Corresponds to: (flags & (0x04 | 0x02))

Where value equals:

0: The `target` field contains a block hash
2: The `target` field contains a block header
4: the `target` field contains a merkle root
6: not valid

Proof type (bit 3):

Corresponds to: (flags & 0x08)

Where value equals:

0: Merkle branch (or sub-branch in the extension format)
1: Merkle tree (or sub-tree in the extension format)

Composite proof (bit 4):

Corresponds to: (flags & 0x10)

Where value equals:

0: Single proof
1: Composite proof

Defaults

Note that default values have been selected such that a flag value of 0 means:

  1. The txOrId field contains a transaction ID.
  2. The target field contains a block hash.
  3. The proof is a Merkle branch.
  4. The proof is a single proof that an be validated using the simplest algorithm.

JSON note

In the JSON form of this data structure, the information contained in this flag byte can be implicitly derived from the form of the data itself. However, for clarity and for strict error checking, we use the same flag format.

Although some of the following combinations may not have real use cases, for future proofing, the following version values are reserved:

Index and left/right determination

A complete Merkle proof requires not only the transaction you are proving, but also the transaction ID of its pair. If the transaction index in layer 0 of the tree is i then where i mod 2 == 0 the pair will be at index i + 1. Where i mod 2 == 1 the pair will be at index i - 1. This ordering is required to be maintained when hashing the left/right nodes to calculate the parent. It could optionally also be provided as a flag for each provided node in the tree.

We have chosen to use the positional index rather than left/right flags for the following reasons:

  1. It simplifies the data structure to include only a single integer.
  2. The index in block may be useful in some cases.
  3. The index in block can be proven as part of the Merkle proof.
  4. Calculation of the leftness of rightness of a node along with the indexes of parent nodes during proof execution is trivially simple.
  5. Whilst it is possible to calculate the positional index using left right flags, the calculation is more complex and even in the best cases (assuming 1TB blocks) requires just as much data to be included as is required for the positional index.

Nodes

The nodes field is an array data structure that contains all of the nodes that must be provided as pairs to the calculated nodes. It does NOT include the transaction ID being proven (assumed to be calculated from the transaction) OR the Merkle root (calculated as part of the proof).

Both the binary and the JSON formats specify a mechanism for designating elements of the path that are duplicates, i.e., where the provided element p[n] should be assumed to be a copy of of the calculated element c[n] for that layer of the tree.

Merkle proof validation

In the following example, we will validate a simple Merkle branch type proof. A complete functioning version of this example code is available here: https://github.com/bitcoin-sv-specs/merkle-proof-standard-example.

const bsv = require('bsv')
const { swapEndianness } = require('buffer-swap-endianness')

function VerifyMerkleProof (merkleProof) {
  // flags:

  // Transaction or TxId (bit 0):
  let txid
  if (merkleProof.flags & 1) { // bit 0 is set
    // The `txOrId` field contains a full transaction
    const tx = new bsv.Transaction(merkleProof.txOrId)
    txid = tx.id
  } else { // bit 0 is NOT set
    // The `txOrId` field contains a transaction ID
    txid = merkleProof.txOrId
  }

  // Target type (bits 1 and 2):
  let merkleRoot
  if (merkleProof.flags & 2) { // bit 1 set
    // The `target` field contains a block header
    merkleRoot = merkleProof.target.merkleroot
  } else if (merkleProof.flags & 4) { // bit 2 set
    // the `target` field contains a merkle root
    merkleRoot = merkleProof.target
  } else { // bits 1 & 2 NOT set
    // The `target` field contains a block hash

    // You will need to get the block header corresponding
    // to this block hash in order to get the merkle root
    // from it. You can get this from from the headers
    // store of an SPV client or from a third party
    // provider like WhatsOnChain
    merkleRoot = mapHashToHeader[merkleProof.target].merkleroot
  }

  // flags bits 3 (Proof type) and 4 (Composite proof) not supported in this version

  if (!txid) {
    throw new Error('txid missing')
  }

  if (!merkleRoot) {
    throw new Error('merkleRoot missing')
  }

  const nodes = merkleProof.nodes // different nodes used in the merkle proof
  let index = merkleProof.index // index of node in current layer (will be changed on every iteration)
  let c = txid // first calculated node is the txid of the tx to prove
  let isLastInTree = true

  nodes.forEach(p => {
    // Check if the node is the left or the right child
    const cIsLeft = index % 2 === 0

    // Check for duplicate hash - this happens if the node (p) is
    // the last element of an uneven merkle tree layer
    if (p === '*') {
      if (!cIsLeft) { // this shouldn't happen...
        return { isValidIndex: false, proofValid: false }
      }
      p = c
    }

    // This check fails at least once if it's not the last element
    if (cIsLeft && c !== p) {
      isLastInTree = false
    }

    // Calculate the parent node
    if (cIsLeft) {
      // Concatenate left leaf (c) with right leaf (p)
      c = getMerkleTreeParent(c, p)
    } else {
      // Concatenate left leaf (p) with right leaf (c)
      c = getMerkleTreeParent(p, c)
    }

    // We need integer division here with remainder dropped.
    // Javascript does floating point math by default so we
    // need to use Math.floor to drop the fraction.
    // In most languages we would use: i = i / 2;
    index = Math.floor(index / 2)
  })

  // c is now the calculated merkle root
  return {
    proofValid: c === merkleRoot,
    isLastInTree
  }
}

function getMerkleTreeParent (leftNode, rightNode) {
  // swap endianness before concatenating
  const leftConc = swapEndianness(Buffer.from(leftNode, 'hex'))
  const rightConc = swapEndianness(Buffer.from(rightNode, 'hex'))

  // concatenate leaves
  const concat = Buffer.concat([leftConc, rightConc])

  // hash the concatenation
  const hash = bsv.crypto.Hash.sha256sha256(concat)

  // swap endianness at the end and convert to hex string
  return swapEndianness(Buffer.from(hash, 'hex')).toString('hex')
}

History

ArtefactDescription
Erratan/a
Change Logn/a
Decision Logn/a

Relationships

RelationshipDescription
IP licences and dependenciesLicensing terms to be announced
Previous versionsn/a
Extends (existing standards extended by this standard)n/a
Modifies (existing standards changed by this standard)n/a
Deprecates (existing standards obsoleted by this standard)n/a
Depends On (existing standards that are foundational or prerequisite to this standard)n/a
Prior Artn/a
Existing Solutionn/a
Referencesn/a

Supplementary Material

No supplementary material

Overview
Request for comment

This Standard is at the public review stage. To leave comments, feedbacks or suggestions please register below.

Already have an account? Login
Standard details
  • BRFC ID: n/a
  • Risk Category: n/a
  • IP Generation: GB2009798.6 – Merkle Proof Standardized Format
  • Acknowledgements n/a
  • Sensitivity: PUBLIC
  • Known Implementations: Bitcoin SV Node mAPI v1.2
Become a Contributor
If you wish to join us on this mission to make BSV the public blockchain of choice please fill in our preliminary registration form below. We look forward to having you on board.