 # The Bulletproof Protocols

## Introduction

The overview of Bulletproofs given in Bulletproofs and Mimblewimble was largely based on the original work done by Bünz et al. . They documented a number of different Bulletproof protocols, but not all of them in an obvious manner. This report summarizes and explains the different Bulletproof protocols as simply as possible. It also simplifies the logic and explains the base mathematical concepts in more detail where prior knowledge was assumed. The report concludes with a discussion on an improved Bulletproof zero-knowledge proof protocol provided by some community members following an evolutionary approach.

## Preliminaries

### Notation Used

This section gives the general notation of mathematical expressions when specifically referenced, based on . This notation provides important pre-knowledge for the remainder of the report.

• Let $p$ and $q ​$ be large prime numbers.
• Let $\mathbb G ​$ and $\mathbb Q ​$ denote cyclic groups of prime order $p ​$ and $q ​$ respectively.
• let $\mathbb Z_p ​$ and $\mathbb Z_q ​$ denote the ring of integers $modulo \mspace{4mu} p ​$ and $modulo \mspace{4mu} q ​$ respectively.
• Let generators of $\mathbb G$ be denoted by $g, h, v, u \in \mathbb G$, i.e. there exists a number $g \in \mathbb G$ such that $\mathbb G = \lbrace 1 \mspace{3mu} , \mspace{3mu} g \mspace{3mu} , \mspace{3mu} g^2 \mspace{3mu} , \mspace{3mu} g^3 \mspace{3mu} , \mspace{3mu} ... \mspace{3mu} , \mspace{3mu} g^{p-1} \rbrace \equiv \mathbb Z_p$. Note that not every element of $\mathbb Z_p$ is a generator of $\mathbb G$.
• Let $\mathbb Z_p^*$ denote $\mathbb Z_p \setminus \lbrace 0 \rbrace$ and $\mathbb Z_q^*$ denote $\mathbb Z_q \setminus \lbrace 0 \rbrace$, i.e. all invertible elements of $\mathbb Z_p$ and $\mathbb Z_q$ respectively. This excludes the element $0 ​$, which is not invertible.
• Let $\mathbb G^n$ and $\mathbb Z^n_p$ be vector spaces of dimension $n$ over $\mathbb G$ and $\mathbb Z_p$ respectively.
• Let $h^r \mathbf g^\mathbf x = h^r \prod_i g_i^{x_i} \in \mathbb G ​$ be the vector Pedersen Commitmentdef with $\mathbf {g} = (g_1 \mspace{3mu} , \mspace{3mu} ... \mspace{3mu} , \mspace{3mu} g_n) \in \mathbb G^n ​$ and $\mathbf {x} = (x_1 \mspace{3mu} , \mspace{3mu} ... \mspace{3mu} , \mspace{3mu} x_n) \in \mathbb G^n ​$.
• Let $\mathbf {a} \in \mathbb F^n ​$ be a vector with elements $a_1 \mspace{3mu} , \mspace{3mu} . . . \mspace{3mu} , \mspace{3mu} a_n \in \mathbb F ​$.
• Let $\langle \mathbf {a}, \mathbf {b} \rangle = \sum _{i=1}^n {a_i \cdot b_i} ​$ denote the inner-product between two vectors $\mathbf {a}, \mathbf {b} \in \mathbb F^n ​$.
• Let $\mathbf {a} \circ \mathbf {b} = (a_1 \cdot b_1 \mspace{3mu} , \mspace{3mu} . . . \mspace{3mu} , \mspace{3mu} a_n \cdot b_n) \in \mathbb F^n ​$ denote the entry wise multiplication of two vectors $\mathbf {a}, \mathbf {b} \in \mathbb F^n ​$.
• Let $\mathbf {A} \circ \mathbf {B} = (a_{11} \cdot b_{11} \mspace{3mu} , \mspace{3mu} . . . \mspace{3mu} , \mspace{3mu} a_{1m} \cdot b_{1m} \mspace{6mu} ; \mspace{6mu} . . . \mspace{6mu} ; \mspace{6mu} a_{n1} \cdot b_{n1} \mspace{3mu} , \mspace{3mu} . . . \mspace{3mu} , \mspace{3mu} a_{nm} \cdot b_{nm} )$ denote the entry wise multiplication of two matrixes, also known as the Hadamard Productdef.
• Let $\mathbf {a} \parallel \mathbf {b} ​$ denote the concatenation of two vectors; if $\mathbf {a} \in \mathbb Z_p^n ​$ and $\mathbf {b} \in \mathbb Z_p^m ​$ then $\mathbf {a} \parallel \mathbf {b} \in \mathbb Z_p^{n+m} ​$.
• Let $p(X) = \sum _{i=0}^d { \mathbf {p_i} \cdot X^i} \in \mathbb Z_p^n [X]$ be a vector polynomial where each coefficient $\mathbf {p_i}$ is a vector in $\mathbb Z_p^n$.
• Let $\langle l(X),r(X) \rangle = \sum _{i=0}^d { \sum _{j=0}^i { \langle l_i,r_i \rangle \cdot X^{i+j}}} \in \mathbb Z_p [X]$ denote the inner-product between two vector polynomials $l(X),r(X)$.
• Let $t(X)=\langle l(X),r(X) \rangle$, then the inner-product is defined such that $t(x)=\langle l(x),r(x) \rangle$ holds for all $x \in \mathbb{Z_p}$.
• Let $C=g^a = \prod _{i=1}^n g_i^{a_i} \in \mathbb{G}$ be a binding (but not hiding) commitment to the vector $\mathbf {a} \in \mathbb Z_p^n$ where $\mathbf {g} = (g_1 \mspace{3mu} , \mspace{3mu} ... \mspace{3mu} , \mspace{3mu} g_n) \in \mathbb G^n$. Given vector $\mathbf {b} \in \mathbb Z_p^n$ with non-zero entries, $\mathbf {a} \circ \mathbf {b}$ is treated as a new commitment to $C$. For this let $g_i^\backprime =g_i^{(b_i^{-1})}$ such that $C= \prod _{i=1}^n (g_i^\backprime)^{a_i \cdot b_i}$. The binding property of this new commitment is inherited from the old commitment.
• Let $\mathbf a _{[:l]} = ( a_1 \mspace{3mu} , \mspace{3mu} . . . \mspace{3mu} , \mspace{3mu} a_l ) \in \mathbb F ^ l$ and $\mathbf a _{[l:]} = ( a_{1+1} \mspace{3mu} , \mspace{3mu} . . . \mspace{3mu} , \mspace{3mu} a_n ) \in \mathbb F ^ {n-l}$ be slices of vectors for $0 \le l \le n$ (using Python notation).
• Let $\mathbf {k}^n$ denote the vector containing the first $n$ powers of $k \in \mathbb Z_p^*$ such that $\mathbf {k}^n = (1,k,k^2, \mspace{3mu} ... \mspace{3mu} ,k^{n-1}) \in (\mathbb Z_p^*)^n$.
• Let $\mathcal{P}$ and $\mathcal{V}$ denote the prover and verifier respectively.
• Let $\mathcal{P_{IP}}$ and $\mathcal{V_{IP}} ​$ denote the prover and verifier in relation to inner-product calculations respectively.

