基于QAP的zkSnark的验证成本

Question

在CGPR (链接到纸上)第3.5节中，考虑到电路尺寸为|C|，验证器的成本为O(|C| \log(|C|))。

在我看来，得到的QAP中的多项式度应该是O(|C|)。证明费用不是O(|C|)吗？我是不是错过了几步？

Answer 1

关键是他们使用的是通用电路：

当我们构造电路O(|C| \log |C|)时，我们使用QSP作为通用电路，其中|C|是可满足性问题中电路的最大尺寸。

通用电路是一种可以计算任何其他电路的电路。这种概括性就是额外的对数因子出现的地方。在第3节开始时对此作了解释：

与Groth直接比较，我们可以将u作为一个自适应选择的电路，通过一个通用电路构造R (关系)。在这种情况下，电路计算R的大小可以通过对数因子大于|u|，从而相应地增加\tilde{O}(|u|)的CRS大小和验证器计算。如果u ..。可以非自适应地选择，使我们的方案更有效。

\tilde{O}表示法隐藏对数因子。最后，他们提到，了解具体的电路u将是更有效的-这是你的想法。适应性健全的原因是，这更正确地模拟了在实际情况下如何使用该协议--通常您会期望验证者在开始验证之前看到CRS，这样他们就可以选择他们正在(可能是错误的)根据CRS (自适应)进行证明的陈述。

本论文解释了一种有效的通用电路结构，并解释了这些电路在初级阶段是如何工作的(例如，请参阅第4-7页)。直观地说，引入对数因子是因为这些电路往往是递归构建的，每个子问题大约只有二叉树的一半大小，所以我们在处理二叉树时有通常的对数因子。为了得到更好的解释，我认为报纸本身是最好的读物。