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

kimchi/
verifier_index.rs
