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

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

use super::{construct_intermediate_sets, ChallengeU, ChallengeV};
use crate::arithmetic::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, MSMKZG};
use crate::poly::kzg::strategy::GuardKZG;
use crate::poly::query::Query;
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;

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

impl<'params, E> Verifier<'params, KZGCommitmentScheme<E>> for VerifierGWC<E>
where
    E: MultiMillerLoop + Debug,
    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,
        }
    }

    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 v: ChallengeV<_> = transcript.squeeze_challenge_scalar();

        let commitment_data = construct_intermediate_sets(queries);

        let w: Vec<E::G1Affine> = (0..commitment_data.len())
            .map(|_| transcript.read_point().map_err(|_| Error::SamplingError))
            .collect::<Result<Vec<E::G1Affine>, Error>>()?;

        let u: ChallengeU<_> = transcript.squeeze_challenge_scalar();

        let mut commitment_multi = MSMKZG::<E>::new();
        let mut eval_multi = E::Fr::ZERO;

        let mut witness = MSMKZG::<E>::new();
        let mut witness_with_aux = MSMKZG::<E>::new();

        for ((commitment_at_a_point, wi), power_of_u) in
            commitment_data.iter().zip(w.into_iter()).zip(powers(*u))
        {
            assert!(!commitment_at_a_point.queries.is_empty());
            let z = commitment_at_a_point.point;

            let (mut commitment_batch, eval_batch) = commitment_at_a_point
                .queries
                .iter()
                .zip(powers(*v))
                .map(|(query, power_of_v)| {
                    assert_eq!(query.get_point(), z);

                    let commitment = match query.get_commitment() {
                        CommitmentReference::Commitment(c) => {
                            let mut msm = MSMKZG::<E>::new();
                            msm.append_term(power_of_v, (*c).into());
                            msm
                        }
                        CommitmentReference::MSM(msm) => {
                            let mut msm = msm.clone();
                            msm.scale(power_of_v);
                            msm
                        }
                    };
                    let eval = power_of_v * query.get_eval();

                    (commitment, eval)
                })
                .reduce(|(mut commitment_acc, eval_acc), (commitment, eval)| {
                    commitment_acc.add_msm(&commitment);
                    (commitment_acc, eval_acc + eval)
                })
                .unwrap();

            commitment_batch.scale(power_of_u);
            commitment_multi.add_msm(&commitment_batch);
            eval_multi += power_of_u * eval_batch;

            witness_with_aux.append_term(power_of_u * z, wi.into());
            witness.append_term(power_of_u, wi.into());
        }

        msm_accumulator.left.add_msm(&witness);

        msm_accumulator.right.add_msm(&witness_with_aux);
        msm_accumulator.right.add_msm(&commitment_multi);
        let g0: E::G1 = <E::G1Affine as PrimeCurveAffine>::generator().into();
        msm_accumulator.right.append_term(eval_multi, -g0);

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