Sparse Merkle Trees: Definitions and Space-Time Trade-Offs with Applications for Balloon
Independent thesis Basic level (degree of Bachelor), 10 credits / 15 HE creditsStudent thesis
This dissertation proposes an efficient representation of a sparse Merkle tree (SMT): an authenticated data structure that supports logarithmic insertion, removal, and look-up in a verifiable manner. The proposal is general in the sense that it can be implemented using a variety of underlying non-authenticated data structures, and it allows trading time for space by the use of an abstract model which represents caching strategies. Both theoretical evaluations and performance results from a proof-of-concept implementation are provided, and the proposed SMT is applied to another authenticated data structure referred to as Balloon. The resulting Balloon has preserved efficiency in the expected case, and is improved with respect to worst case scenarios.
Place, publisher, year, edition, pages
2016. , 49 p.
Merkle Trees, Sparse Merkle Trees, Balloon, Authenticated Data Structures
IdentifiersURN: urn:nbn:se:kau:diva-42913OAI: oai:DiVA.org:kau-42913DiVA: diva2:936353
Subject / course
Engineering: Computer Engineering (300 ECTS credits)
2016-06-08, 21E 309, Universitetsgatan 2, 651 88, Karlstad, 09:15 (Swedish)
Pulls, Tobias, Postdoktor
Holleboom, Thijs J., Universitetslektor, docent