wizard

package
v0.0.0-...-06294fd Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Jan 9, 2025 License: Apache-2.0 Imports: 23 Imported by: 0

Documentation

Overview

Package wizard provides the main structure articulating the framework. Namely, it provides the following structures:

  • Builder provides a user-friendly interface to generate a custom polynomial IOP. Note that this structure will be deprecated and the user should use instead the lower-level CompiledIOP to define its own protocol. In particular, the Builder is a wrapper around the CompiledIOP that has the capacity to auto-detect the rounds at which the "items" (i.e. the columns, queries or coins) are declared.

  • CompiledIOP stores a representation of the elaborated protocol before, during and after its compilation.

  • ProverRuntime is the entrypoint to interact with the runtime of the prover of the protocol. It is used internally as a placeholder to store the witness and is the entrypoint to specify custom prover behaviors.

  • VerifierRuntime is the entrypoint to interact with the runtime of the verifier of the protocol. It is used internally to capture all the computations and checks directly performed by the verifier

  • [GnarkVerifierRuntime] - similar to VerifierRuntime - is the entrypoint to interact with the verifier of the protocol inside a gnark circuit. It provides a way to do recursive composition of the wizard into a gnark circuit.

Here is a minimal example of the definition of a protocol to prove knowledge of the Fibonacci sequence.

``` // This function is provided to the function Compile by the user to // specify what the protocol should be. The user has access to a pallet of // different queries func defineFibo(build *wizard.Builder) { 

	// Number of rows (e.g. the size of the fibonacci sequence to prove
	// knowledge of).
	n := 1 << 3

	// This declares a column to commit to, allegedly containing the sequence.
	p1 := build.RegisterCommit(P1, n)

	// This declares a constraints that `p1` is valid fibonacci sequence:
	// in other words it enforces that p1[i] = pi[i-1] + pi[i-2]
	expr := ifaces.ColumnAsVariable(column.Shift(p1, -1)).
		Add(ifaces.ColumnAsVariable(column.Shift(p1, -2))).
		Sub(ifaces.ColumnAsVariable(p1))

	_ = build.GlobalConstraint(GLOBAL1, expr)
}

// This function is passed to the wizard and assigns the witness (namely,
// the fibonacci sequence to the above-defined `p1`). All columns defined
// in the "define" function require an explicit assignment from the user. It
// is also the case for some types of query. This is not the case here, but
// for instance, if we had declared a polynomial evaluation query, we would
// have needed to also provide an evaluation point `x` and the corresponding
// evaluation claim `y``.
func proveFibo(run *wizard.ProverRuntime) {
	x := smartvectors.ForTest(1, 1, 2, 3, 5, 8, 13, 21)
	run.AssignColumn(P1, x)
}

func TestFibo(t *testing.T) {

	// This instantiates the protocol, converting all the Wizard queries and
	// columns into a concrete protocol.
	compiled := wizard.Compile(
		defineFibo,
		compiler.Arcane(8, 8),
		vortex.Compile(2),
	)

	// This generates a proof based on the witness assigned by `proverFibo`
	proof := wizard.Prove(compiled, proveFibo)

	// This runs the verifier and returns an error if the proof was incorrect
	if err := wizard.Verify(compiled, proof); err != nil {
		panic("invalid proof")
	}
}

