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.")
}
}