Make it Bulletproof

An-depth breakdown of Zero-Knowledge Proofs and Benedikt Bünz’s brainchild.

Let’s say it’s 2030 and every single institution now uses distributed ledgers as a database. Everything’s working as it should; auditing is quick and easy because it’s so easy to trace back mistakes, there’s no more central point of failure, important private information is less vulnerable to attack, and there’s real-time transparent updates of the network’s state.

Wait, rewind that.

Real-time transparent updates of the network’s state? Wouldn’t that mean that if a company were using a blockchain as their underlying database, the salary of every single employee could be easily viewed and traced through history?

Well, not as easily as you might think, because distributed ledgers like blockchain are, after all, pseudo-anonymous. However, since most people re-use addresses, it’s a lot easier than it should be to trace transaction graphs and associate transactions back to the individual. So we can see that this becomes a huge liability in a corporate setting where employees will want to keep their compensation private.

This isn’t the only case where the complete transparency of blockchain becomes rather inconvenient; the truth of it is that, while criminal actors will always be willing to splurge on a guarantee of privacy regardless of the transparency of the network, it’s simply not a priority for average people like you and me to gather up the money to pay for that kind of anonymity.

So how do we fix this?

Humble Beginnings

One of the first steps to better confidentiality was taken by Gregory Maxwell’s Confidential Transaction proposal for Bitcoin, where the inputs and the outputs of each transaction are cryptographically encrypted so that the true values cannot be seen. This keeps the amounts transacted secret, which decreases a lot of risk for people, especially those who are moving large sums.

Confidential Transactions are facilitated by something called Petersen commitments, which essentially allow you to commit to a certain value without necessarily revealing that value to anyone until you choose to do so. Petersen commitments operate under the discrete logarithm problem, which is a type of one-way computation. In other words, it’s totally infeasible to compute the input from the output. This not only makes Petersen commitments really tough to crack, thus keeping your value safe, but also forces the person sending the transaction to commit to that value, thus binding them to that commitment.

What’s awesome about Confidential Transactions is that they’re homomorphically encrypted, which means you can perform different operations (like adding and subtracting) on the encrypted values but have the true result still be computationally correct. This gives a lot more freedom and flexibility to different institutions looking to adopt blockchain.

Unfortunately, because there’s so much added bulk after you encrypt all these transaction inputs and outputs, Confidential Transactions are super heavy. This is a huge problem if we want to implement them, as one of Bitcoin’s major problems right now is scalability. Confidential Transactions as they are right now will also cause many problems for people running nodes on lower-end hardware. Not only that, but they make it really difficult to verify the validity of each transaction.

Beyond Confidential Transactions, zkSNARKs are also another, more complete, potential solution to the privacy problem. They hide not only the transaction amounts but also the senders and the recipients themselves — it’s the proof of knowledge protocol that projects like Zcash have implemented. They also allow you to verify all these transactions without needing to know what the transactions really were to begin with.

So what are they really? zkSNARK stands for Zero-Knowledge Succinct Non-Interactive Argument of Knowledge. Whew! That was a mouthful; let’s break that down.

Zero-knowledge proofs are the basis of what we’ll be looking at today; they’re important because they allow anyone to prove that a certain piece of information is valid without actually having to show what that piece of information was.

Imagine a zero-knowledge proof as a situation where you want to prove to your colour-blind friend that you know the colour of each of the two pens you’re holding — without actually revealing which one is what colour. You give the pens to your friend, and ask them to hide the pens behind their back. Your friend will switch the pens from hand to hand or keep them in the same hands as they wish, and bring them back out to ask you if they’ve switched the pens or not. At first, if you were also colourblind you’d have a 50% chance of guessing correctly; however, the possibility to guess correctly slims down at a really fast pace until you’re in the decimals of probability in later rounds.

The succinct part tells us that the proofs themselves are really, really fast and really, really small; think in the scale of mere milliseconds and bytes. This is important for protocol implementation, because as I’ve mentioned previously, one of blockchain’s biggest issues right now is scalability and speed. We need every aspect of the technology to be as efficient and compact as possible.

Lastly, the very first zero-knowledge proofs needed multiple rounds of back-and-forth between the prover and the verifier (as you can see in the diagram above) to be able to validate a certain piece of information, but the keyword non-interactive here shows that zkSNARKs actually consist of one single interaction between the prover and the verifier, which is part of why they can be so tiny.

