Re: [zapps-wg] Powers of Tau participation + zk proof question
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
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
>> >> > 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
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
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
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
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
> I'd like to participate in the setup ceremony.
Great! I'll be in touch.
> {(a) : A = a * G, B = H(a)}
Are you constrained by the choice of H and/or the curve?
Sean
On Wed, Jan 3, 2018 at 12: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
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
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?
[zapps-wg] Powers of Tau participation + zk proof question
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?
