loopring_sign 0.1.4

/*
This module implements the extended twisted edwards and extended affine coordinates
described in the paper "Twisted Edwards Curves Revisited":

 - https://iacr.org/archive/asiacrypt2008/53500329/53500329.pdf
   Huseyin Hisil, Kenneth Koon-Ho Wong, Gary Carter, and Ed Dawson

        Information Security Institute,
        Queensland University of Technology, QLD, 4000, Australia
        {h.hisil, kk.wong, g.carter, e.dawson}@qut.edu.au

By using the extended coordinate system we can avoid expensive modular exponentiation
calls, for example - a scalar multiplication call (or multiple...) may perform only
one 3d->2d projection at the point where affine coordinates are necessary, and every
intermediate uses a much faster form.

# XXX: none of these functions are constant time, they should not be used interactively!
*/
// ax^2 + y^2 = 1 + dx^2y^2

use super::field::FQ;
use crate::poseidon::field::SNARK_SCALAR_FIELD;
use num_bigint::BigInt;
use num_traits::{One, Zero};
use std::{
    ops::{Add, Div, Mul},
    str::FromStr,
};

lazy_static! {
    pub static ref JUBJUB_Q: BigInt = SNARK_SCALAR_FIELD.clone();
    pub static ref JUBJUB_E: BigInt = BigInt::from_str(
        "21888242871839275222246405745257275088614511777268538073601725287587578984328"
    )
    .unwrap();
    pub static ref JUBJUB_C: BigInt = BigInt::from_str("8").unwrap();

    //L is the order of the prime-order subgroup generated by the base point
    pub static ref JUBJUB_L: BigInt = JUBJUB_E.clone().div(JUBJUB_C.clone()); // L*B = 0, and (2^C)*L == #E
    pub static ref JUBJUB_A: BigInt = BigInt::from_str("168700").unwrap();
    pub static ref JUBJUB_D: BigInt = BigInt::from_str("168696").unwrap();
}

pub struct Point {
    x: FQ,
    y: FQ,
}

impl Point {
    pub fn new(x: FQ, y: FQ) -> Self {
        Point { x, y }
    }
    pub fn x(&self) -> &FQ {
        &self.x
    }

    pub fn y(&self) -> &FQ {
        &self.y
    }

    // These numbers has beeen taken from https://eips.ethereum.org/EIPS/eip-2494
    pub fn generate() -> Self {
        let x = BigInt::from_str(
            "16540640123574156134436876038791482806971768689494387082833631921987005038935",
        )
        .unwrap();
        let y = BigInt::from_str(
            "20819045374670962167435360035096875258406992893633759881276124905556507972311",
        )
        .unwrap();
        Point {
            x: FQ::new(x),
            y: FQ::new(y),
        }
    }

    pub fn infinity() -> Self {
        Point {
            x: FQ::new(BigInt::zero()),
            y: FQ::new(BigInt::one()),
        }
    }
    pub fn as_scalar(&self) -> Vec<BigInt> {
        vec![self.x.n().clone(), self.y.n().clone()]
    }

    // Add Implementation for calculation in babyjub
    // https://eips.ethereum.org/EIPS/eip-2494
    // λ = d * x1 * x2 * y1 * y2,
    // x3 = (x1y2 + y1 * x2)/(1 + λ)
    // y3 = (y1 * y2 − a * x1 * x2)/(1 − λ).

    fn add_points(x1: &FQ, y1: &FQ, x2: &FQ, y2: &FQ) -> Point {
        let d = FQ::new(JUBJUB_D.clone());
        let a = FQ::new(JUBJUB_A.clone());

        let lambda = d * x1 * x2 * y1 * y2;
        let x3 = (x1 * y2 + y1 * x2) / (FQ::one() + &lambda);
        let y3 = (y1 * y2 - a * x1 * x2) / (FQ::one() - &lambda);

        Point { x: x3, y: y3 }
    }
    fn is_at_inifinity(&self) -> bool {
        let zero = BigInt::from_str("0").unwrap();
        self.x.n() == &zero && self.y.n() == &zero
    }

    // Add eliptic curve multiplication using the double-and-add method:
    // 1. https://en.wikipedia.org/wiki/Elliptic_curve_point_multiplication
    // 2. https://iden3-docs.readthedocs.io/en/latest/_downloads/33717d75ab84e11313cc0d8a090b636f/Baby-Jubjub.pdf

    fn scalar_mul(point: &Point, mut scalar: BigInt) -> Point {
        let mut p = Point::new(point.x.clone(), point.y.clone());
        let mut a = Self::infinity();
        let mut i = 0;

        while scalar != BigInt::zero() {
            let bitwise_and = &scalar & BigInt::from(1);
            if bitwise_and != BigInt::from(0) {
                a = a + &p;
            }
            let copy_p1 = p.clone();
            let copy_p2 = p.clone();
            p = copy_p1 + copy_p2;
            scalar = scalar.div(BigInt::from(2));
            i = i + 1;
        }
        a
    }
}

