Verify Ethereum Account Balance with State Proof

8 min read Original article ↗

Leo Zhang

How to check the balance of your Ethereum account?

You could use etherscan.io, or any other web API.

But how to convince yourself the balance shown on the site is correct?

You could download the entire blockchain history data and then check the latest state of your account. But that requires tons of data and can be time-consuming.

One great feature of Ethereum is that, a full node can provide proof for anyone, especially light clients, to verify the balance of any account.

Full nodes are those who have stored the entire blockchain data.

Light clients are clients who don’t have access to the entire blockchain data, but rely on full nodes to query that.

In order for full node to provide proof, Ethereum uses a data structure called Merkle Patricia Trie to store the state of accounts and their storage.

We’ve previously introduced this data structure — Merkle Patricia Trie.

In this blog, I will:

  • Talk about how Merkle Patricia Trie is used to structure and store the account state. And how Merkle proof is created to verify the state of any account.
  • Walk through an example that queries the balance of an account and the Merkle Proof of it from a full node, and verify the Proof using a simple Merkle Patricia Trie implementation that I made for demo purpose.

This blog is also part of the series that explain how Ethereum Storage works.

The full series of blog posts include:

If you are interested in more details about Ethereum storage and proof, please follow and subscribe.

Let’s get started.

Ethereum World State

How is Ethereum World State look like? Are there a bunch of tables like in relation database?

No.

Ethereum World State is essentially key-value pairs, with key being account address, and value being AccountState. Account state includes 4 piece of data: Nonce, Balance, StorageHash, CodeHash.

WorldState = [(address, AccountState)]AccountState = [Nonce, Balance, StorageHash, CodeHash]

Instead of using the naive map to store the key-value pairs of WorldState, Ethereum uses Merkle Patricia Trie structure.

Why? Because Merkle Patricia Trie not only can be used as a map to store key-value pairs, but also, more importantly, it can generate Merkle Proof to prove a certain key value pair exists in the trie.

In other words, it can generate Merkle Proof to prove a certain account address has a certain account state.

This allows a light client to be able to verify account state without the access to the entire blockchain data.

In order to verify account state, what a light client needs are:

  1. StateRoot, from the block header that they trust
  2. Merkle Proof for the account, received from an untrusted full node

With the above data, a light client can verify the untrusted Merkle Proof against the trusted StateRoot.

If the Merkle Proof is invalid, then the account state response should not be trusted.

If the Merkle Proof is valid, then they can trust the account state, which includes Nonce, Balance, StorageHash and CodeHash.

Account State

There are two types of accounts: smart contract account and user account (or external owned account, which means account has no contract).

Both of them have Nonce and Balance. But only smart contract account has code and extra storage for storing data.

The CodeHash is the hash for the smart contract code. For user account, it’s always a constant string 0xc5d2460186f7233c927e7db2dcc703c0e500b653ca82273b7bfad8045d85a470, which is keccak256 hash of an empty string.

The StorageHash is the Merkle Root Hash of the storage state. Since smart contract’s data is also key-value pairs, it can also use Merkle Patricia Trie to store the data. We will explain how smart contract stores data in future posts.

For now, we just need to know the StorageHash is Merkle Root Hash of the smart contract’s storage data.

For user account, StorageHash is always 0x56e81f171bcc55a6ff8345e692c0f86e5b48e01b996cadc001622fb5e363b421, which is keccak256 hash of an empty trie.

Example

Let’s go through a simple code example to explain how Merkle Patricia Trie stores the World State, and how the Merkle Proof looks like.

Let’s say the world state contains the following 2 user accounts - account1 and account2:

24264ae01b1abbc9a91e18926818ad5cbf39017b, {Nonce: 1, Balance: 1ETH}3a844bb6252b584f76febb40c941ec898df9bc23, {Nonce: 0, Balance: 2ETH}

Then the key value pair for account1 to be stored in the merkle trie for the world state is (account1Hash, accountState1), calculated as below:

// 1ee3017a85544556ea847c203623a9c84efdb77fa4951a5b01296d9aacefc5f7
 account1Hash := crypto.Keccak256(common.HexToAddress("0x24264ae01b1abbc9a91e18926818ad5cbf39017b").Bytes()) accountState1, err := rlp.EncodeToBytes([]interface{}{
  uint64(1),                     // Nonce
  (new(big.Int)).SetInt64(1e18), // 1 ETH
  EmptyNodeHash,                 // Empty StorageHash
  crypto.Keccak256([]byte("")),  // Empty CodeHash
 })
 require.NoError(t, err)

The key is the keccak256 hash of account address, the value is the RLP encoding of the account state, which includes Nonce, Balance, CodeHash and StorageHash.

Likewise, the key value pair for account2 is (account2Hash, accountState2):

