merkle-trees

Optimized Merkle Tree algorithm for traversal/verification and path computation. [Work In Progress]

API

This library is generic over the underlying used hash algorithm. Once the hash is provided, the main functor will return a merkle tree algorithm. The interface for such returned merkle tree module follows below:

type tree

The abstract data type of Merkle Tree instance.

val tree : string list -> tree

Computes a Merkle Tree instance given a list of leaves. This list can be of any size, but sizes such as 2.0 ** 20.0 break the runtime with stack overflow exceptions. This operation, so, is unfeasible on huge values, even if we rewrite the implementation to avoid stack overflows.

val root : tree -> string

Retrieves the Root Hash of Merkle Tree for verification. Runs in O(1) complexity.

val path : tree:tree -> leaf:string -> string list

Generates a proof-of-inclusion through a list of hashes known as the Authentication Path.

val verify : root:string -> leaf:string -> path:string list -> bool

Verifies the proof-of-inclusion of the leaf for given Merkle Tree Root Hash.