winter_air/air/boundary/constraint.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 math::{fft, polynom};
9
10use super::{Assertion, ExtensionOf, FieldElement};
11
12// BOUNDARY CONSTRAINT
13// ================================================================================================
14
15/// The numerator portion of a boundary constraint.
16///
17/// A boundary constraint is described by a rational function $\frac{f(x) - b(x)}{z(x)}$, where:
18///
19/// * $f(x)$ is a trace polynomial for the column against which the constraint is placed.
20/// * $b(b)$ is the value polynomial for this constraint.
21/// * $z(x)$ is the constraint divisor polynomial.
22///
23/// In addition to the value polynomial, a [BoundaryConstraint] also contains info needed to
24/// evaluate the constraint and to compose constraint evaluations with other constraints (i.e.,
25/// constraint composition coefficient).
26///
27/// When the protocol is run in a large field, types `F` and `E` are the same. However, when
28/// working with small fields, `F` and `E` can be set as follows:
29/// * `F` could be the base field of the protocol, in which case `E` is the extension field used.
30/// * `F` could be the extension field, in which case `F` and `E` are the same type.
31///
32/// Boundary constraints cannot be instantiated directly, they are created internally from
33/// [Assertions](Assertion).
34#[derive(Debug, Clone, Eq, PartialEq)]
35pub struct BoundaryConstraint<F, E>
36where
37 F: FieldElement,
38 E: FieldElement<BaseField = F::BaseField> + ExtensionOf<F>,
39{
40 column: usize,
41 poly: Vec<F>,
42 poly_offset: (usize, F::BaseField),
43 cc: E,
44}
45
46impl<F, E> BoundaryConstraint<F, E>
47where
48 F: FieldElement,
49 E: FieldElement<BaseField = F::BaseField> + ExtensionOf<F>,
50{
51 // CONSTRUCTORS
52 // --------------------------------------------------------------------------------------------
53
54 /// Creates a new boundary constraint from the specified assertion.
55 pub(super) fn new(
56 assertion: Assertion<F>,
57 inv_g: F::BaseField,
58 twiddle_map: &mut BTreeMap<usize, Vec<F::BaseField>>,
59 composition_coefficient: E,
60 ) -> Self {
61 // build a polynomial which evaluates to constraint values at asserted steps; for
62 // single-value assertions we use the value as constant coefficient of degree 0
63 // polynomial; but for multi-value assertions, we need to interpolate the values
64 // into a polynomial using inverse FFT
65 let mut poly_offset = (0, F::BaseField::ONE);
66 let mut poly = assertion.values;
67 if poly.len() > 1 {
68 // get the twiddles from the map; if twiddles for this domain haven't been built
69 // yet, build them and add them to the map
70 let inv_twiddles = twiddle_map
71 .entry(poly.len())
72 .or_insert_with(|| fft::get_inv_twiddles(poly.len()));
73 // interpolate the values into a polynomial
74 fft::interpolate_poly(&mut poly, inv_twiddles);
75 if assertion.first_step != 0 {
76 // if the assertions don't fall on the steps which are powers of two, we can't
77 // use FFT to interpolate the values into a polynomial. This would make such
78 // assertions quite impractical. To get around this, we still use FFT to build
79 // the polynomial, but then we evaluate it as f(x * offset) instead of f(x)
80 let x_offset = inv_g.exp((assertion.first_step as u64).into());
81 poly_offset = (assertion.first_step, x_offset);
82 }
83 }
84
85 BoundaryConstraint {
86 column: assertion.column,
87 poly,
88 poly_offset,
89 cc: composition_coefficient,
90 }
91 }
92
93 // PUBLIC ACCESSORS
94 // --------------------------------------------------------------------------------------------
95
96 /// Returns index of the column against which this constraint applies.
97 pub fn column(&self) -> usize {
98 self.column
99 }
100
101 /// Returns a value polynomial for this constraint.
102 pub fn poly(&self) -> &[F] {
103 &self.poly
104 }
105
106 /// Returns offset by which we need to shift the domain before evaluating this constraint.
107 ///
108 /// The offset is returned as a tuple describing both, the number of steps by which the
109 /// domain needs to be shifted, and field element by which a domain element needs to be
110 /// multiplied to achieve the desired shift.
111 pub fn poly_offset(&self) -> (usize, F::BaseField) {
112 self.poly_offset
113 }
114
115 /// Returns composition coefficient for this constraint.
116 pub fn cc(&self) -> &E {
117 &self.cc
118 }
119
120 // CONSTRAINT EVALUATOR
121 // --------------------------------------------------------------------------------------------
122 /// Evaluates this constraint at the specified point `x`.
123 ///
124 /// The constraint is evaluated by computing $f(x) - b(x)$, where:
125 /// * $f$ is a trace polynomial for the column against which the constraint is placed.
126 /// * $f(x)$ = `trace_value`
127 /// * $b$ is the value polynomial for this constraint.
128 ///
129 /// For boundary constraints derived from single and periodic assertions, $b(x)$ is a constant.
130 pub fn evaluate_at(&self, x: E, trace_value: E) -> E {
131 let assertion_value = if self.poly.len() == 1 {
132 // if the value polynomial consists of just a constant, use that constant
133 E::from(self.poly[0])
134 } else {
135 // otherwise, we need to evaluate the polynomial at `x`; for assertions which don't
136 // fall on steps that are powers of two, we need to evaluate the value polynomial
137 // at x * offset (instead of just x).
138 //
139 // note that while the coefficients of the value polynomial are in the base field,
140 // if we are working in an extension field, the result of the evaluation will be a
141 // value in the extension field.
142 let x = x * E::from(self.poly_offset.1);
143 polynom::eval(&self.poly, x)
144 };
145 // subtract assertion value from trace value
146 trace_value - assertion_value
147 }
148}