# 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. [1]. 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 [1]. 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 [15].

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 ([12], [13]).

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 ([1], [3], [8], [14], [15]).
• 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 ([26], [27], [28]).
• 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 [1]. Refer to Notation Used.

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

### 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 [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 [1].
• 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 [24] recently introduced the Programmable Constraint Systems for Bulletproofs [23], 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 [25] 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 [22] 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 [23]

## 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. [1] proposed that the switch commitment scheme defined by Ruffing et al. [10] 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. [1] 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.

## References

[1] B. Bünz, J. Bootle, D. Boneh, A. Poelstra, P. Wuille and G. Maxwell, "Bulletproofs: Short Proofs for Confidential Transactions and More", Blockchain Protocol Analysis and Security Engineering 2018 [online]. Available: http://web.stanford.edu/~buenz/pubs/bulletproofs.pdf. Date accessed: 2018‑09‑18.

[2] J. Bootle, A. Cerulli, P. Chaidos, J. Groth and C. Petit, "Efficient Zero-knowledge Arguments for Arithmetic Circuits in the Discrete Log Setting", Annual International Conference on the Theory and Applications of Cryptographic Techniques, pp. 327‑357. Springer, 2016 [online]. Available: https://eprint.iacr.org/2016/263.pdf. Date accessed: 2018‑09‑21.

[3] A. Poelstra, A. Back, M. Friedenbach, G. Maxwell G. and P. Wuille, "Confidential Assets", Blockstream [online]. Available: https://blockstream.com/bitcoin17-final41.pdf. Date accessed: 2018‑09‑25.

[4] Wikipedia: "Zero-knowledge Proof" [online]. Available: https://en.wikipedia.org/wiki/Zero-knowledge_proof. Date accessed: 2018‑09‑18.

[5] Wikipedia: "Discrete Logarithm" [online]. Available: https://en.wikipedia.org/wiki/Discrete_logarithm. Date accessed: 2018‑09‑20.

[6] A. Fiat and A. Shamir, "How to Prove Yourself: Practical Solutions to Identification and Signature Problems", CRYPTO 1986: pp. 186‑194 [online]. Available: https://link.springer.com/content/pdf/10.1007%2F3-540-47721-7_12.pdf. Date accessed: 2018‑09‑20.

[7] D. Bernhard, O. Pereira and B. Warinschi, "How not to Prove Yourself: Pitfalls of the Fiat-Shamir Heuristic and Applications to Helios" [online]. Available: https://link.springer.com/content/pdf/10.1007%2F978-3-642-34961-4_38.pdf. Date accessed: 2018‑09‑20.

[8] "Pedersen-commitment: An Implementation of Pedersen Commitment Schemes" [online]. Available: https://hackage.haskell.org/package/pedersen-commitment. Date accessed: 2018‑09‑25.

[9] "Zero Knowledge Proof Standardization - An Open Industry/Academic Initiative" [online]. Available: https://zkproof.org/documents.html. Date accessed: 2018‑09‑26.

[10] T. Ruffing and G. Malavolta, "Switch Commitments: A Safety Switch for Confidential Transactions" [online]. Available: https://eprint.iacr.org/2017/237.pdf. Date accessed: 2018‑09‑26.

[11] GitHub: "adjoint-io/Bulletproofs, Bulletproofs are Short Non-interactive Zero-knowledge Proofs that Require no Trusted Setup" [online]. Available: https://github.com/adjoint-io/Bulletproofs. Date accessed: 2018‑09‑10.

[12] Wikipedia: "Commitment Scheme" [online]. Available: https://en.wikipedia.org/wiki/Commitment_scheme. Date accessed: 2018‑09‑26.

[13] Cryptography Wikia: "Commitment Scheme" [online]. Available: http://cryptography.wikia.com/wiki/Commitment_scheme. Date accessed: 2018‑09‑26.

[14] Adjoint Inc. Documentation: "Pedersen Commitment Scheme" [online]. Available: https://www.adjoint.io/docs/cryptography.html#pedersen-commitment-scheme. Date accessed: 2018‑09‑27.

[15] T. Pedersen. "Non-interactive and Information-theoretic Secure Verifiable Secret Sharing" [online]. Available: https://www.cs.cornell.edu/courses/cs754/2001fa/129.pdf. Date accessed: 2018‑09‑27.

