TL;DR If you already understand hash-linked lists and merkle trees, and how to represent transactions in a Merkle tree, here’s what's discussed in the remainder of the post: A blockchain is simply a hash-linked list of blocks, where each block contains the Merkle root of a tree encoding one or more transactions. Visually, it may look as follows: Each block has a prev field containing the hash value of the previous block (unless it’s the first block in the chain). A root field contains the Merkle root of a tree that encodes the transactions associated with the block. The Merkle tree itself is not part of the blockchain, but it is calculated at run-time to validate the consistency of a given block. The hash functions used in blockchain are usually SHA-256. Note: prev and root may not match the names of the fields in an actual implementation. And for a few details... Hash-linked lists are sometimes referred to as hash chains, but this is a bit confusing, since hash chains are often represented as Merkle trees, so I will avoid that naming convention. In this post I will refer to them as hash-linked lists, until I figure out the proper name for this data structure. The Hash-Linked List A hash-linked list is similar to a normal single-linked list, where instead of pointers, we use the hash of the previous item in the list. This allows the validation of a linked item, by recalculating its hash as needed. Consider the example from the previous diagram: The above list contains three items, ba, bb, and bc. The head item is often called the genesis block in Bitcoin terminology, and the tail is called.. the tail, I think. Suppose we must add an item bd to the list. Given a hash function H(), we must:
The Merkle Tree The Merkle tree was originally proposed by Ralph Merkle in 1979. This data structure is a tree of hashes, widely used in cryptography, and many peer to peer systems. In Bitcoin specifically, the leaves of the Merkle tree are Bitcoin transactions, and the topmost hash (the Merkle root) is stored as part of each block data. A Merkle tree looks similar to the following, with tx(n) being a Bitcoin transaction or some other type of data. To read this tree correctly, start from the bottom, and assume we have eighttransactions (tx(1), tx(2), tx(3), tx(4), and so on) that we want to encode,
If you paid attention, you noticed that this is a binary tree. A Merkle tree is not necessarily a binary tree, but enforcing a binary structure helps minimize the number of hashes needed to reconstruct a given branch. Furthermore, due to its binary nature, it expects an even number of transactions (or data being represented). By convention in Bitcoin, to represent a block with an odd number of transactions, the last item in the block is paired with itself. References: Bitcoin Developer Reference, https://bitcoin.org/en/developer-reference Antonopoulos, A. M. (2017). Mastering bitcoin: programming the open blockchain. Bejing: OReilly.
0 Comments
|
ArchivesCategories
All
|