Fuzzing

[mratsim]

A a minimum we need to add fuzzing to Hash-To-Curve as we might receive forged messages that might trigger edge cases.

One nice thing is that Milagro is using Exception-Free Addition formulas that fail to handle infinity points and for a point P(x, y) that needs special handling of Q(x, y) or Q(x, -y)

The issue stems from Short Weierstrass Addition law

P + Q = R
(Px, Py) + (Qx, Qy) = (Rx, Ry)

with
Rx = λ² - Px - Qx
Ry = λ(Px - Rx) - Py

with `λ = (Qy - Py) / (Px - Qx)`
which would divide by 0 if Px == Qx

For actual elliptic curve testing, it's quite probably the a fuzzer won't be able to create valid elliptic curve points (though AFL learned to create valid jpegs from nothing but fuzzing https://lcamtuf.blogspot.com/2014/11/pulling-jpegs-out-of-thin-air.html) so we will need to turn to differential fuzzing.

Thankfully there is a host of alternative implementations that we can use and that are sufficiently fast:

• Herumi's MCL - https://github.com/herumi/mcl
• Milagro Rust - https://github.com/sigp/milagro_bls
• Goff - https://github.com/ConsenSys/goff
• Algorand pairing (fork of Zcash that is 100x faster?? - https://github.com/algorand/pairing-plus

And somewhat slower:

• Zcash BLS12-381 - https://github.com/zcash/librustzcash
• Formally-verified BLS12-381 from fiat-crypto: https://github.com/mratsim/constantine/blob/ff9dec48/formal_verification/bls12_381_q_64.c
  • https://github.com/mit-plv/fiat-crypto

[zah]

#53 shows how you can get started. I hope you'll be able to take if from here.

[mratsim]

Ah, somehow I missed this PR

[arnetheduck]

what's our stance on herumi, in the end? it seems to have reached a critical support point