Type Definition kimchi::circuits::expr::Expr

pub type Expr<C, Column> = Operations<ExprInner<C, Column>>;

An multi-variate polynomial over the base ring C with variables

• Cell(v) for v : Variable
• VanishesOnZeroKnowledgeAndPreviousRows
• UnnormalizedLagrangeBasis(i) for i : i32

This represents a PLONK “custom constraint”, which enforces that the corresponding combination of the polynomials corresponding to the above variables should vanish on the PLONK domain.

Implementations

impl<C, Column> Expr<C, Column>

pub fn cell(col: Column, row: CurrOrNext) -> Expr<C, Column>

Convenience function for constructing cell variables.

pub fn double(self) -> Self

pub fn square(self) -> Self

pub fn constant(c: C) -> Expr<C, Column>

Convenience function for constructing constant expressions.

pub fn degree(&self, d1_size: u64, zk_rows: u64) -> u64

Return the degree of the expression. The degree of a cell is defined by the first argument d1_size, a constant being of degree zero. The degree of the expression is defined recursively using the definition of the degree of a multivariate polynomial. The function can be (and is) used to compute the domain size, hence the name of the first argument d1_size. The second parameter zk_rows is used to define the degree of the constructor VanishesOnZeroKnowledgeAndPreviousRows.

impl<'a, F: Field, Column: PartialEq + Copy, ChallengeTerm: AlphaChallengeTerm<'a>> Expr<ConstantExpr<F, ChallengeTerm>, Column>

pub fn literal(x: F) -> Self

Convenience function for constructing expressions from literal field elements.

pub fn combine_constraints( alphas: impl Iterator<Item = u32>, cs: Vec<Self> ) -> Self

Combines multiple constraints [c0, ..., cn] into a single constraint alpha^alpha0 * c0 + alpha^{alpha0 + 1} * c1 + ... + alpha^{alpha0 + n} * cn.

impl<F: FftField, Column: Copy, ChallengeTerm: Copy> Expr<ConstantExpr<F, ChallengeTerm>, Column>

pub fn to_polish(&self) -> Vec<PolishToken<F, Column, ChallengeTerm>>

Compile an expression to an RPN expression.

impl<F: FftField, Column: PartialEq + Copy, ChallengeTerm: Copy> Expr<ConstantExpr<F, ChallengeTerm>, Column>

pub fn evaluate<'a, Evaluations: ColumnEvaluations<F, Column = Column>, Challenge: Index<ChallengeTerm, Output = F>, Environment: ColumnEnvironment<'a, F, ChallengeTerm, Challenge, Column = Column>>( &self, d: D<F>, pt: F, evals: &Evaluations, env: &Environment ) -> Result<F, ExprError<Column>>

Evaluate an expression as a field element against an environment.

pub fn evaluate_<Evaluations: ColumnEvaluations<F, Column = Column>>( &self, d: D<F>, pt: F, evals: &Evaluations, c: &Constants<F>, chals: &dyn Index<ChallengeTerm, Output = F> ) -> Result<F, ExprError<Column>>

Evaluate an expression as a field element against the constants.

pub fn evaluate_constants<'a, Challenge: Index<ChallengeTerm, Output = F>, Environment: ColumnEnvironment<'a, F, ChallengeTerm, Challenge, Column = Column>>( &self, env: &Environment ) -> Expr<F, Column>

Evaluate the constant expressions in this expression down into field elements.

pub fn evaluations<'a, Challenge: Index<ChallengeTerm, Output = F>, Environment: ColumnEnvironment<'a, F, ChallengeTerm, Challenge, Column = Column>>( &self, env: &Environment ) -> Evaluations<F, D<F>>

Compute the polynomial corresponding to this expression, in evaluation form. The routine will first replace the constants (verifier challenges and constants like the matrix used by Poseidon) in the expression with their respective values using evaluate_constants and will after evaluate the monomials with the corresponding column values using the method evaluations.

impl<F: FftField, Column: Copy> Expr<F, Column>

pub fn evaluate<Evaluations: ColumnEvaluations<F, Column = Column>>( &self, d: D<F>, pt: F, zk_rows: u64, evals: &Evaluations ) -> Result<F, ExprError<Column>>

Evaluate an expression into a field element.

pub fn evaluations<'a, ChallengeTerm, Challenge: Index<ChallengeTerm, Output = F>, Environment: ColumnEnvironment<'a, F, ChallengeTerm, Challenge, Column = Column>>( &self, env: &Environment ) -> Evaluations<F, D<F>>

Compute the polynomial corresponding to this expression, in evaluation form.

impl<F: Neg<Output = F> + Clone + One + Zero + PartialEq, Column: Ord + Copy + Hash> Expr<F, Column>where ExprInner<F, Column>: Literal, <ExprInner<F, Column> as Literal>::F: Field,

pub fn linearize( &self, evaluated: HashSet<Column> ) -> Result<Linearization<Expr<F, Column>, Column>, ExprError<Column>>

There is an optimization in PLONK called “linearization” in which a certain polynomial is expressed as a linear combination of other polynomials in order to reduce the number of evaluations needed in the IOP (by relying on the homomorphic property of the polynomial commitments used.)

The function performs this “linearization”, which we now describe in some detail.

In mathematical language, an expression e: Expr<F> is an element of the polynomial ring F[V], where V is a set of variables.

Given a subset V_0 of V (and letting V_1 = V \setminus V_0), there is a map factor_{V_0}: F[V] -> (F[V_1])[V_0]. That is, polynomials with F coefficients in the variables V = V_0 \cup V_1 are the same thing as polynomials with F[V_1] coefficients in variables V_0.

There is also a function lin_or_err : (F[V_1])[V_0] -> Result<Vec<(V_0, F[V_1])>, &str>

