This crate implements a Namespaced Merkle Tree compatible with https://github.com/celestiaorg/nmt. To quote from their documentation:

A Namespaced Merkle Tree is an ordered Merkle tree that uses a modified hash function so that each node in the tree includes the range of namespaces of the messages in all of the descendants of each node. The leafs in the tree are ordered by the namespace identifiers of the messages. In a namespaced Merkle tree, each non-leaf node in the tree contains the lowest and highest namespace identifiers found in all the leaf nodes that are descendants of the non-leaf node, in addition to the hash of the concatenation of the children of the node. This enables Merkle inclusion proofs to be created that prove to a verifier that all the elements of the tree for a specific namespace have been included in a Merkle inclusion proof.

The concept was first introduced by @musalbas in the LazyLedger academic paper.

This implementation was developed independently by Sovereign Labs, and is not endorsed by the Celestia foundation.

NMT

An implementation of a namespaced merkle tree in Rust.

Warning

This code has not been audited, and may contain critical vulnerabilities. Do not attempt to use in production.

Functionality

• Compute merkle root

• Create index-based range proofs

• Verify index-based range proofs

• Create namespace range proofs

• Verify namespace range proofs

• Narrow namespace range proofs: supply part of the range to generate a proof for the remaining sub-range

License

Licensed under the Apache License, Version 2.0.

Unless you explicitly state otherwise, any contribution intentionally submitted for inclusion in this repository by you, as defined in the Apache-2.0 license, shall be licensed as above, without any additional terms or conditions.