Paper 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.
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.
Metadata
- Available format(s)
- Category
- Applications
- Publication info
- Preprint. MINOR revision.
- Keywords
- vector-commitmentsauthenticated-data-structures
- Contact author(s)
- dtl @ csail mit edu
- History
- 2021-10-16: last of 2 revisions
- 2020-08-18: received
- See all versions
- Short URL
- https://ia.cr/2020/975
- License
-
CC BY