Fiat-Shamir变换

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中的应用，同时强调了在设计安全协议时需要考虑的潜在风险和必要的安全分析。