poly_commitment/
combine.rs

1//! Batch elliptic curve algorithms based on the batch-affine principle.
2//!
3//! The principle is the following:
4//!
5//! Usually, affine coordinates are not used because curve operations require
6//! division, which is very inefficient. However, if one is performing a large
7//! number of curve operations at the same time, then the inverses can be computed
8//! efficiently using the *batch inversion algorithm* which allows you to compute
9//! the inverses for an array of elements at a cost of 3 multiplications per element.
10//!
11//! With the reduced cost of inversion, in settings where you are computing many
12//! parallel elliptic curve operations, it is actually cheaper to use affine coordinates.
13//!
14//! Most algorithms in this module take an argument `denominators: &mut Vec<F>` which
15//! is a scratch array used for performing inversions. It is passed around to
16//! avoid re-allocating such a scratch array within each algorithm.
17
18use alloc::{vec, vec::Vec};
19use ark_ec::{
20    models::short_weierstrass::Affine as SWJAffine, short_weierstrass::SWCurveConfig,
21    AdditiveGroup, AffineRepr, CurveGroup,
22};
23use ark_ff::{BitIteratorBE, Field, One, PrimeField, Zero};
24use core::ops::AddAssign;
25use itertools::Itertools;
26use mina_poseidon::sponge::ScalarChallenge;
27#[cfg(feature = "parallel")]
28use rayon::prelude::*;
29
30fn add_pairs_in_place<P: SWCurveConfig>(pairs: &mut Vec<SWJAffine<P>>) {
31    let len = if pairs.len().is_multiple_of(2) {
32        pairs.len()
33    } else {
34        pairs.len() - 1
35    };
36    let mut denominators = pairs
37        .as_chunks_mut::<2>()
38        .0
39        .iter()
40        .map(|p| {
41            if p[0].x == p[1].x {
42                if p[1].y.is_zero() {
43                    P::BaseField::one()
44                } else {
45                    p[1].y.double()
46                }
47            } else {
48                p[0].x - p[1].x
49            }
50        })
51        .collect::<Vec<_>>();
52
53    ark_ff::batch_inversion::<P::BaseField>(&mut denominators);
54
55    for (i, d) in (0..len).step_by(2).zip(denominators.iter()) {
56        let j = i / 2;
57        if pairs[i + 1].is_zero() {
58            pairs[j] = pairs[i];
59        } else if pairs[i].is_zero() {
60            pairs[j] = pairs[i + 1];
61        } else if pairs[i + 1].x == pairs[i].x
62            && (pairs[i + 1].y != pairs[i].y || pairs[i + 1].y.is_zero())
63        {
64            pairs[j] = SWJAffine::<P>::zero();
65        } else if pairs[i + 1].x == pairs[i].x && pairs[i + 1].y == pairs[i].y {
66            let sq = pairs[i].x.square();
67            let s = (sq.double() + sq + P::COEFF_A) * d;
68            let x = s.square() - pairs[i].x.double();
69            let y = -pairs[i].y - (s * (x - pairs[i].x));
70            pairs[j].x = x;
71            pairs[j].y = y;
72        } else {
73            let s = (pairs[i].y - pairs[i + 1].y) * d;
74            let x = s.square() - pairs[i].x - pairs[i + 1].x;
75            let y = -pairs[i].y - (s * (x - pairs[i].x));
76            pairs[j].x = x;
77            pairs[j].y = y;
78        }
79    }
80
81    let len = pairs.len();
82    if len % 2 == 1 {
83        pairs[len / 2] = pairs[len - 1];
84        pairs.truncate(len / 2 + 1);
85    } else {
86        pairs.truncate(len / 2);
87    }
88}
89
90/// Given arrays of curve points `v0` and `v1` do `v0[i] += v1[i]` for each i,
91/// assuming that for each `i`, `v0[i].x != v1[i].x` so we can use the ordinary
92/// addition formula and don't have to handle the edge cases of doubling and
93/// hitting the point at infinity.
94fn batch_add_assign_no_branch<P: SWCurveConfig>(
95    denominators: &mut [P::BaseField],
96    v0: &mut [SWJAffine<P>],
97    v1: &[SWJAffine<P>],
98) {
99    o1_utils::cfg_iter_mut!(denominators)
100        .enumerate()
101        .for_each(|(i, denom)| {
102            let p0 = v0[i];
103            let p1 = v1[i];
104            let d = p0.x - p1.x;
105            *denom = d;
106        });
107
108    ark_ff::batch_inversion::<P::BaseField>(denominators);
109
110    o1_utils::cfg_iter!(denominators)
111        .zip(o1_utils::cfg_iter_mut!(v0))
112        .zip(o1_utils::cfg_iter!(v1))
113        .for_each(|((d, p0), p1)| {
114            let s = (p0.y - p1.y) * d;
115            let x = s.square() - p0.x - p1.x;
116            let y = -p0.y - (s * (x - p0.x));
117            p0.x = x;
118            p0.y = y;
119        });
120}
121
122/// Given arrays of curve points `v0` and `v1` do `v0[i] += v1[i]` for each i.
123pub fn batch_add_assign<P: SWCurveConfig>(
124    denominators: &mut [P::BaseField],
125    v0: &mut [SWJAffine<P>],
126    v1: &[SWJAffine<P>],
127) {
128    o1_utils::cfg_iter_mut!(denominators)
129        .zip(o1_utils::cfg_iter!(v0))
130        .zip(o1_utils::cfg_iter!(v1))
131        .for_each(|((denom, p0), p1)| {
132            let d = if p0.x == p1.x {
133                if p1.y.is_zero() {
134                    P::BaseField::one()
135                } else {
136                    p1.y.double()
137                }
138            } else {
139                p0.x - p1.x
140            };
141            *denom = d;
142        });
143
144    ark_ff::batch_inversion::<P::BaseField>(denominators);
145
146    o1_utils::cfg_iter!(denominators)
147        .zip(o1_utils::cfg_iter_mut!(v0))
148        .zip(o1_utils::cfg_iter!(v1))
149        .for_each(|((d, p0), p1)| {
150            if p1.is_zero() {
151            } else if p0.is_zero() {
152                *p0 = *p1;
153            } else if p1.x == p0.x && (p1.y != p0.y || p1.y == P::BaseField::zero()) {
154                *p0 = SWJAffine::<P>::zero();
155            } else if p1.x == p0.x && p1.y == p0.y {
156                let sq = p0.x.square();
157                let s = (sq.double() + sq + P::COEFF_A) * d;
158                let x = s.square() - p0.x.double();
159                let y = -p0.y - (s * (x - p0.x));
160                p0.x = x;
161                p0.y = y;
162            } else {
163                let s = (p0.y - p1.y) * d;
164                let x = s.square() - p0.x - p1.x;
165                let y = -p0.y - (s * (x - p0.x));
166                p0.x = x;
167                p0.y = y;
168            }
169        });
170}
171
172fn affine_window_combine_base<P: SWCurveConfig>(
173    g1: &[SWJAffine<P>],
174    g2: &[SWJAffine<P>],
175    x1: P::ScalarField,
176    x2: P::ScalarField,
177) -> Vec<SWJAffine<P>> {
178    let g1g2 = {
179        let mut v: Vec<_> = (0..2 * g1.len())
180            .map(|i| {
181                let j = i / 2;
182                if i % 2 == 0 {
183                    g1[j]
184                } else {
185                    g2[j]
186                }
187            })
188            .collect();
189        add_pairs_in_place(&mut v);
190        v
191    };
192    assert_eq!(g1g2.len(), g1.len());
193
194    let windows1 = BitIteratorBE::new(x1.into_bigint()).tuples();
195    let windows2 = BitIteratorBE::new(x2.into_bigint()).tuples();
196
197    let mut points = vec![SWJAffine::<P>::zero(); g1.len()];
198
199    let mut denominators = vec![P::BaseField::zero(); g1.len()];
200
201    let [g01_00, g10_00, g11_00, g00_01, g01_01, g10_01, g11_01, g00_10, g01_10, g10_10, g11_10, g00_11, g01_11, g10_11, g11_11] =
202        affine_shamir_window_table(&mut denominators, g1, g2);
203
204    for ((hi_1, lo_1), (hi_2, lo_2)) in windows1.zip(windows2) {
205        // double in place
206        for _ in 0..2 {
207            for i in 0..g1.len() {
208                denominators[i] = points[i].y.double();
209            }
210            ark_ff::batch_inversion::<P::BaseField>(&mut denominators);
211
212            // TODO: Use less memory
213            for i in 0..g1.len() {
214                let d = denominators[i];
215                let sq = points[i].x.square();
216                let s = (sq.double() + sq + P::COEFF_A) * d;
217                let x = s.square() - points[i].x.double();
218                let y = -points[i].y - (s * (x - points[i].x));
219                points[i].x = x;
220                points[i].y = y;
221            }
222        }
223
224        match ((hi_1, lo_1), (hi_2, lo_2)) {
225            ((false, false), (false, false)) => (),
226            ((false, true), (false, false)) => {
227                batch_add_assign(&mut denominators, &mut points, &g01_00);
228            }
229            ((true, false), (false, false)) => {
230                batch_add_assign(&mut denominators, &mut points, &g10_00);
231            }
232            ((true, true), (false, false)) => {
233                batch_add_assign(&mut denominators, &mut points, &g11_00);
234            }
235
236            ((false, false), (false, true)) => {
237                batch_add_assign(&mut denominators, &mut points, &g00_01);
238            }
239            ((false, true), (false, true)) => {
240                batch_add_assign(&mut denominators, &mut points, &g01_01);
241            }
242            ((true, false), (false, true)) => {
243                batch_add_assign(&mut denominators, &mut points, &g10_01);
244            }
245            ((true, true), (false, true)) => {
246                batch_add_assign(&mut denominators, &mut points, &g11_01);
247            }
248
249            ((false, false), (true, false)) => {
250                batch_add_assign(&mut denominators, &mut points, &g00_10);
251            }
252            ((false, true), (true, false)) => {
253                batch_add_assign(&mut denominators, &mut points, &g01_10);
254            }
255            ((true, false), (true, false)) => {
256                batch_add_assign(&mut denominators, &mut points, &g10_10);
257            }
258            ((true, true), (true, false)) => {
259                batch_add_assign(&mut denominators, &mut points, &g11_10);
260            }
261
262            ((false, false), (true, true)) => {
263                batch_add_assign(&mut denominators, &mut points, &g00_11);
264            }
265            ((false, true), (true, true)) => {
266                batch_add_assign(&mut denominators, &mut points, &g01_11);
267            }
268            ((true, false), (true, true)) => {
269                batch_add_assign(&mut denominators, &mut points, &g10_11);
270            }
271            ((true, true), (true, true)) => {
272                batch_add_assign(&mut denominators, &mut points, &g11_11);
273            }
274        }
275    }
276    points
277}
278
279fn batch_endo_in_place<P: SWCurveConfig>(endo_coeff: P::BaseField, ps: &mut [SWJAffine<P>]) {
280    o1_utils::cfg_iter_mut!(ps).for_each(|p| p.x *= endo_coeff);
281}
282
283fn batch_negate_in_place<P: SWCurveConfig>(ps: &mut [SWJAffine<P>]) {
284    o1_utils::cfg_iter_mut!(ps).for_each(|p| {
285        p.y = -p.y;
286    });
287}
288
289/// Uses a batch version of Algorithm 1 of
290/// <https://eprint.iacr.org/2019/1021.pdf> (on page 19) to compute `g1 +
291/// g2.scale(chal.to_field(endo_coeff))`
292fn affine_window_combine_one_endo_base<P: SWCurveConfig>(
293    endo_coeff: P::BaseField,
294    g1: &[SWJAffine<P>],
295    g2: &[SWJAffine<P>],
296    chal: &ScalarChallenge<P::ScalarField>,
297) -> Vec<SWJAffine<P>> {
298    fn assign<A: Copy>(dst: &mut [A], src: &[A]) {
299        let n = dst.len();
300        dst[..n].clone_from_slice(&src[..n]);
301    }
302
303    const fn get_bit(limbs_lsb: &[u64], i: u64) -> u64 {
304        let limb = i / 64;
305        let j = i % 64;
306        (limbs_lsb[limb as usize] >> j) & 1
307    }
308
309    let rep = chal.inner().into_bigint();
310    let r = rep.as_ref();
311
312    let mut denominators = vec![P::BaseField::zero(); g1.len()];
313    // acc = 2 (phi(g2) + g2)
314    let mut points = g2.to_vec();
315    batch_endo_in_place(endo_coeff, &mut points);
316    batch_add_assign_no_branch(&mut denominators, &mut points, g2);
317    batch_double_in_place(&mut denominators, &mut points);
318
319    let mut tmp_s = g2.to_vec();
320    let mut tmp_acc = g2.to_vec();
321    for i in (0..(128 / 2)).rev() {
322        // s = g2
323        assign(&mut tmp_s, g2);
324        // tmp = acc
325        assign(&mut tmp_acc, &points);
326
327        let r_2i = get_bit(r, 2 * i);
328        if r_2i == 0 {
329            batch_negate_in_place(&mut tmp_s);
330        }
331        if get_bit(r, 2 * i + 1) == 1 {
332            batch_endo_in_place(endo_coeff, &mut tmp_s);
333        }
334
335        // acc = (acc + s) + acc
336        batch_add_assign_no_branch(&mut denominators, &mut points, &tmp_s);
337        batch_add_assign_no_branch(&mut denominators, &mut points, &tmp_acc);
338    }
339    // acc += g1
340    batch_add_assign(&mut denominators, &mut points, g1);
341    points
342}
343
344/// Double an array of curve points in-place.
345fn batch_double_in_place<P: SWCurveConfig>(
346    denominators: &mut [P::BaseField],
347    points: &mut [SWJAffine<P>],
348) {
349    o1_utils::cfg_iter_mut!(denominators)
350        .zip(o1_utils::cfg_iter!(points))
351        .for_each(|(d, p)| {
352            *d = p.y.double();
353        });
354    ark_ff::batch_inversion::<P::BaseField>(denominators);
355
356    // TODO: Use less memory
357    o1_utils::cfg_iter!(denominators)
358        .zip(o1_utils::cfg_iter_mut!(points))
359        .for_each(|(d, p)| {
360            let sq = p.x.square();
361            let s = (sq.double() + sq + P::COEFF_A) * d;
362            let x = s.square() - p.x.double();
363            let y = -p.y - (s * (x - p.x));
364            p.x = x;
365            p.y = y;
366        });
367}
368
369fn affine_window_combine_one_base<P: SWCurveConfig>(
370    g1: &[SWJAffine<P>],
371    g2: &[SWJAffine<P>],
372    x2: P::ScalarField,
373) -> Vec<SWJAffine<P>> {
374    let windows2 = BitIteratorBE::new(x2.into_bigint()).tuples();
375
376    let mut points = vec![SWJAffine::<P>::zero(); g1.len()];
377
378    let mut denominators = vec![P::BaseField::zero(); g1.len()];
379
380    let [g01, g10, g11] = affine_shamir_window_table_one(&mut denominators, g2);
381
382    for (hi_2, lo_2) in windows2 {
383        // double in place
384        for _ in 0..2 {
385            for i in 0..g1.len() {
386                denominators[i] = points[i].y.double();
387            }
388            ark_ff::batch_inversion::<P::BaseField>(&mut denominators);
389
390            // TODO: Use less memory
391            for i in 0..g1.len() {
392                let d = denominators[i];
393                let sq = points[i].x.square();
394                let s = (sq.double() + sq + P::COEFF_A) * d;
395                let x = s.square() - points[i].x.double();
396                let y = -points[i].y - (s * (x - points[i].x));
397                points[i].x = x;
398                points[i].y = y;
399            }
400        }
401
402        match (hi_2, lo_2) {
403            (false, false) => (),
404            (false, true) => batch_add_assign(&mut denominators, &mut points, &g01),
405            (true, false) => batch_add_assign(&mut denominators, &mut points, &g10),
406            (true, true) => {
407                batch_add_assign(&mut denominators, &mut points, &g11);
408            }
409        }
410    }
411
412    batch_add_assign(&mut denominators, &mut points, g1);
413
414    points
415}
416
417pub fn affine_window_combine<P: SWCurveConfig>(
418    g1: &[SWJAffine<P>],
419    g2: &[SWJAffine<P>],
420    x1: P::ScalarField,
421    x2: P::ScalarField,
422) -> Vec<SWJAffine<P>> {
423    const CHUNK_SIZE: usize = 10_000;
424    let b: Vec<_> = g1.chunks(CHUNK_SIZE).zip(g2.chunks(CHUNK_SIZE)).collect();
425    let v: Vec<_> = o1_utils::cfg_into_iter!(b)
426        .map(|(v1, v2)| affine_window_combine_base(v1, v2, x1, x2))
427        .collect();
428    v.concat()
429}
430
431/// Given vectors of curve points `g1` and `g2`, compute a vector whose ith
432/// entry is `g1[i] + g2[i].scale(chal.to_field(endo_coeff))`
433///
434/// Internally, it uses the curve endomorphism to speed up this operation.
435pub fn affine_window_combine_one_endo<P: SWCurveConfig>(
436    endo_coeff: P::BaseField,
437    g1: &[SWJAffine<P>],
438    g2: &[SWJAffine<P>],
439    chal: &ScalarChallenge<P::ScalarField>,
440) -> Vec<SWJAffine<P>> {
441    const CHUNK_SIZE: usize = 4096;
442    let b: Vec<_> = g1.chunks(CHUNK_SIZE).zip(g2.chunks(CHUNK_SIZE)).collect();
443    let v: Vec<_> = o1_utils::cfg_into_iter!(b)
444        .map(|(v1, v2)| affine_window_combine_one_endo_base(endo_coeff, v1, v2, chal))
445        .collect();
446    v.concat()
447}
448pub fn affine_window_combine_one<P: SWCurveConfig>(
449    g1: &[SWJAffine<P>],
450    g2: &[SWJAffine<P>],
451    x2: P::ScalarField,
452) -> Vec<SWJAffine<P>> {
453    const CHUNK_SIZE: usize = 10_000;
454    let b: Vec<_> = g1.chunks(CHUNK_SIZE).zip(g2.chunks(CHUNK_SIZE)).collect();
455    let v: Vec<_> = o1_utils::cfg_into_iter!(b)
456        .map(|(v1, v2)| affine_window_combine_one_base(v1, v2, x2))
457        .collect();
458    v.concat()
459}
460
461pub fn window_combine<G: AffineRepr>(
462    g_lo: &[G],
463    g_hi: &[G],
464    x_lo: G::ScalarField,
465    x_hi: G::ScalarField,
466) -> Vec<G> {
467    let mut g_proj: Vec<G::Group> = {
468        let pairs: Vec<_> = g_lo.iter().zip(g_hi).collect();
469        o1_utils::cfg_into_iter!(pairs)
470            .map(|(lo, hi)| window_shamir::<G>(x_lo, *lo, x_hi, *hi))
471            .collect()
472    };
473    G::Group::normalize_batch(g_proj.as_mut_slice())
474}
475
476pub fn affine_shamir_window_table<P: SWCurveConfig>(
477    denominators: &mut [P::BaseField],
478    g1: &[SWJAffine<P>],
479    g2: &[SWJAffine<P>],
480) -> [Vec<SWJAffine<P>>; 15] {
481    fn assign<A: Copy>(dst: &mut [A], src: &[A]) {
482        let n = dst.len();
483        dst[..n].clone_from_slice(&src[..n]);
484    }
485
486    let n = g1.len();
487
488    let mut res: [Vec<_>; 15] = [
489        vec![SWJAffine::<P>::zero(); n],
490        vec![SWJAffine::<P>::zero(); n],
491        vec![SWJAffine::<P>::zero(); n],
492        vec![SWJAffine::<P>::zero(); n],
493        vec![SWJAffine::<P>::zero(); n],
494        vec![SWJAffine::<P>::zero(); n],
495        vec![SWJAffine::<P>::zero(); n],
496        vec![SWJAffine::<P>::zero(); n],
497        vec![SWJAffine::<P>::zero(); n],
498        vec![SWJAffine::<P>::zero(); n],
499        vec![SWJAffine::<P>::zero(); n],
500        vec![SWJAffine::<P>::zero(); n],
501        vec![SWJAffine::<P>::zero(); n],
502        vec![SWJAffine::<P>::zero(); n],
503        vec![SWJAffine::<P>::zero(); n],
504    ];
505
506    let [g01_00, g10_00, g11_00, g00_01, g01_01, g10_01, g11_01, g00_10, g01_10, g10_10, g11_10, g00_11, g01_11, g10_11, g11_11] =
507        &mut res;
508
509    assign(g01_00, g1);
510
511    assign(g10_00, g1);
512    batch_add_assign(denominators, g10_00, g1);
513
514    assign(g11_00, g10_00);
515    batch_add_assign(denominators, g11_00, g1);
516
517    assign(g00_01, g2);
518
519    assign(g01_01, g00_01);
520    batch_add_assign(denominators, g01_01, g1);
521
522    assign(g10_01, g01_01);
523    batch_add_assign(denominators, g10_01, g1);
524
525    assign(g11_01, g10_01);
526    batch_add_assign(denominators, g11_01, g1);
527
528    assign(g00_10, g00_01);
529    batch_add_assign(denominators, g00_10, g2);
530
531    assign(g01_10, g00_10);
532    batch_add_assign(denominators, g01_10, g1);
533
534    assign(g10_10, g01_10);
535    batch_add_assign(denominators, g10_10, g1);
536
537    assign(g11_10, g10_10);
538    batch_add_assign(denominators, g11_10, g1);
539
540    assign(g00_11, g00_10);
541    batch_add_assign(denominators, g00_11, g2);
542
543    assign(g01_11, g00_11);
544    batch_add_assign(denominators, g01_11, g1);
545
546    assign(g10_11, g01_11);
547    batch_add_assign(denominators, g10_11, g1);
548
549    assign(g11_11, g10_11);
550    batch_add_assign(denominators, g11_11, g1);
551
552    res
553}
554
555pub fn affine_shamir_window_table_one<P: SWCurveConfig>(
556    denominators: &mut [P::BaseField],
557    g1: &[SWJAffine<P>],
558) -> [Vec<SWJAffine<P>>; 3] {
559    fn assign<A: Copy>(dst: &mut [A], src: &[A]) {
560        let n = dst.len();
561        dst[..n].clone_from_slice(&src[..n]);
562    }
563
564    let n = g1.len();
565
566    let mut res: [Vec<_>; 3] = [
567        vec![SWJAffine::<P>::zero(); n],
568        vec![SWJAffine::<P>::zero(); n],
569        vec![SWJAffine::<P>::zero(); n],
570    ];
571
572    let [g01, g10, g11] = &mut res;
573
574    assign(g01, g1);
575
576    assign(g10, g1);
577    batch_add_assign(denominators, g10, g1);
578
579    assign(g11, g10);
580    batch_add_assign(denominators, g11, g1);
581
582    res
583}
584
585fn window_shamir<G: AffineRepr>(x1: G::ScalarField, g1: G, x2: G::ScalarField, g2: G) -> G::Group {
586    let [_g00_00, g01_00, g10_00, g11_00, g00_01, g01_01, g10_01, g11_01, g00_10, g01_10, g10_10, g11_10, g00_11, g01_11, g10_11, g11_11] =
587        shamir_window_table(g1, g2);
588
589    let windows1 = BitIteratorBE::new(x1.into_bigint()).tuples();
590    let windows2 = BitIteratorBE::new(x2.into_bigint()).tuples();
591
592    let mut res = G::Group::zero();
593
594    for ((hi_1, lo_1), (hi_2, lo_2)) in windows1.zip(windows2) {
595        res.double_in_place();
596        res.double_in_place();
597        match ((hi_1, lo_1), (hi_2, lo_2)) {
598            ((false, false), (false, false)) => (),
599            ((false, true), (false, false)) => res.add_assign(&g01_00),
600            ((true, false), (false, false)) => res.add_assign(&g10_00),
601            ((true, true), (false, false)) => res.add_assign(&g11_00),
602
603            ((false, false), (false, true)) => res.add_assign(&g00_01),
604            ((false, true), (false, true)) => res.add_assign(&g01_01),
605            ((true, false), (false, true)) => res.add_assign(&g10_01),
606            ((true, true), (false, true)) => res.add_assign(&g11_01),
607
608            ((false, false), (true, false)) => res.add_assign(&g00_10),
609            ((false, true), (true, false)) => res.add_assign(&g01_10),
610            ((true, false), (true, false)) => res.add_assign(&g10_10),
611            ((true, true), (true, false)) => res.add_assign(&g11_10),
612
613            ((false, false), (true, true)) => res.add_assign(&g00_11),
614            ((false, true), (true, true)) => res.add_assign(&g01_11),
615            ((true, false), (true, true)) => res.add_assign(&g10_11),
616            ((true, true), (true, true)) => res.add_assign(&g11_11),
617        }
618    }
619
620    res
621}
622
623pub fn shamir_window_table<G: AffineRepr>(g1: G, g2: G) -> [G; 16] {
624    let g00_00 = G::generator().into_group();
625    let g01_00 = g1.into_group();
626    let g10_00 = {
627        let mut g = g01_00;
628        g.add_assign(&g1);
629        g
630    };
631    let g11_00 = {
632        let mut g = g10_00;
633        g.add_assign(&g1);
634        g
635    };
636
637    let g00_01 = g2.into_group();
638    let g01_01 = {
639        let mut g = g00_01;
640        g.add_assign(&g1);
641        g
642    };
643    let g10_01 = {
644        let mut g = g01_01;
645        g.add_assign(&g1);
646        g
647    };
648    let g11_01 = {
649        let mut g = g10_01;
650        g.add_assign(&g1);
651        g
652    };
653
654    let g00_10 = {
655        let mut g = g00_01;
656        g.add_assign(&g2);
657        g
658    };
659    let g01_10 = {
660        let mut g = g00_10;
661        g.add_assign(&g1);
662        g
663    };
664    let g10_10 = {
665        let mut g = g01_10;
666        g.add_assign(&g1);
667        g
668    };
669    let g11_10 = {
670        let mut g = g10_10;
671        g.add_assign(&g1);
672        g
673    };
674    let g00_11 = {
675        let mut g = g00_10;
676        g.add_assign(&g2);
677        g
678    };
679    let g01_11 = {
680        let mut g = g00_11;
681        g.add_assign(&g1);
682        g
683    };
684    let g10_11 = {
685        let mut g = g01_11;
686        g.add_assign(&g1);
687        g
688    };
689    let g11_11 = {
690        let mut g = g10_11;
691        g.add_assign(&g1);
692        g
693    };
694
695    let mut v = vec![
696        g00_00, g01_00, g10_00, g11_00, g00_01, g01_01, g10_01, g11_01, g00_10, g01_10, g10_10,
697        g11_10, g00_11, g01_11, g10_11, g11_11,
698    ];
699    let v: Vec<_> = G::Group::normalize_batch(v.as_mut_slice());
700    [
701        v[0], v[1], v[2], v[3], v[4], v[5], v[6], v[7], v[8], v[9], v[10], v[11], v[12], v[13],
702        v[14], v[15],
703    ]
704}
poly_commitment/combine.rs

poly_commitment/
combine.rs
