# What Is a Proof and Why Do You Need One?

9.20.2022
-
BY —
Stefan Adolf
Developers
Insights
Product
News
Partners

Decentralized apps rely heavily on blockchain state to display current and historical values like an account's balance, its NFT holdings, or current exchange rates on DEXes. Projects like The Graph or Covalent make blockchain data accessible, chain indexers like Etherscan provide historical information about the chain's state, and RPC providers like Infura or Alchemy allow wallet extensions like Metamask to connect to their full-node infrastructure. However, unless you run your very own full-node you cannot prove that any value provided by these sources truly resembles the chain state they represent. In short: relying on external, centralized services imposes a trust risk. However, the way Ethereum stores data allows trusting the chain state data without trusting the provider itself, thanks to proofs. This is how it works.

## Ethereum's storage model

Ethereum uses a tree-based storage model that contains each account's balance and the storage for contract-based accounts. All values are wrapped in a traversable hash trie structure - a Patricia Merkle Trie - that allows creating cryptographic hash proofs for each tree node. The state root hash of a block represents the complete state of all accounts and contracts at a given block height, aka the world state. Block producers execute new transactions on their local state copy and bundle the resulting new state root hash and a list of all executed transactions into a new block.

Light Ethereum clients cannot verify the current chain's state since they're not keeping a full copy of the world state. Full nodes can rebuild the state tree by executing every transaction since genesis, and then constantly update it as new blocks arrive. To save storage space they only keep the most recent chain states and hence cannot respond to state queries from the past, i.e. they're not able to determine an account's balance older than - depending on the node's settings - 64 blocks. That's sufficient to create proofs about the current state, though.

## Cryptographic proofs on hash trees

Merkle trees use hashes of their nodes' values as keys to guarantee their content integrity. To build a simple binary Merkle tree, a prover starts by computing a hash over a node L's content h(L). Next, they compute the hash over h(L) and the hash of a sibling content node K: h(h(K)+h(L)). Using this hash as a key they create a new node KL with h(K) and h(L) as children and find another node IJ at the same tree level to create a new parent node that hashes all values of the underlying tree structure: h(IJ + KL) = h(h(h(I) + h(J)) + h(h(K) + h(L))). This process is repeated until all nodes are combined to a single root hash. Since each parent node keeps a hash of its children, it's impossible to change anything down the tree without affecting the tree's root node.

To prove that a certain base value has been incorporated into a Merkle tree's root, one collects the hashes of sibling nodes at each level of the tree. A prover successively computes their hash sums to finally recreate the root hash, thereby proving the inclusion of the node's value.

A simple way of storing binary Merkle trees in a flat key/value database structure is with radix tries. To store a node, one splits its hexadecimal hash key into its nibbles (the hex characters) and create subdirectories for each of them. A node with the key 0xcafe would end up in a folder structure like c/a/f/e/value. Looking up a node requires traversing the directory structure along the key's nibbles down to the last nibble's directory where the node's value will be stored. While simple to understand this approach is far too inefficient to store large tree data structures like Ethereum's world state. The network instead uses Patricia Merkle Tries that add some complexity to the data structure by introducing branch-, extension-, leaf- and null-nodes but are way more efficient to store and traverse. Additionally, a Recursive Length Prefix (RLP) encoding is used to serialize nested arrays and data structures.

## Proving account state

