trie

package
v0.5.0 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Mar 23, 2021 License: MIT, MIT Imports: 11 Imported by: 0

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
usage

the following piece of example code shows how to setup an instance of badger db, a new sparse merkle tree with that database, and how to commit new data to it

dbPath := path.Join(".db", "db")
if _, err := os.Stat(dbPath); os.IsNotExist(err) {
    _ = os.MkdirAll(dbPath, 0711)
}
st := NewDB(dbPath)

smt := NewSMT(nil, Hasher, st)
keys := getFreshData(32, 32)
values := getFreshData(32, 32)
smt.Update(keys, values)
smt.Commit()

in that example, the getFreshData function returns 32 byte slices that are each contain 32 bytes, so 32 keys and values are added to the sparse merkle tree. instead of a badgerdb instance, there is also an in memory options which stores keys and values with a map data structure

dbPath := path.Join(".db", "db")
if _, err := os.Stat(dbPath); os.IsNotExist(err) {
    _ = os.MkdirAll(dbPath, 0711)
}
st := NewMemoryDB(dbPath)

additionally, there is an option to use an unmanaged version of badgerdb, if you would like to use your own instance without the default option which comes with a predefined setup and garbage collection. the following is an example of how you could create a sparse merkle tree with the unmanaged badgerdb

func getPrefix() []byte {
    return []byte {3,5}
}

dbPath := path.Join(".db", "db")
if _, err := os.Stat(dbPath); os.IsNotExist(err) {
    _ = os.MkdirAll(dbPath, 0711)
}

opts := badger.DefaultOptions(dir)
db, err := badger.Open(opts)
if err != nil {
	return nil, err
}

st := NewUnmanagedBadgerDB(dbPath, db, getPrefix)

smt := NewSMT(nil, Hasher, st)

in that example, you are free to change how you get your *badger.DB object and the prefix function. the prefix function will allow you to segregate the data in this tree from other data in the database. once you have a sparse merkle tree object, you can create merkle proofs and verify them. the following example shows one way you could do this

val, err := smt.Get(keys[0])
if err != nil {
    log.Fatal(err)
}

bitset, mp, err := smt.MerkleProofCompressed(keys[0])
if err != nil {
    log.Fatal(err)
}

result := smt.VerifyMerkleProofCompressed(bitset, mp, keys[0], val)

Documentation

Index

Constants

This section is empty.

Variables

View Source 
var (
	// DefaultLeaf is the value that may be passed to Update in order to delete
	// a key from the database.
	DefaultLeaf = Hasher([]byte{0})
)
View Source 
var ErrCBDone = errors.New("cb done with iteration")

ErrCBDone should be passed up from the callback to walkNodes when the iteration will stop.

Functions

func GetFreshData 

func GetFreshData(size, length int) [][]byte

GetFreshData gets size number of byte slice where each slice should have a length of length

func GetFreshDataUnsorted 

func GetFreshDataUnsorted(size, length int) [][]byte

GetFreshDataSorted gets size number of byte slice where each slice should have a length of length

func GetNodeDB 

func GetNodeDB(txn *badger.Txn, prefix []byte, key []byte) ([]byte, error)

func Hasher 

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

Hasher is a default hasher to use and calls the hash function defined in our crypto library. It has 32 byte (256 bit) output.

Types

type DataArray 

type DataArray [][]byte

DataArray is 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 [constants.HashLen]byte

Hash is used to convert a hash into a byte array

type LeafNode 

type LeafNode struct {
	Key   []byte
	Value []byte
}

type MemoryTrie 

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

func NewMemoryTrie 

func NewMemoryTrie() *MemoryTrie

func (*MemoryTrie) Update 

func (mt *MemoryTrie) Update(keys, values [][]byte) ([]byte, error)

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
	// contains filtered or unexported fields
}

SMT is a sparse Merkle tree.

func NewSMT 

func NewSMT(root []byte, hash func(data ...[]byte) []byte, prefixFunc func() []byte) *SMT

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

func NewSMTForHeight 

