query

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: 21 Imported by: 0

Documentation

Index

Constants

This section is empty.

Variables

This section is empty.

Functions

func CheckFixedPermutation 

func CheckFixedPermutation(a, b []ifaces.ColAssignment, S []ifaces.ColAssignment) error

Checks a fixedpermutation query manually.

func CheckPermutation 

func CheckPermutation(a, b []ifaces.ColAssignment) error

CheckPermutation manually checks that a permutation argument is satisfied.

Types

type FixedPermutation 

type FixedPermutation struct {
	ID ifaces.QueryID
	//splittings
	A, B []ifaces.Column

	//fixed  permutation
	S []ifaces.ColAssignment
}
Enforces a fixedPermutation constraint, that  two handles must
be a fixedpermutation of eachother

fix permutation over splittings of two vectors 

here vectors A_i,B_i are splitting of target vectors A*,B*

where a fixed permutation is applied between target vectors i.e.,A* = A0||...||An, B* = B0||...||Bn and B* = s(A*) for the fixed permutation s

func NewFixedPermutation 

func NewFixedPermutation(id ifaces.QueryID, S []ifaces.ColAssignment, a, b []ifaces.Column) FixedPermutation

Constructor for fixedPermutation constraints also makes the input validation

func (FixedPermutation) Check 

func (r FixedPermutation) Check(run ifaces.Runtime) error

Check implements the ifaces.Query interface

func (FixedPermutation) CheckGnark 

func (f FixedPermutation) CheckGnark(api frontend.API, run ifaces.GnarkRuntime)

GnarkCheck will panic in this construction because we do not have a good way to check the query within a circuit

func (FixedPermutation) Name 

func (r FixedPermutation) Name() ifaces.QueryID

Name implements the ifaces.Query interface

type GlobalConstraint 

type GlobalConstraint struct {
	/*
		Symbolic expression representing the global constraint
	*/
	*symbolic.Expression
	/*
		ifaces.QueryID of the coinstraint
	*/
	ID ifaces.QueryID
	/*
		Domain over which the constraints applies
	*/
	DomainSize int
	/*
		Optional field: prevents the constraint to be cancelled on the
		bound. This is used in the "permutation" global constraint for
		instance. False by default
	*/
	NoBoundCancel bool
}

A global constraint is an arithmetic constraint that is applied on several vectors For instance A[i - 1] * B[i] = A[i] for all i \in 0..1000. The expression can also use random coins as variables.

func NewGlobalConstraint 

func NewGlobalConstraint(id ifaces.QueryID, expr *symbolic.Expression, noBoundCancel ...bool) GlobalConstraint

Constructor for global constraints

  • getSize is a function that gives the size of a commitment from its ifaces.QueryID. It is aimed at abstracting the "CompiledIOP" from this package to avoid circular dependencies. It used mainly for validating the constraint and computing the size of the domain on which the constraint applies.

func (GlobalConstraint) Check 

func (cs GlobalConstraint) Check(run ifaces.Runtime) error

Test a polynomial identity relation

func (GlobalConstraint) CheckGnark 

func (cs GlobalConstraint) CheckGnark(api frontend.API, run ifaces.GnarkRuntime)

Test a polynomial identity relation

func (*GlobalConstraint) MinMaxOffset 

func (cs *GlobalConstraint) MinMaxOffset() utils.Range

Returns the min and max offset happening in the expression

func (GlobalConstraint) Name 

func (cs GlobalConstraint) Name() ifaces.QueryID

Name implements the ifaces.Query interface

type GnarkInnerProductParams 

type GnarkInnerProductParams struct {
	Ys []frontend.Variable
}

A gnark circuit version of InnerProductParams

func (GnarkInnerProductParams) UpdateFS 

func (p GnarkInnerProductParams) UpdateFS(fs *fiatshamir.GnarkFiatShamir)

Update the fiat-shamir state with the the present parameters

type GnarkLocalOpeningParams 

type GnarkLocalOpeningParams struct {
	Y frontend.Variable
}

A gnark circuit version of the LocalOpeningResult

func (GnarkLocalOpeningParams) UpdateFS 

