linear codes

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及其在现代密码学中的应用奠定了基础，展示了如何利用这些理论构建高效的证明系统。