Module expression 

This module describes the “regular”-style polynomial relationships described within https://eprint.iacr.org/2013/351.pdf, Theorem 1 on page 25.

Specifically, polynomial relationships between GKR circuit layers which look like the following:

\widetilde{V}i(x_1, …, x_n) = \sum{b_1, …, b_n} \widetilde{\beta}(b, x) Expr(b_1, …, b_n)

Where $Expr(b_1, …, b_n)$ is comprised of one or more of the following: (read as a CFG; see documentation within generic_expr::ExpressionNode)

Note that all expressions are written in “expanded” form, such that all MLEs which are multiplied together appear next to one another in the expression, i.e. all distribution over the sum of other MLEs has already been performed.

As an example, the “data” relationship described by V_{i + 1}(b_1, …, b_n) * (V_{i + 1}(b_1, …, b_n) + V_{i + 2}(b_1, …, b_n)) is inexpressible using the functionality within crate::expression. Rather, it would be written as the (mathematically equivalent) V_{i + 1}(b_1, …, b_n) * V_{i + 1}(b_1, …, b_n) + V_{i + 1}(b_1, …, b_n) * V_{i + 2}(b_1, …, b_n)

Expressions are constructed as a tree of generic_expr::ExpressionNodes. Note that there are four “phases” to the “life cycle” of an expression, i.e. the changes it goes through during the circuit-building process (see documentation for this under under TODO(vishady): write documentation for the compilation process):

• circuit_expr::ExprDescription: The “circuit description” view of an expression. In particular, it describes the polynomial relationship between the MLE representing the data output of a particular layer against MLEs representing data “slices” within other layers, and contains information about the expression “structure” (in the form of the expansion of the CFG description from above), with the leaves of the expression tree always being generic_expr::ExpressionNode::Constants or generic_expr::ExpressionNode::Mles or generic_expr::ExpressionNode::Products.
• prover_expr::ProverExpr: The prover’s view of an expression. It contains all the information within circuit_expr::ExprDescription, but contains crate::mle::dense::DenseMles rather than crate::mle::mle_description::MleDescriptions.
• verifier_expr::VerifierExpr: The verifier’s view of an expression. It contains all the information within circuit_expr::ExprDescription, but contains crate::mle::verifier_mle::VerifierMles rather than crate::mle::mle_description::MleDescriptions.

Modules

circuit_expr

The “pure” polynomial relationship description between the MLE representing a single layer of a “structured” circuit and those representing data from other layers. See documentation in crate::expression for more details.

expr_errors

generic_expr

Functionality which is common to all “expression“s (see documentation within crate::expression). See documentation in Expression for high-level summary.

prover_expr

The prover’s view of an Expression – see file-level documentation within crate::expression for more details.

verifier_expr

The verifier’s “view” of a “fully-bound” polynomial relationship between an output layer and those of its inputs (see documentation within crate::expression for more general information).