accumulator

Documentation

Index

• Constants
• type LeafOpenings
• type Module
  • func NewModule(comp *wizard.CompiledIOP, s Settings) Module
  • func (am *Module) Assign(run *wizard.ProverRuntime, traces []statemanager.DecodedTrace)
• type Settings
  • func (s Settings) NumRows() int

Constants

const (

	// Column names
	ACCUMULATOR_PROOFS_NAME                ifaces.ColID = "ACCUMULATOR_PROOFS"
	ACCUMULATOR_ROOTS_NAME                 ifaces.ColID = "ACCUMULATOR_ROOTS"
	ACCUMULATOR_POSITIONS_NAME             ifaces.ColID = "ACCUMULATOR_POSITIONS"
	ACCUMULATOR_LEAVES_NAME                ifaces.ColID = "ACCUMULATOR_LEAVES"
	ACCUMULATOR_USE_NEXT_MERKLE_PROOF_NAME ifaces.ColID = "ACCUMULATOR_USE_NEXT_PROOF"
	ACCUMULATOR_IS_ACTIVE_NAME             ifaces.ColID = "ACCUMULATOR_IS_ACTIVE"
	// Column for checking the sequentiality of merkle proofs
	ACCUMULATOR_COUNTER_NAME ifaces.ColID = "ACCUMULATOR_COUNTER"
	// Column for local consistency check
	ACCUMULATOR_IS_FIRST_NAME         ifaces.ColID = "ACCUMULATOR_IS_FIRST"
	ACCUMULATOR_IS_INSERT_NAME        ifaces.ColID = "ACCUMULATOR_IS_INSERT"
	ACCUMULATOR_IS_DELETE_NAME        ifaces.ColID = "ACCUMULATOR_IS_DELETE"
	ACCUMULATOR_IS_UPDATE_NAME        ifaces.ColID = "ACCUMULATOR_IS_UPDATE"
	ACCUMULATOR_IS_READ_ZERO_NAME     ifaces.ColID = "ACCUMULATOR_IS_READ_ZERO"
	ACCUMULATOR_IS_READ_NON_ZERO_NAME ifaces.ColID = "ACCUMULATOR_IS_READ_NON_ZERO"
	// Columns for sandwich check
	ACCUMULATOR_HKEY_NAME       ifaces.ColID = "ACCUMULATOR_HKEY"
	ACCUMULATOR_HKEY_MINUS_NAME ifaces.ColID = "ACCUMULATOR_HKEY_MINUS"
	ACCUMULATOR_HKEY_PLUS_NAME  ifaces.ColID = "ACCUMULATOR_HKEY_PLUS"
	// Columns for pointer check
	ACCUMULATOR_LEAF_MINUS_INDEX_NAME   ifaces.ColID = "ACCUMULATOR_LEAF_MINUS_INDEX"
	ACCUMULATOR_LEAF_MINUS_NEXT_NAME    ifaces.ColID = "ACCUMULATOR_LEAF_MINUS_NEXT"
	ACCUMULATOR_LEAF_PLUS_INDEX_NAME    ifaces.ColID = "ACCUMULATOR_LEAF_PLUS_INDEX"
	ACCUMULATOR_LEAF_PLUS_PREV_NAME     ifaces.ColID = "ACCUMULATOR_LEAF_PLUS_PREV"
	ACCUMULATOR_LEAF_DELETED_INDEX_NAME ifaces.ColID = "ACCUMULATOR_LEAF_DELETED_INDEX"
	ACCUMULATOR_LEAF_DELETED_PREV_NAME  ifaces.ColID = "ACCUMULATOR_LEAF_DELETED_PREV"
	ACCUMULATOR_LEAF_DELETED_NEXT_NAME  ifaces.ColID = "ACCUMULATOR_LEAF_DELETED_NEXT"
	// Columns for leaf hash check (some more columns for this are declared below)
	ACCUMULATOR_LEAF_HASHES_NAME   ifaces.ColID = "ACCUMULATOR_LEAF_HASHES"
	ACCUMULATOR_IS_EMPTY_LEAF_NAME ifaces.ColID = "ACCUMULATOR_IS_EMPTY_LEAF"
	// Columns for NextFreeNode consistency check
	ACCUMULATOR_NEXT_FREE_NODE_NAME ifaces.ColID = "ACCUMULATOR_NEXT_FREE_NODE"
	ACCUMULATOR_INSERTION_PATH_NAME ifaces.ColID = "ACCUMULATOR_INSERTION_PATH"
	ACCUMULATOR_IS_INSERT_ROW3_NAME ifaces.ColID = "ACCUMULATOR_IS_INSERT_ROW3"
	// Columns for hashing the top root
	ACCUMULATOR_INTERM_TOP_ROOT_NAME ifaces.ColID = "ACCUMULATOR_INTERM_TOP_ROOT"
	ACCUMULATOR_TOP_ROOT_NAME        ifaces.ColID = "ACCUMULATOR_TOP_ROOT"
)

