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

Abol_Fa

2/13/24, 4:31 PM

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?

1 + 1

hash-tree

lamba

6/30/24, 3:09 PM

Yes, this was done in [CONIKS](https://www.usenix.org/system/files/conference/usenixsecurity15/sec15-paper-melara.pdf) for example. They called it prefix trees. A standalone implementation can be found here https://github.com/dedis/cothority/tree/main/byzcoin/trie

Score:0

Crypto

Thore

6/30/24, 1:59 PM

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.

+ 3

fgrieu

6/30/24, 2:18 PM

"Patricia" [initially](https://doi.org/10.1145/321479.321481) was an acronym for "Practical Algorithm To Retrieve Information Coded in Alphanumeric".

Abol_Fa

6/30/24, 2:55 PM

@Thore when hashing nodes, do we hash only their data(value) or do we hash their key as well?

Thore

7/1/24, 4:07 PM

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: https://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.

Elon Musk

I sit in a Tesla and translated this thread with Ai:

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

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.