What Are Bulletproofs? w/ Jonathan Bootle (zk-SNARKS, Monero, Zcash, and PIVX)

In this video, we sit down with Jon Bootle, who invented a faster and more efficient form of zero-knowledge proofs (one which does not require a trusted setup). Privacy coins from Monero to PIVX have voiced plans to integrate the new technology, which is a major security and speed upgrade.

➜ Coin Crunch: https://coincrunch.io
➜ Coin Crunch Mastermind Group: https://www.facebook.com/groups/coincrunch/
➜ Our telegram channel: https://t.me/coincrunch
➜ Coin Crunch Announcements Channel - https://t.me/coincrunchannoucements
➜ The Crunch Podcast: https://itunes.apple.com/us/podcast/the-crunch/id1363950785

Based on a 2016 improvement in the space efficiency of discrete-log based zero knowledge proofs from Jonathan Bootle and others, Bulletproofs are an even more space efficient form of zero-knowledge proof. Importantly for our purposes, these proofs also have native support for committed values such as Pedersen commitments and public keys. This lets us implement things such as rangeproofs in this general zero-knowledge framework without implementing the heavy machinery of elliptic curve arithmetic in zero knowledge.

Stronger.

To limit the size of transactions, our old rangeproofs constrained outputs to be in a range of size 2^32. This limited outputs to about 43 BTC, though this could be increased by reducing the granularity of proofs from 1 satoshi to 10 or 100, or by increasing the minimum value from zero. These adjustments were possible but used explicit amounts, limiting the privacy provided by the system.

These 32-bit rangeproofs were approximately 2.5 KiB in size. With Adam’s optimization they would have been 2 KiB in size. With Bulletproofs, they would have been 610 bytes. With such small sizes, we might as well double the range to 64 bits, eliminating the need for any non-private adjustments. This would increase the paltry 610 bytes to 1220, right? Nope. In fact, a 64-bit Bulletproof rangeproof is only 674 bytes.

Smaller.

The reason that we can double the range size while adding only 64 bytes to the proof size is that they grow logarithmically in size. This is done using a variant of a the inner product argument from the Bootle et al 2016 paper. (Jonathan Bootle also helped Benedikt and Dan develop Bulletproofs). Specifically, the logarithmically-sized inner product argument described in that paper was reduced even further in Bulletproofs from 6log(N) curvepoints to 2log(N).

This same trick allows aggregation of multiple rangeproofs within a transaction into one, again with only a small size increase. An aggregate of two rangeproofs would be 738 bytes, of four would be 802, and of eight would be 866. Eight 64-bit classical rangeproofs would be over 40000 bytes!

Faster.

This space savings is great, but our initial analysis of the technique showed that verification would be slower than the old rangeproofs. It appeared that verification of a single 64-bit proof would require more than 200 scalar-point multiplications, each one an onerous 50-microsecond affair, while the old rangeproofs needed only 128.

But after further analysis, we were able to combine many of the multiplications, reducing the total number to only 147. More importantly, we realized that unlike the old rangeproofs, none of these multiplications depended on each other, and we could do them all in one big batch. As part of our work on aggregate signatures, we knew how to batch-multiply very quickly. Pieter Wuille, Greg Maxwell, Jonas Nick, Peter Dettman and myself had spent several months on this problem and had reduced the speed of 147 multiplications to only 15.5 microseconds each, getting the total verification time of a Bulletproof down to 2.3 ms, vs 5.8 ms for the old proofs.

This is already more than a doubling in speed, but because our batch-multiplication gets faster the more points you give it, the performance numbers for aggregates are even more impressive. An aggregate of eight 64-bit Bulletproofs can be verified in only 11.5 ms, vs 46.8 ms for the old proofs, more than quadrupling the speed.

But it gets even better. Bulletproofs