winter_air/air/transition/
degree.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::vec::Vec;
7use core::cmp;
8
9use super::{super::super::ProofOptions, MIN_CYCLE_LENGTH};
10
11// TRANSITION CONSTRAINT DEGREE
12// ================================================================================================
13/// Degree descriptor of a transition constraint.
14///
15/// Describes constraint degree as a combination of multiplications of periodic and trace
16/// columns. For example, degree of a constraint which requires multiplication of two trace
17/// columns can be described as: `base: 2, cycles: []`. A constraint which requires
18/// multiplication of 3 trace columns and a periodic column with a period of 32 steps can be
19/// described as: `base: 3, cycles: [32]`.
20#[derive(Clone, Debug, PartialEq, Eq)]
21pub struct TransitionConstraintDegree {
22    base: usize,
23    cycles: Vec<usize>,
24}
25
26impl TransitionConstraintDegree {
27    /// Creates a new transition constraint degree descriptor for constraints which involve
28    /// multiplications of trace columns only.
29    ///
30    /// For example, if a constraint involves multiplication of two trace columns, `degree`
31    /// should be set to 2. If a constraint involves multiplication of three trace columns,
32    /// `degree` should be set to 3 etc.
33    ///
34    /// # Panics
35    /// Panics if the provided `degree` is zero.
36    pub fn new(degree: usize) -> Self {
37        assert!(degree > 0, "transition constraint degree must be at least one, but was zero");
38        TransitionConstraintDegree { base: degree, cycles: vec![] }
39    }
40
41    /// Creates a new transition degree descriptor for constraints which involve multiplication
42    /// of trace columns and periodic columns.
43    ///
44    /// For example, if a constraint involves multiplication of two trace columns and one
45    /// periodic column with a period length of 32 steps, `base_degree` should be set to 2,
46    /// and `cycles` should be set to `vec![32]`.
47    ///
48    /// # Panics
49    /// Panics if:
50    /// * `base_degree` is zero.
51    /// * Any of the values in the `cycles` vector is smaller than two or is not powers of two.
52    pub fn with_cycles(base_degree: usize, cycles: Vec<usize>) -> Self {
53        assert!(
54            base_degree > 0,
55            "transition constraint degree must be at least one, but was zero"
56        );
57        for (i, &cycle) in cycles.iter().enumerate() {
58            assert!(
59                cycle >= MIN_CYCLE_LENGTH,
60                "cycle length must be at least {MIN_CYCLE_LENGTH}, but was {cycle} for cycle {i}"
61            );
62            assert!(
63                cycle.is_power_of_two(),
64                "cycle length must be a power of two, but was {cycle} for cycle {i}"
65            );
66        }
67        TransitionConstraintDegree { base: base_degree, cycles }
68    }
69
70    /// Computes a degree to which this degree description expands in the context of execution
71    /// trace of the specified length.
72    ///
73    /// The expanded degree is computed as follows:
74    ///
75    /// $$
76    /// b \cdot (n - 1) + \sum_{i = 0}^{k - 1}{\frac{n \cdot (c_i - 1)}{c_i}}
77    /// $$
78    ///
79    /// where: $b$ is the base degree, $n$ is the `trace_length`, $c_i$ is a cycle length of
80    /// periodic column $i$, and $k$ is the total number of periodic columns for this degree
81    /// descriptor.
82    ///
83    /// Thus, evaluation degree of a transition constraint which involves multiplication of two
84    /// trace columns and one periodic column with a period length of 32 steps when evaluated
85    /// over an execution trace of 64 steps would be:
86    ///
87    /// $$
88    /// 2 \cdot (64 - 1) + \frac{64 \cdot (32 - 1)}{32} = 126 + 62 = 188
89    /// $$
90    pub fn get_evaluation_degree(&self, trace_length: usize) -> usize {
91        let mut result = self.base * (trace_length - 1);
92        for cycle_length in self.cycles.iter() {
93            result += (trace_length / cycle_length) * (cycle_length - 1);
94        }
95        result
96    }
97
98    /// Returns a minimum blowup factor needed to evaluate constraint of this degree.
99    ///
100    /// This is guaranteed to be a power of two, greater than one.
101    pub fn min_blowup_factor(&self) -> usize {
102        // The blowup factor needs to be a power of two large enough to accommodate degree of
103        // transition constraints defined by rational functions `C(x) / z(x)` where `C(x)` is the
104        // constraint polynomial and `z(x)` is the transition constraint divisor.
105        //
106        // Degree of `C(x)` is always smaller than or equal to `[self.base + self.cycles.len()] * [trace_length - 1]`.
107        // Degree of `z(x)` is `[trace_length - 1]`. Thus, the degree of `C(x) / z(x)` is
108        // `[self.base + self.cycles.len() - 1] * [trace_length - 1]` and the blowup factor needed
109        // to accommodate this degree can be estimated as `self.base + self.cycles.len() - 1`.
110        //
111        // For example, if degree of our constraints is 6, the blowup factor would need to be 8.
112        // However, if the degree is 5, the blowup factor could be as small as 4.
113        let degree_bound = self.base + self.cycles.len() - 1;
114        cmp::max(degree_bound.next_power_of_two(), ProofOptions::MIN_BLOWUP_FACTOR)
115    }
116}
winter_air/air/transition/degree.rs

winter_air/air/transition/
degree.rs
