Aardvark: An Asynchronous Authenticated Dictionary with Applications to Account-based Cryptocurrencies

We design Aardvark, a novel authenticated dictionary with short proofs of correctness for lookups and modifications. Our design reduces storage requirements for transaction validation in cryptocurrencies by outsourcing data from validators to untrusted servers, which supply proofs of correctness of this data as needed. In this setting, short proofs are particularly important because proofs are distributed to many validators, and the transmission of long proofs can easily dominate costs. A proof for a piece of data in an authenticated dictionary may change whenever any (even unrelated) data changes. This presents a problem for concurrent issuance of cryptocurrency transactions, as proofs become stale. To solve this problem, Aardvark employs a versioning mechanism to safely accept stale proofs for a limited time. On a dictionary with 100 million keys, operation proof sizes are about 1KB in a Merkle Tree versus 100-200B in Aardvark. Our evaluation shows that a 32-core validator processes 1492-2941 operations per second, saving about 800× in storage costs relative to maintaining the entire state.