Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
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
Identifiers
URN: urn:nbn:se:kau:diva-42913OAI: oai:DiVA.org:kau-42913DiVA: diva2:936353
Subject / course
Computer Science
Educational program
Engineering: Computer Engineering (300 ECTS credits)
Presentation
2016-06-08, 21E 309, Universitetsgatan 2, 651 88, Karlstad, 09:15 (Swedish)
Supervisors
Examiners
Available from: 2016-06-20 Created: 2016-06-13 Last updated: 2016-06-20Bibliographically approved

Open Access in DiVA

fulltext(1715 kB)79 downloads
File information
File name FULLTEXT01.pdfFile size 1715 kBChecksum SHA-512
167ecebc925fda496c735d1d1a8acd00d86a72e454e0869a0dd5afb201e5e0908b07130ee144478c5f4e01acdff8b49d2ea9a4accdc1b529342d77646b96c97f
Type fulltextMimetype application/pdf
Arkivfil(1723 kB)248 downloads
File information
File name FULLTEXT02.pdfFile size 1723 kBChecksum SHA-512
dad5a9bf05dc994a7108b44e910dfcdc853ea7e3624a4f5ab42c15558948162f98384e907c29f489df14c75ec19304c5983cf4a7d6081ed188d52c5231b713b5
Type fulltextMimetype application/pdf

By organisation
Karlstad University
Computer Science

Search outside of DiVA

GoogleGoogle Scholar
Total: 327 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

urn-nbn

Altmetric score

urn-nbn
Total: 271 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf