Generic EC #186

dvdplm · 2025-02-03T13:49:09Z

Make synderion generic over the elliptic curve type.

Very noisy PR, but the gist of it is that we make the SchemeParams trait agnostic over the elliptic curve used and thread that change across the code base while removing all explicit dependencies on k256.
Introduces a new generic parameter P: SchemeParams in many places, hence most of the noise.

The main areas to consider during review are:

Deserialization bounds. I have to admit that I often have very little clue as to why certain #[serde(bound(deserialize(STUFF))] are necessary or even why they work beyond "serde magic". Not great.
bip32 related functionality. BIP32 is only really well-defined for secp256k1 and while the code in this PR works for other curves as well, nothing but secp256k1 should ever be used in production without careful analysis.
The added HashOutput associated type on SchemeParams should be considered temporary. The goal is to remove the need for it and then we can remove it entirely.
The added WideCurveUint associated type on SchemeParams is there to allow reduced bias when generating scalars from extendable hashes. It's not great to have to do this, but I have found no better way. :/
There is an unfortunate delay in releasing updates to the RustCrypto stack following the release of crypto-bigint 0.6, which means that in this PR we're juggling two different versions of the bigint library. Hopefully we can get rid of this Real Soon™.

One outstanding question not addressed here is how to tweak the TestParams for optimal speed. For TinyCurve64 these settings seem to work:

-    const L_BOUND: u32 = 256;
-    const LP_BOUND: u32 = 256;
-    const EPS_BOUND: u32 = 320;
+    const L_BOUND: u32 = 64;
+    const LP_BOUND: u32 = 320;
+    const EPS_BOUND: u32 = 128;

…along with a PRIME_BITS setting of 256.

Closes #27.

…e::Scalar. So this goes back to the old `Scalar(BackendScalar)` type and makes it generic over the curve.

Patch sec1 crate v0.7.3 to impl ModulusSize for U8

Make Point generic over scheme params

fjarri · 2025-02-21T22:18:07Z

synedrion/benches/bench.rs

@@ -5,13 +5,15 @@ use manul::{
    dev::{run_sync, BinaryFormat, TestSessionParams, TestSigner, TestVerifier},
    signature::Keypair,
 };
-use rand_core::OsRng;
-use synedrion::{AuxGen, AuxInfo, InteractiveSigning, KeyInit, KeyShare, TestParams};
+use primeorder::FieldBytes;


We only need primeorder for this type, and it's just a type alias, perhaps we can just define it ourselves.

synedrion/src/curve/arithmetic.rs

fjarri · 2025-02-21T22:22:23Z

synedrion/src/curve/arithmetic.rs

