openvm_native_recursion/fri/
mod.rs

1pub use domain::*;
2use openvm_native_compiler::{
3    ir::{
4        Array, ArrayLike, Builder, Config, Ext, ExtensionOperand, Felt, RVar, SymbolicVar, Usize,
5        Var,
6    },
7    prelude::MemVariable,
8};
9use openvm_native_compiler_derive::iter_zip;
10use openvm_stark_backend::p3_field::{FieldAlgebra, TwoAdicField};
11pub use two_adic_pcs::*;
12
13use self::types::{DimensionsVariable, FriConfigVariable, FriQueryProofVariable};
14use crate::{
15    digest::{CanPoseidon2Digest, DigestVariable},
16    outer_poseidon2::Poseidon2CircuitBuilder,
17    utils::cond_eval,
18    vars::{HintSlice, OuterDigestVariable},
19};
20
21pub mod domain;
22pub mod hints;
23pub mod two_adic_pcs;
24pub mod types;
25pub mod witness;
26
27/// Verifies a FRI query.
28///
29/// Currently assumes the index that is accessed is constant.
30///
31/// Reference: <https://github.com/Plonky3/Plonky3/blob/4809fa7bedd9ba8f6f5d3267b1592618e3776c57/fri/src/verifier.rs#L101>
32#[allow(clippy::too_many_arguments)]
33fn verify_query<C: Config>(
34    builder: &mut Builder<C>,
35    config: &FriConfigVariable<C>,
36    commit_phase_commits: &Array<C, DigestVariable<C>>,
37    index_bits: &Array<C, Var<C::N>>,
38    proof: &FriQueryProofVariable<C>,
39    betas: &Array<C, Ext<C::F, C::EF>>,
40    betas_squared: &Array<C, Ext<C::F, C::EF>>,
41    reduced_openings: &Array<C, Ext<C::F, C::EF>>,
42    log_max_lde_height: RVar<C::N>,
43    i_plus_one_arr: &Array<C, Usize<C::N>>,
44) -> Ext<C::F, C::EF>
45where
46    C::F: TwoAdicField,
47    C::EF: TwoAdicField,
48{
49    builder.cycle_tracker_start("verify-query");
50    // reduced_openings.len() == MAX_TWO_ADICITY >= log_max_lde_height
51    let folded_eval: Ext<C::F, C::EF> = builder.get(reduced_openings, log_max_lde_height);
52    let two_adic_generator_f = config.get_two_adic_generator(builder, log_max_lde_height);
53
54    let two_adic_gen_ext = two_adic_generator_f.to_operand().symbolic();
55    let two_adic_generator_ef: Ext<_, _> = builder.eval(two_adic_gen_ext);
56
57    let index_bits_truncated = index_bits.slice(builder, 0, log_max_lde_height);
58    let x = builder.exp_bits_big_endian(two_adic_generator_ef, &index_bits_truncated);
59
60    // assert proof.commit_phase_openings.len() == log_max_height
61    // where
62    //   - commit_phase_commits.len() = log_max_height is compile-time constant (assuming
63    //     log_final_poly_len = 0)
64    //   - log_max_lde_height = log_max_height + log_blowup by definition in verify_two_adic_pcs
65    builder.assert_usize_eq(
66        proof.commit_phase_openings.len(),
67        commit_phase_commits.len(),
68    );
69    // By definition in verify_two_adic_pcs:
70    // - betas, betas_squared, i_plus_one_arr have length log_max_height
71    // - index_bits has length log_max_lde_height
72    iter_zip!(
73        builder,
74        commit_phase_commits,
75        proof.commit_phase_openings,
76        betas,
77        betas_squared,
78        i_plus_one_arr,
79        index_bits
80    )
81    .for_each(|ptr_vec, builder| {
82        let [comm_ptr, opening_ptr, beta_ptr, beta_sq_ptr, i_plus_one_ptr, index_bit_ptr] =
83            ptr_vec.try_into().unwrap();
84
85        let i_plus_one = builder.iter_ptr_get(i_plus_one_arr, i_plus_one_ptr);
86        let i_plus_one = RVar::from(i_plus_one);
87        let log_folded_height = builder.eval_expr(log_max_lde_height - i_plus_one);
88        let commit = builder.iter_ptr_get(commit_phase_commits, comm_ptr);
89        let step = builder.iter_ptr_get(&proof.commit_phase_openings, opening_ptr);
90        let beta = builder.iter_ptr_get(betas, beta_ptr);
91        let beta_sq = builder.iter_ptr_get(betas_squared, beta_sq_ptr);
92
93        let index_bit = builder.iter_ptr_get(index_bits, index_bit_ptr);
94        let index_sibling_mod_2: Var<C::N> = builder.eval(SymbolicVar::from(C::N::ONE) - index_bit);
95        let index_pair = index_bits.shift(builder, i_plus_one);
96
97        let evals: Array<C, Ext<C::F, C::EF>> = builder.array(2);
98        let eval_0: Ext<C::F, C::EF>;
99        let eval_1: Ext<C::F, C::EF>;
100        if builder.flags.static_only {
101            [eval_0, eval_1] = cond_eval(
102                builder,
103                index_sibling_mod_2,
104                step.sibling_value,
105                folded_eval,
106            );
107            builder.set_value(&evals, 0, eval_0);
108            builder.set_value(&evals, 1, eval_1);
109        } else {
110            builder.set_value(&evals, 0, folded_eval);
111            builder.set_value(&evals, 1, folded_eval);
112            // This is faster than branching.
113            builder.set_value(&evals, index_sibling_mod_2, step.sibling_value);
114            eval_0 = builder.get(&evals, 0);
115            eval_1 = builder.get(&evals, 1);
116        }
117
118        let dims = DimensionsVariable::<C> {
119            log_height: builder.eval(log_folded_height),
120        };
121        let dims_slice: Array<C, DimensionsVariable<C>> = builder.array(1);
122        builder.set_value(&dims_slice, 0, dims);
123
124        let opened_values = builder.array(1);
125        builder.set_value(&opened_values, 0, evals);
126        builder.cycle_tracker_start("verify-batch-ext");
127        verify_batch::<C>(
128            builder,
129            &commit,
130            dims_slice,
131            index_pair,
132            &NestedOpenedValues::Ext(opened_values),
133            &step.opening_proof,
134        );
135        builder.cycle_tracker_end("verify-batch-ext");
136
137        let two_adic_generator_one = config.get_two_adic_generator(builder, Usize::from(1));
138
139        let [xs_0, xs_1]: [Ext<_, _>; 2] =
140            cond_eval(builder, index_sibling_mod_2, x * two_adic_generator_one, x);
141
142        builder.assign(
143            &folded_eval,
144            eval_0 + (beta - xs_0) * (eval_1 - eval_0) / (xs_1 - xs_0),
145        );
146
147        builder.assign(&x, x * x);
148
149        // reduced_openings.len() == MAX_TWO_ADICITY >= log_max_lde_height >= log_folded_height
150        let reduced_opening = builder.get(reduced_openings, log_folded_height);
151        // Roll in new reduced opening polynomial at the folded height. This is 0 if there is no
152        // reduced opening at the folded height.
153        //
154        // Each `reduced_opening` is the evaluation of a reduced opening polynomial, which is itself
155        // a random linear combination `f_{i, 0}(x) + alpha f_{i, 1}(x) + ...`, but when we add it
156        // to the current folded polynomial evaluation claim, we need to multiply by a new random
157        // factor since `f_{i, 0}` has no leading coefficient.
158        //
159        // We use `beta^2` as the random factor since `beta` is already used in the folding.
160        //
161        // Note: this will include the case `reduced_opening = reduced_openings[log_blowup]` in the
162        // last iteration of the loop. Since we roll this in with the beta^2 factor, the low degree
163        // test will also include this case (corresponding to `log_height = 0`, which is not done in
164        // the Plonky3 implementation).
165        builder.assign(&folded_eval, folded_eval + beta_sq * reduced_opening);
166    });
167
168    builder.cycle_tracker_end("verify-query");
169    folded_eval
170}
171
172#[allow(clippy::type_complexity)]
173pub enum NestedOpenedValues<C: Config> {
174    Felt(Array<C, Array<C, Felt<C::F>>>),
175    Ext(Array<C, Array<C, Ext<C::F, C::EF>>>),
176}
177
178/// Verifies a batch opening.
179///
180/// Assumes the dimensions have already been sorted by tallest first.
181///
182/// Reference: <https://github.com/Plonky3/Plonky3/blob/4809fa7bedd9ba8f6f5d3267b1592618e3776c57/merkle-tree/src/mmcs.rs#L92>
183#[allow(clippy::type_complexity)]
184#[allow(unused_variables)]
185pub fn verify_batch<C: Config>(
186    builder: &mut Builder<C>,
187    commit: &DigestVariable<C>,
188    dimensions: Array<C, DimensionsVariable<C>>,
189    index_bits: Array<C, Var<C::N>>,
190    opened_values: &NestedOpenedValues<C>,
191    proof: &HintSlice<C>,
192) {
193    if builder.flags.static_only {
194        verify_batch_static(
195            builder,
196            commit,
197            dimensions,
198            index_bits,
199            opened_values,
200            proof,
201        );
202        return;
203    }
204
205    let dimensions = match dimensions {
206        Array::Dyn(ptr, len) => Array::Dyn(ptr, len.clone()),
207        _ => panic!("Expected a dynamic array of felts"),
208    };
209    let commit = match commit {
210        DigestVariable::Felt(arr) => arr,
211        _ => panic!("Expected a dynamic array of felts"),
212    };
213    match opened_values {
214        NestedOpenedValues::Felt(opened_values) => builder.verify_batch_felt(
215            &dimensions,
216            opened_values,
217            proof.id.get_var(),
218            &index_bits,
219            commit,
220        ),
221        NestedOpenedValues::Ext(opened_values) => builder.verify_batch_ext(
222            &dimensions,
223            opened_values,
224            proof.id.get_var(),
225            &index_bits,
226            commit,
227        ),
228    };
229}
230
231/// [static version] Verifies a batch opening.
232///
233/// Assumes the dimensions have already been sorted by tallest first.
234///
235/// Reference: <https://github.com/Plonky3/Plonky3/blob/4809fa7bedd9ba8f6f5d3267b1592618e3776c57/merkle-tree/src/mmcs.rs#L92>
236#[allow(clippy::type_complexity)]
237#[allow(unused_variables)]
238pub fn verify_batch_static<C: Config>(
239    builder: &mut Builder<C>,
240    commit: &DigestVariable<C>,
241    dimensions: Array<C, DimensionsVariable<C>>,
242    index_bits: Array<C, Var<C::N>>,
243    opened_values: &NestedOpenedValues<C>,
244    proof: &HintSlice<C>,
245) {
246    let commit: OuterDigestVariable<C> = if let DigestVariable::Var(commit) = commit {
247        commit.vec().try_into().unwrap()
248    } else {
249        panic!("Expected a Var commitment");
250    };
251    // The index of which table to process next.
252    let index: Usize<C::N> = builder.eval(C::N::ZERO);
253    // The height of the current layer (padded).
254    let mut current_log_height = builder.get(&dimensions, index.clone()).log_height.value();
255    // Reduce all the tables that have the same height to a single root.
256    let reducer = opened_values.create_reducer(builder);
257    let mut root = reducer
258        .reduce_fast(
259            builder,
260            index.clone(),
261            &dimensions,
262            current_log_height,
263            opened_values,
264        )
265        .into_outer_digest();
266
267    // For each sibling in the proof, reconstruct the root.
268    let witness_refs = builder.get_witness_refs(proof.id.clone()).to_vec();
269    for (i, &witness_ref) in witness_refs.iter().enumerate() {
270        let sibling: OuterDigestVariable<C> = [witness_ref.into()];
271        let bit = builder.get(&index_bits, i);
272
273        let [left, right]: [Var<_>; 2] = cond_eval(builder, bit, root[0], sibling[0]);
274        root = builder.p2_compress([[left], [right]]);
275        current_log_height -= 1;
276
277        builder
278            .if_ne(index.clone(), dimensions.len())
279            .then(|builder| {
280                let next_log_height = builder.get(&dimensions, index.clone()).log_height;
281                builder
282                    .if_eq(next_log_height, Usize::from(current_log_height))
283                    .then(|builder| {
284                        let next_height_openings_digest = reducer
285                            .reduce_fast(
286                                builder,
287                                index.clone(),
288                                &dimensions,
289                                current_log_height,
290                                opened_values,
291                            )
292                            .into_outer_digest();
293                        root = builder.p2_compress([root, next_height_openings_digest]);
294                    });
295            })
296    }
297
298    builder.assert_var_eq(root[0], commit[0]);
299}
300
301#[allow(clippy::type_complexity)]
302fn reduce_fast<C: Config, V: MemVariable<C>>(
303    builder: &mut Builder<C>,
304    dim_idx: Usize<C::N>,
305    dims: &Array<C, DimensionsVariable<C>>,
306    cur_log_height: usize,
307    opened_values: &Array<C, Array<C, V>>,
308    nested_opened_values_buffer: &Array<C, Array<C, V>>,
309) -> DigestVariable<C>
310where
311    Array<C, Array<C, V>>: CanPoseidon2Digest<C>,
312{
313    builder.cycle_tracker_start("verify-batch-reduce-fast");
314
315    // `nested_opened_values_buffer` will be truncated in this function. We want to avoid modifying
316    // the original buffer object, so we create a new one or clone it.
317    let nested_opened_values_buffer = if builder.flags.static_only {
318        builder.array(REDUCER_BUFFER_SIZE)
319    } else {
320        // This points to the same memory. Only the length of this object will change when
321        // truncating.
322        let ret = builder.uninit();
323        builder.assign(&ret, nested_opened_values_buffer.clone());
324        ret
325    };
326
327    let nb_opened_values: Usize<_> = builder.eval(C::N::ZERO);
328    let start_dim_idx: Usize<_> = builder.eval(dim_idx.clone());
329    builder.cycle_tracker_start("verify-batch-reduce-fast-setup");
330    let dims_shifted = dims.shift(builder, start_dim_idx.clone());
331    let opened_values_shifted = opened_values.shift(builder, start_dim_idx);
332    iter_zip!(builder, dims_shifted, opened_values_shifted).for_each(|ptr_vec, builder| {
333        let log_height = builder.iter_ptr_get(&dims_shifted, ptr_vec[0]).log_height;
334        builder
335            .if_eq(log_height, Usize::from(cur_log_height))
336            .then(|builder| {
337                let opened_values = builder.iter_ptr_get(&opened_values_shifted, ptr_vec[1]);
338                builder.set_value(
339                    &nested_opened_values_buffer,
340                    nb_opened_values.clone(),
341                    opened_values.clone(),
342                );
343                builder.assign(&nb_opened_values, nb_opened_values.clone() + C::N::ONE);
344            });
345    });
346    builder.assign(&dim_idx, dim_idx.clone() + nb_opened_values.clone());
347    builder.cycle_tracker_end("verify-batch-reduce-fast-setup");
348
349    nested_opened_values_buffer.truncate(builder, nb_opened_values);
350    let h = nested_opened_values_buffer.p2_digest(builder);
351    builder.cycle_tracker_end("verify-batch-reduce-fast");
352    h
353}
354
355struct NestedOpenedValuesReducerVar<C: Config> {
356    buffer: NestedOpenedValues<C>,
357}
358impl<C: Config> NestedOpenedValuesReducerVar<C> {
359    fn reduce_fast(
360        &self,
361        builder: &mut Builder<C>,
362        dim_idx: Usize<C::N>,
363        dims: &Array<C, DimensionsVariable<C>>,
364        cur_log_height: usize,
365        nested_opened_values: &NestedOpenedValues<C>,
366    ) -> DigestVariable<C> {
367        match nested_opened_values {
368            NestedOpenedValues::Felt(opened_values) => {
369                let buffer = match &self.buffer {
370                    NestedOpenedValues::Felt(buffer) => buffer,
371                    NestedOpenedValues::Ext(_) => unreachable!(),
372                };
373                reduce_fast(
374                    builder,
375                    dim_idx,
376                    dims,
377                    cur_log_height,
378                    opened_values,
379                    buffer,
380                )
381            }
382            NestedOpenedValues::Ext(opened_values) => {
383                let buffer = match &self.buffer {
384                    NestedOpenedValues::Felt(_) => unreachable!(),
385                    NestedOpenedValues::Ext(buffer) => buffer,
386                };
387                reduce_fast(
388                    builder,
389                    dim_idx,
390                    dims,
391                    cur_log_height,
392                    opened_values,
393                    buffer,
394                )
395            }
396        }
397    }
398}
399
400/// 8192 is just a random large enough number.
401const REDUCER_BUFFER_SIZE: usize = 8192;
402
403impl<C: Config> NestedOpenedValues<C> {
404    fn create_reducer(&self, builder: &mut Builder<C>) -> NestedOpenedValuesReducerVar<C> {
405        NestedOpenedValuesReducerVar {
406            buffer: match self {
407                NestedOpenedValues::Felt(_) => {
408                    NestedOpenedValues::Felt(builder.array(REDUCER_BUFFER_SIZE))
409                }
410                NestedOpenedValues::Ext(_) => {
411                    NestedOpenedValues::Ext(builder.array(REDUCER_BUFFER_SIZE))
412                }
413            },
414        }
415    }
416}
openvm_native_recursion/fri/mod.rs

openvm_native_recursion/fri/
mod.rs
