openvm_pairing_guest/halo2curves_shims/bls12_381/
final_exp.rs

1use alloc::vec::Vec;
2
3use halo2curves_axiom::bls12_381::{Fq, Fq12, Fq2};
4use lazy_static::lazy_static;
5use num_bigint::BigUint;
6use openvm_ecc_guest::{algebra::Field, AffinePoint};
7
8use super::{Bls12_381, FINAL_EXP_FACTOR, LAMBDA, POLY_FACTOR};
9use crate::{
10    halo2curves_shims::naf::biguint_to_naf,
11    pairing::{FinalExp, MultiMillerLoop},
12};
13
14lazy_static! {
15    static ref FINAL_EXP_FACTOR_NAF: Vec<i8> = biguint_to_naf(&FINAL_EXP_FACTOR);
16    static ref POLY_FACTOR_NAF: Vec<i8> = biguint_to_naf(&POLY_FACTOR);
17    static ref TWENTY_SEVEN_NAF: Vec<i8> = biguint_to_naf(&BigUint::from(27u32));
18    static ref TEN_NAF: Vec<i8> = biguint_to_naf(&BigUint::from(10u32));
19    static ref FINAL_EXP_TIMES_27: BigUint = FINAL_EXP_FACTOR.clone() * BigUint::from(27u32);
20    static ref FINAL_EXP_TIMES_27_MOD_POLY: BigUint = {
21        let exp_inv = FINAL_EXP_TIMES_27.modinv(&POLY_FACTOR.clone()).unwrap();
22        exp_inv % POLY_FACTOR.clone()
23    };
24    static ref FINAL_EXP_TIMES_27_MOD_POLY_NAF: Vec<i8> =
25        biguint_to_naf(&FINAL_EXP_TIMES_27_MOD_POLY);
26    static ref LAMBDA_INV_FINAL_EXP: BigUint =
27        LAMBDA.clone().modinv(&FINAL_EXP_FACTOR.clone()).unwrap();
28    static ref LAMBDA_INV_FINAL_EXP_NAF: Vec<i8> = biguint_to_naf(&LAMBDA_INV_FINAL_EXP);
29}
30
31// The paper only describes the implementation for Bn254, so we use the gnark implementation for
32// Bls12_381.
33#[allow(non_snake_case)]
34impl FinalExp for Bls12_381 {
35    type Fp = Fq;
36    type Fp2 = Fq2;
37    type Fp12 = Fq12;
38
39    // Adapted from the gnark implementation:
40    // https://github.com/Consensys/gnark/blob/af754dd1c47a92be375930ae1abfbd134c5310d8/std/algebra/emulated/fields_bls12381/e12_pairing.go#L394C1-L395C1
41    fn assert_final_exp_is_one(
42        f: &Self::Fp12,
43        P: &[AffinePoint<Self::Fp>],
44        Q: &[AffinePoint<Self::Fp2>],
45    ) {
46        let (c, s) = Self::final_exp_hint(f);
47
48        // The gnark implementation checks that f * s = c^{q - x} where x is the curve seed.
49        // We check an equivalent condition: f * c^x * c^-q * s = 1.
50        // This is because we can compute f * c^x by embedding the c^x computation in the miller
51        // loop.
52
53        // Since the Bls12_381 curve has a negative seed, the miller loop for Bls12_381 is computed
54        // as f_{Miller,x,Q}(P) = conjugate( f_{Miller,-x,Q}(P) * c^{-x} ).
55        // We will pass in the conjugate inverse of c into the miller loop so that we compute
56        // fc = f_{Miller,x,Q}(P)
57        //    = conjugate( f_{Miller,-x,Q}(P) * c'^{-x} )  (where c' is the conjugate inverse of c)
58        //    = f_{Miller,x,Q}(P) * c^x
59        let c_conj_inv = c.conjugate().invert().unwrap();
60        let c_inv = c.invert().unwrap();
61        let c_q_inv = c_inv.frobenius_map();
62        let fc = Self::multi_miller_loop_embedded_exp(P, Q, Some(c_conj_inv));
63
64        assert_eq!(fc * c_q_inv * s, Fq12::ONE);
65    }
66
67    // Adapted from the gnark implementation:
68    // https://github.com/Consensys/gnark/blob/af754dd1c47a92be375930ae1abfbd134c5310d8/std/algebra/emulated/fields_bls12381/hints.go#L273
69    // returns c (residueWitness) and s (scalingFactor)
70    // The Gnark implementation is based on https://eprint.iacr.org/2024/640.pdf
71    fn final_exp_hint(f: &Self::Fp12) -> (Self::Fp12, Self::Fp12) {
72        let f_final_exp = exp_naf(f, true, &FINAL_EXP_FACTOR_NAF);
73        let root = exp_naf(&f_final_exp, true, &TWENTY_SEVEN_NAF);
74
75        // 1. get p-th root inverse
76        let root_pth_inv = if root == Fq12::ONE {
77            Fq12::ONE
78        } else {
79            exp_naf(&root, false, &FINAL_EXP_TIMES_27_MOD_POLY_NAF)
80        };
81
82        let root = exp_naf(&f_final_exp, true, &POLY_FACTOR_NAF);
83        // 2. get 27th root inverse
84        let root_27th_inv = if exp_naf(&root, true, &TWENTY_SEVEN_NAF) == Fq12::ONE {
85            exp_naf(&root, false, &TEN_NAF)
86        } else {
87            Fq12::ONE
88        };
89
90        // 2.3. shift the Miller loop result so that millerLoop * scalingFactor
91        // is of order finalExpFactor
92        let s = root_pth_inv * root_27th_inv;
93        let f = f * s;
94
95        // 3. get the witness residue
96        // lambda = q - u, the optimal exponent
97        let c = exp_naf(&f, true, &LAMBDA_INV_FINAL_EXP_NAF);
98
99        (c, s)
100    }
101}
102
103/// Exponentiates a field element using a signed digit representation (e.g. NAF).
104/// `digits_naf` is expected to be in LSB-first order with entries in {-1, 0, 1}.
105fn exp_naf(base: &Fq12, is_positive: bool, digits_naf: &[i8]) -> Fq12 {
106    #[cfg(feature = "blstrs")]
107    {
108        exp_naf_blstrs(base, is_positive, digits_naf)
109    }
110    #[cfg(not(feature = "blstrs"))]
111    {
112        exp_naf_basic(base, is_positive, digits_naf)
113    }
114}
115
116#[cfg(not(feature = "blstrs"))]
117fn exp_naf_basic(base: &Fq12, is_positive: bool, digits_naf: &[i8]) -> Fq12 {
118    if digits_naf.is_empty() {
119        return Fq12::ONE;
120    }
121
122    let base = if !is_positive {
123        base.invert().unwrap_or(Fq12::ONE)
124    } else {
125        *base
126    };
127
128    let base_inv = if digits_naf.contains(&-1) {
129        Some(base.invert().unwrap_or(Fq12::ONE))
130    } else {
131        None
132    };
133
134    let mut res = Fq12::ONE;
135    for &digit in digits_naf.iter().rev() {
136        res = res.square();
137        if digit == 1 {
138            res *= base;
139        } else if digit == -1 {
140            res *= base_inv
141                .as_ref()
142                .expect("negative digit requires available inverse");
143        }
144    }
145
146    res
147}
148
149#[cfg(feature = "blstrs")]
150fn exp_naf_blstrs(base: &Fq12, is_positive: bool, digits_naf: &[i8]) -> Fq12 {
151    use halo2curves_axiom::ff::Field;
152
153    if digits_naf.is_empty() {
154        return <Fq12 as halo2curves_axiom::ff::Field>::ONE;
155    }
156
157    // Transmute to blstrs for computation
158    let base_blstrs = unsafe { core::mem::transmute::<Fq12, blstrs::Fp12>(*base) };
159
160    let base_blstrs = if !is_positive {
161        base_blstrs.invert().unwrap_or(blstrs::Fp12::ONE)
162    } else {
163        base_blstrs
164    };
165
166    let base_inv_blstrs = if digits_naf.contains(&-1) {
167        Some(base_blstrs.invert().unwrap_or(blstrs::Fp12::ONE))
168    } else {
169        None
170    };
171
172    let mut res_blstrs = blstrs::Fp12::ONE;
173    for &digit in digits_naf.iter().rev() {
174        res_blstrs = res_blstrs.square();
175        if digit == 1 {
176            res_blstrs *= base_blstrs;
177        } else if digit == -1 {
178            res_blstrs *= base_inv_blstrs
179                .as_ref()
180                .expect("negative digit requires available inverse");
181        }
182    }
183
184    // Transmute back to Fq12
185    unsafe { core::mem::transmute::<blstrs::Fp12, Fq12>(res_blstrs) }
186}
openvm_pairing_guest/halo2curves_shims/bls12_381/final_exp.rs

openvm_pairing_guest/halo2curves_shims/bls12_381/
final_exp.rs
