README
¶
Sparse Merkle Tree
A performance oriented implementation of a binary SMT with parallel update, node batching and storage shortcuts.
Details of the SMT implementation : https://medium.com/@ouvrard.pierre.alain/sparse-merkle-tree-86e6e2fc26da
Features
- Efficient Merkle proof verification (binary tree structure)
- Compressed Merkle proofs
- Efficient database reads and storage (node batching)
- Reduced data storage (shortcut nodes for subtrees containing one key)
- Simultaneous update of multiple keys with goroutines
Related
Check also the state-tools
Documentation
¶
Index ¶
- Constants
- Variables
- func Hasher(data ...[]byte) []byte
- type CacheDB
- type DataArray
- type Hash
- type SMT
- func (s *SMT) AtomicUpdate(keys, values [][]byte) ([]byte, error)
- func (s *SMT) CheckRoot(root []byte) bool
- func (s *SMT) Commit() error
- func (s *SMT) DefaultHash(height int) []byte
- func (s *SMT) Get(key []byte) ([]byte, error)
- func (s *SMT) MerkleProof(key []byte) ([][]byte, error)
- func (s *SMT) MerkleProofCompressed(key []byte) ([]byte, [][]byte, error)
- func (s *SMT) MerkleProofCompressed2(key []byte) ([]byte, [][]byte, error)
- func (s *SMT) Revert(toOldRoot []byte) error
- func (s *SMT) Stash()
- func (s *SMT) Update(keys, values [][]byte) ([]byte, error)
- func (s *SMT) VerifyMerkleProof(ap [][]byte, key, value []byte) bool
- func (s *SMT) VerifyMerkleProofCompressed(bitmap []byte, ap [][]byte, key, value []byte) bool
Constants ¶
const (
HashLength = 32
)
Variables ¶
var ( // Trie default value : hash of 0x0 DefaultLeaf = Hasher([]byte{0x0}) )
Functions ¶
Types ¶
type Hash ¶
type Hash [HashLength]byte
type SMT ¶
type SMT struct {
// Root is the current root of the smt.
Root []byte
// TrieHeight is the number if bits in a key
TrieHeight int
// LoadDbCounter counts the nb of db reads in on update
LoadDbCounter int
// LoadCacheCounter counts the nb of cache reads in on update
LoadCacheCounter int
// CacheHeightLimit is the number of tree levels we want to store in cache
CacheHeightLimit int
// contains filtered or unexported fields
}
SMT is a sparse Merkle tree.
func (*SMT) AtomicUpdate ¶
AtomicUpdate can be called multiple times and all the updated nodes will be commited and roots will be stored in past tries. Can be used for updating several blocks before committing to DB.
func (*SMT) Commit ¶
Commit stores the updated nodes to disk Commit should be called for every block otherwise past tries are not recorded and it is not possible to revert to them
func (*SMT) DefaultHash ¶
DefaultHash is a getter for the defaultHashes array
func (*SMT) MerkleProof ¶
MerkleProof creates a merkle proof for a key in the latest trie A non inclusion proof is a proof to a default value
func (*SMT) MerkleProofCompressed ¶
MerkleProofCompressed returns a compressed merkle proof. The proof contains a bitmap of non default hashes and the non default hashes.
func (*SMT) MerkleProofCompressed2 ¶
MerkleProofCompressed2 returns a compressed merkle proof like MerkleProofCompressed This version 1st calls MerkleProof and then removes the default nodes.
func (*SMT) Revert ¶
Revert rewinds the state tree to a previous version All the nodes (subtree roots and values) reverted are deleted from the database.
func (*SMT) Stash ¶
func (s *SMT) Stash()
Stash rolls back the changes made by previous updates made without commit and loads the cache from before the rollback.
func (*SMT) Update ¶
Update adds a sorted list of keys and their values to the trie If Update is called multiple times, only the state after the last update is commited. When calling Update multiple times without commit, make sure the values of different keys are unique(hash contains the key for example) otherwise some subtree may get overwritten with the wrong hash.
func (*SMT) VerifyMerkleProof ¶
VerifyMerkleProof verifies that key/value is included in the trie with latest root
Source Files