Crate nmt_rs

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.

Re-exports

pub use nmt_proof::NamespaceProof;

Modules

nmt_proof

Adds “namespacing” semantics to proofs for the simple merkle tree, enabling consumers to check that

simple_merkle

Implements a simple RFC 6962 compatible merkle tree over an in-memory data store which maps preimages to hashes.

Structs

InvalidNamespace

An error indicating that a namespace is invalid

InvalidNamespacedHash

The error returned when failing to convert a slice to a namespaced hash

NamespaceId

A namespace identifier

NamespaceMerkleTree

A namespaced merkle tree, implemented as a wrapper around a simple merkle tree.

NamespacedHash

A hash of some data, together with a namespace range

NamespacedSha2Hasher

A sha256 hasher which also supports namespacing

TmSha2Hasher

A sha256 hasher, compatible with Tendermint merkle hash

Enums

RangeProofType

Indicates whether the proof includes all leaves from every namespace it covers.

Constants

HASH_LEN

The length of a hash in bytes

INTERNAL_NODE_DOMAIN_SEPARATOR

A domain separator indicating that a node is internal

LEAF_DOMAIN_SEPARATOR

A domain separator indicating that a node is a leaf

Traits

NamespaceMerkleHasher

An extension of MerkleHash indicating that the hasher is namespace aware. This allows for the creation of namespaced merkle trees and namespaced merkle proofs.

Type Aliases

CelestiaNmt

A namespaced merkle tree as used in Celestia. Uses a sha256 hasher and 29 byte namespace IDs.

DefaultHasher

The default hasher. Currently sha256