# Bulletproofs and Mimblewimble

## Introduction

Bulletproofs form part of the family of distinct Zero-knowledge Proofdef systems, like Zero-Knowledge Succinct Non-Interactive ARguments of Knowledge (zk-SNARK), Succinct Transparent ARgument of Knowledge (STARK) and Zero Knowledge Prover and Verifier for Boolean Circuits (ZKBoo). Zero-knowledge proofs are designed so that a prover is able to indirectly verify that a statement is true without having to provide any information beyond the verification of the statement, for example to prove that a number is found that solves a cryptographic puzzle and fits the hash value without having to reveal the Noncedef. ([2], [4])

The Bulletproofs technology is a Non-interactive Zero-knowledge (NIZK) proof protocol for general Arithmetic Circuitsdef with very short proofs (Arguments of Knowledge Systemsdef) and without requiring a trusted setup. They rely on the Discrete Logarithmdef (DL) assumption and are made non-interactive using the Fiat-Shamir Heuristicdef. The name 'Bulletproof' originated from a non-technical summary from one of the original authors of the scheme's properties: "Short like a bullet with bulletproof security assumptions". ([1], [29])

Bulletproofs also implement a Multi-party Computation (MPC) protocol whereby distributed proofs of multiple provers with secret committed values are aggregated into a single proof before the Fiat-Shamir challenge is calculated and sent to the verifier, thereby minimizing rounds of communication. Secret committed values will stay secret. ([1], [6])

The essence of Bulletproofs is its inner-product algorithm originally presented by Groth [13] and then further refined by Bootle et al. [12]. The latter development provided a proof (argument of knowledge) for two independent (not related) bindingdef vector Pedersen Commitmentsdef that satisfied the given inner-product relation. Bulletproofs build on these techniques, which yield communication-efficient zero-knowledge proofs, but offer a further replacement for the inner product argument that reduces overall communication by a factor of three. ([1], [29])

Mimblewimble is a blockchain protocol designed for confidential transactions. The essence is that a Pedersen Commitment to $0$ can be viewed as an Elliptic Curve Digital Signature Algorithm (ECDSA) public key, and that for a valid confidential transaction the difference between outputs, inputs, and transaction fees must be $0 ​$. A prover constructing a confidential transaction can therefore sign the transaction with the difference of the outputs and inputs as the public key. This enables a greatly simplified blockchain in which all spent transactions can be pruned, and new nodes can efficiently validate the entire blockchain without downloading any old and spent transactions. The blockchain consists only of block-headers, remaining Unspent Transaction Outputs (UTXO) with their range proofs and an unprunable transaction kernel per transaction. Mimblewimble also allows transactions to be aggregated before being committed to the blockchain. ([1], [20])

## How do Bulletproofs work?

The basis of confidential transactions is to replace the input and output amounts with Pedersen Commitmentsdef. It is then publicly verifiable that the transactions balance (the sum of the committed inputs is greater than the sum of the committed outputs, and all outputs are positive), while keeping the specific committed amounts hidden. This makes it a zero-knowledge transaction. The transaction amounts must be encoded as $integers \mod q ​$, which can overflow, but is prevented by making use of range proofs. This is where Bulletproofs come in. The essence of Bulletproofs are its ability to calculate proofs, including range proofs, from inner-products.

The prover must convince the verifier that commitment $C(x,r) = xH + rG ​$ contains a number such that $x \in [0,2^n - 1] ​$. If $\mathbf {a} = (a_1 \mspace{3mu} , \mspace{3mu} ... \mspace{3mu} , \mspace{3mu} a_n) \in {0,1}^n ​$ is the vector containing the bits of $x ​$, the basic idea is to hide all the bits of the amount in a single vector Pedersen Commitment. It must then be proven that each bit satisfies $\omega(\omega-1) = 0 ​$, that is each $\omega ​$ is either $0 ​$ or $1 ​$, and that they sum to $x ​$. As part of the ensuing protocol the verifier sends random linear combinations of constraints and challenges $\in \mathbb{Z_p} ​$ to the prover. The prover is then able to construct a vectorized inner product relation containing the elements of $\mathbf {a} ​$, the constraints and challenges $\in \mathbb{Z_p} ​$, and appropriate blinding vectors $\in \mathbb Z_p^n ​$.

These inner product vectors have size $n$ that would require many expensive exponentiations. The Pedersen Commitment scheme allows a vector to be cut in half and to compress the two halves together, each time calculating a new set of Pedersen Commitment generators. Applying the same trick repeatedly, $\log _2 n$ times, produces a single value. This is applied to the inner product vectors; they are reduced interactively with a logarithmic number of rounds by the prover and verifier into a single multi-exponentiation of size $2n + 2 \log_2(n) + 1$. This single multi-exponentiation can then be calculated much faster than $n$ separate ones. All of this are made non-interactive using the Fiat-Shamir Heuristicdef.

Figure 1: Vector Pedersen Commitment Cut and Half ([12], [63])

Bulletproofs only rely on the discrete logarithm assumption. What this means in practice is that Bulletproofs are compatible with any secure elliptic curve, which makes it extremely versatile. The proof sizes are short; only $[2 \log_2(n) + 9]$ elements are required for the range proofs and $[\log_2(n) + 13]$ elements for arithmetic circuit proofs with $n$ denoting the multiplicative complexity. Additionally, the logarithmic proof size enables the prover to aggregate multiple range proofs into a single short proof, as well as to aggregate multiple range proofs from different parties into one proof (see Figure 1). ([1], [3], [5])

Figure 1: Logarithmic Aggregate Bulletproofs Proof Sizes [3]

If all Bitcoin transactions were confidential, approximately 50 million UTXOs from approximately 22 million transactions would result in roughly 160GB of range proof data, when using current/linear proof systems and assuming use of 52-bits to represent any value from 1 satoshi up to 21 million bitcoins. Aggregated Bulletproofs would reduce the data storage requirement to less than 17GB. [1]

In Mimblewimble the blockchain grows with the size of the UTXO set. Using Bulletproofs as a drop-in replacement for range proofs in confidential transactions, the size of the blockchain would only grow with the number of transactions that have unspent outputs. This is much smaller than the size of the UTXO set. [1]