nmt

package module
v0.23.0 Latest Latest
Warning

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

 Go to latest Published: Jan 20, 2025 License: Apache-2.0 Imports: 8 Imported by: 36

README

Namespaced Merkle Tree (NMT)

Go Reference golangci-lint Go

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 (number of bytes)
    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, err := tree.Root()
    if err != nil {
      panic(fmt.Sprintf("unexpected error: %v", err))
    }
    // 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 was heavily inspired by the initial implementation in celestiaorg/lazyledger-prototype.

Non-endorsed implementations of NMT exist in other languages:

Language Repo
Rust Sovereign-Labs/nmt-rs

Contributing

Markdown files must conform to GitHub Flavored Markdown. Markdown must be formatted with:

Audits

Date Auditor Report
2023/8/18 Informal Systems informal-systems.pdf

Documentation

Overview

Package nmt contains an NMT implementation. The specifications can be found in https://github.com/celestiaorg/nmt/blob/main/docs/spec/nmt.md.

Index

Constants

View Source 
const (
	LeafPrefix = 0
	NodePrefix = 1
)
View Source 
const (
	DefaultNamespaceIDLen = 8
	DefaultCapacity       = 128
)

Variables

View Source 
var (
	ErrUnorderedSiblings         = errors.New("NMT sibling nodes should be ordered lexicographically by namespace IDs")
	ErrInvalidNodeLen            = errors.New("invalid NMT node size")
	ErrInvalidLeafLen            = errors.New("invalid NMT leaf size")
	ErrInvalidNodeNamespaceOrder = errors.New("invalid NMT node namespace order")
)
View Source 
var (
	ErrInvalidRange     = errors.New("invalid proof range")
	ErrInvalidPushOrder = errors.New("pushed data has to be lexicographically ordered by namespace IDs")
)
View Source 
var (
	// ErrFailedCompletenessCheck indicates that the verification of a namespace proof failed due to the lack of completeness property.
	ErrFailedCompletenessCheck = errors.New("failed completeness check")
	ErrWrongLeafHashesSize     = errors.New("wrong leafHashes size")
)

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 extracts the maximum namespace ID from a given namespace hash, which is formatted as: minimum namespace ID || maximum namespace ID || hash digest.

func MinNamespace 

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

MinNamespace extracts the minimum namespace ID from a given namespace hash, which is formatted as: minimum namespace ID || maximum namespace ID || hash digest.

Types

type Hasher 

type Hasher interface {
	IsMaxNamespaceIDIgnored() bool
	NamespaceSize() namespace.IDSize
	HashLeaf(data []byte) ([]byte, error)
	HashNode(leftChild, rightChild []byte) ([]byte, error)
	EmptyRoot() []byte
}

Hasher describes the interface nmts use to hash leafs and nodes.

Note: it is not advised to create alternative hashers if following the specification is desired. The main reason this exists is to not follow the specification for testing purposes.

type LeafRange added in v0.22.0 

type LeafRange struct {
	// Start and End denote the indices of a leaf in the tree.
	// Start ranges from 0 up to the total number of leaves minus 1.
	// End ranges from 1 up to the total number of leaves.
	// End is non-inclusive
	Start, End int
}

func ToLeafRanges added in v0.22.0 

func ToLeafRanges(proofStart, proofEnd, subtreeWidth int) ([]LeafRange, error)

ToLeafRanges returns the leaf ranges corresponding to the provided subtree roots. The proof range defined by proofStart and proofEnd is end exclusive. It uses the subtree root width to calculate the maximum number of leaves a subtree root can commit to. The subtree root width is defined as per ADR-013: https://github.com/celestiaorg/celestia-app/blob/main/docs/architecture/adr-013-non-interactive-default-rules-for-zero-padding.md This method assumes: - The subtree roots are created according to the ADR-013 non-interactive defaults rules - The tree's number of leaves is a power of two The algorithm is as follows: - Let `d` be `y - x` (the range of the proof). - `i` is the index of the next subtree root. - While `d != 0`:

  • Let `z` be the largest power of 2 that fits in `d`; here we are finding the range for the next subtree root.
  • The range for the next subtree root is `[x, x + z)`, i.e., `S_i` is the subtree root of leaves at indices `[x, x + z)`.
  • `d = d - z` (move past the first subtree root and its range).
  • `i = i + 1`.
  • Go back to the loop condition.

