winter_air/air/boundary/
constraint_group.rs

1// Copyright (c) Facebook, Inc. and its affiliates.
2//
3// This source code is licensed under the MIT license found in the
4// LICENSE file in the root directory of this source tree.
5
6use alloc::{collections::BTreeMap, vec::Vec};
7
8use super::{Assertion, BoundaryConstraint, ConstraintDivisor, ExtensionOf, FieldElement};
9
10// BOUNDARY CONSTRAINT GROUP
11// ================================================================================================
12/// A group of boundary constraints all having the same divisor.
13///
14/// A boundary constraint is described by a rational function $\frac{f(x) - b(x)}{z(x)}$, where:
15///
16/// * $f(x)$ is a trace polynomial for the column against which the constraint is placed.
17/// * $b(x)$ is the value polynomial for the constraint.
18/// * $z(x)$ is the constraint divisor polynomial.
19///
20/// A boundary constraint group groups together all boundary constraints where polynomial $z$ is
21/// the same. The constraints stored in the group describe polynomials $b$. At the time of
22/// constraint evaluation, a prover or a verifier provides evaluations of the relevant polynomial
23/// $f$ so that the value of the constraint can be computed.
24///
25/// When the protocol is run in a large field, types `F` and `E` are the same. However, when
26/// working with small fields, `F` and `E` can be set as follows:
27/// * `F` could be the base field of the protocol, in which case `E` is the extension field used.
28/// * `F` could be the extension field, in which case `F` and `E` are the same type.
29///
30/// The above arrangement allows us to describe boundary constraints for main and auxiliary
31/// segments of the execution trace. Specifically:
32/// * For the constraints against columns of the main execution trace, `F` is set to the base field
33///   of the protocol, and `E` is set to the extension field.
34/// * For the constraints against columns of the auxiliary trace segment, both `F` and `E` are set
35///   to the extension field.
36#[derive(Debug, Clone)]
37pub struct BoundaryConstraintGroup<F, E>
38where
39    F: FieldElement,
40    E: FieldElement<BaseField = F::BaseField> + ExtensionOf<F>,
41{
42    constraints: Vec<BoundaryConstraint<F, E>>,
43    divisor: ConstraintDivisor<F::BaseField>,
44}
45
46impl<F, E> BoundaryConstraintGroup<F, E>
47where
48    F: FieldElement,
49    E: FieldElement<BaseField = F::BaseField> + ExtensionOf<F>,
50{
51    // CONSTRUCTOR
52    // --------------------------------------------------------------------------------------------
53    /// Returns a new boundary constraint group to hold constraints with the specified divisor.
54    pub(super) fn new(divisor: ConstraintDivisor<F::BaseField>) -> Self {
55        BoundaryConstraintGroup { constraints: Vec::new(), divisor }
56    }
57
58    // PUBLIC ACCESSORS
59    // --------------------------------------------------------------------------------------------
60
61    /// Returns a list of boundary constraints in this group.
62    pub fn constraints(&self) -> &[BoundaryConstraint<F, E>] {
63        &self.constraints
64    }
65
66    /// Returns a divisor applicable to all boundary constraints in this group.
67    pub fn divisor(&self) -> &ConstraintDivisor<F::BaseField> {
68        &self.divisor
69    }
70
71    // PUBLIC METHODS
72    // --------------------------------------------------------------------------------------------
73
74    /// Creates a new boundary constraint from the specified assertion and adds it to the group.
75    pub(super) fn add(
76        &mut self,
77        assertion: Assertion<F>,
78        inv_g: F::BaseField,
79        twiddle_map: &mut BTreeMap<usize, Vec<F::BaseField>>,
80        composition_coefficients: E,
81    ) {
82        self.constraints.push(BoundaryConstraint::new(
83            assertion,
84            inv_g,
85            twiddle_map,
86            composition_coefficients,
87        ));
88    }
89
90    /// Evaluates all constraints in this group at the specified point `x`.
91    ///
92    /// Constraint evaluations are merges into a single value by computing their random linear
93    /// combination and dividing the result by the divisor of this constraint group as follows:
94    /// $$
95    /// \frac{\sum_{i=0}^{k-1}{\alpha_i \cdot C_i(x)}}{z(x)}
96    /// $$
97    /// where:
98    /// * $C_i(x)$ is the evaluation of the $i$th constraint at `x` computed as $f(x) - b(x)$.
99    /// * $\alpha_i$ are random field elements. In the interactive version of the protocol, these
100    ///   are provided by the verifier.
101    pub fn evaluate_at(&self, state: &[E], x: E) -> E {
102        let mut numerator = E::ZERO;
103        for constraint in self.constraints().iter() {
104            let trace_value = state[constraint.column()];
105            let evaluation = constraint.evaluate_at(x, trace_value);
106            numerator += evaluation * *constraint.cc();
107        }
108
109        let denominator = self.divisor.evaluate_at(x);
110
111        numerator / denominator
112    }
113}
winter_air/air/boundary/constraint_group.rs

winter_air/air/boundary/
constraint_group.rs
