Enum ExpressionNode 

pub enum ExpressionNode<F: Field, E: ExpressionType<F>> {
    Constant(F),
    Selector(MleIndex<F>, Box<ExpressionNode<F, E>>, Box<ExpressionNode<F, E>>),
    Mle(E::MLENodeRepr),
    Sum(Box<ExpressionNode<F, E>>, Box<ExpressionNode<F, E>>),
    Product(Vec<E::MLENodeRepr>),
    Scaled(Box<ExpressionNode<F, E>>, F),
}

ExpressionNode can be made up of the following:

• ExpressionNode::Constant, i.e. + c for c \in \mathbb{F}
• ExpressionNode::Mle, i.e. \widetilde{V}{j > i}(b_1, …, b{m \leq n})
• ExpressionNode::Product, i.e. \prod_j \widetilde{V}{j > i}(b_1, …, b{m \leq n})
• ExpressionNode::Selector, i.e. (1 - b_0) * Expr(b_1, …, b_{m \leq n}) + b_0 * Expr(b_1, …, b_{m \leq n})
• ExpressionNode::Sum, i.e. \widetilde{V}{j_1 > i}(b_1, …, b{m_1 \leq n}) + \widetilde{V}{j_2 > i}(b_1, …, b{m_2 \leq n})
• ExpressionNode::Scaled, i.e. c * Expr(b_1, …, b_{m \leq n}) for c \in mathbb{F}

Variants

Constant(F)

See documentation for ExpressionNode. Note that ExpressionNode::Constant can be an expression tree’s leaf.

Selector(MleIndex<F>, Box<ExpressionNode<F, E>>, Box<ExpressionNode<F, E>>)

See documentation for ExpressionNode.

Mle(E::MLENodeRepr)

An ExpressionNode representing the leaf of an expression tree which is actually mathematically defined as a multilinear extension.

Sum(Box<ExpressionNode<F, E>>, Box<ExpressionNode<F, E>>)

See documentation for ExpressionNode.

Product(Vec<E::MLENodeRepr>)

The product of several multilinear extension functions. This is also an expression tree’s leaf.

Scaled(Box<ExpressionNode<F, E>>, F)

See documentation for ExpressionNode.

Implementations

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

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

Turn this expression into a VerifierExpr which represents a fully bound expression. Should only be applicable after a full layer of sumcheck.

pub fn compute_bookkeeping_table( &self, circuit_map: &CircuitEvalMap<F>, ) -> Option<MultilinearExtension<F>>

Compute the expression-wise bookkeeping table (coefficients of the MLE representing the expression) for a given ExprDescription. This uses a CircuitEvalMap in order to grab the correct data corresponding to the MleDescription.

pub fn reduce<T>( &self, constant: &mut impl FnMut(F) -> T, selector_column: &mut impl FnMut(&MleIndex<F>, T, T) -> T, mle_eval: &mut impl FnMut(&<ExprDescription as ExpressionType<F>>::MLENodeRepr) -> T, sum: &mut impl FnMut(T, T) -> T, product: &mut impl FnMut(&[<ExprDescription as ExpressionType<F>>::MLENodeRepr]) -> T, scaled: &mut impl FnMut(T, F) -> T, ) -> T

Evaluate the polynomial using the provided closures to perform the operations.

pub fn get_all_nonlinear_rounds( &self, curr_nonlinear_indices: &mut Vec<usize>, _mle_vec: &<ExprDescription as ExpressionType<F>>::MleVec, ) -> Vec<usize>

Traverse an expression tree in order and returns a vector of indices of all the nonlinear rounds in an expression (in no particular order).

pub(crate) fn get_all_rounds( &self, curr_indices: &mut Vec<usize>, _mle_vec: &<ExprDescription as ExpressionType<F>>::MleVec, ) -> Vec<usize>

This function traverses an expression tree in order to determine what are the labels for the variables in the expression.

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

Get all the MleDescriptions, recursively, for this expression by adding the MLEs in the leaves into the vector of MleDescriptions.

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

Label the MLE indices of an expression, starting from the start_index.

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

