Authenticated modular maps in Haskell

ABSTRACT

We present hamm, a Haskell library that enables programmers to easily configure authenticated map (key-value store) implementations. We use type level programming techniques to establish an extensible foundation, and provide an example base map and several example “add on” transformers supporting features such as caches, Bloom filters and paging structures. Another add-on enables a prover to provide—and a verifier to verify—a “summary” containing only a small subset of the map’s data, and a verifier to receive and verify additional data only if needed. Preliminary performance results demonstrate significant potential for authenticated maps configured using hamm to support our goal of enabling participants to join blockchain networks faster.

References

1. 2018. auth-adt. (2018). https://github.com/adjoint-io/auth-adt
2. Burton H. Bloom. 1970. Space/Time Trade-offs in Hash Coding with Allowable Errors. Commun. ACM 13, 7 (July 1970), 422-426.
3. Manuel M. T. Chakravarty, Gabriele Keller, Simon Peyton Jones, and Simon Marlow. 2005. Associated Types with Class. In Proceedings of the 32Nd ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL '05). ACM, New York, NY, USA, 1-13.
4. James Cheney and Ralf Hinze. 2003. First-class phantom types. Technical Report. Cornell University.
5. T.H. Cormen, T.H. Cormen, C.E. Leiserson, R.L. Rivest, Massachusetts Institute of Technology, C. Stein, Inc Books24x7, MIT Press, and McGraw-Hill Publishing Company. 2001. Introduction To Algorithms. MIT Press.
6. Cryptographic hash functions 2018. Cryptographic hash functions. (2018). https://en.wikipedia.org/wiki/Cryptographic_hash_function.
7. Richard A. Eisenberg, Stephanie Weirich, and Hamidhasan G. Ahmed. 2016. Visible Type Application. In Programming Languages and Systems, Peter Thiemann (Ed.). Springer Berlin Heidelberg, Berlin, Heidelberg, 229-254.
8. GHC Team. 2018. GHC 8.4.1 User's Guide. (2018). https://downloads.haskell.org/~ghc/8.4.1/docs/html/users_guide/.
9. Sheng Liang, Paul Hudak, and Mark Jones. 1995. Monad Transformers and Modular Interpreters. In Proceedings of the 22Nd ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL '95). ACM, New York, NY, USA, 333-343.
10. Ralph C. Merkle. 1988. A Digital Signature Based on a Conventional Encryption Function. In Advances in Cryptology -- CRYPTO '87, Carl Pomerance (Ed.). Springer Berlin Heidelberg, Berlin, Heidelberg, 369-378.
11. Alp Mestanogullari, Sönke Hahn, Julian K. Arni, and Andres Löh. 2015. Type-level Web APIs with Servant: An Exercise in Domain-specific Generic Programming. In Proceedings of the 11th ACM SIGPLAN Workshop on Generic Programming (WGP 2015). ACM, New York, NY, USA, 1-12.
12. Andrew Miller, Michael Hicks, Jonathan Katz, and Elaine Shi. 2014. Authenticated Data Structures, Generically. SIGPLAN Not. 49, 1 (Jan. 2014), 411-423.
13. Satoshi Nakamoto. 2009. Bitcoin: A peer-to-peer electronic cash system. (2009). http://www.bitcoin.org/bitcoin.pdf
14. Péter Szilágyi. 2015. eth/63 fast synchronization algorithm #1889. (2015). https://github.com/ethereum/go-ethereum/pull/1889
15. Brent A. Yorgey, Stephanie Weirich, Julien Cretin, Simon Peyton Jones, Dimitrios Vytiniotis, and José Pedro Magalhães. 2012. Giving Haskell a Promotion. In Proceedings of the 8th ACM SIGPLAN Workshop on Types in Language Design and Implementation (TLDI '12). ACM, New York, NY, USA, 53-66.

Index Terms

• Software and its engineering

  • Software organization and properties

    • Software system structures

      • Abstraction, modeling and modularity