bulletproofs

[ cryptography, library ] [ Propose Tags ]

Please see the README on GitHub at https://github.com/adjoint-io/bulletproofs#readme


[Skip to Readme]
Versions [faq] 0.1.0, 0.2.0, 0.2.1, 0.3.0, 0.4.0
Change log ChangeLog.md
Dependencies arithmoi, base (>=4.7 && <5), containers, cryptonite, memory, protolude (>=0.2), text [details]
License LicenseRef-Apache
Author
Maintainer Adjoint Inc (info@adjoint.io)
Revised Revision 1 made by sdiehl at Tue Aug 21 16:24:22 UTC 2018
Category Cryptography
Home page https://github.com/adjoint-io/bulletproofs#readme
Bug tracker https://github.com/adjoint-io/bulletproofs/issues
Source repo head: git clone https://github.com/adjoint-io/bulletproofs
Uploaded by sdiehl at Tue Aug 21 16:22:28 UTC 2018
Distributions LTSHaskell:0.4.0, NixOS:0.4.0, Stackage:0.4.0
Downloads 598 total (100 in the last 30 days)
Rating (no votes yet) [estimated by rule of succession]
Your Rating
  • λ
  • λ
  • λ
Status Hackage Matrix CI
Docs available [build log]
Last success reported on 2018-08-21 [all 1 reports]

Modules

[Index] [Quick Jump]

Downloads

Note: This package has metadata revisions in the cabal description newer than included in the tarball. To unpack the package including the revisions, use 'cabal get'.

Maintainer's Corner

For package maintainers and hackage trustees


Readme for bulletproofs-0.2.0

[back to package description]
<p align="center"> <a href="http://www.adjoint.io"><img src="https://www.adjoint.io/assets/img/adjoint-logo@2x.png" width="250"/></a> </p>

CircleCI Hackage

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 2log<sub>2</sub>(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<sub>L</sub> a vector of bit such that <a<sub>L</sub>, 2<sup>n</sup>> = v. The components of a<sub>L</sub> are the binary digits of v. We construct a complementary vector a<sub>R</sub> = a<sub>L</sub>1<sup>n</sup> and require that a<sub>L</sub>a<sub>R</sub> = 0 holds.

  • P -> V : A, S - where A and S are blinded Pedersen commitments to a<sub>L</sub> and a<sub>R</sub>.

       ![equation](https://latex.codecogs.com/gif.latex?\\&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;$)

       ![equation](https://latex.codecogs.com/gif.latex?\\&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 : T<sub>1</sub>, T<sub>2</sub> - where T<sub>1</sub> and T<sub>2</sub> are commitments to the coefficients t<sub>1</sub>, of a polynomial t constructed from the existing values in the protocol.

       ![equation](https://latex.codecogs.com/gif.latex?\\&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$)

       ![equation](https://latex.codecogs.com/gif.latex?\\&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;$)

       ![equation](https://latex.codecogs.com/gif.latex?\\&space;$&space;t&space;=&space;\langle&space;\textbf{l},&space;\textbf{r}&space;\rangle&space;\in&space;\mathbb{Z}_p$)

       ![equation](https://latex.codecogs.com/gif.latex?\\&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.

       ![equation](https://latex.codecogs.com/gif.latex?\\&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;$)

       ![equation](https://latex.codecogs.com/gif.latex?\\&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(log<sub>n</sub>) 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 [log<sub>2</sub>] + 2 elements. In total, the prover sends only 2 [log<sub>2</sub>(n)] + 4 group elements and 5 elements in Z<sub>p</sub>

Usage

import Bulletproofs.RangeProof

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

  -- Prover
  proofE <- generateProof upperBound v vBlinding
  -- Verifier
  case proofE of
    Left err -> panic $ show err
    Right (proof@RangeProof{..})
      -> pure $ verifyProof upperBound vCommit proof

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

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:

  • ◦ : 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/LICENSE-2.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.