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.