Types

type LeafOpenings

type LeafOpenings struct {
	HKey ifaces.Column
	HVal ifaces.Column
	Prev ifaces.Column
	Next ifaces.Column
}

structure for leaf opening

type Module

type Module struct {
	// The compiled IOP
	Settings

	Cols struct {
		Leaves    ifaces.Column
		Roots     ifaces.Column
		Positions ifaces.Column
		Proofs    ifaces.Column
		// Column to verify reuse of Merkle proofs in INSERT, DELETE, and UPDATE operations
		UseNextMerkleProof ifaces.Column
		// Column denoting the active area of the accumulator module
		IsActiveAccumulator ifaces.Column
		// Column to check sequentiality of the accumulator module with Merkle module
		AccumulatorCounter ifaces.Column
		// Column to verify the two equalities of intermediateRoot1 and intermediateRoot3, and empty
		// leafs for INSERT and DELETE operation and one equality of root in IsReadZero operation
		IsFirst ifaces.Column
		// Column indicating an INSERT operation
		IsInsert ifaces.Column
		// Column indicating an DELETE operation
		IsDelete ifaces.Column
		// Column indicating an UPDATE operation
		IsUpdate ifaces.Column
		// Column indicating an READ-ZERO operation
		IsReadZero ifaces.Column
		// Column indicating an READ-NONZERO operation
		IsReadNonZero ifaces.Column

		// Columns for the sandwitch check
		// Column storing the hash of the key of the trace
		HKey ifaces.Column
		// Column storing the hash of the key of the previous leaf
		HKeyMinus ifaces.Column
		// Column storing the hash of the key of the next leaf
		HKeyPlus ifaces.Column

		// Columns for the pointer check
		// Column storing the index of the minus leaf
		LeafMinusIndex ifaces.Column
		// Column storing the index of the next leaf of the minus leaf
		LeafMinusNext ifaces.Column
		// Column storing the index of the plus leaf
		LeafPlusIndex ifaces.Column
		// Column storing the index of the previous leaf of the plus leaf
		LeafPlusPrev ifaces.Column
		// Column storing the index of the deleted leaf
		LeafDeletedIndex ifaces.Column
		// Column storing the index of the previous leaf of the deleted leaf
		LeafDeletedPrev ifaces.Column
		// Column storing the index of the next leaf of the deleted leaf
		LeafDeletedNext ifaces.Column

		// Columns for leaf hashing check
		// LeafOpening contains four columns corresponding to HKey, HVal, Prev, and Next
		LeafOpenings LeafOpenings
		// Interm contains the three intermediate states corresponding to the MiMC block computation
		Interm []ifaces.Column
		// Zero contains the column with zero value, used in the MiMc query
		Zero ifaces.Column
		// LeafHash contains the leafHashes (the final MiMC block), equals with Leaves, except when it is empty leaf
		LeafHashes ifaces.Column
		// IsEmptyLeaf is one when Leaves contains empty leaf and does not match with LeafHash
		IsEmptyLeaf ifaces.Column

		// Columns to check NextFreeNode consistency
		// NextFreeNode stores the nextFreeNode for each row of every operation
		NextFreeNode ifaces.Column
		// InsertionPath stores the index of the newly inserted leaf by INSERT
		InsertionPath ifaces.Column
		// IsInsertRow3 is one for row 3 of INSERT operation
		IsInsertRow3 ifaces.Column

		// Columns for hashing the top root
		// IntermTopRoot contains the intermediate MiMC state hash
		IntermTopRoot ifaces.Column
		// TopRoot contains the MiMC hash of Roots and NextFreeNode
		TopRoot ifaces.Column
	}
	// contains filtered or unexported fields
}

Module module

func NewModule

func NewModule(comp *wizard.CompiledIOP, s Settings) Module

NewModule generates and constraints the accumulator module. The accumulator module is entrusted to check all individual Linea's state accumulator traces.

func (*Module) Assign

func (am *Module) Assign(
	run *wizard.ProverRuntime,

	traces []statemanager.DecodedTrace,
)

Assign is a high level function which is used to arithmetize the columns of the Accumulator module from a slice of decoded traces

type Settings

type Settings struct {
	// MaxNbProof is the maximum number of accumulator proofs that the accumulator
	// can verify.
	MaxNumProofs int
	// Name is a string identifying the accumulator module to construct. It is
	// not used as only one instance per Wizard exists.
	Name string
	// MerkleTreeDepth is the depth of the Merkle tree to use to construct the
	// accumulator. In production, we use a value of 40 and this should not be
	// changed as this would modify the state.
	MerkleTreeDepth int
	// Round denotes the interaction round at which the module should be
	// constructed. In production, this should always be zero.
	Round int
}

Settings collects all input parameters to dimension an Module during its construction.

func (Settings) NumRows

func (s Settings) NumRows() int

leaveSizes returns the column length for the