# bulletproofs

 Version on this page: 0.4.0 LTS Haskell 13.4: 0.4.0 Stackage Nightly 2019-01-23: 0.4.0 Latest on Hackage: 0.4.0

See all snapshots `bulletproofs` appears in

Maintained by

Bulletproofs are short zero-knowledge 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 non-interactive using the Fiat-Shamir heuristic.

The core algorithm of Bulletproofs is the inner-product 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 inner-product proof that reduces overall communication complexity of the argument to only 2log2(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 aL a vector of bit such that <aL, 2n> = v. The components of aL are the binary digits of v. We construct a complementary vector aR = aL1n and require that aLaR = 0 holds.

• P -> V : A, S - where A and S are blinded Pedersen commitments to aL and aR.

$\&space;&space;A&space;=&space;h&space;\cdot&space;\alpha&space;+&space;\textbf{g}&space;\cdot&space;\textbf{a}_L&space;+&space;\textbf{h}&space;\cdot&space;\textbf{a}_R&space;\in&space;\mathbb{G}&space;$

$\&space;&space;S&space;=&space;h&space;\cdot&space;\rho&space;+&space;\textbf{g}&space;\cdot&space;\textbf{s}_L&space;+&space;\textbf{h}&space;\cdot&space;\textbf{s}_R&space;\in&space;\mathbb{G}&space;$

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

• P -> V : T1, T2 - where T1 and T2 are commitments to the coefficients t1, of a polynomial t constructed from the existing values in the protocol.

$\&space;&space;\textbf{l}&space;=&space;l(x)&space;=&space;\textbf{a}_L&space;-&space;z&space;\cdot&space;\textbf{1}^n&space;+&space;\textbf{s}_L&space;\cdot&space;x&space;\in&space;\mathbb{Z}^n_p$

$\&space;&space;\textbf{r}&space;=&space;r(x)&space;=&space;\textbf{y}^n&space;\circ&space;(\textbf{a}_R&space;+&space;z&space;\cdot&space;\textbf{1}^n&space;+&space;\textbf{s}_R&space;\cdot&space;x&space;)&space;+&space;z^2&space;\cdot&space;\textbf{2}^n&space;\in&space;\mathbb{Z}^n_p&space;$

$\&space;&space;t&space;=&space;\langle&space;\textbf{l},&space;\textbf{r}&space;\rangle&space;\in&space;\mathbb{Z}_p$

$\&space;T_i&space;=&space;g&space;\cdot&space;t_i&space;+&space;h&space;\cdot&space;\tau_i&space;\in&space;\mathbb{G},&space;\hspace{3em}&space;i&space;=&space;{1,&space;2}&space;$

• 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.

$\&space;&space;\tau_x&space;=&space;\tau_2&space;\cdot&space;x^2&space;+&space;\tau_1&space;\cdot&space;x&space;+&space;z^2&space;\cdot&space;\gamma&space;\in&space;\mathbb{Z}_p&space;$

$\&space;&space;\mu&space;=&space;\alpha&space;+&space;\rho&space;\cdot&space;x&space;\in&space;\mathbb{Z}_p&space;$

See Prover.hs for implementation details.

The interaction described is made non-interactive using the Fiat-Shamir Transform wherein all the random challenges made by V are replaced with a hash of the transcript up until that point.

# Inner-product range proof

The size of the proof is further reduced by leveraging the compact O(logn) inner product proof.

The inner-product argument in the protocol allows to prove knowledge of vectors l and r, whose inner product is t and the commitment PG 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 inner-product argument transmits only 2 [log2] + 2 elements. In total, the prover sends only 2 [log2(n)] + 4 group elements and 5 elements in Zp

# Aggregating Logarithmic Proofs

We can construct a single proof of range of multiple values, while only incurring an additional space cost of 2 log2(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 [log2 (n * m)] + 4 group elements and 5 elements in Zp.

# Usage

## Single range proof:

``````import qualified Bulletproofs.RangeProof as RP

testSingleRangeProof :: (Integer, Integer) -> IO Bool
testSingleRangeProof (v, vBlinding) = do
let vCommit = commit v vBlinding
-- n needs to be a power of 2
n = 2 ^ 8
upperBound = 2 ^ n

-- Prover
proofE <- runExceptT \$ RP.generateProof upperBound (v, vBlinding)

-- Verifier
case proofE of
Left err -> panic \$ show err
Right (proof@RangeProof{..})
-> pure \$ RP.verifyProof upperBound vCommit proof
``````

## Multi range proof:

``````import qualified Bulletproofs.MultiRangeProof as MRP

testMultiRangeProof :: [(Integer, Integer)] -> IO Bool
testMultiRangeProof vsAndvBlindings = do
let vCommits = fmap (uncurry commit) vsAndvBlindings
-- n needs to be a power of 2
n = 2 ^ 8
upperBound = 2 ^ n

-- Prover
proofE <- runExceptT \$ MRP.generateProof upperBound vsAndvBlindings

-- Verifier
case proofE of
Left err -> panic \$ show err
Right (proof@RangeProof{..})
-> pure \$ MRP.verifyProof upperBound vCommits proof
``````

The dimension n needs to be a power of 2. This implementation offers support for SECp256k1, a Koblitz curve. Further information about this curve can be found in the Uplink docs: SECp256k1 curve

# Zero-knowledge proof for Arithmetic Circuits

An arithmetic circuit over a field and variables (a1, …, an) 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 zero-knowledge argument for arithmetic circuits using the inner product argument, which allows to get a proof of size 2 log2(n) + 13 elements and include committed values as inputs to the arithmetic circuit.

In the protocol, the Prover proves that the hadamard product of aL and aR 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 qualified Bulletproofs.ArithmeticCircuit

--  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 Fq
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 :: ([Fq], [Fq]) -> ArithCircuit Fq -> IO Bool
testArithCircuitProof (aL, aR) arithCircuit = do
let n = 4
m = 2
q = 2

-- Multiplication constraints
let aO = aL `hadamardp` aR

-- Linear constraints
v0 = sum aL
v1 = sum aR

commitBlinders <- replicateM m Fq.random
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
``````

References:

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

2. Groth J. “Linear Algebra with Sub-linear Zero-Knowledge Arguments”. University College London, 2009

3. Bootle J., Cerully A., Chaidos P., Groth J, Petit C. “Efficient Zero-Knowledge Arguments for Arithmetic Circuits in the Discrete Log Setting”. University College London and University of Oxford, 2016.

Notation:

• <> :Inner product
• a: Vector

``````Copyright 2018 Adjoint Inc

you may not use this file except in compliance with the License.
You may obtain a copy of the License at

Unless required by applicable law or agreed to in writing, software
WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
See the License for the specific language governing permissions and
``````

# Changelog for bulletproofs

## 0.1

• Initial release.
• Implementation of the Bulletproofs protocol for range proofs
• Use of the improved inner-product argument to reduce the communication complexity
• Support for SECp256k1 curve

## 0.2

• Prove and verify computations of arithmetic circuits using Bulletproofs protocol.
• Extend range proofs with support for multi-range proofs.
• Add documentation and provide examples to explain and use arithmetic circuits.
• Provide examples for using aggregated range proofs.