1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142

use std::fmt::Debug;
use std::marker::PhantomData;

use super::ChallengeY;
use super::{construct_intermediate_sets, ChallengeU, ChallengeV};
use crate::arithmetic::{
    eval_polynomial, evaluate_vanishing_polynomial, lagrange_interpolate, powers,
};
use crate::helpers::SerdeCurveAffine;
use crate::poly::commitment::Verifier;
use crate::poly::commitment::MSM;
use crate::poly::kzg::commitment::KZGCommitmentScheme;
use crate::poly::kzg::msm::DualMSM;
use crate::poly::kzg::msm::{PreMSM, MSMKZG};
use crate::poly::kzg::strategy::GuardKZG;
use crate::poly::query::{CommitmentReference, VerifierQuery};
use crate::poly::Error;
use crate::transcript::{EncodedChallenge, TranscriptRead};
use group::prime::PrimeCurveAffine;
use halo2_middleware::ff::Field;
use halo2curves::pairing::{Engine, MultiMillerLoop};
use halo2curves::CurveExt;
use std::ops::MulAssign;

/// Concrete KZG multiopen verifier with SHPLONK variant
#[derive(Debug)]
pub struct VerifierSHPLONK<E: Engine> {
    _marker: PhantomData<E>,
}

impl<'params, E> Verifier<'params, KZGCommitmentScheme<E>> for VerifierSHPLONK<E>
where
    E: MultiMillerLoop + Debug,
    E::Fr: Ord,
    E::G1Affine: SerdeCurveAffine<ScalarExt = <E as Engine>::Fr, CurveExt = <E as Engine>::G1>,
    E::G1: CurveExt<AffineExt = E::G1Affine>,
    E::G2Affine: SerdeCurveAffine,
{
    type Guard = GuardKZG<E>;
    type MSMAccumulator = DualMSM<E>;

    fn new() -> Self {
        Self {
            _marker: PhantomData,
        }
    }

    /// Verify a multi-opening proof
    fn verify_proof<
        'com,
        Ch: EncodedChallenge<E::G1Affine>,
        T: TranscriptRead<E::G1Affine, Ch>,
        I,
    >(
        &self,
        transcript: &mut T,
        queries: I,
        mut msm_accumulator: DualMSM<E>,
    ) -> Result<Self::Guard, Error>
    where
        I: IntoIterator<Item = VerifierQuery<'com, E::G1Affine, MSMKZG<E>>> + Clone,
    {
        let intermediate_sets = construct_intermediate_sets(queries);
        let (rotation_sets, super_point_set) = (
            intermediate_sets.rotation_sets,
            intermediate_sets.super_point_set,
        );

        let y: ChallengeY<_> = transcript.squeeze_challenge_scalar();
        let v: ChallengeV<_> = transcript.squeeze_challenge_scalar();

        let h1 = transcript.read_point().map_err(|_| Error::SamplingError)?;
        let u: ChallengeU<_> = transcript.squeeze_challenge_scalar();
        let h2 = transcript.read_point().map_err(|_| Error::SamplingError)?;

        let (mut z_0_diff_inverse, mut z_0) = (E::Fr::ZERO, E::Fr::ZERO);
        let (mut outer_msm, mut r_outer_acc) = (PreMSM::<E>::default(), E::Fr::ZERO);
        for (i, (rotation_set, power_of_v)) in rotation_sets.iter().zip(powers(*v)).enumerate() {
            let diffs: Vec<E::Fr> = super_point_set
                .iter()
                .filter(|point| !rotation_set.points.contains(point))
                .copied()
                .collect();
            let mut z_diff_i = evaluate_vanishing_polynomial(&diffs[..], *u);

            // normalize coefficients by the coefficient of the first commitment
            if i == 0 {
                z_0 = evaluate_vanishing_polynomial(&rotation_set.points[..], *u);
                z_0_diff_inverse = z_diff_i.invert().unwrap();
                z_diff_i = E::Fr::ONE;
            } else {
                z_diff_i.mul_assign(z_0_diff_inverse);
            }

            let (mut inner_msm, r_inner_acc) = rotation_set
                .commitments
                .iter()
                .zip(powers(*y))
                .map(|(commitment_data, power_of_y)| {
                    // calculate low degree equivalent
                    let r_x = lagrange_interpolate(
                        &rotation_set.points[..],
                        &commitment_data.evals()[..],
                    );
                    let r_eval = power_of_y * eval_polynomial(&r_x[..], *u);
                    let msm = match commitment_data.get() {
                        CommitmentReference::Commitment(c) => {
                            let mut msm = MSMKZG::<E>::new();
                            msm.append_term(power_of_y, (*c).into());
                            msm
                        }
                        CommitmentReference::MSM(msm) => {
                            let mut msm = msm.clone();
                            msm.scale(power_of_y);
                            msm
                        }
                    };
                    (msm, r_eval)
                })
                .reduce(|(mut msm_acc, r_eval_acc), (msm, r_eval)| {
                    msm_acc.add_msm(&msm);
                    (msm_acc, r_eval_acc + r_eval)
                })
                .unwrap();

            inner_msm.scale(power_of_v * z_diff_i);
            outer_msm.add_msm(inner_msm);
            r_outer_acc += power_of_v * r_inner_acc * z_diff_i;
        }
        let mut outer_msm = outer_msm.normalize();
        let g1: E::G1 = <E::G1Affine as PrimeCurveAffine>::generator().into();
        outer_msm.append_term(-r_outer_acc, g1);
        outer_msm.append_term(-z_0, h1.into());
        outer_msm.append_term(*u, h2.into());

        msm_accumulator.left.append_term(E::Fr::ONE, h2.into());

        msm_accumulator.right.add_msm(&outer_msm);

        Ok(Self::Guard::new(msm_accumulator))
    }
}