openvm_pairing_guest/halo2curves_shims/bn254/
final_exp.rs

1use halo2curves_axiom::{
2    bn256::{Fq, Fq12, Fq2},
3    ff::Field,
4};
5use openvm_ecc_guest::{algebra::field::FieldExtension, AffinePoint};
6
7use super::{Bn254, EXP1, EXP2, M_INV, R_INV, U27_COEFF_0, U27_COEFF_1};
8use crate::pairing::{FinalExp, MultiMillerLoop};
9
10#[allow(non_snake_case)]
11impl FinalExp for Bn254 {
12    type Fp = Fq;
13    type Fp2 = Fq2;
14    type Fp12 = Fq12;
15
16    fn assert_final_exp_is_one(
17        f: &Self::Fp12,
18        P: &[AffinePoint<Self::Fp>],
19        Q: &[AffinePoint<Self::Fp2>],
20    ) {
21        let (c, u) = Self::final_exp_hint(f);
22        let c_inv = c.invert().unwrap();
23
24        // We follow Theorem 3 of https://eprint.iacr.org/2024/640.pdf to check that the pairing equals 1
25        // By the theorem, it suffices to provide c and u such that f * u == c^λ.
26        // Since λ = 6x + 2 + q^3 - q^2 + q, we will check the equivalent condition:
27        // f * c^-{6x + 2} * u * c^-{q^3 - q^2 + q} == 1
28        // This is because we can compute f * c^-{6x+2} by embedding the c^-{6x+2} computation in
29        // the miller loop.
30
31        // c_mul = c^-{q^3 - q^2 + q}
32        let c_q3_inv = FieldExtension::frobenius_map(&c_inv, 3);
33        let c_q2 = FieldExtension::frobenius_map(&c, 2);
34        let c_q_inv = FieldExtension::frobenius_map(&c_inv, 1);
35        let c_mul = c_q3_inv * c_q2 * c_q_inv;
36
37        // Pass c inverse into the miller loop so that we compute fc == f * c^-{6x + 2}
38        let fc = Self::multi_miller_loop_embedded_exp(P, Q, Some(c_inv));
39
40        assert_eq!(fc * c_mul * u, Fq12::ONE);
41    }
42
43    // Adapted from the Gnark implementation:
44    // https://github.com/Consensys/gnark/blob/af754dd1c47a92be375930ae1abfbd134c5310d8/std/algebra/emulated/sw_bn254/hints.go#L23
45    // returns c (residueWitness) and u (cubicNonResiduePower)
46    // The Gnark implementation is based on https://eprint.iacr.org/2024/640.pdf
47    fn final_exp_hint(f: &Self::Fp12) -> (Self::Fp12, Self::Fp12) {
48        // Residue witness
49        let mut c;
50        // Cubic nonresidue power
51        let u;
52
53        // get the 27th root of unity
54        let u0 = U27_COEFF_0.to_u64_digits();
55        let u1 = U27_COEFF_1.to_u64_digits();
56        let u_coeffs = Fq2::from_coeffs([
57            Fq::from_raw([u0[0], u0[1], u0[2], u0[3]]),
58            Fq::from_raw([u1[0], u1[1], u1[2], u1[3]]),
59        ]);
60        let unity_root_27 = Fq12::from_coeffs([
61            Fq2::ZERO,
62            Fq2::ZERO,
63            u_coeffs,
64            Fq2::ZERO,
65            Fq2::ZERO,
66            Fq2::ZERO,
67        ]);
68        debug_assert_eq!(unity_root_27.pow([27]), Fq12::one());
69
70        if f.pow(EXP1.to_u64_digits()) == Fq12::ONE {
71            c = *f;
72            u = Fq12::ONE;
73        } else {
74            let f_mul_unity_root_27 = f * unity_root_27;
75            if f_mul_unity_root_27.pow(EXP1.to_u64_digits()) == Fq12::ONE {
76                c = f_mul_unity_root_27;
77                u = unity_root_27;
78            } else {
79                c = f_mul_unity_root_27 * unity_root_27;
80                u = unity_root_27.square();
81            }
82        }
83
84        // 1. Compute r-th root and exponentiate to rInv where
85        //   rInv = 1/r mod (p^12-1)/r
86        c = c.pow(R_INV.to_u64_digits());
87
88        // 2. Compute m-th root where
89        //   m = (6x + 2 + q^3 - q^2 +q)/3r
90        // Exponentiate to mInv where
91        //   mInv = 1/m mod p^12-1
92        c = c.pow(M_INV.to_u64_digits());
93
94        // 3. Compute cube root
95        // since gcd(3, (p^12-1)/r) != 1, we use a modified Tonelli-Shanks algorithm
96        // see Alg.4 of https://eprint.iacr.org/2024/640.pdf
97        // Typo in the paper: p^k-1 = 3^n * s instead of p-1 = 3^r * s
98        // where k=12 and n=3 here and exp2 = (s+1)/3
99        let mut x = c.pow(EXP2.to_u64_digits());
100
101        // 3^t is ord(x^3 / residueWitness)
102        let c_inv = c.invert().unwrap();
103        let mut x3 = x.square() * x * c_inv;
104        let mut t = 0;
105        let mut tmp = x3.square();
106
107        // Modified Tonelli-Shanks algorithm for computing the cube root
108        fn tonelli_shanks_loop(x3: &mut Fq12, tmp: &mut Fq12, t: &mut i32) {
109            while *x3 != Fq12::ONE {
110                *tmp = (*x3).square();
111                *x3 *= *tmp;
112                *t += 1;
113            }
114        }
115
116        tonelli_shanks_loop(&mut x3, &mut tmp, &mut t);
117
118        while t != 0 {
119            tmp = unity_root_27.pow(EXP2.to_u64_digits());
120            x *= tmp;
121
122            x3 = x.square() * x * c_inv;
123            t = 0;
124            tonelli_shanks_loop(&mut x3, &mut tmp, &mut t);
125        }
126
127        debug_assert_eq!(c, x * x * x);
128        // x is the cube root of the residue witness c
129        c = x;
130
131        (c, u)
132    }
133}
openvm_pairing_guest/halo2curves_shims/bn254/final_exp.rs

openvm_pairing_guest/halo2curves_shims/bn254/
final_exp.rs
