License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/OASIcs.FMBC.2020.6
URN: urn:nbn:de:0030-drops-134196
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/13419/
Go to the corresponding OASIcs Volume Portal

Lochbihler, Andreas ; Marić, Ognjen

Authenticated Data Structures as Functors in Isabelle/HOL

pdf-format:
OASIcs-FMBC-2020-6.pdf (0.4 MB)

Abstract

Merkle trees are ubiquitous in blockchains and other distributed ledger technologies (DLTs). They guarantee that the involved systems are referring to the same binary tree, even if each of them knows only the cryptographic hash of the root. Inclusion proofs allow knowledgeable systems to share subtrees with other systems and the latter can verify the subtrees' authenticity. Often, blockchains and DLTs use data structures more complicated than binary trees; authenticated data structures generalize Merkle trees to such structures.
We show how to formally define and reason about authenticated data structures, their inclusion proofs, and operations thereon as datatypes in Isabelle/HOL. The construction lives in the symbolic model, i.e., we assume that no hash collisions occur. Our approach is modular and allows us to construct complicated trees from reusable building blocks, which we call Merkle functors. Merkle functors include sums, products, and function spaces and are closed under composition and least fixpoints. As a practical application, we model the hierarchical transactions of Canton, a practical interoperability protocol for distributed ledgers, as authenticated data structures. This is a first step towards formalizing the Canton protocol and verifying its integrity and security guarantees.

BibTeX - Entry

@InProceedings{lochbihler_et_al:OASIcs:2020:13419,
  author =	{Andreas Lochbihler and Ognjen Marić},
  title =	{{Authenticated Data Structures as Functors in Isabelle/HOL}},
  booktitle =	{2nd Workshop on Formal Methods for Blockchains (FMBC 2020)},
  pages =	{6:1--6:15},
  series =	{OpenAccess Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-169-6},
  ISSN =	{2190-6807},
  year =	{2020},
  volume =	{84},
  editor =	{Bruno Bernardo and Diego Marmsoler},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/13419},
  URN =		{urn:nbn:de:0030-drops-134196},
  doi =		{10.4230/OASIcs.FMBC.2020.6},
  annote =	{Keywords: Merkle tree, functor, distributed ledger, datatypes, higher-order logic}
}

Keywords: Merkle tree, functor, distributed ledger, datatypes, higher-order logic
Collection: 2nd Workshop on Formal Methods for Blockchains (FMBC 2020)
Issue Date: 2020
Date of publication: 11.12.2020
Supplementary Material: The formalization is available in the Archive of Formal Proofs [Andreas Lochbihler and Ognjen Marić, 2020]: http://isa-afp.org/entries/ADS_Functor.html.

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI