Paper 2020/975

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

Derek Leung, Yossi Gilad, Sergey Gorbunov, Leonid Reyzin, and Nickolai Zeldovich


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.

Note: Remove first-page box containing copyright and publication ID, which had been added for submission to a conference but erroneously left in the pre-print.

Available format(s)
Publication info
Published elsewhere. Minor revision. 31st USENIX Security Symposium
Contact author(s)
dtl @ csail mit edu
2021-10-16: last of 2 revisions
2020-08-18: received
See all versions
Short URL
Creative Commons Attribution


      author = {Derek Leung and Yossi Gilad and Sergey Gorbunov and Leonid Reyzin and Nickolai Zeldovich},
      title = {Aardvark: An Asynchronous Authenticated Dictionary with Applications to Account-based Cryptocurrencies},
      howpublished = {Cryptology ePrint Archive, Paper 2020/975},
      year = {2020},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.