mssmt

package
v0.3.3 Latest Latest
Warning

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

 Go to latest Published: Feb 7, 2024 License: MIT Imports: 17 Imported by: 0

Documentation

Index

Constants

View Source 
const (
	// MaxTreeLevels represents the depth of the MS-SMT.
	MaxTreeLevels = hashSize * 8
)

Variables

View Source 
var (
	// EmptyLeafNode represents an empty leaf in a MS-SMT, one with a nil
	// value and 0 sum.
	EmptyLeafNode = NewLeafNode(nil, 0)

	// ZeroNodeHash represents the empty node hash that is all zeroes.
	ZeroNodeHash = NodeHash{}
)
View Source 
var (
	// EmptyTree stores a copy of all nodes up to the root in a MS-SMT in
	// which all the leaves are empty.
	EmptyTree []Node

	// EmptyTreeRootHash caches the value of a completely empty tree's root
	// hash. This can be used to detect a tree's emptiness without needing
	// to rely on the root sum alone.
	EmptyTreeRootHash NodeHash

	// ErrIntegerOverflow is an error returned when the result of an
	// arithmetic operation on two integer values exceeds the maximum value
	// that can be stored in the data type.
	ErrIntegerOverflow = errors.New("integer overflow")
)
View Source 
var (
	ErrExceedsMaxLeafSize = fmt.Errorf(
		"proof leaf exceeds maximum size of %d bytes", maxLeafSize,
	)
)
View Source 
var (
	// ErrInvalidCompressedProof is returned when a compressed proof has an
	// invalid combination of explicit nodes and default hash bits.
	ErrInvalidCompressedProof = errors.New("mssmt: invalid compressed proof")
)

Functions

func CheckSumOverflowUint64 

func CheckSumOverflowUint64(a, b uint64) error

CheckSumOverflowUint64 checks if the sum of two uint64 values will overflow.

func HexProof added in v0.3.0 

func HexProof(t testing.TB, proof *Proof) string

func IsEqualNode 

func IsEqualNode(a, b Node) bool

IsEqualNode determines whether a and b are equal based on their NodeHash and NodeSum.

func PackBits 

func PackBits(bits []bool) []byte

PackBits packs a bit vector into a byte slice.

func RandLeafAmount 

func RandLeafAmount() uint64

RandLeafAmount generates a random leaf node sum amount.

func RegisterTreeStore 

func RegisterTreeStore(driver *TreeStoreDriver) error

RegisterTreeStore registers a TreeStoreDriver which is capable of driving a concrete TreeStore interface. In the case that this driver has already been registered, an error is returned.

NOTE: This function is safe for concurrent access.

func UnpackBits 

func UnpackBits(bytes []byte) []bool

UnpackBits unpacks a byte slice into a bit vector.

func VerifyMerkleProof 

func VerifyMerkleProof(key [hashSize]byte, leaf *LeafNode, proof *Proof,
	root Node) bool

VerifyMerkleProof determines whether a merkle proof for the leaf found at the given key is valid.

Types

type BranchNode 

type BranchNode struct {
	Left  Node
	Right Node
	// contains filtered or unexported fields
}

BranchNode represents an intermediate or root node within a MS-SMT. It commits to its left and right children, along with their respective sum values.

func NewBranch 

func NewBranch(left, right Node) *BranchNode

NewBranch constructs a new branch backed by its left and right children.

func NewComputedBranch 

func NewComputedBranch(nodeHash NodeHash, sum uint64) *BranchNode

NewComputedBranch creates a new branch without any reference it its children. This method of construction allows as to walk the tree down by only fetching minimal subtrees.

func (*BranchNode) Copy 

func (n *BranchNode) Copy() Node

Copy returns a deep copy of the branch node, with its children returned as `ComputedNode`.

func (*BranchNode) NodeHash 

func (n *BranchNode) NodeHash() NodeHash

NodeHash returns the unique identifier for a MS-SMT node. It represents the hash of the branch committing to its internal data.

func (*BranchNode) NodeSum 

func (n *BranchNode) NodeSum() uint64

NodeSum returns the sum commitment of the branch's left and right children.

type CompactedLeafNode 

