Parallel Transaction Execution in Blockchain and the Ambiguous State Representation Problem

Blockchains commonly employ tree data structures (e.g., Merkle trees) to represent state. While tree structures enable fast and compact state correctness checks, they introduce constraints when it comes to parallelizing transaction execution. In particular, concurrent transaction execution can lead to multiple trees representing the same state, hindering consensus among blockchain peers. We characterize this phenomenon as the ambiguous state representation problem and propose an optimistic algorithm that guarantees the creation of the same state tree across multiple peers. We integrated our solution into Cosmos SDK framework, a popular production blockchain system, allowing applications to benefit from parallel transaction execution without modifying their existing codebase. We report on the performance of parallel transaction execution under a variety of conditions in a network of up to 40 peers.