Merkle proof verification for Ethereum Patricia tree
The Ethereum blockchain uses a modified Merkle Patricia tree for state authentication. This lets blockchain nodes come to consensus on the whole blockchain state at every block and enables light clients to create Merkle proofs for any state information.
However, even though state Merkle proof verification has been possible since the early days of Ethereum, only recently it has been added to the JSON RPC API so it would be nice to see more applications leverage this great feature.
A storage Merkle proof is only valid for a specific trie root, ie a specific state. Therefore the user or light client application should trust that state root, by either running a light client, or trusting a state root that has been multi-signed by multiple attesting parties : the more the safer.
Account and contract variable queries
In this example we will use Web3.py to build a Merkle proof that some value for a key is included in the given state root.
Web3.py does not yet support eth_getProof as the PR is not merged at the time of writing. So this fork of web3.py can be used instead: https://github.com/paouvrard/web3.py/tree/EIP-1186-eth_getProof
EDIT (Oct 2019) : eth_getProof is now available in web3.py and web3.js, but not in the Metamask provider.
Web3.py connects to an Ethereum node and makes a state query with proof via the JSON RPC or IPC API eth_getProof.
Contract state variable query
Simple solidity contract in which we want to prove the value of a mapping’s key :
Verifying storage proofs for ‘greeting’ and ‘my_map’:
With the above script we can now build and verify state merkle proofs of accounts and contract variables. Note that verify_eth_getProof(…) only verifies inclusion proofs and will return False is an exclusion proof is included. Verifying exclusion can be done with the ‘proof’ object returned by eth.getProof(…).
How are contract variables stored in the Patricia trie ?
To store variables, the EVM uses a key based on the position at which the variable is defined in a contract : keccack(LeftPad32(key, 0), LeftPad32(map position, 0)). More details here : https://github.com/ethereum/wiki/wiki/JSON-RPC#eth_getstorageat.
The web3.py fork provides the convenient storage_position() which returns the Patricia tree storage key for the requested mapping key.
As a comparison, Aergo Lua VM stores variable state information in the trie with the key : hash( bytes(“__sv__” + variable_name + [“-”, var_index], ‘utf-8’)) where var_index is optional and used for a map’s key or an array’s index.
Proof verification code
Here is a great diagram explaining the different types of nodes in the Patricia tree :
source : https://ethereum.stackexchange.com/questions/6415/eli5-how-does-a-merkle-patricia-trie-tree-work
In Python
The following code verifies the proof for a key and expected_value by iterating the proof nodes (Extension, branch, leaf… from the above diagram). Returns true if the expected_value is equal to the value contained in the proof.
In Solidity :
https://github.com/loredanacirstea/goldengate/blob/master/contracts/contracts/lib/MPT.sol
Conclusion
This was a quick overview of how solidity contract variables can be queried with inclusion/exclusion proofs. eth_getStorageAt and eth_getProof actually remove the need to define getters in contract code as the getProof API queries the trie state db directly (getters are still needed for a contract getting another contracts’s variable). In a future article we’ll have a look at how these state proofs can be used for inter-blockchain communication with on-chain state verification of a sidechain.
