Standard: Merkle proof data format

Proposer: Steve Shadders (nChain)
TSC Sponsor: Ryan X Charles (Money Button)
Authors: (proposer by default) Steve Shadders
Reviewers: TBA

Supplementary: As needed, the TSC may appoint users, implementers, technical experts and standards experts to supplementary roles within a working group.

Specialist reviewers: Legal, IP, Compliance

1. Background

  1. Problem statement

    A Merkle proof represents a branch of a Merkle tree with a root typically embedded in a Bitcoin block header. Executing the proof requires the recombination of supplied data elements along with calculated data elements according to a specific algorithm.

    A Merkle proof format needs to define not only the required data, but how to interpret that data in the context of the algorithmic execution.

  2. Objectives/Justification

    The Merkle proof is fundamental to the Simplified Payment Verification (SPV) model described in the original Bitcoin white paper and that underpins Bitcoin scaling. In order for SPV wallets to make use of them, Merkle proofs need to be provided to wallets by miners or other actors that 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 across the ecosystem if a standard format is adopted.

    Current prior art is embodied in FilteredBlock p2p messages which makes use of a bit vector and list of hashes. This arrangement is unnecessarily confusing requiring validation of the proof in reverse as it 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.

  3. Scope

    The most common use case for a Merkle proof is to prove that a transaction has been included in a block which we refer to as a Simplified Payment Verification (SPV). The proof itself may require additional information including the transaction, the index of the transaction in a block and a reference to the block header it is included in.

    Additionally, where a transaction is not yet included in a block or where a Merkle proof for it may not yet be available, the proof can be provided by presenting an unbroken chain of ancestor transactions terminating in a transaction for which a Merkle proof can be supplied. We refer to this extended data set tentatively as an “SPV envelope” containing Merkle proofs and additional data. As such, the SPV envelope is a superset of the Merkle proof format itself.

    Whilst we regard the SPV envelope as integral to meeting industry needs, it should be dealt with separately and is not in the scope of this standard proposal as such a standard can encapsulate the Merkle proof element regardless of how it is formatted.

  4. Benefits

    The TSC mission statement includes the goal to: “improve Bitcoin SV utility by enhancing interoperability through standardization.” Merkle proofs sit at the core of peer to peer interactions on Bitcoin. By definition, such interaction requires interoperation between systems that are likely distinct and unique. As such, the primary benefit of developing a standard Merkle proof data format is in line with the stated goals of the TSC and meets a need that will simplify implementation across the ecosystem of a fundamentally primitive SPV operation.

  5. Deliverable

    A standards document describing a data format and accompanying execution algorithm for receiving and executing a Merkle proof.

    The standard should describe the format in a way that can be implemented in both a binary and human readable format.

2. Brief workgroup process description

External: Call for expressions of interest to serve on review panel

Internal: Draft >> Review >> Iterate (if required)

Internal: Specialist review (legal, IP, Compliance) >> Iterate to draft (if required)

External: Public review >> respond to comments >> Iterate to draft (if required)

External: Ratification by TSC

3. Reviewer selection

Note that a public review process open to anyone who wishes to provide input is a later part of this standards development process.

  1. Criteria

    Persons wishing the apply to join this TSC workgroup review panel should meet the following criteria:

    • Can demonstrate at least one of the following:
      1. Subject matter expertise in the standard proposal’s specific domain
        • Bachelor’s degree or equivalent experience in a relevant field of study
          • e.g. Engineering, Computer Science, Mathematics, other relevant science fields
      2. Are a key stakeholder in the outcomes of this standard either as an existing or future user or implementer of the standard
      3. Have significant experience in standards development associated with an internationally recognised standards institution
    • Are willing to sign an NDA for the duration of the workgroup lifecycle
    • Have sufficient time to commit to the review process over the expected lifetime of the workgroup (as a guideline, workgroup life cycles are expected to be in the range of 3-4 months and would typically require several days review work split across 2-3 iterations of a draft standard)
  2. Application

    Application to participate in the internal development phase of this standard can be made by addressing the above criteria in an email to: [email protected]. Applications must be received by 3 July 2020.