smt

package module
v1.0.0 Latest Latest
Warning

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

 Go to latest Published: Jul 12, 2024 License: MIT Imports: 8 Imported by: 10

README

smt

Tag GoDoc Go Version Go Report Card Tests codecov

NOTE: Requires Go 1.20.12+

Overview

This is a Go library that implements a Sparse Merkle Trie for a key-value map. The trie implements the same optimisations specified in the Libra whitepaper, to reduce the number of hash operations required per trie operation to $O(k)$ where $k$ is the number of non-empty elements in the trie. And is implemented in a similar way to the JMT whitepaper, with additional features and proof mechanics.

Documentation

Documentation for the different aspects of this library, the trie, proofs and all its different components can be found in the docs directory.

Tests

To run all tests (excluding benchmarks) run the following command:

make test_all

To test the badger submodule that provides a more fully featured key-value store, run the following command:

make test_badger

Benchmarks

To run the full suite of benchmarks simply run the following command:

make benchmark_all

To view pre-ran results of the entire benchmarking suite see benchmarks

Release Tags

You can tag and publish a new release by following the instructions bellow.

Tagging a new release

For a bug fix:

make tag_bug_fix

For a minor release run:

make tag_minor_release
Push and Release

Then, push the tag to the repository:

git push origin v<release>

Create a release on GitHub with the tag and the release notes here.

Documentation

Overview

Unlike the JMT, it only supports binary trees and does not implemented the same RocksDB optimizations as specified in the original JMT library when optimizing for disk iops

This package implements additional SMT specific functionality related to tree sums and closest proof mechanics.

Index

Constants

View Source 
const (
	// These are intentionally exposed to allow for for testing and custom
	// implementations of downstream applications.
	SmtRootSizeBytes  = 32
	SmstRootSizeBytes = SmtRootSizeBytes + sumSizeBytes + countSizeBytes
)

Variables

View Source 
var (
	// ErrBadProof is returned when an invalid Merkle proof is supplied.
	ErrBadProof = errors.New("bad proof")
	// ErrKeyNotFound is returned when a key is not found in the tree.
	ErrKeyNotFound = errors.New("key not found")
	// ErrInvalidClosestPath is returned when the path used in the ClosestProof
	// method does not match the size of the trie's PathHasher
	ErrInvalidClosestPath = errors.New("invalid path does not match path hasher size")
)

Functions

func NewTrieHasher added in v0.11.0 

func NewTrieHasher(hasher hash.Hash) *trieHasher

NewTrieHasher returns a new trie hasher with the given hash function.

func VerifyClosestProof added in v0.7.1 

func VerifyClosestProof(proof *SparseMerkleClosestProof, root []byte, spec *TrieSpec) (bool, error)

VerifyClosestProof verifies a Merkle proof for a proof of inclusion for a leaf found to have the closest path to the one provided to the proof structure

func VerifyCompactClosestProof added in v0.7.1 

func VerifyCompactClosestProof(proof *SparseCompactMerkleClosestProof, root []byte, spec *TrieSpec) (bool, error)

VerifyCompactClosestProof is similar to VerifyClosestProof but for a compacted merkle proof

func VerifyCompactProof 

func VerifyCompactProof(proof *SparseCompactMerkleProof, root []byte, key, value []byte, spec *TrieSpec) (bool, error)

VerifyCompactProof is similar to VerifyProof but for a compacted Merkle proof.

func VerifyCompactSumProof added in v0.6.0 

func VerifyCompactSumProof(
	proof *SparseCompactMerkleProof,
	root []byte,
	key, value []byte,
	sum, count uint64,
	spec *TrieSpec,
) (bool, error)

VerifyCompactSumProof is similar to VerifySumProof but for a compacted Merkle proof.

func VerifyProof 

func VerifyProof(proof *SparseMerkleProof, root, key, value []byte, spec *TrieSpec) (bool, error)

VerifyProof verifies a Merkle proof.

func VerifySumProof added in v0.6.0 

func VerifySumProof(proof *SparseMerkleProof, root, key, value []byte, sum, count uint64, spec *TrieSpec) (bool, error)

VerifySumProof verifies a Merkle proof for a sum trie.

Types

type MerkleRoot added in v0.9.0 

type MerkleRoot []byte