impl Add for Point {
    type Output = Self;
    fn add(self, rhs: Point) -> Self::Output {
        if self.is_at_inifinity() {
            return rhs;
        }
        Point::add_points(&self.x, &self.y, &rhs.x, &rhs.y)
    }
}

impl<'a> Add<&'a Point> for Point {
    type Output = Self;
    fn add(self, rhs: &'a Point) -> Self::Output {
        if self.is_at_inifinity() {
            return rhs.clone();
        }
        Point::add_points(&self.x, &self.y, &rhs.x, &rhs.y)
    }
}

impl Mul<BigInt> for Point {
    type Output = Point;

    fn mul(self, scalar: BigInt) -> Self::Output {
        Point::scalar_mul(&self, scalar)
    }
}
impl<'a> Mul<&'a BigInt> for Point {
    type Output = Point;

    fn mul(self, scalar: &'a BigInt) -> Self::Output {
        Point::scalar_mul(&self, scalar.clone())
    }
}

impl<'a, 'b> Mul<&'b BigInt> for &'a Point {
    type Output = Point;

    fn mul(self, scalar: &'b BigInt) -> Self::Output {
        Point::scalar_mul(self, scalar.clone())
    }
}

impl Mul<Point> for BigInt {
    type Output = Point;

    fn mul(self, rhs: Point) -> Self::Output {
        Point::scalar_mul(&rhs, self)
    }
}

impl Clone for Point {
    fn clone(&self) -> Self {
        Self {
            x: self.x.clone(),
            y: self.y.clone(),
        }
    }

    fn clone_from(&mut self, source: &Self) {
        *self = source.clone()
    }
}

#[cfg(test)]
mod tests {
    use num_traits::Zero;

    use super::*;

    #[test]
    fn point_add_test_1() {
        let point = Point::new(
            FQ::new(
                BigInt::from_str(
                    "5925710879559963920674585068280151559572021649049974518737186312396312983287",
                )
                .unwrap(),
            ),
            FQ::new(
                BigInt::from_str(
                    "16975020951829843291561856284829257584634286376639034318405002894754175986822",
                )
                .unwrap(),
            ),
        );
        let other = Point::new(
            FQ::new(
                BigInt::from_str(
                    "5925710879559963920674585068280151559572021649049974518737186312396312983287",
                )
                .unwrap(),
            ),
            FQ::new(
                BigInt::from_str(
                    "16975020951829843291561856284829257584634286376639034318405002894754175986822",
                )
                .unwrap(),
            ),
        );

        let sum = point.add(other);
        assert_eq!(
            *sum.x.n(),
            BigInt::from_str(
                "3921821752680400551661691533275335336907961697969280331905459386565873550491",
            )
            .unwrap()
        );
        assert_eq!(
            *sum.x.m(),
            BigInt::from_str(
                "21888242871839275222246405745257275088548364400416034343698204186575808495617",
            )
            .unwrap()
        );
        assert_eq!(
            *sum.y.n(),
            BigInt::from_str(
                "8522068897570808837785568881356377871354274006792075192589502922612862896342",
            )
            .unwrap()
        );
        assert_eq!(
            *sum.y.m(),
            BigInt::from_str(
                "21888242871839275222246405745257275088548364400416034343698204186575808495617",
            )
            .unwrap()
        );
    }

    #[test]
    fn point_add_test_2() {
        let point = Point::new(
            FQ::new(
                BigInt::from_str(
                    "10975113445185536695224737904225227344281568447400334915125839333792816477396",
                )
                .unwrap(),
            ),
            FQ::new(
                BigInt::from_str(
                    "18445435810976842694581549336952093637971779711294581156054437925992025486446",
                )
                .unwrap(),
            ),
        );
        let other = Point::new(
            FQ::new(
                BigInt::from_str(
                    "5925710879559963920674585068280151559572021649049974518737186312396312983287",
                )
                .unwrap(),
            ),
            FQ::new(
                BigInt::from_str(
                    "16975020951829843291561856284829257584634286376639034318405002894754175986822",
                )
                .unwrap(),
            ),
        );

        let sum = point.add(other);
        assert_eq!(
            *sum.x.n(),
            BigInt::from_str(
                "4991609103248925747358645194965349262579784734809679007552644294476920671344",
            )
            .unwrap()
        );
        assert_eq!(
            *sum.x.m(),
            BigInt::from_str(
                "21888242871839275222246405745257275088548364400416034343698204186575808495617",
            )
            .unwrap()
        );
        assert_eq!(
            *sum.y.n(),
            BigInt::from_str(
                "423391641476660815714427268720766993055332927752794962916609674122318189741",
            )
            .unwrap()
        );
        assert_eq!(
            *sum.y.m(),
            BigInt::from_str(
                "21888242871839275222246405745257275088548364400416034343698204186575808495617",
            )
            .unwrap()
        );
    }
    #[test]
    fn test_divide_1() {
        let scalar = BigInt::from(1);
        let result = scalar.div(2);
        assert_eq!(BigInt::zero(), result);
    }

