FRI

ZK白板系列S2 - M8：FRI和邻近证明（第二部分）

在本次讲座的第二部分中，讲者深入探讨了FRI（快速重构插值）及其在接近性证明中的应用。FRI是一种基于Reed-Solomon编码的接近性证明系统，旨在通过验证者与证明者之间的交互，确保给定的函数是否接近于Reed-Solomon编码的代码字。 ### 核心内容概述： 1. **FRI的目标**：FRI的主要目标是通过一个证明系统，确保如果函数u0是Reed-Solomon代码的代码字，验证者将以概率1接受；如果u0与代码字的距离超过某个阈值（delta），验证者将以高概率拒绝。 2. **FRI的工作机制**：FRI协议分为两个阶段：承诺阶段和查询阶段。在承诺阶段，证明者通过折叠函数并发送给验证者；在查询阶段，验证者通过随机点检查折叠的正确性。 ### 关键论据和信息： - **折叠操作**：折叠操作不会降低与代码的距离，这一特性使得即使在多轮折叠后，验证者仍能有效判断函数的接近性。 - **查询阶段的有效性**：验证者通过随机抽样点来检查每一轮的折叠是否正确，确保了协议的完整性和安全性。 - **安全性分析**：通过对每一轮的独立性分析，证明了如果u0距离代码字较远，验证者拒绝的概率将显著增加。 - **变体的探讨**：讲者还介绍了FRI的几种变体，包括高阶折叠、批处理FRI、磨削技术（grinding）和STIR等，这些变体旨在提高效率和安全性。 ### 未来展望： 讲者强调了在SNARKs（简洁非交互式知识论证）领域中，继续探索更高效的编码方案的重要性，尤其是超越Reed-Solomon编码的可能性。通过引入新的编码方法和技术，未来的研究可以进一步优化SNARKs的性能和安全性。 总的来说，本次讲座不仅详细阐述了FRI的基本原理和应用，还探讨了其变体及未来的发展方向，为参与者提供了丰富的理论基础和实践启示。

ZK白板系列S2 - M7：FRI和邻近证明（第一部分）

在本次讲座中，我们讨论了FRI（快速Reed-Solomon接近交互式证明）及其在构建SNARKs（简洁非交互式知识论证）中的应用。讲座的核心内容包括FRI的定义、其工作原理以及如何利用FRI构建基于代码的SNARKs。 ### 核心内容概述： 1. **FRI的定义**：FRI是一种高效的交互式证明系统，允许证明者证明某个函数与Reed-Solomon码字的接近程度。 2. **FRI的工作原理**：通过将函数的评估与Reed-Solomon码进行比较，FRI能够有效地验证函数的正确性。 3. **SNARKs的构建**：FRI作为一种交互式证明，可以通过BCS编译器转化为SNARKs，提供高效的证明系统。 ### 关键论据和信息： 1. **线性码的基础知识**：讲座中介绍了线性码的基本概念，包括汉明权重、相对汉明距离等，这些概念为理解FRI提供了必要的背景。 2. **Reed-Solomon码**：作为经典的最大距离可分离（MDS）码，Reed-Solomon码在FRI中起到了核心作用，讲座详细解释了其构造和性质。 3. **交互式证明系统**：介绍了交互式oracle证明（IOP）和交互式oracle接近证明（IOPP）的概念，强调了它们在SNARKs构建中的重要性。 4. **距离保持变换**：讲座中讨论了折叠（folding）和批处理（batching）等技术，这些技术能够提高FRI的效率，减少计算复杂度。 5. **Johnson界限**：强调了在Johnson界限以下，接近码字的代码字数量是有限的，这一性质对于FRI的有效性至关重要。 通过这些内容，讲座为理解FRI及其在现代密码学中的应用奠定了基础，展示了如何利用这些理论构建高效的证明系统。