[Ethereum] How to calculate the merkle proof for quering the balance of a token holder

erc-20ethereumjsmerkle-patricia-triessolidity

I know this can be done through accessing the full node of Ethereum, but I want to know, how could I do it technically? Suppose I have an ERC20 token contract having address 0xabc.. and Alice is the token holder having account address 0xqwe.. .I want to query the blockchain for getting the balance of Alice till X block number. As per my research, I can get this by accessing the state trie using the key, state trie hash, Merkle Proof.

I calculate the partial key using this Solidity-Miscellaneous

but still, don't understand how do I map my key related to the ERC20 token contract.

I have the state trie hash but still trying to find out the Merkle proof, How do I do that? Should I need to use the ethereumjs/merkle-patricia-trie or there is an alternate present to calculate the Merkle proof.

Best Answer

The eth_getProof API is available in geth and parity to query smart contract storage and returns a proof from which you can verify inclusion and non inclusion in a state root. You probably have to run a full node locally as Infura might not support the API.

See EIP 1186 eth_getProof for details about the EIP.

At the time of writing this, web3js and web3py do not implement the API so you should access it in a different way. One way to do it is this fork of web3py which let's you query eth_getProof : https://github.com/paouvrard/web3.py/tree/EIP-1186-eth_getProof

Example solidity contract:

contract Token {
    string public greeting;
    mapping (address => uint) public balances;
    constructor() public {
            greeting = 'Hello';
            balances[msg.sender] = 33333;
    }
}

Verifying storage proofs for 'greeting' and 'balances': this is how I do it on a private network.

from web3 import Web3, IPCProvider
from web3.middleware import geth_poa_middleware
from web3._utils.proof import verify_eth_getProof, storage_position

w3 = Web3(IPCProvider(...))
w3.middleware_stack.inject(geth_poa_middleware, layer=0)
w3.eth.defaultAccount = Web3.toChecksumAddress('0x...')

# get the latest block state root
block = w3.eth.getBlock('latest')
# calculate storate position == patricia trie key
trie_key_greeting = "0x0"
trie_key_balance = storage_position(w3.eth.defaultAccount, "0x1")
# query eth_getProof
proof = w3.eth.getProof(contract_addr, [trie_key_greeting, trie_key_balance], block.number)
# verify the value is included in the state root
is_valid_proof = verify_eth_getProof(proof, block.stateRoot)

To query a contract variable, you need to know the key used to store it in the trie. This key is based on the order in which the variable was defined in the contract. 'greeting' was defined first so its "0x0". For the 'balances' mapping it's a bit more complex as it's a combination of the position and the map's key you are accessing : keccack(LeftPad32(key, 0), LeftPad32(map position, 0)). For more details, see eth_getStorageAt here in the Ethereum wiki.

The proof object returned by w3.eth.getProof contains the account proof and an array of storage proofs that were queried ([trie_key_greeting, trie_key_balance]).

Related Solutions

[Ethereum] Transaction tree and receipt tree

With reference to the Yellow Paper and this diagram...

(Note I'm referring to them as tries, not trees. I don't suppose it matters too much in this explanation.)

Q1.As in binary merkle tree hash of a node is calculated and we combine the hash of two child node to create parent node and so on.state tree is merkle patricia tree, so how hash is calculated in this(means hash of all node or only root node)

Each node in the world state trie - with the exception of the leaf nodes - potentially has 16 child nodes (it's not a binary tree). Each leaf node represents the account of a given address. The parents of these leaf nodes are created from the hashes of their children. The parents of these nodes are again created from the hashes of their children, and so on, until you reach the root node.

Blockchain Storage – How Blocks and Tries are Stored in Merkle Patricia Tries

Low level geth database format is:

var databaseVerisionKey = new Buffer("DatabaseVersion"); // databaseVerisionKey tracks the current database version.
var headHeaderKey = new Buffer("LastHeader"); // headHeaderKey tracks the latest know header's hash.
var headBlockKey = new Buffer("LastBlock"); // headBlockKey tracks the latest know full block's hash.
var headFastBlockKey = new Buffer("LastFast"); // headFastBlockKey tracks the latest known incomplete block's hash duirng fast sync.
var fastTrieProgressKey = new Buffer("TrieSync"); // fastTrieProgressKey tracks the number of trie entries imported during fast sync.

// Data item prefixes (use single byte to avoid mixing data types, avoid `i`, used for indexes).
var headerPrefix = new Buffer("h"); // headerPrefix + num (uint64 big endian) + hash -> header
var headerTDSuffix = new Buffer("t"); // headerPrefix + num (uint64 big endian) + hash + headerTDSuffix -> td
var headerHashSuffix = new Buffer("n"); // headerPrefix + num (uint64 big endian) + headerHashSuffix -> hash
var headerNumberPrefix = new Buffer("H"); // headerNumberPrefix + hash -> num (uint64 big endian)
var blockBodyPrefix = new Buffer("b"); // blockBodyPrefix + num (uint64 big endian) + hash -> block body
var blockReceiptsPrefix = new Buffer("r"); // blockReceiptsPrefix + num (uint64 big endian) + hash -> block receipts
var txLookupPrefix = new Buffer("l"); // txLookupPrefix + hash -> transaction/receipt lookup metadata
var bloomBitsPrefix = new Buffer("B"); // bloomBitsPrefix + bit (uint16 big endian) + section (uint64 big endian) + hash -> bloom bits
var preimagePrefix = new Buffer("secure-key-");      // preimagePrefix + hash -> preimage
var configPrefix = new Buffer("ethereum-config-"); // config prefix for the db
var BloomBitsIndexPrefix = new Buffer("iB"); // BloomBitsIndexPrefix is the data table of a chain indexer to track its progress // Chain index prefixes (use `i` + single byte to avoid mixing data types).

To get data you have to recursivily build tree`s from this data. Knowing hash of state root you can find state root, and then you know hashes of children of state root, so you know children so you can get up to leafs.

Depending on geth option --gcmode archive|fast|light (you can also specifie how many blocks you want to remember), geth stores or doesn`t some tries.

Diffrent tries are world state tree (links to accounts), storage tries (account data), and receipt tries (for transaction receipts).

To get value "sample value" from tree (for example contract adress). You need to go 32 length way down the tree depending on 32 chars length sha3("sample value").

To understand better which data are stored in db and how tries are made look at these to pictures:

Best Answer

Related Solutions

[Ethereum] Transaction tree and receipt tree

Blockchain Storage – How Blocks and Tries are Stored in Merkle Patricia Tries

Related Topic