```

Index

Constants

This section is empty.

Variables

This section is empty.

Functions

func Verify 

func Verify(c *CompiledIOP, proof Proof) error

Verify verifies a wizard proof. The caller specifies a CompiledIOP that describes the protocol to run and a proof to verify. The function returns `nil` to indicate that the proof passed and an error to indicate the proof was invalid.

Types

type Artefact 

type Artefact interface {
	io.ReaderFrom
	io.WriterTo
}

Artefact is an ad-hoc interface characterizing serializable objects. The interface should be implemented over a pointer type as it is used for reading the object from a blob of bytes.

type Builder deprecated 

type Builder struct {
	*CompiledIOP
	// contains filtered or unexported fields
}

Builder provides the go-to user interface to specify a custom Wizard protocol. The builder is essentially a wrapper around the CompiledIOP struct and has the additional capability to track the "current" prover-verifier interaction round.

In particular, Builder provides the utilities to

  • Declare columns
  • Declare random coins
  • Declare queries

Deprecated: @alex: we should deprecate this and directly embed the "round" tracking capability within the CompiledIOP struct. The round-tracking mechanism does not allow for a smooth way to decompose the user's protocol into sub-protocols that spans on multiple rounds efficiently as a new round will be created everytime the user declares a new Coin.

func (*Builder) FixedPermutation 

func (b *Builder) FixedPermutation(name ifaces.QueryID, p []ifaces.ColAssignment, a, b_ []ifaces.Column)

Creates a fixed-permutation query. Were 'a' is the fixedpermutation of 'b' for a given-permutation p: p(a)=b, p can be deifed only by 'b' over a defult vector 'a'.

func (*Builder) GlobalConstraint 

func (b *Builder) GlobalConstraint(name ifaces.QueryID, cs_ *symbolic.Expression) query.GlobalConstraint

Create an GlobalConstraint query, returns the global constraint

func (*Builder) Inclusion 

func (b *Builder) Inclusion(name ifaces.QueryID, including, included []ifaces.Column)

Creates an inclusion query. Here, `included` and `including` are viewed as a arrays and the query asserts that `included` contains only rows that are contained within `includings`, regardless of the multiplicity.

func (*Builder) InclusionConditionalOnIncluded 

func (b *Builder) InclusionConditionalOnIncluded(name ifaces.QueryID, including, included []ifaces.Column, includedFilter ifaces.Column)

An inclusion query that adds a filter on the included array The filter should be a column that contains only field elements for 0 and 1.

func (*Builder) InclusionConditionalOnIncluding 

func (b *Builder) InclusionConditionalOnIncluding(name ifaces.QueryID, including, included []ifaces.Column, includingFilter ifaces.Column)

An inclusion query that adds a filter on the including array The filter should be a column that contains only field elements for 0 and 1.

func (*Builder) InclusionDoubleConditional 

func (b *Builder) InclusionDoubleConditional(name ifaces.QueryID, including, included []ifaces.Column, includingFilter, includedFilter ifaces.Column)

An inclusion query that adds two filters on the including and included arrays The filters should be columns that contain only field elements for 0 and 1.

func (*Builder) InnerProduct 

func (b *Builder) InnerProduct(name ifaces.QueryID, a ifaces.Column, bs ...ifaces.Column) query.InnerProduct

Create an inner-product query

func (*Builder) LocalConstraint 

func (b *Builder) LocalConstraint(name ifaces.QueryID, cs_ *symbolic.Expression) query.LocalConstraint

Create an LocalConstraint query

func (*Builder) LocalOpening 

func (b *Builder) LocalOpening(name ifaces.QueryID, pol ifaces.Column) query.LocalOpening

Create a local opening query

func (*Builder) Permutation 

func (b *Builder) Permutation(name ifaces.QueryID, a, b_ []ifaces.Column)

Creates an permutation query. The query views `a` and `b_` to be lists of columns and asserts that `a` and `b_` have the same rows (possibly in a different order) but with the same multiplicity.

func (*Builder) Range 

func (b *Builder) Range(name ifaces.QueryID, h ifaces.Column, max int)

Create a Range query

func (*Builder) RegisterCommit 

func (b *Builder) RegisterCommit(name ifaces.ColID, size int) ifaces.Column

Registers a new column in the protocol

func (*Builder) RegisterPrecomputed 

func (b *Builder) RegisterPrecomputed(name ifaces.ColID, v smartvectors.SmartVector) ifaces.Column

Registers a precomputed column in the protocol

func (*Builder) RegisterRandomCoin 

func (b *Builder) RegisterRandomCoin(name coin.Name, type_ coin.Type, size ...int) coin.Info

Asserts there will be a Fiat-Shamir hash

(for integer vec coin only, the caller must pass a slice of length 2 such that - size[0] contains the number of integers and - size[1] contains the upperBound.

func (*Builder) UnivariateEval 

func (b *Builder) UnivariateEval(name ifaces.QueryID, pols ...ifaces.Column)

Create a univariate query for a list of already registered polynomials. The witnesses here are assumed to be in COEFFICIENT FORM. It is important to note, that this function assumes that, `X`, the evaluation point is **unique** and **not known yet** (it could be a random coin challenge for instance). If you want to register a query for which the evaluation point is already known, you should use `FixedPointUnivariateEval` instead. If you would like to do a multi-evaluation instead, you need to register several queries

type ByRoundRegister 

type ByRoundRegister[ID comparable, DATA any] struct {
	// contains filtered or unexported fields
}

ByRoundRegister is a an abstract data-structure used to register the column.Natural, coin.Info and ifaces.Query etc... Each item is added at a particular round. The structure additionally records compilation informations about the objects stored in the register.

func NewRegister 

func NewRegister[ID comparable, DATA any]() ByRoundRegister[ID, DATA]

Construct a new round register

func (*ByRoundRegister[ID, DATA]) AddToRound 

func (r *ByRoundRegister[ID, DATA]) AddToRound(round int, id ID, data DATA)

Insert for a given round. Will panic if an item with the same ID has been registered first

func (*ByRoundRegister[ID, DATA]) AllKeys 

func (r *ByRoundRegister[ID, DATA]) AllKeys() []ID

Returns the list of all the keys ever. The result is returned in Deterministic order.

func (*ByRoundRegister[ID, DATA]) AllKeysAt 

func (r *ByRoundRegister[ID, DATA]) AllKeysAt(round int) []ID

Returns the list of all keys for a given round. Result has deterministic order (order of insertion)

func (*ByRoundRegister[ID, DATA]) AllUnignoredKeys 

func (s *ByRoundRegister[ID, DATA]) AllUnignoredKeys() []ID

Returns all the keys that are not marked as ignored in the structure

func (*ByRoundRegister[ID, DATA]) Data 

func (r *ByRoundRegister[ID, DATA]) Data(id ID) DATA

Returns the data for associated to an ID. Panic if not found

func (*ByRoundRegister[ID, DATA]) Exists 

func (r *ByRoundRegister[ID, DATA]) Exists(id ...ID) bool

Returns true if all the entry exist

func (*ByRoundRegister[ID, DATA]) IsIgnored 

func (r *ByRoundRegister[ID, DATA]) IsIgnored(id ID) bool

Returns if the entry is ignored. Panics if the entry is missing from the map.

func (*ByRoundRegister[ID, DATA]) IsSkippedFromProverTranscript 

func (r *ByRoundRegister[ID, DATA]) IsSkippedFromProverTranscript(id ID) bool

IsSkippedFromProverTranscript returns if the entry is skipped from the transcript. Panics if the entry is missing from the map.

func (*ByRoundRegister[ID, DATA]) IsSkippedFromVerifierTranscript 

func (r *ByRoundRegister[ID, DATA]) IsSkippedFromVerifierTranscript(id ID) bool

IsSkippedFromVerifierTranscript returns if the entry is skipped from the transcript. Panics if the entry is missing from the map.

func (*ByRoundRegister[ID, DATA]) MarkAsIgnored 

func (r *ByRoundRegister[ID, DATA]) MarkAsIgnored(id ID) bool

Marks an entry as compiled. Panic if the key is missing from the register. Returns true if the item was already ignored.

func (*ByRoundRegister[ID, DATA]) MarkAsSkippedFromProverTranscript 

func (r *ByRoundRegister[ID, DATA]) MarkAsSkippedFromProverTranscript(id ID) bool

MarkAsSkippedFromProverTranscript marks an entry as skipped from the transcript of the verifier. Panic if the key is missing from the register. Returns true if the item was already ignored.

func (*ByRoundRegister[ID, DATA]) MarkAsSkippedFromVerifierTranscript 

func (r *ByRoundRegister[ID, DATA]) MarkAsSkippedFromVerifierTranscript(id ID) bool

MarkAsSkippedFromVerifierTranscript marks an entry as skipped from the transcript of the verifier. Panic if the key is missing from the register. Returns true if the item was already ignored.

func (*ByRoundRegister[ID, DATA]) MustBeInRound 

func (r *ByRoundRegister[ID, DATA]) MustBeInRound(round int, id ID)

Panic if the name is not found at the given round

func (*ByRoundRegister[ID, DATA]) MustExists 

func (r *ByRoundRegister[ID, DATA]) MustExists(id ...ID)

Panic if the name is not found at all

func (*ByRoundRegister[ID, DATA]) NumRounds 

func (r *ByRoundRegister[ID, DATA]) NumRounds() int

Returns the number of rounds

func (*ByRoundRegister[ID, DATA]) ReserveFor 

func (r *ByRoundRegister[ID, DATA]) ReserveFor(newLen int)

Make sure enough rounds are allocated up to the given length No-op if enough rounds have been allocated, otherwise, will reserve as many as necessary.

func (*ByRoundRegister[ID, DATA]) Round 

func (r *ByRoundRegister[ID, DATA]) Round(id ID) int

Find

type CompiledIOP 

type CompiledIOP struct {

	// Columns registers and stores the Columns (ie: messages for the oracle)
	// of the protocol. This includes the committed vectors, the proof messages,
	// the preprocessed commitments that intervene in the protocol.
	Columns column.Store

	// QueriesParams registers and stores all the parametrizable queries of the
	// specified protocol. By "parametrizable", we mean the queries for which
	// the prover is required to assign runtime parameters. For instance, for
	// a univariate evaluation query : the prover is required to assign an
	// evaluation point X and and at least one evaluation claim.
	QueriesParams ByRoundRegister[ifaces.QueryID, ifaces.Query]

	// QueriesNoParams registers and stores all queries without parameters.
	// Namely, this is storing the queries for which the prover does not need
	// bring extra information at runtime. An example, is [query.GlobalConstraint]
	// which ensures that an arithmetic expression vanishes over its domain. In
	// this case, as long as the arithmetic expression is defined, there is
	// nothing to add.
	QueriesNoParams ByRoundRegister[ifaces.QueryID, ifaces.Query]

	// Coins registers and stores all the verifier's random challenge that are
	// specified in the protocol. A challenge can be either a single field
	// element, an array of field element or an array of bounded field elements.
	// The challenges can be used to specify sub-protocols and are a very
	// widespread cryptographic tool to build them.
	Coins ByRoundRegister[coin.Name, coin.Info]

	// SubProver stores all the specified steps that needs to be performed by
	// the prover as specified in the protocol. These functions are provided to
	// the user and the compilers and their role is to assign the columns and
	// parametrizable's queries parameters during the prover runtime of the
	// protocol.
	SubProvers collection.VecVec[ProverStep]

	// subVerifier stores all the steps that need to be performed by the verifier
	// explicitly. The role of the verifier function's is to implement all the
	// manual checks that the verifier has to perform. This is useful when a check
	// cannot be represented in term of query but, when possible, queries should
	// always be preferred to express a relation that the witness must satisfy.
	SubVerifiers collection.VecVec[VerifierAction]

	// FiatShamirHooks is an action that is run during the FS sampling. Compared
	// to a normal verifier action it has the possibility to interact with the
	// Fiat-Shamir state.
	FiatShamirHooks collection.VecVec[VerifierAction]

	// Precomputed stores the assignments of all the Precomputed and VerifierKey
	// polynomials. It is assigned directly when registering a precomputed
	// column.
	Precomputed collection.Mapping[ifaces.ColID, ifaces.ColAssignment]

	// PcsCtxs stores the compilation context of the last used
	// cryptographic compiler. Specifically, it is aimed to store the last
	// Vortex compilation context (see [github.com/consensys/linea-monorepo/prover/protocol/compiler]) that was used. And
	// its purpose is to provide the Vortex context to the self-recursion
	// compilation context; see [github.com/consensys/linea-monorepo/prover/protocol/compiler/selfrecursion]. This allows
	// the self-recursion context to learn about the columns to use and the
	// Vortex parameters.
	PcsCtxs any

	// DummyCompiled that can be set internally by the compilation, when we are
	// using the [github.com/consensys/linea-monorepo/prover/protocol/compiler/dummy.Compile] compilation step. This steps
	// commands that the verifier of the protocol should not be compiled into a
	// circuit. This is needed because `dummy.Compile` turns all the columns of
	// the protocol in columns that are visible to the verifier and all the
	// queries into explcit verifier checks. This can incurs a super-massive
	// amount of constraints and the flag
	DummyCompiled bool

	// SelfRecursionCount counts the number of self-recursions induced in the protocol. Used to
	// derive unique names for when the self-recursion is called several time.
	SelfRecursionCount int

	// Artefacts is a generic data-store that can be used to serialize
	// compilation data. For instance, this is used to cache the factorized
	// grand global constraint expression as the factorization is an expensive
	// process. An artefact must satisfy the io.ReadWriteTo interface.
	Artefacts artefactCache

	// FunctionalPublic inputs lists the queries representing a public inputs
	// and their identifiers
	PublicInputs []PublicInput
	// contains filtered or unexported fields
}

CompiledIOP carries a static description of the IOP protocol throughout the compilation of the protocol and after the compilation of the protocol. It collects the descriptions of the involved columns in protocol, their status and their sizes. It also registers all the random challenge coins that the verifier of the protocol is expected to send during the verification process. Additionally, the CompiledIOP object can register "queries". Queries are an indication that something is not proven yet but are expected to be justified during the compilation steps. Additionally, the compiled IOP object registers the computations of the prover and the verifier at every round of the protocol.

CompiledIOP objects should not be directly constructed by the user, which should instead implicitly construct it via the Compile function and access it via the Builder.CompiledIOP object. Namely, the zero value of the CompiledIOP does not implement anything useful.

func Compile 

func Compile(define DefineFunc, compilers ...func(*CompiledIOP)) *CompiledIOP

Compile an IOP from a protocol definition

func (*CompiledIOP) BootstrapFiatShamir 

func (comp *CompiledIOP) BootstrapFiatShamir(vm VersionMetadata, ser CompiledIOPSerializer) *CompiledIOP

BootstrapFiatShamir hashes the description of the struct to bootstrap the initial Fiat-Shamir state.

func (*CompiledIOP) GenericFragmentedConditionalInclusion 

func (c *CompiledIOP) GenericFragmentedConditionalInclusion(
	round int,
	name ifaces.QueryID,
	including [][]ifaces.Column,
	included []ifaces.Column,
	includingFilter []ifaces.Column,
	includedFilter ifaces.Column,
)

GenericFragmentedConditionalInclusion constructs a generic inclusion query where the table can possibly be fragmented in several sub-tables. The user set `includedFilter` and/or `includingFilter` to be nil if he does not wish to use a filter. For the non-fragmented case, the user can set including to have length 1 (on the left-side of the double slice).

In all cases, the provided parameters must be consistent in their length to represent a well-formed inclusion query or the function panics.

func (*CompiledIOP) GetInnerProduct deprecated 

func (run *CompiledIOP) GetInnerProduct(name ifaces.QueryID) query.InnerProduct

Get an Inner-product query

Deprecated: the user should directly grab it from the `Data` section.

func (*CompiledIOP) InsertCoin 

func (c *CompiledIOP) InsertCoin(round int, name coin.Name, type_ coin.Type, size ...int) coin.Info

Registers a new coin at a given rounds. Returns a coin.Info object.

* For normal coins, pass 

_ = c.InsertCoin(<round of sampling>, <stringID of the coin>, coin.Field)

* For IntegerVec coins, pass 

_ = c.InsertCoin(<round of sampling>, <stringID of the coin>, coin.IntegerVec, <#Size of the vec>, <#Bound on the integers>)

func (*CompiledIOP) InsertColumn 

func (c *CompiledIOP) InsertColumn(round int, name ifaces.ColID, size int, status column.Status) ifaces.Column

InsertColumn registers a new column in the protocol at a given round and returns the corresponding ifaces.Column object which summarizes the metadata of the column. Compared to CompiledIOP.InsertCommit, the user can additionally provide a custom Status to the column. See column.Status for more details. Importantly, if the user wants to register either a verifying key column (i.e. an offline-computed column public to the verifier) or a precomputed column (i.e. a precomputed column that is not public to the verifier and meant to be committed to) then the ad-hoc functions CompiledIOP.RegisterVerifyingKey and CompiledIOP.InsertPrecomputed should be preferred instead. Otherwise, this will cause an error since using these types of status requires the user to explicitly provide an assignment.

Note that the function panics

  • if the name is the empty string
  • if the size of the column is not a power of 2
  • if a column using the same name has already been registered

func (*CompiledIOP) InsertCommit 

func (c *CompiledIOP) InsertCommit(round int, name ifaces.ColID, size int) ifaces.Column

InsertCommit registers a new column (as committed) in the protocol at a given round and returns the corresponding ifaces.Column object which summarizes the metadata of the column. The user should provide a unique identifier `name` and specify a size for the column.

func (*CompiledIOP) InsertFixedPermutation 

func (c *CompiledIOP) InsertFixedPermutation(round int, name ifaces.QueryID, p []ifaces.ColAssignment, a, b []ifaces.Column) query.FixedPermutation

InsertFixedPermutation registers a new query.FixedPermutation constraint in the CompiledIOP. The caller can provide a name to uniquely identify the registered constraint and provide some context regarding its role in the currently specified protocol.

The function panics if - any of the columns in both `a` and `b` do not have the same size - any column in `a` or `b“ is a not registered columns - a constraint with the same name already exists in the CompiledIOP