MerkleRoot is a type alias for a byte slice returned from the Root method

func (MerkleRoot) Count added in v0.11.1 

func (r MerkleRoot) Count() uint64

Count returns the uint64 count of the merkle root, a cryptographically secure count of the number of non-empty leafs in the tree.

func (MerkleRoot) MustSum added in v1.0.0 

func (r MerkleRoot) MustSum() uint64

MustSum returns the uint64 sum of the merkle root, it checks the length of the merkle root and if it is no the same as the size of the SMST's expected root hash it will panic.

func (MerkleRoot) Sum added in v0.9.0 

func (r MerkleRoot) Sum() (uint64, error)

Sum returns the uint64 sum of the merkle root, it checks the length of the merkle root and if it is no the same as the size of the SMST's expected root hash it will return an error.

type PathHasher added in v0.5.0 

type PathHasher interface {
	// Path hashes a key (preimage) and returns a trie path (digest).
	Path([]byte) []byte
	// PathSize returns the length (in bytes) of digests produced by this hasher.
	PathSize() int
}

PathHasher defines how key inputs are hashed to produce trie paths.

type SMST added in v0.6.0 

type SMST struct {
	TrieSpec
	*SMT
}

SMST is an object wrapping a Sparse Merkle Trie for custom encoding

func ImportSparseMerkleSumTrie added in v0.8.0 

func ImportSparseMerkleSumTrie(
	nodes kvstore.MapStore,
	hasher hash.Hash,
	root []byte,
	options ...TrieSpecOption,
) *SMST

ImportSparseMerkleSumTrie returns a pointer to an SMST struct with the root hash provided

func NewSparseMerkleSumTrie added in v0.8.0 

func NewSparseMerkleSumTrie(
	nodes kvstore.MapStore,
	hasher hash.Hash,
	options ...TrieSpecOption,
) *SMST

NewSparseMerkleSumTrie returns a pointer to an SMST struct

func (*SMST) Commit added in v0.6.0 

func (smst *SMST) Commit() error

Commit persists all dirty nodes in the trie, deletes all orphaned nodes from the database and then computes and saves the root hash

func (*SMST) Count added in v0.11.0 

func (smst *SMST) Count() uint64

Count returns the number of non-empty nodes in the entire trie stored in the root.

func (*SMST) Delete added in v0.6.0 

func (smst *SMST) Delete(key []byte) error

Delete removes the node at the path corresponding to the given key

func (*SMST) Get added in v0.6.0 

func (smst *SMST) Get(key []byte) (valueDigest []byte, weight uint64, err error)

Get retrieves the value digest for the given key, along with its weight assuming the node exists, otherwise the default placeholder values are returned

func (*SMST) Prove added in v0.6.0 

func (smst *SMST) Prove(key []byte) (*SparseMerkleProof, error)

Prove generates a SparseMerkleProof for the given key

func (*SMST) ProveClosest added in v0.7.0 

func (smst *SMST) ProveClosest(path []byte) (
	proof *SparseMerkleClosestProof,
	err error,
)

ProveClosest generates a SparseMerkleProof of inclusion for the key with the most common bits as the path provided

func (*SMST) Root added in v0.6.0 

func (smst *SMST) Root() MerkleRoot

Root returns the root hash of the trie with the total sum bytes appended

func (*SMST) Spec added in v0.6.0 

func (smst *SMST) Spec() *TrieSpec

Spec returns the SMST TrieSpec

func (*SMST) Sum added in v0.6.0 

func (smst *SMST) Sum() uint64

Sum returns the sum of the entire trie stored in the root. If the tree is not a sum tree, it will panic.

func (*SMST) Update added in v0.6.0 

func (smst *SMST) Update(key, value []byte, weight uint64) error

The weight is used to compute the interim sum of the node which then percolates up to the total sum of the trie.

type SMT added in v0.5.0 

type SMT struct {
	TrieSpec
	// contains filtered or unexported fields
}

SMT is a Sparse Merkle Trie object that implements the SparseMerkleTrie interface

func ImportSparseMerkleTrie added in v0.8.0 

func ImportSparseMerkleTrie(
	nodes kvstore.MapStore,
	hasher hash.Hash,
	root []byte,
	options ...TrieSpecOption,
) *SMT