Note: This method is Celestia specific.

type NamespacedMerkleTree 

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

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) ComputeSubtreeRoot added in v0.22.0 

func (n *NamespacedMerkleTree) ComputeSubtreeRoot(start, end int) ([]byte, error)

ComputeSubtreeRoot takes a leaf range and returns the corresponding subtree root. Also, it requires the start and end range to correctly reference an inner node. The provided range, defined by start and end, is end-exclusive.

func (*NamespacedMerkleTree) ForceAddLeaf added in v0.17.0 

func (n *NamespacedMerkleTree) ForceAddLeaf(leaf namespace.PrefixedData) error

ForceAddLeaf adds a namespaced data to the tree without validating its namespace ID. This method should only be used by tests that are attempting to create out of order trees. The default hasher will fail for trees that are out of order.

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) MaxNamespace added in v0.15.0 

func (n *NamespacedMerkleTree) MaxNamespace() (namespace.ID, error)

MaxNamespace returns the maximum namespace ID in this Namespaced Merkle Tree. Any errors returned by this method are irrecoverable and indicate an illegal state of the tree (n).

func (*NamespacedMerkleTree) MinNamespace added in v0.15.0 

func (n *NamespacedMerkleTree) MinNamespace() (namespace.ID, error)

MinNamespace returns the minimum namespace ID in this Namespaced Merkle Tree. Any errors returned by this method are irrecoverable and indicate an illegal state of the tree (n).

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 returns a NMT inclusion proof for the leaf at the supplied index. Note this is not really NMT specific but the tree supports inclusions proofs like any vanilla Merkle tree. Prove is a thin wrapper around the ProveRange. If the supplied index is invalid i.e., if index < 0 or index > n.Size(), then Prove returns an ErrInvalidRange error. Any other errors rather than this are irrecoverable and indicate an illegal state of the tree (n).

func (*NamespacedMerkleTree) ProveNamespace 

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

ProveNamespace returns a range proof for the given NamespaceID.

case 1) If the namespace nID is out of the range of the tree's min and max namespace i.e., (nID < n.minNID) or (n.maxNID < nID) ProveNamespace returns an empty Proof with empty nodes and the range (0,0) i.e., Proof.start = 0 and Proof.end = 0 to indicate that this namespace is not contained in the tree.

case 2) If the namespace nID is within the range of the tree's min and max namespace i.e., n.minNID<= n.ID <=n.maxNID and the tree does not have any entries with the given Namespace ID nID, this will be proven by returning the inclusion/range Proof of the (namespaced or rather flagged) hash of the leaf of the tree 1) with the smallest namespace ID that is larger than nID and 2) the namespace ID of the leaf to the left of it is smaller than the nid. The nodes field of the returned Proof structure is populated with the Merkle inclusion proof. the leafHash field of the returned Proof will contain the namespaced hash of such leaf. The start and end fields of the Proof are set to the indices of the identified leaf. The start field is set to the index of the leaf, and the end field is set to the index of the leaf + 1.

case 3) In case the underlying tree contains leaves with the given namespace their start and end (end is non-inclusive) index will be returned together with a range proof for [start, end). In that case the leafHash field of the returned Proof will be nil.

The isMaxNamespaceIDIgnored field of the Proof reflects the ignoreMaxNs field of n.treeHasher. When set to true, this indicates that the proof was generated using a modified version of the namespace hash with a custom namespace ID range calculation. For more information on this, please refer to the HashNode method in the Hasher. Any error returned by this method is irrecoverable and indicates an illegal state of the tree (n).

func (*NamespacedMerkleTree) ProveRange 

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

