Sorry for resuscitating an old thread, but I’m not finding much about the pasta curves and I would be highly interested in having some pasta curves support in the EVM. We also use them in Mina protocol and supporting them on the EVM would allow us to have a fully verified light client for Mina running in Ethereum.
2 Likes
There is a solitidy implementation here with benchmark info. GitHub - zhenfeizhang/pasta-solidity: A Solidity implementation of Halo2's Pasta curves
3 Likes
That is exactly what our Mina to Ethereum bridge is about, https://blog.nil.foundation/2021/09/30/mina-ethereum-bridge.html, GitHub - NilFoundation/mina-state-proof: In-EVM Mina State Verification. No trusted setup.
1 Like
Do we really need Pallas and Vesta when we already have Grumpkin?
3 Likes
Yes:
- BN254 is estimated to have at most 103-bit security against STNFS. If this isn’t already within reach of well-funded adversaries, such as intelligence agencies, it will be. (See this talk for why attacks on discrete-log cryptosystems require only a single large precomputation to then break any given discrete logarithm quickly; this does apply to the target group of a pairing.) I don’t think it’s a good idea to essentially force designers into trade-offs that make their protocols potentially breakable by an intelligence agency.
- While BN254’s scalar field has 2-adicity 28, Grumpkin’s scalar field has no 2-adicity, making it inefficient to perform FFTs for proof systems instantiated on Grumpkin.
Note that what Genya-Z and Pratyush have said about the relative security of the Pasta curves and pairing-friendly curves is correct. BN, BLS, and as far as I’m aware all other pairing-friendly curves used in cryptography, are constructed by CM. Pairing-friendly curves also have low embedding degrees. I’m skeptical of the value for security analysis of looking at “how structured” a construction is, but if we are going to do that then we should at least get things in the right order. At risk of oversimplifying, the ordering goes like this from least to most “structured”:
(general elliptic curves) < (CM curves like secp256k1) < (2-adic cycles like Pasta) <<< (half-pairing 2-adic cycles like Pluto-Eris) < (non-cyclic pairings) < (MNT pairing cycles) << (discrete log in \mathbb{F}_p)
All of the curves on the left of the “<<<” have high embedding degree. (A half-pairing cycle has high embedding degree for one of the curves in the cycle.) It is high embedding degree that prevents a curve from being subject to reductions that allow index calculus attacks. To my knowledge, the only attack that depends on CM structure is a slight speed up to Pollard rho in some cases. As we said in a footnote to the Halo paper:
A conservative estimate of the available improvement to Pollard rho is that on a group of prime order q with an automorphism group of order 6, the attack cost is \sqrt{\frac{\pi q}{12}}, as compared to \sqrt{\frac{\pi q}{4}} using only the negation map as described in [6]. That is, the maximum speed-up is only a factor of \sqrt{3} ≈ 1.732 for a given success probability.
(This footnote applies to j = 0 curves like secp256k1 or Pallas/Vesta, and also to BN or BLS12 pairing-friendly curves when Pollard rho is used.)
I’m obviously somewhat biased because I constructed the Pasta cycle and my colleague Sean Bowe constructed BLS12-381, but in my opinion there is a strong engineering and security justification for adding both of these as precompiles, and there’s no need to pit them against each other as is done in this thread.
4 Likes
Late to the party, but one cool application of BLS (and more generally pairing-based curves) that I don’t think pasta curves support is identity-based encryption such as timelock encryption.
1 Like
Hi, sorry to be late and I know it s not that much related but I do see unlike Zcash that Ethereum do provide and allow points at infinity in optimal ate pairings.
This of course breaks the non degenerancy criteria if smarts contracts don t check input points since pairings with points at infitinity are skipped in the eip197 precompile. But is it a risk for groth16 or only for third party zksnarks systems?
And more generally are there current uses on Ethereum about allowing this? If not would it be usefull for the precompile call to fail if a point at infinity is used like it s currently done for points outside curves?