Bulletproofs In Crypto – An introduction to a Non-Interactive ZK Proof
Bulletproofs In Crypto – An introduction to a Non-Interactive ZK Proof

Table of Contents:

"Short like bullets, yet offering bulletproof security assumptions". With these words, Shashank Agrawal's named the technology that played an essential role in stabilizing blockchain privacy solutions.
Although Agrawal's epic caption meant that this new technology earned the name bulletproofs, it does not explain why they’re safe, useful, and necessary for the blockchain industry. Let’s have a look at the concept of bulletproofs, how they work, and their applications.

Introduction: It all started with CTs and range proofs

During Bitcoin's early years, one of its selling points was a promise of anonymity to users. The popular belief, which was motivated both by the time’s misconception of Bitcoin’s capabilities and lack of chain analysis techniques, was that you could send and receive Bitcoin and interact with the network without leaving a digital footprint traceable to your real-world identity. Of course, many accepted the somewhat erroneous concept as a fact, but it all came undone as innovative efforts began to link people's real-world identities to their on-chain activity. Law enforcement agencies could suddenly trace transactions by uncovering the identities behind alphanumerical public keys.

As it became clear to all that Bitcoin's transparency meant that it could not offer absolute confidentiality, people began to devise ways to get around loopholes to achieve privacy. Coin mixers or tumblers were one of the earliest endeavors, but one of the most successful series of attempts came under the name of Confidential Transactions (CT).

In short, with Confidential Transactions, a user can send or receive funds without disclosing the values or addresses involved. However, due to the structural changes their implementation would imply, CTs never got integrated into the Bitcoin protocol. This is because they would prevent public validation of the blockchain. An observer could no longer verify that the number of Bitcoin arriving at one address equals the number of Bitcoin leaving another – one of the fundamental principles of the Bitcoin network.

Confidential Transactions obscure sender and receiver addresses. (Source)

And so range proofs were invented

Range proofs are a type of zero-knowledge proof system that helps determine whether a number is negative or positive without revealing its value. In essence, a range proof could solve the problem of proving that within a Confidential Transaction, the number of Bitcoin being transacted are within a required range without actually revealing the amount.

Regardless of their efficacy, attaching range proofs to every transaction effectively increases their size and impairs the efficiency of the verification and storage processes. Larger transactions mean higher gas fees and lower throughput, which do not bode well for any blockchain network.

However, a proposal in an academic paper changed everything.

What are bulletproofs?

In December 2017, the Stanford Applied Cryptography Group proposed the concept of bulletproofs, defining them as a novel zero-knowledge argument of knowledge that can prove that a secret lies within a given range. Bulletproofs are short, non-interactive zero-knowledge proofs that can convince a verifier that an encrypted value lies within a stated range without disclosing any information about the number.

Oleg Andreev’s stylized illustration of the Bulletproofs range-proof protocol. (Source)

Bulletproofs are a type of range proof that employs zero-knowledge proofing techniques similar to those seen in zkSNARKs and zkSTARKs. Like zkSTARKs, bulletproofs do not require an initial trusted setup ceremony or procedure. Also, they are smaller than zkSTARKs and have significant efficiency and security. However, as stated in the academic paper, it takes longer to verify a bulletproof than a zkSNARK proof.

Bulletproofs attracted for the edge they provided to verifying commitments in Confidential Transactions. Privacy blockchains like Monero were quite public about their switch to using bulletproofs, and they recorded up to an 80% decrease in transaction size and fees after implementing them.

How do bulletproofs work?

As established earlier, bulletproofs are both secure and non-interactive, and they achieve this through a discrete logarithm problem and the Fiat-Shamir heuristic. A discrete logarithm problem is a type of one-way computation which makes it totally infeasible to compute an input given only the output. This makes bulletproofs unbreakable with limited computing power i.e., creates an infeasibility assumption. This last concept underlies the basis of much of modern cryptography.

