Documentation ¶
Index ¶
- Constants
- Variables
- func CheckSumOverflowUint64(a, b uint64) error
- func IsEqualNode(a, b Node) bool
- func PackBits(bits []bool) []byte
- func RandLeafAmount() uint64
- func RegisterTreeStore(driver *TreeStoreDriver) error
- func UnpackBits(bytes []byte) []bool
- func VerifyMerkleProof(key [hashSize]byte, leaf *LeafNode, proof *Proof, root Node) bool
- type BranchNode
- type CompactedLeafNode
- type CompactedTree
- func (t *CompactedTree) Delete(ctx context.Context, key [hashSize]byte) (Tree, error)
- func (t *CompactedTree) DeleteAllNodes(ctx context.Context) error
- func (t *CompactedTree) DeleteRoot(ctx context.Context) error
- func (t *CompactedTree) Get(ctx context.Context, key [hashSize]byte) (*LeafNode, error)
- func (t *CompactedTree) Insert(ctx context.Context, key [hashSize]byte, leaf *LeafNode) (Tree, error)
- func (t *CompactedTree) MerkleProof(ctx context.Context, key [hashSize]byte) (*Proof, error)
- func (t *CompactedTree) Root(ctx context.Context) (*BranchNode, error)
- type CompressedProof
- type ComputedNode
- type DefaultStore
- func (d *DefaultStore) DeleteAllNodes() error
- func (d *DefaultStore) DeleteBranch(key NodeHash) error
- func (d *DefaultStore) DeleteCompactedLeaf(key NodeHash) error
- func (d *DefaultStore) DeleteLeaf(key NodeHash) error
- func (d *DefaultStore) DeleteRoot() error
- func (d *DefaultStore) GetChildren(height int, key NodeHash) (Node, Node, error)
- func (d *DefaultStore) InsertBranch(branch *BranchNode) error
- func (d *DefaultStore) InsertCompactedLeaf(leaf *CompactedLeafNode) error
- func (d *DefaultStore) InsertLeaf(leaf *LeafNode) error
- func (d *DefaultStore) NumBranches() int
- func (d *DefaultStore) NumCompactedLeaves() int
- func (d *DefaultStore) NumLeaves() int
- func (d *DefaultStore) RootNode() (Node, error)
- func (d *DefaultStore) Stats() string
- func (d *DefaultStore) Update(_ context.Context, update func(tx TreeStoreUpdateTx) error) error
- func (d *DefaultStore) UpdateRoot(node *BranchNode) error
- func (d *DefaultStore) View(_ context.Context, view func(tx TreeStoreViewTx) error) error
- type FullTree
- func (t *FullTree) Delete(ctx context.Context, key [hashSize]byte) (Tree, error)
- func (t *FullTree) DeleteAllNodes(ctx context.Context) error
- func (t *FullTree) DeleteRoot(ctx context.Context) error
- func (t *FullTree) Get(ctx context.Context, key [hashSize]byte) (*LeafNode, error)
- func (t *FullTree) Insert(ctx context.Context, key [hashSize]byte, leaf *LeafNode) (Tree, error)
- func (t *FullTree) MerkleProof(ctx context.Context, key [hashSize]byte) (*Proof, error)
- func (t *FullTree) Root(ctx context.Context) (*BranchNode, error)
- type LeafNode
- type Node
- type NodeHash
- type Proof
- type Tree
- type TreeStore
- type TreeStoreDriver
- type TreeStoreUpdateTx
- type TreeStoreViewTx
Constants ¶
const (
// MaxTreeLevels represents the depth of the MS-SMT.
MaxTreeLevels = hashSize * 8
)
Variables ¶
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{} )
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") )
var (
ErrExceedsMaxLeafSize = fmt.Errorf(
"proof leaf exceeds maximum size of %d bytes", maxLeafSize,
)
)
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 ¶
CheckSumOverflowUint64 checks if the sum of two uint64 values will overflow.
func IsEqualNode ¶
IsEqualNode determines whether a and b are equal based on their NodeHash and NodeSum.
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 ¶
UnpackBits unpacks a byte slice into a bit vector.
Types ¶
type BranchNode ¶
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 ¶
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) 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 ¶
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.
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 ¶
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 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 ¶
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) DeleteAllNodes ¶ added in v0.2.1
DeleteAllNodes deletes all nodes in the MS-SMT.
func (*FullTree) DeleteRoot ¶ added in v0.2.1
DeleteRoot deletes the root node of the MS-SMT.
func (*FullTree) MerkleProof ¶
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.
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 ¶
NewLeafNode constructs a new 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 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 (Proof) Compress ¶
func (p Proof) Compress() *CompressedProof
Compress compresses a merkle proof by replacing its empty nodes with a bit vector.
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.