What is a Merkle Proof?

A Merkle Proof is the mechanism by which a data element can be verified to exist within a dataset. Assume you are given a UTXO, if you can verify its existence within a block, you can verify that its creation has been validated by a miner and the UTXO is indeed legitimate and did at least once contain the funds stated. This reasoning stands since there is no way for its generating transaction to be included in a block if it wasn't valid per the rules of the miner who recorded it in there and the other nodes who accepted it to build upon the block its contained in.

Merkle proofs enable Bitcoin SV businesses and wallets to implement Simplified Payment Verification (SPV), as described in section 8 of the Bitcoin whitepaper. Thanks to the properties of Merkle proofs, SPV allows a transaction recipient to prove that the sender has control of the source funds of the payment they are offering without downloading the entire blockchain. Merchants can safely choose to use SPV rather than waiting for a transaction to be confirmed a number of times before concluding the deal. Where the value of small transactions poses a relatively small risk to the merchant, it is more cost-effective for merchants to accept the SPV than to run their own Bitcoin fully synched block subscriber. Because the block header chain that underpins SPV is relatively small in terms of storage and grows at such a nominal rate (about 4MB per year), a business can use simple hardware to operate with it at a low cost instead of running the bitcoin client and handling all data from the ledger.

A wallet can store all necessary block headers in around 60MB – this covers the entire Blockchain (as of January 2022, with 80 bytes per block and approximately 750,000 blocks in the chain). The total grows linearly at about 4.2MB per year (i.e., it increases by 80 bytes with each block mined, regardless of the size of that block). Contrast this with the hundreds and soon to be thousands of gigabytes required to store the entire chain if SPV were not used.

To perform a Merkle proof, the UTXO in question is provided with its TXID and index within the block as well as the TXID or leaf node it would have been concatenated with originally and the interior node values along the Merkle path that connects the transaction to the Merkle root. The calculations commence from the leaf node layer and each child is concatenated with its adjunct pair that has been provided for the particular layer, where from there you traverse towards the target value which is usually the Merkle root. Depending upon the depth of the Merkle tree, the number of these node values to be provided will vary but it will always be significantly less than providing the entire dataset as the efficiency of the process increases as the depth increases.

In the above Merkle Tree it can be seen which node values need to be calculated against the values provided as Merkle proofs in order to establish and verify the target value of the Merkle root within the block header. By convention the first layer of TXID leaf nodes is labelled layer 0 with the layers increasing toward the root. The first transaction of the block (B1), which will be the coinbase transaction has an index value of 0.