多项式承诺

ZKP MOOC 第6课：基于配对和离散对数的多项式承诺

在本次讲座中，Yupeng Zhang 讨论了基于双线性配对和离散对数的多项式承诺方案，重点介绍了 KZG 多项式承诺方案及其变体，以及无可信设置的多项式承诺方案。 ### 核心内容 1. **多项式承诺的定义与结构**：多项式承诺是一种协议，允许证明者在不直接发送多项式的情况下，承诺一个多项式，并在后续的查询中提供该多项式在特定点的评估值及证明。KZG 多项式承诺方案通过生成全局参数、承诺多项式、评估和验证四个算法实现。 2. **KZG 多项式承诺方案**：该方案依赖于双线性配对，具有高效的性能，承诺和证明的大小均为常数（一个群元素），验证时间为单个配对操作。然而，该方案需要可信的设置，即生成一个秘密参数 tau，并在生成后将其删除，以确保安全性。 3. **无可信设置的多项式承诺方案**：为了解决 KZG 方案的可信设置问题，提出了基于离散对数的无可信设置方案，如 Bulletproofs。Bulletproofs 通过递归减少多项式的度数，最终在最后一轮直接发送常数大小的多项式进行验证。尽管其证明大小为对数级别，但验证时间仍为线性。 4. **后续改进**：后续的研究如 Hyrax、Dory 和 Dark 方案进一步优化了验证时间，Hyrax 将验证时间降低到平方根级别，而 Dory 和 Dark 方案则实现了对数级别的验证时间和证明大小。 ### 关键论据与信息 - **多项式承诺的四个算法**：包括密钥生成、承诺、评估和验证。 - **KZG 方案的安全性**：基于知识声称的假设，确保证明者无法伪造评估值。 - **Bulletproofs 的递归结构**：通过将多项式分为左右两部分，利用随机线性组合来减少多项式的度数。 - **后续方案的优势**：Hyrax、Dory 和 Dark 方案在不牺牲安全性的前提下，显著提高了效率，尤其是在验证时间方面。 总之，本次讲座深入探讨了多项式承诺的理论基础及其在零知识证明中的应用，展示了如何通过不同的技术手段来优化性能和安全性。

ZKP MOOC 第8课：基于FRI的多项式承诺和Fiat-Shamir

本次讲座的核心内容是关于基于FRI的多项式承诺和Fiat-Shamir变换。讲师Justin Thaler介绍了如何将多项式交互式Oracle证明（IOP）与多项式承诺方案结合，形成简洁的交互式论证，并通过Fiat-Shamir变换将其转化为非交互式的SNARK（简洁非交互式知识论证）。 ### 主要观点： 1. **多项式承诺与交互式证明的结合**：大多数SNARK是通过结合多项式承诺方案和多项式IOP构建的。每种方案都有其独特的性能特征和优缺点。 2. **FRI的工作原理**：FRI（快速重构插值）通过对多项式的评估进行Merkle承诺，并在验证过程中使用折叠和查询阶段来确保多项式的低度性。FRI的折叠过程通过将多项式的评估在特定的根单位上进行随机线性组合，从而降低多项式的度数。 3. **Fiat-Shamir变换的应用**：Fiat-Shamir变换将交互式协议转化为非交互式协议，但在多轮协议中可能导致安全性显著下降。特别是，设计者需要确保协议满足逐轮安全性，以避免潜在的安全漏洞。 ### 关键论据： - **多项式IOP和承诺方案的组合**：不同的多项式IOP和承诺方案可以组合使用，形成不同的SNARK，每种组合都有其性能权衡。 - **FRI的安全性分析**：FRI的安全性依赖于相对汉明距离的概念，证明了在一定条件下，欺诈性证明者通过FRI的验证查询成功的概率是有限的。 - **Fiat-Shamir的安全性问题**：在多轮协议中，应用Fiat-Shamir变换可能导致攻击者通过“磨损攻击”成功的概率显著增加，因此需要更高的安全级别。 本讲座深入探讨了FRI的机制及其在SNARK中的应用，同时强调了在设计安全协议时需要考虑的潜在风险和必要的安全分析。

ZKP MOOC 第 7 课：基于纠错码的多项式承诺

在本次讲座中，Yupeng Zhang 讨论了基于纠错码的多项式承诺方案，重点介绍了其在零知识证明中的应用。以下是视频的核心内容和关键论据总结： 1. **核心内容概括**： - 本讲座介绍了基于纠错码的多项式承诺方案，强调了其在构建高效的SNARK（简洁非交互式知识论证）中的重要性。通过结合多项式承诺方案和适当的多项式交互证明，可以实现对一般电路的高效证明。 2. **关键论据和信息**： - **纠错码的背景**：纠错码用于在网络传输中纠正错误，具有最小距离的概念，最小距离决定了码字之间的差异程度。 - **多项式承诺方案的优缺点**： - 优点包括：对量子计算机的抗性、快速的证明者时间（不需要群体指数运算）、小的全局参数大小（只需采样哈希函数）。 - 缺点包括：证明大小通常较大（可达数十兆字节），缺乏同态性质，难以聚合。 - **多项式承诺的构建**：通过使用线性纠错码和Merkle树，构建了一个具有平方根大小证明和平方根验证时间的多项式承诺方案。 - **接近性测试和一致性测试**：通过这两个步骤，验证者可以确保承诺的矩阵确实符合编码要求，并且能够正确计算多项式的值。 - **线性时间编码的实现**：使用扩展图构建线性时间可编码的代码，确保在多项式承诺中实现线性时间的证明者。 总的来说，本讲座深入探讨了基于纠错码的多项式承诺方案的理论基础、实现方法及其在零知识证明中的应用，展示了其在现代密码学中的重要性和潜力。

ZKP MOOC 第 5 课：Plonk SNARK

在本次讲座中，Dan Boneh详细介绍了一个广泛使用的SNARK（简洁非交互式知识论证）构造，名为Plonk。讲座的核心内容是逐步构建Plonk的各个组成部分，并解释其工作原理。 ### 核心内容概述 Plonk是一个多项式交互式oracle证明（IOP），用于验证任意电路的计算。它通过将电路的计算过程编码为多项式，并利用多项式承诺方案来实现高效的证明和验证。Plonk的设计允许在不需要信任设置的情况下进行有效的证明。 ### 关键论据和信息 1. **多项式承诺方案**：Plonk的构建依赖于多项式承诺方案，特别是KZG承诺方案。该方案允许承诺者在不泄露多项式的情况下，向验证者承诺一个多项式，并在后续阶段提供对该多项式的评估证明。 2. **多项式的构造**：通过将电路的输入和输出映射到多项式的特定点，构造一个多项式T，该多项式编码了电路的计算过程。每个电路门的输入和输出都通过特定的点值表示。 3. **验证步骤**： - **输入验证**：验证者检查多项式T是否正确编码了电路的公共输入。 - **门的正确性**：通过构造选择多项式S，验证每个门的计算是否正确（加法或乘法）。 - **连线验证**：通过定义一个旋转多项式W，检查电路中各个门的输入输出是否正确连接。 4. **零知识证明**：Plonk可以通过通用的转换方法扩展为零知识SNARK，确保证明过程中的隐私性。 5. **性能**：Plonk的证明大小是常数级别，验证者的运行时间是对电路大小的对数级别，证明者的运行时间接近线性。 6. **扩展性**：Plonk支持自定义门和Plookup功能，使得电路的表示更加灵活，并能够进一步优化证明者的运行时间。 通过这些步骤和构造，Plonk实现了高效的电路验证，成为现代密码学和区块链技术中重要的工具之一。