func (p GnarkLocalOpeningParams) UpdateFS(fs *fiatshamir.GnarkFiatShamir)

Update the fiat-shamir state with the the present parameters

type GnarkUnivariateEvalParams 

type GnarkUnivariateEvalParams struct {
	X  frontend.Variable
	Ys []frontend.Variable
}

A gnark circuit version of univariate eval params

func (GnarkUnivariateEvalParams) UpdateFS 

func (p GnarkUnivariateEvalParams) UpdateFS(fs *fiatshamir.GnarkFiatShamir)

Update the fiat-shamir state with the the present parameters

type Inclusion 

type Inclusion struct {
	// Included represents the table over which the constraint applies. The
	// columns must be a non-zero collection of columns of the same size.
	Included []ifaces.Column
	// Including represents the reference table of the inclusion constraint. It
	// stores all the values that the “including" table is required to store.
	// The table must be a non-zero collection of columns of the same size.
	//
	// Including can also represent a fragmented table. In that case, the double
	// slice is indexed as [fragment][column]. In the non-fragmented case, the
	// slice is as if there is only a single fragment
	Including [][]ifaces.Column
	// ID stores the identifier string of the query
	ID ifaces.QueryID
	// IncludedFilter is (allegedly) a binary-assigned column specifying
	// with a one whether the corresponding row of the “included" is subjected
	// to the constraint and with a 0 whether the row is disregarded.
	IncludedFilter ifaces.Column
	// IncludingFilter is (allegedly) a binary-assigned column specifying
	// with a one whether a row of the including “table" is allowed and with a
	// 0 whether the corresponding row is forbidden.
	//
	// The slices is indexed per number of fragment, in the non-fragmented case,
	// consider there is only a single segment.
	IncludingFilter []ifaces.Column
}

Inclusion describes an inclusion query (a.k.a. a lookup constraint). The query can feature conditional “included" tables and conditional “including" tables. The query can additionally feature an fragmented table meaning that the including “table" to consider is the union of two tables.

func NewInclusion 

func NewInclusion(
	id ifaces.QueryID,
	included []ifaces.Column,
	including [][]ifaces.Column,
	includedFilter ifaces.Column,
	includingFilter []ifaces.Column,
) Inclusion

NewInclusion constructs an inclusion. Will panic if it is mal-formed

func (Inclusion) Check 

func (r Inclusion) Check(run ifaces.Runtime) error

Check implements the ifaces.Query interface

func (Inclusion) CheckGnark 

func (i Inclusion) CheckGnark(api frontend.API, run ifaces.GnarkRuntime)

GnarkCheck implements the ifaces.Query interface. It will panic in this construction because we do not have a good way to check the query within a circuit

func (Inclusion) IsFilteredOnIncluded 

func (r Inclusion) IsFilteredOnIncluded() bool

IsFilteredOnIncluded returns true if the table is filtered on the including side of the table

func (Inclusion) IsFilteredOnIncluding 

func (r Inclusion) IsFilteredOnIncluding() bool

IsFilteredOnIncluding returns true if the table is filtered on the included side of the table.

func (Inclusion) Name 

func (r Inclusion) Name() ifaces.QueryID

Name implements the ifaces.Query interface

type InnerProduct 

type InnerProduct struct {
	A  ifaces.Column
	Bs []ifaces.Column
	ID ifaces.QueryID
}

Represent a batch of inner-product <a, b0>, <a, b1>, <a, b2> ...

func NewInnerProduct 

func NewInnerProduct(id ifaces.QueryID, a ifaces.Column, bs ...ifaces.Column) InnerProduct

Constructor for inner-product. The list of polynomial Bs must be deduplicated.

func (InnerProduct) Check 

func (r InnerProduct) Check(run ifaces.Runtime) error

Check the inner-product manually

func (InnerProduct) CheckGnark 

func (r InnerProduct) CheckGnark(api frontend.API, run ifaces.GnarkRuntime)

Check the inner-product manually

func (InnerProduct) GnarkAllocate 

func (p InnerProduct) GnarkAllocate() GnarkInnerProductParams

func (InnerProduct) Name 

