10x? Acceleration of Tx Execution Without State Trie

Archived Tendermint
1

Motivation

To make sure the majority validators agree on the same application state, the block header of Tendermint includes a apphash field, which contains the hash of the application state (generally a KV map). To efficiently compute the hash of the application state after applying the transactions of a block, we use a Merkle tree (e.g., IAVL tree or Merkle Patricia Tree (MPT)) to represent the application state and use the root hash as apphash. However, when the number of accounts is large (e.g., Ethereum currently has 100M unique addresses), reading/updating the Merkle tree can result in multiple KV store get/put operations. Further, extra storage space of the state map is also needed (compared to a plain KV map) to keep the internal nodes of the Merkle tree.

The motivation of the proposal is to circumvent the Merkle tree by exploiting one great benefit of Tendermint - forkless. Unlike probabilistic-finality chains such as PoW-based chains, every block passed to the application (via BeginBlock/DeliverTx/EndBlock/CommitBlock) in Tendermint will be finalized and thus not be reverted due to re-org. This means that we only need to maintain a single version of the application state rather than multiple in Ethereum.

Proposal

Instead of maintaining a Merkle tree and use its root hash as apphash, we use a plain KV store to maintain the state of the application. To make sure every validator agrees on the same state of the application, we use the hash of the write set of the transactions of a block as the apphash:

  • the hash of a list of put(k, v) and delete(k) operations that are generated by the transactions of the block, which can be efficiently computed since the operations are in-memory.

As a result, the validators vote and agree on the hash of the results (deltas) of a block instead of the hash of the application state of a block - they are essentially the same as long as the validators agree on the history of all deltas of the blocks, i.e., prevBlockHash thanks to the nature of blockchain.

In addition, thanks to the forkless feature of Tendermint, we only need to maintain the latest version of the application state in plain KV store instead of multiple versions of the application state corresponding to different blocks, which Ethereum must maintain in order to deal with re-org.

Using the hash of the deltas as apphash, there are several benefits of using plain KV store to maintain the application state:

  • IO saving: Getting a value from the application state takes one KV get operation, while Merkle tree can take multiple gets, which is greater if the tree size is larger;
  • CPU saving: Less hash computation and encoding/decoding in reading/updating nodes;
  • Storage saving: No need to store internal nodes.

Early Comparison on Savings

We use a machine with 8 core-CPU, 22G memory, and SSD storage. The early result is summarized as follows.

image
image830×77 9.4 KB

where we observe about 10x performance in get/update and about 3x storage space reduction. Comparisons with MPT and large number of accounts are on-going.

3 Likes
2

This is a good analogy imo. Thanks for sharing.

I think entire state hash can be voted for every 1k blocks as a periodic snapshot if we want to confirm it periodically.

3

Yes, we could definitively include the entire state hash for every 1K blocks (likely the hash of the state for the previous 1K block, i.e., block height with current_block_height - 1K so that we could have 1K block time to calculate the hash if we do not maintain a Merkle). This could also help a fast-sync client to download and verify the latest state snapshot by using the state hash of the block with nearest height that is multiple of 1K, and then get the latest state by replying the remaining blocks.