Bulletproofs+ is a recently proposed range proof which is similar in spirit to Bulletproofs. Both of these range proof protocols enable proof sizes logarithmic in the number of bits of the range using a recursive inner product protocol. Bulletproofs relies on the improved inner product protocol while Bulletproofs+ uses a weighted inner product protocol .
Improved Inner Product Argument
The recursive inner product argument introduced in  gives an argument of knowledge for the language given by
where is the common reference string (crs).
Note that is a Pedersen vector commitment to .
We can write the witness as and .
Similarly, the base vectors can be written as and . Now, we compute Pedersen vector commitments to the vector tuples and as
Given a challenge scalar , we can blind the original witness to get
The 4-tuple becomes a valid proof of knowledge of the witness.
This can be verified by checking the following
Instead of publishing vectors , we can further repeat the same process of dividing in halves and compute and so on until we are left with scalars .
This is the main idea of the log-sized inner product protocol and the proof is of the form
Note that the above argument is perfectly complete and sound, but not zero-knowledge.
This is because we cannot construct a PPT simulator who could generate a valid transcript given statement and the crs.
Weighted Inner Product Argument
The weighted inner product argument uses a weighted inner product operation defined as
where and . The weighted inner product is essentially a way to combine multiple equations into a single equation. For instance,
represent distinct equations.
The weighted inner product combines these equations to give a single equation of the form
The weighted inner product protocol is also bilinear and satisfies the following property
We now wish to design a proof system based on the weighted inner product.
The language of the weighted inner product protocol becomes
Similar to the inner product protocol, suppose the prover commits to vectors and and the scalars ,
the prover must convince the verifier of the relation .
For this, we blind the original witness vectors using a challenge scalar .
Now, similar to the inner product argument, the 4-tuple becomes a valid proof of knowledge of the witness. We can shrink this argument too to logarithmic in the size of witness vectors.
The WIP based argument presented in Bulletproofs+ paper is zero-knowledge as against the inner product argument.
This is achieved by including randomly chosen blinding factors in computing the Pedersen vector commitments as
where . Further, in the last round of the protocol, instead of sending , we use a sigma-like protocol yeilding constant communication and computation.
This is the main difference in the inner product and the weighted inner product arguments.
We will see in the next blog how this helps building Bulletproofs+ - a range proof protocol with proof size shorter than that of Bulletproofs.
References and Notes