README
¶
smt
A Go library that implements a Sparse Merkle tree for a key-value map. The tree implements the same optimisations specified in the Libra whitepaper, to reduce the number of hash operations required per tree operation to O(k) where k is the number of non-empty elements in the tree.
Example
package main
import (
"crypto/sha256"
"fmt"
"github.com/celestiaorg/smt"
)
func main() {
// Initialise two new key-value store to store the nodes and values of the tree
nodeStore := smt.NewSimpleMap()
valueStore := smt.NewSimpleMap()
// Initialise the tree
tree := smt.NewSparseMerkleTree(nodeStore, valueStore, sha256.New())
// Update the key "foo" with the value "bar"
_, _ = tree.Update([]byte("foo"), []byte("bar"))
// Generate a Merkle proof for foo=bar
proof, _ := tree.Prove([]byte("foo"))
root := tree.Root() // We also need the current tree root for the proof
// Verify the Merkle proof for foo=bar
if smt.VerifyProof(proof, root, []byte("foo"), []byte("bar"), sha256.New()) {
fmt.Println("Proof verification succeeded.")
} else {
fmt.Println("Proof verification failed.")
}
}
Documentation
¶
Overview ¶
Package smt implements a Sparse Merkle tree.
Index ¶
- Variables
- func VerifyCompactProof(proof SparseCompactMerkleProof, root []byte, key []byte, value []byte, ...) bool
- func VerifyProof(proof SparseMerkleProof, root []byte, key []byte, value []byte, ...) bool
- type DeepSparseMerkleSubTree
- type InvalidKeyError
- type MapStore
- type Option
- type SimpleMap
- type SparseCompactMerkleProof
- type SparseMerkleProof
- type SparseMerkleTree
- func (smt *SparseMerkleTree) Delete(key []byte) ([]byte, error)
- func (smt *SparseMerkleTree) DeleteForRoot(key, root []byte) ([]byte, error)
- func (smt *SparseMerkleTree) Get(key []byte) ([]byte, error)
- func (smt *SparseMerkleTree) GetDescend(key []byte) ([]byte, error)
- func (smt *SparseMerkleTree) Has(key []byte) (bool, error)
- func (smt *SparseMerkleTree) HasDescend(key []byte) (bool, error)
- func (smt *SparseMerkleTree) Prove(key []byte) (SparseMerkleProof, error)
- func (smt *SparseMerkleTree) ProveCompact(key []byte) (SparseCompactMerkleProof, error)
- func (smt *SparseMerkleTree) ProveCompactForRoot(key []byte, root []byte) (SparseCompactMerkleProof, error)
- func (smt *SparseMerkleTree) ProveForRoot(key []byte, root []byte) (SparseMerkleProof, error)
- func (smt *SparseMerkleTree) ProveUpdatable(key []byte) (SparseMerkleProof, error)
- func (smt *SparseMerkleTree) ProveUpdatableForRoot(key []byte, root []byte) (SparseMerkleProof, error)
- func (smt *SparseMerkleTree) Root() []byte
- func (smt *SparseMerkleTree) SetRoot(root []byte)
- func (smt *SparseMerkleTree) Update(key []byte, value []byte) ([]byte, error)
- func (smt *SparseMerkleTree) UpdateForRoot(key []byte, value []byte, root []byte) ([]byte, error)
Constants ¶
This section is empty.
Variables ¶
var ErrBadProof = errors.New("bad proof")
ErrBadProof is returned when an invalid Merkle proof is supplied.
Functions ¶
func VerifyCompactProof ¶
func VerifyCompactProof(proof SparseCompactMerkleProof, root []byte, key []byte, value []byte, hasher hash.Hash) bool
VerifyCompactProof verifies a compacted Merkle proof.
func VerifyProof ¶
func VerifyProof(proof SparseMerkleProof, root []byte, key []byte, value []byte, hasher hash.Hash) bool
VerifyProof verifies a Merkle proof.
Types ¶
type DeepSparseMerkleSubTree ¶
type DeepSparseMerkleSubTree struct {
*SparseMerkleTree
}
DeepSparseMerkleSubTree is a deep Sparse Merkle subtree for working on only a few leafs.
func NewDeepSparseMerkleSubTree ¶
func NewDeepSparseMerkleSubTree(nodes, values MapStore, hasher hash.Hash, root []byte) *DeepSparseMerkleSubTree
NewDeepSparseMerkleSubTree creates a new deep Sparse Merkle subtree on an empty MapStore.
func (*DeepSparseMerkleSubTree) AddBranch ¶
func (dsmst *DeepSparseMerkleSubTree) AddBranch(proof SparseMerkleProof, key []byte, value []byte) error
AddBranch adds a branch to the tree. These branches are generated by smt.ProveForRoot. If the proof is invalid, a ErrBadProof is returned.
If the leaf may be updated (e.g. during a state transition fraud proof), an updatable proof should be used. See SparseMerkleTree.ProveUpdatable.
type InvalidKeyError ¶
type InvalidKeyError struct {
Key []byte
}
InvalidKeyError is thrown when a key that does not exist is being accessed.
func (*InvalidKeyError) Error ¶
func (e *InvalidKeyError) Error() string
type MapStore ¶
type MapStore interface {
Get(key []byte) ([]byte, error) // Get gets the value for a key.
Set(key []byte, value []byte) error // Set updates the value for a key.
Delete(key []byte) error // Delete deletes a key.
}
MapStore is a key-value store.
type SimpleMap ¶
type SimpleMap struct {
// contains filtered or unexported fields
}
SimpleMap is a simple in-memory map.
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 SparseMerkleTree.
func CompactProof ¶
func CompactProof(proof SparseMerkleProof, hasher hash.Hash) (SparseCompactMerkleProof, error)
CompactProof compacts a proof, to reduce its size.
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 SparseMerkleTree.
func DecompactProof ¶
func DecompactProof(proof SparseCompactMerkleProof, hasher hash.Hash) (SparseMerkleProof, error)
DecompactProof decompacts a proof, so that it can be used for VerifyProof.
type SparseMerkleTree ¶
type SparseMerkleTree struct {
// contains filtered or unexported fields
}
SparseMerkleTree is a Sparse Merkle tree.
func ImportSparseMerkleTree ¶
func ImportSparseMerkleTree(nodes, values MapStore, hasher hash.Hash, root []byte) *SparseMerkleTree
ImportSparseMerkleTree imports a Sparse Merkle tree from a non-empty MapStore.
func NewSparseMerkleTree ¶
func NewSparseMerkleTree(nodes, values MapStore, hasher hash.Hash, options ...Option) *SparseMerkleTree
NewSparseMerkleTree creates a new Sparse Merkle tree on an empty MapStore.
func (*SparseMerkleTree) Delete ¶
func (smt *SparseMerkleTree) Delete(key []byte) ([]byte, error)
Delete deletes a value from tree. It returns the new root of the tree.
func (*SparseMerkleTree) DeleteForRoot ¶
func (smt *SparseMerkleTree) DeleteForRoot(key, root []byte) ([]byte, error)
DeleteForRoot deletes a value from tree at a specific root. It returns the new root of the tree.
func (*SparseMerkleTree) Get ¶
func (smt *SparseMerkleTree) Get(key []byte) ([]byte, error)
Get gets the value of a key from the tree.
func (*SparseMerkleTree) GetDescend ¶
func (smt *SparseMerkleTree) GetDescend(key []byte) ([]byte, error)
GetDescend gets the value of a key from the tree by descending it. Use if a key was _not_ previously added with AddBranch, otherwise use Get. Errors if the key cannot be reached by descending.
func (*SparseMerkleTree) Has ¶
func (smt *SparseMerkleTree) Has(key []byte) (bool, error)
Has returns true if the value at the given key is non-default, false otherwise.
func (*SparseMerkleTree) HasDescend ¶
func (smt *SparseMerkleTree) HasDescend(key []byte) (bool, error)
HasDescend returns true if the value at the given key is non-default, false otherwise. Use if a key was _not_ previously added with AddBranch, otherwise use Has. Errors if the key cannot be reached by descending.
func (*SparseMerkleTree) Prove ¶
func (smt *SparseMerkleTree) Prove(key []byte) (SparseMerkleProof, error)
Prove generates a Merkle proof for a key against the current root.
This proof can be used for read-only applications, but should not be used if the leaf may be updated (e.g. in a state transition fraud proof). For updatable proofs, see ProveUpdatable.
func (*SparseMerkleTree) ProveCompact ¶
func (smt *SparseMerkleTree) ProveCompact(key []byte) (SparseCompactMerkleProof, error)
ProveCompact generates a compacted Merkle proof for a key against the current root.
func (*SparseMerkleTree) ProveCompactForRoot ¶
func (smt *SparseMerkleTree) ProveCompactForRoot(key []byte, root []byte) (SparseCompactMerkleProof, error)
ProveCompactForRoot generates a compacted Merkle proof for a key, at a specific root.
func (*SparseMerkleTree) ProveForRoot ¶
func (smt *SparseMerkleTree) ProveForRoot(key []byte, root []byte) (SparseMerkleProof, error)
ProveForRoot generates a Merkle proof for a key, against a specific node. This is primarily useful for generating Merkle proofs for subtrees.
This proof can be used for read-only applications, but should not be used if the leaf may be updated (e.g. in a state transition fraud proof). For updatable proofs, see ProveUpdatableForRoot.
func (*SparseMerkleTree) ProveUpdatable ¶
func (smt *SparseMerkleTree) ProveUpdatable(key []byte) (SparseMerkleProof, error)
ProveUpdatable generates an updatable Merkle proof for a key against the current root.
func (*SparseMerkleTree) ProveUpdatableForRoot ¶
func (smt *SparseMerkleTree) ProveUpdatableForRoot(key []byte, root []byte) (SparseMerkleProof, error)
ProveUpdatableForRoot generates an updatable Merkle proof for a key, against a specific node. This is primarily useful for generating Merkle proofs for subtrees.
func (*SparseMerkleTree) Root ¶
func (smt *SparseMerkleTree) Root() []byte
Root gets the root of the tree.
func (*SparseMerkleTree) SetRoot ¶
func (smt *SparseMerkleTree) SetRoot(root []byte)
SetRoot sets the root of the tree.
func (*SparseMerkleTree) Update ¶
func (smt *SparseMerkleTree) Update(key []byte, value []byte) ([]byte, error)
Update sets a new value for a key in the tree, and sets and returns the new root of the tree.
func (*SparseMerkleTree) UpdateForRoot ¶
UpdateForRoot sets a new value for a key in the tree at a specific root, and returns the new root.
Source Files
Directories