smt

Documentation

Index

• func EmptyLeaf() types.Bytes32
• func GnarkRecoverRoot(api frontend.API, proof GnarkProof, leaf frontend.Variable, h hash.FieldHasher) frontend.Variable
• func GnarkVerifyMerkleProof(api frontend.API, proof GnarkProof, leaf frontend.Variable, ...)
• type Config
• type GnarkProof
• type Proof
  • func (p *Proof) RecoverRoot(conf *Config, leaf types.Bytes32) (types.Bytes32, error)
  • func (p *Proof) String() string
  • func (p *Proof) Verify(conf *Config, leaf, root types.Bytes32) bool
• type ProvedClaim
• type Tree
  • func BuildComplete(leaves []types.Bytes32, hashFunc func() hashtypes.Hasher) *Tree
  • func NewEmptyTree(conf *Config) *Tree
  • func (t *Tree) GetLeaf(pos int) (types.Bytes32, error)
  • func (t *Tree) MustGetLeaf(pos int) types.Bytes32
  • func (t *Tree) MustProve(pos int) Proof
  • func (t *Tree) Prove(pos int) (Proof, error)
  • func (t *Tree) Update(pos int, newVal types.Bytes32)

Functions

func EmptyLeaf

func EmptyLeaf() types.Bytes32

EmptyLeaf returns an empty leaf (e.g. the zero bytes value).

func GnarkRecoverRoot

func GnarkRecoverRoot(
	api frontend.API,
	proof GnarkProof,
	leaf frontend.Variable,
	h hash.FieldHasher) frontend.Variable

GnarkRecoverRoot is as [RecoverRoot] in a gnark circuit. The provided position is range-checked against the number of siblings in the Merkle proof object.

func GnarkVerifyMerkleProof

func GnarkVerifyMerkleProof(
	api frontend.API,
	proof GnarkProof,
	leaf frontend.Variable,
	root frontend.Variable,
	h hash.FieldHasher)

GnarkVerifyMerkleProof asserts the validity of a GnarkProof against a root.

Types

type Config

type Config struct {
	// HashFunc is a function returning initialized hashers
	HashFunc func() hashtypes.Hasher
	// Depth is the depth of the tree
	Depth int
}

Config specifies the parameters of the tree (choice of hash function, depth).

type GnarkProof

type GnarkProof struct {
	Path     frontend.Variable
	Siblings []frontend.Variable
}

GnarkProof mirrors Proof in a gnark circuit.

type Proof

type Proof struct {
	Path     int             `json:"leafIndex"` // Position of the leaf
	Siblings []types.Bytes32 `json:"siblings"`  // length 40
}

Proof represents a Merkle proof of membership for the Merkle-tree

func (*Proof) RecoverRoot

func (p *Proof) RecoverRoot(conf *Config, leaf types.Bytes32) (types.Bytes32, error)

RecoverRoot returns the root recovered from the Merkle proof.

func (*Proof) String

func (p *Proof) String() string

String pretty-prints a proof

func (*Proof) Verify

func (p *Proof) Verify(conf *Config, leaf, root types.Bytes32) bool

Verify the Merkle-proof against a hash and a root

type ProvedClaim

type ProvedClaim struct {
	Proof      Proof
	Root, Leaf types.Bytes32
}

ProvedClaim is the composition of a proof with the claim it proves.

type Tree

type Tree struct {
	// Config of the hash function
	Config *Config
	// Root stores the root of the tree
	Root types.Bytes32
	// OccupiedLeaves continuously list of the occupied leaves. For the toy
	// implementation we track all the leaves.
	OccupiedLeaves []types.Bytes32
	// Occupied not stores all the node with a non-trivial value in the tree.
	//
	// Does not include the root. (So there are 39 levels and not 40).
	// Returns a node at a given level:
	// 	- 0 is the level just above the leaves
	// 	- 38 is the level just below the root
	OccupiedNodes [][]types.Bytes32
	// EmptyNodes stores the value of the trivial nodes of the SMT (i.e the one
	// corresponding to empty sub-trees).
	//
	// It does not include the "empty root" nor the empty leaf
	// so the first position contains the empty node for the level one.
	// So there are 39, and not 40 levels. That way, the indexing stays
	// consistent with "OccupiedNode"
	EmptyNodes []types.Bytes32
}

Tree represents a binary sparse Merkle-tree (SMT).

func BuildComplete

func BuildComplete(leaves []types.Bytes32, hashFunc func() hashtypes.Hasher) *Tree

BuildComplete builds from scratch a complete Merkle-tree. Requires that the input leaves are powers of 2. The depth of the tree is deduced from the list.

It panics if the number of leaves is a non-power of 2.

func NewEmptyTree

func NewEmptyTree(conf *Config) *Tree

NewEmptyTree creates and returns an empty tree with the provided config.

func (*Tree) GetLeaf

func (t *Tree) GetLeaf(pos int) (types.Bytes32, error)

GetLeaf returns a leaf by position or an error if the leaf is out of bounds.

func (*Tree) MustGetLeaf

func (t *Tree) MustGetLeaf(pos int) types.Bytes32

MustGetLeaf is as Tree.GetLeaf but panics on errors.

func (*Tree) MustProve

func (t *Tree) MustProve(pos int) Proof

MustProve runs Tree.Prove and panics on error

func (*Tree) Prove

func (t *Tree) Prove(pos int) (Proof, error)

Prove returns a Merkle proof of membership of the leaf at position `pos` and an error if the position is out of bounds.

func (*Tree) Update

func (t *Tree) Update(pos int, newVal types.Bytes32)

Update overwrites a leaf in the tree and updates the associated parent nodes.