ProveRange returns a Merkle inclusion proof for a specified range of leaves, from start to end exclusive. The returned Proof structure contains the nodes field, which holds the necessary tree nodes for the Merkle range proof in an in-order traversal order. These nodes include the namespaced hash of the left siblings for the proof of the leaf at index start, and the namespaced hash of the right siblings for the proof of the leaf at index end.

If the specified range [start, end) exceeds the current range of leaves in the tree, ProveRange returns an error together with an empty Proof with empty nodes and start and end fields set to 0.

The isMaxNamespaceIDIgnored field of the Proof reflects the ignoreMaxNs field of n.treeHasher. When set to true, this indicates that the proof was generated using a modified version of the namespace hash with a custom namespace ID range calculation. For more information on this, please refer to the HashNode method in the Hasher. If the supplied (start, end) range is invalid i.e., if start < 0 or end > n.Size() or start >= end, then ProveRange returns an ErrInvalidRange error. Any errors rather than ErrInvalidRange are irrecoverable and indicate an illegal state of the tree (n).

func (*NamespacedMerkleTree) Push 

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

Push adds a namespaced data to the tree. The first `n.NamespaceSize()` bytes of namespacedData is treated as its namespace ID. Push returns an error if the namespaced data is not namespace-prefixed (i.e., its size is smaller than the tree's NamespaceSize), or if it is not pushed in ascending order based on the namespace ID compared to the previously inserted data (i.e., it is not lexicographically sorted by namespace ID).

func (*NamespacedMerkleTree) Root 

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

Root calculates the namespaced Merkle Tree's root based on the data that has been added through the use of the Push method. the returned byte slice is of size 2* n.NamespaceSize + the underlying hash output size, and should be parsed as minND || maxNID || hash Any error returned by this method is irrecoverable and indicate an illegal state of the tree (n).

func (*NamespacedMerkleTree) Size added in v0.16.0 

func (n *NamespacedMerkleTree) Size() int

Size returns the number of leaves in the tree.

type NmtHasher added in v0.17.0 

type NmtHasher struct {
	NamespaceLen namespace.IDSize
	// contains filtered or unexported fields
}

NmtHasher is the default hasher. It follows the description of the original hashing function described in the LazyLedger white paper.

func NewNmtHasher 

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

func (*NmtHasher) BlockSize added in v0.17.0 

func (n *NmtHasher) BlockSize() int

BlockSize returns the hash's underlying block size.

func (*NmtHasher) EmptyRoot added in v0.17.0 

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

func (*NmtHasher) HashLeaf added in v0.17.0 

func (n *NmtHasher) HashLeaf(ndata []byte) ([]byte, error)

HashLeaf computes namespace hash of the namespaced data item `ndata` as ns(ndata) || ns(ndata) || hash(leafPrefix || ndata), where ns(ndata) is the namespaceID inside the data item namely leaf[:n.NamespaceLen]). Note that for leaves minNs = maxNs = ns(leaf) = leaf[:NamespaceLen]. HashLeaf can return the ErrInvalidNodeLen error if the input is not namespaced.

func (*NmtHasher) HashNode added in v0.17.0 

func (n *NmtHasher) HashNode(left, right []byte) ([]byte, error)

HashNode calculates a namespaced hash of a node using the supplied left and right children. The input values, `left` and `right,` are namespaced hash values with the format `minNID || maxNID || hash.` The HashNode function returns an error if the provided inputs are invalid. Specifically, it returns the ErrInvalidNodeLen error if the left and right inputs are not in the namespaced hash format, and the ErrUnorderedSiblings error if left.maxNID is greater than right.minNID. By default, the normal namespace hash calculation is followed, which is `res = min(left.minNID, right.minNID) || max(left.maxNID, right.maxNID) || H(NodePrefix, left, right)`. `res` refers to the return value of the HashNode. However, if the `ignoreMaxNs` property of the Hasher is set to true, the calculation of the namespace ID range of the node slightly changes. Let MAXNID be the maximum possible namespace ID value i.e., 2^NamespaceIDSize-1. If the namespace range of the right child is start=end=MAXNID, indicating that it represents the root of a subtree whose leaves all have the namespace ID of `MAXNID`, then exclude the right child from the namespace range calculation. Instead, assign the namespace range of the left child as the parent's namespace range.

