[protocol spec] Include a cost analysis of attacks against BLS12-381 (STNFS, Cheon), Jubjub, and Pallas/Vesta

[daira]

For Cheon see https://ethresear.ch/t/cheons-attack-and-its-effect-on-the-security-of-big-trusted-setups/6692/16 , which estimates the cost as ~2^125.2 scalar field operations (equivalent to ~2¹²² group operations). [Updated 2021-09-03 to take account of d being 2²¹ for the Sapling setup, rather than 2²⁷ for the Filecoin setup.]

For Kim–Barbulescu the cost is somewhat unclear; there's some discussion in https://github.com/zcash/zcash/issues/4065 , but see https://github.com/zcash/zcash/issues/2502#issuecomment-508028959 . For Jubjub the best discrete-log attack is I think Pollard kangaroo against a 251-bit ivk (although that only gets the specific ivk; Pollard rho against one of the generators gets you a complete break).

[daira]

Note that due to the BCTV14 flaw, there's little value in estimating the discrete-log security of BN-254 [for Zcash, although there are still other projects using it]. Zero knowledge of the pre-Sapling BN-254 proofs is statistical, not dependent on DL hardness; soundness of those proofs is completely broken, although not believed to have been exploited.

[daira]

https://eprint.iacr.org/2019/885.pdf gives an estimated cost of 2¹²⁶ for BLS12-381 (Table 10). This matches the Sapling design security level of 2¹²⁵.

(Although the cost for a Cheon attack is slightly less than this in terms of equivalent group operations, there's also less uncertainty about it. I personally am not worried at all about an attack that takes ~2^125.2 field operations.)

[daira]

These were all calculated for my Zcon3 presentation (slides here).