func NewSMTForHeight(txn *badger.Txn, height uint32, hash func(data ...[]byte) []byte, prefixFunc func() []byte) (*SMT, error)

func (*SMT) Commit 

func (s *SMT) Commit(txn *badger.Txn, height uint32) ([]byte, error)

Commit stores the updated nodes to disk Commit should be called for every block

func (*SMT) Discard 

func (s *SMT) Discard()

Discard rolls back the changes made by previous updates made without commit

func (*SMT) Drop 

func (s *SMT) Drop(bDB *badger.DB) error

Drop will drop all data associated with this trie from the database.

func (*SMT) FinalizeSnapShotRoot 

func (s *SMT) FinalizeSnapShotRoot(txn *badger.Txn, root []byte, height uint32) error

func (*SMT) Get 

func (s *SMT) Get(txn *badger.Txn, key []byte) ([]byte, error)

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

func (*SMT) Height 

func (s *SMT) Height(txn *badger.Txn) (uint32, error)

Height returns the number of times commit has been called on this trie

func (*SMT) MerkleProof 

func (s *SMT) MerkleProof(txn *badger.Txn, key []byte) ([][]byte, bool, []byte, []byte, error)

MerkleProof generates a Merkle proof of inclusion or non-inclusion for the current trie root returns the audit path, bool (key included), key, value, error (key,value) can be 1- (nil, value), value of the included key, 2- the kv of a LeafNode on the path of the non-included key, 3- (nil, nil) for a non-included key with a DefaultLeaf on the path

func (*SMT) MerkleProofCompressed 

func (s *SMT) MerkleProofCompressed(txn *badger.Txn, key []byte) ([]byte, [][]byte, int, bool, []byte, []byte, error)

MerkleProofCompressed returns a compressed merkle proof

func (*SMT) MerkleProofCompressedR 

func (s *SMT) MerkleProofCompressedR(txn *badger.Txn, key, root []byte) ([]byte, [][]byte, int, bool, []byte, []byte, error)

MerkleProofCompressedR returns a compressed merkle proof in the given trie

func (*SMT) MerkleProofR 

func (s *SMT) MerkleProofR(txn *badger.Txn, key, root []byte) ([][]byte, bool, []byte, []byte, error)

MerkleProofR generates a Merkle proof of inclusion or non-inclusion for a given past trie root returns the audit path, bool (key included), key, value, error (key,value) can be 1- (nil, value), value of the included key, 2- the kv of a LeafNode on the path of the non-included key, 3- (nil, nil) for a non-included key with a DefaultLeaf on the path

func (*SMT) SnapShot 

func (s *SMT) SnapShot(txn *badger.Txn, snapShotPrefix func() []byte) (*SMT, error)

SnapShot allows the state of the database to be copied into a different prefix. This function will return that copy as an SMT object to the caller.

func (*SMT) StoreSnapShotNode 

func (s *SMT) StoreSnapShotNode(txn *badger.Txn, batch []byte, root []byte, layer int) ([][]byte, int, []LeafNode, error)

func (*SMT) Update 

func (s *SMT) Update(txn *badger.Txn, 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 committed. 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) VerifyInclusion 

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

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

func (*SMT) VerifyInclusionC 

func (s *SMT) VerifyInclusionC(bitmap, key, value []byte, ap [][]byte, length int) bool

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

func (*SMT) VerifyInclusionCR 

func (s *SMT) VerifyInclusionCR(root []byte, bitmap, key, value []byte, ap [][]byte, length int) bool

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

func (*SMT) VerifyNonInclusion 

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

VerifyNonInclusion verifies a proof of non inclusion, Returns true if the non-inclusion is verified

func (*SMT) VerifyNonInclusionC 

func (s *SMT) VerifyNonInclusionC(ap [][]byte, length int, bitmap, key, value, proofKey []byte) bool

VerifyNonInclusionC verifies a proof of non inclusion, Returns true if the non-inclusion is verified

Source Files

View all Source files

Directories

Path Synopsis

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.