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    OpenProof, SRS as _,
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<G: KimchiCurve, OpeningProof: OpenProof<G>> {
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    #[serde(bound(deserialize = "OpeningProof::SRS: Default"))]
70    pub srs: Arc<OpeningProof::SRS>,
71    /// number of public inputs
72    pub public: usize,
73    /// number of previous evaluation challenges, for recursive proving
74    pub prev_challenges: usize,
75
76    // index polynomial commitments
77    /// permutation commitment array
78    #[serde(bound = "PolyComm<G>: Serialize + DeserializeOwned")]
79    pub sigma_comm: [PolyComm<G>; PERMUTS],
80    /// coefficient commitment array
81    #[serde(bound = "PolyComm<G>: Serialize + DeserializeOwned")]
82    pub coefficients_comm: [PolyComm<G>; COLUMNS],
83    /// generic gate commitment array
84    #[serde(bound = "PolyComm<G>: Serialize + DeserializeOwned")]
85    pub generic_comm: PolyComm<G>,
86
87    // poseidon polynomial commitments
88    /// poseidon constraint selector polynomial commitment
89    #[serde(bound = "PolyComm<G>: Serialize + DeserializeOwned")]
90    pub psm_comm: PolyComm<G>,
91
92    // ECC arithmetic polynomial commitments
93    /// EC addition selector polynomial commitment
94    #[serde(bound = "PolyComm<G>: Serialize + DeserializeOwned")]
95    pub complete_add_comm: PolyComm<G>,
96    /// EC variable base scalar multiplication selector polynomial commitment
97    #[serde(bound = "PolyComm<G>: Serialize + DeserializeOwned")]
98    pub mul_comm: PolyComm<G>,
99    /// endoscalar multiplication selector polynomial commitment
100    #[serde(bound = "PolyComm<G>: Serialize + DeserializeOwned")]
101    pub emul_comm: PolyComm<G>,
102    /// endoscalar multiplication scalar computation selector polynomial commitment
103    #[serde(bound = "PolyComm<G>: Serialize + DeserializeOwned")]
104    pub endomul_scalar_comm: PolyComm<G>,
105
106    /// RangeCheck0 polynomial commitments
107    #[serde(bound = "Option<PolyComm<G>>: Serialize + DeserializeOwned")]
108    pub range_check0_comm: Option<PolyComm<G>>,
109
110    /// RangeCheck1 polynomial commitments
111    #[serde(bound = "Option<PolyComm<G>>: Serialize + DeserializeOwned")]
112    pub range_check1_comm: Option<PolyComm<G>>,
113
114    /// Foreign field addition gates polynomial commitments
115    #[serde(bound = "Option<PolyComm<G>>: Serialize + DeserializeOwned")]
116    pub foreign_field_add_comm: Option<PolyComm<G>>,
117
118    /// Foreign field multiplication gates polynomial commitments
119    #[serde(bound = "Option<PolyComm<G>>: Serialize + DeserializeOwned")]
120    pub foreign_field_mul_comm: Option<PolyComm<G>>,
121
122    /// Xor commitments
123    #[serde(bound = "Option<PolyComm<G>>: Serialize + DeserializeOwned")]
124    pub xor_comm: Option<PolyComm<G>>,
125
126    /// Rot commitments
127    #[serde(bound = "Option<PolyComm<G>>: Serialize + DeserializeOwned")]
128    pub rot_comm: Option<PolyComm<G>>,
129
130    /// wire coordinate shifts
131    #[serde_as(as = "[o1_utils::serialization::SerdeAs; PERMUTS]")]
132    pub shift: [G::ScalarField; PERMUTS],
133    /// zero-knowledge polynomial
134    #[serde(skip)]
135    pub permutation_vanishing_polynomial_m: OnceCell<DensePolynomial<G::ScalarField>>,
136    // TODO(mimoo): isn't this redundant with domain.d1.group_gen ?
137    /// domain offset for zero-knowledge
138    #[serde(skip)]
139    pub w: OnceCell<G::ScalarField>,
140    /// endoscalar coefficient
141    #[serde(skip)]
142    pub endo: G::ScalarField,
143
144    #[serde(bound = "PolyComm<G>: Serialize + DeserializeOwned")]
145    pub lookup_index: Option<LookupVerifierIndex<G>>,
146
147    #[serde(skip)]
148    pub linearization:
149        Linearization<Vec<PolishToken<G::ScalarField, Column, BerkeleyChallengeTerm>>, Column>,
150    /// The mapping between powers of alpha and constraints
151    #[serde(skip)]
152    pub powers_of_alpha: Alphas<G::ScalarField>,
153}
154//~spec:endcode
155
156impl<G: KimchiCurve, OpeningProof: OpenProof<G>> ProverIndex<G, OpeningProof>
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<G, OpeningProof>
166    where
167        VerifierIndex<G, OpeningProof>: 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<G: KimchiCurve, OpeningProof: OpenProof<G>> VerifierIndex<G, OpeningProof> {
318    /// Gets srs from [`VerifierIndex`] lazily
319    pub fn srs(&self) -> &Arc<OpeningProof::SRS>
320    where
321        G::BaseField: PrimeField,
322    {
323        &self.srs
324    }
325
326    /// Gets permutation_vanishing_polynomial_m from [`VerifierIndex`] lazily
327    pub fn permutation_vanishing_polynomial_m(&self) -> &DensePolynomial<G::ScalarField> {
328        self.permutation_vanishing_polynomial_m
329            .get_or_init(|| vanishes_on_last_n_rows(self.domain, self.zk_rows))
330    }
331
332    /// Gets w from [`VerifierIndex`] lazily
333    pub fn w(&self) -> &G::ScalarField {
334        self.w.get_or_init(|| zk_w(self.domain, self.zk_rows))
335    }
336
337    /// Deserializes a [`VerifierIndex`] from a file, given a pointer to an SRS and an optional offset in the file.
338    ///
339    /// # Errors
340    ///
341    /// Will give error if it fails to deserialize from file or unable to set `srs` in `verifier_index`.
342    pub fn from_file(
343        srs: Arc<OpeningProof::SRS>,
344        path: &Path,
345        offset: Option<u64>,
346        // TODO: we shouldn't have to pass these
347        endo: G::ScalarField,
348    ) -> Result<Self, String>
349    where
350        OpeningProof::SRS: Default,
351    {
352        // open file
353        let file = File::open(path).map_err(|e| e.to_string())?;
354
355        // offset
356        let mut reader = BufReader::new(file);
357        if let Some(offset) = offset {
358            reader.seek(Start(offset)).map_err(|e| e.to_string())?;
359        }
360
361        // deserialize
362        let mut verifier_index = Self::deserialize(&mut rmp_serde::Deserializer::new(reader))
363            .map_err(|e| e.to_string())?;
364
365        // fill in the rest
366        verifier_index.srs = srs;
367        verifier_index.endo = endo;
368
369        Ok(verifier_index)
370    }
371
372    /// Writes a [`VerifierIndex`] to a file, potentially appending it to the already-existing content (if append is set to true)
373    // TODO: append should be a bool, not an option
374    /// # Errors
375    ///
376    /// Will give error if it fails to open a file or writes to the file.
377    ///
378    /// # Panics
379    ///
380    /// Will panic if `path` is invalid or `file serialization` has issue.
381    pub fn to_file(&self, path: &Path, append: Option<bool>) -> Result<(), String> {
382        let append = append.unwrap_or(true);
383        let file = OpenOptions::new()
384            .append(append)
385            .open(path)
386            .map_err(|e| e.to_string())?;
387
388        let writer = BufWriter::new(file);
389
390        self.serialize(&mut rmp_serde::Serializer::new(writer))
391            .map_err(|e| e.to_string())
392    }
393
394    /// Compute the digest of the [`VerifierIndex`], which can be used for the Fiat-Shamir
395    /// transformation while proving / verifying.
396    pub fn digest<EFqSponge: Clone + FqSponge<G::BaseField, G, G::ScalarField>>(
397        &self,
398    ) -> G::BaseField {
399        let mut fq_sponge = EFqSponge::new(G::other_curve_sponge_params());
400        // We fully expand this to make the compiler check that we aren't missing any commitments
401        let VerifierIndex {
402            domain: _,
403            max_poly_size: _,
404            zk_rows: _,
405            srs: _,
406            public: _,
407            prev_challenges: _,
408
409            // Always present
410            sigma_comm,
411            coefficients_comm,
412            generic_comm,
413            psm_comm,
414            complete_add_comm,
415            mul_comm,
416            emul_comm,
417            endomul_scalar_comm,
418
419            // Optional gates
420            range_check0_comm,
421            range_check1_comm,
422            foreign_field_add_comm,
423            foreign_field_mul_comm,
424            xor_comm,
425            rot_comm,
426
427            // Lookup index; optional
428            lookup_index,
429
430            shift: _,
431            permutation_vanishing_polynomial_m: _,
432            w: _,
433            endo: _,
434
435            linearization: _,
436            powers_of_alpha: _,
437        } = &self;
438
439        // Always present
440
441        for comm in sigma_comm.iter() {
442            absorb_commitment(&mut fq_sponge, comm);
443        }
444        for comm in coefficients_comm.iter() {
445            absorb_commitment(&mut fq_sponge, comm);
446        }
447        absorb_commitment(&mut fq_sponge, generic_comm);
448        absorb_commitment(&mut fq_sponge, psm_comm);
449        absorb_commitment(&mut fq_sponge, complete_add_comm);
450        absorb_commitment(&mut fq_sponge, mul_comm);
451        absorb_commitment(&mut fq_sponge, emul_comm);
452        absorb_commitment(&mut fq_sponge, endomul_scalar_comm);
453
454        // Optional gates
455
456        if let Some(range_check0_comm) = range_check0_comm {
457            absorb_commitment(&mut fq_sponge, range_check0_comm);
458        }
459
460        if let Some(range_check1_comm) = range_check1_comm {
461            absorb_commitment(&mut fq_sponge, range_check1_comm);
462        }
463
464        if let Some(foreign_field_mul_comm) = foreign_field_mul_comm {
465            absorb_commitment(&mut fq_sponge, foreign_field_mul_comm);
466        }
467
468        if let Some(foreign_field_add_comm) = foreign_field_add_comm {
469            absorb_commitment(&mut fq_sponge, foreign_field_add_comm);
470        }
471
472        if let Some(xor_comm) = xor_comm {
473            absorb_commitment(&mut fq_sponge, xor_comm);
474        }
475
476        if let Some(rot_comm) = rot_comm {
477            absorb_commitment(&mut fq_sponge, rot_comm);
478        }
479
480        // Lookup index; optional
481
482        if let Some(LookupVerifierIndex {
483            joint_lookup_used: _,
484            lookup_info: _,
485            lookup_table,
486            table_ids,
487            runtime_tables_selector,
488
489            lookup_selectors:
490                LookupSelectors {
491                    xor,
492                    lookup,
493                    range_check,
494                    ffmul,
495                },
496        }) = lookup_index
497        {
498            for entry in lookup_table {
499                absorb_commitment(&mut fq_sponge, entry);
500            }
501            if let Some(table_ids) = table_ids {
502                absorb_commitment(&mut fq_sponge, table_ids);
503            }
504            if let Some(runtime_tables_selector) = runtime_tables_selector {
505                absorb_commitment(&mut fq_sponge, runtime_tables_selector);
506            }
507
508            if let Some(xor) = xor {
509                absorb_commitment(&mut fq_sponge, xor);
510            }
511            if let Some(lookup) = lookup {
512                absorb_commitment(&mut fq_sponge, lookup);
513            }
514            if let Some(range_check) = range_check {
515                absorb_commitment(&mut fq_sponge, range_check);
516            }
517            if let Some(ffmul) = ffmul {
518                absorb_commitment(&mut fq_sponge, ffmul);
519            }
520        }
521        fq_sponge.digest_fq()
522    }
523}
kimchi/verifier_index.rs

kimchi/
verifier_index.rs
