wip: eddsa_poseidon_benchmarknoir-benchmarks

2 files changed, 341 insertions, 0 deletions

diff --git a/guests/eddsa_poseidon/src/ec.rs b/guests/eddsa_poseidon/src/ec.rs
new file mode 100644
index 0000000..3af1afa
--- /dev/null
+++ b/guests/eddsa_poseidon/src/ec.rs
@@ -0,0 +1,276 @@
+// Twisted Edwards curves
+
+use num::BigInt;
+pub type Field = BigInt;
+
+// TEPoint in extended twisted Edwards coordinates
+pub struct GroupPoint {
+    pub x: Field,
+    pub y: Field,
+    pub t: Field,
+    pub z: Field,
+}
+
+// TECurve specification
+pub struct GroupCurve { // Twisted Edwards curve
+    // Coefficients in defining equation a(x^2 + y^2)z^2 = z^4 + dx^2y^2
+    pub a: Field,
+    pub d: Field,
+    // Generator as point in projective coordinates
+    pub gen: GroupPoint,
+}
+
+impl GroupPoint {
+    // GroupPoint constructor
+    pub fn new(x: Field, y: Field, t: Field, z: Field) -> Self {
+        Self { x, y, t, z }
+    }
+
+    // Check if zero
+    pub fn is_zero(self) -> bool {
+        let Self { x, y, t, z } = self;
+        (&x == &BigInt::ZERO) & (&y == &z) & (&y != &BigInt::ZERO) & (&t == &BigInt::ZERO)
+    }
+
+    // Additive identity
+    pub fn zero() -> Self {
+        GroupPoint::new(0.into(), 1.into(), 0.into(), 1.into())
+    }
+
+    // Conversion to affine coordinates
+    pub fn into_affine(self) -> TEPoint {
+        let Self { x, y, t: _t, z } = self;
+
+        TEPoint::new(&x / &z, &y / &z)
+    }
+}
+
+impl PartialEq for GroupPoint {
+    fn eq(&self, p: &Self) -> bool {
+        let Self { x: x1, y: y1, t: _t1, z: z1 } = self;
+        let Self { x: x2, y: y2, t: _t2, z: z2 } = p;
+
+        (x1 * z2 == x2 * z1) & (y1 * z2 == y2 * z1)
+    }
+}
+
+impl GroupCurve {
+    // GroupCurve constructor
+    pub fn new(a: Field, d: Field, gen: GroupPoint) -> GroupCurve {
+        // Check curve coefficients
+        assert!(&a * &d * (&a - &d) != 0.into());
+
+        let curve = GroupCurve { a, d, gen };
+
+        // gen should be on the curve
+        assert!(curve.contains(curve.gen.clone()));
+
+        curve
+    }
+
+    // Conversion to affine coordinates
+    pub fn into_affine(self) -> TECurve {
+        let GroupCurve { a, d, gen } = self;
+
+        TECurve { a, d, gen: gen.into_affine() }
+    }
+
+    // Point addition
+    pub fn add(self, p1: GroupPoint, p2: GroupPoint) -> GroupPoint {
+        let GroupPoint { x: x1, y: y1, t: t1, z: z1 } = p1;
+        let GroupPoint { x: x2, y: y2, t: t2, z: z2 } = p2;
+
+        let a = &x1 * &x2;
+        let b = &y1 * &y2;
+        let c = self.d * &t1 * &t2;
+        let d = &z1 * &z2;
+        let e = (&x1 + &y1) * (&x2 + &y2) - &a - &b;
+        let f = &d - &c;
+        let g = &d + &c;
+        let h = b - self.a * a;
+
+        let x = &e * &f;
+        let y = &g * &h;
+        let t = &e * &h;
+        let z = &f * &g;
+
+        GroupPoint::new(x, y, t, z)
+    }
+
+    // Scalar multiplication with scalar represented by a bit array (little-endian convention).
+    // If k is the natural number represented by `bits`, then this computes p + ... + p k times.
+    pub fn bit_mul<const N: usize>(self, bits: [bool; N], p: GroupPoint) -> GroupPoint {
+        let mut out = GroupPoint::zero();
+
+        for i in 0..N {
+            out = self.add(
+                self.add(out, out),
+                if bits[N - i - 1] == false {
+                    GroupPoint::zero()
+                } else {
+                    p
+                },
+            );
+        }
+
+        out
+    }
+
+    // Scalar multiplication (p + ... + p n times)
+    pub fn mul(self, n: Field, p: GroupPoint) -> GroupPoint {
+        // TODO: temporary workaround until issue 1354 is solved
+        let mut n_as_bits: [bool; 254] = [false; 254];
+        let tmp: [bool; 254] = n.to_le_bits();
+        for i in 0..254 {
+            n_as_bits[i] = tmp[i];
+        }
+
+        self.bit_mul(n_as_bits, p)
+    }
+
+    // Membership check
+    pub fn contains(self, p: GroupPoint) -> bool {
+        let GroupPoint { x, y, t, z } = p;
+
+        (z != BigInt::ZERO)
+            & (z * t == x * y)
+            & (z * z * (self.a * x * x + y * y) == z * z * z * z + self.d * x * x * y * y)
+    }
+}
+
+// TEPoint in Cartesian coordinates
+#[derive(Clone)]
+pub struct TEPoint {
+    pub x: Field,
+    pub y: Field,
+}
+
+// TECurve specification
+#[derive(Clone)]
+pub struct TECurve { // Twisted Edwards curve
+    // Coefficients in defining equation ax^2 + y^2 = 1 + dx^2y^2
+    pub a: Field,
+    pub d: Field,
+    // Generator as point in Cartesian coordinates
+    pub gen: TEPoint,
+}
+
+impl TEPoint {
+    // TEPoint constructor
+    pub fn new(x: Field, y: Field) -> Self {
+        Self { x, y }
+    }
+
+    // Check if zero
+    pub fn is_zero(self) -> bool {
+        self.eq(&TEPoint::zero())
+    }
+
+    // Conversion to TECurveGroup coordinates
+    pub fn into_group(self) -> GroupPoint {
+        let Self { x, y } = self;
+
+        GroupPoint::new(x.clone(), y.clone(), &x * y, 1.into())
+    }
+
+    // Additive identity
+    pub fn zero() -> Self {
+        TEPoint::new(0.into(), 1.into())
+    }
+}
+
+impl PartialEq for TEPoint {
+    fn eq(&self, p: &Self) -> bool {
+        let Self { x: x1, y: y1 } = self;
+        let Self { x: x2, y: y2 } = p;
+
+        (x1 == x2) & (y1 == y2)
+    }
+}
+
+impl TECurve {
+    // TECurve constructor
+    pub fn new(a: Field, d: Field, gen: TEPoint) -> TECurve {
+        // Check curve coefficients
+        assert!(&a * &d * (&a - &d) != 0.into());
+
+        let curve = TECurve { a, d, gen };
+
+        // gen should be on the curve
+        assert!(curve.contains(curve.gen.clone()));
+
+        curve
+    }
+
+    // Conversion to TECurveGroup coordinates
+    pub fn into_group(self) -> GroupCurve {
+        let TECurve { a, d, gen } = self;
+
+        GroupCurve { a, d, gen: gen.into_group() }
+    }
+
+    // Membership check
+    pub fn contains(self, p: TEPoint) -> bool {
+        let TEPoint { x, y } = p;
+        self.a * &x * &x + &y * &y == 1 + self.d * &x * &x * &y * &y
+    }
+
+    // TEPoint addition, implemented in terms of mixed addition for reasons of efficiency
+    pub fn add(self, p1: TEPoint, p2: TEPoint) -> TEPoint {
+        self.mixed_add(p1, p2.into_group()).into_affine()
+    }
+
+    // Mixed point addition, i.e. first argument in affine, second in TECurveGroup coordinates.
+    pub fn mixed_add(self, p1: TEPoint, p2: GroupPoint) -> GroupPoint {
+        let TEPoint { x: x1, y: y1 } = p1;
+        let GroupPoint { x: x2, y: y2, t: t2, z: z2 } = p2;
+
+        let a = &x1 * &x2;
+        let b = &y1 * &y2;
+        let c = self.d * &x1 * &y1 * &t2;
+        let e = (x1 + y1) * (x2 + y2) - &a - &b;
+        let f = &z2 - &c;
+        let g = &z2 + &c;
+        let h = &b - self.a * &a;
+
+        let x = &e * &f;
+        let y = &g * &h;
+        let t = &e * &h;
+        let z = &f * &g;
+
+        GroupPoint::new(x, y, t, z)
+    }
+
+    // Scalar multiplication (p + ... + p n times)
+    pub fn mul(self, n: Field, p: TEPoint) -> TEPoint {
+        self.into_group().mul(n, p.into_group()).into_affine()
+    }
+}
+
+pub struct BabyJubjub {
+    pub curve: TECurve,
+    pub base8: TEPoint,
+    pub suborder: Field,
+}
+
+pub fn baby_jubjub() -> BabyJubjub {
+    BabyJubjub {
+        // Baby Jubjub (ERC-2494) parameters in affine representation
+        curve: TECurve::new(
+            168700.into(),
+            168696.into(),
+            // G
+            TEPoint::new(
+                995203441582195749578291179787384436505546430278305826713579947235728471134,
+                5472060717959818805561601436314318772137091100104008585924551046643952123905,
+            ),
+        ),
+        // [8]G precalculated
+        base8: TEPoint::new(
+            5299619240641551281634865583518297030282874472190772894086521144482721001553,
+            16950150798460657717958625567821834550301663161624707787222815936182638968203,
+        ),
+        // The size of the group formed from multiplying the base field by 8.
+        suborder: 2736030358979909402780800718157159386076813972158567259200215660948447373041,
+    }
+}
diff --git a/guests/eddsa_poseidon/src/lib.rs b/guests/eddsa_poseidon/src/lib.rs
new file mode 100644
index 0000000..53df361
--- /dev/null
+++ b/guests/eddsa_poseidon/src/lib.rs
@@ -0,0 +1,65 @@
+#![cfg_attr(feature = "no_std", no_std)]
+
+use std::default::Default;
+use std::hash::Hasher;
+use std::hash::poseidon::PoseidonHasher;
+
+mod ec;
+use ec::{ baby_jubjub, TEPoint, Field };
+
+#[guests_macro::proving_entrypoint]
+pub fn main(
+    msg: Field,
+    pub_key_x: Field,
+    pub_key_y: Field,
+    r8_x: Field,
+    r8_y: Field,
+    s: Field,
+) -> bool {
+    eddsa_verify::<PoseidonHasher>(pub_key_x, pub_key_y, s, r8_x, r8_y, msg)
+}
+
+pub fn eddsa_verify<H>(
+    pub_key_x: Field,
+    pub_key_y: Field,
+    signature_s: Field,
+    signature_r8_x: Field,
+    signature_r8_y: Field,
+    message: Field,
+) -> bool
+where
+    H: Hasher + Default,
+{
+    // Verifies by testing:
+    // S * B8 = R8 + H(R8, A, m) * A8
+    let bjj = baby_jubjub();
+
+    let pub_key = TEPoint::new(pub_key_x, pub_key_y);
+    assert!(bjj.curve.contains(pub_key));
+
+    let signature_r8 = TEPoint::new(signature_r8_x, signature_r8_y);
+    assert!(bjj.curve.contains(signature_r8));
+    // Ensure S < Subgroup Order
+    assert!(signature_s.lt(&bjj.suborder));
+    // Calculate the h = H(R, A, msg)
+    let mut hasher = H::default();
+    hasher.write(signature_r8_x);
+    hasher.write(signature_r8_y);
+    hasher.write(pub_key_x);
+    hasher.write(pub_key_y);
+    hasher.write(message);
+    let hash: Field = hasher.finish().into();
+    // Calculate second part of the right side:  right2 = h*8*A
+    // Multiply by 8 by doubling 3 times. This also ensures that the result is in the subgroup.
+    let pub_key_mul_2 = bjj.curve.add(pub_key, pub_key);
+    let pub_key_mul_4 = bjj.curve.add(pub_key_mul_2, pub_key_mul_2);
+    let pub_key_mul_8 = bjj.curve.add(pub_key_mul_4, pub_key_mul_4);
+    // We check that A8 is not zero.
+    assert!(!pub_key_mul_8.is_zero());
+    // Compute the right side: R8 + h * A8
+    let right = bjj.curve.add(signature_r8, bjj.curve.mul(hash, pub_key_mul_8));
+    // Calculate left side of equation left = S * B8
+    let left = bjj.curve.mul(signature_s, bjj.base8);
+
+    left.eq(&right)
+}