So zkSNARKs sound pretty much like the complete package — they’re fast, zero-knowledge, and from a user’s point of view, relatively simple. Unfortunately, as with anything in this space, there’s a catch; zkSNARKs require a preprocessing method called a trusted setup. The trusted setup is what allows zkSNARKs to be succinct in the first place, but it’s also their greatest weakness.

Before we start, let me introduce to you my friends Peggy the Prover, Victor the Verifier, and Tiana the Trusted Party. They’ll help guide us through these following breakdowns.

To replace the interactive challenge/response protocol of previous zero-knowledge proofs (that were just back-and-forths between Peggy and Victor), in zkSNARKs a new character is introduced — Tiana. Tiana sits between Peggy and Victor. She encrypts all new incoming queries with a special secret key before passing on the garbled messages to Peggy, who performs some impressive computations on the encrypted queries to make a short proof of the validity of the query.

While Peggy’s doing that, Tiana users another short verification key to encrypt the answers to the query, and passes on those answers to Victor. Victor takes these short answers together with Peggy’s short proof and is quickly able to verify the validity of Peggy’s proof. Every time after each interaction, Tiana has to destroy both the initial secret keys and the verification keys so that no repeated forgery of transactions with these two keys can happen.

You can sort of see the problem here: what if Tiana was actually feeling a little malicious that day and decided to secretly keep the keys after the transaction and continue on to use them to prove and verify her own transactions? This is a big problem; because of this setup, each person needs to trust that this third party will effectively destroy all these secret keys once the interaction is complete. Because these keys not only help create the proofs for the transactions, but also help to verify them, if they remain in the wrong hands they can be used to forge transactions with fake verifications, allowing that individual to make currency out of thin air — without anyone ever knowing.

So with Confidential Transactions we got computationally heavy privacy, with zkSNARKs we get short zero-knowledge proofs that require a little too much trust to be completely secure. What now?

Bang Bang, Bulletproof

Before we throw ourselves into the details of how these work, let’s talk about why exactly Bulletproofs are so exciting. Bulletproofs combine the best of both worlds of zkSNARKs and Confidential Transactions; they’re smaller than CTs, don’t need trusted setups, and allow for zero-knowledge verification of transactions. In fact, they’re so good that Monero actually released an upgrade with Bulletproofs implementation just this October 18th. Not to mention, because Bulletproofs are a lot smaller than nearly anything we’ve seen before, Monero’s fees have fallen by 96% as a result. This is awesome news!

At a very base level, just like zkSNARKs, Bulletproofs are zero-knowledge proofs of knowledge, specifically a type of range proof. Range proofs verify that a certain committed value exists within a certain range without necessarily revealing any real information about the value. So fundamentally, Bulletproofs really give a probabilistic result.

Digging deeper, Bulletproofs operate under the discrete logarithm assumption (which means you assume the difficulty of cracking discrete logarithm problems is near impossible), vastly reducing their size. They also leverage the Fiat-Shamir heuristic, which is a method that essentially collapses multi-round challenge/response zero-knowledge protocols into one single non-interactive proof, which is what we need to keep things light. As compared to the Trusted Setup that zkSNARKs use, this is a more trustless method. Let’s take a closer look at how this elegant solution works!

Non-Interactive Proofs and the Fiat-Shamir Heuristic

I’m gonna bring in Peggy and Victor again to make this a little more digestible.

So Peggy has this transaction that she wants to have Victor validate. She hashes the transaction, getting a value x, and then takes a base g, putting it to the power of x. So we have something like this: y = g^ x, where the transaction hash becomes the discrete logarithm of y base g.

Easy to compute, hard to crack.

Peggy then takes a random number v, and computes t = g^v. After that, she finally hashes g, y, and t all together to obtain a value c. She’s not done yet! Peggy whips out her calculator to compute the following:

After this tedious four-step computation, she finally sends over her proof pair (t, r) to Victor to have him verify it, and for him it’s as easy as simply making sure that the following is true:

How does this one single operation prove that Peggy’s proof was valid? It’s because the math checks out:

So as a general rule, these kinds of proofs based on the Fiat-Shamir heuristic will take the longest time to prove, but are really fast when it comes to verification. The process might seem complex, but in reality we’ve essentially condensed the original zero-knowledge proof process of three separate back-and-forths between Peggy and Victor to just one single interaction.

How it Sizes Up

So Bulletproofs seem great and all, but how do they really compare to all the other zero-knowledge protocols out there today? And there has to be a catch somewhere, right? Right. So before we take a look into Bulletproofs’ downsides, let’s throw out some quick numbers:

Final Takeaways