Enum kimchi::circuits::expr::Operations

pub enum Operations<T> {
    Atom(T),
    Pow(Box<Self>, u64),
    Add(Box<Self>, Box<Self>),
    Mul(Box<Self>, Box<Self>),
    Sub(Box<Self>, Box<Self>),
    Double(Box<Self>),
    Square(Box<Self>),
    Cache(CacheId, Box<Self>),
    IfFeature(FeatureFlag, Box<Self>, Box<Self>),
}

Variants

Atom(T)

Pow(Box<Self>, u64)

Add(Box<Self>, Box<Self>)

Mul(Box<Self>, Box<Self>)

Sub(Box<Self>, Box<Self>)

Double(Box<Self>)

Square(Box<Self>)

Cache(CacheId, Box<Self>)

IfFeature(FeatureFlag, Box<Self>, Box<Self>)

Implementations

impl<T: Literal> Operations<T>where T::F: Field,

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

Exponentiate a constant expression.

impl<F: Field, ChallengeTerm: Copy> Operations<ConstantExprInner<F, ChallengeTerm>>

pub fn value( &self, c: &Constants<F>, chals: &dyn Index<ChallengeTerm, Output = F> ) -> F

Evaluate the given constant expression to a field element.

impl<T: Literal + PartialEq> Operations<T>where T::F: Field,

pub fn apply_feature_flags(&self, features: &FeatureFlags) -> Self

impl<C, Column> Operations<ExprInner<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>> Operations<ExprInner<Operations<ConstantExprInner<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> Operations<ExprInner<Operations<ConstantExprInner<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> Operations<ExprInner<Operations<ConstantExprInner<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> Operations<ExprInner<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> Operations<ExprInner<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> Operations<ExprInner<Operations<ConstantExprInner<F, ChallengeTerm>>, Column>>where F: PrimeField, ChallengeTerm: AlphaChallengeTerm<'a>,

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

Converts the expression in LaTeX

Trait Implementations

impl<T: Literal> Add<Operations<T>> for Operations<T>where T::F: Field,

type Output = Operations<T>

The resulting type after applying the + operator.

fn add(self, other: Self) -> Self

Performs the + operation.

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<T: Clone> Clone for Operations<T>

fn clone(&self) -> Operations<T>

Returns a copy of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<T: Debug> Debug for Operations<T>

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

Formats the value using the given formatter.

impl<T: FormattedOutput + Clone> FormattedOutput for Operations<T>

fn is_alpha(&self) -> bool

fn ocaml(&self, cache: &mut HashMap<CacheId, Self>) -> String

fn latex(&self, cache: &mut HashMap<CacheId, Self>) -> String

fn text(&self, cache: &mut HashMap<CacheId, Self>) -> String

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<T> From<T> for Operations<T>

fn from(x: T) -> Self

Converts to this type from the input type.

impl<T: Hash> Hash for Operations<T>

fn hash<__H: Hasher>(&self, state: &mut __H)

Feeds this value into the given Hasher.

fn hash_slice<H>(data: &[Self], state: &mut H)where H: Hasher, Self: Sized,

Feeds a slice of this type into the given Hasher.

impl<T: Literal + Clone> Literal for Operations<T>

type F = <T as Literal>::F

fn literal(x: Self::F) -> Self

fn to_literal(self) -> Result<Self::F, Self>

fn to_literal_ref(&self) -> Option<&Self::F>

fn as_literal(&self, constants: &Constants<Self::F>) -> Self

Obtains the representation of some constants as a literal. This is useful before converting Kimchi expressions with constants to folding compatible expressions.

impl<T: Literal + PartialEq> Mul<Operations<T>> for Operations<T>where T::F: Field,

type Output = Operations<T>

The resulting type after applying the * operator.

fn mul(self, other: Self) -> Self

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.

impl<T: Literal> Neg for Operations<T>where T::F: One + Neg<Output = T::F> + Copy,

type Output = Operations<T>

The resulting type after applying the - operator.

fn neg(self) -> Self

Performs the unary - operation.

impl<T: Literal + PartialEq> One for Operations<T>where T::F: Field,

fn one() -> Self

Returns the multiplicative identity element of Self, 1.

fn is_one(&self) -> bool

Returns true if self is equal to the multiplicative identity.

fn set_one(&mut self)

Sets self to the multiplicative identity element of Self, 1.

impl<T: PartialEq> PartialEq<Operations<T>> for Operations<T>

fn eq(&self, other: &Operations<T>) -> bool

This method tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &Rhs) -> bool

This method tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl<T: Literal> Sub<Operations<T>> for Operations<T>where T::F: Field,

type Output = Operations<T>

The resulting type after applying the - operator.

fn sub(self, other: Self) -> Self

Performs the - operation.

impl<T: Literal> Zero for Operations<T>where T::F: Field,

fn zero() -> Self

Returns the additive identity element of Self, 0.

fn is_zero(&self) -> bool

Returns true if self is equal to the additive identity.

fn set_zero(&mut self)

Sets self to the additive identity element of Self, 0.

impl<T: Eq> Eq for Operations<T>

impl<T> StructuralEq for Operations<T>

impl<T> StructuralPartialEq for Operations<T>