func (r InnerProduct) Name() ifaces.QueryID

Name implements the ifaces.Query interface

type InnerProductParams 

type InnerProductParams struct {
	Ys []field.Element
}

Inner product params

func NewInnerProductParams 

func NewInnerProductParams(ys ...field.Element) InnerProductParams

Constructor for fixed point univariate evaluation query parameters

func (InnerProductParams) GnarkAssign 

func (p InnerProductParams) GnarkAssign() GnarkInnerProductParams

func (InnerProductParams) UpdateFS 

func (ipp InnerProductParams) UpdateFS(state *fiatshamir.State)

Update the fiat-shamir state with inner-product params

type LocalConstraint 

type LocalConstraint struct {
	*symbolic.Expression
	ID         ifaces.QueryID
	DomainSize int
}

A local constraint is an arithmetic relation between prespecified polynomial commitment openings and random coin. the local constraint is evaluated at 0 in order to obtain evaluations at different points, the vector should be shifted first and the constraint applied after

func NewLocalConstraint 

func NewLocalConstraint(id ifaces.QueryID, expr *symbolic.Expression) LocalConstraint

Construct a new local constraint

func (LocalConstraint) Check 

func (cs LocalConstraint) Check(run ifaces.Runtime) error

Test the polynomial identity

func (LocalConstraint) CheckGnark 

func (cs LocalConstraint) CheckGnark(api frontend.API, run ifaces.GnarkRuntime)

Test the polynomial identity in a circuit setting

func (LocalConstraint) Name 

func (r LocalConstraint) Name() ifaces.QueryID

Name implements the ifaces.Query interface

type LocalOpening 

type LocalOpening struct {
	Pol ifaces.Column
	ID  ifaces.QueryID
}

Queries the opening of a handle at zero

func NewLocalOpening 

func NewLocalOpening(id ifaces.QueryID, pol ifaces.Column) LocalOpening

Constructs a new local opening query

func (LocalOpening) Check 

func (r LocalOpening) Check(run ifaces.Runtime) error

Test that the polynomial evaluation holds

func (LocalOpening) CheckGnark 

func (r LocalOpening) CheckGnark(api frontend.API, run ifaces.GnarkRuntime)

Test that the polynomial evaluation holds

func (LocalOpening) Name 

func (r LocalOpening) Name() ifaces.QueryID

Name implements the ifaces.Query interface

type LocalOpeningParams 

type LocalOpeningParams struct {
	Y field.Element
}

Contains the result of a local opening

func NewLocalOpeningParams 

func NewLocalOpeningParams(y field.Element) LocalOpeningParams

Constructor for non-fixed point univariate evaluation query parameters

func (LocalOpeningParams) GnarkAssign 

func (p LocalOpeningParams) GnarkAssign() GnarkLocalOpeningParams

func (LocalOpeningParams) UpdateFS 

func (lop LocalOpeningParams) UpdateFS(fs *fiatshamir.State)

Updates a Fiat-Shamir state

type MiMC 

type MiMC struct {
	// The columns on which the query applies
	Blocks, OldState, NewState ifaces.Column
	// The name of the query
	ID ifaces.QueryID
}

A MiMC query over a set of 3 columns (block, oldState, newState) enforces that newState is the result of applying the MiMC compression function to block and oldState.

We use the MiMC as specified in the following paper. https://eprint.iacr.org/2016/492.pdf

And the compression function uses the Miyaguchi's construction https://en.wikipedia.org/wiki/One-way_compression_function#Miyaguchi.E2.80.93Preneel

func NewMiMC 

func NewMiMC(id ifaces.QueryID, block, oldState, newState ifaces.Column) MiMC

Constructs a new MiMC query

func (MiMC) Check 

func (m MiMC) Check(run ifaces.Runtime) error

The verifier checks that the permutation was applied correctly

func (MiMC) CheckGnark 

func (m MiMC) CheckGnark(api frontend.API, run ifaces.GnarkRuntime)

Check the mimc relation in a gnark circuit

func (MiMC) Name 

func (m MiMC) Name() ifaces.QueryID

Name implements the ifaces.Query interface

