From 703539c236ad0cdb7a1834ac81446dc64187ebfb Mon Sep 17 00:00:00 2001 From: Kamen Mladenov Date: Fri, 28 Feb 2025 12:23:37 +0200 Subject: wip: eddsa_poseidon_benchmark --- guests/eddsa_poseidon/Cargo.lock | 94 ++++++++ guests/eddsa_poseidon/Cargo.toml | 17 ++ guests/eddsa_poseidon/default.env | 2 + guests/eddsa_poseidon/default_private_input.toml | 3 + guests/eddsa_poseidon/default_public_input.toml | 3 + guests/eddsa_poseidon/src/ec.rs | 276 +++++++++++++++++++++++ guests/eddsa_poseidon/src/lib.rs | 65 ++++++ 7 files changed, 460 insertions(+) create mode 100644 guests/eddsa_poseidon/Cargo.lock create mode 100644 guests/eddsa_poseidon/Cargo.toml create mode 100644 guests/eddsa_poseidon/default.env create mode 100644 guests/eddsa_poseidon/default_private_input.toml create mode 100644 guests/eddsa_poseidon/default_public_input.toml create mode 100644 guests/eddsa_poseidon/src/ec.rs create mode 100644 guests/eddsa_poseidon/src/lib.rs diff --git a/guests/eddsa_poseidon/Cargo.lock b/guests/eddsa_poseidon/Cargo.lock new file mode 100644 index 0000000..358e2ee --- /dev/null +++ b/guests/eddsa_poseidon/Cargo.lock @@ -0,0 +1,94 @@ +# This file is automatically @generated by Cargo. +# It is not intended for manual editing. +version = 3 + +[[package]] +name = "autocfg" +version = "1.4.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "ace50bade8e6234aa140d9a2f552bbee1db4d353f69b8217bc503490fc1a9f26" + +[[package]] +name = "bench_eddsa_poseidon" +version = "0.1.0" +dependencies = [ + "guests_macro", + "num", +] + +[[package]] +name = "guests_macro" +version = "0.1.0" + +[[package]] +name = "num" +version = "0.4.3" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "35bd024e8b2ff75562e5f34e7f4905839deb4b22955ef5e73d2fea1b9813cb23" +dependencies = [ + "num-bigint", + "num-complex", + "num-integer", + "num-iter", + "num-rational", + "num-traits", +] + +[[package]] +name = "num-bigint" +version = "0.4.6" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "a5e44f723f1133c9deac646763579fdb3ac745e418f2a7af9cd0c431da1f20b9" +dependencies = [ + "num-integer", + "num-traits", +] + +[[package]] +name = "num-complex" +version = "0.4.6" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "73f88a1307638156682bada9d7604135552957b7818057dcef22705b4d509495" +dependencies = [ + "num-traits", +] + +[[package]] +name = "num-integer" +version = "0.1.46" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "7969661fd2958a5cb096e56c8e1ad0444ac2bbcd0061bd28660485a44879858f" +dependencies = [ + "num-traits", +] + +[[package]] +name = "num-iter" +version = "0.1.45" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "1429034a0490724d0075ebb2bc9e875d6503c3cf69e235a8941aa757d83ef5bf" +dependencies = [ + "autocfg", + "num-integer", + "num-traits", +] + +[[package]] +name = "num-rational" +version = "0.4.2" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "f83d14da390562dca69fc84082e73e548e1ad308d24accdedd2720017cb37824" +dependencies = [ + "num-bigint", + "num-integer", + "num-traits", +] + +[[package]] +name = "num-traits" +version = "0.2.19" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "071dfc062690e90b734c0b2273ce72ad0ffa95f0c74596bc250dcfd960262841" +dependencies = [ + "autocfg", +] diff --git a/guests/eddsa_poseidon/Cargo.toml b/guests/eddsa_poseidon/Cargo.toml new file mode 100644 index 0000000..d476c89 --- /dev/null +++ b/guests/eddsa_poseidon/Cargo.toml @@ -0,0 +1,17 @@ +[package] +name = "bench_eddsa_poseidon" +version = "0.1.0" +edition = "2021" + +[dependencies] +guests_macro = { version = "0.1.0", path = "../../guests_macro" } +num = "0.4.3" + +[features] +no_std = [] +jolt = [] +nexus = [] +risc0 = [] +sp1 = [] +zkm = [] +zkwasm = [] diff --git a/guests/eddsa_poseidon/default.env b/guests/eddsa_poseidon/default.env new file mode 100644 index 0000000..b0537a5 --- /dev/null +++ b/guests/eddsa_poseidon/default.env @@ -0,0 +1,2 @@ +## ZKM ## +SEG_SIZE=2786 diff --git a/guests/eddsa_poseidon/default_private_input.toml b/guests/eddsa_poseidon/default_private_input.toml new file mode 100644 index 0000000..3e12916 --- /dev/null +++ b/guests/eddsa_poseidon/default_private_input.toml @@ -0,0 +1,3 @@ +r8_x = 0x163814666f04c4d2969059a6b63ee26a0f9f0f81bd5957b0796e2e8f4a8a2f06 +r8_y = 0x1255b17d9e4bfb81831625b788f8a1665128079ac4b6c8c3cd1b857666a05a54 +s = 1230930278088778318663840827871215383007447616379808164955640681455510074924 diff --git a/guests/eddsa_poseidon/default_public_input.toml b/guests/eddsa_poseidon/default_public_input.toml new file mode 100644 index 0000000..f349bf8 --- /dev/null +++ b/guests/eddsa_poseidon/default_public_input.toml @@ -0,0 +1,3 @@ +msg = 789 +pub_key_x = 0x16b051f37589e0dcf4ad3c415c090798c10d3095bedeedabfcc709ad787f3507 +pub_key_y = 0x062800ac9e60839fab9218e5ed9d541f4586e41275f4071816a975895d349a5e 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(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::(pub_key_x, pub_key_y, s, r8_x, r8_y, msg) +} + +pub fn eddsa_verify( + 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) +} -- cgit v1.2.3