SNARK

ZK白板系列S2 - M5：小域，二进制域

在本模块中，Jim Posen与Nico讨论了小域和二进制域在SNARK（可证明非交互式知识）中的应用，特别是小域技术的性能效率及其重要性。 **核心内容概括：** 视频主要探讨了使用小域（如64位Goldilocks域）构建SNARK的优势，尤其是在计算效率和内存使用方面。Jim强调，传统上使用256位的有限域虽然安全性高，但在计算性能上存在显著劣势。通过使用小域，可以显著提高域乘法的速度，从而提升整体性能。 **关键论据和信息：** 1. **性能效率**：使用256位域的乘法速度远低于64位域，后者在单核计算机上每秒可进行1200万次乘法，而256位域仅为60万次。 2. **小域的定义**：小域指的是能够适应计算机寄存器（如32位或64位）的域，使用小域可以减少内存浪费和提高缓存利用率。 3. **安全性问题**：小域的安全性较低，错误接受概率与域大小成反比。为了解决这一问题，Jim介绍了使用扩展域（如Goldilocks的平方扩展）来提高安全性。 4. **二进制塔**：通过构建二进制塔，可以在保持小域的同时，利用更大的域进行计算，从而实现更高的安全性。 5. **打包技术**：打包技术允许将多个小域元素组合成一个大域元素，从而在不增加计算复杂度的情况下，解决了小域在FFT和多项式编码中的限制。 总的来说，视频强调了小域在SNARK构建中的潜力，提出了通过扩展域和打包技术来克服安全性和性能问题的解决方案。

ZK白板系列 - 模块14：Nova 速成课程

在本期ZK Hack白板系列视频中，Brendan与以太坊研究员Justin Drake讨论了Nova的概念及其在区块链中的应用。Nova是一种新近提出的技术，旨在作为SNARK（简洁非交互式论证）系统的预处理步骤，能够显著提高证明和验证的效率。 ### 核心内容概括 Nova的主要功能是通过“折叠”多个相似的计算实例，减少需要验证的工作量，从而加快验证速度。它可以被视为对BLS签名的推广，允许将多个签名合并为一个，从而只需验证合并后的结果。Nova特别适用于具有重复结构的计算，如以太坊虚拟机（EVM）中的交易处理。 ### 关键论据与信息 1. **折叠机制**：Nova通过将多个计算实例折叠成一个，减少了验证的复杂性。每个实例的验证只需检查最后一个折叠的结果，从而提高了效率。 2. **VDF（可验证延迟函数）**：Nova被用于VDF项目中，利用其折叠特性来处理需要时间的计算，确保验证者能够快速确认计算结果的正确性。 3. **R1CS与放松R1CS**：Nova使用了一种称为放松R1CS的结构，允许在证明过程中引入额外的向量和系数，以便更灵活地处理计算。 4. **无信任设置**：Nova是一个透明的证明系统，不需要信任的设置，且具有后量子安全的潜力，可以使用不同的承诺方案。 5. **性能优势**：Nova在处理速度上比传统的SNARK系统快得多，且在递归验证时的开销非常低，适合大规模并行计算。 6. **未来应用**：Nova有潜力在以太坊生态系统中发挥重要作用，尤其是在ZK-EVM和其他零知识证明相关的项目中。 总之，Nova通过其创新的折叠机制和高效的验证过程，为区块链技术的可扩展性和效率提供了新的解决方案，值得关注和进一步研究。

ZK白板系列 - 模块六：用于性能优化的 lookup Tables

在本期ZK Whiteboard系列视频中，Brendan与Ethereum Foundation的SNARK研究负责人Mary Maller讨论了“查找论证”（lookup arguments），这是一种在SNARK领域中提高证明速度的关键技术。 **核心内容概括：** 视频主要介绍了查找论证的概念及其在SNARK电路中的应用，尤其是在范围证明中的重要性。Mary解释了如何通过查找论证来证明一个私有值是否属于一个公共集合，而不泄露该值的其他信息。 **关键论据和信息：** 1. **查找论证的定义**：查找论证允许证明某个私有值W属于一个公共集合（如0到8），而不透露W的具体值。这种方法比直接检查所有约束更高效。 2. **范围证明的应用**：在SNARK电路中，范围证明经常出现，尤其是在处理溢出错误时。通过二进制分解，W被表示为多个比特，这会导致证明过程中的见证膨胀。 3. **R1CS约束系统**：Mary介绍了如何在R1CS（Rank-1 Constraint System）中表示这些约束，并展示了如何通过矩阵表示来实现。 4. **Halo 2查找论证**：Mary详细讲解了Halo 2中的查找论证如何工作，包括如何通过多项式承诺和Lagrange基来简化证明过程。 5. **CULK查找论证**：最后，Mary提到CULK查找论证的研究，旨在实现比线性时间更优的复杂度，尤其是在处理大表时。 总的来说，视频深入探讨了查找论证的理论基础及其在提高SNARK电路效率方面的潜力，强调了在实际应用中优化证明过程的重要性。