On the other side, the Fiat-Shamir heuristic takes an interactive zero-knowledge proof and creates a digital signature based on that proof. With the Fiat-Shamir heuristic, bulletproofs can power confidential transactions by becoming the digital signature of a previously established interactive proof of knowledge. The Fiat-Shamir heuristic also converts the interactive zero-knowledge proof to a non-interactive form (bulletproofs).

Bulletproofs derive their security from the infeasibility assumption of discrete logarithm problem, as mentioned above. While regular range proofs increase linearly in proportion to the number of transactions bulletproofs increase logarithmically in proportion to the size of the data to be verified. This makes bulletproofs more succinct and smaller in size.

Bulletproofs rely on Pedersen commitments, which allow zero-knowledge verification of values using a mathematical trick that reveals that the sum of the inputs is of a greater value than the sum of the outputs without disclosing any of the values. Pedersen commitments are cryptographic algorithms that allow a prover to commit to a certain value without revealing it or being able to change it.

Here's a long but great explainer video for bulletproofs

What makes bulletproofs so secure?

Bulletproofs offered a breath of fresh air to cryptographic protocols that utilized range proofs through two of their most significant characteristics.

Firstly, bulletproofs are short, so they take up much less storage space than other range-proofing systems. If a regular transaction with a range proof occupies 10KB worth of space, a transaction with a bulletproof could save up to 80% of that size, taking up only 2KB instead.

Comparison of bulletproofs against zkSNARKs and zkSTARKs. (Source)

Secondly, bulletproofs are non-interactive zero-knowledge proofs, requiring no interaction between prover and verifier. Their non-interactive nature means that they could be proved in a single exchange, unlike interactive zero-knowledge proofs that require constant back-and-forth communication between both parties.

Also, bulletproofs do not need trusted setups. Zero-knowledge proofs that depend on trusted setups are subject to lingering concerns from users. Everyone involved in them needs to trust the participants involved in creating the parameters to destroy the keys (toxic waste) after the event. Failure to trash the toxic waste could lead to the malicious creation of new tokens, inflating the total token supply and endangering the ecosystem. With bulletproofs, there is no such concern.

Furthermore, bulletproofs are storage-saving and scalable, occupying less block space and allowing faster verification times than the average range proof. However, zkSNARKs and zkSTARKs require less verification time than bulletproofs.

Bulletproofs require no trusted setup because they rely on publicly generated algorithms that take advantage of mathematical principles to obfuscate inputs.

Range proofs vs. bulletproofs

Earlier, we mentioned that bulletproofs are a type of range proof. Not only are they a variation of the latter, but bulletproofs are also a significant improvement upon range proofs. To understand how they measure up to one another, we must first explain the concept of range proofs.

Range proofs

Range proofs were the earliest forms of commitment validations applied in Confidential Transactions. They provided a way for an individual to prove that a specific commitment is a value within a given range while withholding any information about the value and its worth. For instance, using a simple range proof, you could validate that the late Queen Elizabeth was born after the first World War and before World War II without disclosing her actual birth year.

Range proofs were primarily adopted by privacy-enhancing cryptographic protocols and used to obfuscate transaction amounts on networks like Monero. It’s worth noting that Monero has implemented an even more efficient range-proving system called Bulletproofs+. When you transfer coins on the Monero blockchain, for instance, Bulletproofs+ proves that your payment is a positive number without revealing how much you paid.

How bulletproofs improved on range proofs?

Range proofs were effective in shielding transaction amounts and offering privacy on publicly distributed ledgers. Yet, they had one shortcoming that rendered them impractical in the long run. According to the Stanford paper, when it was published, all implementations of confidential transactions used range proofs, and the proof size was linear in n.

Range proofs contain the number of outputs and bits that make up the range; hence, they scale linearly. Their linear scalability resulted in increased size, especially when verifying multiple transactions. Furthermore, range proofs are attached to every confidential transaction, making them larger than regular, unshielded transactions and a less sustainable long-term option for any cryptographic protocol.

At the time, all blockchain networks had fixed block sizes. A larger transaction size meant that fewer transactions would fit into a block. With increased adoption, the blockchain size would increase at a faster rate, limiting the ability of regular people to participate as nodes due to storage constraints.

