bsmt

package module
v0.0.9 Latest Latest
Warning

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

 Go to latest Published: Mar 12, 2023 License: MIT Imports: 13 Imported by: 0

README

zkbnb-smt

zkbnb-smt is an implementation code library based on the concept of SparseMerkleTree, which implements the concepts of data persistence and data compression.

For an overview, see the design.

Installation

go get github.com/zecrey-labs/zecrey-smt@latest

Quickstart

package main

import (
	"crypto/sha256"
	"fmt"

	bsmt "github.com/zecrey-labs/zecrey-smt"
	"github.com/zecrey-labs/zecrey-smt/database/memory"
)

func main() {
	db := memory.NewMemoryDB()
	hasher := bsmt.NewHasher(sha256.New())
	nilHash := hasher.Hash([]byte("nilHash"))
	maxDepth := uint8(8)

	smt, err := bsmt.NewBNBSparseMerkleTree(hasher, db, maxDepth, nilHash)
	if err != nil {
		fmt.Println(err)
		return
	}

	key1 := uint64(1)
	key2 := uint64(2)
	key3 := uint64(23)
	val1 := hasher.Hash([]byte("test1"))
	val2 := hasher.Hash([]byte("test2"))
	val3 := hasher.Hash([]byte("test3"))
	smt.Set(key1, val1)
	smt.Set(key2, val2)
	smt.Set(key3, val3)

	version1, err := smt.Commit(nil)
	if err != nil {
		fmt.Println(err)
		return
	}

	_, err = smt.Get(key1, &version1)
	if err != nil {
		fmt.Println(err)
		return
	}

	_, err = smt.Get(key2, &version1)
	if err != nil {
		fmt.Println(err)
		return
	}
	_, err = smt.Get(key3, &version1)
	if err != nil {
		fmt.Println(err)
		return
	}

	proof, err := smt.GetProof(key1)
	if err != nil {
		fmt.Println(err)
		return
	}
	if !smt.VerifyProof(key1, proof) {
		fmt.Println("verify proof failed")
		return
	}
}

Documentation

Index

Constants

This section is empty.

Variables

View Source 
var (
	ErrEmptyRoot = errors.New("empty root")

	ErrVersionTooOld = errors.New("the version is lower than the rollback version")

	ErrVersionTooHigh = errors.New("the version is higher than the latest version")

	ErrNodeNotFound = errors.New("tree node not found")

	ErrVersionMismatched = errors.New("the version is mismatched with the database")

	ErrUnexpected = errors.New("unexpected error")

	ErrInvalidKey = errors.New("invalid key")

	ErrInvalidDepth = errors.New("depth must be a multiple of 4")

	ErrExtendNode = errors.New("extending node error")
)

Functions

This section is empty.

Types

type BNBSparseMerkleTree 

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

func (*BNBSparseMerkleTree) Clear added in v0.0.4 

func (tree *BNBSparseMerkleTree) Clear(recentVersion *Version) (err error)

func (*BNBSparseMerkleTree) Commit 

func (tree *BNBSparseMerkleTree) Commit(recentVersion *Version) (Version, error)

func (*BNBSparseMerkleTree) Get 

func (tree *BNBSparseMerkleTree) Get(key uint64, version *Version) ([]byte, error)

func (*BNBSparseMerkleTree) GetProof 

func (tree *BNBSparseMerkleTree) GetProof(key uint64) (Proof, error)

func (*BNBSparseMerkleTree) IsEmpty 

func (tree *BNBSparseMerkleTree) IsEmpty() bool

func (*BNBSparseMerkleTree) LatestVersion 

func (tree *BNBSparseMerkleTree) LatestVersion() Version

func (*BNBSparseMerkleTree) MultiSet 

func (tree *BNBSparseMerkleTree) MultiSet(items []Item) error

MultiSet sets k,v pairs in parallel

1. generate all intermediate nodes, with lock; 2. set all leaves, without lock; 3. re-compute hash, from leaves to root

func (*BNBSparseMerkleTree) RecentVersion 

func (tree *BNBSparseMerkleTree) RecentVersion() Version

func (*BNBSparseMerkleTree) Reset 

func (tree *BNBSparseMerkleTree) Reset()

func (*BNBSparseMerkleTree) Rollback 

func (tree *BNBSparseMerkleTree) Rollback(version Version) error

func (*BNBSparseMerkleTree) Root 

func (tree *BNBSparseMerkleTree) Root() []byte

func (*BNBSparseMerkleTree) Set 

func (tree *BNBSparseMerkleTree) Set(key uint64, val []byte) error

func (*BNBSparseMerkleTree) Size 

func (tree *BNBSparseMerkleTree) Size() uint64

func (*BNBSparseMerkleTree) VerifyProof 

