Bulletproofs are short zeroknowledge arguments of knowledge that do not require a trusted setup.
Argument systems are proof systems with computational soundness.
Bulletproofs are suitable for proving statements on committed values, such as range proofs, verifiable suffles, arithmetic circuits, etc.
They rely on the discrete logarithmic assumption and are made noninteractive using
the FiatShamir heuristic.
The core algorithm of Bulletproofs is the innerproduct algorithm presented by Groth [2].
The algorithm provides an argument of knowledge of two binding vector Pedersen commitments that satisfy a given inner product relation.
Bulletproofs build on the techniques of Bootle et al. [3] to introduce a communication efficient innerproduct proof that reduces
overall communication complexity of the argument to only 2log_{2}(n) where n is the dimension
of the two vectors of commitments.
Range proofs
Bulletproofs present a protocol for conducting short and aggregatable range proofs.
They encode a proof of the range of a committed number in an inner product, using polynomials.
Range proofs are proofs that a secret value lies in a certain interval.
Range proofs do not leak any information about the secret value, other
than the fact that they lie in the interval.
The proof algorithm can be sketched out in 5 steps:
Let v be a value in [0, n) and a_{L} a vector of bit such that <a_{L}, 2^{n}> = v.
The components of a_{L} are the binary digits of v.
We construct a complementary vector a_{R} = a_{L} − 1^{n}
and require that a_{L} ◦ a_{R} = 0 holds.
 P > V : A, S  where A and S are blinded Pedersen commitments to a_{L} and a_{R}.

V > P : y, z  Verifier sends challenges y and z to fix A and S.

P > V : T_{1}, T_{2}  where T_{1} and T_{2} are commitments to
the coefficients t_{1}, of a polynomial t constructed from the existing values in the protocol.

V > P : x  Verifier challenges Prover with value x.

P > V : tau, mu, t, l, r  Prover sends several commitments that the verifier will then check.
See Prover.hs for implementation details.
The interaction described is made noninteractive using the FiatShamir Transform wherein all the random
challenges made by V are replaced with a hash of the transcript up until that point.
Innerproduct range proof
The size of the proof is further reduced by leveraging the compact O(log_{n}) inner product proof.
The innerproduct argument in the protocol allows to prove knowledge of vectors l and r, whose inner product is t and
the commitment P ∈ G is a commitment of these two vectors. We can therefore replace sending
(tau, mu, t, l, r) with a transfer of (tau, mu, t) and an execution of an inner product argument.
Then, instead of sharing l and r, which has a communication cost of 2n elements, the innerproduct
argument transmits only 2 [log_{2}] + 2 elements. In total, the prover sends only 2 [log_{2}(n)] + 4
group elements and 5 elements in Z_{p}
Aggregating Logarithmic Proofs
We can construct a single proof of range of multiple values, while only incurring an additional space cost of 2 log_{2}(m) for
m additional values v, as opposed to a multiplicative factor of m when creating m independent range proofs.
The aggregate range proof makes use of the inner product argument. It uses 2 [log_{2} (n * m)] + 4 group elements and 5 elements in Z_{p}.
See Multi range proof example
Usage
Single range proof:
import Data.Curve.Weierstrass.SECP256K1 (Fr)
import qualified Bulletproofs.RangeProof as RP
import Bulletproofs.Utils (commit)
testSingleRangeProof :: Integer > (Fr, Fr) > IO Bool
testSingleRangeProof upperBound (v, vBlinding) = do
let vCommit = commit v vBlinding
 Prover
proofE < runExceptT $ RP.generateProof upperBound (v, vBlinding)
 Verifier
case proofE of
Left err > panic $ show err
Right proof@RP.RangeProof{..}
> pure $ RP.verifyProof upperBound vCommit proof
Multi range proof:
import Data.Curve.Weierstrass.SECP256K1 (Fr)
import qualified Bulletproofs.MultiRangeProof as MRP
import Bulletproofs.Utils (commit)
testMultiRangeProof :: Integer > [(Fr, Fr)] > IO Bool
testMultiRangeProof upperBound vsAndvBlindings = do
let vCommits = fmap (uncurry commit) vsAndvBlindings
 Prover