ImportSparseMerkleTrie returns a pointer to an SMT struct with the provided root hash

func NewSparseMerkleTrie added in v0.8.0 

func NewSparseMerkleTrie(
	nodes kvstore.MapStore,
	hasher hash.Hash,
	options ...TrieSpecOption,
) *SMT

NewSparseMerkleTrie returns a new pointer to an SMT struct, and applies any options provided

func (*SMT) Commit added in v0.5.0 

func (smt *SMT) Commit() (err error)

Commit persists all dirty nodes in the trie, deletes all orphaned nodes from the database and then computes and saves the root hash

func (*SMT) Delete added in v0.5.0 

func (smt *SMT) Delete(key []byte) error

Delete removes the node at the path corresponding to the given key

func (*SMT) Get added in v0.5.0 

func (smt *SMT) Get(key []byte) ([]byte, error)

Get returns the hash (i.e. digest) of the leaf value stored at the given key

func (*SMT) Prove added in v0.5.0 

func (smt *SMT) Prove(key []byte) (proof *SparseMerkleProof, err error)

Prove generates a SparseMerkleProof for the given key

func (*SMT) ProveClosest added in v0.7.0 

func (smt *SMT) ProveClosest(path []byte) (
	proof *SparseMerkleClosestProof,
	err error,
)

ProveClosest generates a SparseMerkleProof of inclusion for the first key with the most common bits as the path provided.

This method will follow the path provided until it hits a leaf node and then exit. If the leaf is along the path it will produce an inclusion proof for the key (and return the key-value internal pair) as they share a common prefix. If however, during the trie traversal according to the path, a nil node is encountered, the traversal backsteps and flips the path bit for that depth (ie tries left if it tried right and vice versa). This guarantees that a proof of inclusion is found that has the most common bits with the path provided, biased to the longest common prefix.

func (*SMT) Root added in v0.5.0 

func (smt *SMT) Root() MerkleRoot

Root returns the root hash of the trie

func (*SMT) Update added in v0.5.0 

func (smt *SMT) Update(key, value []byte) error

Update inserts the `value` for the given `key` into the SMT

type SparseCompactMerkleClosestProof added in v0.7.1 

type SparseCompactMerkleClosestProof struct {
	Path             []byte                    // the path provided to the ProveClosest method
	FlippedBits      [][]byte                  // the index of the bits flipped in the path during trie traversal
	Depth            []byte                    // the depth of the trie when trie traversal stopped
	ClosestPath      []byte                    // the path of the leaf closest to the path provided
	ClosestValueHash []byte                    // the value hash of the leaf closest to the path provided
	ClosestProof     *SparseCompactMerkleProof // the proof of the leaf closest to the path provided
}

SparseCompactMerkleClosestProof is a compressed representation of the SparseMerkleClosestProof

func CompactClosestProof added in v0.7.1 

func CompactClosestProof(proof *SparseMerkleClosestProof, spec *TrieSpec) (*SparseCompactMerkleClosestProof, error)

CompactClosestProof compacts a proof, to reduce its size.

func (*SparseCompactMerkleClosestProof) Marshal added in v0.7.1 

func (proof *SparseCompactMerkleClosestProof) Marshal() ([]byte, error)

Marshal serialises the SparseCompactMerkleClosestProof to bytes

func (*SparseCompactMerkleClosestProof) Unmarshal added in v0.7.1 

func (proof *SparseCompactMerkleClosestProof) Unmarshal(bz []byte) error

Unmarshal deserialises the SparseCompactMerkleClosestProof from bytes

type SparseCompactMerkleProof 

type SparseCompactMerkleProof struct {
	// SideNodes is an array of the sibling nodes leading up to the leaf of the proof.
	SideNodes [][]byte

	// NonMembershipLeafData is the data of the unrelated leaf at the position
	// of the key being proven, in the case of a non-membership proof. For
	// membership proofs, is nil.
	NonMembershipLeafData []byte

	// BitMask, in the case of a compact proof, is a bit mask of the sidenodes
	// of the proof where an on-bit indicates that the sidenode at the bit's
	// index is a placeholder. This is only set if the proof is compact.
	BitMask []byte

	// NumSideNodes, in the case of a compact proof, indicates the number of
	// sidenodes in the proof when decompacted. This is only set if the proof is compact.
	NumSideNodes int

	// SiblingData is the data of the sibling node to the leaf being proven,
	// required for updatable proofs. For unupdatable proofs, is nil.
	SiblingData []byte
}

