Fast Tx Execution Without State Trie

[adlerjohn]

@qizhou

instead of including the hash of the state in each block, we include the hash of the updates of the state

You’re describing the Merkle root of transactions in an UTXO-based chain: Block Chain — Bitcoin.

@qizhou

a list of DB write and delete operations, after performing all the transactions in the block. As a result, a read from the state always takes one DB read, and a write to the state always takes one DB write - no matter how many entries are in the state.

You’re describing the UTXO data model: Practical parallel transaction validation without state lookups using Merkle accumulators.

@qizhou

If the chain is re-organized, how to recover the state of a previous block

Just un-apply the state deltas.

@qizhou

How to quickly synchronize a node?

Since you don’t need to compute a state root at every block, you can simply apply all the state updates from genesis (very cheap) and compute the final root. Signature verification can be skipped if we only care about verifying the integrity of a state snapshot, not its correctness: bitcoin/doc/release-notes/release-notes-0.14.0.md at cc9d09e73de0fa5639bd782166b171448fd6b90b · bitcoin/bitcoin · GitHub.

@qizhou

How to lightly check if a key-value pair is in the latest state?

One way is by changing the block format to order inputs and outputs: Compact Fraud Proofs for UTXO Chains Without Intermediate State Serialization. Then you can provide exclusion proofs for each block that a UTXO wasn’t spent. Linear in the number of blocks unfortunately, so maybe not applicable to on-chain light clients.