Struct Expression 

pub struct Expression<F: Field, E: ExpressionType<F>> {
    pub expression_node: ExpressionNode<F, E>,
    pub mle_vec: E::MleVec,
}

The high-level idea is that an Expression is generic over ExpressionType , and contains within it a single parent ExpressionNode as well as an ExpressionType::MleVec containing the unique leaf representations for the leaves of the ExpressionNode tree.

Fields

expression_node: ExpressionNode<F, E>

The root of the expression “tree”.

mle_vec: E::MleVec

The unique owned copies of all MLEs which are “leaves” within the expression “tree”.

Implementations

impl<F: Field> Expression<F, ExprDescription>

pub fn bind( &self, point: &[F], transcript_reader: &mut impl VerifierTranscript<F>, ) -> Result<Expression<F, VerifierExpr>>

Binds the variables of this expression to point, and retrieves the leaf MLE values from the transcript_reader. Returns a Expression<F, VerifierExpr> version of self.

pub fn from_mle_desc(mle_desc: MleDescription<F>) -> Self

Convenience function which creates a trivial Expression<F, ExprDescription> referring to a single MLE.

pub fn get_all_nonlinear_rounds(&self) -> Vec<usize>

Traverses the expression tree to get the indices of all the nonlinear rounds. Returns a sorted vector of indices.

pub fn get_all_rounds(&self) -> Vec<usize>

Traverses the expression tree to return all indices within the expression. Can only be used after indexing the expression.

pub fn get_circuit_mles(&self) -> Vec<&MleDescription<F>>

Get the MleDescriptions for this expression, which are at the leaves of the expression.

pub fn index_mle_vars(&mut self, start_index: usize)

Label the free variables in an expression.

pub fn into_prover_expression( &self, circuit_map: &CircuitEvalMap<F>, ) -> Expression<F, ProverExpr>

Get the Expression<F, ProverExpr> corresponding to this Expression<F, ExprDescription> using the associated data in the CircuitEvalMap.

pub fn get_post_sumcheck_layer( &self, multiplier: F, challenges: &[F], ) -> PostSumcheckLayer<F, Option<F>>

Get the PostSumcheckLayer for this expression, which represents the fully bound values of the expression. Relevant for the Hyrax IP, where we need commitments to fully bound MLEs as well as their intermediate products.

pub fn get_max_degree(&self) -> usize

Get the maximum degree of any variable in this expression.

pub fn get_round_degree(&self, curr_round: usize) -> usize

Returns the maximum degree of b_{curr_round} within an expression (and therefore the number of prover messages we need to send)

impl<F: Field> Expression<F, ExprDescription>

pub fn num_vars(&self) -> usize

Returns the total number of variables (i.e. number of rounds of sumcheck) within the MLE representing the output “data” of this particular expression.

Note that unlike within the AbstractExpr case, we don’t need to return a Result since all MLEs within a ExprDescription are instantiated with their appropriate number of variables.

pub fn products(circuit_mle_descs: Vec<MleDescription<F>>) -> Self

Creates an Expression<F, ExprDescription> which describes the polynomial relationship

circuit_mle_descs[0](x_1, ..., x_{n_0}) * circuit_mle_descs[1](x_1, ..., x_{n_1}) * ...

pub fn select(self, rhs: Expression<F, ExprDescription>) -> Self

Creates an Expression<F, ExprDescription> which describes the polynomial relationship (1 - x_0) * Self(x_1, ..., x_{n_lhs}) + b_0 * rhs(x_1, ..., x_{n_rhs})

NOTE that by default, performing a select() over an LHS and an RHS with different numbers of variables will create a selector tree such that the side with fewer variables always falls down the left-most side of that subtree.

For example, if we are calling select() on two MLEs, V_i(x_0, …, x_4) and V_i(x_0, …, x_6) then the resulting expression will have a single top-level selector, and will forcibly move the first MLE (with two fewer variables) to the left-most subtree with 5 variables: (1 - x_0) * (1 - x_1) * (1 - x_2) * V_i(x_3, …, x_7) + x_0 * V_i(x_1, …, x_7)

pub fn binary_tree_selector(expressions: Vec<Self>) -> Self

Create a nested selector Expression that selects between 2^k Expressions by creating a binary tree of Selector Expressions. The order of the leaves is the order of the input expressions. (Note that this is very different from calling Self::select consecutively.)

pub fn constant(constant: F) -> Self

Literally just constant as a term, but as an “Expression”

pub fn negated(expression: Self) -> Self

Literally just -expression, as an “Expression”

pub fn sum(lhs: Self, rhs: Self) -> Self

