Vector set commitments generalize Schnorr and utxo proof of ownership

Reading Adam Gibson’s “From Zero (Knowledge) to Bulletproofs” [1], I noticed how the zero knowledge argument of knowledge of a set of vectors generalizes both Schnorr signatures (as a proof of knowledge of discrete log), and MW utxo ownership proofs (as a proof of knowledge of both blinding factor and value in a Pedersen commitment).

Suppose a prover knows a set of m vectors x1xm each of length N, and forms vector commitments

  • C1 = r1 * G + x1 * H
  • C2 = r2 * G + x2 * H
  • Cm = rm * G + xm * H

where H denotes a vector of Nothing-Up-My-Sleeve points H1 … HN and x * H denotes the linear combination x1 * H1 + x2 * H2 + … + xN * HN.

To prove knowledge of the vectors to a verifier, the prover picks a random new vector commitment

  • C0 = r0 * G + x0 * H

and receives a challenge from the verifier in the form of a single scalar e.
They then show the scalar s = Σmi=0 ei * ri and the vector z = Σmi=0 ei * xi

and the verifier may check that

Σmi=0 ei * Ci = s * G + z * H

For a single vector (m=1) which is empty (N=0) this can be seen to reduce to a regular Schnorr signature on a public key C1 = r1 * G.

For a single vector (m=1) of length N=1 this reduces to a proof of ownership/knowledge of a Pedersen Commitment C1 = r1 * G + x1 * H.

[1] from0k2bp/from0k2bp.pdf at master · AdamISZ/from0k2bp · GitHub


That’s a very cool abstraction. Not sure how this would be abstracted further, but it makes me wonder what else can be done with this.