proofE < runExceptT $ MRP.generateProof upperBound vsAndvBlindings
 Verifier
case proofE of
Left err > panic $ show err
Right proof@RP.RangeProof{..}
> pure $ MRP.verifyProof upperBound vCommits proof
Note that the upper bound u must be such that u = 2 ^ n
, where n is also a power of 2.
This implementation uses the elliptic curve secp256k1, a Koblitz curve, which
has 128 bit security.
See Range proofs examples for further details.
Zeroknowledge proof for Arithmetic Circuits
An arithmetic circuit over a field and variables (a_{1}, ..., a_{n}) is a directed acyclic graph whose vertices are called gates.
Arithmetic circuit can be described alternatively as a list of multiplication gates with a collection of linear consistency equations
relating the inputs and outputs of the gates. Any circuit described as an acyclic graph can be efficiently converted into this alternative description.
Bulletproofs present a protocol to generate zeroknowledge argument for arithmetic circuits using the inner product argument,
which allows to get a proof of size 2 log_{2}(n) + 13 elements and include committed values as inputs to the arithmetic circuit.
In the protocol, the Prover proves that the hadamard product of a_{L} and a_{R} and a set of linear constraints hold.
The input values v used to generate the proof are then committed and shared with the Verifier.
import Data.Curve.Weierstrass.SECP256K1 (Fr)
import Data.Field.Galois (rnd)
import Bulletproofs.ArithmeticCircuit
import Bulletproofs.Utils (hadamard, commit)
 Example:
 2 linear constraints (q = 2):
 aL[0] + aL[1] + aL[2] + aL[3] = v[0]
 aR[0] + aR[1] + aR[2] + aR[3] = v[1]

 4 multiplication constraints (implicit) (n = 4):
 aL[0] * aR[0] = aO[0]
 aL[1] * aR[1] = aO[1]
 aL[2] * aR[2] = aO[2]
 aL[3] * aR[3] = aO[3]

 2 input values (m = 2)
arithCircuitExample :: ArithCircuit Fr
arithCircuitExample = ArithCircuit
{ weights = GateWeights
{ wL = [[1, 1, 1, 1]
,[0, 0, 0, 0]]
, wR = [[0, 0, 0, 0]
,[1, 1, 1, 1]]
, wO = [[0, 0, 0, 0]
,[0, 0, 0, 0]]
}
, commitmentWeights = [[1, 0]
,[0, 1]]
, cs = [0, 0]
}
testArithCircuitProof :: ([Fr], [Fr]) > ArithCircuit Fr > IO Bool
testArithCircuitProof (aL, aR) arithCircuit = do
let m = 2
 Multiplication constraints
let aO = aL `hadamard` aR
 Linear constraints
v0 = sum aL
v1 = sum aR
commitBlinders < replicateM m rnd
let commitments = zipWith commit [v0, v1] commitBlinders
let arithWitness = ArithWitness
{ assignment = Assignment aL aR aO
, commitments = commitments
, commitBlinders = commitBlinders
}
proof < generateProof arithCircuit arithWitness
pure $ verifyProof commitments proof arithCircuit
See Aritmetic circuit example for further details.
References:

Bunz B., Bootle J., Boneh D., Poelstra A., Wuille P., Maxwell G.
"Bulletproofs: Short Proofs for Confidential Transactions and More". Stanford, UCL, Blockstream, 2017

Groth J. "Linear Algebra with Sublinear ZeroKnowledge Arguments". University College London, 2009

Bootle J., Cerully A., Chaidos P., Groth J, Petit C. "Efficient ZeroKnowledge Arguments for
Arithmetic Circuits in the Discrete Log Setting". University College London and University of Oxford, 2016.
Notation:
 ◦ : Hadamard product
 <> :Inner product
 a: Vector
License
Copyright 2018 Adjoint Inc
Licensed under the Apache License, Version 2.0 (the "License");
you may not use this file except in compliance with the License.
You may obtain a copy of the License at
http://www.apache.org/licenses/LICENSE2.0
Unless required by applicable law or agreed to in writing, software
distributed under the License is distributed on an "AS IS" BASIS,
WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
See the License for the specific language governing permissions and
limitations under the License.