censustree

Documentation

Index

• Constants
• func DeleteCensusTreeFromDatabase(kv db.Database, name string) (int, error)
• type Options
• type Tree
  • func New(opts Options) (*Tree, error)
  • func (t *Tree) Add(key, value []byte) error
  • func (t *Tree) AddBatch(keys, values [][]byte) ([]int, error)
  • func (t *Tree) BigIntToBytes(b *big.Int) []byte
  • func (*Tree) BytesToBigInt(data []byte) *big.Int
  • func (t *Tree) Close() error
  • func (t *Tree) Dump() ([]byte, error)
  • func (t *Tree) FromRoot(root []byte) (*Tree, error)
  • func (t *Tree) GenProof(key []byte) ([]byte, []byte, error)
  • func (t *Tree) Get(key []byte) ([]byte, error)
  • func (t *Tree) GetCensusWeight() (*big.Int, error)
  • func (t *Tree) Hash(data []byte) ([]byte, error)
  • func (t *Tree) ImportDump(b []byte) error
  • func (t *Tree) IterateLeaves(callback func(key, value []byte) bool) error
  • func (t *Tree) Root() ([]byte, error)
  • func (t *Tree) Size() (uint64, error)
  • func (t *Tree) Type() models.Census_Type
  • func (t *Tree) VerifyProof(key, value, proof, root []byte) (bool, error)

Constants

const DefaultMaxKeyLen = DefaultMaxLevels / 8

DefaultMaxKeyLen is the maximum length of a census tree key is defined by the number of levels of the census tree. It is the number of bytes that can fit into 'n' bits, where 'n' is the number of levels of the census tree.

const DefaultMaxLevels = 160

DefaultMaxLevels is by default, the maximum number of levels will be 160, which allows to add up to 2^160 leaves to the tree, with keys with up to 20 bytes. However the number of levels could be set up during the tree initialization which allows to support uses cases with specific restrictions such as the zkweighted census, which needs to optimize some artifacts size that depends of the number of levels of the tree.

Functions

func DeleteCensusTreeFromDatabase

func DeleteCensusTreeFromDatabase(kv db.Database, name string) (int, error)

DeleteCensusTreeFromDatabase removes all the database entries for the census identified by name. Caller must take care of potential data races, the census must be closed before calling this method. Returns the number of removed items.

Types

type Options

type Options struct {
	// ParentDB is the Database under which all censuses are stored, each
	// with a different prefix.
	ParentDB   db.Database
	Name       string
	MaxLevels  int
	CensusType models.Census_Type
}

type Tree

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

Tree implements the Merkle Tree used for census Concurrent updates to the tree.Tree can lead to losing some of the updates, so we don't expose the tree.Tree directly, and lock it in every method that updates it.

func New

func New(opts Options) (*Tree, error)

New returns a new Tree, if there already is a Tree in the database, it will load it.

func (*Tree) Add

func (t *Tree) Add(key, value []byte) error

Add adds a new key and value to the census merkle tree. The key must ideally be hashed with the tree function. If not, caller must ensure the key is inside the hashing function field. The value is considered the weight for the voter. So a serialized big.Int() is expected. Value must be inside the hashing function field too. If the census is indexed (indexAsKeysCensus), the value must be nil.

func (*Tree) AddBatch

func (t *Tree) AddBatch(keys, values [][]byte) ([]int, error)

AddBatch wraps t.tree.AddBatch while acquiring the lock.

func (*Tree) BigIntToBytes

func (t *Tree) BigIntToBytes(b *big.Int) []byte

BigIntToBytes marshals a bigInt following the censusTree encoding rules

func (*Tree) BytesToBigInt

func (*Tree) BytesToBigInt(data []byte) *big.Int

BytesToBigInt unmarshals a slice of bytes into a bigInt following the censusTree encoding rules

func (*Tree) Close

func (t *Tree) Close() error

Close closes the database for the tree.

func (*Tree) Dump

func (t *Tree) Dump() ([]byte, error)

Dump wraps t.tree.Dump.

func (*Tree) FromRoot

func (t *Tree) FromRoot(root []byte) (*Tree, error)

FromRoot returns a new read-only Tree for the given root, that uses the same underlying db.

func (*Tree) GenProof

func (t *Tree) GenProof(key []byte) ([]byte, []byte, error)

GenProof generates a census proof for the provided key. The returned values are `value` and `siblings`. If the census is indexed, value will be equal to key.

func (*Tree) Get

func (t *Tree) Get(key []byte) ([]byte, error)

Get wraps tree.Tree.Get.

func (*Tree) GetCensusWeight

func (t *Tree) GetCensusWeight() (*big.Int, error)

GetCensusWeight returns the current weight of the census.

func (*Tree) Hash

func (t *Tree) Hash(data []byte) ([]byte, error)

Hash executes the tree hash function for input data and returns its output

func (*Tree) ImportDump

func (t *Tree) ImportDump(b []byte) error

ImportDump wraps t.tree.ImportDump while acquiring the lock.

func (*Tree) IterateLeaves

func (t *Tree) IterateLeaves(callback func(key, value []byte) bool) error

IterateLeaves wraps t.tree.IterateLeaves.

func (*Tree) Root

func (t *Tree) Root() ([]byte, error)

Root wraps tree.Tree.Root.

func (*Tree) Size

func (t *Tree) Size() (uint64, error)

Size returns the census index (number of added leafs to the merkle tree).

func (*Tree) Type

func (t *Tree) Type() models.Census_Type

Type returns the numeric identifier of the censustree implementation

func (*Tree) VerifyProof

func (t *Tree) VerifyProof(key, value, proof, root []byte) (bool, error)

VerifyProof verifies a census proof. If the census is indexed key can be nil (value provides the key already). If root is nil the last merkle root is used for verify.