Get the ExpressionNode<F, ProverExpr> recursively, for this expression.

pub fn get_post_sumcheck_layer( &self, multiplier: F, challenges: &[F], _mle_vec: &<VerifierExpr as ExpressionType<F>>::MleVec, ) -> PostSumcheckLayer<F, Option<F>>

Recursively get the PostSumcheckLayer for an Expression node, which is the fully bound representation of an expression. Relevant for the Hyrax IP, where we need commitments to fully bound MLEs as well as their intermediate products.

fn get_max_degree( &self, _mle_vec: &<ExprDescription as ExpressionType<F>>::MleVec, ) -> usize

Get the maximum degree of an ExpressionNode, recursively.

fn get_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.

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

Generic helper methods shared across all types of ExpressionNodes.

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

traverse the expression tree, and applies the observer_fn to all child node / the mle_vec reference

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

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

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

pub fn transform_to_verifier_expression_node( &mut self, mle_vec: &<ProverExpr as ExpressionType<F>>::MleVec, ) -> Result<ExpressionNode<F, VerifierExpr>>

Transforms the expression to a verifier expression should only be called when no variables are bound in the expression. Traverses the expression and changes the DenseMle to MleDescription.

pub fn fix_variable_node( &mut self, round_index: usize, challenge: F, mle_vec: &mut <ProverExpr as ExpressionType<F>>::MleVec, )

fix the variable at a certain round index, always the most significant index.

pub fn fix_variable_at_index_node( &mut self, round_index: usize, challenge: F, mle_vec: &mut <ProverExpr as ExpressionType<F>>::MleVec, )

fix the variable at a certain round index, can be arbitrary indices.

pub fn evaluate_sumcheck_node_beta_cascade_sum( &self, beta_values: &BetaValues<F>, round_index: usize, degree: usize, mle_vec: &<ProverExpr as ExpressionType<F>>::MleVec, ) -> SumcheckEvals<F>

pub fn evaluate_sumcheck_node_beta_cascade( &self, beta_vec: &[&BetaValues<F>], mle_vec: &<ProverExpr as ExpressionType<F>>::MleVec, random_coefficients: &[F], round_index: usize, degree: usize, ) -> SumcheckEvals<F>

This is the function to compute a single-round sumcheck message using the beta cascade algorithm.

Arguments

• expr: the Expression P defining a GKR layer. The caller is expected to have already fixed the variables of previous rounds.
• round_index: the MLE index corresponding to the variable that is going to be the independent variable for this round. The caller is expected to have already fixed variables 1 .. (round_index - 1) in expression P to the verifier’s challanges.
• max_degree: the degree of the polynomial to be exchanged in this round’s sumcheck message.
• beta_value: the beta function associated with expression exp. It is the caller’s responsibility to keep this consistent with expr before/after each call.

In particular, if round_index == k, and the current GKR layer expression was originally on n variables, expr is expected to represent a polynomial expression on n - k + 1 variables: P(r_1, r_2, ..., r_{k-1}, x_k, x_{k+1}, ..., x_n): F^{n - k + 1} -> F, with the first k - 1 free variables already fixed to random challenges r_1, ..., r_{k-1}. Similarly, beta_values should represent the polynomial: \beta(r_1, ..., r_{k-1}, b_k, ..., b_n, g_1, ..., g_n) whose unbound variables are b_k, ..., b_n.

Returns

If successful, this functions returns a representation of the univariate polynomial:

    g_{round_index}(x) =
        \sum_{b_{k+1} \in {0, 1}}
        \sum_{b_{k+2} \in {0, 1}}
            ...
        \sum_{b_{n} \in {0, 1}}
            \beta(r_1, ..., r_k, x, b_{k+1}, ..., b_{n}, g_1, ..., g_n)
                * P(r_1, ..., r_k, x, b_{k+1}, ..., b_n)

1. This function should be responsible for mutating expr and beta_values by fixing variables (if any) after the sumcheck round. It should maintain the invariant that expr and beta_values are consistent with each other!
2. max_degree should NOT be the caller’s responsibility to compute. The degree should be determined through expr and round_index. It is error-prone to allow for sumcheck message to go through with an arbitrary degree.

