1

i am not a computer scientist so please bare with me. I had a few questions about the usage of Tries in Ethereum.

  1. My understanding is that - the Tries are actually stored in databases. Where each node is stored as KECCAK256(RLP(node)) as the key and the value is the RLP(node)?
  2. Assuming the above is correct, say we are dealing with the State Trie and I wanted to find the balance of a particular account, say XYZ, would i just look in the State Trie database, decode the RLP(node) part and read the balance of the account from there?
  3. Is the main point of Merkling in the MPT to convince me that this is indeed the value/balance which is in the blockchain as provided with a Merkle-proof i should be able to get back to the State Trie root? Or is there a more subtle use?
  4. Is the main point of hashing the nodes for Merkle proofs as well? The common reason to hash in this context is to 'save space' - the only use/reason i can see to hash the data is to 'save space' in the context of proving that what I am being reported is indeed the truth..

many thanks - and once again apologies if my question is a bit ill-formed/naive.

1
  • Please edit the question to limit it to a specific problem with enough detail to identify an adequate answer.
    – Community Bot
    Jun 11, 2022 at 22:33

1 Answer 1

2

My understanding is that - the Tries are actually stored in databases. Where each node is stored as KECCAK256(RLP(node)) as the key and the value is the RLP(node)?

In the MPT, as well as in the Merkle tree, every node has a hash value. Each node’s hash is decided by the sha3 hash value of its contents. This hash is also used as the key that refers to the node. Keys and values saved in the storage are not the key-values of the Ethereum state. The value that is stored in the storage is the content of MPT node while the key is the hash of this node.

A Node that does not have a child node is called a leaf node. A leaf node consists of two items: its path and value.

you can read more here

Assuming the above is correct, say we are dealing with the State Trie and I wanted to find the balance of a particular account, say XYZ, would i just look in the State Trie database, decode the RLP(node) part and read the balance of the account from there?

A trie is a tree-like data structure, that is used to retrieve a string value by traversing down a branch of nodes that store associated references (keys) that together lead to the end value that can be returned. Specifically, if we begin from the top of the tree at the root node, each character in the key indicates which child node to follow resulting in a path to the corresponding value.

take a look at the following diagram from here:

enter image description here

Here we have a simplified world state. The keys represent addresses and the values represent balances (1)

In this example, the root node (2) is an extension node [encodedPath, key] and we know that based on the hex-prefix. Also note that in this example, all the keys share the same nibble of a7, thus they’re grouped accordingly, an attribute of radix tries. Since the root is an extension node [encodedPath, key] the ‘next node’ bucket will be a hash pointing to the next node, which in this case is a branch node (3)

If we follow the first key in our simplified state (a711355), we use the 1 after a7, to look in the first index of the branch node. This leads us to create a leaf node (4) where if we compare the key and the path, they’re the same, allowing us to skip ahead and leading us to the value or the account balance of 45.0 ETH.

Is the main point of Merkling in the MPT to convince me that this is indeed the value/balance which is in the blockchain as provided with a Merkle-proof i should be able to get back to the State Trie root? Or is there a more subtle use?

Merkle patricia trie allows us to verify data integrity, if any key-value pair is updated, the merkle root hash of the trie would be different; if two Tries have the identical key-value pairs, they should have the same merkle root hash. So you can compare the entire state by comparing two hashes

you can read more about the different tries here

This allows light clients to easily make and get verifiable answers to many kinds of queries:

Has this transaction been included in a particular block?

Tell me all instances of an event of type X (eg. a crowdfunding contract reaching its goal) emitted by this address in the past 30 days What is the current balance of my account?

Does this account exist?

Pretend to run this transaction on this contract. What would the output be?

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.

read more here

Is the main point of hashing the nodes for Merkle proofs as well? The common reason to hash in this context is to 'save space' - the only use/reason i can see to hash the data is to 'save space' in the context of proving that what I am being reported is indeed the truth..

enter image description here

Finding out whether two different nodes have the same data or not can be efficiently done with the Merkle tree. You first have to compare the Top Hash value of the two nodes. If they are the same, then the two nodes have same data. For example, if you look at the picture above, when there are four nodes (L1, L2, L3, L4), you only need to check whether they have the same Top Hash or not. If the Top Hash is different and you want to know which data is different, you should compare Hash 0 with Hash1 and check which branch is different. By doing so, you will eventually find out which data is different.

read more here

1
  • thank you - this is very helpful. one more question/clarification: As we traverse down the tree and eventually reach a leaf node where the key (address) is equal to the path, is what is retrieved from the MPT the hash of the contents of the node? Therefore, to then actually get the contents of the node back, i would use this same hash to refer to the database, look up this hash (key) and get the relevant value (which I assume i can just decode) to get say the account balance? Jun 13, 2022 at 9:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.