Literally just lhs + rhs, as an “Expression”

pub fn scaled(expression: Expression<F, ExprDescription>, scale: F) -> Self

scales an Expression by a field element

impl<F: Field, E: ExpressionType<F>> Expression<F, E>

generic methods shared across all types of expressions

pub fn new(expression_node: ExpressionNode<F, E>, mle_vec: E::MleVec) -> Self

Create a new expression

pub fn deconstruct_ref(&self) -> (&ExpressionNode<F, E>, &E::MleVec)

Returns a reference to the internal expression_node and mle_vec fields.

pub fn deconstruct_mut(&mut self) -> (&mut ExpressionNode<F, E>, &mut E::MleVec)

Returns a mutable reference to the expression_node and mle_vec present within the given Expression.

pub fn deconstruct(self) -> (ExpressionNode<F, E>, E::MleVec)

Takes ownership of the Expression and returns the owned values to its internal expression_node and mle_vec.

pub fn traverse( &self, observer_fn: &mut impl FnMut(&ExpressionNode<F, E>, &E::MleVec) -> Result<()>, ) -> Result<()>

traverse the expression tree, and applies the observer_fn to all child node because the expression node has the recursive structure, the traverse_node helper function is implemented on it, with the mle_vec reference passed in

pub fn traverse_mut( &mut self, observer_fn: &mut impl FnMut(&mut ExpressionNode<F, E>, &mut E::MleVec) -> Result<()>, ) -> Result<()>

similar to traverse, but allows mutation of self (expression node and mle_vec)

impl<F: Field> Expression<F, ProverExpr>

this is what the prover manipulates to prove the correctness of the computation. Methods here include ones to fix bits, evaluate sumcheck messages, etc.

pub fn select(self, rhs: Expression<F, ProverExpr>) -> Self

See documentation in super::circuit_expr::ExprDescription’s select() function for more details!

pub fn pow(pow: usize, mle: DenseMle<F>) -> Self

Create a product Expression that raises one MLE to a given power

pub fn products(product_list: <ProverExpr as ExpressionType<F>>::MleVec) -> Self

Create a product Expression that multiplies many MLEs together

pub fn mle(mle: DenseMle<F>) -> Self

Create a mle Expression that contains one MLE

pub fn constant(constant: F) -> Self

Create a constant Expression that contains one field element

pub fn negated(expression: Self) -> Self

negates an Expression

pub fn sum(lhs: Self, rhs: Self) -> Self

Create a Sum Expression that contains two MLEs

pub fn scaled(expression: Expression<F, ProverExpr>, scale: F) -> Self

scales an Expression by a field element

pub fn num_mle(&self) -> usize

returns the number of MleRefs in the expression

pub fn increment_mle_vec_indices(&mut self, offset: usize)

which increments all the MleVecIndex in the expression by param amount

pub fn transform_to_verifier_expression( self, ) -> Result<Expression<F, VerifierExpr>>

Transforms the prover expression to a verifier expression.

Should only be called when the entire expression is fully bound.

Traverses the expression and changes the DenseMle to VerifierMle, by grabbing their bookkeeping table’s 1st and only element.

If the bookkeeping table has more than 1 element, it throws an ExpressionError::EvaluateNotFullyBoundError

pub fn fix_variable(&mut self, round_index: usize, challenge: F)

fix the variable at a certain round index, always MSB index

pub fn fix_variable_at_index(&mut self, round_index: usize, challenge: F)

fix the variable at a certain round index, arbitrary index

pub fn evaluate_expr(&mut self, challenges: Vec<F>) -> Result<F>

evaluates an expression on the given challenges points, by fixing the variables

pub fn evaluate_sumcheck_beta_cascade( &self, beta: &[&BetaValues<F>], random_coefficients: &[F], round_index: usize, degree: usize, ) -> SumcheckEvals<F>

This evaluates a sumcheck message using the beta cascade algorithm by calling it on the root node of the expression tree. This assumes that there is an independent variable in the expression, which is the round_index.

pub fn evaluate_sumcheck_node_beta_cascade_sum( &self, beta_values: &BetaValues<F>, round_index: usize, degree: usize, ) -> SumcheckEvals<F>

This evaluates a sumcheck message using the beta cascade algorithm, taking the sum of the expression over all the variables round_index and after. For the variables before, we compute the fully bound beta equality MLE and scale the rest of the sum by this value.

pub fn get_all_rounds(&self) -> Vec<usize>

Traverses the expression tree to return all indices within the expression. Can only be used after indexing the expression.

pub fn get_all_nonlinear_rounds(&self) -> Vec<usize>

