snark_verifier/pcs/kzg/
accumulation.rs

Help
1use crate::{
2    loader::{native::NativeLoader, LoadedScalar, Loader},
3    pcs::{kzg::KzgAccumulator, AccumulationScheme, AccumulationSchemeProver},
4    util::{
5        arithmetic::{Curve, CurveAffine, Field, MultiMillerLoop},
6        msm::Msm,
7        transcript::{TranscriptRead, TranscriptWrite},
8    },
9    Error,
10};
11use rand::Rng;
12use std::{fmt::Debug, marker::PhantomData};
13
14/// KZG accumulation scheme. The second generic `MOS` stands for different kind
15/// of multi-open scheme.
16#[derive(Clone, Debug)]
17pub struct KzgAs<M, MOS>(PhantomData<(M, MOS)>);
18
19impl<M, L, MOS> AccumulationScheme<M::G1Affine, L> for KzgAs<M, MOS>
20where
21    M: MultiMillerLoop,
22    M::G1Affine: CurveAffine<ScalarExt = M::Fr, CurveExt = M::G1>,
23    L: Loader<M::G1Affine>,
24    MOS: Clone + Debug,
25{
26    type Accumulator = KzgAccumulator<M::G1Affine, L>;
27    type VerifyingKey = KzgAsVerifyingKey;
28    type Proof = KzgAsProof<M::G1Affine, L>;
29
30    fn read_proof<T>(
31        vk: &Self::VerifyingKey,
32        instances: &[Self::Accumulator],
33        transcript: &mut T,
34    ) -> Result<Self::Proof, Error>
35    where
36        T: TranscriptRead<M::G1Affine, L>,
37    {
38        KzgAsProof::read(vk, instances, transcript)
39    }
40
41    fn verify(
42        _: &Self::VerifyingKey,
43        instances: &[Self::Accumulator],
44        proof: &Self::Proof,
45    ) -> Result<Self::Accumulator, Error> {
46        let (lhs, rhs) = instances
47            .iter()
48            .map(|accumulator| (&accumulator.lhs, &accumulator.rhs))
49            .chain(proof.blind.as_ref().map(|(lhs, rhs)| (lhs, rhs)))
50            .unzip::<_, _, Vec<_>, Vec<_>>();
51
52        let powers_of_r = proof.r.powers(lhs.len());
53        let [lhs, rhs] = [lhs, rhs].map(|bases| {
54            bases
55                .into_iter()
56                .zip(powers_of_r.iter())
57                .map(|(base, r)| Msm::<M::G1Affine, L>::base(base) * r)
58                .sum::<Msm<_, _>>()
59                .evaluate(None)
60        });
61
62        Ok(KzgAccumulator::new(lhs, rhs))
63    }
64}
65
66/// KZG accumulation scheme proving key.
67#[derive(Clone, Copy, Debug, Default)]
68pub struct KzgAsProvingKey<C>(pub Option<(C, C)>);
69
70impl<C: Clone> KzgAsProvingKey<C> {
71    /// Initialize a [`KzgAsProvingKey`].
72    pub fn new(g: Option<(C, C)>) -> Self {
73        Self(g)
74    }
75
76    /// Returns if it supports zero-knowledge or not.
77    pub fn zk(&self) -> bool {
78        self.0.is_some()
79    }
80
81    /// Returns [`KzgAsVerifyingKey`].
82    pub fn vk(&self) -> KzgAsVerifyingKey {
83        KzgAsVerifyingKey(self.zk())
84    }
85}
86
87/// KZG accumulation scheme verifying key.
88#[derive(Clone, Copy, Debug, Default)]
89pub struct KzgAsVerifyingKey(bool);
90
91impl KzgAsVerifyingKey {
92    /// Returns if it supports zero-knowledge or not.
93    pub fn zk(&self) -> bool {
94        self.0
95    }
96}
97
98/// KZG accumulation scheme proof.
99#[derive(Clone, Debug)]
100pub struct KzgAsProof<C, L>
101where
102    C: CurveAffine,
103    L: Loader<C>,
104{
105    blind: Option<(L::LoadedEcPoint, L::LoadedEcPoint)>,
106    r: L::LoadedScalar,
107}
108
109impl<C, L> KzgAsProof<C, L>
110where
111    C: CurveAffine,
112    L: Loader<C>,
113{
114    fn read<T>(
115        vk: &KzgAsVerifyingKey,
116        instances: &[KzgAccumulator<C, L>],
117        transcript: &mut T,
118    ) -> Result<Self, Error>
119    where
120        T: TranscriptRead<C, L>,
121    {
122        assert!(!instances.is_empty());
123
124        for accumulator in instances {
125            transcript.common_ec_point(&accumulator.lhs)?;
126            transcript.common_ec_point(&accumulator.rhs)?;
127        }
128
129        let blind = vk
130            .zk()
131            .then(|| Ok((transcript.read_ec_point()?, transcript.read_ec_point()?)))
132            .transpose()?;
133
134        let r = transcript.squeeze_challenge();
135
136        Ok(Self { blind, r })
137    }
138}
139
140impl<M, MOS> AccumulationSchemeProver<M::G1Affine> for KzgAs<M, MOS>
141where
142    M: MultiMillerLoop,
143    M::G1Affine: CurveAffine<ScalarExt = M::Fr, CurveExt = M::G1>,
144    MOS: Clone + Debug,
145{
146    type ProvingKey = KzgAsProvingKey<M::G1Affine>;
147
148    fn create_proof<T, R>(
149        pk: &Self::ProvingKey,
150        instances: &[KzgAccumulator<M::G1Affine, NativeLoader>],
151        transcript: &mut T,
152        rng: R,
153    ) -> Result<KzgAccumulator<M::G1Affine, NativeLoader>, Error>
154    where
155        T: TranscriptWrite<M::G1Affine>,
156        R: Rng,
157    {
158        assert!(!instances.is_empty());
159
160        for accumulator in instances {
161            transcript.common_ec_point(&accumulator.lhs)?;
162            transcript.common_ec_point(&accumulator.rhs)?;
163        }
164
165        let blind = pk
166            .zk()
167            .then(|| {
168                let s = M::Fr::random(rng);
169                let (g, s_g) = pk.0.unwrap();
170                let lhs = (s_g * s).to_affine();
171                let rhs = (g * s).to_affine();
172                transcript.write_ec_point(lhs)?;
173                transcript.write_ec_point(rhs)?;
174                Ok((lhs, rhs))
175            })
176            .transpose()?;
177
178        let r = transcript.squeeze_challenge();
179
180        let (lhs, rhs) = instances
181            .iter()
182            .cloned()
183            .map(|accumulator| (accumulator.lhs, accumulator.rhs))
184            .chain(blind)
185            .unzip::<_, _, Vec<_>, Vec<_>>();
186
187        let powers_of_r = r.powers(lhs.len());
188        let [lhs, rhs] = [lhs, rhs].map(|msms| {
189            msms.iter()
190                .zip(powers_of_r.iter())
191                .map(|(msm, power_of_r)| Msm::<M::G1Affine, NativeLoader>::base(msm) * power_of_r)
192                .sum::<Msm<_, _>>()
193                .evaluate(None)
194        });
195
196        Ok(KzgAccumulator::new(lhs, rhs))
197    }
198}
snark_verifier/pcs/kzg/accumulation.rs

snark_verifier/pcs/kzg/
accumulation.rs
