2
$\begingroup$

I was looking at a layman explanation for zero-knowledge proofs in zk-SNARKs here.

The idea there is that if one knows a solution (3) to a question (find a value of x satisfying x^3 + x + 5 = 0), then one can prove this using a circuit to represent the computation and its intermediate variables. Further details on how to do the zero knowledge proof are not important for this question.

Is this a general idea for any zero knowledge proof? In particular, for a graph coloring problem, how does one take a valid coloring and represent a circuit (presumably, the circuit outputs 0 for valid colorings and 1 for invalid colorings)?

$\endgroup$

1 Answer 1

2
$\begingroup$

The beauty of QAP is that it is NP-Complete. Thus, the 3-coloring problem reduces to QAP. In fact, any problem in NP can be represented using QAP constraints.

More practically, all that is required is an arithmetic encoding of a graph and a coloring. Then, the rest of the work is to design arithmetic constraints such as the ones you saw in the write-up that encode the 3-coloring requirements.

For example, I can represent graphs as node labels as elements $1, 2, 3, \dots$ in the field and the edge set as pairs $(1,4), (1,6), \dots$. For the coloring, you can choose the numbers $1,2,3$.

Then, the QAP input-witness pair are simply those elements laid out in a long vector (to encode a tuple, you can just designate the left and right inputs are adjacent).

$$(1,t_{1,l}, t_{1,r}, t_{2,l}, t_{2,r}\dots, t_{m, l}, t_{m, r};c_{1}, c_{2},\dots, c_{n}, p^{-1})$$ where $1$ will be a public helper element (useful when you need constants), $t$'s are public instance inputs representing the graph (where the i'th edge (a,b) is encoded as $t_{i, l}=a, t_{i,r}=b$) and the coloring $c$'s are the private witness inputs.

There's an additional witness input $p^{-1}$, which we will use later. Here, I’m omitting all of the intermediate variables which also must be included in the witness, but it suffices just to extend the witness to add them. I suggest reading the intuition below and then coming back to this minor issue. Now the tricky part is how to encode the witness validity checks and coloring constraints.

  • First, you have to verify that all the $c_i\in\{1,2,3\}$. You can do this by encoding the constraint $(c_i-1)(c_i-2)(c_i-3)=0$. Notice the degree of this constraint is three. I'll leave it up to you to figure out how you can encode that in multiple QAP constraints; hint, requires some intermediate variables / inputs.
  • Then, you need to encode the coloring constraint. This is a little more complicated. You need to encode the constraint: For every tuple $(a,b)$, $c_a-c_b\neq 0$... This requires lookup constraints to match corresponding colors to indices in the tuple... I suggest you ask a separate question on how to encode lookup constraints (as it's more complicated), but after the lookup constraints. You should end up with intermediate variables which encode the following vector: $$c_{t_{1,l}}, c_{t_{2,l}}, ..., c_{t_{m,l}}, c_{t_{m,l}}$$ Then, you can produce intermediate variables that encode: $$c_{t_{1,l}}-c_{t_{2,l}}, ..., c_{t_{m,l}}-c_{t_{m,l}}$$ Then, you can obtain their product: $$p := \prod_{i\leq m}(c_{t_{i,l}}-c_{t_{i,l}})$$ by using a linear number of intermediate constraints. Now all you have to check is that $p\neq 0$. To do so, you can add a witness input $p^{-1}$ and check the constraint $p\cdot p^{-1} = 1$. The reason for this constraint is that 0 does not have an inverse in the field.
$\endgroup$
1
  • $\begingroup$ Thank you for the very nice answer. I think I get the intuition for it (which was the main goal) and I will ask a separate question on how to encode the lookup constraints. $\endgroup$ May 21, 2023 at 20:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.