search

Zokrates / ZoKrates

A toolbox for zkSNARKs on Ethereum
https://zokrates.github.io
GNU Lesser General Public License v3.0
1.82k stars 362 forks source link

Is it possible to write secp256k1 curve arithmetic inside a SNARK #367

Closed kunxian-xia closed 5 years ago

kunxian-xia commented 5 years ago

For example, if we can implement scalar multiplication inside a SNARK, then we can prove knowledge of discrete log using libsnark instead of using Schnorr-like protocols.

HarryR commented 5 years ago

Hi

Please see: https://github.com/Zokrates/ZoKrates/tree/master/zokrates_stdlib/stdlib/ecc

However, this implements a twisted Edwards curve rather than secp256k1, where the 'Baby JubJub' curve operates over the native field of the SNARK.

This is much faster than implementing secp256k1 specifically, because with secp256k1 the field the curve operates over would have to be emulated - which is very costly. So compatibility with BitCoin (or e.g. NEO, which uses secp256r1) would require hundreds of thousands of constraints.

But, yes... you can do Schnorr-like protocols, ring signatures, EdDSA signatures etc. inside a zkSNARK using Zokrates using the Baby-JubJub curve.

See: https://github.com/Zokrates/ZoKrates/blob/master/zokrates_stdlib/stdlib/ecc/proofOfOwnership.code as an example

kunxian-xia commented 5 years ago

Yeah, I know about the JubJub curve proposed by ZCash team. I was wondering if there is some estimates about number of constraints to build general elliptic curve, such as secp256k1 or secp256r1.

HarryR commented 5 years ago

See: https://user.eng.umd.edu/~cpap/published/xjsnark.pdf which outlines some of the best known methods for performing arbitrary field arithmetic in a zkSNARK.

At the moment, I think xjsnark is the only application which implements this, but iirc could take ~250k constraints for a Schnorr signature verification.

It would be really cool if we could add this to Zokrates :D

Schaeff commented 5 years ago

Thanks for your help @HarryR. It would be indeed awesome to use some of the xjsnark bignumber tricks. Closing now as this was answered.