halo2_ecc/bn254/
pairing.rs

Help
1#![allow(non_snake_case)]
2use super::{Fp12Chip, Fp2Chip, FpChip, FpPoint, Fq, FqPoint};
3use crate::fields::vector::FieldVector;
4use crate::halo2_proofs::halo2curves::bn256::{
5    G1Affine, G2Affine, FROBENIUS_COEFF_FQ12_C1, SIX_U_PLUS_2_NAF,
6};
7use crate::{
8    ecc::{EcPoint, EccChip},
9    fields::fp12::mul_no_carry_w6,
10    fields::FieldChip,
11};
12use halo2_base::utils::BigPrimeField;
13use halo2_base::Context;
14
15const XI_0: i64 = 9;
16
17// Inputs:
18//  Q0 = (x_1, y_1) and Q1 = (x_2, y_2) are points in E(Fp2)
19//  P is point (X, Y) in E(Fp)
20// Assuming Q0 != Q1
21// Output:
22//  line_{Psi(Q0), Psi(Q1)}(P) where Psi(x,y) = (w^2 x, w^3 y)
23//  - equals w^3 (y_1 - y_2) X + w^2 (x_2 - x_1) Y + w^5 (x_1 y_2 - x_2 y_1) =: out3 * w^3 + out2 * w^2 + out5 * w^5 where out2, out3, out5 are Fp2 points
24// Output is [None, None, out2, out3, None, out5] as vector of `Option<FqPoint>`s
25pub fn sparse_line_function_unequal<F: BigPrimeField>(
26    fp2_chip: &Fp2Chip<F>,
27    ctx: &mut Context<F>,
28    Q: (&EcPoint<F, FqPoint<F>>, &EcPoint<F, FqPoint<F>>),
29    P: &EcPoint<F, FpPoint<F>>,
30) -> Vec<Option<FqPoint<F>>> {
31    let (x_1, y_1) = (&Q.0.x, &Q.0.y);
32    let (x_2, y_2) = (&Q.1.x, &Q.1.y);
33    let (X, Y) = (&P.x, &P.y);
34    assert_eq!(x_1.0.len(), 2);
35    assert_eq!(y_1.0.len(), 2);
36    assert_eq!(x_2.0.len(), 2);
37    assert_eq!(y_2.0.len(), 2);
38
39    let y1_minus_y2 = fp2_chip.sub_no_carry(ctx, y_1, y_2);
40    let x2_minus_x1 = fp2_chip.sub_no_carry(ctx, x_2, x_1);
41    let x1y2 = fp2_chip.mul_no_carry(ctx, x_1, y_2);
42    let x2y1 = fp2_chip.mul_no_carry(ctx, x_2, y_1);
43
44    let out3 = fp2_chip.0.fp_mul_no_carry(ctx, y1_minus_y2, X);
45    let out2 = fp2_chip.0.fp_mul_no_carry(ctx, x2_minus_x1, Y);
46    let out5 = fp2_chip.sub_no_carry(ctx, &x1y2, &x2y1);
47
48    // so far we have not "carried mod p" for any of the outputs
49    // we do this below
50    [None, None, Some(out2), Some(out3), None, Some(out5)]
51        .into_iter()
52        .map(|option_nc| option_nc.map(|nocarry| fp2_chip.carry_mod(ctx, nocarry)))
53        .collect()
54}
55
56// Assuming curve is of form Y^2 = X^3 + b (a = 0) to save operations
57// Inputs:
58//  Q = (x, y) is a point in E(Fp2)
59//  P = (P.x, P.y) in E(Fp)
60// Output:
61//  line_{Psi(Q), Psi(Q)}(P) where Psi(x,y) = (w^2 x, w^3 y)
62//  - equals (3x^3 - 2y^2)(XI_0 + u) + w^4 (-3 x^2 * Q.x) + w^3 (2 y * Q.y) =: out0 + out4 * w^4 + out3 * w^3 where out0, out3, out4 are Fp2 points
63// Output is [out0, None, None, out3, out4, None] as vector of `Option<FqPoint>`s
64pub fn sparse_line_function_equal<F: BigPrimeField>(
65    fp2_chip: &Fp2Chip<F>,
66    ctx: &mut Context<F>,
67    Q: &EcPoint<F, FqPoint<F>>,
68    P: &EcPoint<F, FpPoint<F>>,
69) -> Vec<Option<FqPoint<F>>> {
70    let (x, y) = (&Q.x, &Q.y);
71    assert_eq!(x.0.len(), 2);
72    assert_eq!(y.0.len(), 2);
73
74    let x_sq = fp2_chip.mul(ctx, x, x);
75
76    let x_cube = fp2_chip.mul_no_carry(ctx, &x_sq, x);
77    let three_x_cu = fp2_chip.scalar_mul_no_carry(ctx, &x_cube, 3);
78    let y_sq = fp2_chip.mul_no_carry(ctx, y, y);
79    let two_y_sq = fp2_chip.scalar_mul_no_carry(ctx, &y_sq, 2);
80    let out0_left = fp2_chip.sub_no_carry(ctx, &three_x_cu, &two_y_sq);
81    let out0 = mul_no_carry_w6::<_, _, XI_0>(fp2_chip.fp_chip(), ctx, out0_left);
82
83    let x_sq_Px = fp2_chip.0.fp_mul_no_carry(ctx, x_sq, &P.x);
84    let out4 = fp2_chip.scalar_mul_no_carry(ctx, x_sq_Px, -3);
85
86    let y_Py = fp2_chip.0.fp_mul_no_carry(ctx, y.clone(), &P.y);
87    let out3 = fp2_chip.scalar_mul_no_carry(ctx, &y_Py, 2);
88
89    // so far we have not "carried mod p" for any of the outputs
90    // we do this below
91    [Some(out0), None, None, Some(out3), Some(out4), None]
92        .into_iter()
93        .map(|option_nc| option_nc.map(|nocarry| fp2_chip.carry_mod(ctx, nocarry)))
94        .collect()
95}
96
97// multiply Fp12 point `a` with Fp12 point `b` where `b` is len 6 vector of Fp2 points, where some are `None` to represent zero.
98// Assumes `b` is not vector of all `None`s
99pub fn sparse_fp12_multiply<F: BigPrimeField>(
100    fp2_chip: &Fp2Chip<F>,
101    ctx: &mut Context<F>,
102    a: &FqPoint<F>,
103    b_fp2_coeffs: &[Option<FqPoint<F>>],
104) -> FqPoint<F> {
105    assert_eq!(a.0.len(), 12);
106    assert_eq!(b_fp2_coeffs.len(), 6);
107    let mut a_fp2_coeffs = Vec::with_capacity(6);
108    for i in 0..6 {
109        a_fp2_coeffs.push(FieldVector(vec![a[i].clone(), a[i + 6].clone()]));
110    }
111    // a * b as element of Fp2[w] without evaluating w^6 = (XI_0 + u)
112    let mut prod_2d = vec![None; 11];
113    for i in 0..6 {
114        for j in 0..6 {
115            prod_2d[i + j] =
116                match (prod_2d[i + j].clone(), &a_fp2_coeffs[i], b_fp2_coeffs[j].as_ref()) {
117                    (a, _, None) => a,
118                    (None, a, Some(b)) => {
119                        let ab = fp2_chip.mul_no_carry(ctx, a, b);
120                        Some(ab)
121                    }
122                    (Some(a), b, Some(c)) => {
123                        let bc = fp2_chip.mul_no_carry(ctx, b, c);
124                        let out = fp2_chip.add_no_carry(ctx, &a, &bc);
125                        Some(out)
126                    }
127                };
128        }
129    }
130
131    let mut out_fp2 = Vec::with_capacity(6);
132    for i in 0..6 {
133        // prod_2d[i] + prod_2d[i+6] * w^6
134        let prod_nocarry = if i != 5 {
135            let eval_w6 = prod_2d[i + 6]
136                .as_ref()
137                .map(|a| mul_no_carry_w6::<_, _, XI_0>(fp2_chip.fp_chip(), ctx, a.clone()));
138            match (prod_2d[i].as_ref(), eval_w6) {
139                (None, b) => b.unwrap(), // Our current use cases of 235 and 034 sparse multiplication always result in non-None value
140                (Some(a), None) => a.clone(),
141                (Some(a), Some(b)) => fp2_chip.add_no_carry(ctx, a, &b),
142            }
143        } else {
144            prod_2d[i].clone().unwrap()
145        };
146        let prod = fp2_chip.carry_mod(ctx, prod_nocarry);
147        out_fp2.push(prod);
148    }
149
150    let mut out_coeffs = Vec::with_capacity(12);
151    for fp2_coeff in &out_fp2 {
152        out_coeffs.push(fp2_coeff[0].clone());
153    }
154    for fp2_coeff in &out_fp2 {
155        out_coeffs.push(fp2_coeff[1].clone());
156    }
157    FieldVector(out_coeffs)
158}
159
160// Input:
161// - g is Fp12 point
162// - Q = (P0, P1) with Q0, Q1 points in E(Fp2)
163// - P is point in E(Fp)
164// Output:
165// - out = g * l_{Psi(Q0), Psi(Q1)}(P) as Fp12 point
166pub fn fp12_multiply_with_line_unequal<F: BigPrimeField>(
167    fp2_chip: &Fp2Chip<F>,
168    ctx: &mut Context<F>,
169    g: &FqPoint<F>,
170    Q: (&EcPoint<F, FqPoint<F>>, &EcPoint<F, FqPoint<F>>),
171    P: &EcPoint<F, FpPoint<F>>,
172) -> FqPoint<F> {
173    let line = sparse_line_function_unequal::<F>(fp2_chip, ctx, Q, P);
174    sparse_fp12_multiply::<F>(fp2_chip, ctx, g, &line)
175}
176
177// Input:
178// - g is Fp12 point
179// - Q is point in E(Fp2)
180// - P is point in E(Fp)
181// Output:
182// - out = g * l_{Psi(Q), Psi(Q)}(P) as Fp12 point
183pub fn fp12_multiply_with_line_equal<F: BigPrimeField>(
184    fp2_chip: &Fp2Chip<F>,
185    ctx: &mut Context<F>,
186    g: &FqPoint<F>,
187    Q: &EcPoint<F, FqPoint<F>>,
188    P: &EcPoint<F, FpPoint<F>>,
189) -> FqPoint<F> {
190    let line = sparse_line_function_equal::<F>(fp2_chip, ctx, Q, P);
191    sparse_fp12_multiply::<F>(fp2_chip, ctx, g, &line)
192}
193
194// Assuming curve is of form `y^2 = x^3 + b` for now (a = 0) for less operations
195// Value of `b` is never used
196// Inputs:
197// - Q = (x, y) is a point in E(Fp2)
198// - P is a point in E(Fp)
199// - `pseudo_binary_encoding` is fixed vector consisting of {-1, 0, 1} entries such that `loop_count = sum pseudo_binary_encoding[i] * 2^i`
200// Output:
201//  - f_{loop_count}(Q,P) * l_{[loop_count] Q', Frob_p(Q')}(P) * l_{[loop_count] Q' + Frob_p(Q'), -Frob_p^2(Q')}(P)
202//  - where we start with `f_1(Q,P) = 1` and use Miller's algorithm f_{i+j} = f_i * f_j * l_{i,j}(Q,P)
203//  - Q' = Psi(Q) in E(Fp12)
204//  - Frob_p(x,y) = (x^p, y^p)
205//  - Above formula is specific to BN curves
206// Assume:
207//  - Q != O and the order of Q in E(Fp2) is r
208//  - r is prime, so [i]Q != [j]Q for i != j in Z/r
209//  - `0 <= loop_count < r` and `loop_count < p` (to avoid [loop_count]Q' = Frob_p(Q'))
210//  - x^3 + b = 0 has no solution in Fp2, i.e., the y-coordinate of Q cannot be 0.
211
212pub fn miller_loop_BN<F: BigPrimeField>(
213    ecc_chip: &EccChip<F, Fp2Chip<F>>,
214    ctx: &mut Context<F>,
215    Q: &EcPoint<F, FqPoint<F>>,
216    P: &EcPoint<F, FpPoint<F>>,
217    pseudo_binary_encoding: &[i8],
218) -> FqPoint<F> {
219    let mut i = pseudo_binary_encoding.len() - 1;
220    while pseudo_binary_encoding[i] == 0 {
221        i -= 1;
222    }
223    let last_index = i;
224
225    let neg_Q = ecc_chip.negate(ctx, Q.clone());
226    assert!(pseudo_binary_encoding[i] == 1 || pseudo_binary_encoding[i] == -1);
227    let mut R = if pseudo_binary_encoding[i] == 1 { Q.clone() } else { neg_Q.clone() };
228    i -= 1;
229
230    // initialize the first line function into Fq12 point
231    let sparse_f = sparse_line_function_equal::<F>(ecc_chip.field_chip(), ctx, &R, P);
232    assert_eq!(sparse_f.len(), 6);
233
234    let fp_chip = ecc_chip.field_chip.fp_chip();
235    let zero_fp = fp_chip.load_constant(ctx, Fq::zero());
236    let mut f_coeffs = Vec::with_capacity(12);
237    for coeff in &sparse_f {
238        if let Some(fp2_point) = coeff {
239            f_coeffs.push(fp2_point[0].clone());
240        } else {
241            f_coeffs.push(zero_fp.clone());
242        }
243    }
244    for coeff in &sparse_f {
245        if let Some(fp2_point) = coeff {
246            f_coeffs.push(fp2_point[1].clone());
247        } else {
248            f_coeffs.push(zero_fp.clone());
249        }
250    }
251
252    let mut f = FieldVector(f_coeffs);
253
254    let fp12_chip = Fp12Chip::<F>::new(fp_chip);
255    loop {
256        if i != last_index - 1 {
257            let f_sq = fp12_chip.mul(ctx, &f, &f);
258            f = fp12_multiply_with_line_equal::<F>(ecc_chip.field_chip(), ctx, &f_sq, &R, P);
259        }
260        R = ecc_chip.double(ctx, &R);
261
262        assert!(pseudo_binary_encoding[i] <= 1 && pseudo_binary_encoding[i] >= -1);
263        if pseudo_binary_encoding[i] != 0 {
264            let sign_Q = if pseudo_binary_encoding[i] == 1 { Q } else { &neg_Q };
265            f = fp12_multiply_with_line_unequal::<F>(
266                ecc_chip.field_chip(),
267                ctx,
268                &f,
269                (&R, sign_Q),
270                P,
271            );
272            R = ecc_chip.add_unequal(ctx, &R, sign_Q, false);
273        }
274        if i == 0 {
275            break;
276        }
277        i -= 1;
278    }
279
280    // Frobenius coefficient coeff[1][j] = ((9+u)^{(p-1)/6})^j
281    // load coeff[1][2], coeff[1][3]
282    let c2 = FROBENIUS_COEFF_FQ12_C1[1] * FROBENIUS_COEFF_FQ12_C1[1];
283    let c3 = c2 * FROBENIUS_COEFF_FQ12_C1[1];
284    let c2 = ecc_chip.field_chip.load_constant(ctx, c2);
285    let c3 = ecc_chip.field_chip.load_constant(ctx, c3);
286
287    let Q_1 = twisted_frobenius::<F>(ecc_chip, ctx, Q, &c2, &c3);
288    let neg_Q_2 = neg_twisted_frobenius::<F>(ecc_chip, ctx, &Q_1, &c2, &c3);
289    f = fp12_multiply_with_line_unequal::<F>(ecc_chip.field_chip(), ctx, &f, (&R, &Q_1), P);
290    R = ecc_chip.add_unequal(ctx, &R, &Q_1, false);
291    f = fp12_multiply_with_line_unequal::<F>(ecc_chip.field_chip(), ctx, &f, (&R, &neg_Q_2), P);
292
293    f
294}
295
296// let pairs = [(a_i, b_i)], a_i in G_1, b_i in G_2
297// output is Prod_i e'(a_i, b_i), where e'(a_i, b_i) is the output of `miller_loop_BN(b_i, a_i)`
298pub fn multi_miller_loop_BN<F: BigPrimeField>(
299    ecc_chip: &EccChip<F, Fp2Chip<F>>,
300    ctx: &mut Context<F>,
301    pairs: Vec<(&EcPoint<F, FpPoint<F>>, &EcPoint<F, FqPoint<F>>)>,
302    pseudo_binary_encoding: &[i8],
303) -> FqPoint<F> {
304    let mut i = pseudo_binary_encoding.len() - 1;
305    while pseudo_binary_encoding[i] == 0 {
306        i -= 1;
307    }
308    let last_index = i;
309    assert_eq!(pseudo_binary_encoding[last_index], 1);
310
311    let neg_b = pairs.iter().map(|pair| ecc_chip.negate(ctx, pair.1)).collect::<Vec<_>>();
312
313    let fp_chip = ecc_chip.field_chip.fp_chip();
314    // initialize the first line function into Fq12 point
315    let mut f = {
316        let sparse_f =
317            sparse_line_function_equal::<F>(ecc_chip.field_chip(), ctx, pairs[0].1, pairs[0].0);
318        assert_eq!(sparse_f.len(), 6);
319
320        let zero_fp = fp_chip.load_constant(ctx, Fq::zero());
321        let mut f_coeffs = Vec::with_capacity(12);
322        for coeff in &sparse_f {
323            if let Some(fp2_point) = coeff {
324                f_coeffs.push(fp2_point[0].clone());
325            } else {
326                f_coeffs.push(zero_fp.clone());
327            }
328        }
329        for coeff in &sparse_f {
330            if let Some(fp2_point) = coeff {
331                f_coeffs.push(fp2_point[1].clone());
332            } else {
333                f_coeffs.push(zero_fp.clone());
334            }
335        }
336        FieldVector(f_coeffs)
337    };
338    for &(a, b) in pairs.iter().skip(1) {
339        f = fp12_multiply_with_line_equal::<F>(ecc_chip.field_chip(), ctx, &f, b, a);
340    }
341
342    i -= 1;
343    let mut r = pairs.iter().map(|pair| pair.1.clone()).collect::<Vec<_>>();
344    let fp12_chip = Fp12Chip::<F>::new(fp_chip);
345    loop {
346        if i != last_index - 1 {
347            f = fp12_chip.mul(ctx, &f, &f);
348            for (r, &(a, _)) in r.iter().zip(pairs.iter()) {
349                f = fp12_multiply_with_line_equal::<F>(ecc_chip.field_chip(), ctx, &f, r, a);
350            }
351        }
352        for r in r.iter_mut() {
353            *r = ecc_chip.double(ctx, r.clone());
354        }
355
356        assert!(pseudo_binary_encoding[i] <= 1 && pseudo_binary_encoding[i] >= -1);
357        if pseudo_binary_encoding[i] != 0 {
358            for ((r, neg_b), &(a, b)) in r.iter_mut().zip(neg_b.iter()).zip(pairs.iter()) {
359                let sign_b = if pseudo_binary_encoding[i] == 1 { b } else { neg_b };
360                f = fp12_multiply_with_line_unequal::<F>(
361                    ecc_chip.field_chip(),
362                    ctx,
363                    &f,
364                    (r, sign_b),
365                    a,
366                );
367                *r = ecc_chip.add_unequal(ctx, r.clone(), sign_b, false);
368            }
369        }
370        if i == 0 {
371            break;
372        }
373        i -= 1;
374    }
375
376    // Frobenius coefficient coeff[1][j] = ((9+u)^{(p-1)/6})^j
377    // load coeff[1][2], coeff[1][3]
378    let c2 = FROBENIUS_COEFF_FQ12_C1[1] * FROBENIUS_COEFF_FQ12_C1[1];
379    let c3 = c2 * FROBENIUS_COEFF_FQ12_C1[1];
380    let c2 = ecc_chip.field_chip.load_constant(ctx, c2);
381    let c3 = ecc_chip.field_chip.load_constant(ctx, c3);
382
383    // finish multiplying remaining line functions outside the loop
384    for (r, (a, b)) in r.iter_mut().zip(pairs) {
385        let b_1 = twisted_frobenius(ecc_chip, ctx, b, &c2, &c3);
386        let neg_b_2 = neg_twisted_frobenius(ecc_chip, ctx, &b_1, &c2, &c3);
387        f = fp12_multiply_with_line_unequal(ecc_chip.field_chip(), ctx, &f, (r, &b_1), a);
388        *r = ecc_chip.add_unequal(ctx, r.clone(), b_1, false);
389        f = fp12_multiply_with_line_unequal::<F>(ecc_chip.field_chip(), ctx, &f, (r, &neg_b_2), a);
390    }
391    f
392}
393
394// Frobenius coefficient coeff[1][j] = ((9+u)^{(p-1)/6})^j
395// Frob_p( twist(Q) ) = ( (w^2 x)^p, (w^3 y)^p ) = twist( coeff[1][2] * x^p, coeff[1][3] * y^p )
396// Input:
397// - Q = (x, y) point in E(Fp2)
398// - coeff[1][2], coeff[1][3] as assigned cells: this is an optimization to avoid loading new constants
399// Output:
400// - (coeff[1][2] * x^p, coeff[1][3] * y^p) point in E(Fp2)
401pub fn twisted_frobenius<F: BigPrimeField>(
402    ecc_chip: &EccChip<F, Fp2Chip<F>>,
403    ctx: &mut Context<F>,
404    Q: impl Into<EcPoint<F, FqPoint<F>>>,
405    c2: impl Into<FqPoint<F>>,
406    c3: impl Into<FqPoint<F>>,
407) -> EcPoint<F, FqPoint<F>> {
408    let Q = Q.into();
409    let c2 = c2.into();
410    let c3 = c3.into();
411    assert_eq!(c2.0.len(), 2);
412    assert_eq!(c3.0.len(), 2);
413
414    let frob_x = ecc_chip.field_chip.conjugate(ctx, Q.x);
415    let frob_y = ecc_chip.field_chip.conjugate(ctx, Q.y);
416    let out_x = ecc_chip.field_chip.mul(ctx, c2, frob_x);
417    let out_y = ecc_chip.field_chip.mul(ctx, c3, frob_y);
418    EcPoint::new(out_x, out_y)
419}
420
421// Frobenius coefficient coeff[1][j] = ((9+u)^{(p-1)/6})^j
422// -Frob_p( twist(Q) ) = ( (w^2 x)^p, -(w^3 y)^p ) = twist( coeff[1][2] * x^p, coeff[1][3] * -y^p )
423// Input:
424// - Q = (x, y) point in E(Fp2)
425// Output:
426// - (coeff[1][2] * x^p, coeff[1][3] * -y^p) point in E(Fp2)
427pub fn neg_twisted_frobenius<F: BigPrimeField>(
428    ecc_chip: &EccChip<F, Fp2Chip<F>>,
429    ctx: &mut Context<F>,
430    Q: impl Into<EcPoint<F, FqPoint<F>>>,
431    c2: impl Into<FqPoint<F>>,
432    c3: impl Into<FqPoint<F>>,
433) -> EcPoint<F, FqPoint<F>> {
434    let Q = Q.into();
435    let c2 = c2.into();
436    let c3 = c3.into();
437    assert_eq!(c2.0.len(), 2);
438    assert_eq!(c3.0.len(), 2);
439
440    let frob_x = ecc_chip.field_chip.conjugate(ctx, Q.x);
441    let neg_frob_y = ecc_chip.field_chip.neg_conjugate(ctx, Q.y);
442    let out_x = ecc_chip.field_chip.mul(ctx, c2, frob_x);
443    let out_y = ecc_chip.field_chip.mul(ctx, c3, neg_frob_y);
444    EcPoint::new(out_x, out_y)
445}
446
447// To avoid issues with mutably borrowing twice (not allowed in Rust), we only store fp_chip and construct g2_chip and fp12_chip in scope when needed for temporary mutable borrows
448pub struct PairingChip<'chip, F: BigPrimeField> {
449    pub fp_chip: &'chip FpChip<'chip, F>,
450}
451
452impl<'chip, F: BigPrimeField> PairingChip<'chip, F> {
453    pub fn new(fp_chip: &'chip FpChip<F>) -> Self {
454        Self { fp_chip }
455    }
456
457    pub fn load_private_g1_unchecked(
458        &self,
459        ctx: &mut Context<F>,
460        point: G1Affine,
461    ) -> EcPoint<F, FpPoint<F>> {
462        let g1_chip = EccChip::new(self.fp_chip);
463        g1_chip.load_private_unchecked(ctx, (point.x, point.y))
464    }
465
466    pub fn load_private_g2_unchecked(
467        &self,
468        ctx: &mut Context<F>,
469        point: G2Affine,
470    ) -> EcPoint<F, FqPoint<F>> {
471        let fp2_chip = Fp2Chip::new(self.fp_chip);
472        let g2_chip = EccChip::new(&fp2_chip);
473        g2_chip.load_private_unchecked(ctx, (point.x, point.y))
474    }
475
476    pub fn miller_loop(
477        &self,
478        ctx: &mut Context<F>,
479        Q: &EcPoint<F, FqPoint<F>>,
480        P: &EcPoint<F, FpPoint<F>>,
481    ) -> FqPoint<F> {
482        let fp2_chip = Fp2Chip::<F>::new(self.fp_chip);
483        let g2_chip = EccChip::new(&fp2_chip);
484        miller_loop_BN::<F>(
485            &g2_chip,
486            ctx,
487            Q,
488            P,
489            &SIX_U_PLUS_2_NAF, // pseudo binary encoding for BN254
490        )
491    }
492
493    pub fn multi_miller_loop(
494        &self,
495        ctx: &mut Context<F>,
496        pairs: Vec<(&EcPoint<F, FpPoint<F>>, &EcPoint<F, FqPoint<F>>)>,
497    ) -> FqPoint<F> {
498        let fp2_chip = Fp2Chip::<F>::new(self.fp_chip);
499        let g2_chip = EccChip::new(&fp2_chip);
500        multi_miller_loop_BN::<F>(
501            &g2_chip,
502            ctx,
503            pairs,
504            &SIX_U_PLUS_2_NAF, // pseudo binary encoding for BN254
505        )
506    }
507
508    pub fn final_exp(&self, ctx: &mut Context<F>, f: FqPoint<F>) -> FqPoint<F> {
509        let fp12_chip = Fp12Chip::<F>::new(self.fp_chip);
510        fp12_chip.final_exp(ctx, f)
511    }
512
513    // optimal Ate pairing
514    pub fn pairing(
515        &self,
516        ctx: &mut Context<F>,
517        Q: &EcPoint<F, FqPoint<F>>,
518        P: &EcPoint<F, FpPoint<F>>,
519    ) -> FqPoint<F> {
520        let f0 = self.miller_loop(ctx, Q, P);
521        let fp12_chip = Fp12Chip::<F>::new(self.fp_chip);
522        // final_exp implemented in final_exp module
523        fp12_chip.final_exp(ctx, f0)
524    }
525}
halo2_ecc/bn254/pairing.rs

halo2_ecc/bn254/
pairing.rs
