The Unreasonable Power of the Sum-Check Protocol
The Unreasonable Power of the Sum-Check Protocol
复制标题
和检查协议的不合理权力
DOI：
--
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
L. Andriès
中科院分区：
文献类型：
--
作者：
van der Ark;L. Andriès
在设计高效的交互式证明系统时，您的工具箱中只需要一把锤子：Lund、Fortnow、Karloff 和 Nisan 的求和协议。这篇博文的目的是描述这把锤子并说明它为何如此有用。整篇文章将在交互式证明的背景下进行构建。这意味着验证者 V 的目标是将昂贵的计算卸载给不受信任的证明者 P ，同时实现验证者的工作节省。我们希望验证器在输入大小上按时间线性运行，同时保持证明简短（对数大小）和证明器高效。由于这篇文章出现在 ZKProof 博客上，您可能想知道为什么没有提到零知识。答案是，人们可以将这篇文章中描述的想法与密码学承诺结合起来，以获得最先进的 zk-SNARK。但这将是未来帖子的主题。这篇文章的路线图。在描述了和校验协议之后，我将通过几个应用程序展示其非凡的功能。首先，我将给出矩阵乘法和图中三角形计数的简单交互式证明（IP）。这些 IP 的一个很酷的事情是证明者非常高效：P 运行最著名的算法来解决问题，然后做少量的额外工作来证明答案是正确的。我不知道有任何其他技术可以通过对数证明长度实现这种超级效率。其次，我将重新证明 Goldwasser、Kalai 和 Rothblum（GKR）的以下重要结果：所有在对数空间中可解决的问题都有一个带有线性时间验证器、多项式时间证明器和多对数证明长度的 IP。正如我将解释的，这个结果是矩阵乘法 IP 的直接结果，这比 GKR 的原始处理更简单，GKR 通过用于算术电路评估的复杂 IP 得出结果。
When designing an efficient interactive proof system, there is only one hammer you need to have in your toolbox: the sum-check protocol of Lund, Fortnow, Karloff, and Nisan. The goal of this blog post is to describe this hammer and give a sense of why it is so useful. This entire post will be framed in the context of interactive proofs. This means that the goal is for a verifier V to offload an expensive computation to an untrusted prover P , while achieving work-saving for the verifier. We want the verifier to run in time linear in the input size, while keeping the proof short (logarithmic size) and the prover efficient. Since this post is appearing on the ZKProof blog, you may wonder why there is nothing said about zero-knowledge. The answer is that one can combine the ideas described in this post with cryptographic commitments to get state of the art zk-SNARKs. But that will be the subject of a future post. Roadmap for this post. After describing the sum-check protocol, I will demonstrate its remarkable power through several applications. First, I will give simple interactive proofs (IPs) for matrix multiplication and counting triangles in graphs. A cool thing about these IPs is that the prover is super-efficient: P runs the best-known algorithm to solve the problem, and then does a low-order amount of extra work to prove the answer is correct. I don’t know of any other techniques that achieve this super-efficiency with logarithmic proof length. Second, I will re-prove the following important result of Goldwasser, Kalai, and Rothblum (GKR): all problems solvable in logarithmic space have an IP with a linear-time verifier, polynomial time prover, and polylogarithmic proof length. As I’ll explain, this result is a direct consequence of the matrix-multiplication IP—this is simpler than the original treatment by GKR, who derived the result via a sophisticated IP for arithmetic circuit evaluation.