-pub(crate) const ORDER: U256 = Secp256k1::ORDER;
-
-impl HashableType for Curve {
+impl HashableType for k256::Secp256k1 {


Can it be defined generically for any Curve implementor?

I think problem here was that there's a blanket impl that conflicts? But maybe I'm wrong. I'll try!

fjarri · 2025-02-21T22:30:41Z

synedrion/src/curve/arithmetic.rs

+        let bytes_lo = GenericArray::<_, FieldBytesSize<P::Curve>>::from_slice(&bytes_lo);
+        let bytes_hi = reader.read_boxed(Self::repr_len());
+        let bytes_hi = GenericArray::<_, FieldBytesSize<P::Curve>>::from_slice(&bytes_hi);
+        let uint_lo = <P::Curve as Curve>::Uint::decode_field_bytes(bytes_lo);


Does that work with non-reduced data? Feels like this should be crypto_bigint::Encoding:from_be_bytes() and not something specific to ECC

fjarri · 2025-02-21T22:34:43Z

synedrion/src/curve/arithmetic.rs

+        let uint_lo = <P::Curve as Curve>::Uint::decode_field_bytes(bytes_lo);
+        let uint_hi = <P::Curve as Curve>::Uint::decode_field_bytes(bytes_hi);
+        let wide_uint = uint_lo.concat(&uint_hi);
+        // TODO: When the elliptic curve stack upgrades to crypto-bigint v0.6 we can use RemMixed and


You can use crypto-bigint 0.6 (the one we use for Paillier, for example) all the way and in the last line convert it to the old Uint, like in params::convert_uint()

Hm, but then you'll probably need to convert ORDER too...

fjarri · 2025-02-21T22:35:51Z

synedrion/src/curve/arithmetic.rs

-    pub fn from_reduced_bytes(bytes: &[u8; 32]) -> Self {
-        let arr = GenericArray::<u8, FieldBytesSize<Secp256k1>>::from(*bytes);
-        Self(<BackendScalar as Reduce<U256>>::reduce_bytes(&arr))
+    pub fn from_reduced_bytes(bytes: impl AsRef<[u8]>) -> Self {


I'm wondering if this should reduce from a double-size uint as well.

synedrion/src/curve/arithmetic.rs

synedrion/src/lib.rs

fjarri · 2025-02-21T22:56:41Z

synedrion/src/tools/secret.rs

@@ -25,7 +26,10 @@ use crate::{
 /// - Safe serialization/deserialization (down to `serde` API; what happens there we cannot control)
 pub(crate) struct Secret<T: Zeroize>(SecretBox<T>);

-impl<T: Zeroize> Secret<T> {
+impl<T> Secret<T>


Btw, do you use some tool to move the type bounds into the where clause? I would like to make it consistent throughout the codebase, but I couldn't find a lint in clippy or rustfmt setting that would do that.

Yes, but it only works as a one-off thing, mapped to a key combo I have to press for each spot in the code. Having a way to do it across the code base would be real nice. Like, when I write code it's often convenient to type the bounds directly, but when reading code it's much easier (for me) to scan for the where clause; so automation would work well there for me.

fjarri · 2025-02-21T22:58:14Z

synedrion/src/tools/sss.rs

@@ -83,31 +99,42 @@ impl Polynomial {
 }

 #[derive(Debug, Clone, Serialize, Deserialize)]
-pub(crate) struct PublicPolynomial(Vec<Point>);
+#[serde(bound(deserialize = "for<'x> P: Deserialize<'x>"))]


Strange that you need an explicit bound for Deserialize but not for Serialize

Agreed. See other comment.

synedrion/src/tools/sss.rs

fjarri · 2025-02-21T23:00:49Z

synedrion/src/uint/traits.rs

@@ -175,7 +175,6 @@ impl HasWide for U4096 {
    type Wide = U8192;
 }

-// TODO(dp): Suggest crypto-bigint update nlimbs! macro.


We can probably bring back nlimbs! usage, it doesn't produce clippy warnings anymore.

synedrion/src/www02.rs

synedrion/src/www02/bip32.rs

fjarri · 2025-02-21T23:17:08Z

synedrion/src/www02/bip32.rs

+    for tweak in tweaks {
+        public_key = public_key.derive_child(*tweak)?;
+    }
+    let offset = bip32::KEY_SIZE - <C as Curve>::FieldBytesSize::USIZE;


I'm not sure I understand how this works. bip32::KEY_SIZE = 32, <C as Curve>::FieldBytesSize::USIZE is 32 for k256 or 24 for tiny-curve. Then the length of public_key.to_bytes() is 33, with all of these bytes being meaningful for k256. Then we just drop the first byte (the sign of y) and it works as a SEC1 representation?

Also the question above about unwrapping applies here as well - I don't think you need to de/serialize at all.

Let me spell out my reasoning and you can shoot it down!

For k256 the offset is 0, so bytes.get(offset..) will be the whole slice of 33 bytes yes? Should behave the same as the old code.

For TinyCurve64 the offset is 8, so in this case we truncate the high 8 bytes. This is likely not ok for a proper SEC1 repr, but the premise here is that BIP32 isn't really defined for anything other than secp256k1 so it's unclear what "valid" would even mean.

Hm, perhaps it does work, but in any case it's not necessary - we can avoid serialization entirely, see the other comment.

synedrion/src/www02/bip32.rs

fjarri · 2025-02-21T23:21:59Z

synedrion/src/www02/bip32.rs

+            tweakable_sk = tweakable_sk.derive_child(*tweak)?;
+        }
+        let bytes = tweakable_sk.to_bytes();
+        let bytes = bytes.get(32 - Scalar::<P>::repr_len()..).ok_or(bip32::Error::Decode)?;


Wouldn't it be easier to just unwrap SecretTweakable into SecretKey, via another method in the SecretTweakable trait?

Can you elaborate a bit on this (and "I don't think you need to de/serialize at all" above), not sure how you mean!

See fjarri@fa15322 (naming is rough, bounds may be adjusted, and perhaps some arguments can be taken by value). Basically, you have a trait to convert VerifyingKey<C> to something bip32 accepts, so I just add another method to convert that something back to VerifyingKey<C>, which we can do either by just returning the same object (for k256) or unwrapping the newtype (for tiny-curve). Same for SigningKey.

synedrion/tests/threshold.rs

synedrion/src/www02/key_resharing.rs

synedrion/src/www02/entities.rs

fjarri · 2025-02-21T23:32:51Z

synedrion/src/cggmp21/params.rs

+pub trait SchemeParams:
+    'static + Debug + Clone + Send + PartialEq + Eq + Send + Sync + Ord + Copy + Serialize + for<'x> Deserialize<'x>
+where
+    <Self::Curve as CurveArithmetic>::ProjectivePoint: FromEncodedPoint<Self::Curve>,


Some of the bounds look like they could be removed. The Copy ones, for example.

I assume you mean Copy on SchemeParams? Yeah I was on the fence on that, and tried both with and without; in the end I think that the reduced noise all over the code base from having it be Copy is worth it.

No, the Copy ones in the where clause. The Copy on SchemeParams is reasonable, I think clippy will complain if it's not present.

synedrion/src/cggmp21/params.rs

fjarri · 2025-02-21T23:39:50Z

synedrion/src/cggmp21/sigma/aff_g.rs

 }

 /// ZK proof: Paillier Affine Operation with Group Commitment in Range.
 #[derive(Debug, Clone, Serialize, Deserialize)]
+#[serde(bound(deserialize = "for<'x> P: Deserialize<'x>"))]


It's kind of weird to see these bounds everywhere. I thought about dealing with #10 by bounding SchemeParams on Serialize/Deserialize, which you did, but I would expect that to eliminate the need for the explicit bounds?

This stuff was driving me nuts. I cannot tell you why this works or if there are other/better ways of doing it. It was by far the most frustrating thing about this work. You add a bound in one place and it typechecks, but then breaks somewhere else, you fix it over there in a way that makes sense and now it breaks somewhere else...

Filed serde-rs/serde#2899. These bounds can be avoided if we don't bound SchemeParams on Deserialize, but then other explicit bounds will be needed - but we already had those, so maybe that's the best course of action.

synedrion/src/cggmp21.rs

fjarri · 2025-02-21T23:50:58Z

synedrion/src/www02/bip32.rs

+    fn derive_verifying_key_bip32(&self, derivation_path: &DerivationPath) -> Result<VerifyingKey<C>, bip32::Error>;
+}
+
+mod sealed {


What's up with sealing? Do these traits show up in the docs otherwise?

The idea was to lock down the types for which it's ok to impl them, not really about hiding from docs. You think it's overkill? They have to be pub because the types they are impl'd for are pub.

fjarri · 2025-02-21T23:53:52Z

One outstanding question not addressed here is how to tweak the TestParams for optimal speed. For TinyCurve64 these settings seem to work:

Yes, that looks correct, I added a comment in params.rs before reading the PR description :)
You can check the parameter validity by adding the test for are_self_consistent(), for them.

Also, there are three remaining comments mentioning #27 (in curve.rs, sigma/fac.rs, and paillier/encryption.rs) which can be now removed/amended.

dvdplm added 9 commits February 3, 2025 10:15

Add tinycurve

a02d5bb

Patch elliptic curve and k256

f5b8001

impl HashableType for TinuCurve64

3d98193

Rename old Curve to something greppable

980dbd8

Remove the ORDER constant

8c66ceb

Put bounds in where clause for readability

e1c7391

Put bounds in where-clause for readability

17d1b95

Add elliptic curve directly

b0aa5e9

Add a Scalar assoc type to SchemeParams and start propagating changes

faa6520

fjarri assigned dvdplm Feb 3, 2025

dvdplm added 20 commits February 4, 2025 15:01

Use the Scalar assoc type from SchemeParams::Curve

fc06637

Use the Scalar type from SchemeParmas::Curve

5e80233

Serde custom bounds for Round1DirectMessage

3ffc2b6

Slight change of tack: we do need a wrapper Scalar that wraps P::Curv…

3af9d9e

…e::Scalar. So this goes back to the old `Scalar(BackendScalar)` type and makes it generic over the curve.

Switch to primeorder crate and access elliptic-curve through it

840b7fd

Patch sec1 crate v0.7.3 to impl ModulusSize for U8

Switch to primeorder crate and access elliptic-curve through it

04fc5ee

Don't re-export k256 types

e7d8caf

Don't use k256 types

1fdaad0

Make Point generic over scheme params

Don't use k256 typees

cf5ba46

Cleanup

80f92d1

Replace hardcoded BackendDigest

48fdde4

Get tiny-curve from git

3b70561

Sort out ECDSA

59cebba

No need for Ser/Deser bounds

fda453a

Sort out Shamir Secret Sharing and add Ord+Copy bounds

6864577

Use the right tiny-curve

d861be3

Use the wrapper types

35f5406

Need a PrimeCurve bound for ecdsa ops

9d220df

Use wrapper types and ongoing struggles with ser/de

8bcd895

Sort out conversions and impl ConstantTimeSelect for Secret<T>

d3e6471

Clippy

c9df3e5