merkle

Documentation

Index

• func MerkleProofCheck(comp *wizard.CompiledIOP, name string, depth, numProofs int, ...)
• func MerkleProofCheckWithReuse(comp *wizard.CompiledIOP, name string, depth, numProofs int, ...)
• func PackMerkleProofs(proofs []smt.Proof) smartvectors.SmartVector
• type ComputeMod
  • func (cm *ComputeMod) Define(comp *wizard.CompiledIOP, round int, name string, numProofs, depth int)
• type ResultMod
  • func (rm *ResultMod) Define(comp *wizard.CompiledIOP, round int, name string, numProofs int, depth int, ...)

Functions

func MerkleProofCheck

func MerkleProofCheck(

	comp *wizard.CompiledIOP,

	name string,

	depth, numProofs int,

	proofs, roots, leaves, pos ifaces.Column,
)

The default function to be used in the self recursion and other places

func MerkleProofCheckWithReuse

func MerkleProofCheckWithReuse(

	comp *wizard.CompiledIOP,

	name string,

	depth, numProofs int,

	proofs, roots, leaves, pos, UseNextMerkleProof, IsActive, counter ifaces.Column,
)

func PackMerkleProofs

func PackMerkleProofs(proofs []smt.Proof) smartvectors.SmartVector

pack a list of merkle-proofs into a single vector

Types

type ComputeMod

type ComputeMod struct {

	// Number of rows in the module
	NumRows int
	// Number of proofs
	NumProofs int
	// Depth of the proof
	Depth int
	// Name if the name of parent context joined with a specifier.
	Name string
	// Round of the module
	Round int

	// Columns of the modules
	Cols struct {
		// IsInactive is a flags used to detect when a column
		// is not used
		IsInactive ifaces.Column
		// NewProof is a flag indicating that a new proof is
		// being verified
		NewProof ifaces.Column
		// IsEndOfProof is a flag indicating that this is the
		// last row to verify of a proof and that the NodeHash
		// field contains the computed root.
		IsEndOfProof ifaces.Column
		// Root that contains the leaf of the current proof
		Root ifaces.Column
		// Curr contains the current node to be hashes
		Curr ifaces.Column
		// Columns containing the Merkle proof
		Proof ifaces.Column
		// PosBit, indicates whether the current nodes is left
		// or right
		PosBit ifaces.Column
		// PosAcc recomputes the leaf position from the pos-bits
		PosAcc ifaces.Column
		// Zero is a dummy column containing the constant zero
		Zero ifaces.Column
		// Left contains the leftmost node of the current level
		Left ifaces.Column
		// Right contains the rightmost node of the current level
		Right ifaces.Column
		// Interm contains the intermediate hasher state after
		// hashing Left and before hashing Right.
		Interm ifaces.Column
		// NodeHash contains the hash of the parent node.
		NodeHash ifaces.Column
		// UseNextMerkleProof has a special structure when we want to reuse the next Merkle proof
		// and check if two contiguous Merkle proofs are from the same Merkle tree. It is alternatively 1 or 0
		// in a particular segment strating from 1.
		UseNextMerkleProof ifaces.Column
		// The depth expanded version of UseNextMerkleProof is used in the query
		UseNextMerkleProofExpanded ifaces.Column
		// Denote the active part of the accumultor
		IsActiveAccumulator ifaces.Column
		// The depth expanded version of IsActiveAccumulator is used in the query
		IsActiveExpanded ifaces.Column
		// SegmentCounter is constant in a particular proof segment and
		// increases by 1 in the next segment. It is an optonal column when reuse of Merkle proof
		// is verified by the accumulator module
		SegmentCounter ifaces.Column
	}
	// Expressions required to write the queries of the module
	SugarVar struct {
		// NotNewProof = 1 - NewProof
		NotNewProof *symbolic.Expression
		// IsActive = 1 - IsInactive
		IsActive *symbolic.Expression
		// Variables needed for normal Merkle proof verification
		EndOfProof, NewProof, IsInactive, NotEndOfProof *symbolic.Expression
	}
	// contains filtered or unexported fields
}

ComputeMod defines by the modules whose responsibility is to recompute the Merkle root from the Merkle proofs.

func (*ComputeMod) Define

func (cm *ComputeMod) Define(comp *wizard.CompiledIOP, round int, name string, numProofs, depth int)

Declare all the columns of the module. Assumes that Proof as been assigned to the module. Also registers all the constraints

type ResultMod

type ResultMod struct {

	// Number of rows in the module
	NumRows int
	// Number of proofs
	NumProofs int
	// Name if the name of parent context joined with a specifier.
	Name string
	// Round of the module
	Round int
	// Depth of the proof
	Depth int

	// Leaf contains the alleged leaves
	Leaf ifaces.Column
	// Roots contains the Merkle roots
	Roots ifaces.Column
	// Pos contains the positions of the alleged leaves
	Pos ifaces.Column
	// Use for looking up and selecting only the
	// the columns containing the root in the ComputeMod
	IsActive ifaces.Column
	// Column used to verify reuse of Merkle proofs
	UseNextMerkleProof ifaces.Column
	// Column to verify the sequentiality of Merkle proofs
	Counter ifaces.Column
	// contains filtered or unexported fields
}

Module summarizing the Merkle proof claims

func (*ResultMod) Define

func (rm *ResultMod) Define(comp *wizard.CompiledIOP, round int, name string, numProofs int, depth int, useNextMerkleProof ifaces.Column, isActive ifaces.Column, counter ifaces.Column)

Registers all the columns also assumes that Leaf, Roots and Pos have been passed already.