search

w3f / ring-vrf

MIT License
39 stars 17 forks source link

[DO NOT MERGE] Bandersnatch ad-hoc point compression PoC #85

Closed davxy closed 6 months ago

davxy commented 6 months ago

This PR show how is possible to further compress Bandersnatch points down to 32 bytes.

Arkworks compressed points are encoded in 33 bytes as 1 byte is reserved for the Flags (tracks point at infinite and negative y). This is quite generic, but for bandersnatch we can do better.

Bandersnatch base field is defined as BLS12-381 scalar field (bandersnatch::Fq = BLS12-381::Fr)

Modulo value: q = 0x73eda753299d7d483339d80809a1d80553bda402fffe5bfeffffffff00000001

This means that the most significant bit is always free and it could be used to encode the y sign.

Here I drafted a "dirty" PoC only for the PublicKey. But if it is a reasonable change I will:

davxy commented 6 months ago

This is the relevant part:

https://github.com/davxy/ring-vrf/blob/a8154c254d3b03d7b7c873bb2691a831bec787cd/bandersnatch_vrfs/src/lib.rs#L147-L167

burdges commented 6 months ago

We're maybe supposed to use CanonicalSerializeWithFlags and CanonicalDeserializeWithFlags here, right @mmagician ? Is this how curve25519/ed25519 handles this?

There exists code for this high bit encoding in the Flags structure:

https://github.com/arkworks-rs/algebra/blob/master/ec/src/models/twisted_edwards/serialization_flags.rs

We should fix ark-scale to do this by default probably, which maybe annoying..

davxy commented 6 months ago

Closing in favor of https://github.com/w3f/ring-vrf/pull/86