nmt

package module
v0.12.0 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Dec 16, 2022 License: Apache-2.0 Imports: 7 Imported by: 36

README

Namespaced Merkle Tree (NMT)

Go version API Reference golangci-lint Go codecov.io

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.

Example

package main

import (
    "bytes"
    "crypto/sha256"
    "fmt"

    "github.com/celestiaorg/nmt"
    "github.com/celestiaorg/nmt/namespace"
)

func main() {
    // the tree will use this namespace size
    nidSize := 1
    // the leaves that will be pushed
    data := [][]byte{
      append(namespace.ID{0}, []byte("leaf_0")...),
      append(namespace.ID{0}, []byte("leaf_1")...),
      append(namespace.ID{1}, []byte("leaf_2")...),
      append(namespace.ID{1}, []byte("leaf_3")...)}
    // Init a tree with the namespace size as well as
    // the underlying hash function:
    tree := nmt.New(sha256.New(), nmt.NamespaceIDSize(nidSize))
    for _, d := range data {
      if err := tree.Push(d); err != nil {
        panic(fmt.Sprintf("unexpected error: %v", err))
      }
    }
    // compute the root
    root := tree.Root()
    // the root's min/max namespace is the min and max namespace of all leaves:
    minNS := nmt.MinNamespace(root, tree.NamespaceSize())
    maxNS := nmt.MaxNamespace(root, tree.NamespaceSize())
    if bytes.Equal(minNS, namespace.ID{0}) {
      fmt.Printf("Min namespace: %x\n", minNS)
    }
    if bytes.Equal(maxNS, namespace.ID{1}) {
      fmt.Printf("Max namespace: %x\n", maxNS)
    }

    // compute proof for namespace 0:
    proof, err := tree.ProveNamespace(namespace.ID{0})
    if err != nil {
      panic("unexpected error")
    }

    // verify proof using the root and the leaves of namespace 0:
    leafs := [][]byte{
      append(namespace.ID{0}, []byte("leaf_0")...),
      append(namespace.ID{0}, []byte("leaf_1")...),
    }

    if proof.VerifyNamespace(sha256.New(), namespace.ID{0}, leafs, root) {
      fmt.Printf("Successfully verified namespace: %x\n", namespace.ID{0})
    }

    if proof.VerifyNamespace(sha256.New(), namespace.ID{2}, leafs, root) {
      panic(fmt.Sprintf("Proof for namespace %x, passed for namespace: %x\n", namespace.ID{0}, namespace.ID{2}))
    }
}

The above will create a Namespaced merkle tree with four leafs which looks like this:

example

Where nid_0 = nid_1 = 0 and nid_2 = nid_3 = 1 and data_i = "leaf_i" for i = 0,...,3.

This implementation (currently) uses NebulousLabs' merkletree implementation and was heavily inspired by the initial implementation in the celestiaorg prototype.

Documentation

Overview

Package nmt contains an NMT implementation.

Index

Examples

Constants

View Source 
const (
	LeafPrefix = 0
	NodePrefix = 1

	DefaultNamespaceIDLen = 8
)

Variables

View Source 
var (
	ErrInvalidRange            = errors.New("invalid proof range")
	ErrMismatchedNamespaceSize = errors.New("mismatching namespace sizes")
	ErrInvalidPushOrder        = errors.New("pushed data has to be lexicographically ordered by namespace IDs")
)

Functions

func GetSubrootPaths 

func GetSubrootPaths(squareSize uint, idxStart uint, shareCount uint) ([][][]int, error)

GetSubrootPaths is a pure function that takes arguments: square size, share index start, and share Count, and returns a minimal set of paths to the subtree roots that encompasses that entire range of shares, with each top level entry in the list starting from the nearest row root.

An empty entry in the top level list means the shares span that entire row and so the root for that segment of shares is equivalent to the row root.

func MaxNamespace 

func MaxNamespace(hash []byte, size namespace.IDSize) []byte

MaxNamespace parses the maximum namespace id from a given hash

func MinNamespace 

func MinNamespace(hash []byte, size namespace.IDSize) []byte

MinNamespace parses the minimum namespace id from a given hash

func Sha256Namespace8FlaggedInner 

func Sha256Namespace8FlaggedInner(leftRight []byte) []byte

Sha256Namespace8FlaggedInner hashes inner nodes to: minNID || maxNID || sha256(NodePrefix || leftRight), where leftRight consists of the full left and right child node bytes, including their respective min and max namespace IDs. Hence, the input has to be of size: 48 = 32 + 8 + 8 = sha256.Size + 2*DefaultNamespaceIDLen bytes. If the input does not fulfil this, we will panic. The output will also be of length 2*DefaultNamespaceIDLen+sha256.Size = 48 bytes.

func Sha256Namespace8FlaggedLeaf 

func Sha256Namespace8FlaggedLeaf(namespacedData []byte) []byte

Sha256Namespace8FlaggedLeaf uses sha256 as a base-hasher, 8 bytes for the namespace IDs and ignores the maximum possible namespace.

Sha256Namespace8FlaggedLeaf(namespacedData) results in: ns(rawData) || ns(rawData) || sha256(LeafPrefix || rawData), where rawData is the leaf's data minus the namespace.ID prefix (namely namespacedData[NamespaceLen:]).

Note that different from other cryptographic hash functions, this here makes assumptions on the input: len(namespacedData) >= DefaultNamespaceIDLen has to hold, as the first DefaultNamespaceIDLen bytes are interpreted as the namespace ID). If the input does not fulfil this, we will panic. The output will be of length 2*DefaultNamespaceIDLen+sha256.Size = 48 bytes.

Types

type Hasher 

type Hasher struct {
	hash.Hash
	NamespaceLen namespace.IDSize
	// contains filtered or unexported fields
}

func NewNmtHasher 

func NewNmtHasher(baseHasher hash.Hash, nidLen namespace.IDSize, ignoreMaxNamespace bool) *Hasher

func (*Hasher) EmptyRoot 

func (n *Hasher) EmptyRoot() []byte

func (*Hasher) HashLeaf 

func (n *Hasher) HashLeaf(leaf []byte) []byte

HashLeaf hashes leaves to: ns(rawData) || ns(rawData) || hash(leafPrefix || rawData), where raw data is the leaf's data minus the namespaceID (namely leaf[NamespaceLen:]). Hence, the input length has to be greater or equal to the size of the underlying namespace.ID.

Note that for leaves minNs = maxNs = ns(leaf) = leaf[:NamespaceLen].

func (*Hasher) HashNode 

func (n *Hasher) HashNode(l, r []byte) []byte

HashNode hashes inner nodes to: minNID || maxNID || hash(NodePrefix || left || right), where left and right are the full left and right child node bytes, including their respective min and max namespace IDs: left = left.Min() || left.Max() || l.Hash().

func (*Hasher) IsMaxNamespaceIDIgnored 

func (n *Hasher) IsMaxNamespaceIDIgnored() bool

func (*Hasher) NamespaceSize 

func (n *Hasher) NamespaceSize() namespace.IDSize

type NamespacedMerkleTree 

type NamespacedMerkleTree struct {
	// contains filtered or unexported fields
}
Example 
// the tree will use this namespace size
nidSize := 1
// the leaves that will be pushed
data := [][]byte{
	append(namespace.ID{0}, []byte("leaf_0")...),
	append(namespace.ID{0}, []byte("leaf_1")...),
	append(namespace.ID{1}, []byte("leaf_2")...),
	append(namespace.ID{1}, []byte("leaf_3")...),
}
// Init a tree with the namespace size as well as
// the underlying hash function:
tree := New(sha256.New(), NamespaceIDSize(nidSize))
for _, d := range data {
	if err := tree.Push(d); err != nil {
		panic(fmt.Sprintf("unexpected error: %v", err))
	}
}
// compute the root
root := tree.Root()
// the root's min/max namespace is the min and max namespace of all leaves:
minNS := MinNamespace(root, tree.NamespaceSize())
maxNS := MaxNamespace(root, tree.NamespaceSize())
if bytes.Equal(minNS, namespace.ID{0}) {
	fmt.Printf("Min namespace: %x\n", minNS)
}
if bytes.Equal(maxNS, namespace.ID{1}) {
	fmt.Printf("Max namespace: %x\n", maxNS)
}

