triton_vm/table/
auxiliary_table.rs

1use std::fmt::Display;
2use std::fmt::Formatter;
3use std::fmt::Result as FmtResult;
4
5use itertools::Itertools;
6use ndarray::ArrayView1;
7use twenty_first::math::traits::FiniteField;
8use twenty_first::prelude::*;
9
10use crate::challenges::Challenges;
11use crate::table::ConstraintType;
12use crate::table::master_table::MasterAuxTable;
13
14include!(concat!(env!("OUT_DIR"), "/evaluate_constraints.rs"));
15
16// The implementations of these functions are generated in `build.rs`.
17pub trait Evaluable<FF: FiniteField> {
18    fn evaluate_initial_constraints(
19        main_row: ArrayView1<FF>,
20        aux_row: ArrayView1<XFieldElement>,
21        challenges: &Challenges,
22    ) -> Vec<XFieldElement>;
23
24    fn evaluate_consistency_constraints(
25        main_row: ArrayView1<FF>,
26        aux_row: ArrayView1<XFieldElement>,
27        challenges: &Challenges,
28    ) -> Vec<XFieldElement>;
29
30    fn evaluate_transition_constraints(
31        current_main_row: ArrayView1<FF>,
32        current_aux_row: ArrayView1<XFieldElement>,
33        next_main_row: ArrayView1<FF>,
34        next_aux_row: ArrayView1<XFieldElement>,
35        challenges: &Challenges,
36    ) -> Vec<XFieldElement>;
37
38    fn evaluate_terminal_constraints(
39        main_row: ArrayView1<FF>,
40        aux_row: ArrayView1<XFieldElement>,
41        challenges: &Challenges,
42    ) -> Vec<XFieldElement>;
43}
44
45/// Helps debugging and benchmarking. The maximal degree achieved in any table
46/// dictates the length of the FRI domain, which in turn is responsible for the
47/// main performance bottleneck.
48#[derive(Debug, Clone, Eq, PartialEq, Ord, PartialOrd)]
49pub(crate) struct DegreeWithOrigin {
50    pub degree: isize,
51    pub interpolant_degree: isize,
52    pub zerofier_degree: isize,
53    pub origin_index: usize,
54    pub origin_table_height: usize,
55
56    /// Can be used to determine the degree bounds for the quotient polynomials:
57    /// the degree of the zerofier polynomials differ between the constraint
58    /// types.
59    pub origin_constraint_type: ConstraintType,
60}
61
62impl Display for DegreeWithOrigin {
63    fn fmt(&self, f: &mut Formatter<'_>) -> FmtResult {
64        assert!(self.degree > 0, "constant constraints make no sense");
65        let zerofier_corrected_degree = self.degree + self.zerofier_degree;
66        let degree = zerofier_corrected_degree / self.interpolant_degree;
67        let idx = self.origin_index;
68        let constraint_type = self.origin_constraint_type;
69        write!(
70            f,
71            "Degree of polynomial {idx:02} of type “{constraint_type}” is {degree}."
72        )
73    }
74}
75
76/// Compute the degrees of the quotients from all AIR constraints that apply to
77/// the table.
78pub(crate) fn all_degrees_with_origin(
79    interpolant_degree: isize,
80    padded_height: usize,
81) -> Vec<DegreeWithOrigin> {
82    let initial_degrees_with_origin =
83        MasterAuxTable::initial_quotient_degree_bounds(interpolant_degree)
84            .into_iter()
85            .enumerate()
86            .map(|(origin_index, degree)| DegreeWithOrigin {
87                degree,
88                interpolant_degree,
89                zerofier_degree: 1,
90                origin_index,
91                origin_table_height: padded_height,
92                origin_constraint_type: ConstraintType::Initial,
93            })
94            .collect_vec();
95
96    let consistency_degrees_with_origin =
97        MasterAuxTable::consistency_quotient_degree_bounds(interpolant_degree, padded_height)
98            .into_iter()
99            .enumerate()
100            .map(|(origin_index, degree)| DegreeWithOrigin {
101                degree,
102                interpolant_degree,
103                zerofier_degree: padded_height as isize,
104                origin_index,
105                origin_table_height: padded_height,
106                origin_constraint_type: ConstraintType::Consistency,
107            })
108            .collect();
109
110    let transition_degrees_with_origin =
111        MasterAuxTable::transition_quotient_degree_bounds(interpolant_degree, padded_height)
112            .into_iter()
113            .enumerate()
114            .map(|(origin_index, degree)| DegreeWithOrigin {
115                degree,
116                interpolant_degree,
117                zerofier_degree: padded_height as isize - 1,
118                origin_index,
119                origin_table_height: padded_height,
120                origin_constraint_type: ConstraintType::Transition,
121            })
122            .collect();
123
124    let terminal_degrees_with_origin =
125        MasterAuxTable::terminal_quotient_degree_bounds(interpolant_degree)
126            .into_iter()
127            .enumerate()
128            .map(|(origin_index, degree)| DegreeWithOrigin {
129                degree,
130                interpolant_degree,
131                zerofier_degree: 1,
132                origin_index,
133                origin_table_height: padded_height,
134                origin_constraint_type: ConstraintType::Terminal,
135            })
136            .collect();
137
138    [
139        initial_degrees_with_origin,
140        consistency_degrees_with_origin,
141        transition_degrees_with_origin,
142        terminal_degrees_with_origin,
143    ]
144    .concat()
145}
triton_vm/table/auxiliary_table.rs

triton_vm/table/
auxiliary_table.rs
