...by Daniel Szego
quote
"On a long enough timeline we will all become Satoshi Nakamoto.."
Daniel Szego

Sunday, March 19, 2023

zkSNARK rank one constraint system


A rank one constraint system is a system of equations in which each equation can be written as a linear combination of two vectors. Specifically, if we have n variables x1, x2, ..., xn, then a rank one constraint system consists of m equations of the form:

a1x1 + b1x2 + c1x3 + ... + z1xn = d1

a2x1 + b2x2 + c2x3 + ... + z2xn = d2

...

amx1 + bmx2 + cmx3 + ... + zmxn = dm

where each of the coefficients a1, b1, c1, ..., z1, d1, a2, b2, c2, ..., z2, d2, ..., am, bm, cm, ..., zm, dm can be expressed as a linear combination of two vectors u and v, i.e., for all i, j in {1, 2, ..., n}, we have

ai = uix + vix

bi = uiy + viy

ci = uiz + viz

...

zi = uin + vin

di = u0 + v0

where u and v are fixed vectors and x, y, z, ..., n are variables.

The term "rank one" refers to the fact that each equation can be expressed as the outer product of two vectors, which has rank one. Rank one constraint systems have important applications in optimization, computer science, and engineering.

In zero-knowledge proofs, a rank one constraint can be used to prove that the prover has knowledge of a secret value without revealing the value itself. Specifically, the prover and verifier agree on a rank one constraint system, and the prover must prove that they know a witness that satisfies the system, without revealing the witness itself.

Here's a simplified example of how a rank one constraint can be used in a zero-knowledge proof:

Suppose the prover wants to prove that they know a secret value x that satisfies the equation:

ax + by = c

where a, b, and c are public values, and y is a public random value. To do this, the prover can construct a vector u such that:

u = (a, b*y)

and a scalar v such that:

v = x

Then, the prover can prove that they know a witness (i.e., a value of v) that satisfies the rank one constraint:

u * v = ax + byx = cy

which is equivalent to the original equation. The prover can do this by using a zero-knowledge proof system, such as zk-SNARKs, which allows them to prove knowledge of v without revealing its value. The verifier can then check the proof to ensure that the prover indeed knows a witness that satisfies the rank one constraint, without learning any additional information about the witness or the secret value x.

In summary, a rank one constraint can be used in zero-knowledge proofs to prove knowledge of a secret value without revealing the value itself.