# 零知识证明和zk-SNARK构造 By [戈文波](https://paragraph.com/@gewenbo) · 2024-01-26 --- **第一部分：零知识证明** -------------- 零知识证明（Zero-Knowledge Proof，ZKP）是密码学中的一个重要概念，它允许一方（证明者）向另一方（验证者）证明他们知道某个特定的信息，而不需要透露任何关于这个信息的具体内容。 在零知识证明(Zero-Knowledge Proof)中,证明(Proof)指的是证明者(Prover)向验证者(Verifier)证明某个陈述或命题是正确的过程。 **零知识证明的发展历史** -------------- 1. **1980年代初期**：零知识证明的概念由Shafi Goldwasser、S. Micali和C. Rackoff在1985年的论文《The Knowledge Complexity of Interactive Proof Systems》中首次提出。他们定义了交互式证明系统的知识复杂性，并引入了零知识证明的概念。 2. **1980年代中期**：L. Adleman和M. Blum在1987年的工作中进一步发展了零知识证明的理论，他们提出了一种新的交互式证明系统，即对于一类NP问题，存在一个零知识的交互式证明系统。 3. **1990年代**：零知识证明开始被应用于实际的密码学系统中，如安全多方计算（Secure Multi-Party Computation）和身份验证协议（Authentication Protocols）。 4. **21世纪初**：随着计算能力的提高，零知识证明开始被用于更复杂的应用场景中，如电子投票、电子货币等。 5. **2010年代**：零知识证明在区块链技术中得到广泛应用。例如，Zcash是一种使用零知识证明技术（zk-SNARKs）实现的隐私保护的加密货币。 6. **2020年代**：零知识证明的研究和应用进入了新的阶段，人们开始关注如何提高零知识证明的效率，以满足大规模应用的需求。例如，zk-STARKs和Bulletproofs等新的零知识证明技术被提出，以解决zk-SNARKs在效率和可信设置方面的问题。 **零知识证明的三个特性** -------------- 1. **完全性(Completeness)**: 如果陈述是真的，验证者可以通过证明者提供的证明来验证这个陈述。 2. **可靠性(Soundness)**: 如果陈述是假的，证明者无法骗过验证者。 3. **零知识(Zero-Knowledge)**: 证明过程不会泄露证明者私有的信息。 **交互式零知识证明和非交互式零知识证明** ---------------------- * **交互式零知识证明**：在这种模式下，证明者和验证者需要进行多次交互才能完成证明过程。 * **非交互式零知识证明**：在这种模式下，证明者只需要提交一次证明，然后验证者就可以进行独立验证。 **零知识证明的例子** ------------ ### **Sigma Protocol** Sigma protocol 是一类特殊的交互式证明系统,通常用于构建非交互式零知识证明。它有以下几个特点: 1. 参与者角色包括Prover(证明者)和Verifier(验证者)。 2. 交互轮数是3轮或5轮。 3. 第一轮,Prover发送给Verifier一个承诺(commitment)。 4. 第二轮,Verifier发送给Prover一个随机挑战(challenge)。 5. 第三轮,Prover发送给Verifier一个响应(response)。 6. Verifier根据Prover的承诺、自己的挑战和Prover的响应来验证证明的正确性。 7. 满足完备性、特定知识性和特定零知识性。 8. 可以通过Fiat-Shamir启发式将其转化为非交互式零知识证明。 ### **Schnorr Protocol** Schnorr协议是一种基于离散对数问题的 Sigma 协议,由 Claus Schnorr 在 1991 年提出。它可以用于证明某个公钥对应的私钥的知识,具体流程如下: 1. Prover 选择一个随机数 r,计算 R = g^r mod p,将 R 发送给 Verifier。(p 和 g 是系统参数) 2. Verifier 选择一个随机数 e,将 e 发送给 Prover。(e 是 challenge) 3. Prover 计算 s = r + xe mod q,将 s 发送给 Verifier。(q 是某质数,x 是 Prover 的私钥) 4. Verifier 检验 g^s = R xe mod p 是否成立。如果成立,则证明通过。 Schnorr 协议安全的基础是离散对数问题的困难性。它有完全知识提取的属性,即从一个可交互的证明者那里可以提取出私钥 x。 Schnorr 协议被广泛地应用于各种需要进行身份验证或者证明私钥知识的场合,例如证明钱包所有权、签名验证等。其非交互版本也被用于构建许多密码系统。 总体来说,Schnorr 协议作为一种简单实用的 Sigma 协议,启发并推动了身份认证和数字签名等领域的发展,是现代密码学的重要组成部分。 **数学理论基础** ---------- ### **数学基础** **计算困难问题：** 零知识证明的安全性通常依赖于一些计算问题的困难性，例如整数分解问题和离散对数问题。这些问题的困难性在计算复杂性理论中有深入的研究，尽管这些问题并未被证明是NP-完全的，但在实践中已被广泛接受为难以解决。 ### **计算复杂性理论** ZKP的一个关键假设是存在一些计算问题，它们在计算复杂性理论中被定义为“NP-hard”。这意味着我们可以在多项式时间内验证一个解决方案的正确性，但找到一个解决方案可能需要指数级的时间。 **零知识证明里的角色** ------------- ### **prover（证明者）** 证明者是零知识证明过程中的一个角色，他们会生成并提供证明，以证明他们知道某个特定的信息。 ### **verifier（验证者）** 验证者是零知识证明过程中的另一个角色，他们会接收并检查证明者提供的证明，以确定证明者是否真的知道某个特定的信息。 ### **simulator（模拟器）** 模拟器是在证明零知识性时用到的一个理论构造，它可以在不知道证明者的秘密知识的情况下，模拟出看上去和真实的交互证明一样的对话。 ### **extractor（提取器）** 提取器也是一个理论构造，用于证明可靠性。如果证明者可以通过验证者的交互验证，那么就存在一个提取器能从证明者的策略中"提取"出一个使得陈述为真的证据。 ### **challenger（挑战者）** 在某些类型的零知识证明中，挑战者是一个角色，他们向证明者提出难题或挑战，证明者必须通过回答这些问题来证明他们知道某个特定的信息。 ### **generator（生成器）** 生成器是在某些类型的零知识证明中用到的一个构造，它用于生成证明所需的公共参数或设置。 ### **以上例子** 假设我们有一个大的素数p和一个本原根g，Alice想要向Bob证明她知道某个数x使得g^x = h (mod p)，而不透露x的任何信息。 第一步：承诺 Alice选取一个随机数r，计算t = g^r (mod p)并将t发送给Bob。 第二步：挑战 Bob现在向Alice发送一个随机选择的挑战，这个挑战是一个随机数c。 第三步：响应 Alice收到c后，计算y = r + cx (mod p-1)并将y发送给Bob。 第四步：验证 Bob收到y后，验证等式g^y ?= t \* h^c (mod p)是否成立。如果等式成立，那么Bob接受证明。 模拟器的操作 模拟器在没有x的情况下需要模拟这一过程。模拟器可以先随机选择一个y，然后计算一个t'使得t' = g^y / h^c (mod p)，其中c是模拟器自己随机选择的。模拟器将t'作为承诺发送给Bob，然后等待Bob发回挑战c。由于模拟器已经知道c，它可以直接发送y作为响应。Bob在验证时会发现等式成立，因为模拟器是根据y和c来构造t'的。 提取器的操作 提取器的工作是在多轮交互中，从作弊的Alice那里提取出x。如果Alice能够在多轮的交互中始终使得Bob接受证明，那么提取器会利用这些交互来推导出x。提取器可能会重复执行协议，改变挑战c，直到它能够从Alice提供的不同响应y1, y2, ...中解出x。 ### **例子二** 例如,证明y是模n的二次剩余(即存在x,满足y≡x2 (mod n))。该交互证明的工作流程如下: 1. Prover选择一个随机数r,满足1≤r≤n且gcd(r,n)=1,计算s=r2 mod n,发送给Verifier。 2. Verifier随机选择b∈{0,1},如果b=0,Prover发送z=r;如果b=1,Prover发送z=rx mod n。 3. Verifier检查z2≡syb (mod n),接受该证明。 则该证明的模拟器Sim如下: 1. 随机选择b∈{0,1}。 2. 随机选择z∈Z\*n。 3. 计算s=z2/yb mod n。 4. 输出(s,b,z)。 可以证明Sim模拟出的视图与真实视图具有相同的分布。 提取器Extractor如下: 1. 与Prover进行正常交互,获得s。 2. 发送b=0,获得r。 3. “倒带”,重新发送b=1,获得rx。 4. 输出 x=rx/r mod n。 Extractor通过重新 wind 可以提取出证明者知道的秘密x。 **零知识证明的应用案例** -------------- 零知识证明在许多领域都有应用，包括身份验证、区块链技术（如Zcash和Ethereum扩容）、安全多方计算、隐私保护计算等。 zkML，zkMapReduce，zkBridge **第二部分：ZKSNARK概述** ------------------ ### **ZKNARK介绍** ZK-SNARK (Zero-Knowledge Succinct Non-Interactive Argument of Knowledge) 是一种非交互式的零知识证明，它具有证明简洁和验证快速的特点，但是它需要一个被称为“信任设置”（trusted setup）的过程。 ### **ZKSTARK介绍** ZK-STARK (Zero-Knowledge Scalable Transparent Arguments of Knowledge) 是另一种零知识证明，与ZK-SNARK相比，它不需要“信任设置”过程，因此具有更高的透明性，但是其证明的生成和验证过程比ZK-SNARK更复杂和更慢。 **第三部分：零知识方案构造** ---------------- 零知识方案指的是实现零知识证明的具体方法和框架。一个零知识方案通常包括以下几个部分： 问题的定义：定义需要证明的问题或陈述。 证明的生成：证明者根据他们的私有知识生成一份证明。 证明的验证：验证者检查证明者提供的证明，以确定证明者是否知道某个特定的信息。 零知识性：证明过程不泄露证明者的任何私有知识。 在设计零知识方案时，需要考虑许多因素，包括证明的大小、生成和验证的效率、安全性以及是否需要信任设置等。不同的零知识证明技术（如ZK-SNARK和ZK-STARK）提供了不同的优点和缺点，适用于不同的应用场景。 **通常的流程** --------- 问题转化: 首先，证明者需要把待证明的问题转化为一个标准化的形式，如布尔电路或算术电路或R1CS，即电路可满足性问题（Circuit-SAT）。 生成证明: 证明者使用这个电路生成一个证明。这通常包括把电路变成多项式，转换成多项式可满足性问题（Polynomial-SAT）。 承诺: 证明者将生成的证明（多项式）进行承诺。这是一个加密步骤，旨在确保证明的完整性和防止篡改。 发送承诺: 证明者将这个承诺的证明发送给验证者。 挑战: 在许多零知识证明协议中，验证者会向证明者发送一个随机的挑战。这个挑战的目的是确保证明者真的知道解，而不仅仅是碰巧找到一个满足某些条件的证明。 应答: 证明者根据验证者的挑战构造一个应答。这个应答需要在不泄露任何有关解的信息的情况下，反驳验证者的挑战。 验证: 验证者使用证明者的应答来验证原始的证明。如果应答成功反驳了挑战，那么验证者就可以确认原始声明是真实的，而不需要了解任何其他信息。 ### **算法** keygen(λ, F) -> gp 系统初始化,输出公共参数gp。 commit(gp, f, w) -> com 将多项式f在点w处进行评估承诺,输出承诺com。 eval(gp, f, w) -> y, π 计算f(w)=y并生成证明π。 verify(gp, com, y, π) -> accept/reject 验证π是否证明了com承诺的多项式在某点处的评估结果为y。 通过加入witness w,并只在Prover端使用,可以保证证明的零知识性。 验证者通过com, y, π 判断评估结果而不知晓实际的评估点。 在基于多项式承诺的零知识证明系统中,τ是一个由证明生成者(Prover)随机选择的点,用于生成多项式f的随机承诺。 ### **τ的来源** 具体来说,τ的产生过程是: Prover决定需要证明的多项式f和评估点x。 Prover随机选择一个值τ,作为生成随机承诺的评估点。 Prover计算f(τ)得到结果u,然后对u进行承诺,生成随机承诺com\_f。 在构造证明π时,Prover会使用这个τ来定义证明多项式q。 Prover计算q(τ)并进行承诺作为证明π。 验证者通过检查com\_f和π在点τ上的承诺关系来验证。 所以τ是一个Prover随机选择的用于承诺的点,和真正需要证明的评估点x不同,仅用于增加安全性防止被恶意验证者攻击。 τ不需要向验证者披露,但要在Prover构造com\_f和π时依次使用,以保证二者在τ上的承诺关系。这就是τ的来源和作用。 **电路方案** -------- 在零知识证明中，经常将待证明的陈述转化为一个算术电路或布尔电路的满足性问题。简单来说，电路是由门（函数）和线（变量）组成的图，其中输出线的值由输入线和门函数计算得出。在零知识证明中，证明者需要证明他们知道一组输入变量的值，使得电路的输出满足某个特定的条件。 例如，对于一个布尔电路，证明者可能需要证明他们知道一组布尔值，使得电路的输出为真（1）。这样的电路可以表示各种复杂的计算问题，包括NP完全问题。 电路满足性问题的零知识证明在许多场合都有应用，例如在Zcash这样的隐私保护加密货币中，就使用了基于ZK-SNARK的电路满足性问题的零知识证明，来保护交易的隐私。 **待证明陈述表示形式** ------------- ### **算术/布尔电路** 算术电路和布尔电路是计算模型，可以表示为有向无环图。在这些电路中，每一个节点代表一个操作，例如加法、乘法（在算术电路中）或者AND、OR、NOT（在布尔电路中）。电路的输入是一些变量或常数，输出则是根据这些操作得到的结果。 ### **一阶约束系统** 阶约束系统（Rank-1 Constraint Systems, R1CS）是一种特定的代数约束系统，广泛应用于零知识证明的构造。在R1CS中，每一个约束都要求一组变量的线性组合、另一组变量的线性组合和第三组变量的线性组合的乘积相等。这种约束系统对于构造零知识证明非常有用，因为它可以有效地编码许多不同类型的计算和条件。 ### **对数空间可计算电路** 对数空间可计算电路是一种特殊类型的电路，其计算过程只需要对数级别的内存空间。这类电路在复杂性理论和计算机科学中有重要应用，因为它们可以有效地解决一些具有特定属性的问题。对数空间电路的一个关键特性是它们能够在非常有限的空间内执行复杂的计算，这使得它们在处理大规模数据集或者内存受限的环境中特别有用。 ### **分层算术电路** 分层算术电路是一种特殊的算术电路，其中的门（或操作）被分成不同的层次，每一层的门只能使用前一层门的输出作为输入。这种结构使得电路的计算过程可以进行有效的并行化，同时也能够减少电路的深度。在零知识证明的构建中，分层算术电路可以帮助降低证明的复杂性。 ### **数据并行电路** 数据并行电路是一种可以处理多个输入数据并同时执行多个操作的电路。在这种电路中，同一操作可以在不同数据上并行执行，从而实现高效计算。数据并行电路在处理大规模数据时非常有效，因为它们可以利用现代硬件的并行计算能力来加速运算。 ### **二次算术程序（QAP）双线性配对** 这可能是指在零知识证明中使用双线性配对来处理次算术程序。双线性配对是一种数学工具，可以用于构造各种密码学协议，包括一些零知识证明系统。二次算术程序是一种特殊类型的算术电路，其中的每个门只能执行乘法或者加法操作，并且所有的乘法门的输入必须来自于前一层的门或者输入层。 **几种构造零知识方案的Information-Theoretic (IT) Proof Systems** ------------------------------------------------------ ### **IP (Interactive Proof Systems)** 交互式证明系统,是零知识证明的一个重要基础。 IP系统由证明者(Prover)和验证者(Verifier)组成,通过交互验证某个语句的正确性。 其中,证明者试图让验证者相信某个语句是正确的;验证者则试图 确认该语句确实为真。 IP系统通常有以下特点: * 证明者和验证者交替发送信息(回合交互) * 信息量每轮都很小(通常是多项式大小) * 通过有限回合交互,验证者可以判断语句正确性 * 可提供完全性和可靠性保证 **Sumcheck protocol**：Sumcheck协议是一种交互式证明系统，它允许证明者证明一个关于多项式的性质，例如多项式在一个域上的和。这种协议被广泛应用于一些基于PCP的零知识证明系统。 ### **MPC in-the-Head** MPCin-the-Head是一种广泛用于零知识证明的技术，它将多方计算（MPC）的概念引入到零知识证明中。在这种方案中，证明者在自己的“头脑”中模拟一个多方计算协议，然后使用这个模拟过程来生成证明。 ### **IOP(Interactive Oracle Proof)** 交互式预言机证明(Interactive Oracle Proofs,IOP)是构建SNARK的一个关键概念。 IOP是一个交互协议,包括一个验证者和一个预言机(具有特定功能的黑盒)。验证者可以交互查询预言机,以此验证某个语句的正确性。 IOP的特点: * 验证者只与预言机进行交互,不需要了解预言机的内部构造 * 通过有限的交互,验证者可以验证复杂语句的正确性 * 预言机无需保密,只需要正确回答查询 SNARK构建范式中,先定义一个功能性承诺方案,然后构建一个兼容的IOP。通过非交互化(如Fiat-Shamir转换),可以将IOP转换为SNARK。 * 多项式IOP:预言机是计算多项式的黑盒 * 多线性IOP:预言机是计算线性多项式的黑盒 * 向量IOP:预言机支持向量运算的黑盒 ### **PCP(Probabilistically Checkable Proofs)** 概率检查可证明,它是一个非常重要的理论框架,对零知识证明系统的发展产生了深远影响。 PCP 的主要思想是: 对于一个长证明,验证者只需要读取证明的少数位置,就可以以非常高的概率判断整个证明是否正确。 也就是说,只需要对证明进行抽样式的随机验证,就可以检测出错误,而不需要全面检查整个证明。 **承诺方案** -------- 承诺方案（Commitment Scheme）是密码学中的一个重要概念，它允许一个人向其他人承诺一个值，而不立即透露这个值。承诺方案有两个重要的属性：隐藏性和绑定性。 隐藏性（Hiding）：承诺方案应该保证，一旦一个值被承诺，就不能从承诺本身中获取任何关于这个值的信息。 绑定性（Binding）：承诺方案应该保证，一旦一个值被承诺，就不能修改这个值。也就是说，承诺者不能在不被发现的情况下改变他们已经承诺的值。 在零知识证明中，承诺方案经常被用来保护证明者的私有信息。例如，证明者可以先对他们的私有信息做一个承诺，然后在证明过程中使用这个承诺，而不是直接使用私有信息。这样，验证者可以验证证明的正确性，而不需要知道证明者的私有信息。 假设我们要对一个多项式函数 f(x) 进行承诺。 1. 设置一个双线性映射组G。随机选择s作为秘密,计算 g^s作为公开的生成元。 2. 对每个系数ai进行随机化,计算 g^ai\*s 得到随机化后的系数si。 3. 使用这些随机化系数计算多项式的值: f(x)_g^s = Σ(si_x^i) 4. si构成评估密钥,可以打开承诺,获取ai。g^s是校验密钥,用于公开验证。 5. 发布g^s作为vk,只有si作为pk。 常见的承诺算法包括: * 基于SHA-2的Hash承诺 * 基于椭圆曲线的椭圆曲线承诺 * 基于离散对数的Pedersen承诺 * 基于RSA问题的RSA承诺 ### **Pedersen 承诺方案例子** Pedersen 承诺方案是一种基于离散对数问题的简单且高效的承诺方案。其主要特点如下: 设置算法:选择一个循环群G,生成一个随机生成元g。选择随机的a, b,计算g^a和g^b。然后公共参数为(G, g, g^a, g^b)。 承诺算法:对消息m ∈ G,选择随机r,计算并输出承诺值C = g^m \* (g^a)^r。 打开算法:对消息m和随机数r,验证g^m \* (g^a)^r = C。 承诺的值信息理论上隐藏了消息m。 计算承诺值只需要2次指数运算。 承诺值对同一消息具有绑定性,无法打开两个不同的消息。 **承诺方案的种类** ----------- 承诺包含多项式承诺，向量承诺和多线性承诺等几大类 ### **默克尔树:抗碰撞哈希函数** 默克尔树（Merkle Tree）是一种数据结构，通常用于对大量数据进行有效的验证和校验。它使用抗碰撞哈希函数来创建一个“树”结构，其中每个节点是其子节点内容的哈希值。这使得任何对数据的更改都会导致树中相应节点的哈希值改变，从而能够方便地检测出数据的篡改。 ### **里德-所罗门码;低度检查** 里德-所罗门码（Reed-Solomon codes）是一种纠错码，能够有效地处理信息传输过程中的错误。在零知识证明中，里德-所罗门码可以用于低度检查，这是一种验证电路或者函数是否为低度的方法。通过对求和验证或者其他方法的使用，可以有效地验证一个里德-所罗门码是否满足特定的属性或者条件。 1. Keygen: 随机采样一个哈希函数。 2. Commit: 将多项式f的系数矩阵按行进行线性编码,并计算默克尔树根作为承诺。 3. Eval 和 Verify: (1) 邻近性测试:对所有行做随机线性组合,并用t个随机开放的列验证一致性。目的是检查编码矩阵近似地包含了一个有效代码。 (2) 一致性测试:计算u乘以系数矩阵等于m,对m编码并用t个随机列验证一致性。目的是检查计算结果m被正确编码。 (3) 如果以上两步都通过,那么可以推断出: * 编码矩阵包含了f的有效编码 * m是一个根据u正确计算的输出 (4) 结合上述两点可以证明:f(u) = m 通过编码的纠错性质,随机抽样两次验证编码的近似正确性,从而完成了对多项式计算结果的验证。 验证原理 1. 在证明中,首先计算得到了声称的运行结果m=f(u)。 2. 为了证明m是根据给定的多项式f正确计算得到的,需要进一步编码和验证。 3. 将m进行编码,得到编码结果m'。这里使用的编码需要具备纠错能力,如Reed-Solomon码。 4. 然后随机抽取t列,要求证明者打开这些列的编码值和默克尔证明。 5. 验证者根据打开的数据,可以重新计算编码列的根,并与m'的根进行比较。 6. 如果 reopened 列根和原根一致,则这t列编码是正确的。 7. 当t足够大时,根据编码的纠错性质,m'整体就非常可能是m的正确编码。 8. 也就是说,m'包含了运行结果m的有效编码。 9. 从而间接证明了m就是根据多项式f和输入u正确计算得到的。 ### **内积论证** 内积论证是一种证明两个向量内积值的有效方法。在零知识证明中，内积论证常常用于证明两个向量的内积满足某个特定值，而不需要揭示这两个向量的具体内容。这对于保护证明者的隐私非常有用。 IPA作为一种多项式承诺方案,其核心思路是利用向量内积的性质来进行多项式评估的正确性证明。具体数学构造如下: 证明者选择随机向量v,计算u = ⟨v, f⟩,其中f表示多项式系数向量。 证明者希望证明y是点x处多项式f(x)的评估结果。 构造向量w,满足: f - y⋅δx = (x - v)⋅w,其中δx是标准基向量。 计算t = ⟨v, w⟩。 验证者检查内积关系:⟨v, f⟩ - y⋅⟨v, δx⟩ = (x - v)⋅t 就可以验证y是否正确。 在IPA中,π表示证明,即证明者要向验证者传递的信息,用来证明某个多项式在给定点上的评估结果是正确的。 具体在IPA中,π包含两个要素: 1. u:这是对整个多项式系数的编码,u = ⟨v, f⟩。它承诺了整个多项式f。 2. t:这是对特殊向量w的编码,t = ⟨v, w⟩。它与u配合可以证明特定点x处的评估y是正确的。 所以如果用π表示IPA中的证明,则可以表示为: π = (u, t) u承诺整个多项式;t针对特定评估点,与u一起验证评估值。 ### **KZG承诺** 设置环形椭圆曲线群G,群阶为一个大素数p。 随机选择一个秘密的值τ,用于生成G的生成元H。 对于多项式f(X),计算它在τ点上的评估结果f(τ),然后在群G中进行标量乘法,得到f(τ)·H。 上一步计算的结果就是对f(X)的承诺,记为com\_f。这个承诺隐藏了τ,所以其他人不能从com\_f推断出f(X)。 为了证明f(u)=v,构造另一个多项式q(X),使q(X)·(X-u) = f(X)-v成立。 计算q(τ)·H,记为com\_q。根据q(X)的构造,有(τ-u)·com\_q = com\_f - v·H。 验证者可以通过群G的配对运算来验证上式,而无需知道τ。 如果验证成功,就证明了f(u)=v。 这样通过椭圆曲线和多项式插值,实现了对复杂多项式特定点值的验证。这就是KZG承诺方案的基本数学原理。 Schwartz-Zippel引理: 如果多项式f(x)不是恒等于0,则当取随机点时,f(x)等于0的概率非常小。 具体在KZG承诺的安全性分析中,使用了这个引理的以下变体: 如果两个不同的低阶多项式f(x)和h(x)在一个随机点τ上取值相等,则这种概率非常小。 也就是说: Pr\[ f(τ) = h(τ) \] ≤ d/p 这里d是多项式的最大阶数,p是基域大小。 在KZG承诺的安全性证明中,正是利用了这一引理,证明了攻击者很难构造一个不同的低阶多项式,使其在随机点τ上与原多项式相等。 **一些优化技术** ---------- 对于多项式承诺的验证，通常使用的方案包括但不限于以下几种： 1. **批处理技术**：如果有多个多项式承诺需要验证，一种有效的方式是通过批处理技术（Batching Techniques），将多个验证任务合并成一个。这大大减少了计算和验证的时间。 2. **Fast Fourier Transform (FFT) based techniques**：使用快速傅里叶变换（FFT）的技术可以高效地验证一系列值是否是一个多项式的评估。这种方法在一些零知识证明系统中得到了应用。 3. **Fiat-Shamir heuristic**：Fiat-Shamir启发式是一种将交互式证明转化为非交互式证明的技术。在零知识证明中，它经常被用来验证多项式承诺。 4. **Pippenger's algorithm**：Pippenger的算法是一种高效的点乘算法，它可以用于验证椭圆曲线上的承诺。这种方法在一些使用椭圆曲线的零知识证明系统中得到了应用。 **Fiat-Shamir启发式** ------------------ 将交互式零知识证明转换为非交互式零知识证明的一个常用方案是使用**Fiat-Shamir启发式**。这是一种将交互式公共金钥证明系统转换为非交互式签名方案的通用方法。 以下是用Fiat-Shamir启发式从交互式证明转换到非交互式证明的基本步骤： 1. **交互式零知识证明:** 在原始的交互式证明中，证明者和验证者会进行多轮的挑战-应答过程。证明者会发送一个证明，验证者会回应一个随机挑战，然后证明者会发送一个针对这个挑战的应答。 2. **应用Fiat-Shamir启发式:** 在Fiat-Shamir启发式中，证明者会使用一个密码学安全的哈希函数来生成挑战，而不是等待验证者提供挑战。具体来说，证明者会将他们的原始证明输入到哈希函数中，然后使用哈希输出作为挑战。然后，他们会生成一个针对这个挑战的应答，就像在交互式证明中一样。 3. **生成非交互式证明:** 最后，证明者将原始证明、挑战和应答一起打包成一个非交互式证明。验证者可以通过应用相同的哈希函数到原始证明上，然后比较生成的挑战和非交互式证明中的挑战是否相同来验证证明。 这种方法的一个关键优势是它消除了在证明过程中的交互，这使得证明可以被任何人在任何时候验证，而无需证明者的参与。然而，这种方法也有一些限制，例如它需要一个密码学安全的哈希函数，并且在某些情况下可能不提供零知识性质。 **递归零知识证明** ----------- 递归零知识证明是一种特殊的零知识证明方案，它允许你在一个证明中嵌入另一个证明。这在许多加密协议和应用中是非常有用的，特别是在区块链和加密货币中。 递归零知识证明的关键思想是能够构造一个证明，证明你知道另一个证明的有效性。换句话说，你不仅仅是在证明你知道一个特定的声明（例如，一个交易是有效的），你还在证明你知道一个证明（例如，这个交易的证明是有效的）。 这样做的优势是，你可以将多个证明压缩成一个单一的证明，而无需透露任何关于原始证明或其所证明的声明的信息。这使得你可以有效地处理和验证大量的证明，特别是在资源受限或者需要高效率的环境中。 ### **Proof-Carrying Data** 基本思想是: 在分布式计算任务的每个步骤,节点会生成一个证明,证明它执行这一步的计算是正确的。 然后将这个证明与下一步的计算输入一起传递给下一个节点。 所以每个节点接收到的输入都附带了证明,证明这个输入的计算是正确的。 节点可以验证上一步的证明,确保自己接收到的输入是合法的,然后再执行下一步计算。 最终结果也会附带一个证明,可以被验证器全面验证整个计算的正确性。 这样,整个分布式计算的所有中间状态都被证明化了,任何节点的错误或欺骗行为都能被检测。 ### **Folding schemes** 折叠方案最初由 Nova 引入。 它是一种将两个待证明的实例压缩为一个实例的方法。 假设我们有一个电路 C 和两个实例 (x1,w1) (x2,w2)。 我们想将它们折叠在一起并输出一个新的折叠实例 (x, w)。 如果两个原始实例是有效的，我们将得到一个有效的折叠实例。如果折叠实例是有效的，证明者必须知道原始实例 x1 和 x2 的有效见证 w1 和 w2。 --- *Originally published on [戈文波](https://paragraph.com/@gewenbo/zk-snark)*