Documentation ¶
Overview ¶
Package statedb contains the implementation of StateDB, a database backed structure that holds the state of the blockchain indexed by version (each version corresponding to the state at each block). The StateDB holds a dynamic hierarchy of linked merkle trees starting with the mainTree on top, with the property that the keys and values of all merkle trees can be cryptographically represented by a single hash, the StateDB.Hash (which corresponds to the mainTree.Root).
Internally all subTrees of the StateDB use the same database (for views) and the same transaction (for a block update). Database prefixes are used to split the storage of each subTree while avoiding collisions. The structure of prefixes is detailed here: - subTree: `{KindID}{id}/`
- arbo.Tree: `t/`
- subTrees: `s/`
- contains any number of subTree
- nostate: `n/`
- metadata: `m/`
- versions: `v/` (only in mainTree)
- currentVersion: `current` -> {currentVersion}
- version to root: `{version}` -> `{root}`
Since the mainTree is unique and doesn't have a parent, the prefixes used in the mainTree skip the first element of the path (`{KindID}{id}/`). - Example:
- mainTree arbo.Tree: `t/`
- processTree arbo.Tree (a singleton under mainTree): `s/process/t/`
- censusTree arbo.Tree (a non-singleton under processTree): `s/process/s/census{pID}/t/` (we are using pID, the processID as the id of the subTree)
- voteTree arbo.Tree (a non-singleton under processTree): `s/process/s/vote{pID}/t/` (we are using pID, the processID as the id of the subTree)
Each tree has an associated database that can be accessed via the NoState method. These databases are auxiliary key-values that don't belong to the blockchain state, and thus any value in the NoState databases won't be reflected in the StateDB.Hash. One of the usecases for the NoState database is to store auxiliary mappings used to optimize the capacity usage of merkletrees used for zkSNARKS, where the number of levels is of critical matter. For example, we may want to build a census tree of babyjubjub public keys that will be used to prove ownership of the public key via a SNARK in order to vote. If we build the merkle tree using the public key as path, we will have an unbalanced tree which requires more levels than strictly necessary. On the other hand, if we use a sequential index as path and set the value to the public key, we achieve maximum balancing reducing the number of tree levels. But then we can't easily query for the existence of a public key in the tree to generate a proof, as it requires to know its index. In such a case, we can store the mapping of public key to index in the NoState database.
Index ¶
- Variables
- func GetUint64(v db.Reader, key []byte) (uint64, error)
- func SetUint64(u Updater, key []byte, n uint64) error
- type GetRootFn
- type SetRootFn
- type StateDB
- type TreeConfig
- type TreeNonSingletonConfig
- type TreeParams
- type TreeTx
- type TreeUpdate
- func (u *TreeUpdate) Add(key, value []byte) error
- func (u *TreeUpdate) AsTreeView() TreeViewer
- func (u *TreeUpdate) DeepAdd(key, value []byte, cfgs ...TreeConfig) error
- func (u *TreeUpdate) DeepGet(key []byte, cfgs ...TreeConfig) ([]byte, error)
- func (u *TreeUpdate) DeepSet(key, value []byte, cfgs ...TreeConfig) error
- func (u *TreeUpdate) DeepSubTree(cfgs ...TreeConfig) (treeUpdate *TreeUpdate, err error)
- func (u *TreeUpdate) Del(key []byte) error
- func (u *TreeUpdate) Dump(w io.Writer) error
- func (u *TreeUpdate) GenProof(key []byte) ([]byte, []byte, error)
- func (u *TreeUpdate) Get(key []byte) ([]byte, error)
- func (u *TreeUpdate) Import(r io.Reader) error
- func (u *TreeUpdate) Iterate(callback func(key, value []byte) bool) error
- func (u *TreeUpdate) IterateNodes(callback func(key, value []byte) bool) error
- func (u *TreeUpdate) PrintGraphviz() error
- func (u *TreeUpdate) Root() ([]byte, error)
- func (u *TreeUpdate) Set(key, value []byte) error
- func (u *TreeUpdate) Size() (uint64, error)
- func (u *TreeUpdate) SubTree(cfg TreeConfig) (treeUpdate *TreeUpdate, err error)
- type TreeView
- func (v *TreeView) DeepGet(key []byte, cfgs ...TreeConfig) ([]byte, error)
- func (v *TreeView) DeepSubTree(cfgs ...TreeConfig) (treeUpdate TreeViewer, err error)
- func (v *TreeView) Dump(w io.Writer) error
- func (v *TreeView) GenProof(key []byte) ([]byte, []byte, error)
- func (v *TreeView) Get(key []byte) ([]byte, error)
- func (*TreeView) Import(_ io.Reader) error
- func (v *TreeView) Iterate(callback func(key, value []byte) bool) error
- func (v *TreeView) IterateNodes(callback func(key, value []byte) bool) error
- func (v *TreeView) PrintGraphviz() error
- func (v *TreeView) Root() ([]byte, error)
- func (v *TreeView) Size() (uint64, error)
- func (v *TreeView) SubTree(cfg TreeConfig) (treeView TreeViewer, err error)
- type TreeViewer
- type Updater
Constants ¶
This section is empty.
Variables ¶
var ErrEmptyTree = errors.New("empty tree")
ErrEmptyTree is returned when a tree is opened for read-only but hasn't been created yet.
var ErrReadOnly = errors.New("read only")
ErrReadOnly is returned when a write operation is attempted on a db.WriteTx that we set up for read only.
Functions ¶
Types ¶
type GetRootFn ¶ added in v1.3.0
GetRootFn is a function type that takes a leaf value and returns the contained root.
type SetRootFn ¶ added in v1.3.0
SetRootFn is a function type that takes a leaf value and a root, updates the leaf value with the new root and returns it.
type StateDB ¶
type StateDB struct { NoStateWriteTx db.WriteTx NoStateReadTx db.Reader // contains filtered or unexported fields }
StateDB is a database backed structure that holds a dynamic hierarchy of linked merkle trees with the property that the keys and values of all merkle trees can be cryptographically represented by a single hash, the StateDB.Root (which corresponds to the mainTree.Root).
func NewStateDB ¶ added in v1.3.0
NewStateDB returns an instance of the StateDB.
func (*StateDB) BeginTx ¶ added in v1.3.0
BeginTx creates a new transaction for the StateDB to begin an update, with the mainTree opened for update wrapped in the returned TreeTx. You must either call treeTx.Commit or treeTx.Discard if BeginTx doesn't return an error. Calling treeTx.Discard after treeTx.Commit is ok.
func (*StateDB) Hash ¶
Hash returns the cryptographic summary of the StateDB, which corresponds to the root of the mainTree. This hash cryptographically represents the entire StateDB (except for the NoState databases).
func (*StateDB) TreeView ¶ added in v1.3.0
TreeView returns the mainTree opened at root as a TreeView for read-only. If root is nil, the last version's root is used.
type TreeConfig ¶ added in v1.3.0
type TreeConfig struct { *TreeNonSingletonConfig // contains filtered or unexported fields }
TreeConfig contains the configuration used for a subTree.
func NewTreeSingletonConfig ¶ added in v1.3.0
func NewTreeSingletonConfig(params TreeParams) TreeConfig
NewTreeSingletonConfig creates a new configuration for a singleton subTree.
func (*TreeConfig) HashFunc ¶ added in v1.3.0
func (c *TreeConfig) HashFunc() arbo.HashFunction
HashFunc returns the hashFunc set for this SubTreeSingleConfig
func (*TreeConfig) Key ¶ added in v1.3.0
func (c *TreeConfig) Key() []byte
Key returns the key used in the parent tree in which the value that contains the subTree root is stored. The key is the path of the parent leaf with the root.
type TreeNonSingletonConfig ¶ added in v1.3.0
type TreeNonSingletonConfig struct {
// contains filtered or unexported fields
}
TreeNonSingletonConfig contains the configuration used for a non-singleton subTree.
func NewTreeNonSingletonConfig ¶ added in v1.3.0
func NewTreeNonSingletonConfig(params TreeParams) *TreeNonSingletonConfig
NewTreeNonSingletonConfig creates a new configuration for a non-singleton subTree.
func (*TreeNonSingletonConfig) HashFunc ¶ added in v1.3.0
func (c *TreeNonSingletonConfig) HashFunc() arbo.HashFunction
HashFunc returns the hashFunc set for this SubTreeConfig
func (*TreeNonSingletonConfig) WithKey ¶ added in v1.3.0
func (c *TreeNonSingletonConfig) WithKey(key []byte) TreeConfig
WithKey returns a unified subTree configuration type for opening a singleton subTree that is identified by `key`. `key` is the path in the parent tree to the leaf that contains the subTree root.
type TreeParams ¶ added in v1.3.0
type TreeParams struct { // HashFunc is the hash function used in the merkle tree HashFunc arbo.HashFunction // KindID is a unique identifier that specifies what kind of tree this // is. Different kind of trees under the same parent tree must have // different KindIDs, as this parameter is used to build a disjoint // database prefix for each subTree under the same parent tree. KindID string // MaxLevels is the maximum number of merkle tree levels allowed. MaxLevels int // ParentLeafGetRoot is the function that takes a leaf value of the // parent at which this tree hangs, and returns the root of this tree. ParentLeafGetRoot GetRootFn // ParentLeafSetRoot is the function that takes a leaf value of the // parent at which this tree hangs, and updates it (returning it) with // the new root of this tree. ParentLeafSetRoot SetRootFn }
TreeParams are the parameters used in the constructor for a tree configuration.
type TreeTx ¶ added in v1.3.0
type TreeTx struct { // TreeUpdate contains the mainTree opened for updates. TreeUpdate // contains filtered or unexported fields }
TreeTx is a wrapper over TreeUpdate that includes the Commit and Discard methods to control the transaction used to update the StateDB. It contains the mainTree opened in the wrapped TreeUpdate. The TreeTx is not safe for concurrent use.
func (*TreeTx) Commit ¶ added in v1.3.0
Commit will write all the changes made from the TreeTx into the database, propagating the roots of dirtiy subTrees up to the mainTree so that a new Hash/Root (mainTree.Root == StateDB.Root) is calculated representing the state. Parameter version sets the version used to index this update (identified by the mainTree root). The specified version will be stored as the last version of the StateDB. In general, Commits should use sequential version numbers, but overwriting an existing version can be useful in some cases (for example, overwriting version 0 to setup a genesis state).
func (*TreeTx) CommitOnTx ¶ added in v1.10.0
CommitOnTx do as Commit but without committing the transaction to database. After CommitOnTx(), caller should call SaveWithoutCommit() to commit the transaction.
func (*TreeTx) Discard ¶ added in v1.3.0
func (t *TreeTx) Discard()
Discard all the changes that have been made from the TreeTx. After calling Discard, the TreeTx shouldn't no longer be used.
func (*TreeTx) SaveWithoutCommit ¶ added in v1.8.0
SaveWithoutCommit saves the changes made from the TreeTx without committing a new state. This is useful for testing purposes and for committing only nostate changes.
type TreeUpdate ¶ added in v1.3.0
type TreeUpdate struct {
// contains filtered or unexported fields
}
TreeUpdate is an opened tree that can be updated. All updates are stored in an internal transaction (shared with all the opened subTrees) and will only be committed with the TreeTx.Commit function is called. The TreeUpdate is not safe for concurrent use.
func (*TreeUpdate) Add ¶ added in v1.3.0
func (u *TreeUpdate) Add(key, value []byte) error
Add a new key-value to this tree. `key` is the path of the leaf, and `value` is the content of the leaf.
func (*TreeUpdate) AsTreeView ¶ added in v1.3.0
func (u *TreeUpdate) AsTreeView() TreeViewer
AsTreeView returns a read-only view of this subTree that fulfills the TreeViewer interface.
func (*TreeUpdate) DeepAdd ¶ added in v1.3.0
func (u *TreeUpdate) DeepAdd(key, value []byte, cfgs ...TreeConfig) error
DeepAdd allows performing an Add on a nested subTree by passing the list of tree configurations and the key, value to add on the last subTree.
func (*TreeUpdate) DeepGet ¶ added in v1.3.0
func (u *TreeUpdate) DeepGet(key []byte, cfgs ...TreeConfig) ([]byte, error)
DeepGet allows performing a Get on a nested subTree by passing the list of tree configurations and the key to get at the last subTree.
func (*TreeUpdate) DeepSet ¶ added in v1.3.0
func (u *TreeUpdate) DeepSet(key, value []byte, cfgs ...TreeConfig) error
DeepSet allows performing a Set on a nested subTree by passing the list of tree configurations and the key, value to set on the last subTree.
func (*TreeUpdate) DeepSubTree ¶ added in v1.3.0
func (u *TreeUpdate) DeepSubTree(cfgs ...TreeConfig) (treeUpdate *TreeUpdate, err error)
DeepSubTree allows opening a nested subTree by passing the list of tree configurations.
func (*TreeUpdate) Del ¶ added in v1.8.0
func (u *TreeUpdate) Del(key []byte) error
Del removes a key-value from this tree. `key` is the path of the leaf.
func (*TreeUpdate) Dump ¶ added in v1.3.0
func (u *TreeUpdate) Dump(w io.Writer) error
Dump exports all the tree leafs. Unimplemented because arbo.Tree.Dump doesn't take db.ReadTx as input.
func (*TreeUpdate) GenProof ¶ added in v1.3.0
func (u *TreeUpdate) GenProof(key []byte) ([]byte, []byte, error)
GenProof generates a proof of existence of the given key for this tree. The returned values are the leaf value and the proof itself.
func (*TreeUpdate) Get ¶ added in v1.3.0
func (u *TreeUpdate) Get(key []byte) ([]byte, error)
Get returns the value at key in this tree. `key` is the path of the leaf, and the returned value is the leaf's value.
func (*TreeUpdate) Import ¶ added in v1.3.0
func (u *TreeUpdate) Import(r io.Reader) error
Import writes the content exported with Dump. TODO: use io.Reader once implemented in Arbo.
func (*TreeUpdate) Iterate ¶ added in v1.3.0
func (u *TreeUpdate) Iterate(callback func(key, value []byte) bool) error
Iterate iterates over all leafs of this tree. When callback returns true, the iteration is stopped and this function returns.
func (*TreeUpdate) IterateNodes ¶ added in v1.3.0
func (u *TreeUpdate) IterateNodes(callback func(key, value []byte) bool) error
IterateNodes iterates over all nodes of this tree. The key and value are the Arbo database representation of a node, and don't match the key value used in Get, Add and Set.
func (*TreeUpdate) PrintGraphviz ¶ added in v1.9.0
func (u *TreeUpdate) PrintGraphviz() error
PrintGraphviz prints the tree in Graphviz format.
func (*TreeUpdate) Root ¶ added in v1.3.0
func (u *TreeUpdate) Root() ([]byte, error)
Root returns the root of the tree, which cryptographically summarises the state of the tree.
func (*TreeUpdate) Set ¶ added in v1.3.0
func (u *TreeUpdate) Set(key, value []byte) error
Set adds or updates a key-value in this tree. `key` is the path of the leaf, and `value` is the content of the leaf.
func (*TreeUpdate) Size ¶ added in v1.3.0
func (u *TreeUpdate) Size() (uint64, error)
Size returns the number of leafs (key-values) that this tree contains.
func (*TreeUpdate) SubTree ¶ added in v1.3.0
func (u *TreeUpdate) SubTree(cfg TreeConfig) (treeUpdate *TreeUpdate, err error)
SubTree is used to open the subTree (singleton and non-singleton) as a TreeUpdate. The treeUpdate.tx is created from u.tx appending the prefix `subKeySubTree | cfg.prefix`. In turn the treeUpdate.tree uses the db.WriteTx from treeUpdate.tx appending the prefix `'/' | subKeyTree`.
type TreeView ¶ added in v1.3.0
type TreeView struct {
// contains filtered or unexported fields
}
TreeView is an opened tree that can only be read.
func (*TreeView) DeepGet ¶ added in v1.3.0
func (v *TreeView) DeepGet(key []byte, cfgs ...TreeConfig) ([]byte, error)
DeepGet allows performing a Get on a nested subTree by passing the list of tree configurations and the key to get at the last subTree.
func (*TreeView) DeepSubTree ¶ added in v1.3.0
func (v *TreeView) DeepSubTree(cfgs ...TreeConfig) (treeUpdate TreeViewer, err error)
DeepSubTree allows opening a nested subTree by passing the list of tree configurations.
func (*TreeView) GenProof ¶ added in v1.3.0
GenProof generates a proof of existence of the given key for this tree. The returned values are the leaf value and the proof itself.
func (*TreeView) Get ¶ added in v1.3.0
Get returns the value at key in this tree. `key` is the path of the leaf, and the returned value is the leaf's value.
func (*TreeView) Iterate ¶ added in v1.3.0
Iterate iterates over all leafs of this tree. When callback returns true, the iteration is stopped and this function returns.
func (*TreeView) IterateNodes ¶ added in v1.3.0
IterateNodes iterates over all nodes of this tree. The key and value are the Arbo database representation of a node, and don't match the key value used in Get, Add and Set. When callback returns true, the iteration is stopped and this function returns.
func (*TreeView) PrintGraphviz ¶ added in v1.3.0
func (*TreeView) Root ¶ added in v1.3.0
Root returns the root of the tree, which cryptographically summarises the state of the tree.
func (*TreeView) Size ¶ added in v1.3.0
Size returns the number of leafs (key-values) that this tree contains.
func (*TreeView) SubTree ¶ added in v1.3.0
func (v *TreeView) SubTree(cfg TreeConfig) (treeView TreeViewer, err error)
SubTree is used to open the subTree (singleton and non-singleton) as a TreeView. The treeView.db is created from v.db appending the prefix `subKeySubTree | cfg.prefix`. In turn the treeView.db uses the db.Database from treeView.db appending the prefix `'/' | subKeyTree`. The treeView.tree is opened as a snapshot from the root found in its parent leaf
type TreeViewer ¶ added in v1.3.0
type TreeViewer interface { // Get returns the value at key in this tree. `key` is the path of the leaf, // and the returned value is the leaf's value. Get(key []byte) ([]byte, error) // DeepGet allows performing a Get on a nested subTree by passing the list // of tree configurations and the key to get at the last subTree. DeepGet(key []byte, cfgs ...TreeConfig) ([]byte, error) // Iterate iterates over all leafs of this tree. When callback returns true, // the iteration is stopped and this function returns. Iterate(callback func(key, value []byte) bool) error // Dump exports all the tree leafs into a writer buffer. The leaves can be read // again via Import. Dump(w io.Writer) error // Import reads exported tree leaves from r. Import(r io.Reader) error /// Root returns the root of the tree, which cryptographically summarises the // state of the tree. Root() ([]byte, error) // Size returns the number of leafs (key-values) that this tree contains. Size() (uint64, error) // GenProof generates a proof of existence of the given key for this tree. The // returned values are the leaf value and the proof itself. GenProof(key []byte) ([]byte, []byte, error) // SubTree is used to open the subTree (singleton and non-singleton) as a // TreeView. SubTree(c TreeConfig) (TreeViewer, error) // DeepSubTree allows opening a nested subTree by passing the list of tree // configurations. DeepSubTree(cfgs ...TreeConfig) (TreeViewer, error) PrintGraphviz() error }
TreeViewer groups the read-only methods that can be made on a subTree.