图的3-着色可以表示为电路吗？

Question

我在看zk-SNARKs 这里中关于零知识证明的一个外行解释。

其思想是，如果一个人知道一个问题的解决方案(3) (找到一个满足x^3 + x + 5 = 0的x值)，那么我们可以用一个电路来证明这一点，以表示计算及其中间变量。关于如何进行零知识证明的更多细节对于这个问题并不重要。

这是零知识证明的一般想法吗？特别地，对于图着色问题，如何取有效着色并表示电路(想必，电路输出0表示有效着色，1输出无效着色)？

Answer 1

QAP的优点在于它是NP-完全的。因此，3-着色问题简化为QAP。事实上，NP中的任何问题都可以用QAP约束来表示。

更实际地说，所需要的只是一个图的算术编码和一个着色。然后，剩下的工作是设计算术约束，比如在编写过程中看到的约束，这些约束编码了3种着色要求。

例如，我可以将图表示为节点标签，表示为字段中的元素1, 2, 3, \dots，边缘集表示成对(1,4), (1,6), \dots。对于着色，您可以选择数字1,2,3。

然后，QAP输入-见证对就是那些放置在长向量中的元素(要编码一个元组，只需指定左输入和右输入是相邻的)。

在(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})中，1将是一个公共助手元素(当您需要常量时非常有用)，t's是表示图形的公共实例输入(其中I‘’th边(a，b)编码为t_{i, l}=a, t_{i,r}=b)，着色c's是私人见证输入。

还有一个额外的见证输入p^{-1}，我们稍后将使用它。在这里，我省略了所有中间变量，这些变量也必须包含在见证中，但是只要扩展见证来添加它们就足够了。我建议阅读下面的直觉，然后回到这个小问题上。现在，棘手的部分是如何对证人有效性检查和着色约束进行编码。

• 首先，您必须验证所有的c_i\in\{1,2,3\}。您可以通过对约束(c_i-1)(c_i-2)(c_i-3)=0进行编码来做到这一点。注意，此约束的程度为3。我将由您自己决定如何在多个QAP约束中对其进行编码；提示，需要一些中间变量/输入。
• 然后，需要对着色约束进行编码。这有点复杂。您需要对约束进行编码:对于每个元组(a,b)，c_a-c_b\neq 0.这需要查找约束才能将相应的颜色与元组中的索引相匹配。我建议您就如何编码查找约束(因为它更复杂)提出一个单独的问题，但在查找约束之后。您应该使用中间变量来编码以下向量：c_{t_{1,l}}, c_{t_{2,l}}, ..., c_{t_{m,l}}, c_{t_{m,l}}然后，您可以生成编码：c_{t_{1,l}}-c_{t_{2,l}}, ..., c_{t_{m,l}}-c_{t_{m,l}}的中间变量，然后，您可以使用一个线性的中间约束数来获得它们的乘积：p := \prod_{i\leq m}(c_{t_{i,l}}-c_{t_{i,l}})。现在你要检查的就是p\neq 0。为此，您可以添加见证输入p^{-1}并检查约束p\cdot p^{-1} = 1。这个约束的原因是0在字段中没有逆。