halo2_axiom/poly/kzg/multiopen/shplonk/
verifier.rs

Help
1use std::fmt::Debug;
2use std::hash::Hash;
3
4use super::ChallengeY;
5use super::{construct_intermediate_sets, ChallengeU, ChallengeV};
6use crate::arithmetic::{
7    eval_polynomial, evaluate_vanishing_polynomial, lagrange_interpolate, powers,
8};
9use crate::helpers::SerdeCurveAffine;
10use crate::poly::commitment::Verifier;
11use crate::poly::commitment::MSM;
12use crate::poly::kzg::commitment::{KZGCommitmentScheme, ParamsKZG};
13use crate::poly::kzg::msm::DualMSM;
14use crate::poly::kzg::msm::{PreMSM, MSMKZG};
15use crate::poly::kzg::strategy::GuardKZG;
16use crate::poly::query::{CommitmentReference, VerifierQuery};
17use crate::poly::Error;
18use crate::transcript::{EncodedChallenge, TranscriptRead};
19use ff::Field;
20use pairing::{Engine, MultiMillerLoop};
21use std::ops::MulAssign;
22
23/// Concrete KZG multiopen verifier with SHPLONK variant
24#[derive(Debug)]
25pub struct VerifierSHPLONK<'params, E: Engine> {
26    params: &'params ParamsKZG<E>,
27}
28
29impl<'params, E> Verifier<'params, KZGCommitmentScheme<E>> for VerifierSHPLONK<'params, E>
30where
31    E: MultiMillerLoop + Debug,
32    E::G1Affine: SerdeCurveAffine<ScalarExt = E::Fr, CurveExt = E::G1>,
33    E::G2Affine: SerdeCurveAffine,
34    E::Fr: Hash,
35{
36    type Guard = GuardKZG<'params, E>;
37    type MSMAccumulator = DualMSM<'params, E>;
38
39    const QUERY_INSTANCE: bool = false;
40
41    fn new(params: &'params ParamsKZG<E>) -> Self {
42        Self { params }
43    }
44
45    /// Verify a multi-opening proof
46    fn verify_proof<
47        'com,
48        Ch: EncodedChallenge<E::G1Affine>,
49        T: TranscriptRead<E::G1Affine, Ch>,
50        I,
51    >(
52        &self,
53        transcript: &mut T,
54        queries: I,
55        mut msm_accumulator: DualMSM<'params, E>,
56    ) -> Result<Self::Guard, Error>
57    where
58        I: IntoIterator<Item = VerifierQuery<'com, E::G1Affine, MSMKZG<E>>> + Clone,
59    {
60        let intermediate_sets = construct_intermediate_sets(queries);
61        let (rotation_sets, super_point_set) = (
62            intermediate_sets.rotation_sets,
63            intermediate_sets.super_point_set,
64        );
65
66        let y: ChallengeY<_> = transcript.squeeze_challenge_scalar();
67        let v: ChallengeV<_> = transcript.squeeze_challenge_scalar();
68
69        let h1 = transcript.read_point().map_err(|_| Error::SamplingError)?;
70        let u: ChallengeU<_> = transcript.squeeze_challenge_scalar();
71        let h2 = transcript.read_point().map_err(|_| Error::SamplingError)?;
72
73        let (mut z_0_diff_inverse, mut z_0) = (E::Fr::ZERO, E::Fr::ZERO);
74        let (mut outer_msm, mut r_outer_acc) = (PreMSM::<E>::new(), E::Fr::ZERO);
75        for (i, (rotation_set, power_of_v)) in rotation_sets.iter().zip(powers(*v)).enumerate() {
76            let diffs: Vec<E::Fr> = super_point_set
77                .iter()
78                .filter(|point| !rotation_set.points.contains(point))
79                .copied()
80                .collect();
81            let mut z_diff_i = evaluate_vanishing_polynomial(&diffs[..], *u);
82
83            // normalize coefficients by the coefficient of the first commitment
84            if i == 0 {
85                z_0 = evaluate_vanishing_polynomial(&rotation_set.points[..], *u);
86                z_0_diff_inverse = z_diff_i.invert().unwrap();
87                z_diff_i = E::Fr::ONE;
88            } else {
89                z_diff_i.mul_assign(z_0_diff_inverse);
90            }
91
92            let (mut inner_msm, r_inner_acc) = rotation_set
93                .commitments
94                .iter()
95                .zip(powers(*y))
96                .map(|(commitment_data, power_of_y)| {
97                    // calculate low degree equivalent
98                    let r_x = lagrange_interpolate(
99                        &rotation_set.points[..],
100                        &commitment_data.evals()[..],
101                    );
102                    let r_eval = power_of_y * eval_polynomial(&r_x[..], *u);
103                    let msm = match commitment_data.get() {
104                        CommitmentReference::Commitment(c) => {
105                            let mut msm = MSMKZG::<E>::new();
106                            msm.append_term(power_of_y, (*c).into());
107                            msm
108                        }
109                        CommitmentReference::MSM(msm) => {
110                            let mut msm = msm.clone();
111                            msm.scale(power_of_y);
112                            msm
113                        }
114                    };
115                    (msm, r_eval)
116                })
117                .reduce(|(mut msm_acc, r_eval_acc), (msm, r_eval)| {
118                    msm_acc.add_msm(&msm);
119                    (msm_acc, r_eval_acc + r_eval)
120                })
121                .unwrap();
122
123            inner_msm.scale(power_of_v * z_diff_i);
124            outer_msm.add_msm(inner_msm);
125            r_outer_acc += power_of_v * r_inner_acc * z_diff_i;
126        }
127        let mut outer_msm = outer_msm.normalize();
128        let g1: E::G1 = self.params.g[0].into();
129        outer_msm.append_term(-r_outer_acc, g1);
130        outer_msm.append_term(-z_0, h1.into());
131        outer_msm.append_term(*u, h2.into());
132
133        msm_accumulator.left.append_term(E::Fr::ONE, h2.into());
134
135        msm_accumulator.right.add_msm(&outer_msm);
136
137        Ok(Self::Guard::new(msm_accumulator))
138    }
139}
halo2_axiom/poly/kzg/multiopen/shplonk/verifier.rs

halo2_axiom/poly/kzg/multiopen/shplonk/
verifier.rs
