kimchi/
verifier_index.rs

1//! This module implements the verifier index as [`VerifierIndex`].
2//! You can derive this struct from the [`ProverIndex`] struct.
3
4use crate::{
5    alphas::Alphas,
6    circuits::{
7        berkeley_columns::{BerkeleyChallengeTerm, Column},
8        expr::{Linearization, PolishToken},
9        lookup::{index::LookupSelectors, lookups::LookupInfo},
10        polynomials::permutation::{vanishes_on_last_n_rows, zk_w},
11        wires::{COLUMNS, PERMUTS},
12    },
13    curve::KimchiCurve,
14};
15use alloc::{sync::Arc, vec::Vec};
16use ark_ff::PrimeField;
17use ark_poly::{univariate::DensePolynomial, Radix2EvaluationDomain as D};
18#[cfg(not(feature = "std"))]
19use core::cell::OnceCell as OnceLock;
20use mina_poseidon::FqSponge;
21use poly_commitment::{
22    commitment::{absorb_commitment, CommitmentCurve, PolyComm},
23    SRS,
24};
25use serde::{de::DeserializeOwned, Deserialize, Serialize};
26use serde_with::serde_as;
27
28#[cfg(feature = "prover")]
29use {crate::prover_index::ProverIndex, ark_ff::One, core::array};
30
31#[cfg(feature = "std")]
32use std::{
33    fs::{File, OpenOptions},
34    io::{BufReader, BufWriter, Seek, SeekFrom::Start},
35    path::Path,
36    sync::OnceLock,
37};
38
39//~spec:startcode
40#[serde_as]
41#[derive(Serialize, Deserialize, Debug, Clone)]
42pub struct LookupVerifierIndex<G: CommitmentCurve> {
43    pub joint_lookup_used: bool,
44    #[serde(bound = "PolyComm<G>: Serialize + DeserializeOwned")]
45    pub lookup_table: Vec<PolyComm<G>>,
46    #[serde(bound = "PolyComm<G>: Serialize + DeserializeOwned")]
47    pub lookup_selectors: LookupSelectors<PolyComm<G>>,
48
49    /// Table IDs for the lookup values.
50    /// This may be `None` if all lookups originate from table 0.
51    #[serde(bound = "PolyComm<G>: Serialize + DeserializeOwned")]
52    pub table_ids: Option<PolyComm<G>>,
53
54    /// Information about the specific lookups used
55    pub lookup_info: LookupInfo,
56
57    /// An optional selector polynomial for runtime tables
58    #[serde(bound = "PolyComm<G>: Serialize + DeserializeOwned")]
59    pub runtime_tables_selector: Option<PolyComm<G>>,
60}
61
62#[serde_as]
63#[derive(Serialize, Deserialize, Debug, Clone)]
64pub struct VerifierIndex<const FULL_ROUNDS: usize, G: KimchiCurve<FULL_ROUNDS>, Srs> {
65    /// evaluation domain
66    #[serde_as(as = "o1_utils::serialization::SerdeAs")]
67    pub domain: D<G::ScalarField>,
68    /// maximal size of polynomial section
69    pub max_poly_size: usize,
70    /// the number of randomized rows to achieve zero knowledge
71    pub zk_rows: u64,
72    /// polynomial commitment keys
73    #[serde(skip)]
74    pub srs: Arc<Srs>,
75    /// number of public inputs
76    pub public: usize,
77    /// number of previous evaluation challenges, for recursive proving
78    pub prev_challenges: usize,
79
80    // index polynomial commitments
81    /// permutation commitment array
82    #[serde(bound = "PolyComm<G>: Serialize + DeserializeOwned")]
83    pub sigma_comm: [PolyComm<G>; PERMUTS],
84    /// coefficient commitment array
85    #[serde(bound = "PolyComm<G>: Serialize + DeserializeOwned")]
86    pub coefficients_comm: [PolyComm<G>; COLUMNS],
87    /// generic gate commitment array
88    #[serde(bound = "PolyComm<G>: Serialize + DeserializeOwned")]
89    pub generic_comm: PolyComm<G>,
90
91    // poseidon polynomial commitments
92    /// poseidon constraint selector polynomial commitment
93    #[serde(bound = "PolyComm<G>: Serialize + DeserializeOwned")]
94    pub psm_comm: PolyComm<G>,
95
96    // ECC arithmetic polynomial commitments
97    /// EC addition selector polynomial commitment
98    #[serde(bound = "PolyComm<G>: Serialize + DeserializeOwned")]
99    pub complete_add_comm: PolyComm<G>,
100    /// EC variable base scalar multiplication selector polynomial commitment
101    #[serde(bound = "PolyComm<G>: Serialize + DeserializeOwned")]
102    pub mul_comm: PolyComm<G>,
103    /// endoscalar multiplication selector polynomial commitment
104    #[serde(bound = "PolyComm<G>: Serialize + DeserializeOwned")]
105    pub emul_comm: PolyComm<G>,
106    /// endoscalar multiplication scalar computation selector polynomial commitment
107    #[serde(bound = "PolyComm<G>: Serialize + DeserializeOwned")]
108    pub endomul_scalar_comm: PolyComm<G>,
109
110    /// RangeCheck0 polynomial commitments
111    #[serde(bound = "Option<PolyComm<G>>: Serialize + DeserializeOwned")]
112    pub range_check0_comm: Option<PolyComm<G>>,
113
114    /// RangeCheck1 polynomial commitments
115    #[serde(bound = "Option<PolyComm<G>>: Serialize + DeserializeOwned")]
116    pub range_check1_comm: Option<PolyComm<G>>,
117
118    /// Foreign field addition gates polynomial commitments
119    #[serde(bound = "Option<PolyComm<G>>: Serialize + DeserializeOwned")]
120    pub foreign_field_add_comm: Option<PolyComm<G>>,
121
122    /// Foreign field multiplication gates polynomial commitments
123    #[serde(bound = "Option<PolyComm<G>>: Serialize + DeserializeOwned")]
124    pub foreign_field_mul_comm: Option<PolyComm<G>>,
125
126    /// Xor commitments
127    #[serde(bound = "Option<PolyComm<G>>: Serialize + DeserializeOwned")]
128    pub xor_comm: Option<PolyComm<G>>,
129
130    /// Rot commitments
131    #[serde(bound = "Option<PolyComm<G>>: Serialize + DeserializeOwned")]
132    pub rot_comm: Option<PolyComm<G>>,
133
134    /// wire coordinate shifts
135    #[serde_as(as = "[o1_utils::serialization::SerdeAs; PERMUTS]")]
136    pub shift: [G::ScalarField; PERMUTS],
137    /// zero-knowledge polynomial
138    #[serde(skip)]
139    pub permutation_vanishing_polynomial_m: OnceLock<DensePolynomial<G::ScalarField>>,
140    // TODO(mimoo): isn't this redundant with domain.d1.group_gen ?
141    /// domain offset for zero-knowledge
142    #[serde(skip)]
143    pub w: OnceLock<G::ScalarField>,
144    /// endoscalar coefficient
145    #[serde(skip)]
146    pub endo: G::ScalarField,
147
148    #[serde(bound = "PolyComm<G>: Serialize + DeserializeOwned")]
149    pub lookup_index: Option<LookupVerifierIndex<G>>,
150
151    #[serde(skip)]
152    pub linearization:
153        Linearization<Vec<PolishToken<G::ScalarField, Column, BerkeleyChallengeTerm>>, Column>,
154    /// The mapping between powers of alpha and constraints
155    #[serde(skip)]
156    pub powers_of_alpha: Alphas<G::ScalarField>,
157}
158//~spec:endcode
159
160#[cfg(feature = "prover")]
161impl<const FULL_ROUNDS: usize, G: KimchiCurve<FULL_ROUNDS>, Srs: SRS<G>>
162    ProverIndex<FULL_ROUNDS, G, Srs>
163where
164    G::BaseField: PrimeField,
165{
166    /// Produces the [`VerifierIndex`] from the prover's [`ProverIndex`].
167    ///
168    /// # Panics
169    ///
170    /// Will panic if `srs` cannot be in `cell`.
171    pub fn verifier_index(&self) -> VerifierIndex<FULL_ROUNDS, G, Srs>
172    where
173        VerifierIndex<FULL_ROUNDS, G, Srs>: Clone,
174    {
175        if let Some(verifier_index) = &self.verifier_index {
176            return verifier_index.clone();
177        }
178
179        let mask_fixed = |commitment: PolyComm<G>| {
180            let blinders = commitment.map(|_| G::ScalarField::one());
181            self.srs
182                .mask_custom(commitment, &blinders)
183                .unwrap()
184                .commitment
185        };
186
187        let domain = self.cs.domain.d1;
188
189        let lookup_index = {
190            self.cs
191                .lookup_constraint_system
192                .get()
193                .as_ref()
194                .unwrap()
195                .as_ref()
196                .map(|cs| LookupVerifierIndex {
197                    joint_lookup_used: cs.configuration.lookup_info.features.joint_lookup_used,
198                    lookup_info: cs.configuration.lookup_info,
199                    lookup_selectors: cs
200                        .lookup_selectors
201                        .as_ref()
202                        .map(|e| self.srs.commit_evaluations_non_hiding(domain, e)),
203                    lookup_table: cs
204                        .lookup_table8
205                        .iter()
206                        .map(|e| mask_fixed(self.srs.commit_evaluations_non_hiding(domain, e)))
207                        .collect(),
208                    table_ids: cs.table_ids8.as_ref().map(|table_ids8| {
209                        mask_fixed(self.srs.commit_evaluations_non_hiding(domain, table_ids8))
210                    }),
211                    runtime_tables_selector: cs
212                        .runtime_selector
213                        .as_ref()
214                        .map(|e| self.srs.commit_evaluations_non_hiding(domain, e)),
215                })
216        };
217
218        // Defined as variable for convenience to avoid verbosity
219        let column_evaluations = self.column_evaluations.get();
220
221        // TODO: Switch to commit_evaluations for all index polys
222        VerifierIndex {
223            domain,
224            max_poly_size: self.max_poly_size,
225            zk_rows: self.cs.zk_rows,
226            powers_of_alpha: self.powers_of_alpha.clone(),
227            public: self.cs.public,
228            prev_challenges: self.cs.prev_challenges,
229            srs: Arc::clone(&self.srs),
230
231            sigma_comm: array::from_fn(|i| {
232                self.srs.commit_evaluations_non_hiding(
233                    domain,
234                    &column_evaluations.permutation_coefficients8[i],
235                )
236            }),
237            coefficients_comm: array::from_fn(|i| {
238                self.srs
239                    .commit_evaluations_non_hiding(domain, &column_evaluations.coefficients8[i])
240            }),
241            generic_comm: mask_fixed(
242                self.srs
243                    .commit_evaluations_non_hiding(domain, &column_evaluations.generic_selector4),
244            ),
245
246            psm_comm: mask_fixed(
247                self.srs
248                    .commit_evaluations_non_hiding(domain, &column_evaluations.poseidon_selector8),
249            ),
250
251            complete_add_comm: mask_fixed(
252                self.srs.commit_evaluations_non_hiding(
253                    domain,
254                    &column_evaluations.complete_add_selector4,
255                ),
256            ),
257            mul_comm: mask_fixed(
258                self.srs
259                    .commit_evaluations_non_hiding(domain, &column_evaluations.mul_selector8),
260            ),
261            emul_comm: mask_fixed(
262                self.srs
263                    .commit_evaluations_non_hiding(domain, &column_evaluations.emul_selector8),
264            ),
265
266            endomul_scalar_comm: mask_fixed(self.srs.commit_evaluations_non_hiding(
267                domain,
268                &column_evaluations.endomul_scalar_selector8,
269            )),
270
271            range_check0_comm: column_evaluations
272                .range_check0_selector8
273                .as_ref()
274                .map(|eval8| self.srs.commit_evaluations_non_hiding(domain, eval8)),
275
276            range_check1_comm: column_evaluations
277                .range_check1_selector8
278                .as_ref()
279                .map(|eval8| self.srs.commit_evaluations_non_hiding(domain, eval8)),
280
281            foreign_field_add_comm: column_evaluations
282                .foreign_field_add_selector8
283                .as_ref()
284                .map(|eval8| self.srs.commit_evaluations_non_hiding(domain, eval8)),
285
286            foreign_field_mul_comm: column_evaluations
287                .foreign_field_mul_selector8
288                .as_ref()
289                .map(|eval8| self.srs.commit_evaluations_non_hiding(domain, eval8)),
290            xor_comm: column_evaluations
291                .xor_selector8
292                .as_ref()
293                .map(|eval8| self.srs.commit_evaluations_non_hiding(domain, eval8)),
294            rot_comm: column_evaluations
295                .rot_selector8
296                .as_ref()
297                .map(|eval8| self.srs.commit_evaluations_non_hiding(domain, eval8)),
298
299            shift: self.cs.shift,
300            permutation_vanishing_polynomial_m: {
301                let cell = OnceLock::new();
302                cell.set(
303                    self.cs
304                        .precomputations()
305                        .permutation_vanishing_polynomial_m
306                        .clone(),
307                )
308                .unwrap();
309                cell
310            },
311            w: {
312                let cell = OnceLock::new();
313                cell.set(zk_w(self.cs.domain.d1, self.cs.zk_rows)).unwrap();
314                cell
315            },
316            endo: self.cs.endo,
317            lookup_index,
318            linearization: self.linearization.clone(),
319        }
320    }
321}
322
323impl<const FULL_ROUNDS: usize, G: KimchiCurve<FULL_ROUNDS>, Srs>
324    VerifierIndex<FULL_ROUNDS, G, Srs>
325{
326    /// Gets srs from [`VerifierIndex`] lazily
327    pub fn srs(&self) -> &Arc<Srs>
328    where
329        G::BaseField: PrimeField,
330        Srs: SRS<G>,
331    {
332        &self.srs
333    }
334
335    /// Gets permutation_vanishing_polynomial_m from [`VerifierIndex`] lazily
336    pub fn permutation_vanishing_polynomial_m(&self) -> &DensePolynomial<G::ScalarField> {
337        self.permutation_vanishing_polynomial_m
338            .get_or_init(|| vanishes_on_last_n_rows(self.domain, self.zk_rows))
339    }
340
341    /// Gets w from [`VerifierIndex`] lazily
342    pub fn w(&self) -> &G::ScalarField {
343        self.w.get_or_init(|| zk_w(self.domain, self.zk_rows))
344    }
345
346    /// Deserializes a [`VerifierIndex`] from a file, given a pointer to an SRS and an optional offset in the file.
347    ///
348    /// # Errors
349    ///
350    /// Will give error if it fails to deserialize from file or unable to set `srs` in `verifier_index`.
351    #[cfg(feature = "std")]
352    pub fn from_file(
353        srs: Arc<Srs>,
354        path: &Path,
355        offset: Option<u64>,
356        // TODO: we shouldn't have to pass these
357        endo: G::ScalarField,
358    ) -> Result<Self, String>
359    where
360        Srs: Default,
361    {
362        // open file
363        let file = File::open(path).map_err(|e| e.to_string())?;
364
365        // offset
366        let mut reader = BufReader::new(file);
367        if let Some(offset) = offset {
368            reader.seek(Start(offset)).map_err(|e| e.to_string())?;
369        }
370
371        // deserialize
372        let mut verifier_index = Self::deserialize(&mut rmp_serde::Deserializer::new(reader))
373            .map_err(|e| e.to_string())?;
374
375        // fill in the rest
376        verifier_index.srs = srs;
377        verifier_index.endo = endo;
378
379        Ok(verifier_index)
380    }
381
382    /// Writes a [`VerifierIndex`] to a file, potentially appending it to the already-existing content (if append is set to true)
383    // TODO: append should be a bool, not an option
384    /// # Errors
385    ///
386    /// Will give error if it fails to open a file or writes to the file.
387    ///
388    /// # Panics
389    ///
390    /// Will panic if `path` is invalid or `file serialization` has issue.
391    #[cfg(feature = "std")]
392    pub fn to_file(&self, path: &Path, append: Option<bool>) -> Result<(), String> {
393        let append = append.unwrap_or(true);
394        let file = OpenOptions::new()
395            .append(append)
396            .open(path)
397            .map_err(|e| e.to_string())?;
398
399        let writer = BufWriter::new(file);
400
401        self.serialize(&mut rmp_serde::Serializer::new(writer))
402            .map_err(|e| e.to_string())
403    }
404
405    /// Compute the digest of the [`VerifierIndex`], which can be used for the Fiat-Shamir
406    /// transformation while proving / verifying.
407    pub fn digest<EFqSponge: Clone + FqSponge<G::BaseField, G, G::ScalarField, FULL_ROUNDS>>(
408        &self,
409    ) -> G::BaseField {
410        let mut fq_sponge = EFqSponge::new(G::other_curve_sponge_params());
411        // We fully expand this to make the compiler check that we aren't missing any commitments
412        let VerifierIndex {
413            domain: _,
414            max_poly_size: _,
415            zk_rows: _,
416            srs: _,
417            public: _,
418            prev_challenges: _,
419
420            // Always present
421            sigma_comm,
422            coefficients_comm,
423            generic_comm,
424            psm_comm,
425            complete_add_comm,
426            mul_comm,
427            emul_comm,
428            endomul_scalar_comm,
429
430            // Optional gates
431            range_check0_comm,
432            range_check1_comm,
433            foreign_field_add_comm,
434            foreign_field_mul_comm,
435            xor_comm,
436            rot_comm,
437
438            // Lookup index; optional
439            lookup_index,
440
441            shift: _,
442            permutation_vanishing_polynomial_m: _,
443            w: _,
444            endo: _,
445
446            linearization: _,
447            powers_of_alpha: _,
448        } = &self;
449
450        // Always present
451
452        for comm in sigma_comm.iter() {
453            absorb_commitment(&mut fq_sponge, comm);
454        }
455        for comm in coefficients_comm.iter() {
456            absorb_commitment(&mut fq_sponge, comm);
457        }
458        absorb_commitment(&mut fq_sponge, generic_comm);
459        absorb_commitment(&mut fq_sponge, psm_comm);
460        absorb_commitment(&mut fq_sponge, complete_add_comm);
461        absorb_commitment(&mut fq_sponge, mul_comm);
462        absorb_commitment(&mut fq_sponge, emul_comm);
463        absorb_commitment(&mut fq_sponge, endomul_scalar_comm);
464
465        // Optional gates
466
467        if let Some(range_check0_comm) = range_check0_comm {
468            absorb_commitment(&mut fq_sponge, range_check0_comm);
469        }
470
471        if let Some(range_check1_comm) = range_check1_comm {
472            absorb_commitment(&mut fq_sponge, range_check1_comm);
473        }
474
475        if let Some(foreign_field_mul_comm) = foreign_field_mul_comm {
476            absorb_commitment(&mut fq_sponge, foreign_field_mul_comm);
477        }
478
479        if let Some(foreign_field_add_comm) = foreign_field_add_comm {
480            absorb_commitment(&mut fq_sponge, foreign_field_add_comm);
481        }
482
483        if let Some(xor_comm) = xor_comm {
484            absorb_commitment(&mut fq_sponge, xor_comm);
485        }
486
487        if let Some(rot_comm) = rot_comm {
488            absorb_commitment(&mut fq_sponge, rot_comm);
489        }
490
491        // Lookup index; optional
492
493        if let Some(LookupVerifierIndex {
494            joint_lookup_used: _,
495            lookup_info: _,
496            lookup_table,
497            table_ids,
498            runtime_tables_selector,
499
500            lookup_selectors:
501                LookupSelectors {
502                    xor,
503                    lookup,
504                    range_check,
505                    ffmul,
506                },
507        }) = lookup_index
508        {
509            for entry in lookup_table {
510                absorb_commitment(&mut fq_sponge, entry);
511            }
512            if let Some(table_ids) = table_ids {
513                absorb_commitment(&mut fq_sponge, table_ids);
514            }
515            if let Some(runtime_tables_selector) = runtime_tables_selector {
516                absorb_commitment(&mut fq_sponge, runtime_tables_selector);
517            }
518
519            if let Some(xor) = xor {
520                absorb_commitment(&mut fq_sponge, xor);
521            }
522            if let Some(lookup) = lookup {
523                absorb_commitment(&mut fq_sponge, lookup);
524            }
525            if let Some(range_check) = range_check {
526                absorb_commitment(&mut fq_sponge, range_check);
527            }
528            if let Some(ffmul) = ffmul {
529                absorb_commitment(&mut fq_sponge, ffmul);
530            }
531        }
532        fq_sponge.digest_fq()
533    }
534}
kimchi/verifier_index.rs

kimchi/
verifier_index.rs
