Buletproofs

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 <img src="/tex/c9180fbdcebcd1d43138236079832280.svg?invert_in_darkmode&sanitize=true" align=middle width=62.21854814999998pt height=24.65753399999998pt/> where <img src="/tex/55a049b8f161ae7cfeb0197d75aff967.svg?invert_in_darkmode&sanitize=true" align=middle width=9.86687624999999pt height=14.15524440000002pt/> 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 <img src="/tex/6c4adbc36120d62b98deef2a20d5d303.svg?invert_in_darkmode&sanitize=true" align=middle width=8.55786029999999pt height=14.15524440000002pt/> be a value in <img src="/tex/55f3e69887b882407ce69a32f942ec8b.svg?invert_in_darkmode&sanitize=true" align=middle width=36.35090909999999pt height=24.65753399999998pt/> and <img src="/tex/780fe58ca23d4620755100bcd6df5857.svg?invert_in_darkmode&sanitize=true" align=middle width=18.20773514999999pt height=14.611878600000017pt/> a vector of bit such that <img src="/tex/027c16cc98d01e325f81b02b717810ea.svg?invert_in_darkmode&sanitize=true" align=middle width=79.77706439999999pt height=22.968105600000015pt/>. The components of <img src="/tex/780fe58ca23d4620755100bcd6df5857.svg?invert_in_darkmode&sanitize=true" align=middle width=18.20773514999999pt height=14.611878600000017pt/> are the binary digits of <img src="/tex/6c4adbc36120d62b98deef2a20d5d303.svg?invert_in_darkmode&sanitize=true" align=middle width=8.55786029999999pt height=14.15524440000002pt/>. We construct a complementary vector <img src="/tex/a6a2d4d080eb7f2709d2667b008dd215.svg?invert_in_darkmode&sanitize=true" align=middle width=78.49842824999999pt height=22.968105600000015pt/> and require that <img src="/tex/9ca3a8cc8ef0c73eb5f30bc2a79c10bf.svg?invert_in_darkmode&sanitize=true" align=middle width=85.89737144999998pt height=21.18721440000001pt/> holds.

• <img src="/tex/b4208d8b4738940db657353162d75988.svg?invert_in_darkmode&sanitize=true" align=middle width=96.00990794999998pt height=22.465723500000017pt/> - where <img src="/tex/53d147e7f3fe6e47ee05b88b166bd3f6.svg?invert_in_darkmode&sanitize=true" align=middle width=12.32879834999999pt height=22.465723500000017pt/> and <img src="/tex/e257acd1ccbe7fcb654708f1a866bfe9.svg?invert_in_darkmode&sanitize=true" align=middle width=11.027402099999989pt height=22.465723500000017pt/> are blinded Pedersen commitments to <img src="/tex/780fe58ca23d4620755100bcd6df5857.svg?invert_in_darkmode&sanitize=true" align=middle width=18.20773514999999pt height=14.611878600000017pt/> and <img src="/tex/43c0eea9d6fd13b6dcc00c115f09f827.svg?invert_in_darkmode&sanitize=true" align=middle width=19.15122824999999pt height=14.611878600000017pt/>.

     <img src="/tex/682f94ba2740d7ac0151285bb5c0e2d5.svg?invert_in_darkmode&sanitize=true" align=middle width=221.92594214999994pt height=22.831056599999986pt/>

     <img src="/tex/1cc942c32fa7a265ec264b6b89cb7a5e.svg?invert_in_darkmode&sanitize=true" align=middle width=215.08120259999995pt height=22.831056599999986pt/>

• <img src="/tex/60a45cf4b3b952bb99961cea76f438ec.svg?invert_in_darkmode&sanitize=true" align=middle width=89.67053534999998pt height=22.465723500000017pt/> - Verifier sends challenges <img src="/tex/deceeaf6940a8c7a5a02373728002b0f.svg?invert_in_darkmode&sanitize=true" align=middle width=8.649225749999989pt height=14.15524440000002pt/> and <img src="/tex/f93ce33e511096ed626b4719d50f17d2.svg?invert_in_darkmode&sanitize=true" align=middle width=8.367621899999993pt height=14.15524440000002pt/> to fix <img src="/tex/53d147e7f3fe6e47ee05b88b166bd3f6.svg?invert_in_darkmode&sanitize=true" align=middle width=12.32879834999999pt height=22.465723500000017pt/> and <img src="/tex/e257acd1ccbe7fcb654708f1a866bfe9.svg?invert_in_darkmode&sanitize=true" align=middle width=11.027402099999989pt height=22.465723500000017pt/>.

• <img src="/tex/0a5841e3d06796e4fe2365142851641a.svg?invert_in_darkmode&sanitize=true" align=middle width=105.79308629999998pt height=22.465723500000017pt/> - where <img src="/tex/b1aadae6dafc7da339f61626db58e355.svg?invert_in_darkmode&sanitize=true" align=middle width=16.15873379999999pt height=22.465723500000017pt/> and <img src="/tex/b48cd4fc1cc1b8c602c81734763b31f0.svg?invert_in_darkmode&sanitize=true" align=middle width=16.15873379999999pt height=22.465723500000017pt/> are commitments to the coefficients <img src="/tex/4ad941990ade99427ec9730e46ddcdd4.svg?invert_in_darkmode&sanitize=true" align=middle width=12.48864374999999pt height=20.221802699999984pt/>, of a polynomial <img src="/tex/4f4f4e395762a3af4575de74c019ebb5.svg?invert_in_darkmode&sanitize=true" align=middle width=5.936097749999991pt height=20.221802699999984pt/> constructed from the existing values in the protocol.

     <img src="/tex/3b476246fe46073d297bf73ac65431d4.svg?invert_in_darkmode&sanitize=true" align=middle width=228.34261889999993pt height=24.65753399999998pt/>

     <img src="/tex/3f647f042871be1fa7d4c2dd3a39c860.svg?invert_in_darkmode&sanitize=true" align=middle width=343.26980655pt height=26.76175259999998pt/>

     <img src="/tex/8776955e6030428869cce9bc42d05f80.svg?invert_in_darkmode&sanitize=true" align=middle width=90.58874879999999pt height=22.831056599999986pt/>

     <img src="/tex/a279966ad1c6df42c3dfa8291334fbe7.svg?invert_in_darkmode&sanitize=true" align=middle width=131.93364524999998pt height=22.831056599999986pt/>,      <img src="/tex/131fbdb12ac9849e6ca36f10a618834b.svg?invert_in_darkmode&sanitize=true" align=middle width=65.9370855pt height=24.65753399999998pt/>

• <img src="/tex/4ec1a874225b934747bb34ef5828b457.svg?invert_in_darkmode&sanitize=true" align=middle width=74.74281209999998pt height=22.465723500000017pt/> - Verifier challenges Prover with value <img src="/tex/332cc365a4987aacce0ead01b8bdcc0b.svg?invert_in_darkmode&sanitize=true" align=middle width=9.39498779999999pt height=14.15524440000002pt/>.

• <img src="/tex/f62b5cfd714aaeeb533f9ef8c3aa945f.svg?invert_in_darkmode&sanitize=true" align=middle width=131.58244935pt height=22.831056599999986pt/> - Prover sends several commitments that the verifier will then check.

     <img src="/tex/d3e7839976018ff10b0004522caa8c03.svg?invert_in_darkmode&sanitize=true" align=middle width=195.8404503pt height=26.76175259999998pt/>

     <img src="/tex/21c10ff9f2eb2b517eb136bd2fb72927.svg?invert_in_darkmode&sanitize=true" align=middle width=118.2106728pt height=22.648391699999998pt/>

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 <img src="/tex/a0dbe24a0fee4cdae71ca7c7cd9920f2.svg?invert_in_darkmode&sanitize=true" align=middle width=55.96170689999999pt height=24.65753399999998pt/> inner product proof.

The inner-product argument in the protocol allows to prove knowledge of vectors <img src="/tex/d6e48bf9a93b968d85cb6d6d6e33a0b8.svg?invert_in_darkmode&sanitize=true" align=middle width=5.251113449999989pt height=22.831056599999986pt/> and <img src="/tex/9f9c14b9a3c7d1e583ad84cde97887bc.svg?invert_in_darkmode&sanitize=true" align=middle width=7.785368249999991pt height=14.611878600000017pt/>, whose inner product is <img src="/tex/4f4f4e395762a3af4575de74c019ebb5.svg?invert_in_darkmode&sanitize=true" align=middle width=5.936097749999991pt height=20.221802699999984pt/> and the commitment <img src="/tex/a609ac3c8189720abb255d49a1c40183.svg?invert_in_darkmode&sanitize=true" align=middle width=45.71334404999999pt height=22.648391699999998pt/> is a commitment of these two vectors. We can therefore replace sending (<img src="/tex/3e7a0b9dae6212d3be6814d4732827c6.svg?invert_in_darkmode&sanitize=true" align=middle width=66.23462504999999pt height=22.831056599999986pt/>) with a transfer of (<img src="/tex/9261976c22c8fab73fb9c45ca5e5e760.svg?invert_in_darkmode&sanitize=true" align=middle width=38.58637694999999pt height=20.221802699999984pt/>) and an execution of an inner product argument.

Then, instead of sharing <img src="/tex/d6e48bf9a93b968d85cb6d6d6e33a0b8.svg?invert_in_darkmode&sanitize=true" align=middle width=5.251113449999989pt height=22.831056599999986pt/> and <img src="/tex/9f9c14b9a3c7d1e583ad84cde97887bc.svg?invert_in_darkmode&sanitize=true" align=middle width=7.785368249999991pt height=14.611878600000017pt/>, which has a communication cost of <img src="/tex/47c124971e1327d1d3882a141f95face.s