### Pedersen Commitments and Elliptic Curve Pedersen Commitments

The basis of confidential transactions is the Pedersen Commitment scheme defined in .

A commitment scheme in a Zero-knowledge Proofdef is a cryptographic primitive that allows a prover $\mathcal{P}$ to commit to only a single chosen value/statement from a finite set without the ability to change it later (binding property), while keeping it hidden from a verifier $\mathcal{V}$ (hiding property). Both binding and hiding properties are then further classified in increasing levels of security to be computational, statistical or perfect:

• Computational means that no efficient algorithm running in a practical amount of time can reveal the commitment amount or produce fake commitments, except with a small probability.
• Statistical means that the probability of an adversary doing the same in a finite amount of time is negligible.
• Perfect means that a quantum adversary (an attacker with infinite computing power) cannot tell what amount has been committed to, and is unable to produce fake commitments.

No commitment scheme can simultaneously be perfectly binding and perfectly hiding (, ).

Two variations of the Pedersen Commitment scheme share the same security attributes:

• Pedersen Commitment: The Pedersen Commitment is a system for making a blinded, non-interactive commitment to a value (, , , , ).
• The generalized Pedersen Commitment definition follows (refer to Notation Used):

• Let $q$ be a large prime and $p$ be a large safe prime such that $p = 2q + 1$.
• Let $h$ be a random generator of cyclic group $\mathbb G$ such that $h$ is an element of $\mathbb Z_q^*$.
• Let $a$ be a random value and element of $\mathbb Z_q^*$ and calculate $g$ such that $g = h^a$.
• Let $r$ (the blinding factor) be a random value and element of $\mathbb Z_p^*$.
• The commitment to value $x$ is then determined by calculating $C(x,r) = h^r g^x$, which is called the Pedersen Commitment.
• The generator $h$ and resulting number $g$ are known as the commitment bases and should be shared along with $C(x,r)$, with whomever wishes to open the value.
• Pedersen Commitments are also additionally homomorphic, such that for messages $x_0$ and $x_1$ and blinding factors $r_0$ and $r_1$, we have $C(x_0,r_0) \cdot C(x_1,r_1) = C(x_0+x_1,r_0+r_1)$

