about serialization of bn254 curve point about halo2curves

[mratsim]

When implementing curve serialization, I have seen 3 different cases:

• 3 extra bits, like BLS12-381, the extra bits are used for compressed form, infinity point, sign, Zcash serialization is the defacto standard and is mentioned in the IETF: https://www.ietf.org/archive/id/draft-irtf-cfrg-pairing-friendly-curves-11.html#name-zcash-serialization-format-
• 2 extra bits, like BN254, 1 bit has to be used for the sign, for the rest I would assume arkworks follow libsnarks, as libsnarks was the original that started all, I think halo2curves should follow suit.
• 1 extra bit, like Banderwagon and Pasta curves. That extra bit as to be used for the sign as we can derive compressed form or not from the length, and inifnity by having all zeros content. The only serialization standard followed by multi repos I'm aware of is from @kevaundray for Banderwagon (note, Ristretto/Decaf like construction so serialization is somewhat special: https://hackmd.io/@6iQDuIePQjyYBqDChYw_jg/BJBNcv9fq#Serialisation)

I've stopped myself from ranting against BE. Just letting you know I hate this... It should've all been LE.

BigInts/Fields are always serialized in BE, it's also natural when hex debugging. See I2OSP and OS2IP from RSA spec: https://www.rfc-editor.org/rfc/rfc8017.html#section-4

Additionally, if needed, Fp2 and Fp12 serializations might need standardization as well.

For Fp2, Zcash serializes extension field first, i.e. the i element then the base field.

For Fp12, the serialization should be canonical instead of being tied to a specific towering Fp2 -> Fp6 -> Fp12 vs Fp2 -> Fp4 -> Fp12. See discussion in supranational/blst#101 (comment)

[nanne007]

related discussion on arkworks arkworks-rs/algebra#708

[CPerezz]

Ohhh! That's really unfortunate!
@kilic was the original creator of the bn256 inclusion PR. So he might know better about this specific nuance.

I agree we should make it unified such that we don't bring extra trouble to the usears.

Do you have any specific formatting proposal BTW @nanne007 ?

[nanne007]

Thank you for the reply!
Currently dont have any particular proposal in mind.

In fact, the serialization(compressed version) of bn254 in both projects are very similar except the bit sign.
I think if we can agree on this, maybe a common format of bn254 can be derived from the two projects.

The zcash serialization of bls12-381 sets a good standard here. https://www.ietf.org/archive/id/draft-irtf-cfrg-pairing-friendly-curves-11.html#name-zcash-serialization-format-

But for bn254, it can be harder, as there're already many different impls used on production.
apart from these two projects, ethereum uses big endian encoding for Field, see https://eips.ethereum.org/EIPS/eip-196#encoding .
This can be solved by add an option about le or be when calling serialization function like to_bytes.
However, adding other option for the bit sign of a curve point's negative of y and point of infinity seems a little inconvenient.

[CPerezz]

But for bn254, it can be harder, as there're already many different impls used on production.
apart from these two projects, ethereum uses big endian encoding for Field, see https://eips.ethereum.org/EIPS/eip-196#encoding .

I've stopped myself from ranting against BE. Just letting you know I hate this... It should've all been LE.

On the rest, I agree, we can solve this on this way or another. I think we can flip the bit order in the compressed form such that the two ecosystems match together.
For the general formatting what we can do is offer a general serialization impl which has arbitrary endianness based on an option as you say and sign compression (it's the default IMO).

For the rest, we can define an SerializedExt trait or whatever where we can implement extra serialization options which are more optimal for certain use cases each.

Any idea how could we formalize this a bit more? We'll be happy to jump into a call, clarify this and update it!
At the end, a smooth transition from one ecosystem to the other would be the most desired thing to have!

[guangyuz]

Unifying the formatting makes sense for the community. Add @huyuncong , maybe he knows someone from arkworks who can take a look.

[CPerezz]

Maybe we can try summoning @Pratyush and he can orient us. Also curious to know his thoughts.

[davidnevadoc]

There is an extra case, the curves that have no extra bits for flags, like secp256k1. For this curve we are adding an extra byte to hold the flags in both the compressed an uncompressed format. Bitcoin's implementation does this as well:
https://github.com/bitcoin-core/secp256k1/blob/77af1da9f631fa622fb5b5895fd27be431432368/src/eckey_impl.h#L37

I found a couple more issues.
The infinity flag is the 7th bit in the compressed form:

halo2curves/src/derive/curve.rs

Line 109 in bdb27cc

let is_inf = Choice::from(tmp[[< $name _COMPRESSED_SIZE >] - 1] >> 7);

But it is the 6th in the uncompressed form:

halo2curves/src/derive/curve.rs

Line 235 in bdb27cc

let infinity_flag_set = Choice::from((bytes[[< $name _UNCOMPRESSED_SIZE >] - 1] >> 6) & 1);

The way of determining the sign seems not to be agreed upon either. In fact, we are not getting the sign but the parity of the y-coordinate.

[mratsim]

The way of determining the sign seems not to be agreed upon either. In fact, we are not getting the sign but the parity of the y-coordinate.

Note that "sign" is a convention that splits a cyclic group in 2 halves.

When standardizing hash-to-curve, the "sign" was changed to mean x mod 2:

• 2019, sgn0 with little endian and big-endian variants: cfrg/draft-irtf-cfrg-hash-to-curve#144 / cfrg/draft-irtf-cfrg-hash-to-curve#176
• 2021: breaking spec change to parity - cfrg/draft-irtf-cfrg-hash-to-curve#225

[nanne007]

and should notice that sign of bn254 curve in halo2curves and arkworks have different meaning

in arkworks:

the negative sign always means the bigger one, see the code:

https://github.com/arkworks-rs/algebra/blob/ee0a4078b67037b4c4d22d330113a5d7c28fd6ce/ec/src/models/short_weierstrass/affine.rs#L160

while in halo2curves:
sign is the smallest bit of Y, as y and -y have different even-old parity, so use last bit can distinguish them.
see the code:

https://github.com/privacy-scaling-explorations/halo2curves/blob/a3f15e4106c8ba999ac958ff95aa543eb76adfba/src/derive/curve.rs#L145C35-L145C35

That means one canno distinguish current y is the smaller one or the bigger one based on the sign in halo2curves impl.