No announcement yet.

Bulletproofs for dummies

  • Filter
  • Time
  • Show
Clear All
new posts

  • Bulletproofs for dummies

    Click image for larger version  Name:	IMG_20190825_170344_641.jpg Views:	0 Size:	181.2 KB ID:	125
    Zero-Knowledge Proofs
    Zero-Knowledge (ZK) proof, that has been used in cryptography since 1989, is a method by which one party (the prover) can prove to another party (the verifier) that they know a value x, without conveying any information apart from the fact that they know the value x. As there is a hard math behind this concept, I decided to explain it by three real-world examples so that non-technical people can understand.

    Interactive Zero Knowledge Proof

    Example 1:

    Imagine that you have two pens, one red and one blue, and want to prove to a colorblind person that you indeed have different-colored pens. Give the pens to the other person and make them hold one in each hand. Then let them put them behind their back and shuffle them, or not. When they show them to you again you can tell them if the shuffle was done or not. Of course, you could have guessed and would have had a 50% probability of guessing right. But by doing this multiple times the probability that you guess diminishes. After n correct identifications the probability that you guessed is 0.5^n and we can establish confidence that you can identify one pen from the other.

    There are three key properties for a zero-knowledge protocol:

    1. Correctness: Both parties must be honest.

    2. Soundness: If you don’t know the secret you can’t prove it.

    3. Zero-knowledge: If the protocol is followed nothing new is learned.

    For our pen example notice that no information about which pen is red or blue is leaked. Only that they are distinguishable. In the real world, the pens are replaced by a digital commitment scheme. This allows one party to commit a given message but keeping it secret by encrypting it and later giving everyone the key to decrypt the message.

    Example 2:

    There is a cave with a single entrance but with two interconnected tunnels that form a ring. In the ring, there is a locked door on the opposite side of the entrance which opens when some secret code is input on its puzzle-lock.
    Click image for larger version  Name:	IMG_20190825_170340_547.jpg Views:	0 Size:	41.7 KB ID:	126
    The above figure shows the layout of this cave. Peggy, wearing a pink shirt in the figure , knows the puzzle-lock secret and she, as prover, wants to demonstrate to the verifier Victor, who is wearing the green shirt, that she knows the code that unlocks the door but without revealing the secret code itself. To proceed with this proof, they engage in the following protocol:

    • Peggy enters the cave from one of the two tunnels to the ring, A or B, while Victor waits outside.

    • Then, Victor goes to the cave entrance and shouts to Peggy, asking her to leave the cave from either side A or B. Victor must choose his exit request randomly.

    • If Peggy is on side B and Victor requested exit through side A, she can open the door and leave the cave from the right side. Otherwise, she can just leave the cave from the same side B.

    The point is that if Peggy knows the door secret, she should always be able to satisfy Victor’s exit request regardless of what Victor chooses. Because there is a 50% probability that Victor will request Peggy to exit from the same side that she entered from, Peggy may get lucky and satisfy Victor’s requests without actually knowing the secret code. However, if request for exit side is truly random, and the protocol is repeated enough times, the probability of Peggy satisfying all of Victor’s requests without knowing the secret becomes vanishingly small.
    Click image for larger version  Name:	IMG_20190825_170337_183.jpg Views:	0 Size:	39.2 KB ID:	127
    The above Figure shows the typical structure of interactive zero-knowledge proofs. This structure, also known as Sigma protocol, comprises of three communication steps between prover and verifier:

    1. Commitment: Prover commits to a particular value and transfers the commitment to the verifier. In the cave story, this step is equivalent to Peggy choosing one of the two sides to enter the cave, and letting verifier know once she has entered the cave.

    2. Challenge: Verifier sends a random challenge to the prover. This step is equivalent to Victor challenging Peggy to exit from one of two sides chosen at random.

    3. Response: Prover computes a response based on the challenge and witness, and sends it to verifier for the task of verification. This step corresponds to Peggy leaving the cave from the side requested by Victor given her secret knowledge. Victor, waiting at the mouth of the cave, can check whether Peggy returns from the requested side.

    ​However, Interactive Zero Knowledge has an important problem: it is still a 2-round protocol in which the two parties have to communicate. We would like no communication between the prover and verifier. With cryptography, this is no longer necessary, as it enables non-interactive proofs like Bulletproofs that are validated by a complex arithmetic circuit.

    ​Non-interactive Zero Knowledge Proof

    Alice wants to prove to Bob and his snooty Sudoku club that she has solved a Sudoku puzzle they have not been able to solve.
    Click image for larger version  Name:	IMG_20190825_170333_372.jpg Views:	0 Size:	44.0 KB ID:	128
    To do so, Alice builds a tamper-proof machine that executes the proof to Bob and friends. Alice’s machine follows a specific, publicly verifiable protocol with the following logic.

    1. First, Alice reproduces the original, unsolved puzzle in the machine. For each cell with an existing value, it automatically lays three face-up cards with the corresponding number, e.g. cell C3 has 3 number 9 cards.
    Click image for larger version  Name:	IMG_20190825_170329_608.jpg Views:	0 Size:	58.8 KB ID:	129
    2. Next, Alice encodes her solution by having the machine lay her answers face down on the grid. Of course, the machine prevents Bob from simply flipping over the cards in their cells.
    Click image for larger version  Name:	IMG_20190825_170325_949.jpg Views:	0 Size:	94.8 KB ID:	130
    3. Bob can now interact with the machine. Starting with each row, Bob randomly chooses one card in each cell, from the top, the middle, or the bottom.
    Click image for larger version  Name:	IMG_20190825_170311_552.jpg Views:	0 Size:	91.4 KB ID:	131
    The machine takes the chosen cards and makes a face down, 9-card-packet for each row.

    This action is repeated for each column as well. Finally, the remaining cards are sorted into one packet for each 3x3 grid. In total, the machine makes 27 packets.

    ​4. Then the machine randomly shuffles the cards in each packet, before giving the packets back to Bob.

    ​5. Bob flips the cards over and verifies that each packet contains the numbers 1 through 9 without any numbers missing or duplicated.
    Click image for larger version  Name:	IMG_20190825_170307_339.jpg Views:	0 Size:	15.6 KB ID:	132
    A few verification rounds later, Bob and friends are convinced that Alice has solved this puzzle.

    ​In this example, the proof is non-interactive. Any one can use the machine (or in reality, code) to verify Alice’s claim. Alice doesn’t have to be present to be challenged.


    In order to understand bulletproofs, we first need to understand what a range proof is:

    "A range proof allows anyone to verify that a commitment represents an amount within a specified range, without revealing anything else about its value.”

    Bulletproofs are a more efficient form of range proofs. Bulletproof is a new implementation of the non-interactive zero-knowledge proof protocol that requires no trusted setup. It is based on a 2016 improvement in the space efficiency of zero-knowledge proofs from Bootle et al. A Bulletproof can be used to convince a verifier that an encrypted plain text is well formed. For example, prove that an encrypted number is in a given range, without revealing anything else about the number. Compared to SNARKs, Bulletproofs require no trusted setup. However, verifying a Bulletproof is more time consuming than verifying a SNARK proof.

    Bulletproofs are designed to enable efficient confidential transactions in Bitcoin and other cryptocurrencies. Confidential transactions hide the amount that is transferred in the transaction. Every confidential transaction contains a cryptographic proof that the transaction is valid. Bulletproofs shrink the size of the cryptographic proof from over 10kB to less than 1kB. Moreover, Bulletproofs support proof aggregation,so that proving that m transaction values are valid adds only O(log(m)) additional elements to the size of a single proof. If all Bitcoin transactions were confidential and used Bulletproofs, then the total size of the UTXO set would be only 17 GB, compared to 160 GB with the currently used proofs.

    DAPS uses Bulletproofs as range proofs to prove transaction amounts in the transaction are positive. This is critical because secp256k1 works under a circle space number and there is no way that a full node can verify that the encoded amounts are always positive. Without Bulletproofs checking transaction amounts are positive, an attacker can create a transaction with a UTXO having huge positive amount while the other UTXO having a negative amount and the sum of these two amounts plus transaction fees equal to the sum of inputs, which result in bypassing the RingCT check.


    ​[1] H. A. Estensen, “A comparison of Monero and Zcash”, June 13, 2018

    ​[2] “Zero knowledge proofs applied to auctions”, S. Kumari, May 16, 2019

    ​[3] “Understanding Zero-knowledge proofs through illustrated examples”, Nicole Zhu, April 9, 2019

    ​[4] DAPS whitepaper,​​
    Last edited by crypto_enthusiast; 25 August 2019, 02:07 PM.