// compute proof for namespace 0:
proof, err := tree.ProveNamespace(namespace.ID{0})
if err != nil {
	panic("unexpected error")
}

// verify proof using the root and the leaves of namespace 0:
leafs := [][]byte{
	append(namespace.ID{0}, []byte("leaf_0")...),
	append(namespace.ID{0}, []byte("leaf_1")...),
}

if proof.VerifyNamespace(sha256.New(), namespace.ID{0}, leafs, root) {
	fmt.Printf("Successfully verified namespace: %x\n", namespace.ID{0})
}

if proof.VerifyNamespace(sha256.New(), namespace.ID{2}, leafs, root) {
	panic(fmt.Sprintf("Proof for namespace %x, passed for namespace: %x\n", namespace.ID{0}, namespace.ID{2}))
}

Output:

Min namespace: 00
Max namespace: 01
Successfully verified namespace: 00

func New 

func New(h hash.Hash, setters ...Option) *NamespacedMerkleTree

New initializes a namespaced Merkle tree using the given base hash function and for the given namespace size (number of bytes). If the namespace size is 0 this corresponds to a regular non-namespaced Merkle tree.

func (*NamespacedMerkleTree) Get 

func (n *NamespacedMerkleTree) Get(nID namespace.ID) [][]byte

Get returns leaves for the given namespace.ID.

func (*NamespacedMerkleTree) GetWithProof 

func (n *NamespacedMerkleTree) GetWithProof(nID namespace.ID) ([][]byte, Proof, error)

GetWithProof is a convenience method returns leaves for the given namespace.ID together with the proof for that namespace. It returns the same result as calling the combination of Get(nid) and ProveNamespace(nid).

func (*NamespacedMerkleTree) NamespaceSize 

func (n *NamespacedMerkleTree) NamespaceSize() namespace.IDSize

NamespaceSize returns the underlying namespace size. Note that all namespaced data is expected to have the same namespace size.

func (*NamespacedMerkleTree) Prove 

func (n *NamespacedMerkleTree) Prove(index int) (Proof, error)

Prove leaf at index. Note this is not really NMT specific but the tree supports inclusions proofs like any vanilla Merkle tree.

func (*NamespacedMerkleTree) ProveNamespace 

func (n *NamespacedMerkleTree) ProveNamespace(nID namespace.ID) (Proof, error)

ProveNamespace returns a range proof for the given NamespaceID.

In case the underlying tree contains leaves with the given namespace their start and end index will be returned together with a range proof and the found leaves. In that case the returned leafHash will be nil.

If the tree does not have any entries with the given Namespace ID, but the namespace is within the range of the tree's min and max namespace, this will be proven by returning the (namespaced or rather flagged) hash of the leaf that is in the range instead of the namespace.

In the case (nID < minNID) or (maxNID < nID) we do not generate any proof and we return an empty range (0,0) to indicate that this namespace is not contained in the tree.

func (*NamespacedMerkleTree) ProveRange 

func (n *NamespacedMerkleTree) ProveRange(start, end int) (Proof, error)

ProveRange proves a leaf range [start, end].

func (*NamespacedMerkleTree) Push 

func (n *NamespacedMerkleTree) Push(namespacedData namespace.PrefixedData) error

Push adds data with the corresponding namespace ID to the tree. Returns an error if the namespace ID size of the input does not match the tree's NamespaceSize() or the leaves are not pushed in order (i.e. lexicographically sorted by namespace ID).

func (*NamespacedMerkleTree) Root 

func (n *NamespacedMerkleTree) Root() []byte

Root returns the namespaced Merkle Tree's root with the minimum and maximum namespace. min || max || hashDigest

type NodeVisitorFn 

type NodeVisitorFn = func(hash []byte, children ...[]byte)

type Option 

type Option func(*Options)

func IgnoreMaxNamespace 

