Popularity
5.9
Growing
Activity
2.4
Growing
3
7
0

Monthly Downloads: 38
Programming language: Haskell
License: BSD 3-clause "New" or "Revised" License
Tags: Data    
Latest version: v0.1.0.0

merkle-log alternatives and similar packages

Based on the "Data" category.
Alternatively, view merkle-log alternatives based on common mentions on social networks and blogs.

Do you think we are missing an alternative of merkle-log or a related project?

Add another 'Data' Package

README

Build Status

Haskell Implementation of Merkle Tree Logs

This packages implements Merkle Tree Logs similar to those described in RFC 6962 in Haskell.

Merkle Logs are a append-only data structure. The tree layout in this implementation of Merkle trees is based on the description of Merkle trees in RFC 6962. With this tree layout extending a Merkle tree requires chaining a logarithmic number of nodes at the end of the tree. Unlike RFC 6962 the Merkle trees in this module support the creation of unbalanced MerkleTrees by nesting sub-trees as leafs of Merkle trees. Also, unlike RFC 6962 this module generates fully self-contained inclusion proofs that don't rely on the client being aware of the balancing of the Merkle Tree that was used to generate the proof.

Format

The implementation stores Merkle trees in a packed format in memory. This allows for efficient construction, serialization, and querying. Trees are opaque objects that are allocated and deallocated as well as serialized and deserialized as a whole, which matches many use cases. Also, trees can be nested, by building larger Merkle trees that have smaller trees as inputs to their leafs.

The overhead per indexed item is 64 bytes when 256 bit hashes are used. Thus, about 16,000 items can be index in 1MB of memory.

We plan to make the trees extensible and support loading and storing trees in chunks that represent immutable full subtrees. Please file an issue on GitHub if you need this feature.

Proofs

Proofs are self contained and don't rely on a particular implementation of Merkle tree. In particular, proofs don't depend on how the tree is balanced.

A proof contains the proof subject (the input for which inclusion is proven) as a plain ByteString. The result of validating a proof is a Merkle tree root that must match the root of the Merkle tree that includes the subject. A proof doesn't include the root hash of the Merkle tree, because the root must be obtained from a trusted / authenticated source. Including it in the proof would thus be redundant and may even be misleading.

At the moment only inclusion / audit proofs are supported. We plan to also implement consistency proofs. Please file an issue on GitHub if you need consistency proofs.

Build and Installation

The package can be build with cabal via

cabal new-update
cabal new-build merkle-log

The test suite can be run with

cabal new-test merkle-log

Benchmarks are available via

cabal new-bench merkle-log

Benchmarks

The following benchmark results compare the performance of this package with the Merkle tree implementations in the packages merkle-tree and hash-tree for different hash functions on a 64bit Intel CPU.

Create tree:

[Create Tree Results](bench/results/create-tree.png)

Create inclusion proof:

[Create Inclusion Proof Results](bench/results/create-inclusion-proof.png)

Verify inclusion proof:

[Verify Inclusion Proof Results](bench/results/verify-inclusion-proof.png)