What is it about?
The summary of all transactions of a block in the Bitcoin blockchain is summarized via a so-called Merkle tree (binary hash tree). This is a data structure for the efficient summary of large data sets that are to be checked for integrity.
They contain cryptographic hashes. Merkle trees are used in Bitcoin to summarize all transactions in a block and to provide the data set with a digital fingerprint. This enables efficient proof that a transaction is in a block. In addition, this can also efficiently save storage space in the blockchain.
How does a Merkle tree work in a nutshell?
By recursively hashing node pairs, the so-called Merkle root is hashed at the end, which then represents the only hash that remains. Bitcoin uses the SHA256 hash algorithm which is applied twice.
The Merkle Tree is created from the bottom up and this can be understood in a reverse analogy to the tree. Here the roots are at the top and the leaves at the bottom. The transactions form the leaves. To clarify here, transactions are not stored in the merge tree, but their hash is stored in each leaf node.
Successive pairs of leaf nodes (hashes) are combined into a parent node by joining them together and then hashed in turn.
Example: Hashes of two transactions are 32-byte hashes each. these are joined to form a 64-by string and then the string is hashed twice.Thus, the hash of the parent node is then generated.
This process is repeated until only one node of the Merkle root remains.
Merkle Root is then stored in the block header and thus summarizes all transactions in the block.
The Merkle root is then also only 32 bytes long. With the method, trees of any size can be combined again and again up to a Merkle Root of 32 bytes. This made the mechanism so efficient when you consider that a Bitcoin block can contain up to 1000 transactions. So it really doesn’t matter how many transactions are in a block. Also, the computational effort to check the presence of a data element in the tree is reduced to a maximum of
2xLog2(N) calculations.
Interesting reference sources
Sources that are also mentioned in the Bitcoin whitepaper
R.C. Merkle, “Protocols for public-key cryptosystems,” In Proc. 1980 Symposium on Security and
Privacy, IEEE Computer Society, pages 122-133, April 1980.
S. Haber, W.S. Stornetta, “Secure names for bit-strings,” In Proceedings of the 4th ACM Conference
on Computer and Communications Security, pages 28-35, April 1997.
H. Massias, X.S. Avila, and J.-J. Quisquater, “Design of a secure timestamp service with minimal
Trust Requirements,” 20th Benelux Symposium on Information Theory, May 1999.
