snark_verifier/
pcs.rs

1//! Verifiers for polynomial commitment schemes.
2
3use crate::{
4    loader::{native::NativeLoader, Loader},
5    util::{
6        arithmetic::{CurveAffine, Rotation},
7        msm::Msm,
8        transcript::{TranscriptRead, TranscriptWrite},
9    },
10    Error,
11};
12use rand::Rng;
13use std::{fmt::Debug, marker::PhantomData};
14
15pub mod ipa;
16pub mod kzg;
17
18/// Query to an oracle.
19/// It assumes all queries are based on the same point, but with some `shift`.
20#[derive(Clone, Debug)]
21pub struct Query<S, T = ()> {
22    /// Index of polynomial to query
23    pub poly: usize,
24    /// Shift of the query point.
25    pub shift: S,
26    /// Shift loaded as either constant or witness. It is user's job to ensure this is correctly constrained to have value equal to `shift`
27    pub loaded_shift: T,
28    /// Evaluation read from transcript.
29    pub eval: T,
30}
31
32impl<S> Query<S> {
33    /// Initialize [`Query`] without evaluation.
34    pub fn new(poly: usize, shift: S) -> Self {
35        Self { poly, shift, loaded_shift: (), eval: () }
36    }
37
38    /// Returns [`Query`] with evaluation and optionally the shift are loaded as.
39    pub fn with_evaluation<T>(self, loaded_shift: T, eval: T) -> Query<S, T> {
40        Query { poly: self.poly, shift: self.shift, loaded_shift, eval }
41    }
42}
43
44/// Polynomial commitment scheme verifier.
45pub trait PolynomialCommitmentScheme<C, L>: Clone + Debug
46where
47    C: CurveAffine,
48    L: Loader<C>,
49{
50    /// Verifying key.
51    type VerifyingKey: Clone + Debug;
52    /// Structured proof read from transcript.
53    type Proof: Clone + Debug;
54    /// Output of verification.
55    type Output: Clone + Debug;
56
57    /// Read [`PolynomialCommitmentScheme::Proof`] from transcript.
58    fn read_proof<T>(
59        vk: &Self::VerifyingKey,
60        queries: &[Query<Rotation>],
61        transcript: &mut T,
62    ) -> Result<Self::Proof, Error>
63    where
64        T: TranscriptRead<C, L>;
65
66    /// Verify [`PolynomialCommitmentScheme::Proof`] and output [`PolynomialCommitmentScheme::Output`].
67    fn verify(
68        vk: &Self::VerifyingKey,
69        commitments: &[Msm<C, L>],
70        point: &L::LoadedScalar,
71        queries: &[Query<Rotation, L::LoadedScalar>],
72        proof: &Self::Proof,
73    ) -> Result<Self::Output, Error>;
74}
75
76/// Accumulation scheme verifier.
77pub trait AccumulationScheme<C, L>
78where
79    C: CurveAffine,
80    L: Loader<C>,
81{
82    /// Accumulator to be accumulated.
83    type Accumulator: Clone + Debug;
84    /// Verifying key.
85    type VerifyingKey: Clone + Debug;
86    /// Structured proof read from transcript.
87    type Proof: Clone + Debug;
88
89    /// Read a [`AccumulationScheme::Proof`] from transcript.
90    fn read_proof<T>(
91        vk: &Self::VerifyingKey,
92        instances: &[Self::Accumulator],
93        transcript: &mut T,
94    ) -> Result<Self::Proof, Error>
95    where
96        T: TranscriptRead<C, L>;
97
98    /// Verify old [`AccumulationScheme::Accumulator`]s are accumulated properly
99    /// into a new one with the [`AccumulationScheme::Proof`], and returns the
100    /// new one as output.
101    fn verify(
102        vk: &Self::VerifyingKey,
103        instances: &[Self::Accumulator],
104        proof: &Self::Proof,
105    ) -> Result<Self::Accumulator, Error>;
106}
107
108/// Accumulation scheme decider.
109/// When accumulation is going to end, the decider will perform the check if the
110/// final accumulator is valid or not, where the check is usually much more
111/// expensive than accumulation verification.
112pub trait AccumulationDecider<C, L>: AccumulationScheme<C, L>
113where
114    C: CurveAffine,
115    L: Loader<C>,
116{
117    /// Deciding key. The key for decider for perform the final accumulator
118    /// check.
119    type DecidingKey: Clone + Debug;
120
121    /// Decide if a [`AccumulationScheme::Accumulator`] is valid.
122    fn decide(dk: &Self::DecidingKey, accumulator: Self::Accumulator) -> Result<(), Error>;
123
124    /// Decide if all [`AccumulationScheme::Accumulator`]s are valid.
125    fn decide_all(
126        dk: &Self::DecidingKey,
127        accumulators: Vec<Self::Accumulator>,
128    ) -> Result<(), Error>;
129}
130
131/// Accumulation scheme prover.
132pub trait AccumulationSchemeProver<C>: AccumulationScheme<C, NativeLoader>
133where
134    C: CurveAffine,
135{
136    /// Proving key.
137    type ProvingKey: Clone + Debug;
138
139    /// Create a proof that argues if old [`AccumulationScheme::Accumulator`]s
140    /// are properly accumulated into the new one, and returns the new one as
141    /// output.
142    fn create_proof<T, R>(
143        pk: &Self::ProvingKey,
144        instances: &[Self::Accumulator],
145        transcript: &mut T,
146        rng: R,
147    ) -> Result<Self::Accumulator, Error>
148    where
149        T: TranscriptWrite<C>,
150        R: Rng;
151}
152
153/// Accumulator encoding.
154pub trait AccumulatorEncoding<C, L>: Clone + Debug
155where
156    C: CurveAffine,
157    L: Loader<C>,
158{
159    /// Accumulator to be encoded.
160    type Accumulator: Clone + Debug;
161
162    /// Decode an [`AccumulatorEncoding::Accumulator`] from serveral
163    /// [`crate::loader::ScalarLoader::LoadedScalar`]s.
164    fn from_repr(repr: &[&L::LoadedScalar]) -> Result<Self::Accumulator, Error>;
165}
166
167impl<C, L, PCS> AccumulatorEncoding<C, L> for PhantomData<PCS>
168where
169    C: CurveAffine,
170    L: Loader<C>,
171    PCS: PolynomialCommitmentScheme<C, L>,
172{
173    type Accumulator = PCS::Output;
174
175    fn from_repr(_: &[&L::LoadedScalar]) -> Result<Self::Accumulator, Error> {
176        unimplemented!()
177    }
178}
snark_verifier/pcs.rs

snark_verifier/
pcs.rs