type CompactedLeafNode struct {
	*LeafNode
	// contains filtered or unexported fields
}

CompactedLeafNode holds a leaf node that represents a whole "compacted" subtree omitting all default branches and leafs in the represented subtree.

func NewCompactedLeafNode 

func NewCompactedLeafNode(height int, key *[32]byte,
	leaf *LeafNode) *CompactedLeafNode

NewCompactedLeafNode creates a new compacted leaf at the passed height with the passed leaf key.

func (*CompactedLeafNode) Copy 

func (c *CompactedLeafNode) Copy() Node

Copy returns a deep copy of the compacted leaf node.

func (*CompactedLeafNode) Extract 

func (c *CompactedLeafNode) Extract(height int) Node

Extract extracts the subtree represented by this compacted leaf and returns the topmost node in the tree.

func (*CompactedLeafNode) Key 

func (c *CompactedLeafNode) Key() [32]byte

Key returns the leaf key.

func (*CompactedLeafNode) NodeHash 

func (c *CompactedLeafNode) NodeHash() NodeHash

NodeHash returns the compacted subtree's node hash.

type CompactedTree 

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

CompactedTree represents a compacted Merkle-Sum Sparse Merkle Tree (MS-SMT). The tree has the same properties as a normal MS-SMT tree and is able to create the same proofs and same root as the FullTree implemented in this package. The additional benefit of using the CompactedTree is that it will greatly reduce storage access resulting in more performant access when used for large trees.

func NewCompactedTree 

func NewCompactedTree(store TreeStore) *CompactedTree

NewCompactedTree initializes an empty MS-SMT backed by `store`.

func (*CompactedTree) Delete 

func (t *CompactedTree) Delete(ctx context.Context, key [hashSize]byte) (
	Tree, error)

Delete deletes the leaf node found at the given key within the MS-SMT.

func (*CompactedTree) DeleteAllNodes added in v0.2.1 

func (t *CompactedTree) DeleteAllNodes(ctx context.Context) error

DeleteAllNodes deletes all nodes in the MS-SMT.

func (*CompactedTree) DeleteRoot added in v0.2.1 

func (t *CompactedTree) DeleteRoot(ctx context.Context) error

DeleteRoot deletes the root node of the MS-SMT.

func (*CompactedTree) Get 

func (t *CompactedTree) Get(ctx context.Context, key [hashSize]byte) (
	*LeafNode, error)

Get returns the leaf node found at the given key within the MS-SMT.

func (*CompactedTree) Insert 

func (t *CompactedTree) Insert(ctx context.Context, key [hashSize]byte,
	leaf *LeafNode) (Tree, error)

Insert inserts a leaf node at the given key within the MS-SMT.

func (*CompactedTree) MerkleProof 

func (t *CompactedTree) MerkleProof(ctx context.Context, key [hashSize]byte) (
	*Proof, error)

MerkleProof generates a merkle proof for the leaf node found at the given key within the MS-SMT. If a leaf node does not exist at the given key, then the proof should be considered a non-inclusion proof. This is noted by the returned `Proof` containing an empty leaf.

func (*CompactedTree) Root 

func (t *CompactedTree) Root(ctx context.Context) (*BranchNode, error)

Root returns the root node of the MS-SMT.

type CompressedProof 

type CompressedProof struct {
	// Bits determines whether a sibling node within a proof is part of the
	// empty tree. This allows us to efficiently compress proofs by not
	// including any pre-computed nodes.
	Bits []bool

	// Nodes represents the non-empty siblings that should be hashed with
	// the leaf and its parents to arrive at the root of the MS-SMT.
	Nodes []Node
}

CompressedProof represents a compressed MS-SMT merkle proof. Since merkle proofs for a MS-SMT are always constant size (255 nodes), we replace its empty nodes by a bit vector.

func (*CompressedProof) Decode 

func (p *CompressedProof) Decode(r io.Reader) error

Decode decodes the compressed proof encoded within Reader.

func (*CompressedProof) Decompress 

func (p *CompressedProof) Decompress() (*Proof, error)

Decompress decompresses a compressed merkle proof by replacing its bit vector with the empty nodes it represents.

func (*CompressedProof) Encode 

