Schwartz-Zippel引理

文章详细介绍了二次算术程序（QAP）的概念及其在零知识证明中的应用，特别是如何通过拉格朗日插值将Rank 1约束系统（R1CS）转换为QAP，并通过Schwartz-Zippel引理在O(1)时间内验证QAP的等式。

本文介绍了多线性扩展（MLE）的概念及其在零知识证明中的应用。文章解释了如何将布尔超立方体视为编码信息的方式，并如何使用多线性扩展将定义在布尔超立方体上的多元函数转换为多元多项式，同时保持在超立方体上的一致性，并扩展到超立方体之外。此外，文章还讨论了多线性扩展的唯一性、计算方法以及Schwartz-Zippel引理，为后续将电路与求和检验结合奠定基础。

本文深入探讨了零知识证明（zk-SNARKs）中的Pinocchio协议，通过将程序转化为算术电路，利用多项式编码和Schwartz-Zippel引理，实现了简洁的电路执行证明。文章详细解释了如何构造多项式来表达正确的电路执行，以及如何使用隐藏技术和算法来保证证明的有效性和安全性，最终给出了Pinocchio协议的完整流程。

本文深入探讨了SUMCHECK协议，该协议是许多“可验证计算”原语的基础。文章详细介绍了协议的每一轮，包括证明者如何发送单变量多项式以及验证者如何进行检查和发送挑战。此外，文章还提供了SUMCHECK协议有效性的直观证明，并解释了Schwartz-Zippel引理在该协议中的应用。