Privacy of transactions is an integral component of cryptocurrencies and one of the most important for many users. While Bitcoin is often characterized as an anonymous medium of value transfer by mainstream media outlets, the truth is that Bitcoin is only pseudo anonymous.
The Bitcoin ledger is fully transparent and although user identities are hidden behind alphanumerical addresses, there are ways of tracking and making correlations between addresses and identities. The obfuscation of identities provides a degree of anonymity for users, however, the amounts transferred in each transaction are visible, leaving a certain degree of confidentiality missing.
As a solution to this problem, some privacy-focused cryptocurrencies adopted the use of Confidential Transactions (CTs), which obfuscate the amount transferred in transactions using commitments (specifically Pedersen Commitments) to the amount.
Without the public transparency of transferred values when CTs are implemented, verifying that transactions are valid requires the use of range proofs to ensure that the sum of transaction inputs is greater than the sum of transaction outputs as well as that all transaction values are positive.
These range proofs are attached to every transaction and result in much larger transaction sizes that can lead to transactions with multiple outputs needing multiple range proofs, further increasing transaction size, and degrading verification and storage efficiency. Enter bulletproofs.
Bulletproofs Background
Bulletproofs were proposed by Stanford’s Applied Cryptography Group (ACG) in December 2017 in an academic paper with contributions from the University College of London and Blockstream.
Bulletproofs are “a new zero-knowledge argument of knowledge system, to prove that a secret committed value lies in a given interval.” The bulletproof name is credited to Shashank Agrawal for describing them as being “short like a bullet, with bulletproof security assumptions.”
Praised as an efficient and useful advancement in verifying commitments of CTs, bulletproofs are short, non-interactive zero-knowledge proofs that do not require a trusted setup. They 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. Their application can be beneficial in a variety of different systems and situations, of which many are outlined directly in the academic paper.
Bulletproofs are especially suited for the distributed and trustless nature of blockchains and can create substantial long-term cost savings, enormous space savings, lower fees, and faster verification times than current implementations of range proofs. Before diving into how bulletproofs work though, it is important to understand two terms first, range proofs and zero-knowledge proofs.
Range Proofs
Basically, range proofs are a form of commitment validation that allow anyone to verify that a commitment represents an amount within a specified range, without revealing anything else about its value (known as the secret value).
For instance, a simple range proof can be used to validate that someone’s age is between 28 and 52 years old without actually revealing the exact age of the person.
This has important ramifications for validation of confidential transactions. Within a anonymity-focused cryptocurrency such as Monero, it is used to verify that a payment amount is positive, without actually revealing the amount transferred in the transaction.
More specifically, in a transaction output based system, it proves that the committed inputs are greater than the sum of the committed outputs without actually revealing either the committed inputs or outputs.
According to the Stanford paper at the time, “All current implementations of confidential transactions use range proofs over committed values, where the proof size is linear in n.”
The key part in regard to bulletproofs is the “linear in n”, which means that range proofs scale linearly in size with the number of outputs and bits in the proof’s range.
The result is that in CTs, the range proofs take up a majority of a transaction’s size. Before bulletproofs, this was a large concern as the size of a blockchain of an anonymity-focused cryptocurrency employing CTs, like Monero, grows much faster than a typical cryptocurrency that does not utilize CTs.
Eventually, the size of a blockchain utilizing CTs would become very impractical to many users who do not have the requisite disk space to download the entire blockchain, indirectly affecting decentralization of full nodes.
Zero-Knowledge Proofs
If you’re reading this then you’ve probably heard of zero-knowledge proofs in the cryptocurrency realm before as they represent a very interesting concept that is predicated on some intimidating mathematics. The concept is difficult to grasp, but their implementation combined with the fact that academic institutions are advancing the concept further, as applied to cryptocurrencies, is a very encouraging sign for the industry.
Essentially, a zero-knowledge proof is a method in cryptography where one party can prove to another party that they know the value of a variable y without conveying any other information aside from the fact that they know the value of y.
Traditionally, this implies that the verifier and prover have some form of interaction between them. However, bulletproofs are non-interactive zero-knowledge arguments of knowledge, which are a specific variant of zero-knowledge proofs where no interaction is necessary between the prover and verifier.
This enables proving that a committed value is in a specific range by relying on the discrete logarithm assumption and using the Fiat-Shamir heuristic to make them non-interactive.
So What Are Bulletproofs?
Back to bulletproofs. As just mentioned, bulletproofs rely on the discrete logarithm assumption for security and use the Fiat-Shamir heuristic in order to become non-interactive.
This leads to bulletproofs increasing in size only logarithmically with the number of outputs and size of the range’s proof. The result is that the size of transactions that implement CTs can be substantially reduced.
Monero states that they have reached an 80% reduction in transaction size utilizing bulletproofs which leads to an 80% reduction in fees as well.
Not only can bulletproofs help to reduce the size of transactions employing CTs, they allow the prover to aggregate multiple range proofs for transactions with multiple outputs into a single, short proof.
Instead of transactions with multiple outputs necessitating a range proof for each output, they can all be aggregated into one. Further, validation of bulletproofs is more efficient in not only size, but time.
Outside of zk-SNARKS, which verify quicker than bulletproofs, the time to verify a bulletproof is lower than existing range proofs, leading to quicker blockchain validation.
Importantly, bulletproofs do not require a trusted setup. A trusted setup is a controversial one-time setup that is required when using the zero-knowledge proof zk-SNARKS.
The issue is that this one-time setup requires that users need to implicitly trust whoever created the keys for the one-time setup to destroy them after they are done, otherwise they can be used to create an unlimited amount of the native token, undetected. Obviously, there are serious concerns with a trusted setup.
The proofs of bulletproofs are much shorter than other range proofs and “allow inputs to be Pedersen commitments to elements of the witness.”
The resulting implications of them being short, non-interactive zero knowledge proofs enable bulletproofs to be optimized and applied to a variety of situations such as supporting efficient Multi-party computation (MPC) protocols as well as implementing complex, privacy-preserving smart contracts.
Applications of Bulletproofs
Bulletproofs efficiently support a simple MPC protocol that “allows multiple parties with secret committed values to jointly generate a single small range proof for all their values, without revealing their secret values to each other.”
Essentially, with a complex confidential transaction that has inputs from multiple parties, their proposed MPC protocol would be able to aggregate all of the required proofs into a single, short proof for the entire transaction.
The efficiency and savings afforded by this cannot be understated.
The Provisions protocol is an innovation that allows Bitcoin exchanges to prove that they are solvent without revealing any other information.
This is an important step in verifying solvency of exchanges otherwise deemed to be untrustworthy and insolvent without the exchanges actually having to open their books to the public.
The protocol relies on range proofs “to prevent an exchange from inserting fake accounts with negative balances.” These proof sizes are very large and are linear in the number of customers.
Bulletproofs represent a natural replacement for the non-interactive zero knowledge proofs used in the Provisions protocol and can reduce the size of overall proof size for the exchange by up to nearly 300 times.
Highly expressive smart contracts in Ethereum are public and do not provide a degree of privacy to the contracts’ parameters.
Non-interactive zero knowledge proofs have been proposed as a mechanism for privacy within contracts, however, a contract’s computation is limited and expensive across the blockchain network. SNARKs are another potential solution but problematically, require a trusted setup. You can see where this is going.
Bulletproofs, being short proofs that do not require a trusted setup are a great fit for the role of privacy preservation within expressive smart contracts.
Although as a straight drop-in, bulletproofs are not cheap in this regard, in combination with an incentive delegation model, the validity of a proof does not need to be performed unless a party challenges its verification.
Parties presenting faulty challenges will be punished, and further, this design can be supported with efficient multi-party computation.
Conclusion
Bulletproofs are an important and widely applicable innovation in an important field of research of zero-knowledge proofs and other protocols used to secure and obfuscate transaction amounts.
The inherent tradeoff with confidential transactions has been their larger size. With bulletproofs, the opportunity to significantly reduce this tradeoff while preserving privacy and security is a major step forward.
As more emphasis is placed on the underlying protocols used to secure transactions and provide anonymity, it will be fascinating to watch how academia responds and continues to evolve technologies on the bleeding edge of a field that is already at the forefront of innovation.
Source: https://blockonomi.com/bullet-proofs/