snark_verifier/pcs/kzg/multiopen/
gwc19.rs

Help
1use crate::{
2    cost::{Cost, CostEstimation},
3    loader::{LoadedScalar, Loader},
4    pcs::{
5        kzg::{KzgAccumulator, KzgAs, KzgSuccinctVerifyingKey},
6        PolynomialCommitmentScheme, Query,
7    },
8    util::{
9        arithmetic::{CurveAffine, MultiMillerLoop, Rotation},
10        msm::Msm,
11        transcript::TranscriptRead,
12        Itertools,
13    },
14    Error,
15};
16
17/// Verifier of multi-open KZG. It is for the GWC implementation
18/// in [`halo2_proofs`](crate::halo2_proofs).
19/// Notations are following <https://eprint.iacr.org/2019/953.pdf>.
20#[derive(Clone, Debug)]
21pub struct Gwc19;
22
23impl<M, L> PolynomialCommitmentScheme<M::G1Affine, L> for KzgAs<M, Gwc19>
24where
25    M: MultiMillerLoop,
26    M::G1Affine: CurveAffine<ScalarExt = M::Fr, CurveExt = M::G1>,
27    L: Loader<M::G1Affine>,
28{
29    type VerifyingKey = KzgSuccinctVerifyingKey<M::G1Affine>;
30    type Proof = Gwc19Proof<M::G1Affine, L>;
31    type Output = KzgAccumulator<M::G1Affine, L>;
32
33    fn read_proof<T>(
34        _: &Self::VerifyingKey,
35        queries: &[Query<Rotation>],
36        transcript: &mut T,
37    ) -> Result<Self::Proof, Error>
38    where
39        T: TranscriptRead<M::G1Affine, L>,
40    {
41        Gwc19Proof::read(queries, transcript)
42    }
43
44    fn verify(
45        svk: &Self::VerifyingKey,
46        commitments: &[Msm<M::G1Affine, L>],
47        z: &L::LoadedScalar,
48        queries: &[Query<Rotation, L::LoadedScalar>],
49        proof: &Self::Proof,
50    ) -> Result<Self::Output, Error> {
51        let sets = query_sets(queries);
52        let powers_of_u = &proof.u.powers(sets.len());
53        let f = {
54            let powers_of_v = proof.v.powers(sets.iter().map(|set| set.polys.len()).max().unwrap());
55            sets.iter()
56                .map(|set| set.msm(commitments, &powers_of_v))
57                .zip(powers_of_u.iter())
58                .map(|(msm, power_of_u)| msm * power_of_u)
59                .sum::<Msm<_, _>>()
60        };
61        let z_omegas = sets.iter().map(|set| {
62            let loaded_shift = set.loaded_shift.clone();
63            loaded_shift * z
64        });
65
66        let rhs = proof
67            .ws
68            .iter()
69            .zip(powers_of_u.iter())
70            .map(|(w, power_of_u)| Msm::base(w) * power_of_u)
71            .collect_vec();
72        let lhs = f + rhs.iter().zip(z_omegas).map(|(uw, z_omega)| uw.clone() * &z_omega).sum();
73
74        Ok(KzgAccumulator::new(
75            lhs.evaluate(Some(svk.g)),
76            rhs.into_iter().sum::<Msm<_, _>>().evaluate(Some(svk.g)),
77        ))
78    }
79}
80
81/// Structured proof of [`Gwc19`].
82#[derive(Clone, Debug)]
83pub struct Gwc19Proof<C, L>
84where
85    C: CurveAffine,
86    L: Loader<C>,
87{
88    v: L::LoadedScalar,
89    ws: Vec<L::LoadedEcPoint>,
90    u: L::LoadedScalar,
91}
92
93impl<C, L> Gwc19Proof<C, L>
94where
95    C: CurveAffine,
96    L: Loader<C>,
97{
98    fn read<T>(queries: &[Query<Rotation>], transcript: &mut T) -> Result<Self, Error>
99    where
100        T: TranscriptRead<C, L>,
101    {
102        let v = transcript.squeeze_challenge();
103        let ws = transcript.read_n_ec_points(query_sets(queries).len())?;
104        let u = transcript.squeeze_challenge();
105        Ok(Gwc19Proof { v, ws, u })
106    }
107}
108
109struct QuerySet<'a, S, T> {
110    shift: S,
111    loaded_shift: T,
112    polys: Vec<usize>,
113    evals: Vec<&'a T>,
114}
115
116impl<'a, S, T> QuerySet<'a, S, T>
117where
118    T: Clone,
119{
120    fn msm<C: CurveAffine, L: Loader<C, LoadedScalar = T>>(
121        &self,
122        commitments: &[Msm<'a, C, L>],
123        powers_of_v: &[L::LoadedScalar],
124    ) -> Msm<C, L>
125    where
126        T: LoadedScalar<C::Scalar>,
127    {
128        self.polys
129            .iter()
130            .zip(self.evals.iter().cloned())
131            .map(|(poly, eval)| {
132                let commitment = commitments[*poly].clone();
133                commitment - Msm::constant(eval.clone())
134            })
135            .zip(powers_of_v.iter())
136            .map(|(msm, power_of_v)| msm * power_of_v)
137            .sum()
138    }
139}
140
141fn query_sets<S, T>(queries: &[Query<S, T>]) -> Vec<QuerySet<S, T>>
142where
143    S: PartialEq + Copy,
144    T: Clone + PartialEq,
145{
146    queries.iter().fold(Vec::new(), |mut sets, query| {
147        if let Some(pos) = sets.iter().position(|set| set.shift == query.shift) {
148            sets[pos].polys.push(query.poly);
149            sets[pos].evals.push(&query.eval);
150        } else {
151            sets.push(QuerySet {
152                shift: query.shift,
153                loaded_shift: query.loaded_shift.clone(),
154                polys: vec![query.poly],
155                evals: vec![&query.eval],
156            });
157        }
158        sets
159    })
160}
161
162impl<M> CostEstimation<M::G1Affine> for KzgAs<M, Gwc19>
163where
164    M: MultiMillerLoop,
165{
166    type Input = Vec<Query<Rotation>>;
167
168    fn estimate_cost(queries: &Vec<Query<Rotation>>) -> Cost {
169        let num_w = query_sets(queries).len();
170        Cost { num_commitment: num_w, num_msm: num_w, ..Default::default() }
171    }
172}
snark_verifier/pcs/kzg/multiopen/gwc19.rs

snark_verifier/pcs/kzg/multiopen/
gwc19.rs
