Merkle Trees and SPV

Date: 2019-11-02

Source: https://craigwright.net/blog/bitcoin-blockchain-tech/merkle-trees-and-spv

---

Merkle Trees

By now, it should be well understood that Bitcoin utilises the concept of a Merkle tree to its advantage; by way of background, we provide an explanation in this post.  The following aids as a technical description and definition of similar concepts used more generally in Bitcoin and specifically within SPV; read the necessary background information here.

Such techniques form an important component in implementing SPV in an efficient and secure manner, allowing us to scale and effectively implement a verification solution that provides true peer-to-peer transactioning.

Simplified Payment Verification (SPV)

I’ll start by describing the base of any SPV system. In order to do so, we shall provide an overview of SPV verification techniques for ease of reference.

In what follows, we consider Alice (a customer) and Bob (a merchant) who wish to transact at the point of sale of some goods.  We examine how the interaction takes place using simplified payment verification (SPV) using the traditional method, as outlined in the Nakamoto white paper (Bitcoin: A Peer-to-Peer Electronic Cash System, Craig Wright, [2008]).  The same interaction is described later in respect of an illustrative embodiment of the present invention, in the section entitled Overview of the Invention.  In both cases, we consider the role of three blockchain transactions (Txs). Two transactions have spendable outputs (UTXOs) owned by Alice:

• Tx1– a transaction with a spendable output (vout-1)
• Tx2– a transaction with a spendable output (vout-0)

The transactions Tx1, Tx2 will be referred to herein as input transactions, as a concise way of saying that they are transactions comprising outputs that are being spent by the inputs of some subsequent transaction, that is, a Tx3.

The third blockchain transaction is the payment transaction:

• Tx3 – a transaction using vout-0 and vout-1 as its two inputs and one output paying to Bob. There are only two inputs and one output for simpler demonstration of the invention.

The three transactions, along with the Merkle paths which can be used to relate them to blocks (headers), are shown schematically in the following figure.

The basic concept of SPV has existed since I released the Bitcoin white paper, and the rudimentary concept, though not fully developed, was a part of the original Bitcoin protocol.  In essence, SPV makes use of two properties of the Bitcoin blockchain:

• Merkle proofs that can be used to easily verify that a given transaction is included in a Merkle tree and represented by a Merkle root; and
• Block headers that represent blocks of transactions by including the Merkle root of a Merkle tree of transactions.

By combining the two properties, a lightweight Bitcoin client need only maintain a copy of the block headers for the entire blockchain—rather than blocks in full—to verify that a transaction has been processed by the network.  To verify that a given transaction has been processed and included in a block, an SPV client requires only:

• a full list of up-to-date block headers; and
• the Merkle path for the transaction in question.

It follows from property 1 that the SPV user can verify that the given transaction is part of a Merkle tree—represented by a Merkle root—simply by performing a Merkle-path authentication proof as explained in the section above.  It then follows from property 2 that the transaction is also part of a block in the blockchain if the SPV client has a valid block header that includes the Merkle root.  Performing the same type of payment verification in Bitcoin will be referred to herein as performing an SPV check.

The SPV mechanism as specified by Nakamoto informs the existing method of SPV-client implementation, including at the point of sale.  Importantly, the state of the art in SPV implementation is based on the paradigm whereby a user verifies that a payment has been received by confirming (to a suitable depth on the blockchain, e.g., 6 blocks) that it has been included in a block.  In effect, it is a post-broadcast check on a transaction to verify that it has been mined.

In contrast, the present invention requires that the necessary SPV check be performed on a transaction’s inputs prior to its broadcast.  The shift in emphasis greatly reduces the burden and traffic on the network in dealing with invalid transactions.

A second important paradigm in the existing SPV system is that an SPV client must query full nodes on the network to obtain the Merkle path required for the SPV check.  It can be seen in the Bitcoin implementation where it has been noted that “the SPV client knows the Merkle root and associated transaction information, and requests the respective Merkle branch from a full node”.

SPV checks that remove such burden on the network, by stipulating the lightweight Bitcoin client where users keep, maintain, or at least have access to their own copies of Merkle paths pertinent to the unspent transaction outputs owned by them, allow Bitcoin to scale.

In the following, I will detail the traditional understanding of the method used in implementing SPV (at the point of transaction):

[1] MESSAGE: Bob to Alice

• Bob (merchant) sends Alice (customer) his public-key address. His message may also include the amount that is to be paid, in addition to any other spending conditions provided as the hash of Bob’s chosen redeem script.
• Alice also communicates the transaction ID TxID3 of the payment transaction Tx3 to Bob (not shown).

[2] The P2P network mediates the exchange between Alice and Bob:

[2.i] MESSAGE: Alice to P2P network

• Alice broadcasts Tx3 to the network.

[2.ii] MESSAGE: Bob to P2P network

• Bob queries the network to check whether Tx3 is accepted for mining into the blockchain.
• Bob sends continuous queries [2.ii], until he is satisfied the payment is deemed valid by the network. Note that he may begin querying before [2.i] has occurred.
• If Bob is satisfied, he may treat the transaction as complete without either party waiting for the next block to be mined.

[3] SPV CHECK (MESSAGE): Bob to P2P network

• Bob waits for the next block to be mined, and downloads new block headers as they are broadcast on the network.
• Bob sends an ‘SPV check’ request to the network, for the Merkle path corresponding to Tx3, that links it to the Merkle root in a recently mined block.
• If the network can provide Bob with the Merkle path, he can compute the Merkle proof himself using his SPV wallet and check the payment Tx3 has been processed.

It should be noted that [2.i], [2.ii], and [3] are mediated by the P2P network and thus contribute to traffic on the network.  It should also be noted that in the existing SPV paradigm, the necessary SPV check [3] is performed:

• after the payment (Tx3) is submitted;
• on the payment (Tx3) itself; and
• with the help of other network peers who provide Merkle paths.

In following blog posts and by linking back to my prior post on SPV, I shall contrast the existing paradigm and the errors that have been made in the understanding of how SPV was designed with how SPV can be implemented efficiently and effectively.

---

← Back to archive