From Zero Knowledge Proofs to Bulletproofs Paper

Posted by: Adam Gibson | in Cryptography | 2 years ago | 2 comments

I've spent the last few weeks working on this paper, which comes out of my own desire to understand the technical underpinnings of Bulletproofs (see my previous post). It ends up being a walkthrough of sections of three academic papers, with "Asides" along the ways about various supporting concepts like Commitments and Zero Knowledge Proofs.

This is to be considered just a first version, I intend to move it to github (once I've figured out some format conversion issues), and I'm very happy to receive some comments and corrections from anyone out there so inclined (message me on IRC or twitter).

Thanks to Andrew Poelstra for helping me get started in understanding this (it's kind of intimidating/overwhelming at first, part of why I wrote the doc), and also to Jonas Nick who I discussed some details back and forth with. And of course thanks to all the authors of the three papers under discussion :)

Edit: Now hosting this in .tex and pdf at https://github.com/AdamISZ/from0k2bp ; forgive some glitches here and there, updates will occur as and when; please open an issue if you have a correction, question or comment on the paper. Thank!

For historical reference, first version of the paper:

Link to Version 1 pdf

Current rating: 5

Comments

Xun Li 6 months, 1 week ago

Hi Adam! Thank you for the great writeup about Bulletproof and Confidential Transactions! I have one question about CT after reading your CT paper. (couldn't find a CT blog post, so just commenting here)
Specifically, the paper referred to the ring signature, where if we want to prove a number if between [0, 99], we could think of a table of 100 cryptographers and all we need is to prove that one of them signed. This means that if we want to prove a number is between [0, 2^32 - 1], we need 2^32 cryptographers forming a single ring. How does this transform to the solution where we only need 32 rings each containing 2 people representing 0 and 1?

Link | Reply
Currently unrated

waxwing 5 months, 1 week ago

Hi,
Thanks for your comment.

The simple answer is encoding.

Just as we don't need 1000 characters to display the number 1000, but only 4, so we can do something similar here:

Each digit is obfuscated with a ring signature, and we just have to agree in advance what base the number is represented in.

So if we agree to use base 4, we can represent the number 265 = 1*256(=4**4) + 2*4(=4**1) + 1 * 1 (= 4**0). So it's 10021 in base 4. We use a separate ring signature for each digit. THere's a lot of detail about this in the CT paper.

Link | Reply
Currently unrated

New Comment

required

required (not published)

optional