// 1eeced8d7a011c27d9aed60517c8e596509852f1d208a8a6d6f16d17ea5da204
 account2Hash := crypto.Keccak256(common.HexToAddress("0x3a844bb6252b584f76febb40c941ec898df9bc23").Bytes()) accountState2, err := rlp.EncodeToBytes([]interface{}{
  uint64(3),                     // Nonce
  (new(big.Int)).SetInt64(2e18), // 2 ETH
  EmptyNodeHash,                 // Empty StorageHash
  crypto.Keccak256([]byte("")),  // Empty CodeHash
 })

Note, the two addresses are selected carefully, so that the hash of them have common prefix "1ee", which will create an extension node in the trie.

Next, let’s create a world state trie with the above 2 key-value pairs, and compute the root hash of the trie as the StateRoot hash:

// create a world state with the two accounts
 worldStateTrie := NewTrie()
 worldStateTrie.Put(account1Hash, accountState1)
 worldStateTrie.Put(account2Hash, accountState2)// compute the state root hash
 stateRoot := worldStateTrie.Hash()

At this point, if we visualize the merkle trie for the world state, and what is stored in key-value database, it will look like this:

Press enter or click to view image in full size

Merkle Trie backed World State

OK, now as a full node, we have the world state stored in the database.

Next, as a full node, how to prove to a light client that, for instance, account1 (0x24264ae01b1abbc9a91e18926818ad5cbf39017b) has 1ETH?

We can call the Prove method of the Merkle Trie to generate the proof for account1:

accountState1Proof, ok := worldStateTrie.Prove(account1Hash)

The Prove method creates a Merkle Proof, which is essentially all the trie nodes along the path from the root node to the LeafNode that stores the account state of account1. They are the ExtensionNode, the BranchNode and the LeafNode1.

[
  RLP(133, hash3),  RLP(null, null, null, hash1, null, null, null, null, null, null, null, hash2, null, null, null, null),  RLP(017a85544556ea847c203623a9c84efdb77fa4951a5b01296d9aacefc5f7,  RLP(1, 1ETH, emptyStorageHash, emptyCodeHash)),
]

Which is computed to be a list of hex string:

[
"e48211eea0a97a6826ce3f3f0baa07899c0502c387bf24eae2b6f6a9561169a59e0c10f9d2",
  "f851808080a007c9a6fda8ffe9dbc9fb3ecc78460caef3c4659cfc8e4e865a6121d91375557d8080808080808080a03ce63212850c9a256f4cbb1a7ba7cb576549222339f2b4124621ea4a991fe6eb80808080",
  "f8709f20017a85544556ea847c203623a9c84efdb77fa4951a5b01296d9aacefc5f7b84ef84c01880de0b6b3a7640000a056e81f171bcc55a6ff8345e692c0f86e5b48e01b996cadc001622fb5e363b421a0c5d2460186f7233c927e7db2dcc703c0e500b653ca82273b7bfad8045d85a470",
]

Note, the full node doesn’t need to send the hashes of the trie nodes to the client, but only the RLP encoding of the trie nodes. That’s because the light client can compute the hash themselves.

To verify this merkle proof, the light client will create another merkle trie with the above nodes:

// full node serialize the account state proof
serialized := accountState1Proof.Serialize()// create a proof trie, and add each node from the serialized proof
proofTrie := NewProofDB()
for _, node := range serialized {
  // store each node under its hash
  proofTrie.Put(crypto.Keccak256(node), node)
}

Let’s visualize the above steps again:

Press enter or click to view image in full size

Light Client builds a proof trie with the proof generated by Full node

Note, hash1, hash3, hash4 are computed by the light client.

And then, the light client will start with the state root hash it gets from a trusted source, which is hash4, and use account1Hash as the path to walk through the trie.

If the light client is able to arrive at a LeafNode, which is hash1. And then it can decode the value of the LeafNode, and get the balance as 1ETH, and be convinced that this balance is valid.

However, if the light client is not able to arrive at a LeafNode, then it means the full node is sending an invalid proof.

Malicious full node

What if a malicious full node tries to use 1000ETH as the account balance in the merkle proof? How can a light client find out the merkle Proof is invalid, and reject the invalid account balance?

Since all the hashes of the trie nodes are computed by the light client themselves, the light client will compute a different hash for the LeafNode. And since hash1 is supposed to be included in the BranchNode, which is also included in the ExtensionNode, the hash for the ExtensionNode will be different from the original hash4. This means, when walking through the trie with the StateRoot hash4, the light client won’t be able to find the ExtensionNode under the key hash4. So the light client can conclude that the merkle proof is invalid.

Summary

In this blog post, we explained how Ethereuem structures the world state. And walked through an example to show how a full node can prove to a light client, who doesn’t have access to the entire blockchain data, the state of any account, so that the light client can verify the proof themselves without needing to trust.

The source code of the example is available here.

In the next post, I will introduce EIP1186 — the standard for querying proof from a full node to verify account state for any account.

If you are interested in learning more, check out my blog post series: