Derek Leung
February 1, 2023 at 11:00 AM on Zoom / Soda Hall
Aardvark: An Asynchronous Authenticated Dictionary with Applications to Account-based Cryptocurrencies
Abstract: 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.
Bio: Derek Leung is a Ph.D. student advised by Nickolai Zeldovich at MIT CSAIL. His interests are in formal verification, consensus protocols, and applied cryptography. He graduated from the University of California, Berkeley, in 2016 with a B.A. in Computer Science and Mathematics. At Berkeley, he worked on usable security with David Wagner and was a teaching assistant for Joseph Hellerstein. From 2018 to 2020, he was a software engineer and a manager at the cryptocurrency startup Algorand, where he implemented its Byzantine consensus protocol.