cryptix-bn254 0.1.0

//! The implementation of Optimal-Ate pairing

use cryptix_bigint::digit::Digit;
use cryptix_ecc::CurvePoint;
use cryptix_pairing::Pairing;
use cryptix_field::field::{montgomery::MontgomeryOps, MulIdentity};

use crate::galoisfield::{fp12::Fp12Element, clotomic::Fp12Clotomic};

use super::{e1::BN254Fp, e2::BN254Fp2};

pub struct OptimalAte;

impl OptimalAte {
    const NEGATIVE_T: bool = true;

    /// first easy part
    /// compute f = g^{p^6 - 1}
    fn final_exp_p1(mut g: Fp12Element) -> Fp12Element {
        let ginv = g.mont_inv();
        g.0.1 = -g.0.1;
        g.1.0 = -g.1.0;
        g.2.1 = -g.2.1;
        g.mont_mul(ginv)
    }

    fn final_exp_p2(g: Fp12Element) -> Fp12Element {
        g.map2_frob().mont_mul(g)
    }

    fn final_exp_p3(g: Fp12Clotomic) -> Fp12Element {
        let mut t1 = g.exp_const().clotomic_sqr(); // g_2x
        let t2 = t1.clotomic_sqr();            // g_4x
        let mut t2 = t2.mont_mul(t1);          // g_6x
        let t3 = t2.exp_const();               // g_6x2
        let mut a = t3.clotomic_sqr().exp_const();

        if Self::NEGATIVE_T {
            t1 = t1.clotomic_inv();
            t2 = t2.clotomic_inv();
            a = a.clotomic_inv();
        }

        let a = a.mont_mul(t3).mont_mul(t2);
        let b = t1.clotomic_inv().mont_mul(a);
        let r = a
            .mont_mul(t3).mont_mul(g)
            .mont_mul(b.map_frob())
            .mont_mul(a.map2_frob());

        r.mont_mul(
            g.clotomic_inv().mont_mul(b).map2_frob().map_frob()
        ).into()
    }
}

impl Pairing for OptimalAte {
    type G1 = BN254Fp;
    type G2 = BN254Fp2;

    type GT = Fp12Element;

    fn miller_loop(p: Self::G1, q: Self::G2) -> Self::GT {
        const BITLEN: usize = 64;
        const S: u64 = 0x8300000000000004;

        let mut val;
        let mut f = Fp12Element::ONE.mont_form();
        let mut t = q;

        for i in  (0..BITLEN).rev() {
            f = f.mont_sqr();
            (t, val) = t.dbl_line(p);
            debug_assert!(t.on_curve(), "T not on curve");
            f = val.sparse_mul(f);

            if S.bit(i) {
                debug_assert!(t.on_curve(), "T not on curve");
                debug_assert!(q.on_curve(), "Q not on curve");
                (t, val) = t.mix_add_line(q, p);
                debug_assert!(t.on_curve(), "T not on curve");
                f = val.sparse_mul(f)
            }
        }

        if Self::NEGATIVE_T {
            t = -t;
            f.0.1 = -f.0.1;
            f.1.0 = -f.1.0;
            f.2.1 = -f.2.1;
        }

        let r = q.map_frob();
        debug_assert!(r.on_curve(), "R not on curve");
        (t, val) = t.mix_add_line(r, p);
        debug_assert!(t.on_curve(), "T not on curve");
        f = val.sparse_mul(f);

        let r = -q.map2_frob();
        debug_assert!(r.on_curve(), "R not on curve");
        (t, val) = t.mix_add_line(r, p);
        debug_assert!(t.on_curve(), "T not on curve");
        val.sparse_mul(f)
    }

    fn final_exp(f: Self::GT) -> Self::GT {
        /*
         * # Safety
         * 
         * TODO
         */
        let c = unsafe { 
            Fp12Clotomic::new_unchecked(Self::final_exp_p2(Self::final_exp_p1(f))) 
        };
        Self::final_exp_p3(c)
    }
}


#[cfg(feature = "rand")]
#[test]
fn test_fp12_const_exp() {
    use rand::SeedableRng;
    use cryptix_bigint::bigint;

    use crate::galoisfield::U256;

    const SEED: [u8; 32] = [
        1, 0, 52, 0, 0, 0, 0, 0, 
        1, 0, 10, 0, 22, 32, 0, 0, 
        2, 0, 55, 49, 0, 11, 0, 0, 
        3, 0, 0, 0, 0, 0, 2, 92,
    ];

    let mut rng = rand_chacha::ChaCha8Rng::from_seed(SEED);
    let e = bigint!(U256, "4080000000000001");
    let two = bigint!(U256, "02");
    for _ in 0..20 {
        let a = Fp12Element::rand(&mut rng).mont_form();
        let a = OptimalAte::final_exp_p1(a);
        let a = OptimalAte::final_exp_p2(a);
        let a2s = a.mont_sqr();
        let a2e = a.mont_exp(two).mont_rdc();
        let a2m = a.mont_mul(a);
        let b = a.mont_rdc().mont_exp(e).mont_form();
        let d = a.exp_const();
        let r0 = a.mont_sqr().mont_sqr();
        let a = unsafe { Fp12Clotomic::new_unchecked(a) };
        let r1 = a.clotomic_sqr().clotomic_sqr();
        // println!("r0: {r0:?}");
        // println!("r1: {r1:?}");

        let a2cs: Fp12Element = a.clotomic_sqr().into();
        assert_eq!(a2s, a2m);
        assert_eq!(a2m, a2cs);
        assert_eq!(a2m, a2e);
        let c: Fp12Element = a.exp_const().into();
        // println!("b: {:?}\n", b);
        // println!("d: {:?}\n", d);
        // println!("c: {:?}\n", c);

        assert_eq!(c, d);
        assert_eq!(b, c);
    }
}