Transaction privacy is an integral component of cryptocurrencies and one of the most important for many users. While Bitcoin is often characterized as an anonymous means of transferring value by the mainstream media, the truth is that Bitcoin is only pseudo anonymous.
The Bitcoin ledger is completely transparent and although users’ identities are hidden behind alphanumeric addresses, there are ways to track and make correlations between addresses and identities. Identity obfuscation provides some degree of anonymity for users, however, the amounts transferred in each transaction are visible, leaving some degree of confidentiality missing.
As a solution to this problem, some privacy-focused cryptocurrencies have adopted the use of confidential transactions (CTs), which obfuscate the amount transferred in transactions using commitments (especially Pedersen commitments) to the amount.
Without the public transparency of the transferred values when TCs are implemented, verifying the validity of transactions requires the use of range proofs to ensure that the sum of transaction inputs is greater than the sum of transaction outputs and that all transaction values are positive.
These interval proofs are attached to each transaction and result in much larger transaction sizes that can lead to transactions with multiple outputs that require multiple interval proofs, further increasing transaction size and degrading verification and storage efficiency. Enter Bulletproofs.
Bulletproofs
Bulletproofs was proposed by Stanford’s Applied Cryptography Group (ACG) in December 2017 in an academic paper with contributions from University College London and Blockstream.
Bullet tests are “a new zero-knowledge argument of the knowledge system, to prove that a committed secret value is in a given range.” The bulletproof name is credited to Shashank Agrawal for describing them as “short as a bullet, with bulletproof security assumptions.”
Praised as an efficient and useful advance in verifying CT commitments, bulletproofs are short, non-interactive zero-knowledge proofs that do not require reliable configuration. They are indeed a much more efficient and secure form of flow tests that use zero-knowledge correction methods as seen in zk-SNARKS and STARKs, but they do not require the reliable configuration as required with zk-SNARKS and are not as large as STARK. Their application can be useful in a variety of different systems and situations, many of which are outlined directly in the academic paper.
Bulletproofs are particularly well suited for the distributed and trustless nature of blockchains and can create substantial long-term cost savings, huge space savings, lower fees, and faster verification times than current scope test implementations. Before diving into how bulletproofs work, though, it’s important to first understand two terms, gamma tests and zero-knowledge tests.
Flow tests
Basically, range tests are a form of commitment validation that allows anyone to verify that a commitment represents an amount within a specified range, without revealing anything else about its value (known as a secret value).
For example, a simple interval test 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 validating confidential transactions. Within an anonymity-focused cryptocurrency like 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 system based on transaction output, it shows that committed inputs are greater than the sum of committed outputs without actually revealing either the committed inputs or the outputs.
According to the Stanford paper of the time, “All current implementations of confidential transactions use interval proofs on committed values, where the size of the proof is linear in n. ”
The key part regarding the projectiles is the “linear in n”, which means that gamma tests scale linearly in size with the number of outputs and bits in the demonstration range.
The result is that in CTs, interval proofs occupy most of the size of a transaction. Before bulletproof, this was a big concern as the size of a blockchain of an anonymity-focused cryptocurrency employing CT, such as Monero, grows much faster than a typical cryptocurrency that doesn’t use CT.
Eventually, the size of a blockchain using CT would become very impractical for many users who don’t have the disk space needed to download the entire blockchain, indirectly affecting the decentralization of full nodes.
Zero-knowledge evidence
If you’re reading this, you’ve probably already heard of zero-knowledge proof in the realm of cryptocurrencies as they represent a very interesting concept that is based on intimidating mathematics. The concept is difficult to grasp, but their implementation combined with the fact that academic institutions are further advancing the concept, applied to cryptocurrencies, is a very encouraging sign for the industry.
Essentially, a zero-knowledge proof is a method in cryptography in which one party can prove to another party that it knows the value of a variable y without transmitting any other information than that they know the value of y.
Traditionally, this implies that the verifier and the prover have some form of interaction between them. However, bullet tests are non-interactive zero-knowledge knowledge topics, which are a specific variant of zero-knowledge tests where no interaction between the demonstrator and the verifier is required.
This allows you to prove that a committed value is in a specific range based on the discrete logarithm hypothesis and using the Fiat-Shamir heuristic to make them non-interactive.
So what are bulletproofs?
Let’s go back to the bullets. As just mentioned, bulletproofs are based on the discrete logarithm hypothesis for security and use the Fiat-Shamir heuristic to become non-interactive.
This leads to an increase in bulletproof dimensions only logarithmically with the number of outputs and the size of the interval test. The result is that the size of transactions implementing CTs can be substantially reduced.
Not only can bulletproof proofs help reduce the size of transactions using CT, but 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 that require a proof of interval for each output, they can all be aggregated into one. In addition, the validation of Bulletproofs tests is more efficient not only in size, but also in time.
Outside of zk-SNARKS, which verify faster than bulletproofs, the time to verify a bulletproof is less than existing scope tests, leading to faster blockchain validation.
Importantly, Bulletproofs tests do not require a trusted configuration. A trusted configuration is a controversial one-time configuration that is required when using the zk-SNARKS zero-knowledge proof.
The problem is that this one-time configuration requires that users must implicitly trust who created the keys for the one-time installation to destroy them after they have been completed, otherwise they can be used to create an unlimited amount of the native, undetected token. Of course, there are serious concerns with a reliable configuration.
Bulletproofs’ evidence is much shorter than other remote evidence and “allows inputs to be Pedersen’s commitments to witness elements.”
The implications of being short, non-interactive zero-knowledge proofs allow you to optimize and apply bulletproof testing to a variety of situations such as supporting efficient multi-part computing protocols (MPCs) and implementing complex, privacy-friendly smart contracts.
Bulletproofs Applications
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.”
In essence, with a complex confidential transaction that has input from multiple parties, their proposed MPC protocol would be able to aggregate all the required evidence into a single, short proof for the entire transaction.
The efficiency and savings that come with it cannot be underestimated.
The Provisions protocol is an innovation that allows Bitcoin exchanges to prove to be solvent without revealing any other information.
This is an important step in verifying the solvency of exchanges otherwise deemed unreliable and insolvent without exchanges actually having to open their books to the public.
The protocol relies on interval tests “to prevent an exchange from entering fake accounts with negative balances.” These test dimensions are very large and are linear in the number of customers.
Bulletproof tests are a natural substitute for non-interactive zero-knowledge tests used in the Provisions protocol and can reduce the overall size of the test for exchange by up to nearly 300 times.
Highly expressive smart contracts in Ethereum are public and do not provide some degree of privacy to contract parameters.
Non-interactive zero-knowledge evidence has been proposed as a mechanism for privacy within contracts, however, the calculation of a contract is limited and expensive throughout the blockchain network. SNARKS are another potential solution but, problematically, require a trusted configuration. You can see where it is going.
Bulletproof tests, being short tests that do not require a reliable configuration, are ideal for the role of preserving privacy within expressive smart contracts.
Although as a direct drop-in, bulletproofs are not cheap in this regard, in combination with an incentive delegation model, the validity of a test should not be performed unless a party contests its verification.
Parties that present faulty challenges will be punished, and in addition, this project can be supported with efficient multi-party computing.
Conclusion
Bulletproofs are an important and widely applicable innovation in an important field of zero-knowledge evidence research and other protocols used to protect and obfuscate transaction amounts.
The inherent trade-off with confidential transactions was their larger size. With bullets, the opportunity to significantly reduce this compromise while preserving privacy and security is an important step forward.
As more emphasis is placed on the underlying protocols used to secure transactions and provide anonymity, it will be fascinating to see how academia responds and continues to evolve the cutting-edge technologies of a field that is already at the forefront of innovation.