Beta cascade

Instead of using a beta table to linearize an expression, we utilize the fact that for each specific node in an expression tree, we only need exactly the beta values corresponding to the indices present in that node.

pub fn index_mle_indices_node( &mut self, curr_index: usize, mle_vec: &mut <ProverExpr as ExpressionType<F>>::MleVec, ) -> 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(crate) fn get_all_rounds( &self, mle_vec: &<ProverExpr as ExpressionType<F>>::MleVec, ) -> Vec<usize>

this traverses the expression to get all of the rounds, in total. requires going through each of the nodes and collecting the leaf node indices.

pub fn get_all_nonlinear_rounds( &self, mle_vec: &<ProverExpr as ExpressionType<F>>::MleVec, ) -> Vec<usize>

traverse an expression tree in order to get all of the nonlinear rounds in an expression.

pub fn get_all_linear_rounds( &self, mle_vec: &<ProverExpr as ExpressionType<F>>::MleVec, ) -> Vec<usize>

get all of the linear rounds from an expression tree

fn get_rounds_helper( &self, mle_vec: &<ProverExpr as ExpressionType<F>>::MleVec, ) -> Vec<usize>

pub fn get_expression_num_free_variables_node( &self, curr_size: usize, mle_vec: &<ProverExpr as ExpressionType<F>>::MleVec, ) -> usize

Gets the number of free variables in an expression.

pub fn get_post_sumcheck_layer( &self, multiplier: F, mle_vec: &<ProverExpr as ExpressionType<F>>::MleVec, ) -> PostSumcheckLayer<F, F>

Recursively get the PostSumcheckLayer for an Expression node, which is the fully bound representation of an expression. Relevant for the Hyrax IP, where we need commitments to fully bound MLEs as well as their intermediate products.

fn get_max_degree( &self, _mle_vec: &<ProverExpr as ExpressionType<F>>::MleVec, ) -> usize

Get the maximum degree of an ExpressionNode, recursively.

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

pub fn reduce<T>( &self, constant: &impl Fn(F) -> T, selector_column: &impl Fn(&MleIndex<F>, T, T) -> T, mle_eval: &impl Fn(&<VerifierExpr as ExpressionType<F>>::MLENodeRepr) -> T, sum: &impl Fn(T, T) -> T, product: &impl Fn(&[<VerifierExpr as ExpressionType<F>>::MLENodeRepr]) -> T, scaled: &impl Fn(T, F) -> T, ) -> T

Evaluate the polynomial using the provided closures to perform the operations.

pub fn get_all_nonlinear_rounds( &self, curr_nonlinear_indices: &mut Vec<usize>, _mle_vec: &<VerifierExpr as ExpressionType<F>>::MleVec, ) -> Vec<usize>

Traverse an expression tree in order and returns a vector of indices of all the nonlinear rounds in an expression (in no particular order).

Trait Implementations

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

where E::MLENodeRepr: Clone,

fn clone(&self) -> ExpressionNode<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 ExpressionNode<F, ExprDescription>

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

Formats the value using the given formatter.

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

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

Formats the value using the given formatter.

impl<F: Debug + Field> Debug for ExpressionNode<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 ExpressionNode<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 ExpressionNode<F, E>

where E::MLENodeRepr: 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: PartialEq + Field, E: PartialEq + ExpressionType<F>> PartialEq for ExpressionNode<F, E>

where E::MLENodeRepr: PartialEq,

fn eq(&self, other: &ExpressionNode<F, E>) -> bool

Tests for self and other values to be equal, and is used by ==.

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

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

impl<F, E: ExpressionType<F>> Serialize for ExpressionNode<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: Eq + Field, E: Eq + ExpressionType<F>> Eq for ExpressionNode<F, E>

where E::MLENodeRepr: Eq,

impl<F: Field, E: ExpressionType<F>> StructuralPartialEq for ExpressionNode<F, E>