aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--guests/eddsa_poseidon/Cargo.lock94
-rw-r--r--guests/eddsa_poseidon/Cargo.toml17
-rw-r--r--guests/eddsa_poseidon/default.env2
-rw-r--r--guests/eddsa_poseidon/default_private_input.toml3
-rw-r--r--guests/eddsa_poseidon/default_public_input.toml3
-rw-r--r--guests/eddsa_poseidon/src/ec.rs276
-rw-r--r--guests/eddsa_poseidon/src/lib.rs65
7 files changed, 460 insertions, 0 deletions
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<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)
+}
generated by cgit v1.2.3 (git 2.46.0) at 2026-04-14 19:42:05 +0000