func (*CompiledIOP) InsertFragmentedPermutation 

func (c *CompiledIOP) InsertFragmentedPermutation(round int, name ifaces.QueryID, a, b [][]ifaces.Column) query.Permutation

InsertFragmentedPermutation is as CompiledIOP.InsertPermutation but for fragmented tables. Meanining that permutation operates over the union of the rows of multiple tables.

func (*CompiledIOP) InsertGlobal 

func (c *CompiledIOP) InsertGlobal(round int, name ifaces.QueryID, expr *symbolic.Expression, noBoundCancel ...bool) query.GlobalConstraint

InsertGlobal registers a global constraint (see query.GlobalConstraint) inside of the protocol. The `noBoundCancel` field is used to specify if the constraint should be cancelled at the beginning or at the end when the constraint is applied over shifted columns. If the constraint is not cancelled, then the column will implictly loop-around exactly as if all the columns were circular vectors.

The function will panic if

  • the constraint involves one or more columns that are not registered in the CompiledIOP
  • the constraint involves columns that do not have all the same size
  • the constraint is given an `empty` name
  • the expression is invalid (but it should not be possible for the user to build such invalid expressions)
  • a constraint with the same name already exists
  • the definition round is inconsistent with the expression

func (*CompiledIOP) InsertInclusion 

func (c *CompiledIOP) InsertInclusion(round int, name ifaces.QueryID, including, included []ifaces.Column)

InsertInclusion creates an inclusion query query.Inclusion. Here, `included` and `including` are viewed as arrays and the query asserts that `included` contains only rows that are contained within `includings`, regardless of the multiplicities. The caller must provide a non-empty uniquely-identifying name to the column. The name should provide some context to help recognizing where the column comes from.