func (*NmtHasher) IsMaxNamespaceIDIgnored added in v0.17.0 

func (n *NmtHasher) IsMaxNamespaceIDIgnored() bool

func (*NmtHasher) MustHashLeaf added in v0.17.0 

func (n *NmtHasher) MustHashLeaf(ndata []byte) []byte

MustHashLeaf is a wrapper around HashLeaf that panics if an error is encountered. The ndata must be a valid leaf node.

func (*NmtHasher) NamespaceSize added in v0.17.0 

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

func (*NmtHasher) Reset added in v0.17.0 

func (n *NmtHasher) Reset()

Reset resets the Hash to its initial state.

func (*NmtHasher) Size added in v0.17.0 

func (n *NmtHasher) Size() int

Size returns the number of bytes Sum will return.

func (*NmtHasher) Sum added in v0.17.0 

func (n *NmtHasher) Sum([]byte) []byte

Sum computes the hash. Does not append the given suffix, violating the interface. It may panic if the data being hashed is invalid. This should never happen since the Write method refuses an invalid data and errors out.

func (*NmtHasher) ValidateLeaf added in v0.17.0 

func (n *NmtHasher) ValidateLeaf(data []byte) (err error)

ValidateLeaf verifies if data is namespaced and returns an error if not.

func (*NmtHasher) ValidateNodeFormat added in v0.17.0 

func (n *NmtHasher) ValidateNodeFormat(node []byte) error

ValidateNodeFormat checks whether the supplied node conforms to the namespaced hash format and returns an error if not.

func (*NmtHasher) ValidateNodes added in v0.17.0 

func (n *NmtHasher) ValidateNodes(left, right []byte) error

ValidateNodes is a helper function to verify the validity of the inputs of HashNode. It verifies whether left and right comply by the namespace hash format, and are correctly ordered according to their namespace IDs.

func (*NmtHasher) Write added in v0.17.0 

func (n *NmtHasher) Write(data []byte) (int, error)

Write writes the namespaced data to be hashed.

Requires data of fixed size to match leaf or inner NMT nodes. Only a single write is allowed. It panics if more than one single write is attempted. If the data does not match the format of an NMT non-leaf node or leaf node, an error will be returned.

type NodeVisitorFn 

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

type Option 

type Option func(*Options)

func CustomHasher added in v0.17.0 

func CustomHasher(h Hasher) Option

CustomHasher replaces the default hasher.

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/main/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 indicates the initial number of leaves in the tree
	InitialCapacity int
	// NamespaceIDSize is the size of a namespace ID in bytes
	NamespaceIDSize namespace.IDSize
	// The "IgnoreMaxNamespace" flag influences the calculation of the namespace
	// ID range for intermediate nodes in the tree. This flag signals that, when
	// determining the upper limit of the namespace ID range for a tree node,
	// the maximum possible namespace ID (equivalent to "NamespaceIDSize" bytes
	// of 0xFF, or 2^NamespaceIDSize-1) should be omitted if feasible. For a
	// more in-depth understanding of this field, refer to the "HashNode" method
	// in the "Hasher.
	IgnoreMaxNamespace bool
	NodeVisitor        NodeVisitorFn
	Hasher             Hasher
}

type Proof 

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

Proof represents a namespace 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 ProtoToProof added in v0.18.0 

func ProtoToProof(protoProof pb.Proof) Proof

ProtoToProof creates a proof from its proto representation.

func (Proof) End 

func (proof Proof) End() int

End index of this proof, non-inclusive.

func (Proof) IsEmptyProof added in v0.16.0 

func (proof Proof) IsEmptyProof() bool

