openvm_pairing_guest/halo2curves_shims/bn254/
final_exp.rs

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

openvm_pairing_guest/halo2curves_shims/bn254/
final_exp.rs
