polynomial extension

ZKP MOOC 第 4 课：交互式证明

在本次讲座中，Justin Thaler 介绍了基于交互式证明的 SNARK（简洁非交互式知识论证）的设计，重点讨论了如何利用交互式证明构建 SNARK，特别是在电路可满足性问题上的应用。 ### 核心内容概括 1. **SNARK 定义**：SNARK 是“简洁非交互式知识论证”的缩写，指的是一种简短且易于验证的证明，能够证明某个声明的真实性。SNARK 的特点是证明短小且验证快速。 2. **交互式证明与 SNARK 的关系**：交互式证明是 SNARK 的基础，交互式证明允许证明者和验证者通过多轮交互来确认某个声明的真实性，而 SNARK 则是将这一过程转化为非交互式的形式，适合在区块链等场景中使用。 ### 关键论据与信息 1. **交互式证明的特点**： - 交互式证明需要多轮交互，验证者通过发送挑战来确认证明者的声明。 - 交互式证明的安全性依赖于统计性质，而 SNARK 的安全性则依赖于计算复杂性。 2. **多项式扩展**：在构建 SNARK 时，使用多项式扩展来处理电路的证明。通过将电路的每个门的值视为一个函数，并利用多项式扩展来确保该函数在所有输入下的行为一致。 3. **求和检查协议**：Thaler 介绍了求和检查协议（sum-check protocol），该协议允许验证者通过少量查询来确认多变量多项式在布尔超立方体上的值是否为零。这一协议的设计使得验证者能够高效地确认电路的正确性。 4. **电路可满足性问题**：通过将电路的每个门的值视为一个函数，并利用多项式扩展，验证者可以在不完全了解电路的情况下，确认证明者所声称的电路输出是否正确。 5. **SNARK 的构建过程**： - 证明者首先发送一个多项式，该多项式扩展了正确的转录。 - 验证者通过求和检查协议确认该多项式在布尔超立方体上的值是否为零。 - 最终，利用 Fiat-Shamir 转换将交互式协议转化为非交互式协议，使得 SNARK 可以在区块链等场景中使用。 ### 总结 本次讲座深入探讨了 SNARK 的构建过程，强调了交互式证明在其中的重要性。通过求和检查协议和多项式扩展，证明者能够有效地证明电路的可满足性，而验证者则可以通过少量的查询来确认这一证明的有效性。这一过程不仅提高了证明的效率，也确保了安全性，适用于现代区块链技术的需求。