openvm_native_recursion/fri/
mod.rs

Help
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)]
33#[allow(unused_variables)]
34pub fn verify_query<C: Config>(
35    builder: &mut Builder<C>,
36    config: &FriConfigVariable<C>,
37    commit_phase_commits: &Array<C, DigestVariable<C>>,
38    index_bits: &Array<C, Var<C::N>>,
39    proof: &FriQueryProofVariable<C>,
40    betas: &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) -> Ext<C::F, C::EF>
44where
45    C::F: TwoAdicField,
46    C::EF: TwoAdicField,
47{
48    builder.cycle_tracker_start("verify-query");
49    let folded_eval: Ext<C::F, C::EF> = builder.eval(C::F::ZERO);
50    let two_adic_generator_f = config.get_two_adic_generator(builder, log_max_lde_height);
51
52    let two_adic_gen_ext = two_adic_generator_f.to_operand().symbolic();
53    let two_adic_generator_ef: Ext<_, _> = builder.eval(two_adic_gen_ext);
54
55    let index_bits_truncated = index_bits.slice(builder, 0, log_max_lde_height);
56    let x = builder.exp_bits_big_endian(two_adic_generator_ef, &index_bits_truncated);
57
58    // proof.commit_phase_openings.len() == log_max_lde_height - log_blowup
59    builder.assert_usize_eq(
60        proof.commit_phase_openings.len(),
61        commit_phase_commits.len(),
62    );
63    builder
64        .range(0, commit_phase_commits.len())
65        .for_each(|i_vec, builder| {
66            let i = i_vec[0];
67            let log_folded_height = builder.eval_expr(log_max_lde_height - i - C::N::ONE);
68            let log_folded_height_plus_one = builder.eval_expr(log_folded_height + C::N::ONE);
69            let commit = builder.get(commit_phase_commits, i);
70            let step = builder.get(&proof.commit_phase_openings, i);
71            let beta = builder.get(betas, i);
72
73            // reduced_openings.len() == MAX_TWO_ADICITY >= log_max_lde_height >= log_folded_height_plus_one
74            let reduced_opening = builder.get(reduced_openings, log_folded_height_plus_one);
75            builder.assign(&folded_eval, folded_eval + reduced_opening);
76
77            let index_bit = builder.get(index_bits, i);
78            let index_sibling_mod_2: Var<C::N> =
79                builder.eval(SymbolicVar::from(C::N::ONE) - index_bit);
80            let i_plus_one = builder.eval_expr(i + RVar::one());
81            let index_pair = index_bits.shift(builder, i_plus_one);
82
83            let evals: Array<C, Ext<C::F, C::EF>> = builder.array(2);
84            let eval_0: Ext<C::F, C::EF>;
85            let eval_1: Ext<C::F, C::EF>;
86            if builder.flags.static_only {
87                [eval_0, eval_1] = cond_eval(
88                    builder,
89                    index_sibling_mod_2,
90                    step.sibling_value,
91                    folded_eval,
92                );
93                builder.set_value(&evals, 0, eval_0);
94                builder.set_value(&evals, 1, eval_1);
95            } else {
96                builder.set_value(&evals, 0, folded_eval);
97                builder.set_value(&evals, 1, folded_eval);
98                // This is faster than branching.
99                builder.set_value(&evals, index_sibling_mod_2, step.sibling_value);
100                eval_0 = builder.get(&evals, 0);
101                eval_1 = builder.get(&evals, 1);
102            }
103
104            let dims = DimensionsVariable::<C> {
105                log_height: builder.eval(log_folded_height),
106            };
107            let dims_slice: Array<C, DimensionsVariable<C>> = builder.array(1);
108            builder.set_value(&dims_slice, 0, dims);
109
110            let opened_values = builder.array(1);
111            builder.set_value(&opened_values, 0, evals);
112            builder.cycle_tracker_start("verify-batch-ext");
113            verify_batch::<C>(
114                builder,
115                &commit,
116                dims_slice,
117                index_pair,
118                &NestedOpenedValues::Ext(opened_values),
119                &step.opening_proof,
120            );
121            builder.cycle_tracker_end("verify-batch-ext");
122
123            let two_adic_generator_one = config.get_two_adic_generator(builder, Usize::from(1));
124
125            let [xs_0, xs_1]: [Ext<_, _>; 2] =
126                cond_eval(builder, index_sibling_mod_2, x * two_adic_generator_one, x);
127
128            builder.assign(
129                &folded_eval,
130                eval_0 + (beta - xs_0) * (eval_1 - eval_0) / (xs_1 - xs_0),
131            );
132
133            builder.assign(&x, x * x);
134        });
135
136    builder.cycle_tracker_end("verify-query");
137    folded_eval
138}
139
140#[allow(clippy::type_complexity)]
141pub enum NestedOpenedValues<C: Config> {
142    Felt(Array<C, Array<C, Felt<C::F>>>),
143    Ext(Array<C, Array<C, Ext<C::F, C::EF>>>),
144}
145
146/// Verifies a batch opening.
147///
148/// Assumes the dimensions have already been sorted by tallest first.
149///
150/// Reference: <https://github.com/Plonky3/Plonky3/blob/4809fa7bedd9ba8f6f5d3267b1592618e3776c57/merkle-tree/src/mmcs.rs#L92>
151#[allow(clippy::type_complexity)]
152#[allow(unused_variables)]
153pub fn verify_batch<C: Config>(
154    builder: &mut Builder<C>,
155    commit: &DigestVariable<C>,
156    dimensions: Array<C, DimensionsVariable<C>>,
157    index_bits: Array<C, Var<C::N>>,
158    opened_values: &NestedOpenedValues<C>,
159    proof: &HintSlice<C>,
160) {
161    if builder.flags.static_only {
162        verify_batch_static(
163            builder,
164            commit,
165            dimensions,
166            index_bits,
167            opened_values,
168            proof,
169        );
170        return;
171    }
172
173    let dimensions = match dimensions {
174        Array::Dyn(ptr, len) => Array::Dyn(ptr, len.clone()),
175        _ => panic!("Expected a dynamic array of felts"),
176    };
177    let commit = match commit {
178        DigestVariable::Felt(arr) => arr,
179        _ => panic!("Expected a dynamic array of felts"),
180    };
181    match opened_values {
182        NestedOpenedValues::Felt(opened_values) => builder.verify_batch_felt(
183            &dimensions,
184            opened_values,
185            proof.id.get_var(),
186            &index_bits,
187            commit,
188        ),
189        NestedOpenedValues::Ext(opened_values) => builder.verify_batch_ext(
190            &dimensions,
191            opened_values,
192            proof.id.get_var(),
193            &index_bits,
194            commit,
195        ),
196    };
197}
198
199/// [static version] Verifies a batch opening.
200///
201/// Assumes the dimensions have already been sorted by tallest first.
202///
203/// Reference: <https://github.com/Plonky3/Plonky3/blob/4809fa7bedd9ba8f6f5d3267b1592618e3776c57/merkle-tree/src/mmcs.rs#L92>
204#[allow(clippy::type_complexity)]
205#[allow(unused_variables)]
206pub fn verify_batch_static<C: Config>(
207    builder: &mut Builder<C>,
208    commit: &DigestVariable<C>,
209    dimensions: Array<C, DimensionsVariable<C>>,
210    index_bits: Array<C, Var<C::N>>,
211    opened_values: &NestedOpenedValues<C>,
212    proof: &HintSlice<C>,
213) {
214    let commit: OuterDigestVariable<C> = if let DigestVariable::Var(commit) = commit {
215        commit.vec().try_into().unwrap()
216    } else {
217        panic!("Expected a Var commitment");
218    };
219    // The index of which table to process next.
220    let index: Usize<C::N> = builder.eval(C::N::ZERO);
221    // The height of the current layer (padded).
222    let mut current_log_height = builder.get(&dimensions, index.clone()).log_height.value();
223    // Reduce all the tables that have the same height to a single root.
224    let reducer = opened_values.create_reducer(builder);
225    let mut root = reducer
226        .reduce_fast(
227            builder,
228            index.clone(),
229            &dimensions,
230            current_log_height,
231            opened_values,
232        )
233        .into_outer_digest();
234
235    // For each sibling in the proof, reconstruct the root.
236    let witness_refs = builder.get_witness_refs(proof.id.clone()).to_vec();
237    for (i, &witness_ref) in witness_refs.iter().enumerate() {
238        let sibling: OuterDigestVariable<C> = [witness_ref.into()];
239        let bit = builder.get(&index_bits, i);
240
241        let [left, right]: [Var<_>; 2] = cond_eval(builder, bit, root[0], sibling[0]);
242        root = builder.p2_compress([[left], [right]]);
243        current_log_height -= 1;
244
245        builder
246            .if_ne(index.clone(), dimensions.len())
247            .then(|builder| {
248                let next_log_height = builder.get(&dimensions, index.clone()).log_height;
249                builder
250                    .if_eq(next_log_height, Usize::from(current_log_height))
251                    .then(|builder| {
252                        let next_height_openings_digest = reducer
253                            .reduce_fast(
254                                builder,
255                                index.clone(),
256                                &dimensions,
257                                current_log_height,
258                                opened_values,
259                            )
260                            .into_outer_digest();
261                        root = builder.p2_compress([root, next_height_openings_digest]);
262                    });
263            })
264    }
265
266    builder.assert_var_eq(root[0], commit[0]);
267}
268
269#[allow(clippy::type_complexity)]
270fn reduce_fast<C: Config, V: MemVariable<C>>(
271    builder: &mut Builder<C>,
272    dim_idx: Usize<C::N>,
273    dims: &Array<C, DimensionsVariable<C>>,
274    cur_log_height: usize,
275    opened_values: &Array<C, Array<C, V>>,
276    nested_opened_values_buffer: &Array<C, Array<C, V>>,
277) -> DigestVariable<C>
278where
279    Array<C, Array<C, V>>: CanPoseidon2Digest<C>,
280{
281    builder.cycle_tracker_start("verify-batch-reduce-fast");
282
283    // `nested_opened_values_buffer` will be truncated in this function. We want to avoid modifying
284    // the original buffer object, so we create a new one or clone it.
285    let nested_opened_values_buffer = if builder.flags.static_only {
286        builder.array(REDUCER_BUFFER_SIZE)
287    } else {
288        // This points to the same memory. Only the length of this object will change when truncating.
289        let ret = builder.uninit();
290        builder.assign(&ret, nested_opened_values_buffer.clone());
291        ret
292    };
293
294    let nb_opened_values: Usize<_> = builder.eval(C::N::ZERO);
295    let start_dim_idx: Usize<_> = builder.eval(dim_idx.clone());
296    builder.cycle_tracker_start("verify-batch-reduce-fast-setup");
297    let dims_shifted = dims.shift(builder, start_dim_idx.clone());
298    let opened_values_shifted = opened_values.shift(builder, start_dim_idx);
299    iter_zip!(builder, dims_shifted, opened_values_shifted).for_each(|ptr_vec, builder| {
300        let log_height = builder.iter_ptr_get(&dims_shifted, ptr_vec[0]).log_height;
301        builder
302            .if_eq(log_height, Usize::from(cur_log_height))
303            .then(|builder| {
304                let opened_values = builder.iter_ptr_get(&opened_values_shifted, ptr_vec[1]);
305                builder.set_value(
306                    &nested_opened_values_buffer,
307                    nb_opened_values.clone(),
308                    opened_values.clone(),
309                );
310                builder.assign(&nb_opened_values, nb_opened_values.clone() + C::N::ONE);
311            });
312    });
313    builder.assign(&dim_idx, dim_idx.clone() + nb_opened_values.clone());
314    builder.cycle_tracker_end("verify-batch-reduce-fast-setup");
315
316    nested_opened_values_buffer.truncate(builder, nb_opened_values);
317    let h = nested_opened_values_buffer.p2_digest(builder);
318    builder.cycle_tracker_end("verify-batch-reduce-fast");
319    h
320}
321
322struct NestedOpenedValuesReducerVar<C: Config> {
323    buffer: NestedOpenedValues<C>,
324}
325impl<C: Config> NestedOpenedValuesReducerVar<C> {
326    fn reduce_fast(
327        &self,
328        builder: &mut Builder<C>,
329        dim_idx: Usize<C::N>,
330        dims: &Array<C, DimensionsVariable<C>>,
331        cur_log_height: usize,
332        nested_opened_values: &NestedOpenedValues<C>,
333    ) -> DigestVariable<C> {
334        match nested_opened_values {
335            NestedOpenedValues::Felt(opened_values) => {
336                let buffer = match &self.buffer {
337                    NestedOpenedValues::Felt(buffer) => buffer,
338                    NestedOpenedValues::Ext(_) => unreachable!(),
339                };
340                reduce_fast(
341                    builder,
342                    dim_idx,
343                    dims,
344                    cur_log_height,
345                    opened_values,
346                    buffer,
347                )
348            }
349            NestedOpenedValues::Ext(opened_values) => {
350                let buffer = match &self.buffer {
351                    NestedOpenedValues::Felt(_) => unreachable!(),
352                    NestedOpenedValues::Ext(buffer) => buffer,
353                };
354                reduce_fast(
355                    builder,
356                    dim_idx,
357                    dims,
358                    cur_log_height,
359                    opened_values,
360                    buffer,
361                )
362            }
363        }
364    }
365}
366
367/// 8192 is just a random large enough number.
368const REDUCER_BUFFER_SIZE: usize = 8192;
369
370impl<C: Config> NestedOpenedValues<C> {
371    fn create_reducer(&self, builder: &mut Builder<C>) -> NestedOpenedValuesReducerVar<C> {
372        NestedOpenedValuesReducerVar {
373            buffer: match self {
374                NestedOpenedValues::Felt(_) => {
375                    NestedOpenedValues::Felt(builder.array(REDUCER_BUFFER_SIZE))
376                }
377                NestedOpenedValues::Ext(_) => {
378                    NestedOpenedValues::Ext(builder.array(REDUCER_BUFFER_SIZE))
379                }
380            },
381        }
382    }
383}
openvm_native_recursion/fri/mod.rs

openvm_native_recursion/fri/
mod.rs
