Ethereum Stack Exchange is a question and answer site for users of Ethereum, the decentralized application platform and smart contract enabled blockchain. It only takes a minute to sign up.
Sign up to join this community
i understand that Ethereum leverages modified Patricia Merkle Trees, and that they are capable of proving that a particular key-value pair exists within a tree.
i'd like to know if modified Patricia Merkle Trees also support proof of exclusion/non-inclusion. i.e. can it be proved that a particular key-value pair does not exist in the tree? if it is possible, i would like to know how this is achieved. feel free to point me towards a resource where i can learn more about this.
Yes, but probably different from what you are asking.
Ethereum uses a Merkle Patricia Trie (MPT) to store data, leveraging advantages from both data structures.
An MPT contains all the data, even the leaves (the values), so you can prove any value's inclusion and non-inclusion just by reading them.
Due to the MPT structure, keys depend directly on values in the leaves, and you can use a partial MPT as proof of the inclusion of a specific value.
Because the partial tree is smaller than the full one, you don't need to compute all the hashes, so that represents a more computationally efficient proof of the inclusion of a value vs. hashing all the tree nodes.
On the contrary, without relying on other information (i.e., rainbow tables, other partial trees, etc.), you cannot have the same efficiency level for the non-inclusion of a value, so you need the entire tree to prove the non-inclusion.
If you value the storage more than the computation power, the best (very tiny) optimization I can think of is the removal of half of the leaves, so you can store that instead of the entire tree.
Check, for example, the image below.
Because the first layer of nodes (0-0, 0-1, 1-0, 1-1) depends on the hash of two leaves, you can remove L2 and L4 and compute those values with your searched value.
If the existing leaves (L1 and L3) don't contain the searched value, and none of the computed hashes of the missing leaves match with the content of the first layer of nodes (Hash 0-1 or Hash 1-1), you have proven the non-inclusion of the searched value in the tree.
You can find a very good high-level explanation of how Ethereum uses MPT in this well-written article, "How does Ethereum work, anyway?" by Preethi Kasireddy.
For a technical deep-dive on the MPT, you can read the dedicated article on the official Ethereum documentation.
Modified Patricia Merkle Trees do support proof of exclusion or non-inclusion. To determine the absence of key-value pair, a null hash value can be used, which was assigned to the non-existent node.
This null hash is a fixed 64 bytes value, composed of just 0's:
0x0000000000000000000000000000000000000000000000000000000000000000
