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.
-
semantic-source
Parsing, analyzing, and comparing source code across many languages -
lens
Lenses, Folds, and Traversals - Join us on web.libera.chat #haskell-lens -
code-builder
Packages for defining APIs, running them, generating client code and documentation. -
text
Haskell library for space- and time-efficient operations over Unicode text. -
cassava
A CSV parsing and encoding library optimized for ease of use and high performance -
unordered-containers
Efficient hashing-based container types -
compendium-client
Mu (μ) is a purely functional framework for building micro services. -
holmes
A reference library for constraint-solving with propagators and CDCL. -
binary
Efficient, pure binary serialisation using ByteStrings in Haskell. -
resource-pool
A high-performance striped resource pooling implementation for Haskell -
primitive
This package provides various primitive memory-related operations. -
discrimination
Fast linear time sorting and discrimination for a large class of data types -
audiovisual
Extensible records, variants, structs, effects, tangles -
IORefCAS
A collection of different packages for CAS based data structures. -
dependent-sum
Dependent sums and supporting typeclasses for comparing and displaying them -
reflection
Reifies arbitrary Haskell terms into types that can be reflected back into terms -
dependent-map
Dependently-typed finite maps (partial dependent products) -
streaming
An optimized general monad transformer for streaming applications, with a simple prelude of functions -
orgmode-parse
Attoparsec parser combinators for parsing org-mode structured text! -
safecopy
An extension to Data.Serialize with built-in version control -
text-icu
This package provides the Haskell Data.Text.ICU library, for performing complex manipulation of Unicode text. -
scientific
Arbitrary-precision floating-point numbers represented using scientific notation -
uuid-types
A Haskell library for creating, printing and parsing UUIDs
Static code analysis for 29 languages.
Do you think we are missing an alternative of merkle-log or a related project?
README
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)