<aside> 💾 Storage proofs

An inclusion proof is a computational operation that ensures, with a high confidence level, that a certain claim value belongs to a certain dataset represented by a commitment. A storage proof is an inclusion proof for a storage slot in an EVM contract.

</aside>

To enable storage proofs (among others), Ethereum implements Merkle Patricia Tries to keep track of its historical states in a verifiable and efficient way. More precisely, each block header stores 3 roots:

1. stateRoot
2. transactionsRoot
3. receiptsRoot

As long as the state root is available, a prover can convince a verifier about different claims about the state of the blockchain, including the value of a storage slot in a specific contract, by sharing a storage proof. To really understand how storage proofs work, we must first understand how Ethereum encodes its data.

The World State of Ethereum is a dataset containing all the necessary information to replicate the state of the Virtual Machine. This information is stored as a mapping between addresses (160-bit identifiers) and account states (Nonce, Balance, StorageHash, CodeHash). This information is encoded into a modified Merkle Patricia trie (the State Trie), which uses keccak256(address) as the path and RPL(accountState) as the stored value. Merkle Patricia Tries ensure the following desired properties:

• Efficient updates: there is no need to recompute the whole trie each time the state changes.
• Compact representation: a single root is sufficient to identify and verify the whole dataset.
• Trie’s depth is bounded: this avoids DoS attacks.
• Root doesn’t depend on the order of the updates: unlike a binary Merkle tree, for instance.

MPT are an improvement over regular radix tries (which can have similar properties), as they allow for higher compression by collapsing shared paths.