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(
"fmt"
"crypto/sha256"
"github.com/lazyledger/smt"
)
func main() {
// Initialise a new key-value store to store the nodes of the tree
store := smt.NewSimpleMap()
// Initialise the tree
tree := smt.NewSparseMerkleTree(store, 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.")
}
}
Future wishlist
- Garbage collection for obsolete nodes. When tree is updated, obsolete nodes are not garbage collected, and so storage growth is unbounded. This is desirable for accessing previous revisions of the tree (for example, if you need to revert to a previous block in a blockchain due to a chain reorganisation caused by the chain's consensus algorithm), but otherwise undesirable for storage size. A future wishlist item is to extend the library to allow for an optional garbage collected version of the tree, though this requires further research.
- Tree sharding to process updates in parallel. At the moment, the tree can only safely handle one update at a time. It would be desirable to shard the tree into multiple subtrees and allow parallel updates to the subtrees.
Documentation
¶
Overview ¶
Package smt implements a Sparse Merkle tree.
Index ¶
- Constants
- func VerifyCompactProof(proof SparseCompactMerkleProof, root []byte, key []byte, value []byte, ...) bool
- func VerifyProof(proof SparseMerkleProof, root []byte, key []byte, value []byte, ...) bool
- type BadProofError
- type DeepSparseMerkleSubTree
- type InvalidKeyError
- type MapStore
- type Path
- 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) GetForRoot(key []byte, root []byte) ([]byte, error)
- func (smt *SparseMerkleTree) Has(key []byte) (bool, error)
- func (smt *SparseMerkleTree) HasForRoot(key, root []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) 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 ¶
const (
PathLen = 4 // num of bytes for path, 32bit
)
Variables ¶
This section is empty.
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 BadProofError ¶
type BadProofError struct{}
BadProofError is returned when an invalid Merkle proof is supplied.
func (*BadProofError) Error ¶
func (e *BadProofError) Error() string
type DeepSparseMerkleSubTree ¶
type DeepSparseMerkleSubTree struct {
*SparseMerkleTree
}
DeepSparseMerkleSubTree is a deep Sparse Merkle subtree for working on only a few leafs.
func NewDeepSparseMerkleSubTree ¶
func NewDeepSparseMerkleSubTree(ms 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 BadProofError is returned.
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.
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
}
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
}
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(ms MapStore, hasher hash.Hash, root []byte) *SparseMerkleTree
ImportSparseMerkleTree imports a Sparse Merkle tree from a non-empty MapStore.
func NewSparseMerkleTree ¶
func NewSparseMerkleTree(ms MapStore, hasher hash.Hash) *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 a key from the tree.
func (*SparseMerkleTree) GetForRoot ¶
func (smt *SparseMerkleTree) GetForRoot(key []byte, root []byte) ([]byte, error)
GetForRoot gets a key from the tree at a specific root.
func (*SparseMerkleTree) Has ¶
func (smt *SparseMerkleTree) Has(key []byte) (bool, error)
Has returns true if tree contains given key, false otherwise.
func (*SparseMerkleTree) HasForRoot ¶
func (smt *SparseMerkleTree) HasForRoot(key, root []byte) (bool, error)
HasForRoot returns true if tree contains given key at a specific root, false otherwise.
func (*SparseMerkleTree) Prove ¶
func (smt *SparseMerkleTree) Prove(key []byte) (SparseMerkleProof, error)
Prove generates a Merkle proof for a key.
func (*SparseMerkleTree) ProveCompact ¶
func (smt *SparseMerkleTree) ProveCompact(key []byte) (SparseCompactMerkleProof, error)
ProveCompact generates a compacted Merkle proof for a key.
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, at a specific root.
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