ZK白板系列 - 模块五： PLONK 和自定义门

在这段视频中，Brendan与加密学家Adrian讨论了如何为Planck设计电路，重点介绍了电路的基本概念及其优化方法。视频的核心内容围绕自定义门和查找表的使用，以提高电路的效率和功能。 ### 核心内容概括： 1. **电路设计与优化**：Adrian解释了如何通过自定义门和查找表来优化电路设计，以提高SNARK（简洁非交互式零知识证明）的效率。 2. **自定义门的优势**：自定义门允许执行复杂的操作（如递归、哈希函数和椭圆曲线签名），从而减少电路中的行数，提高计算效率。 3. **查找表的应用**：查找表用于高效地进行范围检查和验证操作，尤其是在处理加密货币时，确保数据在有效范围内。 ### 关键论据与信息： - **电路的基本结构**：电路由多个“门”组成，每个门执行特定的算术操作（如加法和乘法），并通过公共和私有输入进行计算。 - **自定义门的实现**：通过引入选择器变量，Adrian展示了如何将加法和乘法的约束整合为一个大约束，从而简化电路设计。 - **查找表的优势与挑战**：查找表可以存储所有可能的操作结果，允许快速验证而无需重复计算，但需要平衡表的大小与计算复杂度。 - **Lagrange插值与多项式**：视频中提到，Planck使用Lagrange插值来处理电路中的约束，确保在不同的输入条件下，电路的输出保持一致。 总的来说，视频深入探讨了现代电路设计中的复杂性，强调了通过自定义门和查找表来提高效率的重要性，同时也指出了在实际应用中需要考虑的工程挑战。

ZK白板系列 - 第三模块：构建SNARK #2

在本段视频中，讲者深入探讨了如何构建SNARK（简洁非交互式知识论证），并介绍了其中的美妙代数思想。视频的核心内容包括对SNARK的构建过程的详细解释，特别是通过结合功能承诺方案和交互式Oracle证明来实现。 **主要观点概括：** 1. **SNARK的定义与构建**：SNARK是一种允许证明者在不透露具体信息的情况下，向验证者证明其拥有某个见证的有效性。构建SNARK的关键在于使用算术电路模型，通过功能承诺方案和交互式Oracle证明的结合来实现。 2. **功能承诺方案与交互式Oracle证明**：功能承诺方案负责复杂的密码学部分，而交互式Oracle证明则是信息理论的组成部分，其安全性不依赖于复杂性假设。视频中提到的具体实例是多项式承诺方案（PCS）和多项式交互式Oracle证明（poly-IOP）。 **关键论据与信息：** 1. **多项式承诺方案（PCS）**：允许证明者承诺一个多项式，并在后续阶段证明该多项式在某一点的值。这种承诺的大小和验证时间都应为多项式的对数级别。 2. **多项式交互式Oracle证明（poly-IOP）**：通过预处理电路生成证明参数，验证者通过随机选择点来验证承诺的多项式是否满足特定条件。 3. **零测试与求和检查**：视频中介绍了如何通过零测试来验证多项式是否在某个集合上为零，以及如何通过求和检查来验证多项式在某个集合上的值的和是否等于给定值。 4. **Plonk的构建**：讲者详细描述了Plonk的构建过程，包括如何通过插值构造多项式P来编码计算轨迹，并通过零测试和其他方法验证输入、门约束和布线约束的正确性。 最后，视频强调了Plonk的高效性和灵活性，尽管在处理大型电路时可能会面临内存需求较高的问题。整体而言，视频提供了对SNARK构建过程的深入理解，并展示了其在密码学和计算理论中的重要应用。

ZK白板系列 - 模块二：构建 SNARK

在本段视频中，讲解了如何构建一个简洁非交互式知识论证（SNARK）的基本组件和流程。视频的核心内容包括： 1. **SNARK的构建框架**：构建SNARK的过程主要结合了两种概念：功能承诺方案和交互式Oracle证明（IOP）。功能承诺方案允许证明者承诺一个函数，而交互式Oracle证明则用于验证证明者是否知道某个满足特定条件的证据。 2. **关键论据和信息**： - **计算模型**：使用算术电路作为计算模型，电路通过模P的加法和乘法门进行运算，输出有限域中的元素。 - **预处理步骤**：在SNARK的构建中，首先需要对电路进行预处理，生成公用参数供证明者和验证者使用。 - **证明过程**：证明者通过承诺某个函数并生成证明，验证者则通过查询和验证这些承诺来决定是否接受证明。 - **功能承诺的性质**：功能承诺需要满足绑定性（即一旦承诺，证明者不能更改承诺内容）和可选的隐藏性（即承诺内容对验证者不可见）。 - **多项式承诺方案**：视频特别强调了多项式承诺方案（PCS），它允许证明者承诺一个多项式，并在后续阶段证明该多项式在特定点的值。 - **KZG承诺方案**：KZG方案是一个具体的多项式承诺方案，具有高效的承诺和验证过程，但需要信任的设置。 - **交互式Oracle证明的结构**：交互式Oracle证明通过随机值的交互来确保证明的安全性，验证者在承诺后选择随机值，防止证明者伪造证明。 视频最后提到，下一段将深入探讨如何构建多项式交互式Oracle证明，并结合功能承诺方案形成最终的SNARK。

ZK白板系列 - 第一模块：什么是SNARK？

视频的核心内容是关于SNARK（Succinct Non-Interactive Arguments of Knowledge）的介绍，包括其定义、构建方式及实际应用。SNARK是一种用于证明某个陈述的简短证明方法，能够在不透露具体信息的情况下，向验证者证明某个信息的真实性。 关键论据和信息包括： 1. **SNARK的定义**：SNARK是一种简洁的非交互式知识证明，允许证明者生成一个短小的证明，验证者可以快速验证该证明的有效性。 2. **零知识SNARK**：这种扩展形式不仅证明了某个陈述的真实性，还确保在证明过程中不泄露任何关于证明内容的信息。 3. **应用场景**： - **隐私保护**：在公共区块链上进行私密交易，如Tornado Cash和Zcash，确保交易内容不被公开。 - **合规性**：例如，交易所可以证明其资产充足而不透露具体资产信息。 - **税务证明**：未来可能实现零知识税务证明，用户无需公开所有财务信息即可证明其税务合规。 - **可扩展性**：通过批量处理交易并生成短证明，减少区块链上的验证工作量。 4. **构建过程**：SNARK的构建涉及设置程序、证明者和验证者的交互，确保证明的简洁性和快速验证。 5. **不同类型的SNARK**：包括需要信任的设置和透明设置，后者不需要秘密随机数，降低了安全风险。 视频强调了SNARK在区块链技术中的重要性，尤其是在隐私保护和合规性方面的潜在应用，以及其在未来技术发展中的广泛前景。

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实现了高效的电路验证，成为现代密码学和区块链技术中重要的工具之一。

ZKP MOOC 第 4 课：交互式证明

在本次讲座中，Justin Thaler 介绍了基于交互式证明的 SNARK（简洁非交互式知识论证）的设计，重点讨论了如何利用交互式证明构建 SNARK，特别是在电路可满足性问题上的应用。 ### 核心内容概括 1. **SNARK 定义**：SNARK 是“简洁非交互式知识论证”的缩写，指的是一种简短且易于验证的证明，能够证明某个声明的真实性。SNARK 的特点是证明短小且验证快速。 2. **交互式证明与 SNARK 的关系**：交互式证明是 SNARK 的基础，交互式证明允许证明者和验证者通过多轮交互来确认某个声明的真实性，而 SNARK 则是将这一过程转化为非交互式的形式，适合在区块链等场景中使用。 ### 关键论据与信息 1. **交互式证明的特点**： - 交互式证明需要多轮交互，验证者通过发送挑战来确认证明者的声明。 - 交互式证明的安全性依赖于统计性质，而 SNARK 的安全性则依赖于计算复杂性。 2. **多项式扩展**：在构建 SNARK 时，使用多项式扩展来处理电路的证明。通过将电路的每个门的值视为一个函数，并利用多项式扩展来确保该函数在所有输入下的行为一致。 3. **求和检查协议**：Thaler 介绍了求和检查协议（sum-check protocol），该协议允许验证者通过少量查询来确认多变量多项式在布尔超立方体上的值是否为零。这一协议的设计使得验证者能够高效地确认电路的正确性。 4. **电路可满足性问题**：通过将电路的每个门的值视为一个函数，并利用多项式扩展，验证者可以在不完全了解电路的情况下，确认证明者所声称的电路输出是否正确。 5. **SNARK 的构建过程**： - 证明者首先发送一个多项式，该多项式扩展了正确的转录。 - 验证者通过求和检查协议确认该多项式在布尔超立方体上的值是否为零。 - 最终，利用 Fiat-Shamir 转换将交互式协议转化为非交互式协议，使得 SNARK 可以在区块链等场景中使用。 ### 总结 本次讲座深入探讨了 SNARK 的构建过程，强调了交互式证明在其中的重要性。通过求和检查协议和多项式扩展，证明者能够有效地证明电路的可满足性，而验证者则可以通过少量的查询来确认这一证明的有效性。这一过程不仅提高了证明的效率，也确保了安全性，适用于现代区块链技术的需求。