Navigating Ethereum's World State: The Role of Merkle Patricia Tries in Proof of Reserve

Authors: (1) Hamid Bateni, Nobitex Labs (hamid@europe.com); (2) Keyvan Kambakhsh, Nobitex Labs (keyvankambakhsh@gmail.com). Table of Links Abstract and 1 Introduction 2 Proof of Liability and 2.1 Commitment 2.2 Merkle Tree 2.3 Leaves Structure 2.4 Proof Statement 3 Proof of Reserve 3.1 Ethereum 3.2 Bitcoin 4 Proof of Solvency 5 Future Works and References 3.1 Ethereum Ethereum is a public blockchain protocol that uses an account-based model for its accounting system. This model is a key aspect of Ethereum’s architecture and allows for a wide range of financial transactions and applications. The protocol distinguishes between two types of accounts: externally owned accounts (EOAs) and contract accounts. EOAs are controlled by private keys and are used for simple transactions. Contract accounts, on the other hand, are governed by their internal code and are used to create smart contracts. Ethereum also introduced the concept of a Virtual Machine (VM), specifically the Ethereum Virtual Machine (EVM). The EVM is a runtime environment that executes smart contracts on the Ethereum network. These smart contracts are self-executing contracts with the terms of the agreement directly written into lines of code. These features make Ethereum an incredibly powerful platform for a wide range of decentralized applications, including but not limited to financial applications. In addition to its account-based model and the Ethereum Virtual Machine (EVM), Ethereum employs a data structure called the Merkle Patricia Tree (MPT) to manage the state of the entire blockchain network. The World State, a crucial component of Ethereum’s architecture, is represented by the MPT, enabling the efficient storage and retrieval of account information, balances, and smart contract data. The MPT is a key data structure that enhances the integrity and security of the Ethereum blockchain by providing a tamper-evident way to organize and update the state of the network, allowing for rapid verification and validation of transactions and contracts. This combination of the MPT and the EVM forms the backbone of Ethereum’s decentralized ecosystem, facilitating the creation and execution of complex, secure, and transparent applications.[8] 3.1.1 World State and MPT The World State in Ethereum is the global state of the Ethereum system, which is composed of many smaller objects known as accounts. Each account is a data structure that contains four fields: the nonce, balance, storageRoot, and codeHash. The nonce is a scalar value equal to the number of transactions sent from this address, the balance is a scalar value equal to the number of Wei owned by this address, the storageRoot is a 256-bit hash of the root node of a Merkle Patricia tree, and the codeHash is the hash of the EVM code of this account. The Merkle Patricia Trie (MPT) is a cryptographic data structure that maps keys to values. In the context of Ethereum, the MPT is used to map addresses to account states. It is a modified version of the Patricia Trie and the Merkle tree, hence the name. The MPT has three types of nodes: leaf nodes, extension nodes, and branch nodes. Leaf nodes and extension nodes are similar in that they both contain a path and a value. The difference lies in what the value represents. In a leaf node, the value is the account state, whereas in an extension node, the value is the hash of the next node. Branch nodes contain 17 items. The first 16 items point to other nodes in the trie, and the 17th item contains the value of the account state if a key ends at this node. The root hash of the MPT, which is a cryptographic hash of all the data in the trie, is stored in the header of each block. This allows for quick and efficient verification of data. By using the MPT, Ethereum can efficiently store the entire state of the system and quickly retrieve, update, or verify any part of it. This is crucial for maintaining the integrity and performance of the Ethereum network. 3.1.2 GetProof Method The Ethereum JSON-RPC API provides an eth getProof method, a function employed by Ethereum execution nodes. This method requires an address, an array of storage keys, and a block identifier as arguments, subsequently returning an object encompassing information about the account and its storage. The returned data includes the account’s balance, nonce, storage hash, and code hash, complemented by a list of nodes (in Recursive Length Prefix, or RLP, form) that form the proof of the specified account and its storage.[4] This proof essentially comprises a subset of the Merkle Patricia Trie (MPT) necessary for verifying the account’s data. It encompasses the MPT nodes along the path from the root to the account node, and to the storage nodes if storage keys were specified. Using this proof, the correctness of the account’s data and its inclusion in the state of the specified block can be independently verified. The path within the MPT is determined by the account’s address, which is employed as the key in the trie. The path to the key is a sequence of nibbles (half-bytes) derived from the key. Proof verification involves commencing at the root node of the MPT and following the path specified by the key. Each step involves comparing the node’s hash against the expected hash in the proof. If all hashes correspond and the path leads to the expected account data, the proof is validated. This mechanism allows for the verification of an account’s state at a specific block without requiring access to the entire Ethereum state, a feature that significantly enhances the scalability and efficiency of the Ethereum network. 3.1.3 Eth Balance Proof Building upon the information from the previous sections, we understand that an Ethereum address is mapped to specific data in the Ethereum World State via the Merkle Patricia Trie (MPT). The balance of an account is one such data point that is mapped. To prove that a specific address holds at least a minimum amount of Ether, we can design a Zero-Knowledge Proof (ZKP) circuit in the following manner: Our circuit will have two public inputs: • The minimum amount • The block root And several private inputs: • MPT Proof path • Account Data • Block Header Data The circuit for proving the eth minimum balance should follows this flow: 1- Hash the account data 2- Insert the hash into the MPT path 3- Verify the MPT path 4- Insert the calculated root as the state root alongside the other block header data 5- Calculate the block hash based on the block header data 6- Compare the calculated block hash with the public block root. If they match, it means we have correctly proved the data of an account in a specific block 7- In the final step, check if the balance in the account data is greater than or equal to the public minimum amount. After executing all steps in our ZKP circuit, we can prove that a we know a specific address holds at least a minimum Ether balance without revealing the address itself to other people. To implement the described flow in the ZKP circuit, certain specific functions in our zkp circuit need to be implemented. These include the Keccak hash function, Recursive Length Prefix (RLP) encoding, and MPT verification. The Keccak hash function is a cryptographic hash function that is used in Ethereum for various purposes, including calculating the block hash and the hashes of account data and MPT nodes. Implementing this function in the circuit is crucial for verifying the MPT path and the block hash. Recursive Length Prefix (RLP) encoding is a space-efficient object serialization scheme used in Ethereum. It’s used to encode the block header data and the account data. Implementing RLP encoding in the circuit allows us to handle these data structures properly. Lastly, MPT verification is necessary to check the validity of the proof path in the MPT. This involves following the path specified by the account’s address and checking the hashes at each node against the expected hashes in the proof. 3.1.4 ERC20 Balance Proof While the Ether balance proof involves verifying the state MPT for a specific address we want to prove, the ERC20 balance proof involves an additional step: verifying the contract storage for the key related to our address. ERC20 tokens are implemented as smart contracts on the Ethereum platform. The balance of ERC20 tokens for each address is stored in the contract’s storage, not in the account state as in the case of Ether. Therefore, to prove an ERC20 balance, we must access and verify the contract’s storage. The contract’s storage is a separate MPT where each key-value pair is a mapping of an address to its balance. To prove a specific ERC20 token balance, we first need to generate a proof for the contract storage. This can be done using the eth getProof method by providing the key related to the specific address we want to prove. This will return a proof that can commit to the value of the token balance for that address. Once we have this contract storage proof, we then verify the state MPT for the contract address, not the address we want to prove. This involves hashing the contract account data, inserting the hash into the MPT path, verifying the MPT path, and checking if the calculated balance in the contract storage proof matches the public minimum amount. In summary, the key difference for ERC20 balance proof is the addition of verifying the contract storage via its own MPT, and using the contract address to verify the state MPT. This allows us to prove that a specific address holds at least a minimum ERC20 token balance without revealing the address itself, providing a privacy-preserving proof of reserve for ERC20 tokens. This paper is available on arxiv under CC BY-NC-ND 4.0 DEED license. Authors: (1) Hamid Bateni, Nobitex Labs (hamid@europe.com); (2) Keyvan Kambakhsh, Nobitex Labs (keyvankambakhsh@gmail.com). Authors: Authors: (1) Hamid Bateni, Nobitex Labs (hamid@europe.com); (2) Keyvan Kambakhsh, Nobitex Labs (keyvankambakhsh@gmail.com). Table of Links Abstract and 1 Introduction Abstract and 1 Introduction 2 Proof of Liability and 2.1 Commitment 2 Proof of Liability and 2.1 Commitment 2.2 Merkle Tree 2.2 Merkle Tree 2.3 Leaves Structure 2.3 Leaves Structure 2.4 Proof Statement 2.4 Proof Statement 3 Proof of Reserve 3 Proof of Reserve 3.1 Ethereum 3.1 Ethereum 3.2 Bitcoin 3.2 Bitcoin 4 Proof of Solvency 4 Proof of Solvency 5 Future Works and References 5 Future Works and References 3.1 Ethereum Ethereum is a public blockchain protocol that uses an account-based model for its accounting system. This model is a key aspect of Ethereum’s architecture and allows for a wide range of financial transactions and applications. The protocol distinguishes between two types of accounts: externally owned accounts (EOAs) and contract accounts. EOAs are controlled by private keys and are used for simple transactions. Contract accounts, on the other hand, are governed by their internal code and are used to create smart contracts. Ethereum also introduced the concept of a Virtual Machine (VM), specifically the Ethereum Virtual Machine (EVM). The EVM is a runtime environment that executes smart contracts on the Ethereum network. These smart contracts are self-executing contracts with the terms of the agreement directly written into lines of code. These features make Ethereum an incredibly powerful platform for a wide range of decentralized applications, including but not limited to financial applications. In addition to its account-based model and the Ethereum Virtual Machine (EVM), Ethereum employs a data structure called the Merkle Patricia Tree (MPT) to manage the state of the entire blockchain network. The World State, a crucial component of Ethereum’s architecture, is represented by the MPT, enabling the efficient storage and retrieval of account information, balances, and smart contract data. The MPT is a key data structure that enhances the integrity and security of the Ethereum blockchain by providing a tamper-evident way to organize and update the state of the network, allowing for rapid verification and validation of transactions and contracts. This combination of the MPT and the EVM forms the backbone of Ethereum’s decentralized ecosystem, facilitating the creation and execution of complex, secure, and transparent applications.[8] 3.1.1 World State and MPT The World State in Ethereum is the global state of the Ethereum system, which is composed of many smaller objects known as accounts. Each account is a data structure that contains four fields: the nonce, balance, storageRoot, and codeHash. The nonce is a scalar value equal to the number of transactions sent from this address, the balance is a scalar value equal to the number of Wei owned by this address, the storageRoot is a 256-bit hash of the root node of a Merkle Patricia tree, and the codeHash is the hash of the EVM code of this account. The Merkle Patricia Trie (MPT) is a cryptographic data structure that maps keys to values. In the context of Ethereum, the MPT is used to map addresses to account states. It is a modified version of the Patricia Trie and the Merkle tree, hence the name. The MPT has three types of nodes: leaf nodes, extension nodes, and branch nodes. Leaf nodes and extension nodes are similar in that they both contain a path and a value. The difference lies in what the value represents. In a leaf node, the value is the account state, whereas in an extension node, the value is the hash of the next node. Branch nodes contain 17 items. The first 16 items point to other nodes in the trie, and the 17th item contains the value of the account state if a key ends at this node. The root hash of the MPT, which is a cryptographic hash of all the data in the trie, is stored in the header of each block. This allows for quick and efficient verification of data. By using the MPT, Ethereum can efficiently store the entire state of the system and quickly retrieve, update, or verify any part of it. This is crucial for maintaining the integrity and performance of the Ethereum network. 3.1.2 GetProof Method The Ethereum JSON-RPC API provides an eth getProof method, a function employed by Ethereum execution nodes. This method requires an address, an array of storage keys, and a block identifier as arguments, subsequently returning an object encompassing information about the account and its storage. The returned data includes the account’s balance, nonce, storage hash, and code hash, complemented by a list of nodes (in Recursive Length Prefix, or RLP, form) that form the proof of the specified account and its storage.[4] This proof essentially comprises a subset of the Merkle Patricia Trie (MPT) necessary for verifying the account’s data. It encompasses the MPT nodes along the path from the root to the account node, and to the storage nodes if storage keys were specified. Using this proof, the correctness of the account’s data and its inclusion in the state of the specified block can be independently verified. The path within the MPT is determined by the account’s address, which is employed as the key in the trie. The path to the key is a sequence of nibbles (half-bytes) derived from the key. Proof verification involves commencing at the root node of the MPT and following the path specified by the key. Each step involves comparing the node’s hash against the expected hash in the proof. If all hashes correspond and the path leads to the expected account data, the proof is validated. This mechanism allows for the verification of an account’s state at a specific block without requiring access to the entire Ethereum state, a feature that significantly enhances the scalability and efficiency of the Ethereum network. 3.1.3 Eth Balance Proof Building upon the information from the previous sections, we understand that an Ethereum address is mapped to specific data in the Ethereum World State via the Merkle Patricia Trie (MPT). The balance of an account is one such data point that is mapped. To prove that a specific address holds at least a minimum amount of Ether, we can design a Zero-Knowledge Proof (ZKP) circuit in the following manner: Our circuit will have two public inputs: • The minimum amount • The block root And several private inputs: • MPT Proof path • Account Data • Block Header Data The circuit for proving the eth minimum balance should follows this flow: 1- Hash the account data 2- Insert the hash into the MPT path 3- Verify the MPT path 4- Insert the calculated root as the state root alongside the other block header data 5- Calculate the block hash based on the block header data 6- Compare the calculated block hash with the public block root. If they match, it means we have correctly proved the data of an account in a specific block 7- In the final step, check if the balance in the account data is greater than or equal to the public minimum amount. After executing all steps in our ZKP circuit, we can prove that a we know a specific address holds at least a minimum Ether balance without revealing the address itself to other people. To implement the described flow in the ZKP circuit, certain specific functions in our zkp circuit need to be implemented. These include the Keccak hash function, Recursive Length Prefix (RLP) encoding, and MPT verification. The Keccak hash function is a cryptographic hash function that is used in Ethereum for various purposes, including calculating the block hash and the hashes of account data and MPT nodes. Implementing this function in the circuit is crucial for verifying the MPT path and the block hash. Recursive Length Prefix (RLP) encoding is a space-efficient object serialization scheme used in Ethereum. It’s used to encode the block header data and the account data. Implementing RLP encoding in the circuit allows us to handle these data structures properly. Lastly, MPT verification is necessary to check the validity of the proof path in the MPT. This involves following the path specified by the account’s address and checking the hashes at each node against the expected hashes in the proof. 3.1.4 ERC20 Balance Proof While the Ether balance proof involves verifying the state MPT for a specific address we want to prove, the ERC20 balance proof involves an additional step: verifying the contract storage for the key related to our address. ERC20 tokens are implemented as smart contracts on the Ethereum platform. The balance of ERC20 tokens for each address is stored in the contract’s storage, not in the account state as in the case of Ether. Therefore, to prove an ERC20 balance, we must access and verify the contract’s storage. The contract’s storage is a separate MPT where each key-value pair is a mapping of an address to its balance. To prove a specific ERC20 token balance, we first need to generate a proof for the contract storage. This can be done using the eth getProof method by providing the key related to the specific address we want to prove. This will return a proof that can commit to the value of the token balance for that address. Once we have this contract storage proof, we then verify the state MPT for the contract address, not the address we want to prove. This involves hashing the contract account data, inserting the hash into the MPT path, verifying the MPT path, and checking if the calculated balance in the contract storage proof matches the public minimum amount. In summary, the key difference for ERC20 balance proof is the addition of verifying the contract storage via its own MPT, and using the contract address to verify the state MPT. This allows us to prove that a specific address holds at least a minimum ERC20 token balance without revealing the address itself, providing a privacy-preserving proof of reserve for ERC20 tokens. This paper is available on arxiv under CC BY-NC-ND 4.0 DEED license. This paper is available on arxiv under CC BY-NC-ND 4.0 DEED license. available on arxiv