sp1_hypercube/
debug.rs

1use std::{borrow::Borrow, collections::BTreeMap};
2
3use rayon::prelude::*;
4use slop_air::{
5    Air, AirBuilder, AirBuilderWithPublicValues, ExtensionBuilder, PairBuilder,
6    PermutationAirBuilder,
7};
8use slop_algebra::{ExtensionField, Field};
9use slop_alloc::CpuBackend;
10use slop_challenger::IopCtx;
11use slop_matrix::{
12    dense::{RowMajorMatrix, RowMajorMatrixView},
13    Matrix,
14};
15use slop_multilinear::Mle;
16
17use crate::{
18    air::{EmptyMessageBuilder, MachineAir},
19    prover::Traces,
20    Chip,
21};
22
23/// Checks that the constraints of the given AIR are satisfied, including the permutation trace.
24///
25/// Note that this does not actually verify the proof.
26#[allow(clippy::too_many_arguments)]
27pub fn debug_constraints<GC, A>(
28    chip: &Chip<GC::F, A>,
29    preprocessed: Option<&Mle<GC::F>>,
30    main: &Mle<GC::F>,
31    public_values: &[GC::F],
32) -> Vec<(usize, Vec<usize>, Vec<GC::F>)>
33where
34    GC: IopCtx,
35    A: MachineAir<GC::F> + for<'a> Air<DebugConstraintBuilder<'a, GC::F, GC::EF>>,
36{
37    let main: RowMajorMatrix<GC::F> = main.clone().into_guts().try_into().unwrap();
38    let preprocessed: Option<RowMajorMatrix<GC::F>> =
39        preprocessed.map(|pre| pre.clone().into_guts().try_into().unwrap());
40    let height = main.height();
41    if height == 0 {
42        return Vec::new();
43    }
44
45    // Check that constraints are satisfied.
46    let mut failed_rows = (0..height)
47        .par_bridge()
48        .filter_map(|i| {
49            let main_local = main.row_slice(i);
50            let main_local = &(*main_local);
51            let preprocessed_local = if let Some(preprocessed) = preprocessed.as_ref() {
52                let row = preprocessed.row_slice(i);
53                let row: &[_] = (*row).borrow();
54                row.to_vec()
55            } else {
56                Vec::new()
57            };
58
59            let mut builder = DebugConstraintBuilder {
60                preprocessed: RowMajorMatrixView::new_row(&preprocessed_local),
61                main: RowMajorMatrixView::new_row(main_local),
62                public_values,
63                failing_constraints: Vec::new(),
64                num_constraints_evaluated: 0,
65                phantom: std::marker::PhantomData,
66            };
67            chip.eval(&mut builder);
68            if !builder.failing_constraints.is_empty() {
69                Some((i, builder.failing_constraints, main_local.to_vec()))
70            } else {
71                None
72            }
73        })
74        .collect::<Vec<_>>();
75
76    failed_rows.sort_unstable();
77
78    failed_rows
79}
80
81/// Checks that the constraints of all the given AIRs are satisfied on the proposed witnesses sent
82/// in `main` and `preprocessed`.
83pub fn debug_constraints_all_chips<GC, A>(
84    chips: &[Chip<GC::F, A>],
85    preprocessed: &Traces<GC::F, CpuBackend>,
86    main: &Traces<GC::F, CpuBackend>,
87    public_values: &[GC::F],
88) where
89    GC: IopCtx,
90    A: MachineAir<GC::F> + for<'a> Air<DebugConstraintBuilder<'a, GC::F, GC::EF>>,
91{
92    let mut result = BTreeMap::new();
93    for chip in chips.iter() {
94        let preprocessed_trace =
95            preprocessed.get(chip.air.name()).map(|t| t.inner().as_ref().unwrap().as_ref());
96        let maybe_main_trace = main.get(chip.air.name()).unwrap().inner().as_ref();
97
98        if maybe_main_trace.is_none() {
99            continue;
100        }
101        let main_trace = maybe_main_trace.unwrap().as_ref();
102        let failed_rows =
103            crate::debug_constraints::<GC, A>(chip, preprocessed_trace, main_trace, public_values);
104        if !failed_rows.is_empty() {
105            result.insert(chip.name().to_string(), failed_rows);
106        }
107    }
108
109    for (chip_name, failed_rows) in result {
110        if !failed_rows.is_empty() {
111            tracing::error!("======== CONSTRAINTS FAILED ON CHIP '{}' ========", chip_name);
112            tracing::error!("Total failing rows: {}", failed_rows.len());
113            tracing::error!("Printing information for up to three failing rows:");
114        }
115
116        for i in 0..3.min(failed_rows.len()) {
117            // Print up to three failing rows.
118            let (row_idx, failing_constraints, row) = &failed_rows[i];
119
120            tracing::error!("--------------------------------------------------");
121            tracing::error!("row {} failed", row_idx);
122            tracing::error!("constraint indices failed {:?}", failing_constraints);
123            tracing::error!("row values: {:?}", row);
124            tracing::error!("--------------------------------------------------");
125        }
126        if !failed_rows.is_empty() {
127            tracing::error!("==================================================");
128        }
129    }
130}
131
132/// A builder for debugging constraints.
133pub struct DebugConstraintBuilder<'a, F: Field, EF: ExtensionField<F>> {
134    pub(crate) preprocessed: RowMajorMatrixView<'a, F>,
135    pub(crate) main: RowMajorMatrixView<'a, F>,
136    pub(crate) public_values: &'a [F],
137    failing_constraints: Vec<usize>,
138    num_constraints_evaluated: usize,
139    phantom: std::marker::PhantomData<EF>,
140}
141
142impl<F, EF> ExtensionBuilder for DebugConstraintBuilder<'_, F, EF>
143where
144    F: Field,
145    EF: ExtensionField<F>,
146{
147    type EF = EF;
148    type VarEF = EF;
149    type ExprEF = EF;
150
151    fn assert_zero_ext<I>(&mut self, _x: I)
152    where
153        I: Into<Self::ExprEF>,
154    {
155        panic!("Extension fields not supported in debug builder, SP1 Hypercube traces are over base field");
156    }
157}
158
159impl<'a, F, EF> PermutationAirBuilder for DebugConstraintBuilder<'a, F, EF>
160where
161    F: Field,
162    EF: ExtensionField<F>,
163{
164    type MP = RowMajorMatrixView<'a, EF>;
165
166    type RandomVar = EF;
167
168    fn permutation(&self) -> Self::MP {
169        unimplemented!()
170    }
171
172    fn permutation_randomness(&self) -> &[Self::EF] {
173        unimplemented!()
174    }
175}
176
177impl<F, EF> PairBuilder for DebugConstraintBuilder<'_, F, EF>
178where
179    F: Field,
180    EF: ExtensionField<F>,
181{
182    fn preprocessed(&self) -> Self::M {
183        self.preprocessed
184    }
185}
186
187impl<F, EF> DebugConstraintBuilder<'_, F, EF>
188where
189    F: Field,
190    EF: ExtensionField<F>,
191{
192    #[allow(clippy::unused_self)]
193    #[inline]
194    fn debug_constraint(&mut self, x: F, y: F) {
195        if x != y {
196            self.failing_constraints.push(self.num_constraints_evaluated);
197        }
198        self.num_constraints_evaluated += 1;
199    }
200}
201
202impl<'a, F, EF> AirBuilder for DebugConstraintBuilder<'a, F, EF>
203where
204    F: Field,
205    EF: ExtensionField<F>,
206{
207    type F = F;
208    type Expr = F;
209    type Var = F;
210    type M = RowMajorMatrixView<'a, F>;
211
212    fn is_first_row(&self) -> Self::Expr {
213        unimplemented!()
214    }
215
216    fn is_last_row(&self) -> Self::Expr {
217        unimplemented!()
218    }
219
220    fn is_transition_window(&self, _size: usize) -> Self::Expr {
221        unimplemented!()
222    }
223
224    fn main(&self) -> Self::M {
225        self.main
226    }
227
228    fn assert_zero<I: Into<Self::Expr>>(&mut self, x: I) {
229        self.debug_constraint(x.into(), F::zero());
230    }
231
232    fn assert_one<I: Into<Self::Expr>>(&mut self, x: I) {
233        self.debug_constraint(x.into(), F::one());
234    }
235
236    fn assert_eq<I1: Into<Self::Expr>, I2: Into<Self::Expr>>(&mut self, x: I1, y: I2) {
237        self.debug_constraint(x.into(), y.into());
238    }
239
240    /// Assert that `x` is a boolean, i.e. either 0 or 1.
241    fn assert_bool<I: Into<Self::Expr>>(&mut self, x: I) {
242        let x = x.into();
243        if x != F::zero() && x != F::one() {
244            self.failing_constraints.push(self.num_constraints_evaluated);
245        }
246        self.num_constraints_evaluated += 1;
247    }
248}
249
250impl<F: Field, EF: ExtensionField<F>> EmptyMessageBuilder for DebugConstraintBuilder<'_, F, EF> {}
251
252impl<F: Field, EF: ExtensionField<F>> AirBuilderWithPublicValues
253    for DebugConstraintBuilder<'_, F, EF>
254{
255    type PublicVar = F;
256
257    fn public_values(&self) -> &[Self::PublicVar] {
258        self.public_values
259    }
260}
sp1_hypercube/debug.rs

sp1_hypercube/
debug.rs
