As mentioned previously, Bulletproofs are a non-interactive zero-knowledge proof system that does not require a trusted setup but instead runs on transparent setups. They are less complex than a zk-SNARK and allow for the development of smart contracts through their ad hoc logic. Two key distinctions of Bulletproofs from the prior two zero-knowledge proof systems (zk-SNARKs and zk-STARKS) are their use of zero-knowledge range proofs and efficient inner product arguments. Let’s dive into what each of these terms means and how they are implemented.
In a range proof, the goal is to prove that a value $v$ is in a certain range $v \in [0,2^n)$. The intuition behind range proofs is to break the statement $v$ in the range described into several different statements, expanding this into multiple different polynomials.
For the more expert readers, the following illustration is a flow chart representing how range proofs are implemented in Bulletproofs:
Oleg Andreev’s stylized illustration of the Bulletproofs range-proof protocol
Say for example, we want to construct a proof that shows that $0 \le v < 2^n$. If this statement is in fact true, then we know that $v$ must be a binary number of length $n$. This means that if $n=4$ then $v$ can be broken up into a bit representation with a corresponding bit length of 4. To maximize efficiency, this claim will be represented as an inner product proof. Representing this as an inner product, we can prove the claim above by the following two proofs:
The math to combine these proofs can be a bit tedious and relies on the concept of what an inner product is so let’s dive into this in the next section.
In the most simple form, an inner product proof is a proof that attempts to prove that $c$ is an inner product of two vectors $a$ and $b$, or that $c=\langle a,b\rangle$. For readers that are not familiar with inner products, they are basically an operator that computers the sum of the product of each term in a vector, that is $a_0\cdot b_0 + a_1 \cdot b_1 + \cdots +a_{n-1} \cdot b_{n-1}$. This proof is quite easy to complete in a non zero-knowledge system, as a prover could simply send a verifier all of the inputs ($a,b,c$) for them to compute themselves, but even outside of a public verification like this, the computation is inefficient. It not only requires $O(n)$ space to send ($n$ being the length of $a$ and vectors), but also requires $O(n)$ time to verify it. Bulletproofs allow for this proof to be computed in $O(\log(n))$ time and space by halving the vectors $a$ and $b$ in each step of the proof, thus maximizing efficiency for these inner product proofs.
Another core concept related to Bulletproofs is the implementation of a constraint system. A constraint system is comprised of two types of constraints: a linear constraint ($a\cdot x + b\cdot y + c\cdot z + \cdots = 0$) and a multiplicative constraint ($x\cdot y = z$). Constraint systems can represent any efficiently verifiable program and can be implemented with zero-knowledge by proving constraints in a system satisfy secret inputs without any knowledge revealed about the secret inputs. Without going into too much depth on constraint systems, at a high level they implement a sort of “shuffle system,” or a collection of constraints, that enforces that some outputs are a valid permutation of some inputs without necessarily stating which output is tied to which input.
In an example with two inputs, $A,B$ and two outputs, $C,D$, this can be expressed as $(A-x)(B-x)=(C-x)(D-x)$ for some random secret $x$ scalar, showing that $A=C$ and $B=D$ or $A=D$ and $B=D$ in any order. This can be scaled up for $n$ variables.
In Bulletproof systems, all of the above are combined into one system called Cloak. Though the details of Cloak will not be covered here, it is important to know that Cloak is what gives Bulletproofs viability, efficiency and zero-knowledge.