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.
