snark_verifier/pcs/
ipa.rs

Help
1//! Inner product argument polynomial commitment scheme and accumulation scheme.
2//! The notations are following <https://eprint.iacr.org/2020/499.pdf>.
3
4use crate::{
5    loader::{native::NativeLoader, LoadedScalar, Loader, ScalarLoader},
6    util::{
7        arithmetic::{
8            inner_product, powers, Curve, CurveAffine, Domain, Field, Fraction, PrimeField,
9        },
10        msm::{multi_scalar_multiplication, Msm},
11        parallelize,
12        poly::Polynomial,
13        transcript::{TranscriptRead, TranscriptWrite},
14        Itertools,
15    },
16    Error,
17};
18use rand::Rng;
19use std::{fmt::Debug, iter, marker::PhantomData};
20
21mod accumulation;
22mod accumulator;
23mod decider;
24mod multiopen;
25
26pub use accumulation::{IpaAs, IpaAsProof};
27pub use accumulator::IpaAccumulator;
28pub use decider::IpaDecidingKey;
29pub use multiopen::{Bgh19, Bgh19Proof};
30
31/// Inner product argument polynomial commitment scheme.
32#[derive(Clone, Debug)]
33pub struct Ipa<C>(PhantomData<C>);
34
35impl<C> Ipa<C>
36where
37    C: CurveAffine,
38{
39    /// Create an inner product argument.
40    pub fn create_proof<T, R>(
41        pk: &IpaProvingKey<C>,
42        p: &[C::Scalar],
43        z: &C::Scalar,
44        omega: Option<&C::Scalar>,
45        transcript: &mut T,
46        mut rng: R,
47    ) -> Result<IpaAccumulator<C, NativeLoader>, Error>
48    where
49        T: TranscriptWrite<C>,
50        R: Rng,
51    {
52        let mut p_prime = Polynomial::new(p.to_vec());
53        if pk.zk() {
54            let p_bar = {
55                let mut p_bar = Polynomial::rand(p.len(), &mut rng);
56                let p_bar_at_z = p_bar.evaluate(*z);
57                p_bar[0] -= p_bar_at_z;
58                p_bar
59            };
60            let omega_bar = C::Scalar::random(&mut rng);
61            let c_bar = pk.commit(&p_bar, Some(omega_bar));
62            transcript.write_ec_point(c_bar)?;
63
64            let alpha = transcript.squeeze_challenge();
65            let omega_prime = *omega.unwrap() + alpha * omega_bar;
66            transcript.write_scalar(omega_prime)?;
67
68            p_prime = p_prime + &(p_bar * alpha);
69        };
70
71        let xi_0 = transcript.squeeze_challenge();
72        let h_prime = pk.h * xi_0;
73        let mut bases = pk.g.clone();
74        let mut coeffs = p_prime.to_vec();
75        let mut zs = powers(*z).take(coeffs.len()).collect_vec();
76
77        let k = pk.domain.k;
78        let mut xi = Vec::with_capacity(k);
79        for i in 0..k {
80            let half = 1 << (k - i - 1);
81
82            let l_i = multi_scalar_multiplication(&coeffs[half..], &bases[..half])
83                + h_prime * inner_product(&coeffs[half..], &zs[..half]);
84            let r_i = multi_scalar_multiplication(&coeffs[..half], &bases[half..])
85                + h_prime * inner_product(&coeffs[..half], &zs[half..]);
86            transcript.write_ec_point(l_i.to_affine())?;
87            transcript.write_ec_point(r_i.to_affine())?;
88
89            let xi_i = transcript.squeeze_challenge();
90            let xi_i_inv = Field::invert(&xi_i).unwrap();
91
92            let (bases_l, bases_r) = bases.split_at_mut(half);
93            let (coeffs_l, coeffs_r) = coeffs.split_at_mut(half);
94            let (zs_l, zs_r) = zs.split_at_mut(half);
95            parallelize(bases_l, |(bases_l, start)| {
96                let mut tmp = Vec::with_capacity(bases_l.len());
97                for (lhs, rhs) in bases_l.iter().zip(bases_r[start..].iter()) {
98                    tmp.push(lhs.to_curve() + *rhs * xi_i);
99                }
100                C::Curve::batch_normalize(&tmp, bases_l);
101            });
102            parallelize(coeffs_l, |(coeffs_l, start)| {
103                for (lhs, rhs) in coeffs_l.iter_mut().zip(coeffs_r[start..].iter()) {
104                    *lhs += xi_i_inv * rhs;
105                }
106            });
107            parallelize(zs_l, |(zs_l, start)| {
108                for (lhs, rhs) in zs_l.iter_mut().zip(zs_r[start..].iter()) {
109                    *lhs += xi_i * rhs;
110                }
111            });
112            bases = bases_l.to_vec();
113            coeffs = coeffs_l.to_vec();
114            zs = zs_l.to_vec();
115
116            xi.push(xi_i);
117        }
118
119        transcript.write_ec_point(bases[0])?;
120        transcript.write_scalar(coeffs[0])?;
121
122        Ok(IpaAccumulator::new(xi, bases[0]))
123    }
124
125    /// Read [`IpaProof`] from transcript.
126    pub fn read_proof<T, L: Loader<C>>(
127        svk: &IpaSuccinctVerifyingKey<C>,
128        transcript: &mut T,
129    ) -> Result<IpaProof<C, L>, Error>
130    where
131        T: TranscriptRead<C, L>,
132    {
133        IpaProof::read(svk, transcript)
134    }
135
136    /// Perform the succinct check of the proof and returns [`IpaAccumulator`].
137    pub fn succinct_verify<L: Loader<C>>(
138        svk: &IpaSuccinctVerifyingKey<C>,
139        commitment: &Msm<C, L>,
140        z: &L::LoadedScalar,
141        eval: &L::LoadedScalar,
142        proof: &IpaProof<C, L>,
143    ) -> Result<IpaAccumulator<C, L>, Error> {
144        let loader = z.loader();
145        let h = loader.ec_point_load_const(&svk.h);
146        let s = svk.s.as_ref().map(|s| loader.ec_point_load_const(s));
147        let h = Msm::<C, L>::base(&h);
148
149        let h_prime = h * &proof.xi_0;
150        let lhs = {
151            let c_prime = match (s.as_ref(), proof.c_bar_alpha.as_ref(), proof.omega_prime.as_ref())
152            {
153                (Some(s), Some((c_bar, alpha)), Some(omega_prime)) => {
154                    let s = Msm::<C, L>::base(s);
155                    commitment.clone() + Msm::base(c_bar) * alpha - s * omega_prime
156                }
157                (None, None, None) => commitment.clone(),
158                _ => unreachable!(),
159            };
160            let c_0 = c_prime + h_prime.clone() * eval;
161            let c_k = c_0
162                + proof
163                    .rounds
164                    .iter()
165                    .zip(proof.xi_inv().iter())
166                    .flat_map(|(Round { l, r, xi }, xi_inv)| [(l, xi_inv), (r, xi)])
167                    .map(|(base, scalar)| Msm::<C, L>::base(base) * scalar)
168                    .sum::<Msm<_, _>>();
169            c_k.evaluate(None)
170        };
171        let rhs = {
172            let u = Msm::<C, L>::base(&proof.u);
173            let v_prime = h_eval(&proof.xi(), z) * &proof.c;
174            (u * &proof.c + h_prime * &v_prime).evaluate(None)
175        };
176
177        loader.ec_point_assert_eq("C_k == c[U] + v'[H']", &lhs, &rhs);
178
179        Ok(IpaAccumulator::new(proof.xi(), proof.u.clone()))
180    }
181}
182
183/// Inner product argument proving key.
184#[derive(Clone, Debug)]
185pub struct IpaProvingKey<C: CurveAffine> {
186    /// Working domain.
187    pub domain: Domain<C::Scalar>,
188    /// $\mathbb{G}$
189    pub g: Vec<C>,
190    /// $H$
191    pub h: C,
192    /// $S$
193    pub s: Option<C>,
194}
195
196impl<C: CurveAffine> IpaProvingKey<C> {
197    /// Initialize an [`IpaProvingKey`].
198    pub fn new(domain: Domain<C::Scalar>, g: Vec<C>, h: C, s: Option<C>) -> Self {
199        Self { domain, g, h, s }
200    }
201
202    /// Returns if it supports zero-knowledge.
203    pub fn zk(&self) -> bool {
204        self.s.is_some()
205    }
206
207    /// Returns [`IpaSuccinctVerifyingKey`].
208    pub fn svk(&self) -> IpaSuccinctVerifyingKey<C> {
209        IpaSuccinctVerifyingKey::new(self.domain.clone(), self.g[0], self.h, self.s)
210    }
211
212    /// Returns [`IpaDecidingKey`].
213    pub fn dk(&self) -> IpaDecidingKey<C> {
214        IpaDecidingKey::new(self.svk(), self.g.clone())
215    }
216
217    /// Commit a polynomial into with a randomizer if any.
218    pub fn commit(&self, poly: &Polynomial<C::Scalar>, omega: Option<C::Scalar>) -> C {
219        let mut c = multi_scalar_multiplication(&poly[..], &self.g);
220        match (self.s, omega) {
221            (Some(s), Some(omega)) => c += s * omega,
222            (None, None) => {}
223            _ => unreachable!(),
224        };
225        c.to_affine()
226    }
227}
228
229impl<C: CurveAffine> IpaProvingKey<C> {
230    #[cfg(test)]
231    pub(crate) fn rand<R: Rng>(k: usize, zk: bool, mut rng: R) -> Self {
232        use crate::util::arithmetic::{root_of_unity, Group};
233
234        let domain = Domain::new(k, root_of_unity(k));
235        let mut g = vec![C::default(); 1 << k];
236        C::Curve::batch_normalize(
237            &iter::repeat_with(|| C::Curve::random(&mut rng)).take(1 << k).collect_vec(),
238            &mut g,
239        );
240        let h = C::Curve::random(&mut rng).to_affine();
241        let s = zk.then(|| C::Curve::random(&mut rng).to_affine());
242        Self { domain, g, h, s }
243    }
244}
245
246/// Inner product argument succinct verifying key.
247#[derive(Clone, Debug)]
248pub struct IpaSuccinctVerifyingKey<C: CurveAffine> {
249    /// Working domain.
250    pub domain: Domain<C::Scalar>,
251    /// $G_0$
252    pub g: C,
253    /// $H$
254    pub h: C,
255    /// $S$
256    pub s: Option<C>,
257}
258
259impl<C: CurveAffine> IpaSuccinctVerifyingKey<C> {
260    /// Initialize an [`IpaSuccinctVerifyingKey`].
261    pub fn new(domain: Domain<C::Scalar>, g: C, h: C, s: Option<C>) -> Self {
262        Self { domain, g, h, s }
263    }
264
265    /// Returns if it supports zero-knowledge.
266    pub fn zk(&self) -> bool {
267        self.s.is_some()
268    }
269}
270
271/// Inner product argument
272#[derive(Clone, Debug)]
273pub struct IpaProof<C, L>
274where
275    C: CurveAffine,
276    L: Loader<C>,
277{
278    c_bar_alpha: Option<(L::LoadedEcPoint, L::LoadedScalar)>,
279    omega_prime: Option<L::LoadedScalar>,
280    xi_0: L::LoadedScalar,
281    rounds: Vec<Round<C, L>>,
282    u: L::LoadedEcPoint,
283    c: L::LoadedScalar,
284}
285
286impl<C, L> IpaProof<C, L>
287where
288    C: CurveAffine,
289    L: Loader<C>,
290{
291    fn new(
292        c_bar_alpha: Option<(L::LoadedEcPoint, L::LoadedScalar)>,
293        omega_prime: Option<L::LoadedScalar>,
294        xi_0: L::LoadedScalar,
295        rounds: Vec<Round<C, L>>,
296        u: L::LoadedEcPoint,
297        c: L::LoadedScalar,
298    ) -> Self {
299        Self { c_bar_alpha, omega_prime, xi_0, rounds, u, c }
300    }
301
302    /// Read [`crate::pcs::AccumulationScheme::Proof`] from transcript.
303    pub fn read<T>(svk: &IpaSuccinctVerifyingKey<C>, transcript: &mut T) -> Result<Self, Error>
304    where
305        T: TranscriptRead<C, L>,
306    {
307        let c_bar_alpha = svk
308            .zk()
309            .then(|| {
310                let c_bar = transcript.read_ec_point()?;
311                let alpha = transcript.squeeze_challenge();
312                Ok((c_bar, alpha))
313            })
314            .transpose()?;
315        let omega_prime = svk.zk().then(|| transcript.read_scalar()).transpose()?;
316        let xi_0 = transcript.squeeze_challenge();
317        let rounds = iter::repeat_with(|| {
318            Ok(Round::new(
319                transcript.read_ec_point()?,
320                transcript.read_ec_point()?,
321                transcript.squeeze_challenge(),
322            ))
323        })
324        .take(svk.domain.k)
325        .collect::<Result<Vec<_>, _>>()?;
326        let u = transcript.read_ec_point()?;
327        let c = transcript.read_scalar()?;
328        Ok(Self { c_bar_alpha, omega_prime, xi_0, rounds, u, c })
329    }
330
331    /// Returns $\{\xi_0, \xi_1, ...\}$.
332    pub fn xi(&self) -> Vec<L::LoadedScalar> {
333        self.rounds.iter().map(|round| round.xi.clone()).collect()
334    }
335
336    /// Returns $\{\xi_0^{-1}, \xi_1^{-1}, ...\}$.
337    pub fn xi_inv(&self) -> Vec<L::LoadedScalar> {
338        let mut xi_inv = self.xi().into_iter().map(Fraction::one_over).collect_vec();
339        L::batch_invert(xi_inv.iter_mut().filter_map(Fraction::denom_mut));
340        xi_inv.iter_mut().for_each(Fraction::evaluate);
341        xi_inv.into_iter().map(|xi_inv| xi_inv.evaluated().clone()).collect()
342    }
343}
344
345#[derive(Clone, Debug)]
346struct Round<C, L>
347where
348    C: CurveAffine,
349    L: Loader<C>,
350{
351    l: L::LoadedEcPoint,
352    r: L::LoadedEcPoint,
353    xi: L::LoadedScalar,
354}
355
356impl<C, L> Round<C, L>
357where
358    C: CurveAffine,
359    L: Loader<C>,
360{
361    fn new(l: L::LoadedEcPoint, r: L::LoadedEcPoint, xi: L::LoadedScalar) -> Self {
362        Self { l, r, xi }
363    }
364}
365
366fn h_eval<F: PrimeField, T: LoadedScalar<F>>(xi: &[T], z: &T) -> T {
367    let loader = z.loader();
368    let one = loader.load_one();
369    loader.product(
370        &iter::successors(Some(z.clone()), |z| Some(z.square()))
371            .zip(xi.iter().rev())
372            .map(|(z, xi)| z * xi + &one)
373            .collect_vec()
374            .iter()
375            .collect_vec(),
376    )
377}
378
379fn h_coeffs<F: Field>(xi: &[F], scalar: F) -> Vec<F> {
380    assert!(!xi.is_empty());
381
382    let mut coeffs = vec![F::ZERO; 1 << xi.len()];
383    coeffs[0] = scalar;
384
385    for (len, xi) in xi.iter().rev().enumerate().map(|(i, xi)| (1 << i, xi)) {
386        let (left, right) = coeffs.split_at_mut(len);
387        let right = &mut right[0..len];
388        right.copy_from_slice(left);
389        for coeffs in right {
390            *coeffs *= xi;
391        }
392    }
393
394    coeffs
395}
396
397// #[cfg(test)]
398// mod test {
399//     use crate::{
400//         pcs::{
401//             ipa::{self, IpaProvingKey},
402//             AccumulationDecider,
403//         },
404//         util::{arithmetic::Field, msm::Msm, poly::Polynomial},
405//     };
406//     use halo2_curves::pasta::pallas;
407//     use halo2_proofs::transcript::{
408//         Blake2bRead, Blake2bWrite, TranscriptReadBuffer, TranscriptWriterBuffer,
409//     };
410//     use rand::rngs::OsRng;
411
412//     #[test]
413//     fn test_ipa() {
414//         type Ipa = ipa::Ipa<pallas::Affine>;
415//         type IpaAs = ipa::IpaAs<pallas::Affine, ()>;
416
417//         let k = 10;
418//         let mut rng = OsRng;
419
420//         for zk in [false, true] {
421//             let pk = IpaProvingKey::<pallas::Affine>::rand(k, zk, &mut rng);
422//             let (c, z, v, proof) = {
423//                 let p = Polynomial::<pallas::Scalar>::rand(pk.domain.n, &mut rng);
424//                 let omega = pk.zk().then(|| pallas::Scalar::random(&mut rng));
425//                 let c = pk.commit(&p, omega);
426//                 let z = pallas::Scalar::random(&mut rng);
427//                 let v = p.evaluate(z);
428//                 let mut transcript = Blake2bWrite::init(Vec::new());
429//                 Ipa::create_proof(&pk, &p[..], &z, omega.as_ref(), &mut transcript, &mut rng)
430//                     .unwrap();
431//                 (c, z, v, transcript.finalize())
432//             };
433
434//             let svk = pk.svk();
435//             let accumulator = {
436//                 let mut transcript = Blake2bRead::init(proof.as_slice());
437//                 let proof = Ipa::read_proof(&svk, &mut transcript).unwrap();
438//                 Ipa::succinct_verify(&svk, &Msm::base(&c), &z, &v, &proof).unwrap()
439//             };
440
441//             let dk = pk.dk();
442//             assert!(IpaAs::decide(&dk, accumulator).is_ok());
443//         }
444//     }
445// }
snark_verifier/pcs/ipa.rs

snark_verifier/pcs/
ipa.rs