func (p *CompressedProof) Encode(w io.Writer) error

Encode encodes the compressed proof into the provided Writer.

type ComputedNode 

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

ComputedNode is a node within a MS-SMT that has already had its NodeHash and NodeSum computed, i.e., its preimage is not available.

func NewComputedNode 

func NewComputedNode(hash NodeHash, sum uint64) ComputedNode

NewComputedNode instantiates a new computed node.

func (ComputedNode) Copy 

func (n ComputedNode) Copy() Node

Copy returns a deep copy of the branch node.

func (ComputedNode) NodeHash 

func (n ComputedNode) NodeHash() NodeHash

NodeHash returns the unique identifier for a MS-SMT node. It represents the hash of the node committing to its internal data.

func (ComputedNode) NodeSum 

func (n ComputedNode) NodeSum() uint64

NodeSum returns the sum commitment of the node.

type DefaultStore 

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

DefaultStore is an in-memory implementation of the TreeStore interface.

func NewDefaultStore 

func NewDefaultStore() *DefaultStore

NewDefaultStore initializes a new DefaultStore.

func (*DefaultStore) DeleteAllNodes added in v0.2.1 

func (d *DefaultStore) DeleteAllNodes() error

DeleteAllNodes deletes all nodes in the MS-SMT.

func (*DefaultStore) DeleteBranch 

func (d *DefaultStore) DeleteBranch(key NodeHash) error

DeleteBranch deletes the branch node keyed by the given NodeHash.

func (*DefaultStore) DeleteCompactedLeaf 

func (d *DefaultStore) DeleteCompactedLeaf(key NodeHash) error

DeleteCompactedLeaf deletes a compacted leaf keyed by the given NodeHash.

func (*DefaultStore) DeleteLeaf 

func (d *DefaultStore) DeleteLeaf(key NodeHash) error

DeleteLeaf deletes the leaf node keyed by the given NodeHash.

func (*DefaultStore) DeleteRoot added in v0.2.1 

func (d *DefaultStore) DeleteRoot() error

DeleteRoot deletes the root node of the MS-SMT.

func (*DefaultStore) GetChildren 

func (d *DefaultStore) GetChildren(height int, key NodeHash) (
	Node, Node, error)

GetChildren returns the left and right child of the node keyed by the given NodeHash.

func (*DefaultStore) InsertBranch 

func (d *DefaultStore) InsertBranch(branch *BranchNode) error

InsertBranch stores a new branch keyed by its NodeHash.

func (*DefaultStore) InsertCompactedLeaf 

func (d *DefaultStore) InsertCompactedLeaf(leaf *CompactedLeafNode) error

InsertCompactedLeaf stores a new compacted leaf keyed by its NodeHash (not the insertion key).

func (*DefaultStore) InsertLeaf 

func (d *DefaultStore) InsertLeaf(leaf *LeafNode) error

InsertLeaf stores a new leaf keyed by its NodeHash.

func (*DefaultStore) NumBranches 

func (d *DefaultStore) NumBranches() int

NumBranches returns the number of stored branches.

func (*DefaultStore) NumCompactedLeaves 

func (d *DefaultStore) NumCompactedLeaves() int

NumCompactedLeaves returns the number of stored compacted leaves.

func (*DefaultStore) NumLeaves 

func (d *DefaultStore) NumLeaves() int

NumLeaves returns the number of stored leaves.

func (*DefaultStore) RootNode 

func (d *DefaultStore) RootNode() (Node, error)

RootNode returns the root node of the tree.

func (*DefaultStore) Stats 

func (d *DefaultStore) Stats() string

Stats returns store statistics as a string (useful for debugging).

func (*DefaultStore) Update 

func (d *DefaultStore) Update(_ context.Context,
	update func(tx TreeStoreUpdateTx) error) error

Update updates the persistent tree in the passed update closure using the update transaction.

func (*DefaultStore) UpdateRoot 

func (d *DefaultStore) UpdateRoot(node *BranchNode) error

UpdateRoot updates the index that points to the root node for the persistent tree.

NOTE: For some implementations this may be a noop, as the index of the backing storage is able to track the root node easily.

func (*DefaultStore) View 