• Elliptic Curve Pedersen Commitment: An efficient implementation of the Pedersen Commitmentdef will use secure Elliptic Curve Cryptography (ECC), which is based on the algebraic structure of elliptic curves over finite (prime) fields. Elliptic curve points are used as basic mathematical objects, instead of numbers. Note that traditionally in elliptic curve arithmetic, lower-case letters are used for ordinary numbers (integers) and upper-case letters for curve points (, , ).
• The generalized Elliptic Curve Pedersen Commitment definition follows (refer to Notation Used:

• Let $\mathbb F_p$ be the group of elliptic curve points, where $p$ is a large prime.
• Let $G \in \mathbb F_p$ be a random generator point (base point) and let $H \in \mathbb F_p$ be specially chosen so that the value $x_H$ to satisfy $H = x_H G$ cannot be found except if the Elliptic Curve DLP (ECDLP) is solved.
• Let $r$ (the blinding factor) be a random value and element of $\mathbb Z_p$.
• The commitment to value $x \in \mathbb Z_p$ is then determined by calculating $C(x,r) = rH + xG ​$, which is called the Elliptic Curve Pedersen Commitment.
• Elliptic curve point addition is analogous to multiplication in the originally defined Pedersen Commitmentdef. Thus $g^x$, the number $g$ multiplied by itself $m$ times, is analogous to $xG$, the elliptic curve point $G$ added to itself $x$ times. In this context, $xG$ is also a point in $\mathbb F_p$.

• In the Elliptic Curve context, $C(x,r) = rH + xG$ is then analogous to $C(x,r) = h^r g^x$.

• The number $H$ is what is known as a Nothing Up My Sleeve (NUMS) number. With secp256k1, the value of $H$ is the SHA256 hash of a simple encoding of the prespecified generator point $G$.

• Similar to Pedersen Commitments, the Elliptic Curve Pedersen Commitments are also additionally homomorphic, such that for messages $x$, $x_0$ and $x_1$, blinding factors $r$, $r_0$ and $r_1$ and scalar $k$, the following relation holds: $C(x_0,r_0) + C(x_1,r_1) = C(x_0+x_1,r_0+r_1)$ and $C(k \cdot x, k \cdot r) = k \cdot C(x, r)$.

• In secure implementations of ECC, it is as hard to guess $x$ from $xG$ as it is to guess $x$ from $g^x$. This is called the Elliptic Curve DLP (ECDLP).

• Practical implementations usually consist of three algorithms: Setup() to set up the commitment parameters; Commit() to commit to the message using the commitment parameters; and Open() to open and verify the commitment.

### Security Aspects of (Elliptic Curve) Pedersen Commitments

By virtue of their definition, Pedersen Commitments are only computationally binding but perfectly hiding. A simplified explanation follows.

If Alice wants to commit to a value $x$ that will be sent to Bob, who will at a later stage want Alice to prove that the value $x$ is the value that was used to generate the commitment $C$, then Alice will select random blinding factor $r$, calculate $C(x,r) = h^r g^x$ and send that to Bob. Later, Alice can reveal $x$ and $r$, and Bob can do the calculation and see that the commitment $C$ it produces is the same as the one Alice sent earlier.

Perhaps Alice or Bob has managed to build a computer that can solve the DLP and, given a public key, could find alternative solutions to $C(x,r) = h^r g^x$ in a reasonable time, i.e. $C(x,r) = h^{r^\prime} g^{x^\prime}$. This means, even though Bob can find values for $r^\prime$ and $x^\prime$ that produce $C$, he cannot know if those are the specific $x$ and $r$ that Alice chose, because there are so many that can produce the same $C$. Pedersen Commitments are thus perfectly hiding.

Although the Pederson Commitment is perfectly hiding, it does rely on the fact that Alice has NOT cracked the DLP to be able to calculate other pairs of input values to open the commitment to another value when challenged. The Pederson Commitment is thus only computationally binding.

## Bulletproof Protocols

Bulletproof protocols have multiple applications, most of which are discussed in Bulletproofs and Mimblewimble. The following list links these use cases to the different Bulletproof protocols:

• Bulletproofs provide short, non-interactive, zero-knowledge proofs without a trusted setup. The small size of Bulletproofs reduces overall cost. This has applicability in distributed systems where proofs are transmitted over a network or stored for a long time.

• Range Proof Protocol with Logarithmic Size provides short, single and aggregatable range proofs, and can be used with multiple blockchain protocols including Mimblewimble. These can be applied to normal transactions or to some smart contract, where committed values need to be proven to be in a specific range without revealing the values.

• The protocol presented in Aggregating Logarithmic Proofs can be used for Merkle proofs and proof of solvency without revealing any additional information.

• Range proofs can be compiled for a multi-party, single, joined confidential transaction for their known outputs using MPC Protocol for Bulletproofs. Users do not have to reveal their secret transaction values.

• Verifiable shuffles and multi-signatures with deterministic nonces can be implemented with Protocol 3.

• Bulletproofs present an efficient and short zero-knowledge proof for arbitrary Arithmetic Circuitsdef using Zero-knowledge Proof for Arithmetic Circuits.

• Various Bulletproof protocols can be applied to scriptless scripts, to make them non-interactive and not have to use Sigma protocols.

• Batch verifications can be done using Optimized Verifier using Multi-exponentiation and Batch Verification, e.g. a blockchain full node receiving a block of transactions needs to verify all transactions as well as range proofs.

A detailed mathematical discussion of the different Bulletproof protocols follows. Protocols 1, 2 and 3 are numbered consistently with . Refer to Notation Used.

Note: Full mathematical definitions and terms not defined are available in .

### Inner-product Argument (Protocol 1)

The first and most important building block of the Bulletproofs is its efficient algorithm to calculate an inner-product argument for two independent (not related) binding vector Pedersen Commitmentsdef. Protocol 1 is an argument of knowledge that the prover $\mathcal{P}$ knows the openings of two binding Pedersen vector commitments that satisfy a given inner product relation. Let inputs to the inner-product argument be independent generators $g,h \in \mathbb G^n$, a scalar $c \in \mathbb Z_p$ and $P \in \mathbb G$. The argument lets the prover $\mathcal{P}$ convince a verifier $\mathcal{V}$ that the prover $\mathcal{P}$ knows two vectors $\mathbf a, \mathbf b \in \mathbb Z^n_p ​$ such that $$P =\mathbf{g}^\mathbf{a}\mathbf{h}^\mathbf{b} \mspace{30mu} \mathrm{and} \mspace{30mu} c = \langle \mathbf {a} \mspace{3mu}, \mspace{3mu} \mathbf {b} \rangle$$

$P ​$ is referred to as the binding vector commitment to $\mathbf a, \mathbf b ​$. The inner product argument is an efficient proof system for the following relation:

$${ (\mathbf {g},\mathbf {h} \in \mathbb G^n , \mspace{12mu} P \in \mathbb G , \mspace{12mu} c \in \mathbb Z_p ; \mspace{12mu} \mathbf {a}, \mathbf {b} \in \mathbb Z^n_p ) \mspace{3mu} : \mspace{15mu} P = \mathbf{g}^\mathbf{a}\mathbf{h}^\mathbf{b} \mspace{3mu} \wedge \mspace{3mu} c = \langle \mathbf {a} \mspace{3mu}, \mspace{3mu} \mathbf {b} \rangle } \tag{1}$$

Relation (1) requires sending $2n$ elements to the verifier $\mathcal{V}$. The inner product $c = \langle \mathbf {a} \mspace{3mu}, \mspace{3mu} \mathbf {b} \rangle \$ can be made part of the vector commitment $P \in \mathbb G$. This will enable sending only $2 \log 2 (n)$ elements to the verifier $\mathcal{V}$ (explained in the next section). For a given $P \in \mathbb G$, the prover $\mathcal{P}$ proves that it has vectors $\mathbf {a}, \mathbf {b} \in \mathbb Z^n_p$ for which $P =\mathbf{g}^\mathbf{a}\mathbf{h}^\mathbf{b} \cdot u^{ \langle \mathbf {a}, \mathbf {b} \rangle }$. Here $u \in \mathbb G$ is a fixed group element with an unknown discrete-log relative to $\mathbf {g},\mathbf {h} \in \mathbb G^n ​$.

$${ (\mathbf {g},\mathbf {h} \in \mathbb G^n , \mspace{12mu} u,P \in \mathbb G ; \mspace{12mu} \mathbf {a}, \mathbf {b} \in \mathbb Z^n_p ) : \mspace{15mu} P = \mathbf{g}^\mathbf{a}\mathbf{h}^\mathbf{b} \cdot u^{ \langle \mathbf {a}, \mathbf {b} \rangle } } \tag{2}$$

A proof system for relation (2) gives a proof system for (1) with the same complexity, thus only a proof system for relation (2) is required.

Protocol 1 is then defined as the proof system for relation (2) as shown in Figure 1. The element $u$ is raised to a random power $x$ (the challenge) chosen by the verifier $\mathcal{V}$ to ensure that the extracted vectors $\mathbf {a}, \mathbf {b}$ from Protocol 2 satisfy $c = \langle \mathbf {a} , \mathbf {b} \rangle$. Figure 1: Bulletproofs Protocol 1 

The argument presented in Protocol 1 has the following Commitment Scheme properties:

• Perfect completeness (hiding): Every validity/truth is provable. Also refer to Definition 9 in .
• Statistical witness extended emulation (binding): Robust against either extracting a non-trivial discrete logarithm relation between $\mathbf {g} , \mathbf {h} , u$ or extracting a valid witness $\mathbf {a}, \mathbf {b}$.

### How Proof System for Protocol 1 Works, Shrinking by Recursion

Protocol 1 uses an inner product argument of two vectors $\mathbf a, \mathbf b \in \mathbb Z^n_p$ of size $n$. The Pedersen Commitment scheme allows a vector to be cut in half and the two halves to then be compressed together. Let $\mathrm H : \mathbb Z^{2n+1}_p \to \mathbb G$ be a hash function for commitment $P$, with $P = \mathrm H(\mathbf a , \mathbf b, \langle \mathbf a, \mathbf b \rangle)$. Note that commitment $P$ and thus $\mathrm H$ is additively homomorphic, therefore sliced vectors of $\mathbf a, \mathbf b \in \mathbb Z^n_p$ can be hashed together with inner product $c = \langle \mathbf a , \mathbf b \rangle \in \mathbb Z_p$. If $n ^\prime = n/2 ​$, starting with relation (2), then

\begin{aligned} \mathrm H(\mathbf a \mspace{3mu} , \mspace{3mu} \mathbf b \mspace{3mu} , \mspace{3mu} \langle \mathbf a , \mathbf b \rangle) &= \mathbf{g} ^\mathbf{a} \mathbf{h} ^\mathbf{b} \cdot u^{ \langle \mathbf a, \mathbf b \rangle} \mspace{20mu} \in \mathbb G \\ \mathrm H(\mathbf a_{[: n ^\prime]} \mspace{3mu} , \mspace{3mu} \mathbf a_{[n ^\prime :]} \mspace{3mu} , \mspace{3mu} \mathbf b_{[: n ^\prime]} \mspace{3mu} , \mspace{3mu} \mathbf b_{[n ^\prime :]} \mspace{3mu} , \mspace{3mu} \langle \mathbf {a}, \mathbf {b} \rangle) &= \mathbf g ^ {\mathbf a_{[: n ^\prime]}} _{[: n ^\prime]} \cdot \mathbf g ^ {\mathbf a^\prime_{[n ^\prime :]}} _{[n ^\prime :]} \cdot \mathbf h ^ {\mathbf b_{[: n ^\prime]}} _{[: n ^\prime]} \cdot \mathbf h ^ {\mathbf b^\prime_{[n ^\prime :]}} _{[n ^\prime :]} \cdot u^{\langle \mathbf {a}, \mathbf {b} \rangle} \mspace{20mu} \in \mathbb G \end{aligned}

Commitment $P$ can then further be sliced into $L$ and $R$ as follows:

\begin{aligned} P &= \mathrm H(\mspace{3mu} \mathbf a_{[: n ^\prime]} \mspace{6mu} , \mspace{6mu} \mathbf a_{[n ^\prime :]} \mspace{6mu} , \mspace{6mu} \mathbf b_{[: n ^\prime]} \mspace{6mu} , \mspace{6mu} \mathbf b_{[n ^\prime :]} \mspace{6mu} , \mspace{6mu} \langle \mathbf {a}, \mathbf {b} \rangle \mspace{49mu}) \mspace{20mu} \in \mathbb G \\ L &= \mathrm H(\mspace{3mu} 0 ^ {n ^\prime} \mspace{18mu} , \mspace{6mu} \mathbf a_{[: n ^\prime]} \mspace{6mu} , \mspace{6mu} \mathbf b_{[n ^\prime :]} \mspace{6mu} , \mspace{6mu} 0 ^ {n ^\prime} \mspace{18mu} , \mspace{6mu} \langle \mathbf {a_{[: n ^\prime]}} , \mathbf {b_{[n ^\prime :]}} \rangle \mspace{3mu}) \mspace{20mu} \in \mathbb G \\ R &= \mathrm H(\mspace{3mu} \mathbf a_{[n ^\prime :]} \mspace{6mu} , \mspace{6mu} 0 ^ {n ^\prime} \mspace{18mu} , \mspace{6mu} 0 ^ {n ^\prime} \mspace{18mu} , \mspace{6mu} \mathbf b_{[: n ^\prime]} \mspace{6mu} , \mspace{6mu} \langle \mathbf {a_{[n ^\prime :]}} , \mathbf {b_{[: n ^\prime]}} \rangle \mspace{3mu}) \mspace{20mu} \in \mathbb G \end{aligned}

The first reduction step is as follows:

• The prover $\mathcal{P}$ calculates $L,R \in \mathbb G$ and sends it to the verifier $\mathcal{V}$.

#### Batch Verification

A further important optimization concerns the verification of multiple proofs. The essence of the verification is to calculate a large multi-exponentiation. Batch verification is applied in order to reduce the number of expensive exponentiations. This is based on the observation that checking $g^x = 1 \mspace 3mu \wedge \mspace 3mu g^y = 1 ​$ can be checked by drawing a random scalar $\alpha ​$ from a large enough domain and checking that $g^{\alpha x + y} = 1 ​$. With high probability, the latter equation implies the first. When applied to multi-exponentiations, $2n ​$ exponentiations can be saved per additional proof. Verifying $m ​$ distinct range proofs of size $n ​$ only requires a single multi-exponentiation of size $2n+2+m \cdot (2 \cdot \log (n) + 5 ) ​$ along with $O ( m \cdot n ) ​$ scalar operations.

## Evolving Bulletproof Protocols

Interstellar  recently introduced the Programmable Constraint Systems for Bulletproofs , an evolution of Zero-knowledge Proof for Arithmetic Circuits, extending it to support proving arbitrary statements in zero-knowledge using a constraint system, bypassing arithmetic circuits altogether. They provide an Application Programmers Interface (API) for building a constraint system directly, without the need to construct arithmetic expressions and then transform them into constraints. The Bulletproof constraint system proofs are then used as building blocks for a confidential assets protocol called Cloak.

The constraint system has three kinds of variables:

• High-level witness variables
• known only to the prover $\mathcal{P}$, as external inputs to the constraint system;
• represented as individual Pedersen Commitments to the external variables in Bulletproofs.
• Low-level witness variables
• known only to the prover $\mathcal{P}$, as internal to the constraint system;
• representing the inputs and outputs of the multiplication gates.
• Instance variables
• known to both the prover $\mathcal{P}$ and the verifier;
• $\mathcal{V}$, as public parameters;
• represented as a family of constraint systems parameterized by public inputs (compatible with Bulletproofs);
• folding all instance variables into a single constant parameter internally.

Instance variables can select the constraint system out of a family for each proof. The constraint system becomes a challenge from a verifier $\mathcal{V} ​$ to a prover $\mathcal{P} ​$, where some constraints are generated randomly in response to the prover's $\mathcal{P} ​$ commitments. Challenges to parametrize constraint systems make the resulting proof smaller, requiring only $O(n) ​$ multiplications instead of $O(n^2) ​$ in the case of verifiable shuffles when compared to a static constraint system.

Merlin transcripts  employing the Fiat-Shamir Heuristicdef are used to generate the challenges. The challenges are bound to the high-level witness variables (the external inputs to the constraint system), which are added to the transcript before any of the constraints are created. The prover $\mathcal{P}$ and verifier $\mathcal{V}$ can then compute weights for some constraints with the use of the challenges.

Because the challenges are not bound to low-level witness variables, the resulting construction can be unsafe. Interstellar are working on an improvement to the protocol that would allow challenges to be bound to a subset of the low-level witness variables, and have a safer API using features of Rust’s type system.

The resulting API provides a single code path used by both the prover $\mathcal{P} ​$ and verifier $\mathcal{V} ​$ to allocate variables and define constraints. This is organized into a hierarchy of task-specific gadgets, which manages allocation, assignment and constraints on the variables, ensuring that all variables are constrained. Gadgets interact with mutable constraint system objects, which are specific to the prover $\mathcal{P} ​$ and verifier $\mathcal{V} ​$. They also receive secret variables and public parameters and generate challenges.

The Bulletproofs library  does not provide any standard gadgets, but only an API for the constraint system. Each protocol built on top of the Bulletproofs library must create its own collection of gadgets to enable building a complete constraint system out of them. Figure 11 shows the Interstellar Bulletproof zero-knowledge proof protocol built with their programmable constraint system: Figure 11: Interstellar Bulletproof Zero-knowledge Proof Protocol 

## Conclusions, Observations and Recommendations

• Bulletproofs have many potential use cases or applications, but are still under development. A new confidential blockchain protocol such as Tari should carefully consider expanded use of Bulletproofs to maximally leverage functionality of the code base.

• Bulletproofs are not done yet, as illustrated in Evolving Bulletproof Protocols, and their further development and efficient implementation have a lot of traction in the community.

• Bünz et al.  proposed that the switch commitment scheme defined by Ruffing et al.  can be used for Bulletproofs if doubts in the underlying cryptographic hardness (discrete log) assumption arise in future. The switch commitment scheme allows for a blockchain with proofs that are currently only computationally binding to later switch to a proof system that is perfectly binding and secure against quantum adversaries; this will weaken the perfectly hiding property as a drawback and slow down all proof calculations. In the Bünz et al.  proposal, all Pedersen Commitments will be replaced with ElGamal Commitmentsdef to move from computationally binding to perfectly binding. They also gave further ideas about how the ElGamal commitments can possibly be enhanced to improve the hiding property to be statistical or perfect. (Refer to the Grin projects' implementation here.)

• It is important that developers understand more about the fundamental underlying mathematics when implementing something like Bulletproofs, even if they just reuse libraries developed by someone else.

• With the standard MPC protocol implementation, there is no guarantee that the dealer behaves honestly according to the protocol and generates challenges honestly. The protocol can be extended to be more secure if all parties receive partial proof elements and independently compute aggregated challenges.