this traverses the expression tree to get all of the nonlinear rounds. can only be used after indexing the expression. returns the indices sorted.

pub fn get_all_linear_rounds(&self) -> Vec<usize>

this traverses the expression tree to get all of the linear rounds. can only be used after indexing the expression. returns the indices sorted.

pub fn index_mle_indices(&mut self, curr_index: usize) -> usize

Mutate the MLE indices that are MleIndex::Free in the expression and turn them into MleIndex::Indexed. Returns the max number of bits that are indexed.

pub fn get_expression_num_free_variables(&self) -> usize

Gets the number of free variables in an expression.

pub fn get_post_sumcheck_layer(&self, multiplier: F) -> PostSumcheckLayer<F, F>

Get the PostSumcheckLayer for this expression, which represents the fully bound values of the expression. Relevant for the Hyrax IP, where we need commitments to fully bound MLEs as well as their intermediate products.

pub fn get_max_degree(&self) -> usize

Get the maximum degree of any variable in htis expression

impl<F: Field> Expression<F, VerifierExpr>

pub fn mle(mle: VerifierMle<F>) -> Self

Create a mle Expression that contains one MLE

pub fn evaluate(&self) -> Result<F>

Evaluate this fully bound expression.

pub fn get_all_nonlinear_rounds(&mut self) -> Vec<usize>

Traverses the expression tree to get the indices of all the nonlinear rounds. Returns a sorted vector of indices.

Trait Implementations

impl<F: Field> Add for Expression<F, ExprDescription>

implement the Add, Sub, and Mul traits for the Expression

type Output = Expression<F, ExprDescription>

The resulting type after applying the + operator.

fn add( self, rhs: Expression<F, ExprDescription>, ) -> Expression<F, ExprDescription>

Performs the + operation.

impl<F: Field> Add for Expression<F, ProverExpr>

implement the Add, Sub, and Mul traits for the Expression

type Output = Expression<F, ProverExpr>

The resulting type after applying the + operator.

fn add(self, rhs: Expression<F, ProverExpr>) -> Expression<F, ProverExpr>

Performs the + operation.

impl<F: Clone + Field, E: Clone + ExpressionType<F>> Clone for Expression<F, E>

where E::MleVec: Clone,

fn clone(&self) -> Expression<F, E>

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl<F: Debug + Field> Debug for Expression<F, ExprDescription>

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

Formats the value using the given formatter.

impl<F: Debug + Field> Debug for Expression<F, ProverExpr>

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

Formats the value using the given formatter.

impl<F: Debug + Field> Debug for Expression<F, VerifierExpr>

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

Formats the value using the given formatter.

impl<'de, F, E: ExpressionType<F>> Deserialize<'de> for Expression<F, E>

where F: Field,

fn deserialize<__D>(__deserializer: __D) -> Result<Self, __D::Error>

where __D: Deserializer<'de>,

Deserialize this value from the given Serde deserializer.

impl<F: Hash + Field, E: Hash + ExpressionType<F>> Hash for Expression<F, E>

where E::MleVec: Hash,

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<F: Field> Mul<F> for Expression<F, ExprDescription>

type Output = Expression<F, ExprDescription>

The resulting type after applying the * operator.

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

Performs the * operation.

impl<F: Field> Mul<F> for Expression<F, ProverExpr>

type Output = Expression<F, ProverExpr>

The resulting type after applying the * operator.

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

Performs the * operation.

impl<F: Field> Neg for Expression<F, ExprDescription>

type Output = Expression<F, ExprDescription>

The resulting type after applying the - operator.

fn neg(self) -> Self::Output

Performs the unary - operation.

impl<F: Field> Neg for Expression<F, ProverExpr>

type Output = Expression<F, ProverExpr>

The resulting type after applying the - operator.

fn neg(self) -> Self::Output

Performs the unary - operation.

impl<F, E: ExpressionType<F>> Serialize for Expression<F, E>

where F: Field,

fn serialize<__S>(&self, __serializer: __S) -> Result<__S::Ok, __S::Error>

where __S: Serializer,

Serialize this value into the given Serde serializer.

impl<F: Field> Sub for Expression<F, ExprDescription>

type Output = Expression<F, ExprDescription>

The resulting type after applying the - operator.

fn sub( self, rhs: Expression<F, ExprDescription>, ) -> Expression<F, ExprDescription>

Performs the - operation.

impl<F: Field> Sub for Expression<F, ProverExpr>

type Output = Expression<F, ProverExpr>

The resulting type after applying the - operator.

fn sub(self, rhs: Expression<F, ProverExpr>) -> Expression<F, ProverExpr>

Performs the - operation.