func (d *DefaultStore) View(_ context.Context,
	view func(tx TreeStoreViewTx) error) error

View gives a view of the persistent tree in the passed view closure using the view transaction.

type ErrorTestCase added in v0.3.0 

type ErrorTestCase struct {
	InsertedLeaves []string `json:"inserted_leaves"`
	Error          string   `json:"error"`
	Comment        string   `json:"comment"`
}

func (*ErrorTestCase) ShouldInsert added in v0.3.0 

func (ec *ErrorTestCase) ShouldInsert(key string) bool

type FullTree 

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

FullTree represents a Merkle-Sum Sparse Merkle Tree (MS-SMT). A MS-SMT is an augmented version of a sparse merkle tree that includes a sum value, which is combined during the internal branch hashing operation. Such trees permit efficient proofs of non-inclusion, while also supporting efficient fault proofs of invalid merkle sum commitments.

func NewFullTree 

func NewFullTree(store TreeStore) *FullTree

NewFullTree initializes an empty MS-SMT backed by `store`. As a result, `store` will only maintain non-empty relevant nodes, i.e., stale parents are deleted and empty nodes are never stored.

func (*FullTree) Delete 

func (t *FullTree) Delete(ctx context.Context, key [hashSize]byte) (
	Tree, error)

Delete deletes the leaf node found at the given key within the MS-SMT.

func (*FullTree) DeleteAllNodes added in v0.2.1 

func (t *FullTree) DeleteAllNodes(ctx context.Context) error

DeleteAllNodes deletes all nodes in the MS-SMT.

func (*FullTree) DeleteRoot added in v0.2.1 

func (t *FullTree) DeleteRoot(ctx context.Context) error

DeleteRoot deletes the root node of the MS-SMT.

func (*FullTree) Get 

func (t *FullTree) Get(ctx context.Context, key [hashSize]byte) (
	*LeafNode, error)

Get returns the leaf node found at the given key within the MS-SMT.

func (*FullTree) Insert 

func (t *FullTree) Insert(ctx context.Context, key [hashSize]byte,
	leaf *LeafNode) (Tree, error)

Insert inserts a leaf node at the given key within the MS-SMT.

func (*FullTree) MerkleProof 

func (t *FullTree) MerkleProof(ctx context.Context, key [hashSize]byte) (
	*Proof, error)

MerkleProof generates a merkle proof for the leaf node found at the given key within the MS-SMT. If a leaf node does not exist at the given key, then the proof should be considered a non-inclusion proof. This is noted by the returned `Proof` containing an empty leaf.

func (*FullTree) Root 

func (t *FullTree) Root(ctx context.Context) (*BranchNode, error)

Root returns the root node of the MS-SMT.

type LeafNode 

type LeafNode struct {
	Value []byte
	// contains filtered or unexported fields
}

LeafNode represents a leaf node within a MS-SMT. Leaf nodes commit to a value and some integer value (the sum) associated with the value.

func NewLeafNode 

func NewLeafNode(value []byte, sum uint64) *LeafNode

NewLeafNode constructs a new leaf node.

func (*LeafNode) Copy 

func (n *LeafNode) Copy() Node

Copy returns a deep copy of the leaf node.

func (*LeafNode) IsEmpty 

func (n *LeafNode) IsEmpty() bool

IsEmpty returns whether this is an empty leaf.

func (*LeafNode) NodeHash 

func (n *LeafNode) NodeHash() NodeHash

NodeHash returns the unique identifier for a MS-SMT node. It represents the hash of the leaf committing to its internal data.

func (*LeafNode) NodeSum 

func (n *LeafNode) NodeSum() uint64

NodeSum returns the sum commitment of the leaf node.

type Node 

type Node interface {
	// NodeHash returns the unique identifier for a MS-SMT node. It
	// represents the hash of the node committing to its internal data.
	NodeHash() NodeHash

	// NodeSum returns the sum commitment of the node.
	NodeSum() uint64

	// Copy returns a deep copy of the node.
	Copy() Node
}

Node represents a MS-SMT node. A node can either be a leaf or a branch.

type NodeHash 

type NodeHash [hashSize]byte

NodeHash represents the key of a MS-SMT node.

func (NodeHash) String 

