Seminar: Authenticated Data Structures for Stateless Validation and Transparency Logs


Date/Time: 05-Nov-2020, 16:00 UTC

Venue: Virtual Seminar



There is an increasing demand for more versatility in authenticated data structures. For example, statelessly validating transactions in cryptocurrencies such as Ethereum requires updatable authenticated dictionaries (ADs) with aggregatable proofs. Furthermore, transparency logs such as Certificate Transparency (CT) require provably append-only ADs with succinct proofs.

Unfortunately, traditional Merkle-based authenticated data structures do not have these properties and yet are at the core of all these protocols. Furthermore, enhancing Merkle trees with these properties is either not possible or not efficient, requiring expensive argument systems (e.g., SNARKs). In this talk, I will present new techniques for authenticated data structures that can meet the demands of such modern cryptographic applications.

First, I present asymptotically-efficient append-only authenticated dictionaries (AADs) built from any set commitment or accumulator scheme. Our AADs are the first to simultaneously support logarithmic-sized lookup proofs and append-only proofs, solving a decade-old open problem. Second, I present vector commitments (VCs) from polynomial commitments with constant-sized, efficiently-updatable and aggregatable proofs. Our VC scheme is concretely-efficient and supports precomputing all proofs efficiently, making it ideal for stateless validation of payments. Third, I present authenticated dictionaries (ADs) with a new notion of cross-incremental proof aggregation, which allows aggregating proofs with respect to different dictionaries (and doing so incrementally). Our ADs are ideal for stateless validation of smart contract executions, where it is important to aggregate proofs for different smart contracts.

Overall, our techniques are much more powerful for stateless validation and transparency logging than Merkle trees, and leave the door open for a new generation of authenticated data structures.


Alin Tomescu is interested in applied cryptography, mostly walking the fine line between theory and practice. In the past, he has worked on oblivious RAMs, public-key distribution, authenticated data structures, and threshold cryptography. He especially enjoys implementing and open-sourcing his work. He sometimes blogs about his work and muse about other things on my website. For paper LaTeX and PDFs, slides, code artifacts and talk videos, please see

Add to Calendar

This page was last modified on 27 Mar 2014.