Bulletproofs

[Kixunil]

A new paper about range proofs showed up recently. Is this applicable to grin? Any plans to implement it?

[ignopeverell]

Sorry, I just realized that most of the discussion about this happened on Gitter. It's definitely applicable and a great optimization to make our transactions a lot smaller. I believe Andrew et al. are already looking at an implementation on top of secp256l1.

[0xb100d]

Saw this talk at Scaling Bitcoin couple weeks ago... bulletproofs are amazing, and having been off the gitter for a few days really excited to hear Andrew is working on them!

Sent with ProtonMail Secure Email.

-------- Original Message -------- Subject: Re: [mimblewimble/grin] Bulletproofs (#273) Local Time: November 15, 2017 12:34 PM UTC Time: November 15, 2017 8:34 PM From: notifications@github.com To: mimblewimble/grin grin@noreply.github.com Subscribed subscribed@noreply.github.com

Sorry, I just realized that most of the discussion about this happened on Gitter. It's definitely applicable and a great optimization to make our transactions a lot smaller. I believe Andrew et al. are already looking at an implementation on top of secp256l1.

— You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub, or mute the thread.

[sesam]

Interested readers - if the paper feels hard to digest, maybe also try this article https://joinmarket.me/blog/blog/bulletpoints-on-bulletproofs/ that was well liked by some developers.

[yeastplume]

Based on https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2017-December/015346.html and https://github.com/ElementsProject/secp256k1-zkp/pull/16, we may even consider moving the target for this to testnet2?

Single commit bullet proofs appear to be working, which is all we need. The only think I think we're missing here from being able to use this implementation is the ability to store an amount within the rangeproof (for wallet reconstruction).

From conversations with @apoelstra earlier, I believe it's possible to store 64 bytes worth of 'message' (not nearly as much as the current range proofs). We also need to be aware that we can't rely as much on the message hiding properties of range proofs when switching to bullet proofs.

[antiochp]

Looks like @apoelstra's been busy - probably why we haven't much from him these past couple of weeks... 😃

[apoelstra]

@yeastplume are you intending to store the amount in the rangeproof, so should I add that capability to the libsecp implementation? Aggregation seems to break it so we're going to need to come up with a different solution for Elements..

You're correct that the single-output case is done (sans review!!!) which is all that Grin needs, even in the multi-asset case.

[yeastplume]

@apoelstra the amount, and quite possibly the switch commitment hash as well (or just a hash of the entire output) as per https://github.com/mimblewimble/grin/issues/207... If you could add something to let us put as much data as possible in there, that would be great!

With that in place we'd basically have everything we need to implement this (sans review, of course)

[apoelstra]

Ok, I can get you 64 bytes without much trouble (xoring them into tau_1 and alpha which are easy to extract from tau_x and mu if you know the original seed used to produce the randomness).

I think it's possible to get another 32 bytes into t but that's way more involved since t is a big inner product.

[yeastplume]

Great, 64 should be plenty for now, easily enough for a u64 amount and a hash with some room left over for something else if the need comes up. Thanks!

[sesam]

ping @apoelstra what's the status of bullet proofs in libsecp256k1? During grin dev meeting we just discussed that there might be people interested in testing out that functionality and prepare to add it to grin.

Yeastplume 22:16 It will have to be integrated into our libsecp fork.. that work can more or less start, but I need to ask @apoelstra about where it is. We still need to be able to hide some data into them, most importantly amounts for wallet reconstruction.

[apoelstra]

@sesam my working tree is at https://github.com/apoelstra/secp256k1-mw/tree/bulletproofs though it's a bit of a mess and I'm still force-pushing it from time to time.

Preliminary numbers are that with endomorphism optimization on, 64-bit verification takes 3883us on my benchmark machine (which is throttled to 2Ghz, my laptop takes about 2.4ms for this). You can batch verify additional proofs for a marginal cost of 542us per. And there are still optimizations to come. Contrast the Borromean proofs which took 10368us per 64-bit proof.

My code is not reviewed at all and needs to be restructured significantly before it's production-ready. But it's there if you want to look at it.

[yeastplume]

Just an update, I've incorporated @apoelstra's current version into our fork and added rust bindings to the prove/verify functions within. I've also marked them off as deprecated (as I did the aggsig functions) to make sure nobody forgets this is experimental. Like most of the added functionality required for MW, the module is fairly contained so it shouldn't be too much of an issue to keep it up to date. Grin only needs a proof for a single commit at a time, so that makes things much easier.

https://github.com/mimblewimble/rust-secp256k1-zkp/commit/ede955b70c7b642ee2c24194abbb30fcf388494d

I'd merged a different version of the ec_mult while doing aggsig which expect an error callback and some other minor changes, so I had to change the functions to accept the full secp256k1_context and not just a mult context, but the changes are minor. basic tests all pass, extended tests don't compile for some reason but not too worried about that at the moment, as this is more about integration.

I've done up some tests in rust which work as expected, and produce proofs of 674 bytes, and all existing rust data structures can more or less be used as is, so changes on Grin side should be minimal.. the only thing we're missing is the ability to pass a message in when generating the proof, and a method to unwind it. As outlined above, we just need to store the amount in there to ensure wallet reconstruction keeps working. Once that's in place, it should be a relatively quick matter to integrate into Grin for testnet2, (and it's understood the underlying implementation still needs review and work).

[yeastplume]

Merged, I'm going to open separate issues for remaining work.