func (k NodeHash) String() string

String returns a NodeHash as a hex-encoded string.

type Proof 

type Proof struct {
	// Nodes represents the siblings that should be hashed with the leaf and
	// its parents to arrive at the root of the MS-SMT.
	Nodes []Node
}

Proof represents a merkle proof for a MS-SMT.

func NewProof 

func NewProof(nodes []Node) *Proof

NewProof initializes a new merkle proof for the given leaf node.

func ParseProof added in v0.3.0 

func ParseProof(t testing.TB, proofHex string) Proof

func RandProof added in v0.3.0 

func RandProof(t testing.TB) *Proof

RandProof returns a random proof for testing.

func (Proof) Compress 

func (p Proof) Compress() *CompressedProof

Compress compresses a merkle proof by replacing its empty nodes with a bit vector.

func (Proof) Copy 

func (p Proof) Copy() *Proof

Copy returns a deep copy of the proof.

func (Proof) Root 

func (p Proof) Root(key [32]byte, leaf *LeafNode) *BranchNode

Root returns the root node obtained by walking up the tree.

type TestLeaf added in v0.3.0 

type TestLeaf struct {
	Key  string        `json:"key"`
	Node *TestLeafNode `json:"node"`
}

func NewTestFromLeaf added in v0.3.0 

func NewTestFromLeaf(t testing.TB, key [32]byte, leaf *LeafNode) *TestLeaf

func (*TestLeaf) ToLeafNode added in v0.3.0 

func (tl *TestLeaf) ToLeafNode(t testing.TB) *LeafNode

type TestLeafNode added in v0.3.0 

type TestLeafNode struct {
	Value string `json:"value"`
	Sum   string `json:"sum"`
}

type TestNode added in v0.3.0 

type TestNode struct {
	Hash string `json:"hash"`
	Sum  string `json:"sum"`
}

func NewTestFromNode added in v0.3.0 

func NewTestFromNode(t testing.TB, node Node) *TestNode

func (*TestNode) ToNode added in v0.3.0 

func (tn *TestNode) ToNode(t testing.TB) ComputedNode

type TestProof added in v0.3.0 

type TestProof struct {
	Nodes map[int]*TestNode `json:"nodes"`
}

func NewTestFromProof added in v0.3.0 

func NewTestFromProof(t testing.TB, p *Proof) *TestProof

func (*TestProof) ToProof added in v0.3.0 

func (tp *TestProof) ToProof(t testing.TB) *Proof

type TestProofCase added in v0.3.0 

type TestProofCase struct {
	ProofKey        string `json:"proof_key"`
	CompressedProof string `json:"compressed_proof"`
}

func (*TestProofCase) ToProof added in v0.3.0 

func (tpc *TestProofCase) ToProof(t testing.TB) *Proof

type TestVectors added in v0.3.0 

type TestVectors struct {
	AllTreeLeaves  []*TestLeaf      `json:"all_tree_leaves"`
	ValidTestCases []*ValidTestCase `json:"valid_test_cases"`
	ErrorTestCases []*ErrorTestCase `json:"error_test_cases"`
}

func (*TestVectors) FindLeaf added in v0.3.0 

func (tv *TestVectors) FindLeaf(key string) *TestLeaf

type Tree 

type Tree interface {
	// Root returns the root node of the MS-SMT.
	Root(ctx context.Context) (*BranchNode, error)

	// Insert inserts a leaf node at the given key within the MS-SMT.
	Insert(ctx context.Context, key [hashSize]byte, leaf *LeafNode) (
		Tree, error)

	// Delete deletes the leaf node found at the given key within the
	// MS-SMT.
	Delete(ctx context.Context, key [hashSize]byte) (Tree, error)

	// DeleteRoot deletes the root node of the MS-SMT.
	DeleteRoot(ctx context.Context) error

	// DeleteAllNodes deletes all non-root nodes within the MS-SMT.
	DeleteAllNodes(ctx context.Context) error

	// Get returns the leaf node found at the given key within the MS-SMT.
	Get(ctx context.Context, key [hashSize]byte) (*LeafNode, error)

	// MerkleProof generates a merkle proof for the leaf node found at the
	// given key within the MS-SMT. If a leaf node does not exist at the
	// given key, then the proof should be considered a non-inclusion
	// proof. This is noted by the returned `Proof` containing an empty
	// leaf.
	MerkleProof(ctx context.Context, key [hashSize]byte) (*Proof, error)
}

