fullcodec_plonk/proof_system/
prover.rs

1// This Source Code Form is subject to the terms of the Mozilla Public
2// License, v. 2.0. If a copy of the MPL was not distributed with this
3// file, You can obtain one at http://mozilla.org/MPL/2.0/.
4//
5// Copyright (c) DUSK NETWORK. All rights reserved.
6
7use crate::{
8    commitment_scheme::CommitKey,
9    constraint_system::{TurboComposer, Witness},
10    error::Error,
11    fft::{EvaluationDomain, Polynomial},
12    plonkup::MultiSet,
13    proof_system::{
14        linearisation_poly, proof::Proof, quotient_poly, ProverKey,
15    },
16    transcript::TranscriptProtocol,
17};
18use dusk_bls12_381::BlsScalar;
19use merlin::Transcript;
20use sp_std::vec;
21use sp_std::vec::Vec;
22
23/// Abstraction structure designed to construct a circuit and generate
24/// [`Proof`]s for it.
25#[allow(missing_debug_implementations)]
26pub struct Prover {
27    /// ProverKey which is used to create proofs about a specific PLONK circuit
28    pub prover_key: Option<ProverKey>,
29
30    pub(crate) cs: TurboComposer,
31    /// Store the messages exchanged during the preprocessing stage
32    /// This is copied each time, we make a proof
33    pub preprocessed_transcript: Transcript,
34}
35
36impl Prover {
37    /// Mutable borrow of [`TurboComposer`].
38    pub fn composer_mut(&mut self) -> &mut TurboComposer {
39        &mut self.cs
40    }
41
42    /// Preprocesses the underlying constraint system.
43    pub fn preprocess(&mut self, commit_key: &CommitKey) -> Result<(), Error> {
44        if self.prover_key.is_some() {
45            return Err(Error::CircuitAlreadyPreprocessed);
46        }
47        let pk = self
48            .cs
49            .preprocess_prover(commit_key, &mut self.preprocessed_transcript)?;
50        self.prover_key = Some(pk);
51        Ok(())
52    }
53}
54
55impl Default for Prover {
56    fn default() -> Prover {
57        Prover::new(b"plonk")
58    }
59}
60
61impl Prover {
62    /// Creates a new `Prover` instance.
63    pub fn new(label: &'static [u8]) -> Prover {
64        Prover {
65            prover_key: None,
66            cs: TurboComposer::new(),
67            preprocessed_transcript: Transcript::new(label),
68        }
69    }
70
71    /// Creates a new `Prover` object with some expected size.
72    pub fn with_size(label: &'static [u8], size: usize) -> Prover {
73        Prover {
74            prover_key: None,
75            cs: TurboComposer::with_size(size),
76            preprocessed_transcript: Transcript::new(label),
77        }
78    }
79
80    /// Returns the number of gates in the circuit thet the `Prover` actually
81    /// stores inside.
82    pub const fn gates(&self) -> u32 {
83        self.cs.gates()
84    }
85
86    /// Split `t(X)` poly into 4 degree `n` polynomials.
87    pub(crate) fn split_tx_poly(
88        &self,
89        n: usize,
90        t_x: &Polynomial,
91    ) -> (Polynomial, Polynomial, Polynomial, Polynomial) {
92        (
93            Polynomial::from_coefficients_vec(t_x[0..n].to_vec()),
94            Polynomial::from_coefficients_vec(t_x[n..2 * n].to_vec()),
95            Polynomial::from_coefficients_vec(t_x[2 * n..3 * n].to_vec()),
96            Polynomial::from_coefficients_vec(t_x[3 * n..].to_vec()),
97        )
98    }
99
100    /// Computes the quotient Opening [`Polynomial`].
101    fn compute_quotient_opening_poly(
102        n: usize,
103        t_1_poly: &Polynomial,
104        t_2_poly: &Polynomial,
105        t_3_poly: &Polynomial,
106        t_4_poly: &Polynomial,
107        z_challenge: &BlsScalar,
108    ) -> Polynomial {
109        // Compute z^n , z^2n , z^3n
110        let z_n = z_challenge.pow(&[n as u64, 0, 0, 0]);
111        let z_two_n = z_challenge.pow(&[2 * n as u64, 0, 0, 0]);
112        let z_three_n = z_challenge.pow(&[3 * n as u64, 0, 0, 0]);
113
114        let a = t_1_poly;
115        let b = t_2_poly * &z_n;
116        let c = t_3_poly * &z_two_n;
117        let d = t_4_poly * &z_three_n;
118        let abc = &(a + &b) + &c;
119        &abc + &d
120    }
121
122    /// Convert witnesses to their actual witness values.
123    pub(crate) fn to_scalars(&self, vars: &[Witness]) -> Vec<BlsScalar> {
124        vars.iter().map(|var| self.cs.witnesses[var]).collect()
125    }
126
127    /// Resets the witnesses in the prover object.
128    /// This function is used when the user wants to make multiple proofs with
129    /// the same circuit.
130    pub fn clear_witness(&mut self) {
131        self.cs = TurboComposer::new();
132    }
133
134    /// Clears all data in the `Prover` instance.
135    /// This function is used when the user wants to use the same `Prover` to
136    /// make a [`Proof`] regarding a different circuit.
137    pub fn clear(&mut self) {
138        self.clear_witness();
139        self.prover_key = None;
140        self.preprocessed_transcript = Transcript::new(b"plonk");
141    }
142
143    /// Keys the [`Transcript`] with additional seed information
144    /// Wrapper around [`Transcript::append_message`].
145    pub fn key_transcript(&mut self, label: &'static [u8], message: &[u8]) {
146        self.preprocessed_transcript.append_message(label, message);
147    }
148
149    /// Creates a [`Proof]` that demonstrates that a circuit is satisfied.
150    /// # Note
151    /// If you intend to construct multiple [`Proof`]s with different witnesses,
152    /// after calling this method, the user should then call
153    /// [`Prover::clear_witness`].
154    /// This is automatically done when [`Prover::prove`] is called.
155    pub fn prove_with_preprocessed(
156        &self,
157        commit_key: &CommitKey,
158        prover_key: &ProverKey,
159    ) -> Result<Proof, Error> {
160        // make sure the domain is big enough to handle the circuit as well as
161        // the lookup table
162        let domain = EvaluationDomain::new(core::cmp::max(
163            self.cs.gates() as usize,
164            self.cs.lookup_table.0.len(),
165        ))?;
166
167        // Since the caller is passing a pre-processed circuit
168        // We assume that the Transcript has been seeded with the preprocessed
169        // Commitments
170        let mut transcript = self.preprocessed_transcript.clone();
171
172        // 1. Compute witness Polynomials
173        //
174        // Convert Witness to BlsScalars padding them to the
175        // correct domain size.
176        let pad = vec![BlsScalar::zero(); domain.size() - self.cs.w_l.len()];
177        let w_l_scalar = &[&self.to_scalars(&self.cs.w_l)[..], &pad].concat();
178        let w_r_scalar = &[&self.to_scalars(&self.cs.w_r)[..], &pad].concat();
179        let w_o_scalar = &[&self.to_scalars(&self.cs.w_o)[..], &pad].concat();
180        let w_4_scalar = &[&self.to_scalars(&self.cs.w_4)[..], &pad].concat();
181
182        // make sure q_lookup is also the right size for constructing f
183        let padded_q_lookup = [&self.cs.q_lookup[..], &pad].concat();
184
185        // Witnesses are now in evaluation form, convert them to coefficients
186        // So that we may commit to them
187        let w_l_poly =
188            Polynomial::from_coefficients_vec(domain.ifft(w_l_scalar));
189        let w_r_poly =
190            Polynomial::from_coefficients_vec(domain.ifft(w_r_scalar));
191        let w_o_poly =
192            Polynomial::from_coefficients_vec(domain.ifft(w_o_scalar));
193        let w_4_poly =
194            Polynomial::from_coefficients_vec(domain.ifft(w_4_scalar));
195
196        // Commit to witness polynomials
197        let w_l_poly_commit = commit_key.commit(&w_l_poly)?;
198        let w_r_poly_commit = commit_key.commit(&w_r_poly)?;
199        let w_o_poly_commit = commit_key.commit(&w_o_poly)?;
200        let w_4_poly_commit = commit_key.commit(&w_4_poly)?;
201
202        // Add witness polynomial commitments to transcript
203        transcript.append_commitment(b"w_l", &w_l_poly_commit);
204        transcript.append_commitment(b"w_r", &w_r_poly_commit);
205        transcript.append_commitment(b"w_o", &w_o_poly_commit);
206        transcript.append_commitment(b"w_4", &w_4_poly_commit);
207
208        // Generate table compression factor
209        let zeta = transcript.challenge_scalar(b"zeta");
210
211        // Compress table into vector of single elements
212        let compressed_t_multiset = MultiSet::compress_four_arity(
213            [
214                &prover_key.lookup.table_1.0,
215                &prover_key.lookup.table_2.0,
216                &prover_key.lookup.table_3.0,
217                &prover_key.lookup.table_4.0,
218            ],
219            zeta,
220        );
221
222        // Compute table poly
223        let table_poly = Polynomial::from_coefficients_vec(
224            domain.ifft(&compressed_t_multiset.0),
225        );
226
227        // Compute table f
228        // When q_lookup[i] is zero the wire value is replaced with a dummy
229        // value Currently set as the first row of the public table
230        // If q_lookup is one the wire values are preserved
231        let f_1_scalar = w_l_scalar
232            .iter()
233            .zip(&padded_q_lookup)
234            .map(|(w, s)| {
235                w * s + (BlsScalar::one() - s) * compressed_t_multiset.0[0]
236            })
237            .collect::<Vec<BlsScalar>>();
238        let f_2_scalar = w_r_scalar
239            .iter()
240            .zip(&padded_q_lookup)
241            .map(|(w, s)| w * s)
242            .collect::<Vec<BlsScalar>>();
243        let f_3_scalar = w_o_scalar
244            .iter()
245            .zip(&padded_q_lookup)
246            .map(|(w, s)| w * s)
247            .collect::<Vec<BlsScalar>>();
248        let f_4_scalar = w_4_scalar
249            .iter()
250            .zip(&padded_q_lookup)
251            .map(|(w, s)| w * s)
252            .collect::<Vec<BlsScalar>>();
253
254        // Compress all wires into a single vector
255        let compressed_f_multiset = MultiSet::compress_four_arity(
256            [
257                &MultiSet::from(&f_1_scalar[..]),
258                &MultiSet::from(&f_2_scalar[..]),
259                &MultiSet::from(&f_3_scalar[..]),
260                &MultiSet::from(&f_4_scalar[..]),
261            ],
262            zeta,
263        );
264
265        // Compute long query poly
266        let f_poly = Polynomial::from_coefficients_vec(
267            domain.ifft(&compressed_f_multiset.0),
268        );
269
270        // Commit to query polynomial
271        let f_poly_commit = commit_key.commit(&f_poly)?;
272
273        // Add f_poly commitment to transcript
274        transcript.append_commitment(b"f", &f_poly_commit);
275
276        // 2. Compute permutation polynomial
277        //
278        //
279        // Compute permutation challenges; `beta`, `gamma`, `delta` and
280        // `epsilon`.
281        let beta = transcript.challenge_scalar(b"beta");
282        transcript.append_scalar(b"beta", &beta);
283        let gamma = transcript.challenge_scalar(b"gamma");
284        let delta = transcript.challenge_scalar(b"delta");
285        let epsilon = transcript.challenge_scalar(b"epsilon");
286
287        let z_poly = Polynomial::from_coefficients_slice(
288            &self.cs.perm.compute_permutation_poly(
289                &domain,
290                [w_l_scalar, w_r_scalar, w_o_scalar, w_4_scalar],
291                &beta,
292                &gamma,
293                [
294                    &prover_key.permutation.left_sigma.0,
295                    &prover_key.permutation.right_sigma.0,
296                    &prover_key.permutation.out_sigma.0,
297                    &prover_key.permutation.fourth_sigma.0,
298                ],
299            ),
300        );
301
302        // Commit to permutation polynomial
303        //
304        let z_poly_commit = commit_key.commit(&z_poly)?;
305
306        // Add commitment to permutation polynomial to transcript
307        transcript.append_commitment(b"z", &z_poly_commit);
308
309        // 3. Compute public inputs polynomial
310        let pi_poly = Polynomial::from_coefficients_vec(
311            domain.ifft(&self.cs.to_dense_public_inputs()),
312        );
313
314        // Compute evaluation challenge; `z`
315        let z_challenge = transcript.challenge_scalar(b"z_challenge");
316
317        // Compute s, as the sorted and concatenated version of f and t
318        let s = compressed_t_multiset
319            .sorted_concat(&compressed_f_multiset)
320            .unwrap();
321
322        // Compute first and second halves of s, as h_1 and h_2
323        let (h_1, h_2) = s.halve_alternating();
324
325        // Compute h polys
326        let h_1_poly = Polynomial::from_coefficients_vec(domain.ifft(&h_1.0));
327        let h_2_poly = Polynomial::from_coefficients_vec(domain.ifft(&h_2.0));
328
329        // Commit to h polys
330        let h_1_poly_commit = commit_key.commit(&h_1_poly).unwrap();
331        let h_2_poly_commit = commit_key.commit(&h_2_poly).unwrap();
332
333        // Add h polynomials to transcript
334        transcript.append_commitment(b"h1", &h_1_poly_commit);
335        transcript.append_commitment(b"h2", &h_2_poly_commit);
336
337        // Compute lookup permutation poly
338        let p_poly = Polynomial::from_coefficients_slice(
339            &self.cs.perm.compute_lookup_permutation_poly(
340                &domain,
341                &compressed_f_multiset.0,
342                &compressed_t_multiset.0,
343                &h_1.0,
344                &h_2.0,
345                &delta,
346                &epsilon,
347            ),
348        );
349
350        // Commit to permutation polynomial
351        //
352        let p_poly_commit = commit_key.commit(&p_poly)?;
353
354        // Add permutation polynomial commitment to transcript
355        transcript.append_commitment(b"p", &p_poly_commit);
356
357        // 4. Compute quotient polynomial
358        //
359        // Compute quotient challenge; `alpha`
360        let alpha = transcript.challenge_scalar(b"alpha");
361        let range_sep_challenge =
362            transcript.challenge_scalar(b"range separation challenge");
363        let logic_sep_challenge =
364            transcript.challenge_scalar(b"logic separation challenge");
365        let fixed_base_sep_challenge =
366            transcript.challenge_scalar(b"fixed base separation challenge");
367        let var_base_sep_challenge =
368            transcript.challenge_scalar(b"variable base separation challenge");
369        let lookup_sep_challenge =
370            transcript.challenge_scalar(b"lookup challenge");
371
372        let t_poly = quotient_poly::compute(
373            &domain,
374            prover_key,
375            &z_poly,
376            &p_poly,
377            (&w_l_poly, &w_r_poly, &w_o_poly, &w_4_poly),
378            &f_poly,
379            &table_poly,
380            &h_1_poly,
381            &h_2_poly,
382            &pi_poly,
383            &(
384                alpha,
385                beta,
386                gamma,
387                delta,
388                epsilon,
389                zeta,
390                range_sep_challenge,
391                logic_sep_challenge,
392                fixed_base_sep_challenge,
393                var_base_sep_challenge,
394                lookup_sep_challenge,
395            ),
396        )?;
397
398        // Split quotient polynomial into 4 degree `n` polynomials
399        let (t_1_poly, t_2_poly, t_3_poly, t_4_poly) =
400            self.split_tx_poly(domain.size(), &t_poly);
401
402        // Commit to splitted quotient polynomial
403        let t_1_commit = commit_key.commit(&t_1_poly)?;
404        let t_2_commit = commit_key.commit(&t_2_poly)?;
405        let t_3_commit = commit_key.commit(&t_3_poly)?;
406        let t_4_commit = commit_key.commit(&t_4_poly)?;
407
408        // Add quotient polynomial commitments to transcript
409        transcript.append_commitment(b"t_1", &t_1_commit);
410        transcript.append_commitment(b"t_2", &t_2_commit);
411        transcript.append_commitment(b"t_3", &t_3_commit);
412        transcript.append_commitment(b"t_4", &t_4_commit);
413
414        // 4. Compute linearisation polynomial
415        //
416
417        let (lin_poly, evaluations) = linearisation_poly::compute(
418            &domain,
419            prover_key,
420            &(
421                alpha,
422                beta,
423                gamma,
424                delta,
425                epsilon,
426                zeta,
427                range_sep_challenge,
428                logic_sep_challenge,
429                fixed_base_sep_challenge,
430                var_base_sep_challenge,
431                lookup_sep_challenge,
432                z_challenge,
433            ),
434            &w_l_poly,
435            &w_r_poly,
436            &w_o_poly,
437            &w_4_poly,
438            &t_poly,
439            &z_poly,
440            &f_poly,
441            &h_1_poly,
442            &h_2_poly,
443            &table_poly,
444            &p_poly,
445        );
446
447        // Add evaluations to transcript
448        transcript.append_scalar(b"a_eval", &evaluations.proof.a_eval);
449        transcript.append_scalar(b"b_eval", &evaluations.proof.b_eval);
450        transcript.append_scalar(b"c_eval", &evaluations.proof.c_eval);
451        transcript.append_scalar(b"d_eval", &evaluations.proof.d_eval);
452        transcript
453            .append_scalar(b"a_next_eval", &evaluations.proof.a_next_eval);
454        transcript
455            .append_scalar(b"b_next_eval", &evaluations.proof.b_next_eval);
456        transcript
457            .append_scalar(b"d_next_eval", &evaluations.proof.d_next_eval);
458        transcript.append_scalar(
459            b"left_sig_eval",
460            &evaluations.proof.left_sigma_eval,
461        );
462        transcript.append_scalar(
463            b"right_sig_eval",
464            &evaluations.proof.right_sigma_eval,
465        );
466        transcript
467            .append_scalar(b"out_sig_eval", &evaluations.proof.out_sigma_eval);
468        transcript
469            .append_scalar(b"q_arith_eval", &evaluations.proof.q_arith_eval);
470        transcript.append_scalar(b"q_c_eval", &evaluations.proof.q_c_eval);
471        transcript.append_scalar(b"q_l_eval", &evaluations.proof.q_l_eval);
472        transcript.append_scalar(b"q_r_eval", &evaluations.proof.q_r_eval);
473        transcript
474            .append_scalar(b"q_lookup_eval", &evaluations.proof.q_lookup_eval);
475        transcript.append_scalar(b"perm_eval", &evaluations.proof.perm_eval);
476        transcript.append_scalar(
477            b"lookup_perm_eval",
478            &evaluations.proof.lookup_perm_eval,
479        );
480        transcript.append_scalar(b"h_1_eval", &evaluations.proof.h_1_eval);
481        transcript
482            .append_scalar(b"h_1_next_eval", &evaluations.proof.h_1_next_eval);
483        transcript.append_scalar(b"h_2_eval", &evaluations.proof.h_2_eval);
484        transcript.append_scalar(b"t_eval", &evaluations.quot_eval);
485        transcript.append_scalar(b"r_eval", &evaluations.proof.lin_poly_eval);
486
487        // 5. Compute Openings using KZG10
488        //
489        // We merge the quotient polynomial using the `z_challenge` so the SRS
490        // is linear in the circuit size `n`
491        let quot = Self::compute_quotient_opening_poly(
492            domain.size(),
493            &t_1_poly,
494            &t_2_poly,
495            &t_3_poly,
496            &t_4_poly,
497            &z_challenge,
498        );
499
500        // Compute aggregate witness to polynomials evaluated at the evaluation
501        // challenge `z`
502        let aggregate_witness = commit_key.compute_aggregate_witness(
503            &[
504                quot,
505                lin_poly,
506                w_l_poly.clone(),
507                w_r_poly.clone(),
508                w_o_poly,
509                w_4_poly.clone(),
510                prover_key.permutation.left_sigma.0.clone(),
511                prover_key.permutation.right_sigma.0.clone(),
512                prover_key.permutation.out_sigma.0.clone(),
513                f_poly,
514                h_1_poly.clone(),
515                h_2_poly,
516                table_poly.clone(),
517            ],
518            &z_challenge,
519            &mut transcript,
520        );
521        let w_z_comm = commit_key.commit(&aggregate_witness)?;
522
523        // Compute aggregate witness to polynomials evaluated at the shifted
524        // evaluation challenge
525        let shifted_aggregate_witness = commit_key.compute_aggregate_witness(
526            &[
527                z_poly, w_l_poly, w_r_poly, w_4_poly, h_1_poly, p_poly,
528                table_poly,
529            ],
530            &(z_challenge * domain.group_gen),
531            &mut transcript,
532        );
533        let w_zx_comm = commit_key.commit(&shifted_aggregate_witness)?;
534
535        // Create Proof
536        Ok(Proof {
537            a_comm: w_l_poly_commit,
538            b_comm: w_r_poly_commit,
539            c_comm: w_o_poly_commit,
540            d_comm: w_4_poly_commit,
541
542            f_comm: f_poly_commit,
543
544            h_1_comm: h_1_poly_commit,
545            h_2_comm: h_2_poly_commit,
546
547            z_comm: z_poly_commit,
548            p_comm: p_poly_commit,
549
550            t_1_comm: t_1_commit,
551            t_2_comm: t_2_commit,
552            t_3_comm: t_3_commit,
553            t_4_comm: t_4_commit,
554
555            w_z_comm,
556            w_zw_comm: w_zx_comm,
557
558            evaluations: evaluations.proof,
559        })
560    }
561
562    /// Proves a circuit is satisfied, then clears the witness variables
563    /// If the circuit is not pre-processed, then the preprocessed circuit will
564    /// also be computed.
565    pub fn prove(&mut self, commit_key: &CommitKey) -> Result<Proof, Error> {
566        let prover_key: &ProverKey;
567
568        if self.prover_key.is_none() {
569            // Preprocess circuit
570            let prover_key = self.cs.preprocess_prover(
571                commit_key,
572                &mut self.preprocessed_transcript,
573            )?;
574            // Store preprocessed circuit and transcript in the Prover
575            self.prover_key = Some(prover_key);
576        }
577
578        prover_key = self.prover_key.as_ref().unwrap();
579
580        let proof = self.prove_with_preprocessed(commit_key, prover_key)?;
581
582        // Clear witness and reset composer variables
583        self.clear_witness();
584
585        Ok(proof)
586    }
587}
fullcodec_plonk/proof_system/prover.rs

fullcodec_plonk/proof_system/
prover.rs
