Change search
ReferencesLink to record
Permanent link

Direct link
Sparse Merkle Trees: Definitions and Space-Time Trade-Offs with Applications for Balloon
Karlstad University.
2016 (English)Independent thesis Basic level (degree of Bachelor), 10 credits / 15 HE creditsStudent thesis
Abstract [en]

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.
Keyword [en]
Merkle Trees, Sparse Merkle Trees, Balloon, Authenticated Data Structures
National Category
Computer Science
URN: urn:nbn:se:kau:diva-42913OAI: diva2:936353
Subject / course
Computer Science
Educational program
Engineering: Computer Engineering (300 ECTS credits)
2016-06-08, 21E 309, Universitetsgatan 2, 651 88, Karlstad, 09:15 (Swedish)
Available from: 2016-06-20 Created: 2016-06-13 Last updated: 2016-06-20Bibliographically approved

Open Access in DiVA

fulltext(1715 kB)22 downloads
File information
File name FULLTEXT01.pdfFile size 1715 kBChecksum SHA-512
Type fulltextMimetype application/pdf
Arkivfil(1723 kB)36 downloads
File information
File name FULLTEXT02.pdfFile size 1723 kBChecksum SHA-512
Type fulltextMimetype application/pdf

By organisation
Karlstad University
Computer Science

Search outside of DiVA

GoogleGoogle Scholar
Total: 58 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Total: 87 hits
ReferencesLink to record
Permanent link

Direct link