type Permutation 

type Permutation struct {
	// A and B represent the tables on both sides of the argument. The
	// permutation can be fractionned (len(A) = len(B) > 1) and it can be
	// multi-column (len(A[*]) = len(B[*]) > 1.
	A, B [][]ifaces.Column
	// ID is the string indentifier of the query.
	ID ifaces.QueryID
}

Permutation is a predicate that assess that two tables contains the same rows up to a permutation. The tables can contain several columns and they can be described in a fractioned way: the table is the union of the rows of several tables.

func NewPermutation 

func NewPermutation(id ifaces.QueryID, a, b [][]ifaces.Column) Permutation

NewPermutation constructs a new permutation query and performs all the well-formedness sanity-checks. In case of failure, it will panic.

func (Permutation) Check 

func (r Permutation) Check(run ifaces.Runtime) error

Check probabilistically checks whether the permutation predicates holds. The test works by incrementally computes the products: 

\prod_i (\gamma + \sum_j C{i, j} \alpha^j)

With overhelming probability, if the predicate is wrong then then the products will be unequal and this will be equal if the predicate is satisfied.

func (Permutation) CheckGnark 

func (p Permutation) CheckGnark(api frontend.API, run ifaces.GnarkRuntime)

GnarkCheck will panic in this construction because we do not have a good way to check the query within a circuit

func (Permutation) Name 

func (r Permutation) Name() ifaces.QueryID

Name implements the ifaces.Query interface

type Range 

type Range struct {
	ID ifaces.QueryID
	// Maybe we should enforce that the handle is a natural one here
	Handle ifaces.Column
	// Upper-bound
	B int
}

Enforces a range constraint, that all elements in the handle must be within range [0, B)

Where B is a power of two

func NewRange 

func NewRange(id ifaces.QueryID, h ifaces.Column, b int) Range

Constructor for range constraints also makes the input validation

func (Range) Check 

func (r Range) Check(run ifaces.Runtime) error

Test that the range checks hold

func (Range) CheckGnark 

func (r Range) CheckGnark(api frontend.API, run ifaces.GnarkRuntime)

CheckGnark will panic in this construction because we do not have a good way to check the query within a circuit

func (Range) Name 

func (r Range) Name() ifaces.QueryID

Name implements the ifaces.Query interface

type UnivariateEval 

type UnivariateEval struct {
	Pols    []ifaces.Column
	QueryID ifaces.QueryID
}

Multiple polynomials, one point

func NewUnivariateEval 

func NewUnivariateEval(id ifaces.QueryID, pols ...ifaces.Column) UnivariateEval

Constructor for univariate evaluation queries The list of polynomial must be deduplicated.

func (UnivariateEval) Check 

func (r UnivariateEval) Check(run ifaces.Runtime) error

Test that the polynomial evaluation holds

func (UnivariateEval) CheckGnark 

func (r UnivariateEval) CheckGnark(api frontend.API, run ifaces.GnarkRuntime)

Test that the polynomial evaluation holds

func (UnivariateEval) GnarkAllocate 

func (p UnivariateEval) GnarkAllocate() GnarkUnivariateEvalParams

func (UnivariateEval) Name 

func (r UnivariateEval) Name() ifaces.QueryID

Name implements the ifaces.Query interface

type UnivariateEvalParams 

type UnivariateEvalParams struct {
	X  field.Element
	Ys []field.Element
}

Parameters for an univariate evaluation

func NewUnivariateEvalParams 

func NewUnivariateEvalParams(x field.Element, ys ...field.Element) UnivariateEvalParams

Constructor for non-fixed point univariate evaluation query parameters

func (UnivariateEvalParams) GnarkAssign 

func (p UnivariateEvalParams) GnarkAssign() GnarkUnivariateEvalParams

Returns a gnark assignment for the present parameters

func (UnivariateEvalParams) UpdateFS 

func (p UnivariateEvalParams) UpdateFS(state *fiatshamir.State)

Update the fiat-shamir state with the alleged evaluations. We assume that the verifer always computes the values of X upfront on his own. Therefore there is no need to include them in the FS.

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.