BLS signatures on Arkworks

[ArnaudBrousseau]

Hello! I recently published a new Rust package implementing BLS signatures based on Arkworks: https://github.com/ArnaudBrousseau/bls_on_arkworks

Wanted to drop by here and say thank you for a really cool set of crates; couldn't have written this without the foundation you've built here! Here are a few spots where using Arkworks felt harder than it should have been:

• The BigInt type in Arkworks doesn't support multiplication modulo a number or clean import/export to bytes so I found myself using num-bigint instead. I haven't tried too hard so it's possible I'm simply not seeing how to use it properly. Advice appreciated if you have any!
• Took me a long time to figure out how to correctly use MapToCurveBasedHasher. This snippet is the result of lots of trial and error. In the the end looking the the Arkworks tests helped (here). More example in docs could've helped maybe? Not sure.
• ark_ec::pairing::PairingOutput has a function named ::zero which maps to "one"! That was a little surprising (see where this is used: link)
• Converting field elements to bytes is hard. I had to write a helper to do this -- should this be part of Arkworks itself? I'm probably missing something obvious, I bet it is doable today, but I couldn't find how

And here are a few spots where Arkworks really shines:

• hash_to_point implementation, while hard to cobble together, is very succinct and clear: link
• get_ys_from_x_unchecked was just was I needed to implement point deserialization (see here)
• In a similar vein: new_unchecked / is_on_curve / is_in_correct_subgroup_assuming_on_curve were perfect for my use case. Was able to bubble up granular errors thanks to these, without re-implementing any arithmetic at all! See this
• Pairing functionality was super easy to discover and use (see this)

If some of the things I talk about in the "could do better" part are easy PRs to make I'd be down to contribute potentially!

[Pratyush]

Hey! Congrats on the fantastic crate, and thank you for the wonderful feedback! Let me go over your points one-by-one:

(1): BigInt type: I would recommend using the PrimeField/Field trait for arithmetic operations (unless you really need to do integer arithmetic). Regarding conversion to bytes, our CanonicalSerialize/CanonicalDeserialize allow for converting to bytes in a fairly straightforward manner. There's also a specialized function, which should do this directly

(2) Usage of MapToCurveHasher: We would very much welcome a PR adding doc-tests, usage examples, or generally additional documentation! We're also in the process of refactoring the hash-to-curve infra in this PR: arkworks-rs/algebra#643, so feedback from your experience would be useful in making any changes there!

(3) PairingOutput::zero() is one: Yup, this is a point of confusion because we're trying to use an additive group abstraction to represent a multiplicative group. This PR: arkworks-rs/algebra#665 is trying to remedy that by adding in a multiplicative group abstraction as well.

(4) Field elements to_bytes. This is again handled via the CanonicalSerialize/Deserialize infrastructure, or via fe.to_bigint().to_bytes_le()

Separately, I think you shouldn't have to implement point deserialization, because this is again handled by our serialization traits.

[ArnaudBrousseau]

Hi! Thanks for the detailed pointers! I was able to put (1) and (4) to good use! See this PR which simplifies the serialization logic by a mile, and this one which completely removes num-bigint as a direct crate dependency 🎉

It was a bit difficult to wrap my head around the need for a number of limbs at compile time for Arkworks' BigInt. Then I saw the type aliases and went with BigInteger256 as a type. But in the end the proper thing to do was, as you suggested, to switch my SecretKey type alias to point to a proper field element (Fr) instead of bytes or a raw integer. Once I made the switch the rest kind of followed neatly and Fr::from_be_bytes_mod_order came in very handy to deserialize from bytes in test cases.

While refactoring I found two potential things to improve inside of Arkworks itself (existing tests told me when behavior changed as I switched from what I had before to using more Arkworks types and helpers):

• deserialization logic is too loose for points at infinity (see the workaround here). I think that's an actual bug? Happy to upstream this extra validation!
• field elements have an inner BigInt, but it doesn't seem to be consistent with what into() yields. This was surprising:

  let inner_int: BigInteger256 = BLSFr::from(1u8).0;
  let into_int: BigInteger256 = BLSFr::from(1u8).into();
  assert_eq!(inner_int, into_int); # fails!

  From what I can tell the "right" BigInt to use is the one returned by into(): if this is always the case it might be worth a comment or warning somewhere?

[Pratyush]

Glad to see that the suggestions helped!

(1) Re: loose deserialization logic, I think you're right, we have a pending PR here to fix it: arkworks-rs/curves#157. Does that handle the issue?
(2) Re: conversion to BigInt, indeed the into conversion is the right way to proceed, as the field elements are internally represented in Montgomery form, and must be converted out of that form into "plain" form. This is what into() does, and what into_bigint() does. Re: preventing this footgun, we could (a) make the BigInt field of Fp #[doc(hidden)], so that it doesn't show up in the documentation, and (b) additionally suggest that converting to integers requires using into() or into_bigint(). Again, happy to accept PRs for both!

[ArnaudBrousseau]

(1) looks like arkworks-rs/curves#157 takes care of parts of the extra validation I have, namely: if the infinity bit is set, the x/y coordinates following the initial 3 bits should be set to 0. There's also illegal flag combinations: if the infinity bit (2nd bit) is set, then the 3rd bit (which indicates which of the possible y values to use when deserializing compressed points) can't be set to one. More concretely:

• 0b11000000: good first byte for a compressed point at infinity
• 0b01000000: good first bytes for an uncompressed point at infinity
• 0b11100000: bad first byte (2nd and 3rd bit set: nonsensical)
• 0b01100000: bad first byte (for the same reasons)
  I'll try playing with the branch locally to see if it's taken care of or not. And if it's not I'll comment on the PR. EDIT: commented on the PR with a failing test: link.

(2) I like this #[doc(hidden)] idea, and potentially adding more documentation around the "right" way to go from field element to big int 👍