Tree is an interface defining an abstract MSSMT tree type.

type TreeStore 

type TreeStore interface {
	// Update updates the persistent tree in the passed update closure using
	// the update transaction.
	Update(context.Context, func(tx TreeStoreUpdateTx) error) error

	// View gives a view of the persistent tree in the passed view closure
	// using the view transaction.
	View(context.Context, func(tx TreeStoreViewTx) error) error
}

TreeStore represents a generic database interface to update or view a generic MSSMT tree atomically.

type TreeStoreDriver 

type TreeStoreDriver struct {
	// Name is the anme of the minting store driver.
	Name string

	// New creates a new concrete instance of the TreeStore given a set of
	// arguments.
	New func(args ...any) (TreeStore, error)
}

TreeStoreDriver represents a concrete driver of the main TreeStore interface. A driver is identified by a globally unique string identifier, along with a 'New()' method which is responsible for initializing a particular TreeStore concrete implementation.

func RegisteredTreeStores 

func RegisteredTreeStores() []*TreeStoreDriver

RegisteredTreeStores returns a slice of all currently registered minting stores.

NOTE: This function is safe for concurrent access.

type TreeStoreUpdateTx 

type TreeStoreUpdateTx interface {
	TreeStoreViewTx

	// UpdateRoot updates the index that points to the root node for the
	// persistent tree.
	//
	// NOTE: For some implementations this may be a noop, as the index of
	// the backing storage is able to track the root node easily.
	UpdateRoot(*BranchNode) error

	// InsertBranch stores a new branch keyed by its NodeHash.
	InsertBranch(*BranchNode) error

	// InsertLeaf stores a new leaf keyed by its NodeHash (not the insertion
	// key).
	InsertLeaf(*LeafNode) error

	// InsertCompactedLeaf stores a new compacted leaf keyed by its
	// NodeHash (not the insertion key).
	InsertCompactedLeaf(*CompactedLeafNode) error

	// DeleteBranch deletes the branch node keyed by the given NodeHash.
	DeleteBranch(NodeHash) error

	// DeleteLeaf deletes the leaf node keyed by the given NodeHash.
	DeleteLeaf(NodeHash) error

	// DeleteCompactedLeaf deletes a compacted leaf keyed by the given
	// NodeHash.
	DeleteCompactedLeaf(NodeHash) error

	// DeleteRoot deletes the root node of the MS-SMT.
	DeleteRoot() error

	// DeleteAllNodes deletes all nodes in the MS-SMT.
	DeleteAllNodes() error
}

TreeStoreUpdateTx is an interface encompassing all methods of an updating persistent tree transaction.

type TreeStoreViewTx 

type TreeStoreViewTx interface {
	// GetChildren returns the left and right child of the node keyed by
	// the given NodeHash.
	GetChildren(int, NodeHash) (Node, Node, error)

	// RootNode returns the root node of the tree.
	RootNode() (Node, error)
}

TreeStoreViewTx is an interface encompassing all methods of a view only persistent tree transaction.

type ValidTestCase added in v0.3.0 

type ValidTestCase struct {
	RootHash        string           `json:"root_hash"`
	RootSum         string           `json:"root_sum"`
	InsertedLeaves  []string         `json:"inserted_leaves"`
	DeletedLeaves   []string         `json:"deleted_leaves"`
	ReplacedLeaves  []*TestLeaf      `json:"replaced_leaves"`
	InclusionProofs []*TestProofCase `json:"inclusion_proofs"`
	ExclusionProofs []*TestProofCase `json:"exclusion_proofs"`
	Comment         string           `json:"comment"`
}

func (*ValidTestCase) ShouldDelete added in v0.3.0 

func (tc *ValidTestCase) ShouldDelete(key string) bool

func (*ValidTestCase) ShouldInsert added in v0.3.0 

func (tc *ValidTestCase) ShouldInsert(key string) bool

Source Files

View all Source files

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.