The function will panic if: - the columns in `including` do not all have the same size - the columns in `included` do not all have the same size - a constraint with the same name already exists in the CompiledIOP

func (*CompiledIOP) InsertInclusionConditionalOnIncluded 

func (c *CompiledIOP) InsertInclusionConditionalOnIncluded(round int, name ifaces.QueryID, including, included []ifaces.Column, includedFilter ifaces.Column)

Creates an inclusion query. Only the included table is filtered the filters should be columns containing only field elements for 0 and 1

func (*CompiledIOP) InsertInclusionConditionalOnIncluding 

func (c *CompiledIOP) InsertInclusionConditionalOnIncluding(round int, name ifaces.QueryID, including, included []ifaces.Column, includingFilter ifaces.Column)

Creates an inclusion query. Only the including table is filtered the filters should be columns containing only field elements for 0 and 1

func (*CompiledIOP) InsertInclusionDoubleConditional 

func (c *CompiledIOP) InsertInclusionDoubleConditional(round int, name ifaces.QueryID, including, included []ifaces.Column, includingFilter, includedFilter ifaces.Column)

Creates an inclusion query. Both the including and the included tables are filtered the filters should be columns containing only field elements for 0 and 1

func (*CompiledIOP) InsertInnerProduct 

func (c *CompiledIOP) InsertInnerProduct(round int, name ifaces.QueryID, a ifaces.Column, bs []ifaces.Column) query.InnerProduct

InsertInnerProduct registers a (batch) inner-product query (query.InnerProduct) between a common vector `a` and multiple vectors `bs`, meaning it generates an evaluation query for the inner-products <a, bs[i]> all at once. The caller must provide a non-empty uniquely-identifying name to the column. The name should provide some context to help recognizing where the column comes from.

The function panics if: - the name is the empty string - a query with the same name has already been registered in the Wizard - the provided columns `a` and `bs` do not all have the same size

func (*CompiledIOP) InsertLocal 

func (c *CompiledIOP) InsertLocal(round int, name ifaces.QueryID, cs_ *symbolic.Expression) query.LocalConstraint

InsertLocal registers a global constraint (see query.LocalConstraint) inside of the protocol. The provided name is used as unique identifier for the constraint and allows the caller to provide context so that it is easier to understand where the column comes from later on.

The function will panic if

  • the constraint involves one or more columns (or any item) that is not registered in the receiver CompiledIOP
  • the constraint involves columns that do not have all the same size
  • the constraint is given an `empty` name
  • the expression is invalid (but it should not be possible for the user to build such invalid expressions)
  • a constraint with the same name already exists
  • the definition round is inconsistent with the expression

func (*CompiledIOP) InsertLocalOpening 

func (c *CompiledIOP) InsertLocalOpening(round int, name ifaces.QueryID, pol ifaces.Column) query.LocalOpening

InsertLocalOpening registers a new local opening query query.LocalOpening in the current CompiledIOP. A local opening query requires the prover of the protocol to "open" the first position of the vector.

func (*CompiledIOP) InsertMiMC 

func (c *CompiledIOP) InsertMiMC(round int, id ifaces.QueryID, block, old, new ifaces.Column) query.MiMC

InsertMiMC declares a MiMC constraints query; a constraint that all the entries of new are obtained by running the compression function of MiMC over the entries of block and old, row-by-row.

The function returns the registered query.MiMC object and will panic if

  • the columns do not share the same size
  • the declaration round is anterior to the declaration round of the provided input columns.

func (*CompiledIOP) InsertPermutation 

func (c *CompiledIOP) InsertPermutation(round int, name ifaces.QueryID, a, b []ifaces.Column) query.Permutation

InsertPermutation registers a new permutation query.Permutation constraint in the CompiledIOP. The caller can provide a name to uniquely identify the registered constraint and provide some context regarding its role in the currently specified protocol.