func (tree *BNBSparseMerkleTree) VerifyProof(key uint64, proof Proof) bool

type Hasher 

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

func NewHasherPool 

func NewHasherPool(init func() hash.Hash) *Hasher

func (*Hasher) Hash 

func (h *Hasher) Hash(inputs ...[]byte) []byte

type InternalNode 

type InternalNode []byte

type Item 

type Item struct {
	Key uint64
	Val []byte
}

type Option 

type Option func(*BNBSparseMerkleTree)

Option is a function that configures SMT.

func BatchSizeLimit 

func BatchSizeLimit(limit int) Option

func DBCacheSize 

func DBCacheSize(size int) Option

func EnableMetrics 

func EnableMetrics(metrics metrics.Metrics) Option

func GCThreshold 

func GCThreshold(threshold uint64) Option

func GoRoutinePool 

func GoRoutinePool(pool *ants.Pool) Option

func InitializeVersion 

func InitializeVersion(version Version) Option

type Proof 

type Proof [][]byte

type SparseMerkleTree 

type SparseMerkleTree interface {
	Size() uint64
	Get(key uint64, version *Version) ([]byte, error)
	Set(key uint64, val []byte) error
	MultiSet(items []Item) error
	IsEmpty() bool
	Root() []byte
	GetProof(key uint64) (Proof, error)
	VerifyProof(key uint64, proof Proof) bool
	LatestVersion() Version
	RecentVersion() Version
	Reset()
	Clear(recentVersion *Version) error
	Commit(recentVersion *Version) (Version, error)
	Rollback(version Version) error
}

func NewBNBSparseMerkleTree 

func NewBNBSparseMerkleTree(hasher *Hasher, db database.TreeDB, maxDepth uint8, nilHash []byte,
	opts ...Option) (SparseMerkleTree, error)

func NewSparseMerkleTree 

func NewSparseMerkleTree(hasher *Hasher, db database.TreeDB, maxDepth uint8, hashes [][]byte, opts ...Option) (SparseMerkleTree, error)

type StorageLeafNode 

type StorageLeafNode struct {
	Versions []*VersionInfo `rlp:"optional"`
}

type StorageTreeNode 

type StorageTreeNode struct {
	Children  [16]*StorageLeafNode `rlp:"optional"`
	Internals [14]InternalNode     `rlp:"optional"`
	Versions  []*VersionInfo       `rlp:"optional"`
	Path      uint64               `rlp:"optional"`
}

func (*StorageTreeNode) ToTreeNode 

func (node *StorageTreeNode) ToTreeNode(depth uint8, nilHashes *nilHashes, hasher *Hasher) *TreeNode

type TreeNode 

type TreeNode struct {
	Children  [16]*TreeNode
	Internals [14]InternalNode
	Versions  []*VersionInfo
	// contains filtered or unexported fields
}

func NewTreeNode 

func NewTreeNode(depth uint8, path uint64, nilHashes *nilHashes, hasher *Hasher) *TreeNode

func (*TreeNode) ComputeInternalHash 

func (node *TreeNode) ComputeInternalHash()

Recompute all internal hashes

func (*TreeNode) Copy 

func (node *TreeNode) Copy() *TreeNode

func (*TreeNode) IsTemporary 

func (node *TreeNode) IsTemporary() bool

The nodes without child data. will be extended when it needs to be searched down.

func (*TreeNode) PreviousVersion 

func (node *TreeNode) PreviousVersion() Version

PreviousVersion returns the previous version number in the current TreeNode

func (*TreeNode) Prune 

func (node *TreeNode) Prune(oldestVersion Version) uint64

func (*TreeNode) Release 

func (node *TreeNode) Release(oldestVersion Version) uint64

Release nodes that have not been updated for a long time from memory. slowing down memory usage in runtime.

func (*TreeNode) Rollback 

func (node *TreeNode) Rollback(targetVersion Version) (bool, uint64)

func (*TreeNode) Root 

func (node *TreeNode) Root() []byte

Root Get latest hash of a node

func (*TreeNode) Set 

func (node *TreeNode) Set(hash []byte, version Version)

func (*TreeNode) SetChildren 

func (node *TreeNode) SetChildren(child *TreeNode, nibble int, version Version)

func (*TreeNode) Size 

func (node *TreeNode) Size() uint64

size returns the current node size

func (*TreeNode) ToStorageTreeNode 

func (node *TreeNode) ToStorageTreeNode() *StorageTreeNode

type Version 

type Version uint64

type VersionInfo 

type VersionInfo struct {
	Ver  Version
	Hash []byte
}

Source Files

View all Source files

Directories

Path Synopsis
dbtest
leveldb
memory
redis
prometheus

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.