dock_crypto_utils/
randomized_pairing_check.rs

1use ark_ec::{
2    pairing::{MillerLoopOutput, Pairing, PairingOutput},
3    AffineRepr, Group,
4};
5use ark_ff::{One, PrimeField, Zero};
6use ark_std::{cfg_iter, ops::MulAssign, rand::Rng, vec, vec::Vec, UniformRand};
7
8#[cfg(feature = "parallel")]
9use rayon::prelude::*;
10
11/// Inspired from Snarkpack implementation - <https://github.com/nikkolasg/snarkpack/blob/main/src/pairing_check.rs>
12/// RandomizedPairingChecker represents a check of the form `e(A,B) + e(C,D) + ... = T`. Checks can
13/// be aggregated together using random linear combination. The efficiency comes
14/// from keeping the results from the miller loop output before proceeding to a final
15/// exponentiation when verifying if all checks are verified.
16/// For each pairing equation, multiply by a power of a random element created during initialization
17/// eg. to check 3 pairing equations `e(A1, B1) == O1, e(A2, B2) == O2 and e(A3, B3) == O3`, a single
18/// equation can be checked as `e(A1, B1) + e(A2, B2)*r + e(A3, B3)*r^2 == O1 + O2*r + O3*r^2` which is
19/// same as checking `e(A1, B1) + e(A2*r, B2) + e(A3*r^2, B3) == O1 + O2*r + O3*r^2`
20/// Similarly to check 3 pairing equations `e(A1, B1) == e(C1, D1), e(A2, B2) == e(C2, D2) and e(A3, B3) == e(C3, D3)`,
21/// a single check can done as `e(A1, B1) + e(A2, B2)*r + e(A3, B3)*r^2 == e(C1, D1) + e(C2, D2)*r + e(C3, D3)*r^2` which
22/// is same as checking `e(A1, B1) + e(A2*r, B2) + e(A3*r^2, B3) + e(C1*-1, D1) + e(C2*-r, D2) + e(C3*-r^2, D3)== 1`
23#[derive(Debug, Clone)]
24pub struct RandomizedPairingChecker<E: Pairing> {
25    /// a miller loop result that is to be multiplied by other miller loop results
26    /// before going into a final exponentiation result
27    left: MillerLoopOutput<E>,
28    /// a right side result which is already in the right subgroup Gt which is to
29    /// be compared to the left side when "final_exponentiatiat"-ed
30    right: PairingOutput<E>,
31    /// If true, delays the computation of miller loops till the end (unless overridden) trading off
32    /// memory for CPU time.
33    lazy: bool,
34    /// Keeps the pairs of G1, G2 elements that need to be used in miller loops when running lazily
35    pending: (Vec<E::G1Prepared>, Vec<E::G2Prepared>),
36    random: E::ScalarField,
37    /// For each pairing equation, its multiplied by `self.random`
38    current_random: E::ScalarField,
39}
40
41impl<E: Pairing> RandomizedPairingChecker<E> {
42    /// Create a checker using given random number. If `lazy` is set to true, delays the computation
43    /// of miller loops till the end (unless overridden) trading off memory for CPU time.
44    pub fn new(random: E::ScalarField, lazy: bool) -> Self {
45        Self {
46            left: MillerLoopOutput(E::TargetField::one()),
47            right: PairingOutput::zero(),
48            lazy,
49            pending: (vec![], vec![]),
50            random,
51            current_random: E::ScalarField::one(),
52        }
53    }
54
55    /// Same as `Self::new` except that this generates a random value
56    pub fn new_using_rng<R: Rng>(rng: &mut R, lazy: bool) -> Self {
57        Self::new(E::ScalarField::rand(rng), lazy)
58    }
59
60    /// Add single elements from source and target groups
61    pub fn add_sources_and_target(
62        &mut self,
63        a: &E::G1Affine,
64        b: impl Into<E::G2Prepared>,
65        out: &PairingOutput<E>,
66    ) {
67        let m = self.current_random.into_bigint();
68        let a_m = E::G1Prepared::from(a.mul_bigint(m));
69        if self.lazy {
70            self.pending.0.push(a_m);
71            self.pending.1.push(b.into());
72        } else {
73            self.left.0.mul_assign(E::miller_loop(a_m, b.into()).0);
74        }
75        self.right += out.mul_bigint(m);
76        self.current_random *= self.random;
77    }
78
79    /// Add a sequence of group elements whose pairing product must be equal to the given target field
80    /// element, i.e. `\prod_{i}(e(a_i, b_i)) = out`
81    pub fn add_multiple_sources_and_target(
82        &mut self,
83        a: &[E::G1Affine],
84        b: impl IntoIterator<Item = impl Into<E::G2Prepared>>,
85        out: &PairingOutput<E>,
86    ) {
87        self.add_multiple_sources_and_target_with_laziness_choice(a, b, out, self.lazy)
88    }
89
90    /// Add a sequence of group elements whose pairing product must be equal to the another given sequence
91    /// of group elements, i.e. `\prod_{i}(e(a_i, b_i)) = \prod_{i}(e(c_i, d_i))`
92    pub fn add_multiple_sources(
93        &mut self,
94        a: &[E::G1Affine],
95        b: impl IntoIterator<Item = impl Into<E::G2Prepared>>,
96        c: &[E::G1Affine],
97        d: impl IntoIterator<Item = impl Into<E::G2Prepared>>,
98    ) {
99        self.add_multiple_sources_with_laziness_choice(a, b, c, d, self.lazy)
100    }
101
102    /// Add 2 group elements whose pairing should be equal to the pairing of another 2 given group
103    /// elements, i.e. `e(a, b) = e(c, d)`
104    pub fn add_sources(
105        &mut self,
106        a: &E::G1Affine,
107        b: impl Into<E::G2Prepared>,
108        c: &E::G1Affine,
109        d: impl Into<E::G2Prepared>,
110    ) {
111        self.add_sources_with_laziness_choice(a, b, c, d, self.lazy)
112    }
113
114    /// Same as `Self::add_multiple_sources_and_target` except that this accepts whether to be lazy or
115    /// not and does not default to laziness decided during creation of the checker
116    pub fn add_multiple_sources_and_target_with_laziness_choice(
117        &mut self,
118        a: &[E::G1Affine],
119        b: impl IntoIterator<Item = impl Into<E::G2Prepared>>,
120        out: &PairingOutput<E>,
121        lazy: bool,
122    ) {
123        let m = self.current_random.into_bigint();
124        // {a_m}_i = a_i * m
125        let mut a_m = cfg_iter!(a)
126            .map(|a| E::G1Prepared::from(a.mul_bigint(m)))
127            .collect::<Vec<_>>();
128        if lazy {
129            self.pending.0.append(&mut a_m);
130            self.pending
131                .1
132                .append(&mut b.into_iter().map(|b| b.into()).collect());
133        } else {
134            self.left.0.mul_assign(E::multi_miller_loop(a_m, b).0);
135        }
136        self.right += out.mul_bigint(m);
137        self.current_random *= self.random;
138    }
139
140    /// Same as `Self::add_multiple_sources` except that this accepts whether to be lazy or
141    /// not and does not default to laziness decided during creation of the checker
142    pub fn add_multiple_sources_with_laziness_choice(
143        &mut self,
144        a: &[E::G1Affine],
145        b: impl IntoIterator<Item = impl Into<E::G2Prepared>>,
146        c: &[E::G1Affine],
147        d: impl IntoIterator<Item = impl Into<E::G2Prepared>>,
148        lazy: bool,
149    ) {
150        let m = self.current_random.into_bigint();
151        // {a_m}_i = a_i * m
152        let mut a_m = cfg_iter!(a)
153            .map(|a| E::G1Prepared::from(a.mul_bigint(m)))
154            .collect::<Vec<_>>();
155        // {c_m}_i = c_i * -m
156        let mut c_m = cfg_iter!(c)
157            .map(|c| E::G1Prepared::from(-c.mul_bigint(m)))
158            .collect::<Vec<_>>();
159        if lazy {
160            self.pending.0.append(&mut a_m);
161            self.pending
162                .1
163                .append(&mut b.into_iter().map(|b| b.into()).collect());
164            self.pending.0.append(&mut c_m);
165            self.pending
166                .1
167                .append(&mut d.into_iter().map(|d| d.into()).collect());
168        } else {
169            self.left.0.mul_assign(E::multi_miller_loop(a_m, b).0);
170            self.left.0.mul_assign(E::multi_miller_loop(c_m, d).0);
171        }
172        self.current_random *= self.random;
173    }
174
175    /// Same as `Self::add_sources` except that this accepts whether to be lazy or
176    /// not and does not default to laziness decided during creation of the checker
177    pub fn add_sources_with_laziness_choice(
178        &mut self,
179        a: &E::G1Affine,
180        b: impl Into<E::G2Prepared>,
181        c: &E::G1Affine,
182        d: impl Into<E::G2Prepared>,
183        lazy: bool,
184    ) {
185        let m = self.current_random.into_bigint();
186        let am = E::G1Prepared::from(a.mul_bigint(m));
187        let cm = E::G1Prepared::from(-c.mul_bigint(m));
188        let b = b.into();
189        let d = d.into();
190        if lazy {
191            self.pending.0.push(am);
192            self.pending.0.push(cm);
193            self.pending.1.push(b);
194            self.pending.1.push(d);
195        } else {
196            self.left
197                .0
198                .mul_assign(E::multi_miller_loop([am, cm], [b, d]).0);
199        }
200        self.current_random *= self.random;
201    }
202
203    /// Verify that all added pairing equations are satisfied.
204    pub fn verify(&self) -> bool {
205        debug_assert_eq!(self.pending.0.len(), self.pending.1.len());
206        let left = if !self.pending.0.is_empty() {
207            let mut p = E::multi_miller_loop(self.pending.0.clone(), self.pending.1.clone());
208            p.0.mul_assign(self.left.0);
209            p
210        } else {
211            self.left
212        };
213        E::final_exponentiation(left).unwrap() == self.right
214    }
215}
216
217#[cfg(test)]
218mod test {
219    use super::*;
220    use ark_bls12_381::{Bls12_381, G1Projective, G2Projective};
221    use ark_ec::{bls12::G2Prepared, CurveGroup};
222    use ark_std::{
223        rand::{prelude::StdRng, SeedableRng},
224        UniformRand,
225    };
226    use std::time::Instant;
227
228    fn rev_vec<T: Clone>(v: &[T]) -> Vec<T> {
229        let mut x = v.to_vec();
230        x.reverse();
231        x
232    }
233
234    #[test]
235    fn test_pairing_randomize() {
236        let mut rng = StdRng::seed_from_u64(0u64);
237        let n = 10;
238        let mut t1 = 0;
239
240        let a1 = (0..n)
241            .map(|_| G1Projective::rand(&mut rng).into_affine())
242            .collect::<Vec<_>>();
243        let b1 = (0..n)
244            .map(|_| G2Projective::rand(&mut rng).into_affine())
245            .collect::<Vec<_>>();
246        let a2 = (0..n + 5)
247            .map(|_| G1Projective::rand(&mut rng).into_affine())
248            .collect::<Vec<_>>();
249        let b2 = (0..n + 5)
250            .map(|_| G2Projective::rand(&mut rng).into_affine())
251            .collect::<Vec<_>>();
252        let a3 = (0..n - 2)
253            .map(|_| G1Projective::rand(&mut rng).into_affine())
254            .collect::<Vec<_>>();
255        let b3 = (0..n - 2)
256            .map(|_| G2Projective::rand(&mut rng).into_affine())
257            .collect::<Vec<_>>();
258
259        let start = Instant::now();
260        let out1 = Bls12_381::multi_pairing(a1.clone(), b1.clone());
261        t1 += start.elapsed().as_micros();
262
263        let start = Instant::now();
264        let out2 = Bls12_381::multi_pairing(a2.clone(), b2.clone());
265        t1 += start.elapsed().as_micros();
266
267        let start = Instant::now();
268        let out3 = Bls12_381::multi_pairing(a3.clone(), b3.clone());
269        t1 += start.elapsed().as_micros();
270
271        println!("Time taken without checker {} us", t1);
272
273        for lazy in [true, false] {
274            let start = Instant::now();
275            let mut checker = RandomizedPairingChecker::<Bls12_381>::new_using_rng(&mut rng, lazy);
276            checker.add_multiple_sources_and_target(&a1, &b1, &out1);
277            checker.add_multiple_sources_and_target(&a2, &b2, &out2);
278            checker.add_multiple_sources_and_target(&a3, &b3, &out3);
279            assert!(checker.verify());
280            let l_str = if lazy { "lazy-" } else { "" };
281            println!(
282                "Time taken with {}checker {} us",
283                l_str,
284                start.elapsed().as_micros()
285            );
286
287            // Fail on wrong output
288            let mut checker = RandomizedPairingChecker::<Bls12_381>::new_using_rng(&mut rng, lazy);
289            checker.add_multiple_sources_and_target(&a1, &b1, &out2);
290            checker.add_multiple_sources_and_target(&a2, &b2, &out1);
291            assert!(!checker.verify());
292        }
293
294        let b1_prep = b1.iter().map(|b| G2Prepared::from(*b)).collect::<Vec<_>>();
295        let b2_prep = b2.iter().map(|b| G2Prepared::from(*b)).collect::<Vec<_>>();
296        let b3_prep = b3.iter().map(|b| G2Prepared::from(*b)).collect::<Vec<_>>();
297
298        for lazy in [true, false] {
299            let start = Instant::now();
300            let mut checker = RandomizedPairingChecker::<Bls12_381>::new_using_rng(&mut rng, lazy);
301            checker.add_multiple_sources_and_target(&a1, b1_prep.clone(), &out1);
302            checker.add_multiple_sources_and_target(&a2, b2_prep.clone(), &out2);
303            checker.add_multiple_sources_and_target(&a3, b3_prep.clone(), &out3);
304            assert!(checker.verify());
305            let l_str = if lazy { "lazy-" } else { "" };
306            println!(
307                "Time taken with prepared G2 and {}checker {} us",
308                l_str,
309                start.elapsed().as_micros()
310            );
311        }
312
313        let a1_rev = rev_vec(&a1);
314        let a2_rev = rev_vec(&a2);
315        let a3_rev = rev_vec(&a3);
316        let b1_rev = rev_vec(&b1);
317        let b2_rev = rev_vec(&b2);
318        let b3_rev = rev_vec(&b3);
319
320        let b1_rev_prep = b1_rev
321            .iter()
322            .map(|b| G2Prepared::from(*b))
323            .collect::<Vec<_>>();
324        let b2_rev_prep = b2_rev
325            .iter()
326            .map(|b| G2Prepared::from(*b))
327            .collect::<Vec<_>>();
328        let b3_rev_prep = b3_rev
329            .iter()
330            .map(|b| G2Prepared::from(*b))
331            .collect::<Vec<_>>();
332
333        for lazy in [true, false] {
334            let mut checker = RandomizedPairingChecker::<Bls12_381>::new_using_rng(&mut rng, lazy);
335            checker.add_multiple_sources(&a1, &b1, &a1_rev, &b1_rev);
336            assert!(checker.verify());
337        }
338
339        for lazy in [true, false] {
340            let start = Instant::now();
341            let mut checker = RandomizedPairingChecker::<Bls12_381>::new_using_rng(&mut rng, lazy);
342            checker.add_multiple_sources(&a1, &b1, &a1_rev, &b1_rev);
343            checker.add_multiple_sources(&a2, &b2, &a2_rev, &b2_rev);
344            checker.add_multiple_sources(&a3, &b3, &a3_rev, &b3_rev);
345            assert!(checker.verify());
346            let l_str = if lazy { "lazy-" } else { "" };
347            println!(
348                "Time taken with {}checker {} us",
349                l_str,
350                start.elapsed().as_micros()
351            );
352        }
353
354        for lazy in [true, false] {
355            let start = Instant::now();
356            let mut checker = RandomizedPairingChecker::<Bls12_381>::new_using_rng(&mut rng, lazy);
357            checker.add_multiple_sources(&a1, b1_prep.clone(), &a1_rev, b1_rev_prep.clone());
358            checker.add_multiple_sources(&a2, b2_prep.clone(), &a2_rev, b2_rev_prep.clone());
359            checker.add_multiple_sources(&a3, b3_prep.clone(), &a3_rev, b3_rev_prep.clone());
360            assert!(checker.verify());
361            let l_str = if lazy { "lazy-" } else { "" };
362            println!(
363                "Time taken with prepared G2 and {}checker {} us",
364                l_str,
365                start.elapsed().as_micros()
366            );
367        }
368
369        for lazy in [true, false] {
370            let start = Instant::now();
371            let mut checker = RandomizedPairingChecker::<Bls12_381>::new_using_rng(&mut rng, lazy);
372            checker.add_multiple_sources_and_target(&a1, &b1, &out1);
373            checker.add_multiple_sources_and_target(&a2, &b2, &out2);
374            checker.add_multiple_sources_and_target(&a3, &b3, &out3);
375            checker.add_multiple_sources(&a1, &b1, &a1_rev, &b1_rev);
376            checker.add_multiple_sources(&a2, &b2, &a2_rev, &b2_rev);
377            checker.add_multiple_sources(&a3, &b3, &a3_rev, &b3_rev);
378            assert!(checker.verify());
379            let l_str = if lazy { "lazy-" } else { "" };
380            println!(
381                "Time taken with {}checker {} us",
382                l_str,
383                start.elapsed().as_micros()
384            );
385        }
386
387        for lazy in [true, false] {
388            let mut checker = RandomizedPairingChecker::<Bls12_381>::new_using_rng(&mut rng, lazy);
389            checker.add_sources(&a1[0], b1[0], &a1[0], b1[0]);
390            assert!(checker.verify());
391
392            let mut checker = RandomizedPairingChecker::<Bls12_381>::new_using_rng(&mut rng, lazy);
393            checker.add_sources(&a1[0], b1[0], &a1[0], b1[0]);
394            checker.add_sources(&a1[1], b1[1], &a1[1], b1[1]);
395            checker.add_sources(&a1[2], b1[2], &a1[2], b1[2]);
396            assert!(checker.verify());
397        }
398
399        for lazy in [true, false] {
400            let out_0 = Bls12_381::pairing(&a1[0], b1[0]);
401            let out_1 = Bls12_381::pairing(&a1[1], b1[1]);
402            let out_2 = Bls12_381::pairing(&a1[2], b1[2]);
403
404            let mut checker = RandomizedPairingChecker::<Bls12_381>::new_using_rng(&mut rng, lazy);
405            checker.add_sources_and_target(&a1[0], b1[0], &out_0);
406            assert!(checker.verify());
407
408            let mut checker = RandomizedPairingChecker::<Bls12_381>::new_using_rng(&mut rng, lazy);
409            checker.add_sources_and_target(&a1[0], b1[0], &out_0);
410            checker.add_sources_and_target(&a1[1], b1[1], &out_1);
411            checker.add_sources_and_target(&a1[2], b1[2], &out_2);
412            assert!(checker.verify());
413
414            // Fail on wrong output
415            let mut checker = RandomizedPairingChecker::<Bls12_381>::new_using_rng(&mut rng, lazy);
416            let wrong_out = Bls12_381::pairing(&a1[0], b1[1]);
417            checker.add_sources_and_target(&a1[0], b1[0], &wrong_out);
418            assert!(!checker.verify());
419        }
420    }
421}
dock_crypto_utils/randomized_pairing_check.rs

dock_crypto_utils/
randomized_pairing_check.rs
