[PoC] Compress all bandersnatch points in 32 bytes

[davxy]

This is a more elegant and general approach wrt https://github.com/w3f/ring-vrf/pull/85 (gated by tiny-compress feature)

By defining our SWCurveConfig type we catch the serialization of every affine point in one place (this includes serialization of PublicKey, VrfInput, VrfPreOutput, Signature, ..).

---

Note that in the SWCurveConfig we overwrite the point multiplication functions to delegate to the ones defined by the bandersnatch implementation we're actually using (which may be Arkworks upstream or the one using the Substrate hooks)

---

⚠️ Assumption

• We don't use the PointAtInfinity flag
• We assume that the point encoded with all zeros is the point at infinity and that there is no valid point encoded with all zeros which is not the point at infinity (i.e. a point with x = 0 and y != 0)
• Double check this assumption with a test: https://github.com/davxy/ring-vrf/blob/ef5b08fd4d2cfc82799061a628e6c12ba4dcb30e/bandersnatch_vrfs/src/affine.rs#L118-L150

[burdges]

I'll look more closely at this but it.. I've no nice way to make ark-scale handle points properly off the top of my head, not without specilization anyways. And this looks heavy. I'm tempted to see what others say first. @mmagician ?

[davxy]

For your ark-scale concerns, I don't understand what you mean. The implementation works flawlessly with ark-scale. See these tests I've just added:

https://github.com/davxy/ring-vrf/blob/03e1d83444b720d86277b4cbcb2333725d10cd58/bandersnatch_vrfs/src/lib.rs#L362-L381

Maybe you refer to something else?

[davxy]

Oh I gated this "extra" compression behind the tiny-compress feature. By default uses the arkworks one

[davxy]

For the record. Even though this is "not standard", should be noted that:

• arkworks default serialization is not standard (is there a real "standard"?)
• If I understood correctly, arkworks serialization is not inline with some of the other implementations which uses big endian instead

[burdges]

We'll ask for others opinions here, but I do think (0,b^2) should encode correctly if we do this, which means chosing if the point at infinitey has positive or negative.

[davxy]

When decoded the point at infinity in affine coord is always constructed as AffineSW{ x=0, y=0, infinity = true. This is the same behavior as the built-in serializer. So I guess from this perspective there isn't nothing to do?

BTW if in the end we just map the Weierstrass form to Edwards this PR is not relevant (at least for our application)

[burdges]

We'd let (0,b^2) be nagative then? Aka set its high bit. It's currently [0u8; 32] right?

At least generically I'd expect (0,b^2) could be positive or nagative, depending upon the curve. I've not checked but (0,b^2) might serialize as all zeros under this in bandeersnatch.

Anyways sergey pointed out Banderwagon: https://hackmd.io/@6iQDuIePQjyYBqDChYw_jg/BJBNcv9fq https://hackmd.io/@6iQDuIePQjyYBqDChYw_jg/BJ2-L6Nzc https://hackmd.io/@6iQDuIePQjyYBqDChYw_jg/B1ZxTAVz5 and https://hackmd.io/wliPP_RMT4emsucVuCqfHA?view

Appears even Daria hadn't looked closely yet so I'm suspicious nobody deployed bandersnatch yet. lol

[davxy]

I'd serialize it as all zeros. I.e. not setting the negative bit. This is inline with how the built in encoder does it (it doesn't set the bit).

Obviously this encoding technique can't be upstreamed to arkworks as it works well if the Validate flag is always true. If we set the Validate to false the decoder works for all the points except for the two points (x = 0, y != 0) as it will incorrectly decode it as the point at inf.

For the banderwagon thing I don't know, but I have the feeling that switching to it is not immediate and may be a time warp? 🤣

The "just in time" switch to Edwards form could work as well.

I'll discuss about the options with the others as well. For your gut feeling what could be the best approach? Also thinking about interoperability with eventual third party implementations of the bandernatch ring vrf crypto

In the end. If encoding in 33 bytes is not a big deal... we can just leave it as it is now. Maybe is the most obvious and portable of the options. I'll try to clarify this with the team 😅

[burdges]

Banderwagon looks cheap after someone implements SW<->TE maps: https://github.com/crate-crypto/banderwagon/