The function panics if - any of the columns in both `a` and `b` do not have the same size - any column in `a` or `b“ is a not registered columns - a constraint with the same name already exists in the CompiledIOP

func (*CompiledIOP) InsertPrecomputed 

func (c *CompiledIOP) InsertPrecomputed(name ifaces.ColID, v smartvectors.SmartVector) (msg ifaces.Column)

InsertPrecomputed registers a new precomputed column that is statically assigned offline and which is not visible by the verifier. The created column bears the column.Precomputed status which tags that the column is meant to be committed to by the prover and its commitment is meant to be a part of the verifying key.

The caller must provide a uniquely identifying string name which can be used to provide context about the purpose of the column. The caller should also provide an explicit assignment to the column.

func (*CompiledIOP) InsertProof 

func (c *CompiledIOP) InsertProof(round int, name ifaces.ColID, size int) (msg ifaces.Column)

InsertProof registers a proof message by specifying its size and providing it a uniquely identifying name. Proof messages are columns bearing the column.Proof status. They corresponds to columns that are computed by the prover online and that are meant to be directly sent to the verifier at the end of the current prover's round.

The name must be non-empty and unique and the size must be a power of 2.

func (*CompiledIOP) InsertPublicInput deprecated 

func (c *CompiledIOP) InsertPublicInput(round int, name ifaces.ColID, size int) (msg ifaces.Column)

Deprecated: we never really use this type of column to denote actual public inputs. The plan is to resort to using query.LocalOpeningParams instead.

func (*CompiledIOP) InsertRange 

func (c *CompiledIOP) InsertRange(round int, name ifaces.QueryID, h ifaces.Column, max int)

InsertRange registers query.Range in the CompiledIOP. Namely, it ensures that all the values taken by `h` are within the range [[0; max]]. The caller must provide a non-empty uniquely-identifying name to the column. The name should provide some context to help recognizing where the column comes from.

The function panics if: - the column `h` does not exists - the range is not a power of 2 - the name is the empty string - a query with the same name has already been registered in the Wizard.

func (*CompiledIOP) InsertUnivariate 

func (c *CompiledIOP) InsertUnivariate(round int, name ifaces.QueryID, pols []ifaces.Column) query.UnivariateEval

InsertUnivariate declares a new univariate evaluation query query.UnivariateEval in the current CompiledIOP object. A univariate evaluation query is used to get an oracle-evaluation of a set of columns (seen as a polynomial in Lagrange basis) on a common evaluation point. The point may be assigned during the prover runtime and the evaluation are also assigned by the prover

The function panics if: - the name is the empty string - a query with the same name has already been registered in the Wizard

func (*CompiledIOP) InsertVerifier 

func (c *CompiledIOP) InsertVerifier(round int, ver VerifierStep, gnarkVer GnarkVerifierStep)

InsertVerifier registers a verifier steps into the current CompiledIOP; meaning a "native" Go function that performs one or more checks involving wizard items that are accessible to the verifier of the specified protocol.

Unlike for adding prover steps, the caller is required to provide:

  • a version of the verifier function meant to operate in a normal setting
  • a version of the verifier function meant to be executed within a gnark circuit. This is required for recursive composition of the protocol. In a context where recursive composition is not required, it is fine to provide a no-op function, but the caller should not provide the nil function. If not a no-op function, the provided function should perform exactly the same checks as the "native" verifier function.

Both functions should performs exactly the same checks but if the caller does not intend to run the verifier of the Wizard protocol in a gnark circuit, passing `nil` is fine.

func (*CompiledIOP) ListCommitments 

func (c *CompiledIOP) ListCommitments() []ifaces.ColID

ListCommitments returns a list of all the column that are registered in the protocol. The columns are returned in a deterministic order: round-by-round then by chronological order of declaration.

@alex: this should be renamed ListColumns

func (*CompiledIOP) NumRounds 

func (c *CompiledIOP) NumRounds() int

NumRounds returns the total number of prover interactions with the verifier that are registered in the protocol. If the protocol is non-interactive it will return "1"; "2" if one batch of random coins is registered, etc...

func (*CompiledIOP) RegisterProverAction 

func (c *CompiledIOP) RegisterProverAction(round int, action ProverAction)

RegisterProverAction registers an action to be accomplished by the prover of the protocol at a given round.

func (*CompiledIOP) RegisterVerifierAction 

func (c *CompiledIOP) RegisterVerifierAction(round int, action VerifierAction)

RegisterVerifierAction registers an action to be accomplished by the verifier of the protocol at a given round

func (*CompiledIOP) RegisterVerifyingKey 

func (c *CompiledIOP) RegisterVerifyingKey(name ifaces.ColID, witness ifaces.ColAssignment) ifaces.Column

RegistersVerifyingKey registers a column as part of the verifying key of the protocol; meaning a column whose assignment is static and which is visible to the verifier.

type CompiledIOPSerializer 

type CompiledIOPSerializer = func(comp *CompiledIOP) ([]byte, error)

CompiledIOPSerializer is a function capable of serializing a Compiled-IOP

type DefineFunc 

type DefineFunc func(build *Builder)

Function to specify the definition of an IOP

type GnarkVerifierStep 

type GnarkVerifierStep func(frontend.API, *WizardVerifierCircuit)

GnarkVerifierStep functions that can be registered in the CompiledIOP by the successive compilation steps. They correspond to "precompiled" verification steps.

type Proof 

type Proof struct {
	// Messages collection of the prover's message sent to the verifier.
	Messages collection.Mapping[ifaces.ColID, ifaces.ColAssignment]

	// QueriesParams stores all the query parameters (i.e) the messages of the
	// oracle to the verifier.
	QueriesParams collection.Mapping[ifaces.QueryID, ifaces.QueryParams]
}

Proof generically represents a proof obtained from the wizard. This object does not implement any logic and only serves as a registry for all the prover messages that are assigned by the prover runtime and that are necessary to run the verifier. It includes the assignment of all the columns that are visible to the verifier; meaning all columns bearing the tag column.Proof and the query parameters ifaces.QueryParams provided by the prover runtime.

The proof can be constructed using the Prove function and can be used as an input to the Verify function. It can also be used to assign a WizardVerifierCircuit in order to recursively compose the proof within a gnark circuit.

The struct does not implement any serialization logic.

func Prove 

func Prove(c *CompiledIOP, highLevelprover ProverStep) Proof

Prove is the top-level function that runs the Prover on the user's side. It is responsible for instantiating a fresh and new ProverRuntime and running the user's and compiler's ProverStep in order and calling the Fiat-Shamir state to generate the randomness between every rounds.

The caller can specify a `highLevelProver` function that implements the allocation of the columns and parameters defined in the Compile via the `define` parameter of the Compile function used to construct the provided CompiledIOP object `c`. In this case, and only in this case, the `highLevelProver` function is allowed to span over multiple interaction rounds between the prover and the verifier of the protocol. When this happens, the underlying ProverRuntime object is able to automatically follow and detect when the `highLevelProver` function is entering in a new round of the protocol.

However, we plan to deprecate this behavior and plan to require the user to concretely break down the high-level prover round-by-round as this auto-detection adds little value and adds a lot of convolution especially when the specified protocol is complicated and involves multiple multi-rounds sub-protocols that runs independently.

type ProverAction 

type ProverAction interface {
	// Run executes the ProverAction over a [ProverRuntime]
	Run(*ProverRuntime)
}

ProverAction represents an action to be performed by the prover. They have to be registered in the CompiledIOP via the CompiledIOP.RegisterProverAction

type ProverRuntime 

type ProverRuntime struct {

	// Spec is the underlying [CompiledIOP] of the underlying protocol the prover
	// is running.
	Spec *CompiledIOP

	// Columns stores all the column's ([ifaces.Column]) witnesses assigned so
	// far by the ProverRuntime. Columns that are assigned using
	// [ProverRuntime.AssignColumn] method are stored there. For most use-cases,
	// it is preferable to use[ifaces.Columns.GetColAssignment] instead of
	// fetching the assignmentdirectly from the ProverRuntime. The reason is
	// that, the column the caller is trying to fetch may be a "derivative
	// column" or another type of special column whose assignment is not directly
	// available within the prover's runtime.
	//
	// Please consider that this field could become a private field.
	Columns collection.Mapping[ifaces.ColID, ifaces.ColAssignment]

	// QueriesParams accumulates all the query parameters of the queries assigned so far. See
	// [ifaces.QueryParams]. The query parameters that are stored there
	// corresponds to the queries stored in [ProverRuntime.Spec.QueriesParams]
	QueriesParams collection.Mapping[ifaces.QueryID, ifaces.QueryParams]

	// Coins stores all the values of all random Coins that are generated internally
	// as the ProverRuntime unfolds the prover steps round after rounds.
	//
	// The user should not directly access this field and fall back to using the
	// dedicated methods [ProverRuntime.GetRandomCoinField] or
	// [ProverRuntime.GetRandomCoinIntegerVec].
	Coins collection.Mapping[coin.Name, interface{}]

	// State serves as an "any-purpose" data-storage for stateful proving. It allows
	// ProverSteps to persist data that can be accessed in later prover steps
	// without having to store it in a column. For convenience, the user should
	// take care of deleting the entry to free memory when he knows that the
	// field will not be accessed again while proving.
	//
	// The State is used internally by the [github.com/consensys/linea-monorepo/prover/protocol/compiler/vortex] and the
	// [github.com/consensys/linea-monorepo/prover/protocol/compiler/selfrecursion] compilers as a communication channel.
	State collection.Mapping[string, interface{}]

	// FS stores the Fiat-Shamir State, you probably don't want to use it
	// directly unless you know what you are doing. Just know that if you use
	// it to update the FS hash, this can potentially result in the prover and
	// the verifer end up having different state or the same message being
	// included a second time. Use it externally at your own risks.
	FS *fiatshamir.State

	// FiatShamirHistory tracks the fiat-shamir state at the beginning of every
	// round. The first entry is the initial state, the final entry is the final
	// state.
	FiatShamirHistory [][2][]field.Element
	// contains filtered or unexported fields
}

ProverRuntime collects the assignment of all the items with which the prover interacts by the prover of the protocol. This includes the prover's messages, items that are computed solely by the prover, the witness but also the random coins that are sampled by the verifier. The object is implicitly constructed by the Prove function and it should not be explicitly constructed by the user.

Instead, the user should interact with the prover runtime within a ProverStep function that he provides to the CompiledIOP that he is building. Example: 

// Function that the user provide to specify his protocol
func myDefineFunction(builder wizard.Builder) {

	// Registers a column "A" as a column to commit to
	a := build.RegisterCommit("A", 16)

	// Potentially add constraints over the column
	...
}

// The above define function specifies a protocol involving a column
// named "A". If we want to concretely run our protocol, we also need
// to provide a way to assign concrete values to the witness of the
// protocol.
func myProverFunction(run wizard.ProverRuntime) {
	a := smartvector.ForTest(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16)
	run.AssignColumn("A", a)
}

ProverRuntime also bears the logic to track the current round of interaction between the prover and the verifier.

func (*ProverRuntime) AssignColumn 

func (run *ProverRuntime) AssignColumn(name ifaces.ColID, witness ifaces.ColAssignment)

AssignColumn assigns a value to a column specified in the underlying CompiledIOP. For an external user, it should be used only on columns explicitly created via the Builder.RegisterCommit or CompiledIOP.InsertColumn, CompiledIOP.InsertCommit or CompiledIOP.InsertProof or even CompiledIOP.InsertPublicInput.

The function will panic if

  • an empty column name is provided
  • the column is not explictly registered in the CompiledIOP (e.g. if it is a derive column or the underlying type is found in github.com/consensys/linea-monorepo/prover/protocol/column/verifiercol for instance).
  • the assignment does not have the correct size
  • the column assignment occurs at the wrong round. If this error happens, it is likely that the ifaces.Column was created in the wrong round to begin with.

func (*ProverRuntime) AssignInnerProduct 

func (run *ProverRuntime) AssignInnerProduct(name ifaces.QueryID, ys ...field.Element) query.InnerProductParams

AssignInnerProduct assigns the result of an inner-product query in the prover runtime. The function will panic if

  • the wrong number of `ys` value is provided. It should match the length of `bs` that was provided when registering the query.
  • no query with the name `name` are found in the CompiledIOP object.
  • parameters for this query have already been assigned
  • the assignment round is not the correct one

func (*ProverRuntime) AssignLocalPoint 

func (run *ProverRuntime) AssignLocalPoint(name ifaces.QueryID, y field.Element)

AssignLocalPoint assign evaluation point and claimed values for a local point opening. The function will panic if:

  • the parameters were already assigned
  • the specified query is not registered
  • the assignment round is incorrect

func (*ProverRuntime) AssignUnivariate 

func (run *ProverRuntime) AssignUnivariate(name ifaces.QueryID, x field.Element, ys ...field.Element)

AssignUnivariate assigns the evaluation point and the evaluation result and claimed values for a univariate evaluation bearing `name` as an ID.

The function will panic if:

  • the wrong number of `ys` value is provided. It should match the length of `bs` that was provided when registering the query.
  • no query with the name `name` are found in the CompiledIOP object.
  • parameters for this query have already been assigned
  • the assignment round is not the correct one

func (ProverRuntime) CopyColumnInto 

func (run ProverRuntime) CopyColumnInto(name ifaces.ColID, buff *ifaces.ColAssignment)

CopyColumnInto implements `column.GetWitness`. Copies the witness into a slice Deprecated: this is deadcode

func (ProverRuntime) GetColumn 

func (run ProverRuntime) GetColumn(name ifaces.ColID) ifaces.ColAssignment

GetColumn implements `ifaces.Runtime`. Returns a column witness, that has been previously stored. It is a deep-copy operation. And thus, it guarantees that the stored witness cannot be accidentally mutated by the caller as a side effect.

Something to note however, is that the function will panic if the the provided name does not exists explictly in the [ProverRuntime.Columns] database and this will be the case if the attempts to recover a column such as a column.Shifted or any other type of derivative columns. While theses columns are absolutely legal they are not stored explicitly in the runtime and they must be accessed through the ifaces.Column.GetColAssignment method instead which will work for any type of column. The user should use the latter as a go-to way to access an assigned column. The reason this function is exported is to make it accessible to the other functions of the github.com/consensys/linea-monorepo/prover/protocol/column package.

Namely, the function will panic if:

  • `name` relates to a column that does not exists or to a column that is not explictly an assigned column.
  • `name` relates to a column that does exists but whose assignment is not readily available when the function is called.

func (ProverRuntime) GetColumnAt 

func (run ProverRuntime) GetColumnAt(name ifaces.ColID, pos int) field.Element

GetColumnAt does the same as [GetColumn] but only returns a single position instead of returning the whole vector; i.e. it returns the assignment of an explictly assigned column at a requested position.

The same cautiousness as for ProverRuntime.AssignColumn applies to this function. Namely, this function will only work if the requested column is explicitly an assigned column (meaning not a derive column).

func (*ProverRuntime) GetInnerProduct 

func (run *ProverRuntime) GetInnerProduct(name ifaces.QueryID) query.InnerProduct

GetInnerProduct returns an inner-product query from the underlying CompiledIOP. Deprecated: directly use CompiledIOP.Spec.GetInnerProduct() instead, which does exactly the same thing.

func (*ProverRuntime) GetInnerProductParams 

func (run *ProverRuntime) GetInnerProductParams(name ifaces.QueryID) query.InnerProductParams

GetInnerProductParams returns pre-assigned parameters for the specified query.InnerProduct query. The caller specifies the query by its name and the method returns the query's parameters. As a reminders, the parameters of the query means the result of the inner-products.

The function will panic of the parameters are not available or if the parameters have the wrong type: not an query.InnerProductParams.

func (*ProverRuntime) GetLocalPointEval 

func (run *ProverRuntime) GetLocalPointEval(name ifaces.QueryID) query.LocalOpening

GetLocalPointEval gets the metadata of a query.LocalOpening query. Panic if not found. Deprecated, use `comp.Spec.GetLocalPointEval` instead since it does exactly the same thing.

func (*ProverRuntime) GetLocalPointEvalParams 

func (run *ProverRuntime) GetLocalPointEvalParams(name ifaces.QueryID) query.LocalOpeningParams

GetLocalPointEvalParams returns the parameters of a univariate evaluation (i.e: x, the evaluation point) and y, the alleged polynomial opening.

func (*ProverRuntime) GetMessage 

func (run *ProverRuntime) GetMessage(name ifaces.ColID) ifaces.ColAssignment

GetMessage gets a message sent to the verifier Deprecated: use ProverRuntime.GetColumn instead

func (*ProverRuntime) GetParams 

func (run *ProverRuntime) GetParams(name ifaces.QueryID) ifaces.QueryParams

GetParams generically extracts the parameters of a query. Will panic if no parameters are found

func (*ProverRuntime) GetRandomCoinField 

func (run *ProverRuntime) GetRandomCoinField(name coin.Name) field.Element

GetRandomCoinField returns a field element random. The coin should be issued at the same round as it was registered. The same coin can't be retrieved more than once. The coin should also have been registered as a field element before doing this call. Will also trigger the "goNextRound" logic if appropriate.

func (*ProverRuntime) GetRandomCoinIntegerVec 

func (run *ProverRuntime) GetRandomCoinIntegerVec(name coin.Name) []int

GetRandomCoinIntegerVec returns a pre-sampled integer vec random coin. The coin should be issued at the same round as it was registered. The same coin can't be retrieved more than once. The coin should also have been registered as an integer vec before doing this call. Will also trigger the "goNextRound" logic if appropriate.

func (*ProverRuntime) GetUnivariateEval 

func (run *ProverRuntime) GetUnivariateEval(name ifaces.QueryID) query.UnivariateEval

GetUnivariateEval get univariate eval metadata. Panic if not found. Deprecated: fallback to run.Spec.GetUnivariateEval instead which does exactly the same thing.

func (*ProverRuntime) GetUnivariateParams 

func (run *ProverRuntime) GetUnivariateParams(name ifaces.QueryID) query.UnivariateEvalParams

GetUnivariateParams returns the parameters of a univariate evaluation (i.e: x, the evaluation point) and y, the alleged polynomial opening. This is intended to resolve parameters that have been already assigned in a previous step of the prover runtime.

func (*ProverRuntime) NumRounds deprecated 

func (run *ProverRuntime) NumRounds() int

NumRounds returns the total number of rounds in the corresponding WizardIOP.

Deprecated: this method does not bring anything useful as its already easy to get this value from the Spec

type ProverStep 

type ProverStep func(assi *ProverRuntime)

ProverStep represents an operation to be performed by the prover of a wizard protocol. It can be provided by the user or by an internal compiled to the protocol specification CompiledIOP by appending it to the field [CompiledIOP.SubProvers]. 

CompiledIOP.SubProvers.AppendToInner(round, proverStep)

The ProverStep function may interact with the prover runtime to resolve the values of an already assigned item: (ifaces.Colssignment, coin, ifaces.QueryParams, ...).

The ProverStep function that we pass as the `highLevelProver` argument of Prove function has the particularity that it is allowed to span over multiple interaction-rounds between the prover and the verifier. This is a behavior that we intend to deprecate and it should not be used by the prover as this tends to create convolutions in the runtime of the prover.

type PublicInput 

type PublicInput struct {
	Name string
	Acc  ifaces.Accessor
}

PublicInput represents a public input in a wizard protocol. Public inputs are materialized with a functional identifier and a local opening query. The identifier is what ultimately identifies the public input as the query may be mutated by compilation (if we use the FullRecursion compiler), therefore it would unsafe to use the ID of the query to identify the public input in the circuit.

type VerifierAction 

type VerifierAction interface {
	// Skip indicates that the verifier action can be skipped
	Skip()
	// IsSkipped returns whether the current VerifierAction is skipped
	IsSkipped() bool
	// Run executes the VerifierAction over a [VerifierRuntime] it returns an
	// error.
	Run(*VerifierRuntime) error
	// RunGnark is as Run but in a gnark circuit. Instead, of the returning an
	// error the function enforces the passing of the verifier's checks.
	RunGnark(frontend.API, *WizardVerifierCircuit)
}

VerifierAction represents an action to be performed by the verifier of the protocol. Usually, this is used to represent verifier checks. They can be registered via CompiledIOP.RegisterVerifierAction.

type VerifierRuntime 

type VerifierRuntime struct {

	// Spec points to the static description of the underlying protocol
	Spec *CompiledIOP

	// Collection of the prover's message sent to the verifier.
	Columns collection.Mapping[ifaces.ColID, ifaces.ColAssignment]

	// Coins stores all the random coins issued during the protocol
	Coins collection.Mapping[coin.Name, interface{}]

	// Stores all the query parameters (i.e) the messages of the oracle to the
	// verifier.
	QueriesParams collection.Mapping[ifaces.QueryID, ifaces.QueryParams]

	// FS stores the Fiat-Shamir State, you probably don't want to use it
	// directly unless you know what you are doing. Just know that if you use
	// it to update the FS hash, this can potentially result in the prover and
	// the verifer end up having different state or the same message being
	// included a second time. Use it externally at your own risks.
	FS *fiatshamir.State

	// FiatShamirHistory tracks the fiat-shamir state at the beginning of every
	// round. The first entry is the initial state, the final entry is the final
	// state.
	FiatShamirHistory [][2][]field.Element
}

VerifierRuntime runtime collects all data that visible or computed by the verifier of the wizard protocol. This includes the prover's messages, the column.VerifyingKey tagged columns.

The struct is not intended to be constructed by the user and is internally constructed by the Verify function. The user should instead restricts its usage of the function within VerifierStep functions that are provided to either the CompiledIOP or the Verify function.

func (VerifierRuntime) CopyColumnInto deprecated 

func (run VerifierRuntime) CopyColumnInto(name ifaces.ColID, buff *ifaces.ColAssignment)

CopyColumnInto implements `column.GetWitness` Copies the witness into a slice

Deprecated: this is deadcode

func (*VerifierRuntime) GetColumn 

func (run *VerifierRuntime) GetColumn(name ifaces.ColID) ifaces.ColAssignment

GetColumn returns a column by name. The status of the columns must be either proof or public input and the column must be visible to the verifier and consequently be available in the proof.

func (VerifierRuntime) GetColumnAt 

func (run VerifierRuntime) GetColumnAt(name ifaces.ColID, pos int) field.Element

GetColumnAt returns the value of a verifier ifaces.Column at a specified position. This is needed to implement the column.GetWitness interface and it will only work if the requested column is part of the proof the verifier is running on.

func (*VerifierRuntime) GetInnerProductParams 

func (run *VerifierRuntime) GetInnerProductParams(name ifaces.QueryID) query.InnerProductParams

GetInnerProductParams returns the parameters of an inner-product query query.InnerProduct provided by the proof. The function will panic if the query does not exist or if the parameters are not available in the proof.

func (*VerifierRuntime) GetLocalPointEvalParams 

func (run *VerifierRuntime) GetLocalPointEvalParams(name ifaces.QueryID) query.LocalOpeningParams

GetLocalPointEvalParams returns the parameters of a query.LocalOpening query (i.e: y, the alleged opening of the query's column at the first position.

func (*VerifierRuntime) GetParams deprecated 

func (run *VerifierRuntime) GetParams(name ifaces.QueryID) ifaces.QueryParams

GetParams extracts the parameters of a query. Will panic if no parameters are found

Deprecated: there are already methods to return parameters with an explicit type.

func (*VerifierRuntime) GetPublicInput 

func (run *VerifierRuntime) GetPublicInput(name string) field.Element

GetPublicInput returns a public input from its name

func (*VerifierRuntime) GetRandomCoinField 

func (run *VerifierRuntime) GetRandomCoinField(name coin.Name) field.Element

GetRandomCoinField returns a field element random. The coin should be issued at the same round as it was registered. The same coin can't be retrieved more than once. The coin should also have been registered as a field element before doing this call. Will also trigger the "goNextRound" logic if appropriate.

func (*VerifierRuntime) GetRandomCoinIntegerVec 

func (run *VerifierRuntime) GetRandomCoinIntegerVec(name coin.Name) []int

GetRandomCoinIntegerVec returns a pre-sampled integer vec random coin. The coin should be issued at the same round as it was registered. The same coin can't be retrieved more than once. The coin should also have been registered as an integer vec before doing this call. Will also trigger the "goNextRound" logic if appropriate.

func (*VerifierRuntime) GetUnivariateEval 

func (run *VerifierRuntime) GetUnivariateEval(name ifaces.QueryID) query.UnivariateEval

GetUnivariateEval returns a registered query.UnivariateEval. Panic if not found. Deprecated: get it from the CompiledIOP instead

func (*VerifierRuntime) GetUnivariateParams 

func (run *VerifierRuntime) GetUnivariateParams(name ifaces.QueryID) query.UnivariateEvalParams

GetUnivariateParams returns the parameters of a univariate evaluation (i.e: x, the evaluation point) and y, the alleged polynomial opening. This is intended to resolve parameters that have been provided by the proof.

func (*VerifierRuntime) NumRounds 

func (run *VerifierRuntime) NumRounds() int

Returns the number of rounds in the assignment. Deprecated: get it from the CompiledIOP instead

type VerifierStep 

type VerifierStep func(a *VerifierRuntime) error

VerifierStep specifies a single step of verifier for a single subprotocol. This can be used to specify verifier checks involving user-provided columns for relations that cannot be automatically enforced via a ifaces.Query

type VersionMetadata 

type VersionMetadata struct {
	// Title is a generic name that can be used to identify the wizard
	Title string
	// Version number is a version string
	Version string
}

VersionMetadata collects generic information to use to bootstrap the FS state of the already CompiledIOP.

type WizardVerifierCircuit 

type WizardVerifierCircuit struct {

	// Spec points to the inner CompiledIOP and carries all the static
	// informations related to the circuit.
	Spec *CompiledIOP `gnark:"-"`

	// Columns stores the gnark witness part corresponding to the columns
	// provided in the proof and in the VerifyingKey.
	Columns [][]frontend.Variable `gnark:",secret"`

	// UnivariateParams stores an assignment for each [query.UnivariateParams]
	// from the proof. This is part of the witness of the gnark circuit.
	UnivariateParams []query.GnarkUnivariateEvalParams `gnark:",secret"`

	// InnerProductParams stores an assignment for each [query.InnerProductParams]
	// from the proof. It is part of the witness of the gnark circuit.
	InnerProductParams []query.GnarkInnerProductParams `gnark:",secret"`

	// LocalOpeningParams stores an assignment for each [query.LocalOpeningParams]
	// from the proof. It is part of the witness of the gnark circuit.
	LocalOpeningParams []query.GnarkLocalOpeningParams `gnark:",secret"`

	// FS is the Fiat-Shamir state, mirroring [VerifierRuntime.FS]. The same
	// cautionnary rules apply to it; e.g. don't use it externally when
	// possible.
	FS *fiatshamir.GnarkFiatShamir `gnark:"-"`

	// Coins stores all the coins sampled by the verifier circuit. It is not
	// part of the witness since the coins are constructed from the assigned
	// proof. We still track them here to mirror how the [VerifierRuntime]
	// works.
	Coins collection.Mapping[coin.Name, interface{}] `gnark:"-"`

	// HasherFactory is a custom hasher that we use for all the MiMC hashing
	// in the circuit. It is used for efficiently computing the Fiat-Shamir
	// hashes but also the MiMC Vortex column hashes that we use for the
	// last round of the self-recursion.
	HasherFactory *gkrmimc.HasherFactory `gnark:"-"`

	// FiatShamirHistory tracks the fiat-shamir state at the beginning of every
	// round. The first entry is the initial state, the final entry is the final
	// state.
	FiatShamirHistory [][2][]frontend.Variable `gnark:"-"`
	// contains filtered or unexported fields
}

WizardVerifierCircuit the VerifierRuntime in a gnark circuit. The complete implementation follows this mirror logic.

The sub-circuit employs GKR for MiMC in order to improve the performances of the MiMC hashes that occurs during the verifier runtime.

func AllocateWizardCircuit 

func AllocateWizardCircuit(comp *CompiledIOP) (*WizardVerifierCircuit, error)

AllocateWizardCircuit allocates the inner-slices of the verifier struct from a precompiled IOP. It is necessary to run this function before calling the frontend.Compile function as this will pre-allocate all the witness fields of the circuit and will allow the gnark compiler to understand how big is the witness of the circuit.

func GetWizardVerifierCircuitAssignment 

func GetWizardVerifierCircuitAssignment(comp *CompiledIOP, proof Proof) *WizardVerifierCircuit

GetWizardVerifierCircuitAssignment assigns values to the wizard verifier circuit from a proof. The result of this function can be used to construct a gnark assignment circuit involving the verification of Wizard proof.

func NewWizardVerifierCircuit 

func NewWizardVerifierCircuit() *WizardVerifierCircuit

NewWizardVerifierCircuit creates an empty wizard verifier circuit. Initializes the underlying structs and collections.

func (*WizardVerifierCircuit) AllocColumn 

func (c *WizardVerifierCircuit) AllocColumn(id ifaces.ColID, size int) []frontend.Variable

AllocColumn inserts a column in the Wizard verifier circuit and is meant to be called at allocation time.

func (*WizardVerifierCircuit) AllocInnerProduct 

func (c *WizardVerifierCircuit) AllocInnerProduct(qName ifaces.QueryID, qInfo query.InnerProduct)

AllocInnerProduct inserts a slot for an inner-product query opening in the witness of the verifier circuit.

func (*WizardVerifierCircuit) AllocLocalOpening 

func (c *WizardVerifierCircuit) AllocLocalOpening(qName ifaces.QueryID, qInfo query.LocalOpening)

AllocLocalOpening inserts a slot for a local position opening in the witness of the verifier circuit.

func (*WizardVerifierCircuit) AllocUnivariateEval 

func (c *WizardVerifierCircuit) AllocUnivariateEval(qName ifaces.QueryID, qInfo query.UnivariateEval)

AllocUnivariableEval inserts a slot for a univariate query opening in the witness of the verifier circuit.

func (*WizardVerifierCircuit) AssignColumn 

func (c *WizardVerifierCircuit) AssignColumn(id ifaces.ColID, sv smartvectors.SmartVector)

AssignColumn assigns a column in the Wizard verifier circuit

func (*WizardVerifierCircuit) AssignInnerProduct 

func (c *WizardVerifierCircuit) AssignInnerProduct(qName ifaces.QueryID, params query.InnerProductParams)

AssignInnerProduct inserts a slot for an inner-product query opening in the witness of the verifier circuit.

func (*WizardVerifierCircuit) AssignLocalOpening 

func (c *WizardVerifierCircuit) AssignLocalOpening(qName ifaces.QueryID, params query.LocalOpeningParams)

AssignLocalOpening inserts a slot for a local position opening in the witness of the verifier circuit.

func (*WizardVerifierCircuit) AssignUnivariateEval 

func (c *WizardVerifierCircuit) AssignUnivariateEval(qName ifaces.QueryID, params query.UnivariateEvalParams)

AssignUnivariableEval inserts a slot for a univariate query opening in the witness of the verifier circuit.

func (*WizardVerifierCircuit) GetColumn 

func (c *WizardVerifierCircuit) GetColumn(name ifaces.ColID) []frontend.Variable

GetColumns returns the gnark assignment of a column in a gnark circuit. It mirrors the function VerifierRuntime.GetColumn

func (*WizardVerifierCircuit) GetColumnAt 

func (c *WizardVerifierCircuit) GetColumnAt(name ifaces.ColID, pos int) frontend.Variable

GetColumnAt returns the gnark assignment of a column at a requested point in a gnark circuit. It mirrors the function VerifierRuntime.GetColumnAt

func (*WizardVerifierCircuit) GetInnerProductParams 

func (c *WizardVerifierCircuit) GetInnerProductParams(name ifaces.QueryID) query.GnarkInnerProductParams

GetInnerProductParams returns pre-assigned parameters for the requested query.InnerProduct query from the proof. It mirrors the work of VerifierRuntime.GetInnerProductParams

func (*WizardVerifierCircuit) GetLocalPointEvalParams 

func (c *WizardVerifierCircuit) GetLocalPointEvalParams(name ifaces.QueryID) query.GnarkLocalOpeningParams

GetLocalPointEvalParams returns the parameters for the requested query.LocalPointOpening query. Its work mirrors the function [VerifierRuntime.GetLocalOpeningParams]

func (*WizardVerifierCircuit) GetParams 

func (c *WizardVerifierCircuit) GetParams(id ifaces.QueryID) ifaces.GnarkQueryParams

GetParams returns a query parameters as a generic interface

func (*WizardVerifierCircuit) GetPublicInput 

func (c *WizardVerifierCircuit) GetPublicInput(api frontend.API, name string) frontend.Variable

GetPublicInput returns a public input value from its name

func (*WizardVerifierCircuit) GetRandomCoinField 

func (c *WizardVerifierCircuit) GetRandomCoinField(name coin.Name) frontend.Variable

GetRandomCoinField returns the preassigned value of a random coin as frontend.Variable. The implementation implicitly checks that the field element is of the right type. It mirrors VerifierRuntime.GetRandomCoinField

func (*WizardVerifierCircuit) GetRandomCoinIntegerVec 

func (c *WizardVerifierCircuit) GetRandomCoinIntegerVec(name coin.Name) []frontend.Variable

GetRandomCoinIntegerVec returns a pre-sampled integer vec random coin as an array of frontend.Variable. The implementation implicitly checks that the requested coin does indeed have the type coin.IntegerVec and panics if not. The function mirror VerifierRuntime.GetRandomCoinIntegerVec.

func (*WizardVerifierCircuit) GetUnivariateEval 

func (c *WizardVerifierCircuit) GetUnivariateEval(name ifaces.QueryID) query.UnivariateEval

GetUnivariateEval univariate eval metadata of the requested query. Panic if not found.

func (*WizardVerifierCircuit) GetUnivariateParams 

func (c *WizardVerifierCircuit) GetUnivariateParams(name ifaces.QueryID) query.GnarkUnivariateEvalParams

GetUnivariateParams returns the parameters of a univariate evaluation (i.e: x, the evaluation point) and y, the alleged polynomial opening. It mirrors VerifierRuntime.GetUnivariateParams.

func (*WizardVerifierCircuit) Verify 

func (c *WizardVerifierCircuit) Verify(api frontend.API)

Verify generates the constraints to assess the correctness of a wizard transcript. This function has to be called in the context of a frontend.Define function. Its work mirrors the Verify function.

Source Files

View all Source files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.