smt

Documentation

Overview

Package smt implements a Sparse Merkle tree.

Index

• Variables
• func CompactProof(proof [][]byte, hasher hash.Hash, height int) ([][]byte, error)
• func DecompactProof(proof [][]byte, hasher hash.Hash, height int) ([][]byte, error)
• func VerifyCompactProof(proof [][]byte, root []byte, key []byte, value []byte, hasher hash.Hash, ...) bool
• func VerifyProof(proof [][]byte, root []byte, key []byte, value []byte, hasher hash.Hash, ...) bool
• type DeepSparseMerkleSubTree
  • func NewDeepSparseMerkleSubTree(db rollupdb.DB, hasher hash.Hash, height int, hashKey bool) *DeepSparseMerkleSubTree
  • func (dsmst *DeepSparseMerkleSubTree) AddBranches(proof [][]byte, key []byte, value []byte, updateRoot bool) ([]byte, error)
• type SparseMerkleTree
  • func NewSparseMerkleTree(db rollupdb.DB, dbNamespace []byte, hasher hash.Hash, root []byte, height int, ...) (*SparseMerkleTree, error)
  • func (smt *SparseMerkleTree) CompactProof(proof [][]byte) ([][]byte, error)
  • func (smt *SparseMerkleTree) DecompactProof(proof [][]byte) ([][]byte, error)
  • func (smt *SparseMerkleTree) Get(key []byte) ([]byte, error)
  • func (smt *SparseMerkleTree) GetForRoot(key []byte, root []byte) ([]byte, error)
  • func (smt *SparseMerkleTree) Height() int
  • func (smt *SparseMerkleTree) IsHashKey() bool
  • func (smt *SparseMerkleTree) Prove(key []byte) ([][]byte, error)
  • func (smt *SparseMerkleTree) ProveCompact(key []byte) ([][]byte, error)
  • func (smt *SparseMerkleTree) ProveCompactForRoot(key []byte, root []byte) ([][]byte, error)
  • func (smt *SparseMerkleTree) ProveForRoot(key []byte, root []byte) ([][]byte, error)
  • func (smt *SparseMerkleTree) Root() []byte
  • func (smt *SparseMerkleTree) SetRoot(root []byte)
  • func (smt *SparseMerkleTree) Update(key []byte, value []byte) ([]byte, error)
  • func (smt *SparseMerkleTree) UpdateForRoot(key []byte, value []byte, root []byte) ([]byte, error)
  • func (smt *SparseMerkleTree) VerifyCompactProof(proof [][]byte, key []byte, value []byte) bool
  • func (smt *SparseMerkleTree) VerifyProof(proof [][]byte, key []byte, value []byte) bool

Variables

var (
	DefaultValue = make([]byte, 32)
)

Functions

func CompactProof

func CompactProof(proof [][]byte, hasher hash.Hash, height int) ([][]byte, error)

CompactProof compacts a proof, to reduce its size.

func DecompactProof

func DecompactProof(proof [][]byte, hasher hash.Hash, height int) ([][]byte, error)

DecompactProof decompacts a proof, so that it can be used for VerifyProof.

func VerifyCompactProof

func VerifyCompactProof(proof [][]byte, root []byte, key []byte, value []byte, hasher hash.Hash, height int) bool

VerifyCompactProof verifies a compacted Merkle proof.

func VerifyProof

func VerifyProof(proof [][]byte, root []byte, key []byte, value []byte, hasher hash.Hash, height int) bool

VerifyProof verifies a Merkle proof.

Types

type DeepSparseMerkleSubTree

type DeepSparseMerkleSubTree struct {
	*SparseMerkleTree
}

DeepSparseMerkleSubTree is a deep Sparse Merkle subtree for working on only a few leafs.

func NewDeepSparseMerkleSubTree

func NewDeepSparseMerkleSubTree(db rollupdb.DB, hasher hash.Hash, height int, hashKey bool) *DeepSparseMerkleSubTree

NewDeepSparseMerkleSubTree creates a new deep Sparse Merkle subtree on an empty DB.

func (*DeepSparseMerkleSubTree) AddBranches

func (dsmst *DeepSparseMerkleSubTree) AddBranches(proof [][]byte, key []byte, value []byte, updateRoot bool) ([]byte, error)

AddBranches adds new branches to the tree. These branches are generated by smt.ProveForRoot, and should be verified by VerifyProof first. Set updateRoot to true if the current root of the tree should be updated.

type SparseMerkleTree

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

SparseMerkleTree is a Sparse Merkle tree.

func NewSparseMerkleTree

func NewSparseMerkleTree(db rollupdb.DB, dbNamespace []byte, hasher hash.Hash, root []byte, height int, hashKey bool) (*SparseMerkleTree, error)

NewSparseMerkleTree creates or restores a Sparse Merkle tree with a DB.

func (*SparseMerkleTree) CompactProof

func (smt *SparseMerkleTree) CompactProof(proof [][]byte) ([][]byte, error)

func (*SparseMerkleTree) DecompactProof

func (smt *SparseMerkleTree) DecompactProof(proof [][]byte) ([][]byte, error)

func (*SparseMerkleTree) Get

func (smt *SparseMerkleTree) Get(key []byte) ([]byte, error)

Get gets a key from the tree.

func (*SparseMerkleTree) GetForRoot

func (smt *SparseMerkleTree) GetForRoot(key []byte, root []byte) ([]byte, error)

GetForRoot gets a key from the tree at a specific root.

func (*SparseMerkleTree) Height

func (smt *SparseMerkleTree) Height() int

func (*SparseMerkleTree) IsHashKey

func (smt *SparseMerkleTree) IsHashKey() bool

func (*SparseMerkleTree) Prove

func (smt *SparseMerkleTree) Prove(key []byte) ([][]byte, error)

Prove generates a Merkle proof for a key.

func (*SparseMerkleTree) ProveCompact

func (smt *SparseMerkleTree) ProveCompact(key []byte) ([][]byte, error)

ProveCompact generates a compacted Merkle proof for a key.

func (*SparseMerkleTree) ProveCompactForRoot

func (smt *SparseMerkleTree) ProveCompactForRoot(key []byte, root []byte) ([][]byte, error)

ProveCompactForRoot generates a compacted Merkle proof for a key, at a specific root.

func (*SparseMerkleTree) ProveForRoot

func (smt *SparseMerkleTree) ProveForRoot(key []byte, root []byte) ([][]byte, error)

ProveForRoot generates a Merkle proof for a key, at a specific root.

func (*SparseMerkleTree) Root

func (smt *SparseMerkleTree) Root() []byte

Root gets the root of the tree.

func (*SparseMerkleTree) SetRoot

func (smt *SparseMerkleTree) SetRoot(root []byte)

SetRoot sets the root of the tree.

func (*SparseMerkleTree) Update

func (smt *SparseMerkleTree) Update(key []byte, value []byte) ([]byte, error)

Update sets a new value for a key in the tree, returns the new root, and sets the new current root of the tree.

func (*SparseMerkleTree) UpdateForRoot

func (smt *SparseMerkleTree) UpdateForRoot(key []byte, value []byte, root []byte) ([]byte, error)

UpdateForRoot sets a new value for a key in the tree at a specific root, and returns the new root.

func (*SparseMerkleTree) VerifyCompactProof

func (smt *SparseMerkleTree) VerifyCompactProof(proof [][]byte, key []byte, value []byte) bool

func (*SparseMerkleTree) VerifyProof

func (smt *SparseMerkleTree) VerifyProof(proof [][]byte, key []byte, value []byte) bool