[16] A. Sadeghi and M. Steiner, "Assumptions Related to Discrete Logarithms: Why Subtleties Make a Real Difference" [online]. Available: http://www.semper.org/sirene/publ/SaSt_01.dh-et-al.long.pdf. Date accessed: 2018‑09‑24.

[17] P. Sharma P, A. Gupta and S. Sharma, "Intensified ElGamal Cryptosystem (IEC)", International Journal of Advances in Engineering & Technology, January 2012 [online].* Available: http://www.e-ijaet.org/media/58I6-IJAET0612695.pdf. Date accessed: 2018‑10‑09.

[18] Y. Tsiounis and M. Yung M, "On the Security of ElGamal Based Encryption" [online]. Available: https://drive.google.com/file/d/16XGAByoXse5NQl57v_GldJwzmvaQlS94/view. Date accessed: 2018‑10‑09.

[19] Wikipedia: "Decisional Diffie–Hellman Assumption" [online]. Available: https://en.wikipedia.org/wiki/Decisional_Diffie%E2%80%93Hellman_assumption. Date accessed: 2018‑10‑09.

[20] Wikipedia: "Arithmetic Circuit Complexity" [online]. Available: https://en.wikipedia.org/wiki/Arithmetic_circuit_complexity. Date accessed: 2018‑11‑08.

[22] Dalek Cryptography - Crate Bulletproofs [online]. Available: https://doc.dalek.rs/bulletproofs/index.html. Date accessed: 2018‑11‑12.

[23] "Programmable Constraint Systems for Bulletproofs" [online]. Available: https://medium.com/interstellar/programmable-constraint-systems-for-bulletproofs-365b9feb92f7. Date accessed: 2018‑11‑22.

[24] Inter/stellar website [online]. Available: https://interstellar.com. Date accessed: 2018‑11‑22.

[25] "Dalek Cryptography - Crate Merlin" [online]. Available: https://doc.dalek.rs/merlin/index.html. Date accessed: 2018‑11‑22.

[26] B. Franca, "Homomorphic Mini-blockchain Scheme", April 2015 [online]. Available: http://cryptonite.info/files/HMBC.pdf. Date accessed: 2018‑11‑22.

[27] C. Franck and J. Großschädl, "Efficient Implementation of Pedersen Commitments Using Twisted Edwards Curves", University of Luxembourg [online]. Available: http://orbilu.uni.lu/bitstream/10993/33705/1/MSPN2017.pdf. Date accessed: 2018‑11‑22.

[28] A. Gibson, "An Investigation into Confidential Transactions", July 2018 [online]. Available: https://github.com/AdamISZ/ConfidentialTransactionsDoc/blob/master/essayonCT.pdf. Date accessed: 2018‑11‑22.

[29] "Dalek Cryptography - Module bulletproofs::range_proof_mpc" [online]. Available: https://doc-internal.dalek.rs/bulletproofs/range_proof_mpc/index.html. Date accessed: 2019‑07‑10.

[30] "What is the difference between honest verifier zero knowledge and zero knowledge?" [Online]. Available: https://crypto.stackexchange.com/questions/40436/what-is-the-difference-between-honest-verifier-zero-knowledge-and-zero-knowledge. Date accessed: 2019‑11‑12.

[31] "600.641 Special Topics in Theoretical Cryptography - Lecture 11: Honest Verifier ZK and Fiat-Shamir" [online]. Available: https://www.cs.jhu.edu/~susan/600.641/scribes/lecture11.pdf. Date accessed: 2019‑11‑12.

[32] Wikipedia: "Witness-indistinguishable proof" [online]. Available: https://en.wikipedia.org/wiki/Witness-indistinguishable_proof. Date accessed: 2019‑11‑12.

## Appendices

### Appendix A: Definition of Terms

Definitions of terms presented here are high level and general in nature. Full mathematical definitions are available in the cited references.

• Arithmetic Circuits: An arithmetic circuit $C$ over a field $F$ and variables $(x_1, ..., x_n)$ is a directed acyclic graph whose vertices are called gates. Arithmetic circuits can alternatively be described as a list of addition and multiplication gates with a collection of linear consistency equations relating the inputs and outputs of the gates. The size of an arithmetic circuit is the number of gates in it, with the depth being the length of the longest directed path. Upper bounding the complexity of a polynomial $f$ is to find any arithmetic circuit that can calculate $f$, whereas lower bounding is to find the smallest arithmetic circuit that can calculate $f$. An example of a simple arithmetic circuit with size six and depth two that calculates a polynomial is shown here ([11], [20]):

