Scalable and Efficient Data Authentication for Decentralized Systems

Abstract

Decentralized systems such as blockchains promise to fundamentally change how untrusted parties exchange data and assets. A key challenge in the decentralized setting is scalably authenticating data in the system. Merkle Patricia trees (MPT) are widely used in decentralized systems like Ethereum, to verify that the data is correct and up-to-date. Unfortunately, MPTs incur significant overhead due to random IO operations, serialization, and hashing. This paper presents the Distributed Merkle Patrica Tree (DMPT), a novel data structure that reduces the overheads of the MPT. A DMPT vertically shards the MPT across the memory of multiple nodes, eliminating the IO bottleneck. DMPTs reduce network bandwidth utilization using a combination of novel techniques such as witness compaction and node bagging. Compared to the MPT used in Ethereum, put and get operations in the DMPT achieve 80-160x better throughput, even when the Ethereum MPT is stored in memory. We demonstrate the effectiveness of DMPT by building FVCHAIN (Fast Verification blockchain), a modified version of Ethereum which uses DMPT instead of MPT. In a four-region geo-distributed deployment, FVCHAIN can verify 20,000 transactions per second (20x higher than Ethereum).