Authenticated Data Structures, Generically

An authenticated data structure (ADS) is a data structure whose operations can be carried out by an untrusted prover, the results of which a verifier can efficiently check as authentic. This is done by having the prover produce a compact proof that the verifier can check along with each query result. ADSs thus support outsourcing data maintenance and processing tasks to untrusted servers without loss of integrity. Past work on ADSs has focused on particular data structures (or limited classes of data structures), one at a time, often with support only for particular operations. This paper presents a generic method, using a simple extension to a ML-like functional programming language we call lambdaAuth with which one can program authenticated operations over any data structure constructed from standard type constructors, including recursive types, sums, and products. The programmer writes the data structure largely as usual; it can then be compiled to code to be run by the prover and verifier. Using a formalization of lambdaAuth we prove that all well-typed lambdaAuth programs result in code that is secure under the standard cryptographic assumption of collision-resistant hash functions. We have implemented our approach as an extension to the OCaml compiler, and have used it to produce authenticated versions of many interesting data structures including binary search trees, red-black trees, skip lists, and more. Performance experiments show that our approach is efficient, giving up little compared to the hand-optimized data structures developed previously.

Joint work with Andrew Miller, Jonathan Katz, and Elaine Shi

Date:
Speakers:
Michael Hicks
Affiliation:
University of Maryland College Park
    • Portrait of Jeff Running

      Jeff Running