sp1_recursion_program/fri/
mod.rs

1pub mod domain;
2pub mod hints;
3pub mod two_adic_pcs;
4pub mod types;
5
6pub use domain::*;
7use sp1_primitives::types::RecursionProgramType;
8use sp1_recursion_compiler::ir::{ExtensionOperand, Ptr};
9use sp1_recursion_core::runtime::DIGEST_SIZE;
10pub use two_adic_pcs::*;
11
12use p3_field::{AbstractField, Field, TwoAdicField};
13
14use sp1_recursion_compiler::ir::{Array, Builder, Config, Ext, Felt, SymbolicVar, Usize, Var};
15
16use self::types::{
17    DigestVariable, DimensionsVariable, FriChallengesVariable, FriConfigVariable, FriProofVariable,
18    FriQueryProofVariable,
19};
20use crate::challenger::{
21    CanObserveVariable, CanSampleBitsVariable, DuplexChallengerVariable, FeltChallenger,
22};
23
24/// Reference: https://github.com/Plonky3/Plonky3/blob/4809fa7bedd9ba8f6f5d3267b1592618e3776c57/fri/src/verifier.rs#L27
25pub fn verify_shape_and_sample_challenges<C: Config>(
26    builder: &mut Builder<C>,
27    config: &FriConfigVariable<C>,
28    proof: &FriProofVariable<C>,
29    challenger: &mut DuplexChallengerVariable<C>,
30) -> FriChallengesVariable<C> {
31    let mut betas: Array<C, Ext<C::F, C::EF>> = builder.dyn_array(proof.commit_phase_commits.len());
32
33    builder.range(0, proof.commit_phase_commits.len()).for_each(|i, builder| {
34        let comm = builder.get(&proof.commit_phase_commits, i);
35        challenger.observe(builder, comm);
36        let sample = challenger.sample_ext(builder);
37        builder.set(&mut betas, i, sample);
38    });
39
40    // Observe the final polynomial.
41    let final_poly_felts = builder.ext2felt(proof.final_poly);
42    challenger.observe_slice(builder, final_poly_felts);
43
44    let num_query_proofs = proof.query_proofs.len().materialize(builder);
45    builder.if_ne(num_query_proofs, config.num_queries).then(|builder| {
46        builder.error();
47    });
48
49    challenger.check_witness(builder, config.proof_of_work_bits, proof.pow_witness);
50
51    let num_commit_phase_commits = proof.commit_phase_commits.len().materialize(builder);
52    let log_max_height: Var<_> = builder.eval(num_commit_phase_commits + config.log_blowup);
53    let mut query_indices = builder.array(config.num_queries);
54    builder.range(0, config.num_queries).for_each(|i, builder| {
55        let index_bits = challenger.sample_bits(builder, Usize::Var(log_max_height));
56        builder.set(&mut query_indices, i, index_bits);
57    });
58
59    FriChallengesVariable { query_indices, betas }
60}
61
62/// Verifies a set of FRI challenges.
63///
64/// Reference: https://github.com/Plonky3/Plonky3/blob/4809fa7bedd9ba8f6f5d3267b1592618e3776c57/fri/src/verifier.rs#L67
65#[allow(clippy::type_complexity)]
66pub fn verify_challenges<C: Config>(
67    builder: &mut Builder<C>,
68    config: &FriConfigVariable<C>,
69    proof: &FriProofVariable<C>,
70    challenges: &FriChallengesVariable<C>,
71    reduced_openings: &Array<C, Array<C, Ext<C::F, C::EF>>>,
72) where
73    C::F: TwoAdicField,
74    C::EF: TwoAdicField,
75{
76    let nb_commit_phase_commits = proof.commit_phase_commits.len().materialize(builder);
77    let log_max_height = builder.eval(nb_commit_phase_commits + config.log_blowup);
78    builder.range(0, challenges.query_indices.len()).for_each(|i, builder| {
79        let index_bits = builder.get(&challenges.query_indices, i);
80        let query_proof = builder.get(&proof.query_proofs, i);
81        let ro = builder.get(reduced_openings, i);
82
83        let folded_eval = verify_query(
84            builder,
85            config,
86            &proof.commit_phase_commits,
87            &index_bits,
88            &query_proof,
89            &challenges.betas,
90            &ro,
91            Usize::Var(log_max_height),
92        );
93
94        builder.assert_ext_eq(folded_eval, proof.final_poly);
95    });
96}
97
98/// Verifies a FRI query.
99///
100/// Currently assumes the index that is accessed is constant.
101///
102/// Reference: https://github.com/Plonky3/Plonky3/blob/4809fa7bedd9ba8f6f5d3267b1592618e3776c57/fri/src/verifier.rs#L101
103#[allow(clippy::too_many_arguments)]
104#[allow(unused_variables)]
105pub fn verify_query<C: Config>(
106    builder: &mut Builder<C>,
107    config: &FriConfigVariable<C>,
108    commit_phase_commits: &Array<C, DigestVariable<C>>,
109    index_bits: &Array<C, Var<C::N>>,
110    proof: &FriQueryProofVariable<C>,
111    betas: &Array<C, Ext<C::F, C::EF>>,
112    reduced_openings: &Array<C, Ext<C::F, C::EF>>,
113    log_max_height: Usize<C::N>,
114) -> Ext<C::F, C::EF>
115where
116    C::F: TwoAdicField,
117    C::EF: TwoAdicField,
118{
119    builder.cycle_tracker("verify-query");
120    let folded_eval: Ext<C::F, C::EF> = builder.eval(C::F::zero());
121    let two_adic_generator_f = config.get_two_adic_generator(builder, log_max_height);
122
123    let x = if matches!(builder.program_type, RecursionProgramType::Wrap) {
124        builder.exp_reverse_bits_len(two_adic_generator_f, index_bits, log_max_height)
125    } else {
126        builder.exp_reverse_bits_len_fast(two_adic_generator_f, index_bits, log_max_height)
127    };
128
129    let log_max_height = log_max_height.materialize(builder);
130    builder.range(0, commit_phase_commits.len()).for_each(|i, builder| {
131        let log_folded_height: Var<_> = builder.eval(log_max_height - i - C::N::one());
132        let log_folded_height_plus_one: Var<_> = builder.eval(log_folded_height + C::N::one());
133        let commit = builder.get(commit_phase_commits, i);
134        let step = builder.get(&proof.commit_phase_openings, i);
135        let beta = builder.get(betas, i);
136
137        let reduced_opening = builder.get(reduced_openings, log_folded_height_plus_one);
138        builder.assign(folded_eval, folded_eval + reduced_opening);
139
140        let index_bit = builder.get(index_bits, i);
141        let index_sibling_mod_2: Var<C::N> =
142            builder.eval(SymbolicVar::from(C::N::one()) - index_bit);
143        let i_plus_one = builder.eval(i + C::N::one());
144        let index_pair = index_bits.shift(builder, i_plus_one);
145
146        let mut evals: Array<C, Ext<C::F, C::EF>> = builder.array(2);
147        builder.set_value(&mut evals, 0, folded_eval);
148        builder.set_value(&mut evals, 1, folded_eval);
149        builder.set_value(&mut evals, index_sibling_mod_2, step.sibling_value);
150
151        let dims = DimensionsVariable::<C> {
152            height: builder.sll(C::N::one(), Usize::Var(log_folded_height)),
153        };
154        let mut dims_slice: Array<C, DimensionsVariable<C>> = builder.array(1);
155        builder.set_value(&mut dims_slice, 0, dims);
156
157        let mut opened_values = builder.array(1);
158        builder.set_value(&mut opened_values, 0, evals.clone());
159        verify_batch::<C, 4>(
160            builder,
161            &commit,
162            dims_slice,
163            index_pair,
164            opened_values,
165            &step.opening_proof,
166        );
167
168        let two_adic_generator_one = config.get_two_adic_generator(builder, Usize::Const(1));
169        let xs_0: Ext<_, _> = builder.eval(x);
170        let xs_1: Ext<_, _> = builder.eval(x);
171        builder.if_eq(index_sibling_mod_2, C::N::zero()).then_or_else(
172            |builder| {
173                builder.assign(xs_0, x * two_adic_generator_one.to_operand().symbolic());
174            },
175            |builder| {
176                builder.assign(xs_1, x * two_adic_generator_one.to_operand().symbolic());
177            },
178        );
179
180        let eval_0 = builder.get(&evals, 0);
181        let eval_1 = builder.get(&evals, 1);
182        builder.assign(folded_eval, eval_0 + (beta - xs_0) * (eval_1 - eval_0) / (xs_1 - xs_0));
183
184        builder.assign(x, x * x);
185    });
186
187    builder.cycle_tracker("verify-query");
188    folded_eval
189}
190
191/// Verifies a batch opening.
192///
193/// Assumes the dimensions have already been sorted by tallest first.
194///
195/// Reference: https://github.com/Plonky3/Plonky3/blob/4809fa7bedd9ba8f6f5d3267b1592618e3776c57/merkle-tree/src/mmcs.rs#L92
196#[allow(clippy::type_complexity)]
197#[allow(unused_variables)]
198pub fn verify_batch<C: Config, const D: usize>(
199    builder: &mut Builder<C>,
200    commit: &DigestVariable<C>,
201    dimensions: Array<C, DimensionsVariable<C>>,
202    index_bits: Array<C, Var<C::N>>,
203    opened_values: Array<C, Array<C, Ext<C::F, C::EF>>>,
204    proof: &Array<C, DigestVariable<C>>,
205) {
206    builder.cycle_tracker("verify-batch");
207    // The index of which table to process next.
208    let index: Var<C::N> = builder.eval(C::N::zero());
209
210    // The height of the current layer (padded).
211    let current_height = builder.get(&dimensions, index).height;
212
213    // Reduce all the tables that have the same height to a single root.
214    let root = reduce_fast::<C, D>(builder, index, &dimensions, current_height, &opened_values);
215    let root_ptr = match root {
216        Array::Fixed(_) => panic!("root is fixed"),
217        Array::Dyn(ptr, _) => ptr,
218    };
219
220    // For each sibling in the proof, reconstruct the root.
221    let one: Var<_> = builder.eval(C::N::one());
222    let left: Ptr<C::N> = builder.uninit();
223    let right: Ptr<C::N> = builder.uninit();
224    builder.range(0, proof.len()).for_each(|i, builder| {
225        let sibling = builder.get_ptr(proof, i);
226        let bit = builder.get(&index_bits, i);
227
228        builder.if_eq(bit, C::N::one()).then_or_else(
229            |builder| {
230                builder.assign(left, sibling);
231                builder.assign(right, root_ptr);
232            },
233            |builder| {
234                builder.assign(left, root_ptr);
235                builder.assign(right, sibling);
236            },
237        );
238
239        builder.poseidon2_compress_x(
240            &mut Array::Dyn(root_ptr, Usize::Const(0)),
241            &Array::Dyn(left, Usize::Const(0)),
242            &Array::Dyn(right, Usize::Const(0)),
243        );
244        builder.assign(current_height, current_height * (C::N::two().inverse()));
245
246        builder.if_ne(index, dimensions.len()).then(|builder| {
247            let next_height = builder.get(&dimensions, index).height;
248            builder.if_eq(next_height, current_height).then(|builder| {
249                let next_height_openings_digest = reduce_fast::<C, D>(
250                    builder,
251                    index,
252                    &dimensions,
253                    current_height,
254                    &opened_values,
255                );
256                builder.poseidon2_compress_x(
257                    &mut root.clone(),
258                    &root.clone(),
259                    &next_height_openings_digest,
260                );
261            });
262        })
263    });
264
265    // Assert that the commitments match.
266    for i in 0..DIGEST_SIZE {
267        let e1 = builder.get(commit, i);
268        let e2 = builder.get(&root, i);
269        builder.assert_felt_eq(e1, e2);
270    }
271    builder.cycle_tracker("verify-batch");
272}
273
274#[allow(clippy::type_complexity)]
275pub fn reduce_fast<C: Config, const D: usize>(
276    builder: &mut Builder<C>,
277    dim_idx: Var<C::N>,
278    dims: &Array<C, DimensionsVariable<C>>,
279    curr_height_padded: Var<C::N>,
280    opened_values: &Array<C, Array<C, Ext<C::F, C::EF>>>,
281) -> Array<C, Felt<C::F>> {
282    builder.cycle_tracker("verify-batch-reduce-fast");
283    let nb_opened_values: Var<_> = builder.eval(C::N::zero());
284    let mut nested_opened_values: Array<_, Array<_, Ext<_, _>>> = builder.dyn_array(8192);
285    let start_dim_idx: Var<_> = builder.eval(dim_idx);
286    builder.cycle_tracker("verify-batch-reduce-fast-setup");
287    builder.range(start_dim_idx, dims.len()).for_each(|i, builder| {
288        let height = builder.get(dims, i).height;
289        builder.if_eq(height, curr_height_padded).then(|builder| {
290            let opened_values = builder.get(opened_values, i);
291            builder.set_value(&mut nested_opened_values, nb_opened_values, opened_values.clone());
292            builder.assign(nb_opened_values, nb_opened_values + C::N::one());
293            builder.assign(dim_idx, dim_idx + C::N::one());
294        });
295    });
296    builder.cycle_tracker("verify-batch-reduce-fast-setup");
297
298    let h = if D == 1 {
299        let nested_opened_values = match nested_opened_values {
300            Array::Dyn(ptr, len) => Array::Dyn(ptr, len),
301            _ => unreachable!(),
302        };
303        nested_opened_values.truncate(builder, Usize::Var(nb_opened_values));
304        builder.poseidon2_hash_x(&nested_opened_values)
305    } else {
306        nested_opened_values.truncate(builder, Usize::Var(nb_opened_values));
307        builder.poseidon2_hash_ext(&nested_opened_values)
308    };
309    builder.cycle_tracker("verify-batch-reduce-fast");
310    h
311}
sp1_recursion_program/fri/mod.rs

sp1_recursion_program/fri/
mod.rs
