smt

package module
v0.10.2 Latest Latest
Warning

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

 Go to latest Published: Apr 11, 2024 License: MIT Imports: 8 Imported by: 8

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

Package smt provides an implementation of a Sparse Merkle Trie for a key-value map.

The trie implements the same optimizations specified in the JMT whitepaper to account for empty and single-node subtrees. Unlike the JMT, it only supports binary trees and does not optimise for RockDB on-disk storage.

This package implements novel features that include native in-node weight sums, as well as support for ClosestProof mechanics.

Index

Examples

Constants

This section is empty.

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 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 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 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) Sum added in v0.9.0 

func (r MerkleRoot) Sum() uint64

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 panic.

type Option 

type Option func(*TrieSpec)

Option is a function that configures SparseMerkleTrie.

func WithPathHasher added in v0.5.0 

func WithPathHasher(ph PathHasher) Option

WithPathHasher returns an Option that sets the PathHasher to the one provided

func WithValueHasher added in v0.5.0 

func WithValueHasher(vh ValueHasher) Option

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

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.

func NewNilPathHasher added in v0.10.2 

func NewNilPathHasher(hashSize int) PathHasher

type SMST added in v0.6.0 

type SMST struct {
	TrieSpec
	*SMT
}

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

Example 
package main

import (
	"crypto/sha256"
	"fmt"

	"github.com/pokt-network/smt"
	"github.com/pokt-network/smt/kvstore/simplemap"
)

func main() {
	// Initialise a new in-memory key-value store to store the nodes of the trie
	// (Note: the trie only stores hashed values, not raw value data)
	nodeStore := simplemap.NewSimpleMap()

	// Initialise the trie
	trie := smt.NewSparseMerkleSumTrie(nodeStore, sha256.New())

	// Update trie with keys, values and their sums
	_ = trie.Update([]byte("foo"), []byte("oof"), 10)
	_ = trie.Update([]byte("baz"), []byte("zab"), 7)
	_ = trie.Update([]byte("bin"), []byte("nib"), 3)

	// Commit the changes to the nodeStore
	_ = trie.Commit()

	// Calculate the total sum of the trie
	_ = trie.Sum() // 20

	// Generate a Merkle proof for "foo"
	proof1, _ := trie.Prove([]byte("foo"))
	proof2, _ := trie.Prove([]byte("baz"))
	proof3, _ := trie.Prove([]byte("bin"))

	// We also need the current trie root for the proof
	root := trie.Root()

	// Verify the Merkle proof for "foo"="oof" where "foo" has a sum of 10
	valid_true1, _ := smt.VerifySumProof(proof1, root, []byte("foo"), []byte("oof"), 10, trie.Spec())
	// Verify the Merkle proof for "baz"="zab" where "baz" has a sum of 7
	valid_true2, _ := smt.VerifySumProof(proof2, root, []byte("baz"), []byte("zab"), 7, trie.Spec())
	// Verify the Merkle proof for "bin"="nib" where "bin" has a sum of 3
	valid_true3, _ := smt.VerifySumProof(proof3, root, []byte("bin"), []byte("nib"), 3, trie.Spec())
	// Fail to verify the Merkle proof for "foo"="oof" where "foo" has a sum of 11
	valid_false1, _ := smt.VerifySumProof(proof1, root, []byte("foo"), []byte("oof"), 11, trie.Spec())
	fmt.Println(valid_true1, valid_true2, valid_true3, valid_false1)
}

Output:

true true true false

func ImportSparseMerkleSumTrie added in v0.8.0 

func ImportSparseMerkleSumTrie(
	nodes kvstore.MapStore,
	hasher hash.Hash,
	root []byte,
	options ...Option,
) *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 ...Option,
) *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) 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) ([]byte, uint64, error)

Get returns the digest of the value stored at the given key and the weight of the leaf node

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 uint64 sum of the entire trie

func (*SMST) Update added in v0.6.0 

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

Update sets the value for the given key, to the digest of the provided value appended with the binary representation of the weight provided. The weight is used to compute the interim and 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

Example 
package main

import (
	"crypto/sha256"
	"fmt"

	"github.com/pokt-network/smt"
	"github.com/pokt-network/smt/kvstore/simplemap"
)

func main() {
	// Initialise a new in-memory key-value store to store the nodes of the trie
	// (Note: the trie only stores hashed values, not raw value data)
	nodeStore := simplemap.NewSimpleMap()

	// Initialise the trie
	trie := smt.NewSparseMerkleTrie(nodeStore, sha256.New())

	// Update the key "foo" with the value "bar"
	_ = trie.Update([]byte("foo"), []byte("bar"))

	// Commit the changes to the node store
	_ = trie.Commit()

	// Generate a Merkle proof for "foo"
	proof, _ := trie.Prove([]byte("foo"))
	root := trie.Root() // We also need the current trie root for the proof

	// Verify the Merkle proof for "foo"="bar"
	valid, _ := smt.VerifyProof(proof, root, []byte("foo"), []byte("bar"), trie.Spec())
	// Attempt to verify the Merkle proof for "foo"="baz"
	invalid, _ := smt.VerifyProof(proof, root, []byte("foo"), []byte("baz"), trie.Spec())
	fmt.Println(valid, invalid)
}

Output:

true false

func ImportSparseMerkleTrie added in v0.8.0 

func ImportSparseMerkleTrie(
	nodes kvstore.MapStore,
	hasher hash.Hash,
	root []byte,
	options ...Option,
) *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 ...Option,
) *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 digest of the 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 []byte, value []byte) error

Update sets the value for the given key, to the digest of the provided value

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) ([]byte, uint64, error)
	// Root computes the Merkle root digest.
	Root() MerkleRoot
	// Sum computes the total sum of the Merkle trie
	Sum() 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 ...Option) TrieSpec

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

func (*TrieSpec) TrieHasherSize added in v0.10.0 

func (spec *TrieSpec) TrieHasherSize() int

TrieHasherSize returns the length (in bytes) of digests produced by the trie hasher

func (*TrieSpec) ValueHasherSize added in v0.10.0 

func (spec *TrieSpec) ValueHasherSize() int

ValueHasherSize returns the length (in bytes) of digests produced by the value hasher

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

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.