SparseCompactMerkleProof is a compact Merkle proof for an element in a SparseMerkleTrie.

func CompactProof 

func CompactProof(proof *SparseMerkleProof, spec *TrieSpec) (*SparseCompactMerkleProof, error)

CompactProof compacts a proof, to reduce its size.

func (*SparseCompactMerkleProof) Marshal added in v0.7.0 

func (proof *SparseCompactMerkleProof) Marshal() ([]byte, error)

Marshal serialises the SparseCompactMerkleProof to bytes

func (*SparseCompactMerkleProof) Unmarshal added in v0.7.0 

func (proof *SparseCompactMerkleProof) Unmarshal(bz []byte) error

Unmarshal deserialises the SparseCompactMerkleProof from bytes

type SparseMerkleClosestProof added in v0.7.1 

type SparseMerkleClosestProof struct {
	Path             []byte             // the path provided to the ProveClosest method
	FlippedBits      []int              // the index of the bits flipped in the path during trie traversal
	Depth            int                // the depth of the trie when trie traversal stopped
	ClosestPath      []byte             // the path of the leaf closest to the path provided
	ClosestValueHash []byte             // the valueHash of the leaf (or its value if the hasher is nil) from the closest proof
	ClosestProof     *SparseMerkleProof // the proof of the leaf closest to the path provided
}

SparseMerkleClosestProof is a wrapper around a SparseMerkleProof that represents the proof of the leaf with the closest path to the one provided.

func DecompactClosestProof added in v0.7.1 

func DecompactClosestProof(proof *SparseCompactMerkleClosestProof, spec *TrieSpec) (*SparseMerkleClosestProof, error)

DecompactClosestProof decompacts a proof, so that it can be used for VerifyClosestProof.

func (*SparseMerkleClosestProof) GetValueHash added in v0.10.0 

func (proof *SparseMerkleClosestProof) GetValueHash(spec *TrieSpec) []byte

GetValueHash returns the value hash of the closest proof.

func (*SparseMerkleClosestProof) Marshal added in v0.7.1 

func (proof *SparseMerkleClosestProof) Marshal() ([]byte, error)

Marshal serialises the SparseMerkleClosestProof to bytes

func (*SparseMerkleClosestProof) Unmarshal added in v0.7.1 

func (proof *SparseMerkleClosestProof) Unmarshal(bz []byte) error

Unmarshal deserialises the SparseMerkleClosestProof from bytes

type SparseMerkleProof 

type SparseMerkleProof struct {
	// SideNodes is an array of the sibling nodes leading up to the leaf of the proof.
	SideNodes [][]byte

	// NonMembershipLeafData is the data of the unrelated leaf at the position
	// of the key being proven, in the case of a non-membership proof. For
	// membership proofs, is nil.
	NonMembershipLeafData []byte

	// SiblingData is the data of the sibling node to the leaf being proven,
	// required for updatable proofs. For unupdatable proofs, is nil.
	SiblingData []byte
}

SparseMerkleProof is a Merkle proof for an element in a SparseMerkleTrie. TODO: Look into whether the SiblingData is required and remove it if not

func DecompactProof 

func DecompactProof(proof *SparseCompactMerkleProof, spec *TrieSpec) (*SparseMerkleProof, error)

DecompactProof decompacts a proof, so that it can be used for VerifyProof.

func (*SparseMerkleProof) Marshal added in v0.7.0 

func (proof *SparseMerkleProof) Marshal() ([]byte, error)

Marshal serialises the SparseMerkleProof to bytes

func (*SparseMerkleProof) Unmarshal added in v0.7.0 

func (proof *SparseMerkleProof) Unmarshal(bz []byte) error

Unmarshal deserialises the SparseMerkleProof from bytes

type SparseMerkleSumTrie added in v0.8.0 

type SparseMerkleSumTrie interface {
	// Update inserts a value and its sum into the SMST.
	Update(key, value []byte, sum uint64) error
	// Delete deletes a value from the SMST. Raises an error if the key is not present.
	Delete(key []byte) error
	// Get descends the trie to access a value. Returns nil if key is not present.
	Get(key []byte) (data []byte, sum uint64, err error)
	// Root computes the Merkle root digest.
	Root() MerkleRoot
	// Sum computes the total sum of the Merkle trie
	Sum() uint64
	// Count returns the total number of non-empty leaves in the trie
	Count() uint64
	// Prove computes a Merkle proof of inclusion or exclusion of a key.
	Prove(key []byte) (*SparseMerkleProof, error)
	// ProveClosest computes a Merkle proof of inclusion for a key in the trie
	// which is closest to the path provided. It will search for the key with
	// the longest common prefix before finding the key with the most common
	// bits as the path provided.
	ProveClosest([]byte) (*SparseMerkleClosestProof, error)
	// Commit saves the trie's state to its persistent storage.
	Commit() error
	// Spec returns the TrieSpec for the trie
	Spec() *TrieSpec
}

SparseMerkleSumTrie represents a Sparse Merkle Sum Trie.

type SparseMerkleTrie added in v0.8.0 

type SparseMerkleTrie interface {
	// Update inserts a value into the SMT.
	Update(key, value []byte) error
	// Delete deletes a value from the SMT. Raises an error if the key is not present.
	Delete(key []byte) error
	// Get descends the trie to access a value. Returns nil if key is not present.
	Get(key []byte) ([]byte, error)
	// Root computes the Merkle root digest.
	Root() MerkleRoot
	// Prove computes a Merkle proof of inclusion or exclusion of a key.
	Prove(key []byte) (*SparseMerkleProof, error)
	// ProveClosest computes a Merkle proof of inclusion for a key in the trie
	// which is closest to the path provided. It will search for the key with
	// the longest common prefix before finding the key with the most common
	// bits as the path provided.
	ProveClosest([]byte) (*SparseMerkleClosestProof, error)
	// Commit saves the trie's state to its persistent storage.
	Commit() error
	// Spec returns the TrieSpec for the trie
	Spec() *TrieSpec
}

SparseMerkleTrie represents a Sparse Merkle Trie.

type TrieSpec added in v0.8.0 

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

TrieSpec specifies the hashing functions used by a trie instance to encode leaf paths and stored values, and the corresponding maximum trie depth.

func NewTrieSpec added in v0.10.1 

func NewTrieSpec(
	hasher hash.Hash,
	sumTrie bool,
	opts ...TrieSpecOption,
) TrieSpec

NewTrieSpec returns a new TrieSpec with the given hasher and sumTrie flag

func (*TrieSpec) PathHasherSize added in v0.10.0 

func (spec *TrieSpec) PathHasherSize() int

PathHasherSize returns the length (in bytes) of digests produced by the path hasher

func (*TrieSpec) Spec added in v0.8.0 

func (spec *TrieSpec) Spec() *TrieSpec

Spec returns the TrieSpec associated with the given trie

type TrieSpecOption added in v0.11.0 

type TrieSpecOption func(*TrieSpec)

TrieSpecOption is a function that configures SparseMerkleTrie.

func WithPathHasher added in v0.5.0 

func WithPathHasher(ph PathHasher) TrieSpecOption

WithPathHasher returns an Option that sets the PathHasher to the one provided this MUST not be nil or unknown behaviour will occur.

func WithValueHasher added in v0.5.0 

func WithValueHasher(vh ValueHasher) TrieSpecOption

WithValueHasher returns an Option that sets the ValueHasher to the one provided

type ValueHasher added in v0.5.0 

type ValueHasher interface {
	// HashValue hashes value data to produce the digest stored in leaf node.
	HashValue([]byte) []byte
	// ValueHashSize returns the length (in bytes) of digests produced by this hasher.
	ValueHashSize() int
}

ValueHasher defines how value data is hashed to produce leaf data.

Source Files

View all Source files

Directories

Path Synopsis
Package kvstore provides a series of sub-modules that (if they comply with the MapStore interface) can be used as the underlying nodestore for the trie.
 Package kvstore provides a series of sub-modules that (if they comply with the MapStore interface) can be used as the underlying nodestore for the trie.
simplemap
Package simplemap provides a simple in-memory map.
 Package simplemap provides a simple in-memory map.
badger module
pebble module

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.