    #[test]
    fn test_divide_2() {
        let scalar = BigInt::from(2);
        let result = scalar.div(2);
        assert_eq!(BigInt::from(1), result);
    }

    #[test]
    fn test_bitwise_and_1() {
        let scalar = BigInt::from(1);
        let result = scalar & BigInt::from(1);
        assert_eq!(result, BigInt::from(1))
    }
    #[test]
    fn point_mul_1() {
        let b = Point::new(
            FQ::new(
                BigInt::from_str(
                    "16540640123574156134436876038791482806971768689494387082833631921987005038935",
                )
                .unwrap(),
            ),
            FQ::new(
                BigInt::from_str(
                    "20819045374670962167435360035096875258406992893633759881276124905556507972311",
                )
                .unwrap(),
            ),
        );
        let k = BigInt::from(1);
        let a = &b * &k;
        assert_eq!(
            *a.x.n(),
            BigInt::from_str(
                "16540640123574156134436876038791482806971768689494387082833631921987005038935"
            )
            .unwrap()
        );
        assert_eq!(
            *a.x.m(),
            BigInt::from_str(
                "21888242871839275222246405745257275088548364400416034343698204186575808495617"
            )
            .unwrap()
        );
        assert_eq!(
            *a.y.n(),
            BigInt::from_str(
                "20819045374670962167435360035096875258406992893633759881276124905556507972311"
            )
            .unwrap()
        );
        assert_eq!(
            *a.y.m(),
            BigInt::from_str(
                "21888242871839275222246405745257275088548364400416034343698204186575808495617"
            )
            .unwrap()
        );
    }

    #[test]
    fn point_mul_2() {
        let b = Point::new(
            FQ::new(
                BigInt::from_str(
                    "16540640123574156134436876038791482806971768689494387082833631921987005038935",
                )
                .unwrap(),
            ),
            FQ::new(
                BigInt::from_str(
                    "20819045374670962167435360035096875258406992893633759881276124905556507972311",
                )
                .unwrap(),
            ),
        );
        let k = BigInt::from(2);
        let a = &b * &k;
        assert_eq!(
            *a.x.n(),
            BigInt::from_str(
                "17324563846726889236817837922625232543153115346355010501047597319863650987830"
            )
            .unwrap()
        );
        assert_eq!(
            *a.x.m(),
            BigInt::from_str(
                "21888242871839275222246405745257275088548364400416034343698204186575808495617"
            )
            .unwrap()
        );
        assert_eq!(
            *a.y.n(),
            BigInt::from_str(
                "20022170825455209233733649024450576091402881793145646502279487074566492066831"
            )
            .unwrap()
        );
        assert_eq!(
            *a.y.m(),
            BigInt::from_str(
                "21888242871839275222246405745257275088548364400416034343698204186575808495617"
            )
            .unwrap()
        );
    }
    #[test]
    fn point_mul_3() {
        let x = FQ::new(
            BigInt::from_str(
                "16540640123574156134436876038791482806971768689494387082833631921987005038935",
            )
            .unwrap(),
        );
        let y = FQ::new(
            BigInt::from_str(
                "20819045374670962167435360035096875258406992893633759881276124905556507972311",
            )
            .unwrap(),
        );
        let b = Point::new(x, y);
        let k = BigInt::from_str(
            "456425617452149303537516185998917840598824274191970480768523181450944242406",
        )
        .unwrap();
        let a = b * k;

        assert_eq!(
            *a.x.n(),
            BigInt::from_str(
                "4991609103248925747358645194965349262579784734809679007552644294476920671344"
            )
            .unwrap()
        );
        assert_eq!(
            *a.x.m(),
            BigInt::from_str(
                "21888242871839275222246405745257275088548364400416034343698204186575808495617"
            )
            .unwrap()
        );
        assert_eq!(
            *a.y.n(),
            BigInt::from_str(
                "423391641476660815714427268720766993055332927752794962916609674122318189741"
            )
            .unwrap()
        );
        assert_eq!(
            *a.y.m(),
            BigInt::from_str(
                "21888242871839275222246405745257275088548364400416034343698204186575808495617"
            )
            .unwrap()
        );
    }
}