Merkle tree ethereum bitcoin
Announcing World Trade Francs: The Official Ethereum Stablecoin 01st April, Ethereum scalability research and development subsidy programs 02nd January, Merkle trees are a fundamental part of what makes blockchains tick. Although it is definitely theoretically possible to make a blockchain without Merkle trees, simply by creating giant block headers that directly contain every transaction, doing so poses large scalability challenges that arguably puts the ability to trustlessly use blockchains out of the reach of all but the most powerful computers in the long term.
Thanks to Merkle trees, it is possible to build Ethereum nodes that run on all computers and laptops large and small, smart phones, and even internet of things devices such as those that will be produced by Slock. So how exactly do these Merkle trees work, and what value do they provide, both now and in the future?
The most common and simple form of Merkle tree is the binary Mekle tree, where a bucket always consists of two adjacent chunks or hashes; it can be depicted as follows:.
So what is the benefit of this strange kind of hashing algorithm? Why not just concatenate all the chunks together into a single big chunk and use a regular hashing algorithm on that? The answer is that it allows for a neat mechanism known as Merkle proofs:. Someone reading the proof can verify that the hashing, at least for that branch, is consistent going all the way up the tree, and therefore that the given chunk actually is at that position in the tree.
The application is simple: Then, a user who wants to do a key-value lookup on the database eg. It allows a mechanism for authenticating a small amount of data, like a hash, to be extended to also authenticate large databases of potentially unbounded size. The original application of Merkle proofs was in Bitcoin, as described and created by Satoshi Nakamoto in The Bitcoin blockchain uses Merkle proofs in order to store the transactions in every block:.
If the light client wants to determine the status of a transaction, it can simply ask for a Merkle proof showing that a particular transaction is in one of the Merkle trees whose root is in a block header for the main chain.
This gets us pretty far, but Bitcoin-style light clients do have their limitations. One particular limitation is that, while they can prove the inclusion of transactions, they cannot prove anything about the current state eg.
How many bitcoins do you have right now? To get around this, Ethereum takes the Merkle tree concept one step further. Every block header in Ethereum contains not just one Merkle tree, but three trees for three kinds of objects:. This allows for a highly advanced light client protocol that allows light clients to easily make and get verifiable answers to many kinds of queries:.
The first is handled by the transaction tree; the third and fourth are handled by the state tree, and the second by the receipt tree. The first four are fairly straightforward to compute; the server simply finds the object, fetches the Merkle branch the list of hashes going up from the object to the tree root and replies back to the light client with the branch.
The fifth is also handled by the state tree, but the way that it is computed is more complex. Here, we need to construct what can be called a Merkle state transition proof. To compute the proof, the server locally creates a fake block, sets the state to S, and pretends to be a light client while applying the transaction. That is, if the process of applying the transaction requires the client to determine the balance of an account, the light client makes a balance query.
If the light client needs to check a particular item in the storage of a particular contract, the light client makes a query for that, and so on. The server then sends the client the combined data from all of these requests as a proof. The client then undertakes the exact same procedure, but using the provided proof as its database ; if its result is the same as what the server claims, then the client accepts the proof.
For the state tree, however, the situation is more complex. The state in Ethereum essentially consists of a key-value map, where the keys are addresses and the values are account declarations, listing the balance, nonce, code and storage for each account where the storage is itself a tree.
For example, the Morden testnet genesis state looks as follows:. Unlike transaction history, however, the state needs to be frequently updated: What is thus desired is a data structure where we can quickly calculate the new tree root after an insert, update edit or delete operation, without recomputing the entire tree.
There are also two highly desirable secondary properties:. The Patricia treein simple terms, is perhaps the closest that we can come to achieving all of these properties simultaneously. Each node has 16 children, so the path is determined by hex encoding: In practice, there are a few extra optimizations that we can make to make the process much more efficient when the tree is sparse, but that is the basic principle.
The two articles mentioned above describe all of the features in much more detail. A timely article showing clearly that Merkle trees and their variants are the foundation and future of blockchain technology! One question is how to leverage their power to create Ethereum 2. I wrote this article exactly so that I can have something to point to and otherwise just assume background knowledge of Merkle trees for my upcoming article on Ethereum 2.
You may use these HTML tags and attributes: Merkling in Ethereum Introduction. The Official Ethereum Stablecoin 01st April, Ethereum scalability research and development subsidy programs 02nd January, Author Simon Janin Posted at 4: Author Vitalik Buterin Posted at Author bruno cecchini Posted at Author Uri Yurman Posted at Just a small typo in the last paragraph: Author Michael Kilday Posted at Cool explanation of the basics of blockchaining, I never knew this.
Author pardha saradhi kuchipudi Posted at 2: