Please log in to watch this conference skillscast.
The most prominent example of such data structures is Merkle Trees, famously used in the Bitcoin protocol. Merkle Trees allow "lightweight clients" (verifier) to query "full nodes" (prover) about transactions contained in blocks without having to store all block data by themselves.
Andrew Miller et al. published a paper titled "Authenticated Data Structures, Generically" in Proceedings of the ACM Conference on Principles of Programming Languages (POPL), January 2014, where they show how a modified OCaml compiler can equip a wide variety of functional data structures automatically and generically with ADS capabilities - the same piece of OCaml source code is compiled into two different binaries, one version for the prover, one for the verifier. (http://soc1024.ece.illinois.edu/gpads/)
During this talk, you will learn how the same idea can be implemented in a lightweight way as a Haskell library (without the need for a modified compiler): Lars will introduce an abstract monad AuthM (together with a corresponding monad transformer AuthT), that comes with two interpreters, allowing two different interpretations of the same monadic code, one for the prover, one for the verifier.
The running example from the paper, a simple binary tree with authenticated lookup, can easily be implemented in AuthM.
The approach is flexible enough to allow for more sophisticated structures like balanced trees with authenticated insert, delete and lookup.
This is a nice case study of the use of different interpreters for a free monad and should appeal to a wider audience, not just those interested in ADS's.
The code can be found on GitHub.
YOU MAY ALSO LIKE:
- This Ain't Your Daddy's Probability Monad - Modelling Probabilistic Time in Haskell (SkillsCast recorded in October 2019)
- Haskell Fundamentals (2-Day Course) with Alejandro Serrano (Online Course on 5th - 6th July 2021)
- Haskell Fundamentals (4-Day Course) with Alejandro Serrano (Online Course on 8th - 11th November 2021)
- Haskell eXchange 2021 (Online Conference on 16th - 17th November 2021)
- Theorems for Free (SkillsCast recorded in November 2020)
- Comparing Strict and Lazy (SkillsCast recorded in November 2020)
Authenticated Data Structures, Generically, in Haskell