IsEmptyProof checks whether the proof corresponds to an empty proof as defined in NMT specifications https://github.com/celestiaorg/nmt/blob/main/docs/spec/nmt.md.

func (Proof) IsMaxNamespaceIDIgnored 

func (proof Proof) IsMaxNamespaceIDIgnored() bool

IsMaxNamespaceIDIgnored returns true if the proof has been created under the ignore max namespace logic. see ./docs/nmt-lib.md for more details.

func (Proof) IsNonEmptyRange 

func (proof Proof) IsNonEmptyRange() bool

IsNonEmptyRange returns true 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) MarshalJSON added in v0.17.0 

func (proof Proof) MarshalJSON() ([]byte, error)

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) UnmarshalJSON added in v0.17.0 

func (proof *Proof) UnmarshalJSON(data []byte) error

func (Proof) VerifyInclusion 

func (proof Proof) VerifyInclusion(h hash.Hash, nid namespace.ID, leavesWithoutNamespace [][]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 leavesWithoutNamespace 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`. The size of the leavesWithoutNamespace should be equal to the proof range i.e., end-start. VerifyInclusion does not verify the completeness of the proof, so it's possible for leavesWithoutNamespace to be a subset of the leaves in the tree that have the namespace ID nid.

func (Proof) VerifyLeafHashes added in v0.16.0 

func (proof Proof) VerifyLeafHashes(nth *NmtHasher, verifyCompleteness bool, nID namespace.ID, leafHashes [][]byte, root []byte) (bool, error)

The VerifyLeafHashes function checks whether the given proof is a valid Merkle range proof for the leaves in the leafHashes input. It returns true or false accordingly. If there is an issue during the proof verification e.g., a node does not conform to the namespace hash format, then a proper error is returned to indicate the root cause of the issue. The leafHashes parameter is a list of leaf hashes, where each leaf hash is represented by a byte slice. The size of leafHashes should match the proof range i.e., end-start. If the verifyCompleteness parameter is set to true, the function also checks the completeness of the proof by verifying that there is no leaf in the tree represented by the root parameter that matches the namespace ID nID outside the leafHashes list.

func (Proof) VerifyNamespace 

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

VerifyNamespace verifies a whole namespace, i.e. 1) it verifies inclusion of the provided `leaves` in the tree (or the proof.leafHash in case of full/short absence proof) 2) it verifies that the namespace is complete i.e., the data items matching the namespace `nID` are within the range [`proof.start`, `proof.end`) and no data of that namespace was left out. VerifyNamespace deems an empty `proof` valid if the queried `nID` falls outside the namespace range of the supplied `root` or if the `root` is empty

`h` MUST be the same as the underlying hash function used to generate the proof. Otherwise, the verification will fail. `nID` is the namespace ID for which the namespace `proof` is generated. `leaves` contains the namespaced leaves of the tree in the range of [`proof.start`, `proof.end`). For an absence `proof`, the `leaves` is empty. `leaves` items MUST be ordered according to their index in the tree, with `leaves[0]` corresponding to the namespaced leaf at index `start`, and the last element in `leaves` corresponding to the leaf at index `end-1` of the tree.

`root` is the root of the NMT against which the `proof` is verified.

func (Proof) VerifySubtreeRootInclusion added in v0.22.0 

func (proof Proof) VerifySubtreeRootInclusion(nth *NmtHasher, subtreeRoots [][]byte, subtreeWidth int, root []byte) (bool, error)

VerifySubtreeRootInclusion verifies that a set of subtree roots is included in an NMT. Warning: This method is Celestia specific! Using it without verifying the following assumptions, can return unexpected errors, false positive/negatives: - The subtree roots are created according to the ADR-013 https://github.com/celestiaorg/celestia-app/blob/main/docs/architecture/adr-013-non-interactive-default-rules-for-zero-padding.md - The tree's number of leaves is a power of two The subtreeWidth is also defined in ADR-013. More information on the algorithm used can be found in the ToLeafRanges() method docs.

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.