search

arkworks-rs / snark

Interfaces for Relations and SNARKs for these relations
https://www.arkworks.rs
Apache License 2.0
776 stars 209 forks source link

Implement BN curves #225

Closed yelhousni closed 4 years ago

yelhousni commented 4 years ago

This PR implements infrastructure for BN family of curves and instantiate BN256 from Etherem (EDIT: curve renamed to BN254). Type: Feature Label: Ready to review Priority: Medium

Motivation

Support of BN family that is widely used for pairing-based cryptography (Ethereum, libsnark, DIZK, Halo).

Followups

yelhousni commented 4 years ago

@Pratyush @howardwu @kobigurk That would be great if you can review this!

Pratyush commented 4 years ago

Thanks for the helpful chronology! Given this info, what do you suggest we should name the curve? I think bn256 doesn’t make sense if there are two different curves with that name.

On Sat, Jun 20, 2020 at 11:26 AM Kobi Gurkan notifications@github.com wrote:

@kobigurk commented on this pull request.

In algebra/Cargo.toml https://github.com/scipr-lab/zexe/pull/225#discussion_r443150273:

  • "bn256", "bls12_377", "bls12_381", "cp6_782", "bw6_761", "mnt4_298", "mnt4_753", "mnt6_298", "mnt6_753", "ed_on_bls12_377", "ed_on_cp6_782", "ed_on_bw6_761", "ed_on_bls12_381", "ed_on_mnt4_298", "ed_on_mnt4_753" ]

+bn256 = []

If I remember correctly, the history goes like this:

  • bn256 from cloudflare and google implement a BN curve that's unrelated to Zcash. When the Ethereum devs ported it to the libsnark curve, they kept the name.
  • bn128 is the name that was used by libsnark and then by Zcash, denoting 128-bit security.
  • Later on, Zcash and the community mostly decided to switch to the bn254 naming, since it wasn't 128-bit security anymore and 254-bit is the size of the curve.

I believe that the pairing-friendly curve draft from IETF actually calls this curve BN_SNARK1.

— You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub https://github.com/scipr-lab/zexe/pull/225#discussion_r443150273, or unsubscribe https://github.com/notifications/unsubscribe-auth/AAYSJ6WBXRWASFVGALDFABDRXT5M5ANCNFSM4OBLVEBA .

kobigurk commented 4 years ago

IMO bn254.

Pratyush commented 4 years ago

Ok sounds good then!

yelhousni commented 4 years ago

Thank you Kobi for the chronology! If we are to choose the name that makes most sense, then bn254 is the best option indeed. We just need to mention (in mod.rs for instance) that the curve is known also as bn256 in Geth and bn128 in libff.

mratsim commented 4 years ago

For naming I suggest BN254_Snarks as in the literature BN254 often (always?) refers to the one from Nogami et al with parameter -(2^62 + 2^55 + 1)

MCL also uses similar scheme to differentiate both: https://github.com/herumi/mcl#support-curves

Pratyush commented 4 years ago

Hey @mratsim, thanks for the additional perspective!

I still feel that bn254 is fine as it is well known in the context of SNARK systems (which this library is largely targeted towards). I also think that the literature moving forward will probably not use any BN254 curve, as these curves are not secure. For the same reason, existing systems will probably eventually be deprecated the curve anyway.