Posts  / #POST-001294
REDDIT

Bulletproofs Question: How does it prove both a proof of knowledge of the vectors and also the innerproduct?

H
Feb 13, 2025 · 04:38

This is about the Bulletproofs zk Proof protocol - https://eprint.iacr.org/2017/1066.pdf

(I am going to use additive notation instead of the multiplicative notation used in the paper to describe my question)

Prover knows 2 vectors **a** & **b** such that their inner product is c.

She creates a binding (but not hiding) Pedersen commitment to the 2 vectors

P = **aG** + **bH**

(Here **G** & **H** are 2 vectors of generators - the relations between the different generators both inside each vector of generators & also between the 2 set of generators is not known).

assuming **a** = [a1, a2, a3] & **G** = [G1, G2, G3] etc, this commitment will look like

P = a1G1 + a2G2 + a3G3 + b1H1 + b2H2 + b3G3

which we write as

P = **aG** + **bH**

c = <**a**, **b**>

The Prover sends P & c to the verifier.
The verifier samples a random x and sends it to the prover

There is another generator V (the relations between V & **G** & **H** is not known)

Verifier constructs another a new point

P' = P + cxV

Let xV = U

The prover proves

P' = **aG** + **bH** + <a,b>U

using the Bulletproofs Protocol

- I understand the protocol.
- I also understand why the random x is required - i.e. how the prover can prove a wrong c' in place of c if the proof had just proved P' = **aG** + **bH** + <a,b>V instead of P' = **aG** + **bH** + <a,b>U

What I don't understand is how this one proof proves 2 things

- Proof of knowledge of 2 vectors
- Proof that c is the inner product of the 2 vectors

How does proving the longer statement prove the 2 things?

I mean proving A + B = C + D doesn't prove A = C & B = D, so how does it work here?

------------------------

I have my own explanation of why this works but I am not sure if it's correct

For e.g. in many zkProofs let's say we have to prove 3 polynomials to be zero polynomials using the Schwartz Zippel Lemma, we combine them using a linearly independent set.

i.e. if prover wants to prove 3 polynomials f1, f2 & f3 are zero, then instead of proving it using 3 separate Schwartz Zippel proofs, she can combine them into one polynomial.

The Verifier sends a random r. Prover creates a linearly independent set [r^0, r^1, r^2] & then creates a new polynomial

f = f1 + r.f2 + r^(2).f3

Now when f is evaluated at another random point send by the verif & the evaluation is zero, then that proves f1, f2 & f3 are all zero?

is something similar being done here - i.e. the 2 statements are being combined using [x^0 , x^(1)] & hence it proves both statements are true? I am not fully convinced because this isn't a polynomial & nor is Schwarz Zeppel being used here.