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
}

Directories

Path Synopsis

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL