Cryptology ePrint Archive: Report 2020/975

Aardvark: A Concurrent Authenticated Dictionary with Short Proofs

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

Abstract: We design Aardvark, a novel authenticated dictionary backed by vector commitments with short proofs. Aardvark guarantees the integrity of outsourced data by providing proofs for lookups and modifications, even when the servers storing the data are untrusted. To support high-throughput, highly-parallel applications, Aardvark includes a versioning mechanism that allows the dictionary to accept stale proofs for a limited time.

We apply Aardvark to the problem of decoupling storage from transaction verification in cryptocurrencies. Here networking resources are at a premium and transmission of long proofs can easily become the dominant cost, with multiple users reading and writing concurrently.

We implement Aardvark and evaluate it as a standalone authenticated dictionary. We show that Aardvark saves substantial storage resources while incurring limited extra bandwidth and processing costs.

Category / Keywords: applications / vector-commitments, authenticated-data-structures

Date: received 10 Aug 2020, last revised 18 Aug 2020

Contact author: dtl at csail mit edu

Available format(s): PDF | BibTeX Citation

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.

Version: 20200818:170150 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]