Can proofs be generated from Merkle Patricia Tries in the same way as merkle trees?

pe flag

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?

pl flag

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.


Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.