Bulletproofs solved the storage problem with their less-than-1KB size, reducing transaction costs and size without compromising security. Also, with bulletproofs, a prover could aggregate several transaction range proofs for their corresponding outputs as a single proof. Instead of having a range proof for every transaction and their outputs, you can aggregate them all into one short bulletproof, saving space immensely.

Applications of bulletproofs

We have established that bulletproofs are short non-interactive zero-knowledge proofs that have shown tremendous promise towards reducing transaction size and costs, powering Confidential Transactions, and helping to aid blockchain privacy. Here are some applications of bulletproofs in cryptographic protocols:

Enabling confidential transactions

Perhaps the most popular application of bulletproofs is in confidential transactions. Notably, Monero uses bulletproofs to power its RingCT technology. They switched from using Schnorr signatures and Borromean ring signatures to lightweight bulletproofs. The initial ring signatures were effective, but they increased the size of an average RingCT exponentially.

After incorporating bulletproofs into the Monero network and deploying the rewritten version of the original, transaction sizes on Monero were reduced by at least 80%, along with transaction fees. Thus, bulletproofs have effectively replaced range proofs in confidential transactions.

Bulletproofs are also designed to enable Confidential Transactions on public blockchain networks like Bitcoin. If implemented, they will reduce the blockchain size moving forward, and transaction fees may also drop.

Supporting multi-party computation protocols

Bulletproofs can be applied in multi-party computation protocols that allow several secret-holding entities to jointly generate a range proof for their secret values without disclosing them.

Sometimes, a transaction could be so complex that it requires inputs from multiple parties. With such an MPC protocol, instead of producing separate range proofs for each input, all the proofs can be aggregated as one short bulletproof. Bulletproofs are more efficient in cases like these than ordinary range proofs, saving time and space.

Enabling confidential smart contracts

Blockchains like Ethereum support smart contract deployment. Ethereum is a public blockchain solution, which means that the smart contracts are equally public including their parameters. The lack of privacy of the smart contract's parameters can expose users to several risks such as on-chain surveillance, exposure of MEV, etc.

Several developers have proposed introducing privacy to smart contracts with non-interactive zero-knowledge proofs and zkSNARKs. While the former is possible but rather expensive, zkSNARKs require a trusted setup, which is not ideal for such measures.

Bulletproofs, with no trusted setup, fit the bill as a non-interactive zero-knowledge proof system. However, using bulletproofs to power smart contract privacy may still be an expensive venture.

Shortening proof of solvency

Bitcoin and cryptocurrency exchanges use the Provisions protocol to prove their solvency without disclosing any other data or opening their books to the public. The Provisions protocol utilizes range proofs to prevent exchanges from padding their books with fake accounts and negative balances.

As with range proofs, the more customers an exchange has, the larger the range proof size. With bulletproofs, proofs of solvency can be much smaller, up to 300 times lesser, than regular range proofs. Bulletproofs have also been applied as a replacement for sigma protocols.

Closing thoughts

Bulletproofs have proven to be secure and reliable for their primary goals. They enable Confidential Transactions and bring privacy to solvency examinations, smart contracts, and multi-party computation protocols.

Bulletproofs offer privacy to public blockchains like Bitcoin, which can resolve the widespread privacy concerns associated with traditional blockchain networks.

However, several other types of ZK proofs, most importantly zkSNARKs and zkSTARKs, are able to surpass bulletproofs in terms of features. These other types are less resource-intensive and are cost-friendly. Because of this, recent developments of privacy-preserving protocols and scaling solutions have skewed towards zkSNARKs and zkSTARKs instead of bulletproofs.

About Panther

Panther is a decentralized protocol that enables interoperable privacy in DeFi using zero-knowledge proofs.

Users can mint fully-collateralized, composable tokens called zAssets, which can be used to execute private, trusted DeFi transactions across multiple blockchains.

Panther helps investors protect their personal financial data and trading strategies, and provides financial institutions with a clear path to compliantly participate in DeFi.

Stay connected: Telegram | Twitter | LinkedIn | Website

Share this article on: