Bulletproofs: a Crypto Gunfight at the OK Corral

This is a unique blog that I co-authored with Emanuele. We first met at a ZKWarsaw meetup, where I gave a presentation on cryptographic commitments. Later, our conversation led to Bulletproofs.

We thought of using a dialectic match as an engaging way to explain Bulletproofs and why they’re important in the current zero-knowledge landscape, even though they don’t get much attention. At the same time, we wanted to avoid creating just another standard tech blog focused on SEO.

The characters in the dialogue are inspired by the 1957 American Western Gunfight at the O.K. Corral. This classic film, starring Burt Lancaster as Wyatt Earp and Kirk Douglas as Doc Holliday, is loosely based on a real-life gunfight between lawmen and cowboys in Tombstone, Arizona, in 1881.

Generated with AI

---

Kirk: This is going to be an unusual blog, Burt. Given the subject, we might call it the dialectic gunfight at the O.K. Corral.

Burt: You are thinking about bullets already. Somehow, I knew you would get there!

Kirk: Yeah, “short like a bullet with bulletproof security assumptions”! Although I am not sure, they had bulletproof vests in Tombstone.

Burt: I don’t know if Shashank Agrawal¹ was in that frame of mind when he commented about the cryptographic protocol that became Bulletproofs, but certainly, given the history of cryptography and weapons, the analogy is well-posed.

Kirk: The bottom line is that we like bullets.

Burt: We do, and we like to fight too. Let’s start.

Introduction to Bulletproofs

Kirk: The Bulletproof paper was released in 2017 by cryptographers from Stanford University, including prominent names such as Benedikt Bünz, Dan Boneh, and Pieter Wuille

Burt: But it leveraged the inner product technique published one year earlier by Bootle et al., “Efficient Zero-Knowledge Arguments for Arithmetic Circuits in the Discrete Log Setting. “ We will return to the inner product. It is an important weapon in this fight, and I intend to use it.

Kirk: Sure, Burt, I wouldn’t expect anything else. Inner product, indeed!

Bulletproofs are a type of range proof that confirms that a value falls within a specific range. They are based on Pedersen Commitments and don't require a trusted setup like polynomial commitments-based SNARKs. Instead, Bulletproofs use an inner product argument for their short-proof sizes.

Burt: Short like the 9×19mm Parabellum. Originally, Bulletproofs were designed to implement confidential transactions in Bitcoin. 

This hasn’t happened, but Bulletproofs found their way into Monero, a fully privacy-preserving cousin of Bitcoin originally released in 2014. Bulletproofs were implemented into Monero in 2018, making them one of the earliest zero-knowledge proof systems (ZKPs) released into the real world. 

Kirk: We always compare weapons. So, how do Bulletproofs feature against other proving systems like STARKs and SNARKs?

Burt: Rather than reinventing the wheel, I'll refer to an excellent repository on ZKPs by Matter Labs here.

Burt: ZKPs cover a lot of ground, so let’s break it down step by step. If you need a refresher on SNARKs and STARKs, check out my earlier blog posts: SNARKs Part 1, Part 2, and STARKs Part 1, Part 2. Also, if you’re unfamiliar with Big O notation in computational complexity, this article is a good resource.

So Kirk, what do we see on that table?

Kirk: On algorithmic complexity of Prover—SNARKs generate proofs with a linearithmic complexity, making them efficient with some computational overhead. 

STARKs, with quasi-linear complexity, are slightly more complex but still efficient for large datasets. 

Bulletproofs have a similar complexity to SNARKs, making them suitable for small to medium-sized inputs.

Burt: The conclusion for Verifier is that SNARKs are extremely fast and have constant complexity. STARKs are fast but not as fast as SNARKs. Bulletproofs have a linear verification time, making them less efficient than SNARKs and STARKs.

Kirk: Regarding proof size, SNARKs have a constant, small proof size that offers minimal overhead. STARKs' proof size grows gradually, making them larger but still manageable. At least in theory. In practice, various techniques can further improve efficiency. 

Burt: Bulletproofs are efficient for individual transactions, maintaining a manageable proof size as transactions increase. SNARKs have a smaller, consistent proof size, while STARKs start larger and grow significantly, which can cause issues in practice.

Kirk: Indeed, Bulletproofs offer the best efficiency for small transactions, while SNARKs keep constant proof sizes for large batches, which makes them such powerful weapons.

Burt: How you cock a gun is important, so we need to talk about the setup. A trusted setup is required only for SNARKs, which creates significant overhead due to the complexity, expense of running the multi-party computation and the large common reference string it produces. 

Kirk: It is time for a summary: 

• Bulletproofs have small proof sizes and scale well, especially for computations in non-Turing complete blockchains that require only simple transactions. Due to the lack of a trusted setup, they are also easier to implement. SNARKs, with their efficient verification and compact proof sizes, are the best for handling complex computations. 

• STARKs are fast at the prover stage but have larger proof sizes and longer verification times, which is a significant drawback. Recently, a popular solution has been to generate a SNARK proof (Groth16) on top of a STARK to get the best of both worlds.

Range Proofs

Burt: Nice bullet, Kirk. It's very powerful. But what do we use it for? Which type of gun?

Kirk: Range proofs. Range proofs verify that a number is within a certain range, such as

\(0 < n < 2^p\)

without disclosing the actual number.

In Monero, range proofs are essential to ensure that transaction amounts remain within a specified range without revealing the actual values. This is important because, without range proofs, the values could overflow due to modular arithmetic.

Burt: I get it. Let me give you an example.

Imagine I want to pay you 15 XMR. Monero uses Pedersen Commitments (PCs) and Ring Signatures to keep the transaction value hidden, which mixes my payment with other decoy transactions. 

Monero, like Bitcoin, uses the UTXO system to store its state. Each transaction has two parts: inputs and outputs. Unspent outputs can be used as inputs for future transactions. Here's a simplified example:

• Inputs: Burt: 15 XMR; Decoy A: 10 XMR; Decoy B: 5 XMR

• Outputs: A: 20 XMR; B: 10 XMR

If we treat inputs as positive and outputs as negative, the sum of the inputs and outputs should be zero, so 15 + 10 + 5 - 20 - 10 = 0. In a range proof, the values are replaced by PCs that ensure this sum equals zero.

PCs are homomorphic for addition, but the blinding random values must also sum to zero for the equation to hold. The equation looks like this:

\(C(15, r_1) + C(10, r_2) + C(5, r_3) - C(20, r_4) - C(10, r_5) = 0\)

Kirk: The network confirms the transaction is valid if the equation equals zero. 

Diffie-Hellman Key Exchange (DHKE) helps differentiate between the random blinding factors and the true transaction values by allowing two parties to share a secret non-interactively using modular arithmetic. But there is a problem. While modular arithmetic in DHKE  is great for secret sharing, it can cause transaction values to overflow, effectively printing free XMR. 

Burt: Indeed, imagine we're working with modulus 19, and I want to send you 15 XMR. A legitimate transaction would include an input of 15 XMR and the same amount as the output. However, in modulus 19, another way to get 15 XMR is by setting fake outputs at 34 XMR because 34 mod 19 ≡ 15. You wouldn’t notice because the amounts are hidden through PCs, leading to free money being printed.

Kirk: Modular arithmetic introduces new risks when securely hiding transaction amounts without creating overflow vulnerabilities.

This overflow problem is solved with range proofs. In practice, each output cannot be higher than the modulus in which we work. Since PCs are made to the binary representation of the integers, the range is limited by the number of bits in the transaction, which for Monero is:

\(2^{64} - 1\)

Burt: Now that we understand the building blocks of Bulletproofs, let's explore how the protocols work. Math warning 🔺

First Protocol: Inner Product Argument for a Single Range Proof

Kirk: You correctly said protocols. Plural. This bullet is a three-in-one. The first protocol focuses on proving a single-range proof. 

The inner product, or the dot product, is calculated by multiplying the corresponding elements of two vectors and summing the results. 

The goal is to prove that for generators:

\(g, h \in G \text{ and a scalar } c \in \mathbb{Z}_p, \text{ where } \mathbb{Z}_p \text{ is the set of integers modulo } p.\)

The prover knows vectors:

\(\mathbf{a}, \mathbf{b} \in \mathbb{Z}_p \text{ such that } P = g^{\mathbf{a}} h^{\mathbf{b}} \text{ and } c = \langle \mathbf{a}, \mathbf{b} \rangle.\)

Here:

\(g^{\mathbf{a}} h^{\mathbf{b}} \)

denotes element-wise exponentiation. Let's call that Relation 1

Burt: To reduce the communication complexity from O(n) to O(log(n)), the protocol modifies the problem slightly to prove:

\(P = g^{\mathbf{a}} h^{\mathbf{b}} u^{\langle \mathbf{a}, \mathbf{b} \rangle}\)

Where u is a fixed group element. We will call that Relation 2. 

Kirk:  A hash function H is defined such that:

\(H(a, a', b, b', c) = H(g^a \cdot g^{a'} \cdot h^b \cdot h^{b'} \cdot u^c)\)

\(\text{Thus, } P = H(a, a', b, b', u^c).\)

We want to prove that Relations 1 and 2 are the same. So,

1. The prover computes the intermediate values L and R:

\(L = H(0, a, b', 0, \langle a, b' \rangle) \quad \text{and} \quad R = H(a', 0, 0, b, \langle a', b \rangle)\)

2. The verifier sends a random challenge x.

3. The prover responds with new vectors: 

\(a_1 = x a + x^{-1} a'\)

\(b_1 = x^{-1} b + x b'\)

4. Given (L, R, a1, b1), the verifier checks:

\(P_1 = L^{x^2} \cdot P \cdot R^{x-2} = H\left(x^{-1} a_1, x a_1, x b_1, x^{-1} b_1, \langle a_1, b_1 \rangle\right) = g^{a_1} h^{b_1} u^{\langle a_1, b_1 \rangle}\)

If this equality holds, the proof is accepted. 

Burt: But we can do better. Instead of directly sending a and b to the verifier, the prover and verifier engage in a recursive inner product argument on these new vectors. The problem dimension is now n/2.

The steps are repeated: divide vectors, compute intermediate values, send challenges, and verify until n = 1. When n = 1, the prover sends a and b to the verifier, who calculates P1.

This process reduces communication complexity while maintaining the integrity of the proof. The prover only needs to send the tuple (L, R, a1, b1) consisting of n+2 elements.

Second Protocol: Efficient IPA for Aggregated Range Proofs

Kirk: While Protocol 1 works by proving that a single commitment lies within a given range, Protocol 2 handles multiple commitments, aggregates them, and proves that the values are within the specified ranges.

In Protocol 2, we start by aggregating multiple range proofs. Vectors aL and aR represent the binary decompositions for multiple values vj, concatenated into larger vectors of size n x m.

Burt: The relations that need to be proved are:

\(\text {1. } V = h^\gamma g^v \text{ where } v \in \{0, 2^n - 1\}\)

\(\text {2. } \langle a_n, 2^n \rangle = v\)

\(\text {3. } \mathbf{a_L} \circ \mathbf{a_R} = \mathbf{0}_n \)

\(\text 4. \mathbf{a_L} = \mathbf{a_L} - \mathbf{1}_n\)

Here, ⊙ denotes the element-wise (Hadamard) product.

The protocol steps are:

1. Using a random scalar y sent by the verifier, the constraints are combined:

\(\langle \mathbf{a_L}, 2n \rangle = v \)

\(\langle \mathbf{a_L}, \mathbf{a_R} \circ \mathbf{y}^n \rangle = 0\)

\(\langle \mathbf{a_L} - \mathbf{1}^n, \mathbf{y}^n \rangle = 0\)

2. Using another random scalar z sent by the verifier, we further combine the constraints:

\(z^2 \langle \mathbf{a_L}, 2^n \rangle + z \langle \mathbf{a_L} - \mathbf{1}^n, \mathbf{y}^n \rangle + \langle \mathbf{a_L}, \mathbf{a_R} \circ \mathbf{y}^n \rangle = z^2 v + \delta(y, z)\)

where the term δ(y,z) stands for:

\(\delta(y, z) = (z - z^2) \cdot \langle \mathbf{1}^n, \mathbf{y}^n \rangle - z^3 + \langle \mathbf{1^n, 2^n \rangle}\)

This reduction gives us a single range proof for the verifier to check.

3. The prover combines the constraints into polynomials: 

\(l(X) = (\mathbf{a_L} - z \cdot \mathbf{1}^n) + \mathbf{s_L} \cdot X\)

\(r(X) = \mathbf{y}^{n} \circ (\mathbf{a_R} + z \cdot \mathbf{1}^n + \mathbf{s_R} \cdot X) + z^2 \cdot 2^n\)

\(t(X) = \langle l(X), r(X) \rangle = t_0 + t_1 \cdot X + t_2 \cdot X^2\)

Here S are blinding vectors and t1 and t2 are coefficients of the polynomial to which the prover commits. The prover must show that:

\(t_0 = z^2 v + \delta(y, z) \)

Kirk: To convince the verifier, the prover and verifier engage in an interaction:

3. The prover evaluates l(x), r(x), and t(x) on random x sent by the verifier. 

4. The prover also calculates the blinding values τ and μ:

\(\tau_x = \tau_2 \cdot x^2 + \tau_1 \cdot x + z^2 \gamma\)

\(\mu = \alpha + \rho x\)

5. The prover sends to the verifier:

\(\tau_x, \mu, t(x), l(x), r(x) \)

6. The verifier checks that the commitment to the polynomial evaluation matches the given values:

\(g^{\mu} h^{\tau_x} = V^{z^2} g^{\delta(y,z)} T_1^x \ T_2^{x^2} \)

7. Where:

• g and h are generators of the group,

• V is the commitment to the original vector v,

• T1 and T2 are commitments to the polynomial evaluations,

• x and z are the verifier's random challenge,

• δ(y,z) is a polynomial term that adjusts for the offsets introduced by y and z.

8. The verifier switches the generators from h to:

\(h' = h^{y^{-n}}, \text{ transforming } \mathbf{a_R} \circ y^n\)

into a vector commitment with respect to these new generators.

9. The verifier checks the consistency of the commitments to the vectors l and r:

\(P = A \cdot S^x \cdot g^{-z} \cdot (h')^{z \cdot y^n + z^2 \cdot 2^n}\)

10. The verifier then checks that l and r are correct:

\(P \stackrel{?}{=} g^{l(x)} \cdot (h')^{r(x)} \cdot h^{\mu}\)

And that t is correct:

\( t(x)=⟨l(x),r(x)⟩\)

Where:

• A is the initial commitment to the vectors aL and aR

• S is the secondary commitment to the blinding vectors sL and sR scaled by x.

• g adjusts for the blinding factor z applied to the initial commitment.

• (h') ensures that the offset introduced by z is correctly accounted for in the final commitment.

• hμ is the blinding factor that ensures that the prover's responses remain hidden.

Burt: The entire process is illustrated in Figure “Overview of Protocol 2”, available here.

Overview of Protocol 2

Third Protocol: IPA for Arithmetic Circuits

Kirk: Last one, Burt. The main idea behind Protocol 3 is to use an inner-product relation to handle linear constraints and Hadamard (dot) product relations typical in arithmetic circuit evaluations. This protocol simplifies the verification process by transforming these constraints into a single inner product.

Burt: The relations that need to be proved are:

\(\text {1. } V_j = g^{v_j} h^{\gamma_j} \text{ for all } j \in [1, m]\)

\(\text {2. } \mathbf{a_L} \circ \mathbf{a_R} = \mathbf{a_O} \)

\(\text {3. } W_L \cdot \mathbf{a_L} + W_R \cdot \mathbf{a_R} + W_O \cdot \mathbf{a_O} = W_V\cdot v + c\)

Where:

1. Vj​ represents commitments to individual values vj using randomness γj.

2. aL, aR, aO are vectors representing the circuit gates' left, right, and output wires.

3. WL, WR, WO are matrices representing the weights of the left, right, and output wires.

4. Wv and v are weights and values involved in the commitments.

5. c is a constant added for further computational integrity.

Kirk:  The steps in the protocol are:

1. The prover commits to vectors aL, aR, aO using random scalars α, β, ρ

2. Commitments are:

\(A_I = h^{\alpha} g^{a_L} h^{a_R} \)

\(A_O = h^{\beta} g^{a_O}\)

3. The verifier sends random challenges y and z to create a random linear combination of the constraints.

4. Prover forms polynomials l(X), r(X), and t(X) to endocde the constraints:

\(l(X) = \mathbf{a_L} \cdot X + \mathbf{a_O} \cdot X^2 + y^{-n} \circ (z^{Q+1} \cdot W_R) \cdot X + \mathbf{s_L} \cdot X^3\)

\(r(X) = y^n \circ \mathbf{a_R} \cdot X - y^n + z^{Q+1} \cdot (W_L \cdot X + W_O) + y^n \circ \mathbf{s_R} \cdot X^3\)

\(t(X) = \langle l(X), r(X) \rangle\)

5. The verifier computes a check that evaluates the inner product t(X) is consistent with the commitments and challenges and, using a single verification step, checks the equality:

\(g^{t} h^{\tau_x} = g^{x^2 \cdot (\delta(y, z) + \langle z^{Q+1} \cdot c) \rangle} \cdot V^{x^2 \cdot (z^{Q+1} \cdot W_V)} \cdot T_1^x \cdot \prod_{i=3}^{6} T_i^{x^i}\)

Ensuring that all commitments and polynomials align.

Burt: All protocols can be converted to non-interactive versions using the Fiat-Shamir Heuristic, in which the verifier's challenges y and z are replaced by hashes of the prover's commitments, ensuring that the source of randomness is deterministic and reproducible.

Conclusion

Kirk:  Bulletproofs are a set of three powerful cryptographic protocols. Their main advantage is keeping data privacy while significantly reducing complexity and communication costs. 

Burt: Unlike other zero-knowledge proof systems, Bulletproofs don't require a trusted setup phase, making them easier to implement and more secure, as there's no risk of compromised initial setup parameters. These protocols are also scalable, with proof sizes increasing slowly as more data increases. 

Kirk: The most well-known implementation of Bulletproofs is in Monero, where Protocol 2 ensures that multiple transaction values stay within specified ranges without revealing the actual amounts.

Sources

• Cathie Yun, Building on Bulletproofs

• Tari Labs, The Bulletproofs Protocols

• Adam Gibson, An Investigation into Confidential Transactions

• Benedikt Bunz, Jonathan Bootle, Dan Boneh, Andrew Poelstra, Pieter Wuille, and Greg Maxwell, Bulletproofs: Short Proofs for Confidential Transactions and More

1. In the Bulletproofs paper, one of the acknowledgements goes to Shashank Agrawal for coming up with the Bulletproof name—“short like a bullet with bulletproof security assumptions”.