snark_verifier/verifier/
plonk.rs

1//! Verifiers for [PLONK], currently there are [`PlonkSuccinctVerifier`] and
2//! [`PlonkVerifier`] implemented and both are implemented assuming the used
3//! [`PolynomialCommitmentScheme`] has [atomic] or [split] accumulation scheme
4//! ([`PlonkVerifier`] is just [`PlonkSuccinctVerifier`] plus doing accumulator
5//! deciding then returns accept/reject as ouput).
6//!
7//! [PLONK]: https://eprint.iacr.org/2019/953
8//! [atomic]: https://eprint.iacr.org/2020/499
9//! [split]: https://eprint.iacr.org/2020/1618
10
11use crate::{
12    cost::{Cost, CostEstimation},
13    loader::Loader,
14    pcs::{
15        AccumulationDecider, AccumulationScheme, AccumulatorEncoding, PolynomialCommitmentScheme,
16        Query,
17    },
18    util::{
19        arithmetic::{CurveAffine, Rotation},
20        transcript::TranscriptRead,
21    },
22    verifier::{plonk::protocol::CommonPolynomialEvaluation, SnarkVerifier},
23    Error,
24};
25use std::{iter, marker::PhantomData};
26
27mod proof;
28pub(crate) mod protocol;
29
30pub use proof::PlonkProof;
31pub use protocol::PlonkProtocol;
32
33/// Verifier that verifies the cheap part of PLONK and ouput the accumulator.
34#[derive(Debug)]
35pub struct PlonkSuccinctVerifier<AS, AE = PhantomData<AS>>(PhantomData<(AS, AE)>);
36
37impl<C, L, AS, AE> SnarkVerifier<C, L> for PlonkSuccinctVerifier<AS, AE>
38where
39    C: CurveAffine,
40    L: Loader<C>,
41    AS: AccumulationScheme<C, L> + PolynomialCommitmentScheme<C, L, Output = AS::Accumulator>,
42    AE: AccumulatorEncoding<C, L, Accumulator = AS::Accumulator>,
43{
44    type VerifyingKey = <AS as PolynomialCommitmentScheme<C, L>>::VerifyingKey;
45    type Protocol = PlonkProtocol<C, L>;
46    type Proof = PlonkProof<C, L, AS>;
47    type Output = Vec<AE::Accumulator>;
48
49    fn read_proof<T>(
50        svk: &Self::VerifyingKey,
51        protocol: &Self::Protocol,
52        instances: &[Vec<L::LoadedScalar>],
53        transcript: &mut T,
54    ) -> Result<Self::Proof, Error>
55    where
56        T: TranscriptRead<C, L>,
57    {
58        PlonkProof::read::<T, AE>(svk, protocol, instances, transcript)
59    }
60
61    fn verify(
62        svk: &Self::VerifyingKey,
63        protocol: &Self::Protocol,
64        instances: &[Vec<L::LoadedScalar>],
65        proof: &Self::Proof,
66    ) -> Result<Self::Output, Error> {
67        let common_poly_eval = {
68            let mut common_poly_eval = CommonPolynomialEvaluation::new(
69                &protocol.domain,
70                protocol.langranges(),
71                &proof.z,
72                &protocol.domain_as_witness,
73            );
74
75            L::batch_invert(common_poly_eval.denoms());
76            common_poly_eval.evaluate();
77
78            common_poly_eval
79        };
80
81        let mut evaluations = proof.evaluations(protocol, instances, &common_poly_eval)?;
82        let commitments = proof.commitments(protocol, &common_poly_eval, &mut evaluations)?;
83        let queries = proof.queries(protocol, evaluations);
84
85        let accumulator = <AS as PolynomialCommitmentScheme<C, L>>::verify(
86            svk,
87            &commitments,
88            &proof.z,
89            &queries,
90            &proof.pcs,
91        )?;
92
93        let accumulators = iter::empty()
94            .chain(Some(accumulator))
95            .chain(proof.old_accumulators.iter().cloned())
96            .collect();
97
98        Ok(accumulators)
99    }
100}
101
102/// Verifier that first verifies the cheap part of PLONK, then decides
103/// accumulator and returns accept/reject as ouput.
104#[derive(Debug)]
105pub struct PlonkVerifier<AS, AE = PhantomData<AS>>(PhantomData<(AS, AE)>);
106
107impl<C, L, AS, AE> SnarkVerifier<C, L> for PlonkVerifier<AS, AE>
108where
109    C: CurveAffine,
110    L: Loader<C>,
111    AS: AccumulationDecider<C, L> + PolynomialCommitmentScheme<C, L, Output = AS::Accumulator>,
112    AS::DecidingKey: AsRef<<AS as PolynomialCommitmentScheme<C, L>>::VerifyingKey>,
113    AE: AccumulatorEncoding<C, L, Accumulator = AS::Accumulator>,
114{
115    type VerifyingKey = AS::DecidingKey;
116    type Protocol = PlonkProtocol<C, L>;
117    type Proof = PlonkProof<C, L, AS>;
118    type Output = ();
119
120    fn read_proof<T>(
121        vk: &Self::VerifyingKey,
122        protocol: &Self::Protocol,
123        instances: &[Vec<L::LoadedScalar>],
124        transcript: &mut T,
125    ) -> Result<Self::Proof, Error>
126    where
127        T: TranscriptRead<C, L>,
128    {
129        PlonkProof::read::<T, AE>(vk.as_ref(), protocol, instances, transcript)
130    }
131
132    fn verify(
133        vk: &Self::VerifyingKey,
134        protocol: &Self::Protocol,
135        instances: &[Vec<L::LoadedScalar>],
136        proof: &Self::Proof,
137    ) -> Result<Self::Output, Error> {
138        let accumulators =
139            PlonkSuccinctVerifier::<AS, AE>::verify(vk.as_ref(), protocol, instances, proof)?;
140        AS::decide_all(vk, accumulators)
141    }
142}
143
144impl<C, L, AS, AE> CostEstimation<(C, L)> for PlonkSuccinctVerifier<AS, AE>
145where
146    C: CurveAffine,
147    L: Loader<C>,
148    AS: AccumulationScheme<C, L>
149        + PolynomialCommitmentScheme<C, L, Output = AS::Accumulator>
150        + CostEstimation<C, Input = Vec<Query<Rotation>>>,
151{
152    type Input = PlonkProtocol<C, L>;
153
154    fn estimate_cost(protocol: &PlonkProtocol<C, L>) -> Cost {
155        let plonk_cost = {
156            let num_accumulator = protocol.accumulator_indices.len();
157            let num_instance = protocol.num_instance.iter().sum();
158            let num_commitment =
159                protocol.num_witness.iter().sum::<usize>() + protocol.quotient.num_chunk();
160            let num_evaluation = protocol.evaluations.len();
161            let num_msm = protocol.preprocessed.len() + num_commitment + 1 + 2 * num_accumulator;
162            Cost { num_instance, num_commitment, num_evaluation, num_msm, ..Default::default() }
163        };
164        let pcs_cost = {
165            let queries = PlonkProof::<C, L, AS>::empty_queries(protocol);
166            AS::estimate_cost(&queries)
167        };
168        plonk_cost + pcs_cost
169    }
170}
171
172impl<C, L, AS, AE> CostEstimation<(C, L)> for PlonkVerifier<AS, AE>
173where
174    C: CurveAffine,
175    L: Loader<C>,
176    AS: AccumulationScheme<C, L>
177        + PolynomialCommitmentScheme<C, L, Output = AS::Accumulator>
178        + CostEstimation<C, Input = Vec<Query<Rotation>>>,
179{
180    type Input = PlonkProtocol<C, L>;
181
182    fn estimate_cost(protocol: &PlonkProtocol<C, L>) -> Cost {
183        PlonkSuccinctVerifier::<AS, AE>::estimate_cost(protocol)
184            + Cost { num_pairing: 2, ..Default::default() }
185    }
186}