Ethereum's state trie consists of a mapping between account addresses and their state, defined by their current nonce and balance and in the case of contract accounts a storageRoot key that points to a position in the dedicated contract storage trie and their binary code hash. Just using a block's stateRoot one can look up an account's current state at that height using a full node's LevelDB (Geth's default storage database). Our examples are using an archive node of Ethereum's recently launched Sepolia testnet because it's still small enough to be synced to a developer's machine.

`const { SecureTrie } = require("merkle-patricia-tree");
const {
toBuffer,
bufferToHex,
keccak256,
Account,
} = require("ethereumjs-util");
const Web3 = require("web3");
const web3 = new Web3("http://127.0.0.1:8545");
const db = new Level(".ethereum/sepolia/geth/chaindata");
async function getState(address, blockNumber) {
const block = await web3.eth.getBlock(blockNumber);
const trie = new SecureTrie(db, toBuffer(block.stateRoot));
//retrieves the account node's *value*
const rawValue = await trie.get(toBuffer(address));
const account = Account.fromRlpSerializedAccount(rawValue);
console.log(account);
}`

getState("0xe127a39da6ea2d7b1979372ae973a20bab08a80a", 1432400) yields:

`account Account {
nonce: <BN: 2>,
balance: <BN: 1f3d52b3c4f92e45d>,
stateRoot: <Buffer 56 e8 1f 17 1b cc 55 a6 ff 83 45 e6 92 c0 f8 6e 5b 48 e0 1b 99 6c ad c0 01 62 2f b5 e3 63 b4 21>,
codeHash: <Buffer c5 d2 46 01 86 f7 23 3c 92 7e 7d b2 dc c7 03 c0 e5 00 b6 53 ca 82 27 3b 7b fa d8 04 5d 85 a4 70>
}`

The provided account is an EOA, hence the codeHash value corresponds to keccak256([]) (another expression of a null value) and stateRoot is the hash of an RLP encoded zero: keccak256(rlp.encode(0)).

To create a proof of the account node's value against a block's state root you walk down the patricia trie starting at the block's stateRoot node, resolve the paths on the trie's branch and extension nodes according to the signposts expressed by the leaf node's nibbles until the wanted leaf node is reached. On the way we're keeping track of all nodes we see while traversing the path. More details about the traversal can be found here. We're using only high level methods to show proof creation here:

`const { SecureTrie } = require("merkle-patricia-tree");
const { toBuffer, keccak256 } = require("ethereumjs-util");
const db = new Level(".ethereum/sepolia/geth/chaindata");
const trie = new SecureTrie(db, toBuffer(block.stateRoot));
//create a proof by finding the path on our own:
const { node: accountNode, stack } = await trie.findPath(
keccak256(toBuffer(address))
);
const proof = stack.map((stackElem) => {
return stackElem.serialize();
});
//or by using a trie's convenience method:
const proof = await SecureTrie.createProof(trie, toBuffer(address));
//or by using the ethereum node's RPC interface
const { accountProof: proof } = await web3.eth.getProof(
address,
[0],
block.number
);`

All three proofs contain the same array of RLP encoded proof nodes, with our account node at its end:

`[
" ",
" ",
" ",
" ",
"0xf8518080a06b91f274ef06ab455966416f6bb3779519bf72c68e85ec4b61ff8b99aa73a1818080a0937ee4540dc495eaa3cd61e12a4f6158a6be147d71ac3955a50ecd080e9732698080808080808080808080",
"0xf8709e3e0484bbc22108bc77412e65255ce0387dc7c6a8d1917625ddb60ccbd98fb84ff84d028901f3d52b3c4f92e45da056e81f171bcc55a6ff8345e692c0f86e5b48e01b996cadc001622fb5e363b421a0c5d2460186f7233c927e7db2dcc703c0e500b653ca82273b7bfad8045d85a470"
]`

To verify this proof one doesn't need to have access to a full state tree at that block height. It's sufficient to know (and trust, e.g. by running a light node) the proof block's stateRoot:

`const { SecureTrie } = require("merkle-patricia-tree");
const { toBuffer, keccak256, Account } = require("ethereumjs-util");
// look Ma, no ethereum node needed
// @param stateRoot hexString: the block's stateRoot
async function verifyAccountProof(address, proof, stateRoot) {
const proofBufs = proof.map((p) => toBuffer(p));
//build a new trie using only the proof nodes. They will hash towards the block's stateRoot
const proofTrie = await SecureTrie.fromProof(proofBufs);
//the account node can also be retrieved from the partial trie:
const accNodeRaw = await proofTrie.get(keccak256(toBuffer(address)));
const account = Account.fromRlpSerializedAccount(accNodeRaw);
console.log("proven value", account);
const valid = await proofTrie.checkRoot(toBuffer(stateRoot));
//or: const valid = bufferToHex(proofTrie.root) == stateRoot;
return valid;
}`

## Proving contract state

Proofs over contract state are created accordingly. They are rooted at the contract account's own stateRoot member variable that points to the mutable root of the contract's storage trie. Storage slots are addressed by their position hash as outlined in the Solidity documentation and are stored as leaf nodes in the storage trie. To simplify this procedure, we're going to use eth_getProof calls here as described in EIP-1186 and supported by all major chain node implementations and service providers. Lets prove this contract's greeting to be "Hello, Hardhat!" at Sepolia block number 1391140 :

`pragma solidity ^0.8.0;
contract Greeter {
string private greeting;
constructor(string memory _greeting) {
greeting = _greeting;
}
function setGreeting(string memory _greeting) public {
greeting = _greeting;
}
}`

Now, lets create a proof of its storage slot 0 (the string variable greeting ):

`const { bufferToHex } = require("ethereumjs-util");
const { SecureTrie } = require("merkle-patricia-tree");
const Web3 = require("web3");
const web3 = new Web3("http://127.0.0.1:8545");
const proveContractStorage = async (blockNumber) => {
const proof = await web3.eth.getProof(
"0xf492600aed292b1b94a1ba0cd29fb6ed6d6ab872", //the contract's address on Sepolia
[0], //the first storage slot
blockNumber
);
console.log(proof.storageProof);
const value = web3.utils.hexToAscii(proof.storageProof[0].value);
console.log(value);
const proofBufs = proof.storageProof[0].proof.map(toBuffer);
const proofTrie = await SecureTrie.fromProof(proofBufs);
const valid = bufferToHex(proofTrie.root) == proof.storageHash;
console.log(valid);
};[
{
key: '0x0',
value: '0x48656c6c6f2c204861726468617421000000000000000000000000000000001e',
proof: [
'0xf8518080a0e2a22c03c4f21673563d55cbad16de4c4affc9a54c3eea063ce358ccd6d02c4c8080808080808080a0fc47ec7aea920817d850c758a8fd61ecc89b967b2fe8d9ec6d00feedeb0a7d658080808080',
'0xf843a0390decd9548b62a8d60345a988386fc84ba6bc95484008f6362f93160ef3e563a1a048656c6c6f2c204861726468617421000000000000000000000000000000001e'
]
}
]
Hello, Hardhat!
true`

### A non trivial example

Creating proofs over nested structures, dynamic types like strings, or deeply buried storage slots is slightly harder because you have to be familiar with Solidity's storage layout. To demonstrate that, here is a non-trivial example to prove that Jimmy Fallon owned Bored Ape #599 at block height 13572667 as he claimed during his Tonight Show in January 22. The Bored Apes NFT contract inherits from OpenZeppelin's legacy V3 enumerable ERC721 contract. The data structure storing ownership information about a single token is the private _tokenOwners member struct that maps a token id to an index onto another dynamic array of key value mappings.

To prove the ownership storage values we need to take a look at the contract's ownerOf implementation and its related structs. Here's a summary of the relevant parts of the full BAYC code base:

`library EnumerableMap {
struct MapEntry {
bytes32 _key;
bytes32 _value;
}
struct Map {
MapEntry[] _entries;
// Position of the entry defined by a key in the `entries` array, plus 1
// because index 0 means a key is not in the map.
mapping (bytes32 => uint256) _indexes;
}
struct UintToAddressMap {
Map _inner;
}
function _get(Map storage map, bytes32 key) private view returns (bytes32) {
uint256 keyIndex = map._indexes[key];
require(keyIndex != 0, "EnumerableMap: nonexistent key"); // Equivalent to contains(map, key)
return map._entries[keyIndex - 1]._value; // All indexes are 1-based
}
function get(UintToAddressMap storage map, uint256 key) internal view returns (address) {
return address(uint160(uint256(_get(map._inner, bytes32(key)))));
}
//...
}
contract ERC721 is Context, ERC165, IERC721, IERC721Metadata, IERC721Enumerable {
// Mapping from holder address to their (enumerable) set of owned tokens
mapping (address => EnumerableSet.UintSet) private _holderTokens;
// Enumerable mapping from token ids to their owners
EnumerableMap.UintToAddressMap private _tokenOwners;
function ownerOf(uint256 tokenId) public view virtual override returns (address) {
return _tokenOwners.get(tokenId, "ERC721: owner query for nonexistent token");
}
//...
}`

The index mapping _tokenOwners is the contract's third storage member (the 1st one being part of the ERC-165 implementation) and it implicitly points to the Map struct via UintToAddressMap.inner , occupying two storage slots. By applying Solidity's layout rules for dynamic arrays, the storage slot's address of the enumeration index that points to the current owner of token #599 can be computed as const indexSlot = web3.utils.soliditySha3(599, 3);. Querying that storage slot's value by web3.eth.getStorageAt(baycAddress, indexSlot, blockNumber) yields the index 0x258 at the given block height. Considering that the Map._entries array starts at the contract's third slot, it takes two slots to store one MapEntry and the indexes are 1-based we can resolve the map's _value member that carries the token owner's address like so:

`soliditySha3(2) + (0x258 * 2) - 2 + 1`

With that we can construct two storage proofs for the index and the owner's address:

`const baycAddress = "0xbc4ca0eda7647a8ab7c2061c2e118a18a936f13d";
const blockNumber = 13572667;
const indexSlot = web3.utils.soliditySha3(599, 3);
// -> 0x7e2616eb7a75f68a32624f502cf2cabc166c302900bbdc790c2fb85cea316a21
const indexValue = await web3.eth.getStorageAt(
baycAddress,
indexSlot,
blockNumber
); //0x258
const bnIndex = ethers.BigNumber.from(indexValue);
const valueSlot = ethers.BigNumber.from(web3.utils.soliditySha3(2))
.add(bnIndex.mul(2))
.sub(2)
.add(1);
// -> 0x405787fa12a823e0f2b7631cc41b3ba8828b3321ca811111fa75cd3aa3bb5f7d
const proof = await web3.eth.getProof(
baycAddress,
[indexSlot, valueSlot],
blockNumber
);`

To prove the value of the yielded proof, we can:

`async function validateStorage(proof, slot, proofIdx) {
const proofBufs = proof.storageProof[proofIdx].proof.map(toBuffer);
const pTrie = await SecureTrie.fromProof(proofBufs);
const valid = pTrie.checkRoot(toBuffer(proof.storageHash));
const rlpNode = await pTrie.get(toBuffer(web3.utils.keccak256(slot)));
console.log("content at slot", slot, bufferToHex(rlp.decode(rlpNode)));
return valid;
}
console.log(await validateStorage(proof, indexSlot, 0));
console.log(await validateStorage(proof, valueSlot.toHexString(), 1));content at slot 0x9f82913e56c1ea296cd5a3c46bc89a4073098f41767359e4c3742445923985c7 0x0258
true
content at slot 0xd4790f3899b463e8194660196b97cf3ff9c47008d83ca7c0e51ce406d3c784e5 \
0x0394451c1238cec1e825229e692aa9e428c107d8 (<- Jimmy Fallon's address)
true`

## Validating proofs inside smart contracts

These have been client side examples, but proofs can also be validated inside Solidity contracts, e.g. to prove historical chain information that's not available to the contract itself. A good example can be seen at Lido Finance's trustless ETH/stETH price pool oracles that receives price reports as a combination of block header, account and state proofs. Since proofs are submitted as memory variables, price updates are relatively cheap. Here's a contract that's built on Lido's primitives and verifies any given state proof. It's also deployed on Görli:

`// SPDX-License-Identifier: MIT
pragma solidity 0.6.12;
pragma experimental ABIEncoderV2;
import "./StateProofVerifier.sol";
import {RLPReader} from "solidity-rlp/contracts/RLPReader.sol";
contract ProofVerifier {
using RLPReader for bytes;
using RLPReader for RLPReader.RLPItem;
using StateProofVerifier for StateProofVerifier.Account;
/*
struct Account {
bool exists;
uint256 nonce;
uint256 balance;
bytes32 storageRoot;
bytes32 codeHash;
}
struct SlotValue {
bool exists;
uint256 value;
}
*/
function extractAccountFromProof(
address _address,
bytes32 _stateRootHash,
bytes memory _proofRlpBytes
) public pure returns (StateProofVerifier.Account memory account) {
RLPReader.RLPItem[] memory proofs = _proofRlpBytes.toRlpItem().toList();
bytes32 addressHash = keccak256(abi.encodePacked(_address));
account = StateProofVerifier.extractAccountFromProof(
addressHash,
_stateRootHash,
proofs
);
}
function extractSlotValueFromProof(
bytes32 _slotHash,
bytes32 _storageRootHash,
bytes memory _proofRlpBytes
) public pure returns (StateProofVerifier.SlotValue memory slotValue) {
RLPReader.RLPItem[] memory proofs = _proofRlpBytes.toRlpItem().toList();
slotValue = StateProofVerifier.extractSlotValueFromProof(
_slotHash,
_storageRootHash,
proofs
);
}
}`

Continuing with the proof of Jimmy Fallon's Bored Ape, this is how you would prepare RLP encoded versions of the proof's node array as required by the contract's method interface:

`//converts an array of rlp encoded proofs to an rlp encoded array of proofs.
const rlpEncodeProof = (proof) => {
const rlpDecodedProofs = proof.map((p) => rlp.decode(toBuffer(p)));
return rlp.encode(rlpDecodedProofs);
};
const rlpAccountProof = rlpEncodeProof(proof.accountProof);
const indexStorageProof = rlpEncodeProof(proof.storageProof[0].proof);
const valueStorageProof = rlpEncodeProof(proof.storageProof[1].proof);`

and submit it to the contract:

`//state root of mainnet block #13572667
const blockStateRoot =
"0xa710dad6c716e0b762a671865cbe0d286f158198580f4ac97c4ace95ea85ba1b";
const baycAddress = "0xbc4ca0eda7647a8ab7c2061c2e118a18a936f13d";
async function main() {
const Verifier = await ethers.getContractFactory("ProofVerifier");
// 0x52E357F616a13089435bE73E20CFfB788Eb4C928 on Görli:
const verifier = Verifier.attach(process.env.CONTRACT_VERIFIER);
//"account" is the bored apes contract
const accountResult = await verifier.extractAccountFromProof(
baycAddress,
blockStateRoot,
rlpAccountProof
);
const indexResult = await verifier.extractSlotValueFromProof(
ethers.utils.keccak256(indexSlot),
accountResult.storageRoot,
rlpIndexProof
);
const valueResult = await verifier.extractSlotValueFromProof(
ethers.utils.keccak256(valueSlot),
accountResult.storageRoot,
rlpValueProof
);
console.log(
accountResult,
indexResult.value.toHexString(),
valueResult.value.toHexString()
);
}[
exists: true,
nonce: BigNumber { value: "1" },
balance: BigNumber { value: "0" },
storageRoot: '0x3f99b7df7989c11417c18b517c333ec74104e23ae76a50d578292ba3d466d77d',
codeHash: '0x0ba5e25e74d81bab327110c8d8b44320f50ad5c3e91a546a5c5a9b605cf653b3'
]
0x0258
0x0394451c1238cec1e825229e692aa9e428c107d8 // <- Jimmy Fallon, again.`

Creating EIP-1186 compatible historical cryptographic proofs as demonstrated is a rather demanding task. It requires provers to traverse their archive nodes' LevelDBs, requiring up to 16 disk operations per account and storage slot. However, since state proofs like Jimmy Fallon's Bored Ape ownership at block height 13572667 are deterministic and valid forever, one could presciently collect all of the hashes along the nodes from root of the state tree down to specific nodes and index them. Chain indexers or RPC relayers like Metamask could use those hashes to execute proofs, thus minimizing trust in the service itself: each reply would be provable by the client.

The Laconic Network greatly simplifies the process of generating proofs for blockchain data, saving time for developers, and avoiding the extensive recursive querying of full-node databases that would otherwise be required.

Share This Article

## Recent Articles

Developers
Insights
Product
News
Partners
8.20.2024

## LORO Testnet Stage 1 is Live

Read Article
Developers
Insights
Product
News
Partners
8.12.2024

## How to Register for the Laconic Incentivized Testnet

Read Article
Developers
Insights
Product
News
Partners
7.24.2024

## A Return to Chain Minimalism

Read Article