remainder/
expression.rs

1//! This module describes the "regular"-style polynomial relationships described
2//! within <https://eprint.iacr.org/2013/351.pdf>, Theorem 1 on page 25.
3//!
4//! Specifically, polynomial relationships between GKR circuit layers which look
5//! like the following:
6//!
7//! \widetilde{V}_i(x_1, ..., x_n) = \sum_{b_1, ..., b_n} \widetilde{\beta}(b, x) Expr(b_1, ..., b_n)
8//!
9//! Where $Expr(b_1, ..., b_n)$ is comprised of one or more of the following:
10//! (read as a CFG; see documentation within [generic_expr::ExpressionNode])
11//!
12//! Note that all expressions are written in "expanded" form, such that all MLEs
13//! which are multiplied together appear next to one another in the expression,
14//! i.e. all distribution over the sum of other MLEs has already been performed.
15//!
16//! As an example, the "data" relationship described by
17//! V_{i + 1}(b_1, ..., b_n) * (V_{i + 1}(b_1, ..., b_n) + V_{i + 2}(b_1, ..., b_n))
18//! is inexpressible using the functionality within [crate::expression]. Rather,
19//! it would be written as the (mathematically equivalent)
20//! 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)
21//!
22//! Expressions are constructed as a tree of [generic_expr::ExpressionNode]s.
23//! Note that there are four "phases" to the "life cycle" of an expression, i.e.
24//! the changes it goes through during the circuit-building process (see documentation
25//! for this under under TODO(vishady): write documentation for the compilation process):
26//! * [circuit_expr::ExprDescription]: The "circuit description" view of an
27//!   expression. In particular, it describes the polynomial relationship between
28//!   the MLE representing the data output of a particular layer against MLEs
29//!   representing data "slices" within other layers, and contains information about
30//!   the expression "structure" (in the form of the expansion of the CFG description
31//!   from above), with the leaves of the expression tree always being
32//!   [generic_expr::ExpressionNode::Constant]s or [generic_expr::ExpressionNode::Mle]s
33//!   or [generic_expr::ExpressionNode::Product]s.
34//! * [prover_expr::ProverExpr]: The prover's view of an expression. It contains
35//!   all the information within [circuit_expr::ExprDescription], but contains
36//!   [crate::mle::dense::DenseMle]s rather than [crate::mle::mle_description::MleDescription]s.
37//! * [verifier_expr::VerifierExpr]: The verifier's view of an expression. It
38//!   contains all the information within [circuit_expr::ExprDescription], but contains
39//!   [crate::mle::verifier_mle::VerifierMle]s rather than [crate::mle::mle_description::MleDescription]s.
40
41#![allow(missing_docs)]
42pub mod circuit_expr;
43pub mod expr_errors;
44pub mod generic_expr;
45pub mod prover_expr;
46pub mod verifier_expr;
47
48#[cfg(test)]
49pub mod tests;
remainder/expression.rs

remainder/
expression.rs
