184 lines
9.8 KiB
HTML
184 lines
9.8 KiB
HTML
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
|
|
<HTML>
|
|
<HEAD>
|
|
<TITLE> [zapps-wg] Powers of Tau participation + zk proof question
|
|
</TITLE>
|
|
<LINK REL="Index" HREF="/pipermail/zapps-wg/2018/index.html" >
|
|
<LINK REL="made" HREF="mailto:zapps-wg%40lists.zfnd.org?Subject=Re%3A%20%5Bzapps-wg%5D%20Powers%20of%20Tau%20participation%20%2B%20zk%20proof%20question&In-Reply-To=%3CCAOP2Cbw7AR%3DCw68XAKqAjPVg7k%2BbpP2-O2iabCoDGDGOCX881A%40mail.gmail.com%3E">
|
|
<META NAME="robots" CONTENT="index,nofollow">
|
|
<style type="text/css">
|
|
pre {
|
|
white-space: pre-wrap; /* css-2.1, curent FF, Opera, Safari */
|
|
}
|
|
</style>
|
|
<META http-equiv="Content-Type" content="text/html; charset=us-ascii">
|
|
<LINK REL="Previous" HREF="000164.html">
|
|
<LINK REL="Next" HREF="000159.html">
|
|
</HEAD>
|
|
<BODY BGCOLOR="#ffffff">
|
|
<H1>[zapps-wg] Powers of Tau participation + zk proof question</H1>
|
|
<B>James Prestwich</B>
|
|
<A HREF="mailto:zapps-wg%40lists.zfnd.org?Subject=Re%3A%20%5Bzapps-wg%5D%20Powers%20of%20Tau%20participation%20%2B%20zk%20proof%20question&In-Reply-To=%3CCAOP2Cbw7AR%3DCw68XAKqAjPVg7k%2BbpP2-O2iabCoDGDGOCX881A%40mail.gmail.com%3E"
|
|
TITLE="[zapps-wg] Powers of Tau participation + zk proof question">james at prestwi.ch
|
|
</A><BR>
|
|
<I>Wed Jan 3 17:26:28 EST 2018</I>
|
|
<P><UL>
|
|
<LI>Previous message (by thread): <A HREF="000164.html">[zapps-wg] Powers of Tau participation + zk proof question
|
|
</A></li>
|
|
<LI>Next message (by thread): <A HREF="000159.html">[zapps-wg] Powers of Tau participation + zk proof question
|
|
</A></li>
|
|
<LI> <B>Messages sorted by:</B>
|
|
<a href="date.html#165">[ date ]</a>
|
|
<a href="thread.html#165">[ thread ]</a>
|
|
<a href="subject.html#165">[ subject ]</a>
|
|
<a href="author.html#165">[ author ]</a>
|
|
</LI>
|
|
</UL>
|
|
<HR>
|
|
<!--beginarticle-->
|
|
<PRE>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 <<A HREF="/mailman/listinfo/zapps-wg">soc1024 at illinois.edu</A>> wrote:
|
|
|
|
><i> Yeah! It's 2018 and we still don't have a libsnark gadget for
|
|
</I>><i> verifying major cryptocurrency signatures? What gives?
|
|
</I>><i>
|
|
</I>><i> Call me old fashioned #slowcrypto but even with 10-20s proving time it
|
|
</I>><i> could still be useful for things.
|
|
</I>><i>
|
|
</I>><i> On Wed, Jan 3, 2018 at 4:01 PM, James Prestwich <<A HREF="/mailman/listinfo/zapps-wg">james at prestwi.ch</A>> wrote:
|
|
</I>><i> > This is about the point where my math and libsnark knowledge runs out :)
|
|
</I>><i> >
|
|
</I>><i> > My usecase is specifically cryptocurrency related, so I'm mostly
|
|
</I>><i> interested
|
|
</I>><i> > in curves that are used by cryptocurrency signature algorithms. E.g.
|
|
</I>><i> > secp256k1 (Bitcoin and its kids), ed25519 (Sia, Stellar, and a few
|
|
</I>><i> others).
|
|
</I>><i> > Jubjub is definitely on the list once sapling is closer to deployment.
|
|
</I>><i> After
|
|
</I>><i> > a bit of consideration, ed25519 would probably be the most interesting at
|
|
</I>><i> > first.
|
|
</I>><i> >
|
|
</I>><i> > On Wed, Jan 3, 2018 at 2:33 PM Sean Bowe <<A HREF="/mailman/listinfo/zapps-wg">sean at z.cash</A>> wrote:
|
|
</I>><i> >>
|
|
</I>><i> >> I believe those gadgets are specifically for curves where the scalar
|
|
</I>><i> >> field is the base field of the curve you're working with, so they
|
|
</I>><i> >> probably wouldn't be that useful for arbitrary fields. Most of the
|
|
</I>><i> >> complexity here is the bignum arithmetic inside the circuit, though.
|
|
</I>><i> >>
|
|
</I>><i> >> > Is there any more clever way to do this than just providing splitting
|
|
</I>><i> >> > into bits to implement modular arithmetic in a different field?
|
|
</I>><i> >>
|
|
</I>><i> >> Not that I know of. I explored the feasibility of this kind of stuff
|
|
</I>><i> >> in the past and concluded each point addition would be around the cost
|
|
</I>><i> >> of a SHA256 invocation. You can minimize the number of additions using
|
|
</I>><i> >> window tables. The best approach seemed to be giant window tables
|
|
</I>><i> >> queried with merkle tree lookups using something like MiMC. The
|
|
</I>><i> >> additions are most efficient when working with affine formulas
|
|
</I>><i> >> (inversions can be witnessed as efficiently as multiplications). You
|
|
</I>><i> >> may be able to get this down to 2^20 constraints for ~256-bit scalars,
|
|
</I>><i> >> which might be around 10-20 second proving time.
|
|
</I>><i> >>
|
|
</I>><i> >> Sean
|
|
</I>><i> >>
|
|
</I>><i> >> On Wed, Jan 3, 2018 at 1:36 PM, Andrew Miller <<A HREF="/mailman/listinfo/zapps-wg">soc1024 at illinois.edu</A>>
|
|
</I>><i> >> wrote:
|
|
</I>><i> >> > Suppose one did want to build a secp256k1 gadget. I notice that
|
|
</I>><i> libsnark
|
|
</I>><i> >> > already provides a general gadget for weierstrass form elliptic
|
|
</I>><i> curves,
|
|
</I>><i> >> > parameterized by a field. So all we'd have to do is define the
|
|
</I>><i> secp256k1
|
|
</I>><i> >> > operations in the alt_bn128 or in bls12 fields. Is there any more
|
|
</I>><i> clever
|
|
</I>><i> >> > way
|
|
</I>><i> >> > to do this than just providing splitting into bits to implement
|
|
</I>><i> modular
|
|
</I>><i> >> > arithmetic in a different field?
|
|
</I>><i> >> >
|
|
</I>><i> >> > On Jan 3, 2018 2:11 PM, "Sean Bowe" <<A HREF="/mailman/listinfo/zapps-wg">sean at z.cash</A>> wrote:
|
|
</I>><i> >> >>
|
|
</I>><i> >> >> If any curve is acceptable, I would encourage Jubjub, which we'll be
|
|
</I>><i> >> >> using for the next version of Zcash. In which case you will be able
|
|
</I>><i> to
|
|
</I>><i> >> >> leverage our Sapling crypto code once it is more mature over the next
|
|
</I>><i> >> >> month or so. <A HREF="https://github.com/zcash-hackworks/sapling-crypto">https://github.com/zcash-hackworks/sapling-crypto</A>
|
|
</I>><i> >> >>
|
|
</I>><i> >> >> Sean
|
|
</I>><i> >> >>
|
|
</I>><i> >> >> On Wed, Jan 3, 2018 at 1:02 PM, James Prestwich via zapps-wg
|
|
</I>><i> >> >> <<A HREF="/mailman/listinfo/zapps-wg">zapps-wg at lists.z.cash.foundation</A>> wrote:
|
|
</I>><i> >> >> > I'd prefer sha256 or bitcoin-style hash160. I'm interested in a few
|
|
</I>><i> >> >> > different curves, including secp256k1. Eventually for EdDSA keys as
|
|
</I>><i> >> >> > well. Is
|
|
</I>><i> >> >> > there a list of supported curve operations?
|
|
</I>><i> >> >> >
|
|
</I>><i> >> >> > On Wed, Jan 3, 2018 at 12:57 PM Andrew Miller <
|
|
</I>><i> <A HREF="/mailman/listinfo/zapps-wg">soc1024 at illinois.edu</A>>
|
|
</I>><i> >> >> > wrote:
|
|
</I>><i> >> >> >>
|
|
</I>><i> >> >> >> Thank you so much for expressing your question in
|
|
</I>><i> Camenisch-Stadler
|
|
</I>><i> >> >> >> notation! That makes it very clear what you're going for.
|
|
</I>><i> >> >> >>
|
|
</I>><i> >> >> >> What hash function H do you have in mind, would SHA2 work? Also
|
|
</I>><i> what
|
|
</I>><i> >> >> >> group
|
|
</I>><i> >> >> >> G do you have in mind, secp256k1?
|
|
</I>><i> >> >> >>
|
|
</I>><i> >> >> >> If so, I do not know of any existing implementation of secp256k1
|
|
</I>><i> >> >> >> operations specifically in libsnark, so that would presumably be
|
|
</I>><i> the
|
|
</I>><i> >> >> >> biggest
|
|
</I>><i> >> >> >> challenge.
|
|
</I>><i> >> >> >>
|
|
</I>><i> >> >> >>
|
|
</I>><i> >> >> >> On Jan 3, 2018 1:47 PM, "James Prestwich via zapps-wg"
|
|
</I>><i> >> >> >> <<A HREF="/mailman/listinfo/zapps-wg">zapps-wg at lists.z.cash.foundation</A>> wrote:
|
|
</I>><i> >> >> >>
|
|
</I>><i> >> >> >> I'd like to participate in the setup ceremony.
|
|
</I>><i> >> >> >>
|
|
</I>><i> >> >> >> I also have an app I'd like to build using a zk-proof of knowledge
|
|
</I>><i> >> >> >> of
|
|
</I>><i> >> >> >> an
|
|
</I>><i> >> >> >> ECC private key. {(a) : A = a * G, B = H(a)}. Can anyone point me
|
|
</I>><i> to
|
|
</I>><i> >> >> >> good
|
|
</I>><i> >> >> >> resources on getting started?
|
|
</I>><i> >> >> >>
|
|
</I>><i> >> >> >>
|
|
</I>><i> >> >> >
|
|
</I>><i>
|
|
</I>><i>
|
|
</I>><i>
|
|
</I>><i> --
|
|
</I>><i> Andrew Miller
|
|
</I>><i> University of Illinois at Urbana-Champaign
|
|
</I>><i>
|
|
</I>
|
|
</PRE>
|
|
|
|
<!--endarticle-->
|
|
<HR>
|
|
<P><UL>
|
|
<!--threads-->
|
|
<LI>Previous message (by thread): <A HREF="000164.html">[zapps-wg] Powers of Tau participation + zk proof question
|
|
</A></li>
|
|
<LI>Next message (by thread): <A HREF="000159.html">[zapps-wg] Powers of Tau participation + zk proof question
|
|
</A></li>
|
|
<LI> <B>Messages sorted by:</B>
|
|
<a href="date.html#165">[ date ]</a>
|
|
<a href="thread.html#165">[ thread ]</a>
|
|
<a href="subject.html#165">[ subject ]</a>
|
|
<a href="author.html#165">[ author ]</a>
|
|
</LI>
|
|
</UL>
|
|
|
|
<hr>
|
|
<a href="/mailman/listinfo/zapps-wg">More information about the zapps-wg
|
|
mailing list</a><br>
|
|
</body></html>
|