search

miracl / core

MIRACL Core
Apache License 2.0
199 stars 68 forks source link

BLS: ZCash-style curve point encodings? #21

Closed nomeata closed 2 years ago

nomeata commented 3 years ago

I noticed that miracl encodes BLS public keys and signatures using the SEC-style compressed format (leading 0x02 or 0x03 depending on parity of y coordinate, followed by x coordinate). The RFC draft for BLS, however, suggests a different encoding, using the spare top 3 bits of the 48/96 bytes, according to the scheme described at https://github.com/zkcrypto/bls12_381/blob/bc1706f6426aca52b9a99e5f100bdb7d119305d3/src/notes/serialization.rs.

Do you have plans to support that encoding in miracl, too?

mcarrickscott commented 3 years ago

If each curve gets its own bespoke compression format, then we are heading for chaos. And just to save one byte! And the determination of sign is here based on the MSB of y, whereas using the LSB (Least Significant Bit) is more common. Indeed the Hash-To-Curve draft standard just removed MSB as an option, and here it is back again! And for y_1=a+ib and y2=c+id \in F{p^2} which is "lexicographically largest"? Not immediately clear to me.

Having said that it will not be hard to do. IF the curve has 3 spare bits and IF MSB sign is selected (BIG_ENDIAN_SIGN), then we can offer it as an option.

nomeata commented 3 years ago

As a poor minion who has to deal with whatever the spec says (and other implementations produce) would certainly appreciate that :-)

nomeata commented 3 years ago

Is it actually the MSB? Since p isn’t a power of two, aren’t there possible y coordinates (close to the middle of the range) that are negations of each other, but where the MSB is both 0? Maybe that’s the reason why they refer to a (lexicographic) order instead.

mcarrickscott commented 3 years ago

Yes, you are right. I was using MSB rather loosely..

nomeata commented 3 years ago

Oh, and just before someone else stumbled over this: The ZCash encoding also encodes the components of a G2 point in the other order (first b then a)

mcarrickscott commented 3 years ago

Yes, just noticed that. Strange and rather non-intuitive (to me anyway). But there are no standards for this as far as I am aware, so I am happy to go along..

mcarrickscott commented 3 years ago

ZCash encoding is now available as an option, if and only if the modulus has 3 spare bits available in its most significant byte. So a 381-bit modulus has 3 spare bits, whereas a 383 bit modulus has only one. To activate, manually set ALLOW_ALT_COMPRESS to true. This flag may be found in the config_curve. file, or in ecp.

G2 coordinate component ordering has been switched in all cases.

Probably needs a bit more testing..