• Discrete Logarithm/Discrete Logarithm Problem (DLP): In the mathematics of real numbers, the logarithm $\log_b^a$ is a number $x$ such that $b^x=a$​, for given numbers $a$ and $b ​$. Analogously, in any group $G$ , powers $b^k$ can be defined for all integers $k$, and the discrete logarithm $\log_ba$ is an integer $k$ such that $b^k=a$​. Algorithms in public-key cryptography base their security on the assumption that the discrete logarithm problem over carefully chosen cyclic finite groups and cyclic subgroups of elliptic curves over finite fields has no efficient solution ([5], [16]).
• ElGamal Commitment/Encryption: An ElGamal commitment is a Pedersen Commitmentdef with an additional commitment $g^r$ to the randomness used. The ElGamal encryption scheme is based on the Decisional Diffe-Hellman (DDH) assumption and the difficulty of the DLP for finite fields. The DDH assumption states that it is infeasible for a Probabilistic Polynomial-time (PPT) adversary to solve the DDH problem ([1], [17], [18], [19]). Note: The ElGamal encryption scheme should not be confused with the ElGamal signature scheme.
• Fiat–Shamir Heuristic/Transformation: The Fiat–Shamir heuristic is a technique in cryptography to convert an interactive public-coin protocol (Sigma protocol) between a prover $\mathcal{P}$ and a verifier $\mathcal{V}$ into a one-message (non-interactive) protocol using a cryptographic hash function ([6], [7]).
• The prover $\mathcal{P}$ will use a Prove() algorithm to calculate a commitment $A$ with a statement $Y$ that is shared with the verifier $\mathcal{V}$ and a secret witness value $w$ as inputs. The commitment $A$ is then hashed to obtain the challenge $c$, which is further processed with the Prove() algorithm to calculate the response $f$. The single message sent to the verifier $\mathcal{V}$ then contains the challenge $c$ and response $f$.

• The verifier $\mathcal{V}$ is then able to compute the commitment $A$ from the shared statement $Y$, challenge $c$ and response $f$. The verifier $\mathcal{V}$ will then use a Verify() algorithm to verify the combination of shared statement $Y$, commitment $A$, challenge $c$ and response $f$.

• A weak Fiat–Shamir transformation can be turned into a strong Fiat–Shamir transformation if the hashing function is applied to the commitment $A$ and shared statement $Y$ to obtain the challenge $c$ as opposed to only the commitment $A$.

• Hadamard Product: In mathematics, the Hadamard product is a binary operation that takes two matrices $\mathbf {A} , \mathbf {B}$ of the same dimensions, and produces another matrix of the same dimensions where each element $i,j$ is the product of elements $i,j$ of the original two matrices. The Hadamard product $\mathbf {A} \circ \mathbf {B}$ is different from normal matrix multiplication, most notably because it is also commutative $[ \mathbf {A} \circ \mathbf {B} = \mathbf {B} \circ \mathbf {A} ]$ ​along with being associative $[ \mathbf {A} \circ ( \mathbf {B} \circ \mathbf {C} ) = ( \mathbf {A} \circ \mathbf {B} ) \circ \mathbf {C} ]$ and distributive over addition $[ \mathbf {A} \circ ( \mathbf {B} + \mathbf {C} ) = \mathbf {A} \circ \mathbf {B} + \mathbf {A} \circ \mathbf {C} ]$ ([21]).

$$\mathbf {A} \circ \mathbf {B} = \mathbf {C} = (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} )$$

• Zero-knowledge Proof/Protocol: In cryptography, a zero-knowledge proof/protocol is a method by which one party (the prover $\mathcal{P}$) can convince another party (the verifier $\mathcal{V}$) that a statement $Y$ is true, without conveying any information apart from the fact that the prover $\mathcal{P}$ knows the value of $Y$. The proof system must be complete, sound and zero-knowledge ([4], [9]).
• Complete: If the statement is true, and both the prover $\mathcal{P}$ and verifier $\mathcal{V}$ follow the protocol, the verifier will accept.

• Sound: If the statement is false, and the verifier $\mathcal{V}$ follows the protocol, the verifier $\mathcal{P}$ will not be convinced.

• Zero-knowledge: If the statement is true, and the prover $\mathcal{P}$ follows the protocol, the verifier $\mathcal{V}$ will not learn any confidential information from the interaction with the prover $\mathcal{P}$ apart from the fact that the statement is true.