Bulletproofs: The New Kid in Blockchain Security Land

Last night, news broke that Monero will be implementing a new and more scalable privacy protocols as part of its blockchain. Bulletproofs, was originally published in a 2017 whitepaper from Stanford University and quickly became an area of research within the blockchain community. With the announcement, Monero becomes the first cryptocurrency to adopt bulletproofs as a privacy protocol. Just like predecessors such as zk-SNARKS or Secure Multi-Party Computations, bulletproofs has all the ingredients to become one of the most important privacy protocols in the next wave of blockchain applications.

Bulletproofs is not necessary a breakthrough in cryptography but rather a very clever combination of existing techniques. Specifically, bulletproofs has its origins in another privacy protocol such as confidential transactions and zero-knowledge-proofs. In fact, the easiest way to understand bulletproofs is to analyze the evolution of these two other cryptographic methods.

Confidential Transactions and Zero-Knowledge-Proofs

If we think about the steps required to validate a cryptocurrency transaction, they can be summarized in three steps:

· Signatures are Correct: The transaction comes from a valid node.

· Amounts are Unspent: There is no double spending issues.

· The Sum of the Inputs is Greater than the Sum of the Outputs: Specifically: Outputs = Inputs — Transaction Fees.

While all cryptocurrencies have a way to validate transaction correctly, most do so maintaining public access to the information. In 2016, Greg Maxwell introduced the notion of confidential transactions which effectively replaces the amounts of the transactions with cryptographic commitments that can be verified by the receiver. The cryptographic assertion is typically based on Pedersen commitments which is a method that can express a statement about a value that can be verified while hiding the value itself. Confidential transactions certainly enable secure transactions with verifiable signatures and unspent amounts but make it impossible for the recipient to verity that the amounts of the inputs is greater than the amounts of the outputs. That’s where zero-knowledge-proofs come to play.

Zero-knowledge-proofs of knowledge expand confidential transactions by allowing the recipient to challenge the sender to prove a specific assertion. While this technique is incredibly effective from the privacy standpoint, they drastically increase the size of the transaction and, very often, require a trusted setup which difficult its applicability at scale. STARKs is trying to address some of these limitations but remains not very viable practically. Enter bulletproofs.

What are Bulletproofs?

Conceptually, bulletproofs can be considered a more efficient form of zero-knowledge-proof that does not require a trusted setup. Bulletproofs are a new zero-knowledge argument of knowledge system, to prove that a secret committed value lies in a given interval. To achieve that, bulletproofs leverages some of the optimization methods proposed by Jonathan Bottle to implement space efficient zero-knowledge-proofs. Bottle was able to create proof-size that grew logarithmically instead of linearly. However, many of the assumptions behind Bottle’s thesis also resulted impractical.

Bulletproofs improves on some of Bottle’s ideas to create short, non-interactive zero-knowledge proofs and even more efficient form of zero-knowledge-proof that does not require a trusted setup. Bulletproofs are, effectively, a much more efficient and secure form of range proofs that utilize zero-knowledge proofing methods as seen in zk-SNARKS and STARKs, but do not require the trusted setup as required with zk-SNARKS and are not as large as STARKs.

Bulletproofs are more generic than some of its predecessors and can be used, in theory, to prove any arbitrary statements. The logarithmic-size complexity increments of bulletproofs means that they are substantially more efficient than other techniques. For instance if we need additional t proofs, the complexity of the algorithms will increase additively by a factor of log(t) instead of linearly 10 times. The following image clearly illustrates that concept.

Another advantage of bulletproofs is that it can be used in multi-party environments by leveraging multi-party-computation(MPC) models. Specifically, bulletproof MPC is a variation of the protocol in which a proof can be constructed from different parties using a constant number of rounds.

Bulletproofs represents a faster, nimbler and more robust alternative to other blockchain privacy methods. Monero’s implementation is certainly a step towards making bulletproofs more widely adopted within the blockchain community but we should expect more implementation to be available soon.