trie

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
  • func (d DataArray) Len() int
  • func (d DataArray) Less(i, j int) bool
  • func (d DataArray) Swap(i, j int)
• type Hash
• type SMT
  • func NewSMT(root []byte, hash func(data ...[]byte) []byte, store db.DB) *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

func Hasher

func Hasher(data ...[]byte) []byte

Types

type CacheDB

type CacheDB struct {
	// contains filtered or unexported fields
}

type DataArray

type DataArray [][]byte

for sorting

func (DataArray) Len

func (d DataArray) Len() int

func (DataArray) Less

func (d DataArray) Less(i, j int) bool

func (DataArray) Swap

func (d DataArray) Swap(i, j int)

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 NewSMT

func NewSMT(root []byte, hash func(data ...[]byte) []byte, store db.DB) *SMT

NewSMT creates a new SMT given a keySize and a hash function.

func (*SMT) AtomicUpdate

func (s *SMT) AtomicUpdate(keys, values [][]byte) ([]byte, error)

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) CheckRoot

func (s *SMT) CheckRoot(root []byte) bool

CheckRoot returns true if the root exists in Database.

func (*SMT) Commit

func (s *SMT) Commit() error

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

func (s *SMT) DefaultHash(height int) []byte

DefaultHash is a getter for the defaultHashes array

func (*SMT) Get

func (s *SMT) Get(key []byte) ([]byte, error)

Get fetches the value of a key by going down the current trie root.

func (*SMT) MerkleProof

func (s *SMT) MerkleProof(key []byte) ([][]byte, error)

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

func (s *SMT) MerkleProofCompressed(key []byte) ([]byte, [][]byte, error)

MerkleProofCompressed returns a compressed merkle proof. The proof contains a bitmap of non default hashes and the non default hashes.

func (*SMT) MerkleProofCompressed2

func (s *SMT) MerkleProofCompressed2(key []byte) ([]byte, [][]byte, error)

MerkleProofCompressed2 returns a compressed merkle proof like MerkleProofCompressed This version 1st calls MerkleProof and then removes the default nodes.

func (*SMT) Revert

func (s *SMT) Revert(toOldRoot []byte) error

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

func (s *SMT) Update(keys, values [][]byte) ([]byte, error)

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

func (s *SMT) VerifyMerkleProof(ap [][]byte, key, value []byte) bool

VerifyMerkleProof verifies that key/value is included in the trie with latest root

func (*SMT) VerifyMerkleProofCompressed

func (s *SMT) VerifyMerkleProofCompressed(bitmap []byte, ap [][]byte, key, value []byte) bool

VerifyMerkleProofCompressed verifies that key/value is included in the trie with latest root