1

I understand how those tree's work separately, but i can't imagine how to put it in one structure.

From ethereum's wiki:

All substantial quantities of data in Ethereum are stored in a data structure known as the Patricia Merkle tree, a tree structure where each node in the tree is the hash of its children. Each set of key/value pairs maps to a unique root hash, and only a small subset of nodes is needed to prove that a particular key/value combination is in the tree corresponding to a particular root hash.

Also, inspecting this diagram, can't see where each node is a hash of it's childs.

From official specification, can't understand below part. What means <> in current example?

<64 6f> : 'verb'
<64 6f 67> : 'puppy'
<64 6f 67 65> : 'coin'
<68 6f 72 73 65> : 'stallion'
Now, we build such a trie with the following key/value pairs in the 
underlying DB:

rootHash: [ <16>, hashA ]
hashA:    [ <>, <>, <>, <>, hashB, <>, <>, <>, hashC, <>, <>, <>, <>, <>, <>, <>, <> ]
hashC:    [ <20 6f 72 73 65>, 'stallion' ]
hashB:    [ <00 6f>, hashD ]
hashD:    [ <>, <>, <>, <>, <>, <>, hashE, <>, <>, <>, <>, <>, <>, <>, <>, <>, 'verb' ]
hashE:    [ <17>, hashF ]
hashF:    [ <>, <>, <>, <>, <>, <>, hashG, <>, <>, <>, <>, <>, <>, <>, <>, <>, 'puppy' ]
hashG:    [ <35>, 'coin' ]

EDIT: Ok so i understood that hashA empty brackets '<>' is empty slots in branch node.

1

In Ethereum, the data structure is a Modified Merkle Patricia Trie

Merkle:

The merkle part of the tree means that the hash of the children used by the parent to ensure the entire tree is cryptographically proven to be immutable.

In the above example,

  1. the rootHash points to hashA
  2. hashA, in turn, points to hashB & hashC

Patricia Trie :

These are radix trees where r=2, as noted here

enter image description here

In a Patricia ("Practical Algorithm To Retrieve Information Coded In Alphanumeric") Trie (NOTE: "trie" comes from re-trie-val:

  • edges contain the content
  • nodes indicate branching, or leaf (i.e. trie termination).

Modified ____ :

In the Ethereum version of the data structure, the nodes in the tree are either:

  • a combination of a Patricia edge & and a leaf node (such as hashC above)
  • Patricia branching node (such as hashA above)
  • a Patricia edge (such as hashB above)
0

All nodes from modified patricia tree are stored in flat key value LevelDB like so sha3(rlp(node)). Then extension node store hash from levelDB in value as reference to other node. Very good explanation here

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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