1
$\begingroup$

I'm kind of confused about this, I have read that nodes in Merkle Patricia tries are key-value pairs, can someone provide a proof of membership for a data in a Merkle Patricia Trie just as he would with a Merkle tree? That is, providing hash of some nodes and allowing the other party to calculate the rest?

$\endgroup$
1

1 Answer 1

0
$\begingroup$

The "Patricia" part in "Merkle Patricia Trie" refers to the fact that we are labelling the edges. Edges to the left are labelled 0, edges to the right are labelled 1. Following any given path from the root to a leaf now gives us an leaf index (written in binary, but we can interpret it as an integer). E.g. 0000 for the left-most leaf or 1111 for the right-most leaf. So you could think of this index as the "key".

The "Merkle" part just refers to the fact that we are hashing values together. A node's value is the hash of its children's values. Membership proofs are the same as in normal Merkle trees, i.e. a path from the root to the leaf with all the neighbouring hashes along the way.

So yes, you could consider leaf nodes as key-value pairs. (You could do it for internal nodes, too, but I can't see how it is useful.) The Merkle Patricia trie stores a value V at leaf index I.

$\endgroup$
3
  • $\begingroup$ "Patricia" initially was an acronym for "Practical Algorithm To Retrieve Information Coded in Alphanumeric". $\endgroup$
    – fgrieu
    Jun 30, 2023 at 14:18
  • $\begingroup$ @Thore when hashing nodes, do we hash only their data(value) or do we hash their key as well? $\endgroup$
    – Abol_Fa
    Jun 30, 2023 at 14:55
  • $\begingroup$ You only hash the values. In a plain Patricia/radix tree, the nodes store the edge labels (r, om, ulus, ... in Wikipedia's example). In the Merkle Patricia tree, this is not necessary since the edge labels are known by construction. So because the keys can be derived, nodes only store the hashes as values. More interestingly, this opens up a second-preimage type of attack: en.wikipedia.org/wiki/Merkle_tree#Second_preimage_attack So if you wanted, you could manually prefix a nodes' depth to its value to include the depth in the hash. $\endgroup$
    – Thore
    Jul 1, 2023 at 16:07

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.