Merkle trees and their use in Blockchain transaction validation
If you’ve been swatting up on blockchain for any appreciable amount of time, you’ve probably come across Merkle trees. Merkle trees are fundamental to blockchain technology and therefore a basic understanding of how they work is important to anyone looking to expand their knowledge of this space. In this article I’ll share my understanding of the concepts.
Hashing
Before we dive in and look at Merkle trees, you will first need to understand what a hash value (or message digest) is. If you already know this feel free to skip this section. While a full explanation is beyond the scope of this article, at a basic level, a hashing function takes a piece of text as an input, scrambles it using a mathematical algorithm, and produces a result known as a hash value. Given the same input the result will be the same. While hashing functions have many applications, in the context of this article they are useful because two different inputs are highly unlikely to produce the same output. Commonly used hash functions include MD5 (now considered insecure), SHA1, SHA256 and SHA512.
How blockchain data is organised
Blockchain ledgers comprise blocks of data in a fixed order; each subsequent block linked to the one before by a hash pointer, which is a hash of various properties of the block, including its immediate predecessor (only the “genesis” block is missing one of these). This chain of ordered hash values dependent on one-another ensures that peers in a network can reach a consensus about the state of the blockchain, as any differences in any block would lead to a difference in hash pointers from that block forward. A comparison of block hashes at a given block height (the number of a block in a chain, 0, 1, 2 etc) determines if the ledgers are consistent.
Each block is a batch containing a number of transactions. A hash is generated by hashing all the transactions in the block, and then (in proof-of-work) solving some difficult puzzle to produce a final hash pointer for the block.
The problem
Suppose I have a Bitcoin mobile wallet; my wallet tells peers only to broadcast transactions for my wallet address (known as bloom filtering). A peer broadcasts a transaction to me claiming that it is within a particular block. The block pointer may be perfectly valid, but the transaction could have been tampered with. In order to ensure the transaction is valid for that block I need to validate it, and I could do this by repeatedly hashing each transaction in the block (including the hash of the transaction before it) and check that the result matches the block header. Producing a block pointer to validate the transaction requires me to be sent all of the other transactions in that block so I can generate this hash value. It is computationally infeasible to produce the correct hash from a different set of transactions, so this ensures that the transaction is, indeed, in the block (other steps will check to ensure the block itself is valid).
Bitcoin blocks may store upwards of 1,000 transactions. Following the approach I’ve just described means that the payload I receive with my transaction is bloated by data that I have no interest in, beyond validating my transaction of interest. On a mobile device this could severely degrade performance.
Merkle trees
The Merkle tree is a tree structure first proposed by Ralph Merkle in 1979, and is essentially a mash-up of a binary tree and a linked list with some hashing for security. To build a Merkle tree transactions are first paired together (if an odd number of transactions exists then the last is duplicated) based on an agreed approach. A hash is created for each pair. Hashes are then paired up and hashed, the results paired up and hashed, and so on, until eventually a single hash value remains. This is the hash pointer for the block.
Now let’s return to our previous scenario where we received a transaction that we wished to validate. With a Merkle tree the only information we need is the hash of the sibling of the transaction, and the hash of each sibling up the branch to the hash pointer. We need only recompute this branch to produce a hash pointer than matches the one we have stored, not the entire tree. This means we no longer need all of those other transactions.
This approach massively reduces the size of the payload we receive, and also results in less computation during the validation step (an improvement of log₂(n) vs n operations, where n is the number of transactions in the block).
Conclusions
While not the most exciting aspect of Blockchain technology, Merkle trees are fundamental to inner workings of the leading blockchain projects. Thanks to Merkle trees crypto wallets are able to run secure validation of transactions efficiently on devices such as mobile, where hardware and networking resources are heavily constrained.
