Logical Relations for Formally Verified Authenticated Data Structures

Simon Oddershede Gregersen, Chaitanya Agarwal, Joseph Tassarotti · 2025

Read Logical Relations for Formally Verified Authenticated Data Structures by Simon Oddershede Gregersen, Chaitanya Agarwal, Joseph Tassarotti (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2501-10802.txt.

Introduction

Simon Gregersen and co-authors prove the safety of a tool that builds signed data forms on its own. The work dates to 2025. Signed forms let far-off parties run steps and hand back proofs of the result. Such forms are hard to build and easy to get wrong.

The proof rests on a new tie logic for code that uses hash locks. Two sense models of a type frame back the proof. They show how the tool leans on type masks to guard safety and right acts. Speed tweaks to the tool pass the same proof. Hand-built forms can then link with auto code in a sound way.

Catalog record

CREATORSimon Oddershede Gregersen, Chaitanya Agarwal, Joseph Tassarotti
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE121 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2501-10802

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Logical Relations for Formally Verified Authenticated Data Structures Simon Oddershede Gregersen, Chaitanya Agarwal, Joseph Tassarotti Abstract . Authenticated data structures allow untrusted third parties to carry out operations which produce proofs that can be used to verify an operation’s output. Such data structures are challenging to develop and implement correctly. This paper gives a formal proof of security and correctness for a library that generates authenticated versions of data structures automatically. The proof is based on a new relational separation logic for reasoning about programs that use collision-resistant cryptographic hash functions. This logic provides a basis for constructing two semantic models of a type system, which are used to justify how the library makes use of type abstraction to enforce security and correctness. Using these models, we also prove the correctness of several optimizations to the library and then show how optimized, hand-written implementations of authenticated data structures can be soundly linked with automatically generated code. All of the results in this paper have been mechanized in the Coq proof assistant using the Iris framework. DOI: XXXXXXX.XXXXXXX 1. Introduction An authenticated data structure (ADS) ( Tamassia, 2003 ) is a type of data structure in which operations produce cryptographic proofs that can be used to check that the results of the operation are valid. ADSs can be used in scenarios where computations are outsourced to untrusted third parties, where the results of the computation can be verified by checking the proofs that are produced. For example, Merkle trees ( Merkle, 1987 ) are a binary tree data structure in which internal nodes of the tree contain hashes of their children. A retrieve operation on a Merkle tree produces a proof consisting of a list of hashes of nodes. A verifier that only knows the hash of the root node of the tree is able to check the result of the retrieve by re-computing what the root hash would be from the proof and comparing the result to the actual root hash. Because ADSs are used for security-critical applications, it is essential that they are correctly implemented. In particular, adversaries must not be able to construct false proofs that trick a verifier into accepting an invalid result. However, correctly developing and implementing ADSs is challenging. Moreover, it is difficult to test ADS implementations to ensure that adversarially-constructed invalid proofs are rejected. To ease the task of developing ADSs, Miller et al. (2014) develop \lambda\bullet , an extension to the OCaml programming language for implementing ADSs that use cryptographic hash functions to construct proofs. The \lambda\bullet language extends OCaml with a new class of authenticated types , which describe data that comes with an accompanying cryptographic proof. Using \lambda\bullet , a developer writes a standard implementation of a data structure, and then the compiler automatically generates code for an authenticated version. Specifically, the \lambda\bullet compiler converts a program into two different executables, called the prover and verifier executable. The prover performs operations and generates cryptographic proofs corresponding to those operations. Meanwhile, the verifier takes a proof as input and checks whether it is valid or not. Experimental evaluations show that the \lambda\bullet compiler can generate authenticated data structures with the same asymptotic running time as manually-written versions. To justify the correctness of \lambda\bullet ’s approach to generating authenticated data structures, Miller et al. (2014) present a core calculus language for a subset of \lambda\bullet and prove security and correctness properties of programs written in this language. This core calculus has separate formal operational semantics describing how the prover and verifier versions of a program should run. In these different semantics, primitive operations in the language generate or produce proofs. In addition, there is a third operational semantics for ideal execution, in which there are no proof objects and programs execute like a standard, simplified OCaml-like program. This ideal execution behavior is not intended to be run directly, but instead is used to specify how the prover and verifier should behave. In particular, all well-typed programs in this language satisfy two important properties, called security and correctness, which can be informally summarized as: • Security : If the verifier version of a program accepts a proof p and returns a value v , then either the ideal execution of the program would have also returned v , or a hash collision must have occurred during the execution of the verifier. • Correctness : If the prover version generates a proof p and returns a value v , then the ideal version would also return v , and the verifier will accept p and return v as well. In particular, if the cryptographic hash function used in the authenticated data structure operations has (strong) collision resistance, then this security property ensures that it is hard for an attacker to construct a malicious proof that deceives a verifier. However, there are three important limitations of the \lambda\bullet approach. First, maintaining a custom compiler frontend imposes development burden. Second, to achieve efficient performance, the \lambda\bullet compiler implements several optimizations related to how proof objects are stored and checked, but these optimizations are not covered by the security and correctness theorems, because the core calculus only models a simple, unoptimized version of proof object operations. Third, even with these compiler optimizations, the data structures generated by \lambda\bullet are not always as efficient as hand-written versions. For example, Miller et al. report that the \lambda\bullet -generated verifier for a binary tree structure takes twice as long to check proofs as a hand-written C version. In subsequent work, Atkey (2016) addressed the first of these limitations by showing that \lambda\bullet ’s authenticated types could be directly encoded in OCaml’s existing type system, without needing to extend the language or use a custom compiler frontend. With this approach, a programmer uses OCaml’s module system to write an implementation of a data structure that is parameterized by functions that handle proof generation and checking. Then, by linking the data structure code with three different libraries implementing these functions, one obtains the prover, verifier, and ideal versions of an authenticated data structure. Although this approach eliminates the need for a custom compiler, it raises its own challenges. Whereas Miller et al. were able to prove security and correctness of \lambda\bullet ’s core calculus by directly analyzing its new authenticated types, Atkey ’s approach achieves security and correctness by using a parametricity property ( Reynolds, 1983 ) of OCaml’s module system. Atkey hints at how existing proofs of parametricity for type systems related to OCaml’s module system could be used to prove security and correctness, but gives no formal proof. Moreover, existing parametricity theorems cannot be directly applied, since establishing security and correctness properties require reasoning about hash collisions, which is not covered. In this paper, we provide for the first time a complete proof of security and correctness for generating authenticated data structures using a typed module system. Moreover, we also address the second and third limitations of the \lambda\bullet approach described above. In particular, we prove the correctness of several optimizations for proof objects supported by \lambda\bullet ’s compiler. Additionally, we show how to prove that hand-written, optimized implementations of operations on an authenticated data structure can be safely linked with

Read the complete text