which checks if the given input is in fact a degree 1 polynomial in the variables V_0 (i.e., a linear combination of V_0 elements with F[V_1] coefficients) returning this linear combination if so.

Given an expression e and set of columns C_0, letting V_0 = { Variable { col: c, row: r } | c in C_0, r in { Curr, Next } }, this function computes lin_or_err(factor_{V_0}(e)), although it does not compute it in that way. Instead, it computes it by reducing the expression into a sum of monomials with F coefficients, and then factors the monomials.

impl<'a, F, Column: FormattedOutput + Debug + Clone, ChallengeTerm> Expr<ConstantExpr<F, ChallengeTerm>, Column>where F: PrimeField, ChallengeTerm: AlphaChallengeTerm<'a>,

pub fn latex_str(&self) -> Vec<String>

Converts the expression in LaTeX

Trait Implementations

impl<F: Zero + Clone, Column: Clone> AddAssign<Operations<ExprInner<F, Column>>> for Expr<F, Column>where ExprInner<F, Column>: Literal, <ExprInner<F, Column> as Literal>::F: Field,

fn add_assign(&mut self, other: Self)

Performs the += operation.

impl<'a, F, Column: FormattedOutput + Debug + Clone, ChallengeTerm> Display for Expr<ConstantExpr<F, ChallengeTerm>, Column>where F: PrimeField, ChallengeTerm: AlphaChallengeTerm<'a>,

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<F> ExprOps<F, BerkeleyChallengeTerm> for Expr<ConstantExpr<F, BerkeleyChallengeTerm>, Column>where F: PrimeField, Expr<ConstantExpr<F, BerkeleyChallengeTerm>, Column>: Display,

fn two_pow(pow: u64) -> Self

2^pow

fn two_to_limb() -> Self

2^{LIMB_BITS}

fn two_to_2limb() -> Self

2^{2 * LIMB_BITS}

fn two_to_3limb() -> Self

2^{3 * LIMB_BITS}

fn double(&self) -> Self

Double the value

fn square(&self) -> Self

Compute the square of this value

fn pow(&self, p: u64) -> Self

Raise the value to the given power

fn boolean(&self) -> Self

Constrain to boolean

fn crumb(&self) -> Self

Constrain to crumb (i.e. two bits)

fn literal(x: F) -> Self

Create a literal

fn witness(row: CurrOrNext, col: usize, _: Option<&ArgumentData<F>>) -> Self

fn coeff(col: usize, _: Option<&ArgumentData<F>>) -> Self

Coefficient

fn constant( expr: ConstantExpr<F, BerkeleyChallengeTerm>, _: Option<&ArgumentData<F>> ) -> Self

Create a constant

fn cache(&self, cache: &mut Cache) -> Self

Cache item

impl<'a, F, Column: FormattedOutput + Debug + Clone, ChallengeTerm> FormattedOutput for Expr<ConstantExpr<F, ChallengeTerm>, Column>where F: PrimeField, ChallengeTerm: AlphaChallengeTerm<'a>,

fn ocaml( &self, cache: &mut HashMap<CacheId, Expr<ConstantExpr<F, ChallengeTerm>, Column>> ) -> String

Converts the expression in OCaml code Recursively print the expression, except for the cached expression that are stored in the cache.

fn text( &self, cache: &mut HashMap<CacheId, Expr<ConstantExpr<F, ChallengeTerm>, Column>> ) -> String

Recursively print the expression, except for the cached expression that are stored in the cache.

fn is_alpha(&self) -> bool

fn latex( &self, cache: &mut HashMap<CacheId, Expr<ConstantExpr<F, ChallengeTerm>, Column>> ) -> String

impl<'a, F, Column, ChallengeTerm: AlphaChallengeTerm<'a>> From<ChallengeTerm> for Expr<ConstantExpr<F, ChallengeTerm>, Column>

fn from(x: ChallengeTerm) -> Self

Converts to this type from the input type.

impl<'a, F, Column, ChallengeTerm: AlphaChallengeTerm<'a>> From<ConstantTerm<F>> for Expr<ConstantExpr<F, ChallengeTerm>, Column>

fn from(x: ConstantTerm<F>) -> Self

Converts to this type from the input type.

impl<F, Column, ChallengeTerm> From<Operations<ConstantExprInner<F, ChallengeTerm>>> for Expr<ConstantExpr<F, ChallengeTerm>, Column>

fn from(x: ConstantExpr<F, ChallengeTerm>) -> Self

Converts to this type from the input type.

impl<'a, F: Field, Column, ChallengeTerm: AlphaChallengeTerm<'a>> From<u64> for Expr<ConstantExpr<F, ChallengeTerm>, Column>

fn from(x: u64) -> Self

Converts to this type from the input type.

impl<F: Field, Column> From<u64> for Expr<F, Column>

fn from(x: u64) -> Self

Converts to this type from the input type.

impl<'a, F: Field, Column: PartialEq + Copy, ChallengeTerm: AlphaChallengeTerm<'a>> Mul<F> for Expr<ConstantExpr<F, ChallengeTerm>, Column>

type Output = Operations<ExprInner<Operations<ConstantExprInner<F, ChallengeTerm>>, Column>>

The resulting type after applying the * operator.

fn mul(self, y: F) -> Self::Output

Performs the * operation.

impl<F, Column> MulAssign<Operations<ExprInner<F, Column>>> for Expr<F, Column>where F: Zero + One + PartialEq + Clone, Column: PartialEq + Clone, ExprInner<F, Column>: Literal, <ExprInner<F, Column> as Literal>::F: Field,

fn mul_assign(&mut self, other: Self)

Performs the *= operation.