func IgnoreMaxNamespace(ignore bool) Option

IgnoreMaxNamespace sets whether the largest possible namespace.ID MAX_NID should be 'ignored'. If set to true, this allows for shorter proofs in particular use-cases. E.g., see: https://github.com/celestiaorg/celestiaorg-specs/blob/master/specs/data_structures.md#namespace-merkle-tree Defaults to true.

func InitialCapacity 

func InitialCapacity(cap int) Option

InitialCapacity sets the capacity of the internally used slice(s) to the passed in initial value (defaults is 128).

func NamespaceIDSize 

func NamespaceIDSize(size int) Option

NamespaceIDSize sets the size of namespace IDs (in bytes) used by this tree. Defaults to 8 bytes.

func NodeVisitor 

func NodeVisitor(nodeVisitorFn NodeVisitorFn) Option

type Options 

type Options struct {
	InitialCapacity    int
	NamespaceIDSize    namespace.IDSize
	IgnoreMaxNamespace bool
	NodeVisitor        NodeVisitorFn
}

type Proof 

type Proof struct {
	// contains filtered or unexported fields
}

Proof represents proof of a namespace.ID in an NMT. In case this proof proves the absence of a namespace.ID in a tree it also contains the leaf hashes of the range where that namespace would be.

func NewAbsenceProof 

func NewAbsenceProof(proofStart, proofEnd int, proofNodes [][]byte, leafHash []byte, ignoreMaxNamespace bool) Proof

NewAbsenceProof constructs a proof that proves that a namespace.ID falls within the range of an NMT but no leaf with that namespace.ID is included.

func NewEmptyRangeProof 

func NewEmptyRangeProof(ignoreMaxNamespace bool) Proof

NewEmptyRangeProof constructs a proof that proves that a namespace.ID does not fall within the range of an NMT.

func NewInclusionProof 

func NewInclusionProof(proofStart, proofEnd int, proofNodes [][]byte, ignoreMaxNamespace bool) Proof

NewInclusionProof constructs a proof that proves that a namespace.ID is included in an NMT.

func (Proof) End 

func (proof Proof) End() int

End index of this proof.

func (Proof) IsMaxNamespaceIDIgnored 

func (proof Proof) IsMaxNamespaceIDIgnored() bool

func (Proof) IsNonEmptyRange 

func (proof Proof) IsNonEmptyRange() bool

IsNonEmptyRange returns if this proof contains a valid, non-empty proof range.

func (Proof) IsOfAbsence 

func (proof Proof) IsOfAbsence() bool

IsOfAbsence returns true if this proof proves the absence of leaves of a namespace in the tree.

func (Proof) LeafHash 

func (proof Proof) LeafHash() []byte

LeafHash returns nil if the namespace has leaves in the NMT. In case the namespace.ID to be proved is in the min/max range of the tree but absent, this will contain the leaf hash necessary to verify the proof of absence.

func (Proof) Nodes 

func (proof Proof) Nodes() [][]byte

Nodes return the proof nodes that together with the corresponding leaf values can be used to recompute the root and verify this proof.

func (Proof) Start 

func (proof Proof) Start() int

Start index of this proof.

func (Proof) VerifyInclusion 

func (proof Proof) VerifyInclusion(h hash.Hash, nid namespace.ID, leaves [][]byte, root []byte) bool

VerifyInclusion checks that the inclusion proof is valid by using leaf data and the provided proof to regenerate and compare the root. Note that the leaf data should not contain the prefixed namespace, unlike the tree.Push method, which takes prefixed data. All leaves implicitly have the same namespace ID: `nid`.

func (Proof) VerifyNamespace 

func (proof Proof) VerifyNamespace(h hash.Hash, nID namespace.ID, data [][]byte, root []byte) bool

VerifyNamespace verifies a whole namespace, i.e. it verifies inclusion of the provided data in the tree. Additionally, it verifies that the namespace is complete and no leaf of that namespace was left out in the proof.

Source Files

View all Source files

Directories

Path Synopsis
Package namespace contains the core namespaced data types.
 Package namespace contains the core namespaced data types.

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.