Yeah! It's 2018 and we still don't have a libsnark gadget for verifying major cryptocurrency signatures? What gives?

Call me old fashioned #slowcrypto but even with 10-20s proving time it could still be useful for things. On Wed, Jan 3, 2018 at 4:01 PM, James Prestwich <ja...@prestwi.ch> wrote: > This is about the point where my math and libsnark knowledge runs out :) > > My usecase is specifically cryptocurrency related, so I'm mostly interested > in curves that are used by cryptocurrency signature algorithms. E.g. > secp256k1 (Bitcoin and its kids), ed25519 (Sia, Stellar, and a few others). > Jubjub is definitely on the list once sapling is closer to deployment. After > a bit of consideration, ed25519 would probably be the most interesting at > first. > > On Wed, Jan 3, 2018 at 2:33 PM Sean Bowe <s...@z.cash> wrote: >> >> I believe those gadgets are specifically for curves where the scalar >> field is the base field of the curve you're working with, so they >> probably wouldn't be that useful for arbitrary fields. Most of the >> complexity here is the bignum arithmetic inside the circuit, though. >> >> > Is there any more clever way to do this than just providing splitting >> > into bits to implement modular arithmetic in a different field? >> >> Not that I know of. I explored the feasibility of this kind of stuff >> in the past and concluded each point addition would be around the cost >> of a SHA256 invocation. You can minimize the number of additions using >> window tables. The best approach seemed to be giant window tables >> queried with merkle tree lookups using something like MiMC. The >> additions are most efficient when working with affine formulas >> (inversions can be witnessed as efficiently as multiplications). You >> may be able to get this down to 2^20 constraints for ~256-bit scalars, >> which might be around 10-20 second proving time. >> >> Sean >> >> On Wed, Jan 3, 2018 at 1:36 PM, Andrew Miller <soc1...@illinois.edu> >> wrote: >> > Suppose one did want to build a secp256k1 gadget. I notice that libsnark >> > already provides a general gadget for weierstrass form elliptic curves, >> > parameterized by a field. So all we'd have to do is define the secp256k1 >> > operations in the alt_bn128 or in bls12 fields. Is there any more clever >> > way >> > to do this than just providing splitting into bits to implement modular >> > arithmetic in a different field? >> > >> > On Jan 3, 2018 2:11 PM, "Sean Bowe" <s...@z.cash> wrote: >> >> >> >> If any curve is acceptable, I would encourage Jubjub, which we'll be >> >> using for the next version of Zcash. In which case you will be able to >> >> leverage our Sapling crypto code once it is more mature over the next >> >> month or so. https://github.com/zcash-hackworks/sapling-crypto >> >> >> >> Sean >> >> >> >> On Wed, Jan 3, 2018 at 1:02 PM, James Prestwich via zapps-wg >> >> <zapps...@lists.z.cash.foundation> wrote: >> >> > I'd prefer sha256 or bitcoin-style hash160. I'm interested in a few >> >> > different curves, including secp256k1. Eventually for EdDSA keys as >> >> > well. Is >> >> > there a list of supported curve operations? >> >> > >> >> > On Wed, Jan 3, 2018 at 12:57 PM Andrew Miller <soc1...@illinois.edu> >> >> > wrote: >> >> >> >> >> >> Thank you so much for expressing your question in Camenisch-Stadler >> >> >> notation! That makes it very clear what you're going for. >> >> >> >> >> >> What hash function H do you have in mind, would SHA2 work? Also what >> >> >> group >> >> >> G do you have in mind, secp256k1? >> >> >> >> >> >> If so, I do not know of any existing implementation of secp256k1 >> >> >> operations specifically in libsnark, so that would presumably be the >> >> >> biggest >> >> >> challenge. >> >> >> >> >> >> >> >> >> On Jan 3, 2018 1:47 PM, "James Prestwich via zapps-wg" >> >> >> <zapps...@lists.z.cash.foundation> wrote: >> >> >> >> >> >> I'd like to participate in the setup ceremony. >> >> >> >> >> >> I also have an app I'd like to build using a zk-proof of knowledge >> >> >> of >> >> >> an >> >> >> ECC private key. {(a) : A = a * G, B = H(a)}. Can anyone point me to >> >> >> good >> >> >> resources on getting started? >> >> >> >> >> >> >> >> > -- Andrew Miller University of Illinois at Urbana-Champaign