Secure Tree — Why State Trie’s Key is 256 Bits

As explained in the last article, Ethereum’s state is stored in the modified Merkle Patricia Trie(a.k.a. MPT). When it comes to Ethereum, values can be nonce, balance, and account’s state, and the key that corresponds to those values is the account’s address. Since this account’s address is 160 bits, if you were to follow the path of 40 nibbles from the root of the MPT, it should reveal the status of the account. However, in reality, if a node that contains an account’s address as a key is within a MPT that stores Ethereum’s status is found, then a branch node or an extension node is revealed instead of a leaf node.

This is because when Ethereum puts an account into the MPT, it doesn’t use the account’s address as a key, but uses the address’ keccak-256 hash as the key. Thus, you should not follow 40 nibbles of an account address, but 64 nibbles of hash in order to find the desired account. This method of using an account’s hash as the path instead of the account’s address is called using the secure tree in Ethereum.

Before explaining about the secure tree, there are a few more things to know about the MPT that Ethereum uses. Ethereum’s MPT is not only involve the state trie. There are 4 types of MPT in Ethereum.

The first is the state trie. It is where Ethereum’s account information is stored. The account information is the hash of the nonce, balance, and storage root, and the hash of the code. If the account has a smart contract, then a MPT’s root that contains the smart contract’s state is stored in the storage root. In the code, the evm bytecode’s hash value is stored.

The second is the storage trie. Ethereum’s smart contract contains a state. Thus, every account that has a smart contract has a storage trie that contains the state of the contract.

The other two are known as the transactions trie, and the receipts trie. Each of these is an MPT that takes an index of the array as the key when an array that contains the results of the executed transactions that are contained in their respective blocks. Transactions trie and receipts trie are used for merkle proofs.

Out of these four MPTs, only the state trie and storage trie use a secure tree, and the other two do not use a secure trie. In other words, the state and storage trie uses a keccak-256 hash value, which is a 256 bit value, as their key. Transactions and receipts tries use their own keys of arbitrary lengths.

The reason Ethereum uses a secure tree to prevent a DoS attack. Both the state and storage trie are stored in a file. That is, if there are new nodes added into, a modification of, or an attempt to read these two tries, there must be a disk IO, and if possible, must pass by the least amount of nodes possible until reaching the leaf node. For this reason, MPT allowed for the compressing of the 1-child branch node with the extension node.

However, only branch nodes with a single child can be compressed into an extension node. Thus, if an attacker can maliciously create a branch node with two children, he/she can attack at a low cost. Thus, the secure tree uses a keccak-256 hash value as its key, and prevents an attacker from creating a node at a location that he/she desires.

The reason transactions trie and receipts trie do not use a secure tree is because it cannot protect anything by hashing the key. Since the keys in these two tries are the transactions’ and receipts’ index values, the attacker cannot insert his/her own key.

Furthermore, a secure tree has an advantage where its keys are fixed as 256 bit. This guarantees that the depth of the tree is less than 64, so one can calculate the maximum cost of changing any value of the state trie or storage trie. In particular, the state or storage trie is read or modified by a transaction. At this moment, it does not matter in which node the value that has been modified exists in. If it does the same work, then the transaction cost is the same. Thus, the biggest advantage of the secure tree is that the maximum cost is always ensured.

Originally published at medium on June 1, 2018.