Re: [zapps-wg] Powers of Tau participation + zk proof question

[James Prestwich via zapps-wg]

10-20s proving time is more than fast enough for me.

I'm going to dig through the gadgetlibs to get a feel for what it'd take to
implement this, but it's been a long time since my last algebra class.

On Wed, Jan 3, 2018 at 3:06 PM Andrew Miller  wrote:

> 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  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  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 
> >> 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"  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
> >> >>  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"
> >> >> >>  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
>

Re: [zapps-wg] Powers of Tau participation + zk proof question

[James Prestwich via zapps-wg]

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  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 
> 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"  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
> >>  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 
> >> > 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"
> >> >>  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?
> >> >>
> >> >>
> >> >
>

Re: [zapps-wg] Powers of Tau participation + zk proof question

[Andrew Miller via zapps-wg]

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"
 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?