.jpg)
Merkle trees are a key part of what makes blockchain technology effective. Although it is certainly possible in theory to create a blockchain without Merkle trees, simply by creating giant block headers that directly contain every transaction, doing so poses significant scalability challenges that arguably compromise the ability to use a blockchain reliably. Out of reach of all but most people. Powerful computers for the long term. Thanks to Merkle trees, it is possible to build Ethereum nodes that run on all computers and laptops large and small, smartphones, and even IoT devices like the ones that will be produced by Slock.it. So how exactly do these Merkel Trees work, and what value do they provide, now and in the future?
First, the basics. A Merkel tree, in the most general sense, is a method of hashing a large number of “parts” of data together which relies on dividing the parts into groups, where each group contains only a few parts, then taking the hash of each group and repeating the same process, continuing to do so until There is only one remaining hash in total: the root hash.
The most common and simple form of a Merkle tree is a binary Mekle tree, where a bucket always consists of two adjacent chunks or hashes; It can be depicted as follows:
So what is the use of this strange kind of hashing algorithm? Why don’t we just concatenate all the pieces together into one big chunk and use a regular hashing algorithm on that? The answer is that it allows for an elegant mechanism known as Merkel’s proofs:
Merkle’s proof consists of a chunk, the root hash of the tree, and a “branch” that consists of all the hashes that go along the path from the chunk to the root. Anyone reading the manual can verify that the hash, at least for that branch, is consistent all the way up the tree, and so the given chunk actually exists at that position in the tree. The application is simple: Suppose there is a large database, and the contents of the entire database are stored in a Merkle tree where the root of the Merkle tree is publicly known and trusted (i.e., digitally signed by enough trusted parties), or has abundant evidence on work). Then, a user who wants to perform a key-value lookup in the database (for example, “Tell me the object at position 85273”) can request a Merkle proof, and upon receiving the proof verifies its validity, and thus the value received In reality At position 85273 in the database with this specific root. It provides a mechanism for authentication small An amount of data, such as a hash, that will also be expanded for authentication big Databases of unlimited size.
Merkel’s proofs in Bitcoin
The original application of Merkle proofs was in Bitcoin, as described and created by Satoshi Nakamoto in 2009. The Bitcoin blockchain uses Merkle proofs in order to store transactions in each block:
The benefit this provides is the concept that Satoshi described as “simplified payment verification”: instead of downloading all Every transaction and every block, only the “light client” can download the chain Cluster headerschunks of data 80 bytes per block containing only five things:
- Hash of the previous head
- Timestamp
- Mining difficulty value
- Proof of work nonce
- The root hash of a Merkle tree containing the transactions of that block.
If a lightweight client wants to determine the state of a transaction, it can simply request a Merkle proof that shows that a particular transaction exists in one of the Merkle trees whose root is in the block head of the main chain.
This takes us further, but Bitcoin-style light clients have their limitations. One specific limitation is that although they can prove the listing of transactions, they cannot prove anything about the current status (e.g., digital asset holdings, name registrations, status of financial contracts, etc.). How many bitcoins do you have now? A lightweight Bitcoin client could use a protocol that involves querying multiple nodes and trusting that at least one of them will notify you of any given transaction spending from your addresses, and this will get you very far in this use case, but for other more complex applications this is not enough. The exact nature of the effect of a transaction can depend on the effect of many previous transactions, which themselves depend on previous transactions, so you will eventually have to authenticate every transaction in the entire chain. To overcome this problem, Ethereum takes the Merkle tree concept one step further.
Merkel Proofs in Ethereum
Each block head in Ethereum contains not just one Merkle tree; three Trees are for three types of things:
- Transactions
- Receipts (basically, pieces of data that appear impact per transaction)
- state
This allows for a highly advanced light client protocol that allows light clients to provide easily verifiable answers to many types of queries:
- Is this transaction included in a specific block?
- Tell me all instances of event type
- What is the current balance in my account?
- Does this account exist?
- Pretending to make this transaction on this contract. What will be the output?
The former is processed by the transaction tree; The third and fourth are handled by the state tree, and the second by the receiving tree. The first four are fairly easy to calculate; The server simply finds the object, fetches the Merkle branch (a list of hashes that goes up from the object to the root of the tree) and replies back to the lightweight client with the branch.
The fifth is also handled by the state tree, but the way it is calculated is more complex. Here, we need to build what can be called Proof of Merkel’s case transmission. Basically, it is a guide that makes the claim “If you run a transaction T On state with root sThe result will be a case with a root s’with the record to And directing Hey(“Output” exists as a concept in Ethereum because every transaction is a function call; it is not necessary in theory.)
To compute the proof, the server locally creates a fake block, sets the state to S, and pretends to be a light client while committing the transaction. That is, if the transaction application process requires the client to determine the account balance, the light client inquires about the balance. If a light client needs to check a particular item in a particular contract store, the light client will make a query for that, and so on. The server “responds” all of its queries correctly, but it keeps track of all the data it sends. The server then sends to the client the aggregated data from all these requests as evidence. The client then performs the exact same action, but… Using the provided directory as its database; If its result is the same as what the server claims, the client accepts the proof.
Patricia trees
We mentioned above that the simplest type of Merkel tree is the binary Merkel tree; However, the trees used in Ethereum are more complex – this is the “Patricia Merkel Tree” you heard about in our documentation. This article will not go into detailed specifications; It is better to do this This article And thisalthough I will discuss the underlying logic.
Merkle binary trees are very good data structures for authenticating information in a “list” format; Basically, a series of pieces one after another. For transaction trees, it’s also good because it doesn’t matter how much time it takes release A tree once created, just as a tree is created once and then forever frozen solid.
But for the state tree, the situation is more complicated. A state in Ethereum essentially consists of a key-value map, where the keys are addresses and the values are account declarations, listing the balance, number, token, and storage for each account (where the storage is itself a tree). For example, the Morden testnet generation state looks like this:
{
"0000000000000000000000000000000000000001": {
"balance": "1"
},
"0000000000000000000000000000000000000002": {
"balance": "1"
},
"0000000000000000000000000000000000000003": {
"balance": "1"
},
"0000000000000000000000000000000000000004": {
"balance": "1"
},
"102e61f5d8f9bc71d0ad4a084df4e65e05ce0e1c": {
"balance": "1606938044258990275541962092341162602522202993782792835301376"
}
}
However, unlike transaction history, state needs to be updated frequently: the balance and number of accounts are often changed, what’s more, new accounts are frequently inserted, and existing keys in storage are frequently inserted and deleted. Thus what is needed is a data structure where we can quickly compute the new tree root after an insert, update or delete operation, without recomputing the entire tree. There are also two secondary properties that are highly desirable:
- The depth of the tree is limited, even with an attacker deliberately crafting parameters to make the tree as deep as possible. Otherwise, an attacker could perform a denial-of-service attack by manipulating the tree to be so deep that each individual update becomes extremely slow.
- The root of the tree is based only on the data, not on the order in which updates are made. Performing updates in a different order and even recalculating the tree from the beginning should not change the root.
the Patricia treeIn simple terms, it’s probably the closest we can come to achieving all of these properties at once. The simplest explanation of how it works is that the key under which the value is stored is encoded in the “path” where you have to cut the tree. Each node has 16 children, so the path is determined by hexadeciphering: e.g., the key dog It is encoded in hexadecimal 6 4 6 15 6 7You start with the root, then go down to the sixth child, then the fourth, and so on until you reach the end. In practice, there are some additional improvements we can make to make the process more efficient when the tree is sparse, but that’s the basic principle. Both Articles Mentioned above Describe all features in more detail.
