零常识证明(ZK Proofs)是功能强壮的密码学原语，答应一方（证明者）在不透露任何私密信息的情况下，使另一方（验证者）相信某个给定的声明是真实有用的。近年来ZK在可验证私密核算、为核算机程序供给有用性证明以及区块链范畴获得了广泛重视，而且对世界的开展发生了重大的积极作用。
尽管ZK是新兴技能，但其根本思想和概念能够追溯到上世纪80年代。在与比特币和以太坊等区块链结合后，ZK技能的开展明显加速，因为区块链能够经过SNARK和STARK进行有用性证明，极大程度的增强可扩展性，这使ZK在区块链范畴中炙手可热。
正如Starkware创始人Eli Ben-Sasson所言，近年来咱们见证了密码学证明体系的“寒武纪大爆发”，每种证明体系各有一同的优势和劣势，而且在设计时进行了权衡。硬件的前进、更好的算法、新的观点和周边工具，都刺激了ZK体系的功能提高及新式体系的诞生。许多证明系现已在实践运用中被选用，而人们仍在不断扩展ZK的边界。
这也促使人们深化考虑一个问题：是否有一个适用于一切运用的通用ZK证明体系？对此咱们以为这种或许性不大，原因有三点：
1. 运用程序的多样性；
2. 不同的束缚类型（包括内存、验证时刻、证明时刻）；
3. 对鲁棒性的需求（假如一种证明体系被黑客攻破，咱们仍然能够切换到其他体系作为稳妥）。
依据上述理由，ZK证明体系理应是多样性的。但即便证明体系的种类许多，也一定有一个明显的共性：ZK证明能够被快速的验证，而且拥有一个验证层，能够很简单地习惯新的证明体系，以处理其依附的根底层（如以太坊）的相关困难。
在ZK范畴中，zk-SNARK被频繁提及。它是完成零常识证明的一种方法，经过运用杂乱的数学工具，如双线性配对和算术电路，来完成高效的零常识证明。zk-SNARK的特点是证明过程简洁化、非交互式，证明者和验证者之间只需求单次通讯不需求屡次交互。此外，zk-SNARK的证明尺度非常短小，验证功率高，适合在资源有限的环境中运用。
而zk-STARK是另一种常见的方法，旨在战胜zk-SNARK的某些局限性。zk-STARK不依赖于可信设置，运用更通明的数学结构体系，如多项式许诺和有限域运算、哈希磕碰等，来生成和验证证明。zk-STARK比zk-SNARK更具可扩展性，适用于更大规划的核算，证明生成速度更快，可是Proof自身的尺度一般较大。
能够说，zk-SNARK和zk-STARK都是零常识证明中常用的方法，但它们在通明度、可扩展性、证明巨细等方面有所不同。
整体来看，一个ZK证明体系一般包括PIOP（多项式交互式预言机）和PCS（多项式许诺计划）两大部分。常见的PIOP计划包括PLONKish、GKR等，而常见的PCS计划包括FRI，KZG，IPA等，比方Zcash版本的Halo2运用了Plonkish+IPA的完成方法，至于zk-STARK其实能够当成是一种依据FRI的特殊的zk-SNARK。
假如更详细的说，不同类型的证明体系会运用不同的多项式许诺计划(PCS)、算术化计划、交互式预言机证明(IOP)或概率可查看证明(PCP)。
进一步说，不同的ZK证明体系往往在如下指标上有所不同：
-
密码学假定：抗磕碰哈希函数、椭圆曲线上的离散对数问题、指数常识
-
通明设置vs可信设置
-
生成证明的耗时：线性vs超线性
-
验证证明的耗时：常数时刻、对数时刻、次线性、线性
-
证明尺度的巨细
-
递归的简易性
-
算术化计划
-
单变量vs多变量多项式
下文中咱们将简要谈及ZK技能的来源，探究其根本的构建模块，概述不同ZK证明体系的鼓起和式微过程。一同，本文并不对证明体系自身进行翔实分析，而是侧重介绍那些对该范畴发生深远影响的人，究竟任何职业的开展只要经过先驱者的巨大主意并诉诸实践，才有或许完成。
zk-SNARK的历史开展头绪
来源：20世纪80~90年代
正如咱们所说到的，零常识证明并不是新概念，其界说、根底、重要定理，甚至相关的重要协议，早在上世纪80年代中期就现已呈现，首次呈现是在是在Goldwasser、Micali(Algorand创始人)和Rackoff的论文《The Knowledge Complexity of Interactive Proof Systems》中。
而如今咱们用来构建ZK-SNARK技能的要害思想和协议，在20世纪90年代就被出，比方Sumcheck协议，将对多元多项式求值总和的声明，简化为在椭圆曲线上随机挑选的点进行单一求值，该协议为ZK技能奠定了重要根底。
所以，ZK思想的萌芽实践上远远早于比特币的呈现，但在其时遍及缺少ZK的适宜用例，人们也无法供给满意ZK证明体系所需的强壮算力，究竟互联网和硬件设备在上世纪90年代并不兴旺。
GKR协议（2007)
GKR（Goldwasser-Kalai-Rothblum）是一种交互式协议，证明者的运转时刻与电路中逻辑门的数量呈线性相关，而验证者的耗时则与电路巨细呈次线性关系。在GKR协议中，证明者和验证者需求对一个有限域上的双输入算术电路运转成果达到一致，该电路的深度为d，第d层为输入层，第0层为输出层。协议从关于电路输出的声明开端，经过递归将其简化为对上一层的声明。最终，咱们能够将对输出的声明转换为对电路输入参数的声明，这很简单被验证。能够说，GKR协议是在前面提及的Sumcheck协议根底上进行了高度简化的。
KZG多项式许诺计划(2010)
2010年，三名ZK范畴的专家——来自德国研究机构MPI-SWS的Kate，来自加拿大密码学公司Certicom Research的Zaverucha，以及来自滑铁卢大学的Goldberg联合宣布了一篇论文《Constant-Size Commitments to Polynomialsand Their Applications》。该论文提出了一种运用双线性对群的多项式许诺计划，名为KZG。
该许诺由一个独自的群元素组成，提交者能够高效地提醒多项式的任何正确求值，借助批处理技能，能够对多个多项式的求值进行提醒。KZG许诺成为了一些闻名ZK证明体系的根本构建模块之一（比方以太坊PES小组用的halo2），更是在以太坊的EIP-4844中起到了核心作用。若要更直观地了解批处理技能的概念，能够参阅关于Mina-Ethereum桥的文章Mina-Ethereum bridge。
参阅资料：https://blog.lambdaclass.com/mina-to-ethereum-bridge/
依据椭圆曲线的有用ZK-SNARK体系（2013）
ZK-SNARK的第一个有用结构呈现在2013年，需求一个预处理步骤来生成证明密钥和验证密钥，而且是随程序或电路特定的，没有泛用化。这些密钥的尺度或许非常大，并取决于隐秘参数自身；若这种保密性被损坏，攻击者就能够伪造出证明。在这种有用的ZK-SNARK体系中，要将代码转换为能够被证明的方法，需求将代码编译为一组数学方法的多项式束缚。
起初，上述过程有必要手动完成，既耗时又简单犯错。后来针对该方向的技能更迭，首要企图处理下述核心问题：
-
供给更高效的证明
-
削减预处理的次数
-
完成通用的而非电路特定的设置
-
防止可信设置
-
开发运用高档语言描述电路的办法，而不是手动编写多项式束缚
Pinocchio协议（2013）
Pinocchio协议是第一个实践可用的zk-SNARK体系，依据二次算术程序（QAP），开始的证明巨细为288字节。Pinocchio的工具链供给了一个将C语言编译为算术电路的编译器，它能够进一步转换为QAP。Pinocchio协议要求验证者生成密钥，这些密钥并不通用，而是由电路特定的。该证明体系生成和密钥设置的渐进时刻杂乱度与核算规划呈线性关系，验证时刻与公共输入和输出的巨细呈线性关系。
Groth16(2016)
Groth引进了一种新的ZK明算法，在处理R1CS上具有更高的功能。R1CS即Rank-1 Constraint System，一阶束缚体系，是zk-SNARK中的一种多项式束缚方法。Gorth的证明是数据规划最小的（仅包括三个群元素），且验证速度很快，只需进行三个配对运算，以及一个使参阅字符串结构化的预处理步骤。但Gorth首要的缺陷是每个需求证明的程序都需求进行不同的可信设置，这在实践运用中相当不便。
后来Groth16被用于ZCash，后者是一个比较有名的隐私区块链项目（Starkware创始人Eli参加做的）。
Bulletproofs与IPA（2016）
前面说到的KZG多项式许诺计划，其一大缺点是需求可信设置。Bootle等人提出了一种有用的零常识证明体系，该体系对满意内在乘积关系的Pedersen许诺的敞开进行了分析。内积证明具有线性杂乱度的证明耗时，证明者和验证者之间的交互次数是对数级的，但验证时刻是线性的。此外Bootle等人还开发了一种不需求可信设置的多项式许诺计划。这些思想后来被Halo2和Kimchi等选用。
Sonic、Marlin和Plonk（2019）
Sonic、Plonk和Marlin处理了Groth16算法中每个程序都需求可信设置的问题，引进了通用且可更新的结构化参阅字符串（用来完成仅需一次的可信设置）。其间，Marlin供给了一个依据R1CS的证明体系，而且成为了Aleo的核心技能。
而Plonk引进了一种新的算术计划（后来被称为Plonkish）以及运用grand-product来查看仿制束缚。Plonkish还答应引进用于特定操作的专用电路逻辑门，即所谓的“自界说门”。许多闻名的区块链项目方都用到了Plonk的定制化版本，包括Aztec、zkSync、Polygon zkEVM、Mina、以太坊PSE小组和Scroll等。
Spartan（2019）
Spartan为运用R1CS描述的电路供给了一个IOP，运用了多变量多项式和求和查验协议的特性。经过运用适宜的多项式许诺计划，它完成了一套具有通明性的zk-SNARK体系，而且生成证明的时刻杂乱度是线性的。
Lookups(2020)
Gabizon和Williamson于2020年在论文中提出了plookup，运用grand-product证明某个值包括在预先核算出的真值表中，展示了如何将plookup参数引进Plonk算法。
但是，这些lookup arguments有一个一同的问题，证明者需求耗费巨大成本树立完整的真值表，因而之前围绕着Lookups的工作都致力于将证明成本削减。
后来Haböck在论文中引进了LogUp，它运用对数导数将grand-product查看转化为倒数之和。LogUp关于Polygon zkEVM的功能提高至关重要，因为他们需求将整个真值表拆分为多个STARK模块。这些模块有必要正确链接，而跨表查找能够强制完成这一点。尔后LogUp-GKR的引进又经过GKR协议提高了LogUp的功能。
Caulk是第一个使证明时刻与真值表巨细呈亚线性关系的计划，它的预处理时刻杂乱度为O(NlogN)，存储占用的空间杂乱度为O(N)，其间N是真值表巨细。随后又呈现了其他计划，如Baloo、flookup、cq和caulk+。此外，Lasso提出了若干改善计划，防止在真值表具有特定结构时对其进行许诺。
HyperPlonk（2022）
HyperPlonk在论文《HyperPlonk: Plonk with Linear-Time Prover and High-Degree Custom Gates》中被提出。HyperPlonk依据Plonk的理念，选用多变量多项式。它不运用除法来查看束缚的履行，而是依赖于求和查验协议。一同，它还支持高阶束缚，而不会影响证明生成的时刻。
因为运用了多变量多项式，无需履行快速傅里叶变换（FFT），证明生成的时刻与电路规划成线性关系。HyperPlonk还引进了一种适用于小字段的新置换IOP，而且选用依据求和查验的协议，削减了证明者的工作量、证明巨细，以及验证时刻。
运用防磕碰哈希函数的ZK证明体系
在2013年Pinocchio被提出的一同，有一些关于生成电路/算术化计划的计划，这些计划能够证明虚拟机对指令的履行成果正确。尽管为虚拟机开发算术化计划比为某些程序编写专用电路更杂乱或功率更低，但它却有一个重要优势：无论程序多杂乱，只需证明其在虚拟机中是正确履行的即可。
TinyRAM中的一些主意后来在Cairo虚拟机的设计中得到了改善，随后又有了zk-evm和通用zkvm等。在证明体系中运用抗磕碰的哈希函数消除了对可信设置或椭圆曲线操作的需求，但价值是证明时刻更长。
TinyRAM（2013）
在“SNARKs for C”中，他们依据PCP开发了一种证明体系，用于证明C语言编写的程序的履行成果正确。该程序被编译为TinyRAM，一种简化的VM。该VM具有字节级可寻址的随机存储器，电路巨细在核算规划上呈准线性增加，能够高效地处理循环、控制流和内存拜访等操作。
其间，PCP指Probabilistically Checkable Proof，即概率可查看证明，验证者只需阅览证明中随机挑选的一小部分内容，就能以很高的置信度查看证明的有用性。与验证者需求查看整个证明的传统证明体系不同，PCP只需有限的随机性即可完成高效验证。
Ligero（2017）
Ligero引进了一套证明体系，该体系可完成巨细为O(√￣n)的证明，其间n是电路的巨细。它以矩阵方法摆放多项式系数。Brakedown依据Ligero构建，并引进了范畴无关的多项式许诺计划的概念。
STARKs（2018）
STARKs（Scalable Transparent ARguments of Knowledge）由Eli Ben-Sasson等人于2018年提出。它们完成了?(log²?)的证明杂乱度，具有快速的验证速度，不需求可信设置，而且被推测为后量子安全。它们被Starkware/Starknet与Cairo虚拟机一同投入选用。其要害立异包括代数中心表明（AIR）和快速Reed-Solomon交互式Oracle挨近证明（FRI）协议。别的，STARKs也被许多闻名的区块链项目所运用（如Polygon Miden、RiscZero、Winterfell、Neptune以及ZeroSync、zkSync等）。
新的开展方向
不同的证明体系在实践运用中的运用展示了不同办法的优点，并推动了ZK的开展。例如，Plonkish的算术化计划供给了一种简单的办法，来包括自界说逻辑门和lookup arguments；FRI现已显示出作为PCS的超卓功能，促成了Plonky的诞生。一同，在AIR中运用grand-products查看（带来了预处理的随机化AIR）提高了其功能并简化了内存拜访参数。zk-STARK因为在生成功率上更好，且有越来越多的ZK友爱型哈希函数被引进，而越来越受欢迎。
新的多项式许诺计划（2023）
随着依据多变量多项式的高效SNARK（如Spartan或HyperPlonk）的呈现，人们对适用于此类多项式的新许诺计划的兴趣日益增加。Binius、Zeromorph和Basefold都提出了新的方法来许诺多线性多项式。Binius的优势在于表明数据类型时没有额外开支（而许多其他证明体系至少运用32位字段元从来表明单个位），而且在二进制域上工作。该许诺计划选用了为范畴无关而设计的brakedown。Basefold将FRI推行到除Reed-Solomon之外，从而完成了范畴无关的多项式许诺计划（PCS）。
范畴无关是多项式许诺计划的一个性质，指多项式许诺计划中，许诺过程不依赖于任何特定范畴的特定属性。这意味着能够对任何代数结构的多项式做出许诺，如有限域、椭圆曲线，甚至整数环。
可定制束缚体系（2023）
CCS泛化了R1CS，一同捕捉了R1CS、Plonkish和AIR的算术化，而没有额外开支。运用CCS与Spartan IOP结合能够发生SuperSpartan，它支持高维度束缚，而证明者无需承当与束缚阶数成份额的加密成本。特别地，SuperSpartan为AIR供给了一个具有线性时刻证明的SNARK。
总结
这篇文章综述了自上世纪80年代中期以来ZK技能的发展。核算机科学、数学和硬件的前进，加上区块链的引进，催生了新的、更高效的ZK证明体系呈现，为许多或许改变社会的运用开辟了路途。
研究人员和工程师们依据需求提出了ZK体系的改善计划，重点围绕在证明尺度巨细、内存运用程度、通明度、抗量子安全性、证明时刻和验证时刻等方面。尽管一直以来，ZK的干流完成计划有两大类（SNARK与STARKs），但这两者之间的边界现已逐渐模糊，不同证明体系的优势正被结合起来，例如结合不同的算术化计划与新的多项式许诺计划。
咱们能够预期，新的ZK证明体系将持续出现，且功能会不断提高。关于运用这些证明体系的运用来说，假如不能跟随最新技能的迭代开展，不断重构并运用最新的算法，现在的领先地位也只是暂时的。
原文链接：https://blog.lambdaclass.com/our-highly-subjective-view-on-the-history-of-zero-knowledge-proofs/
此时快讯
【昨日GBTC净流出7700万美元，ETHE净流出4170万美元】金色财经报道，据Farside Investors监测，截至发稿时，美国现货比特币ETF和现货以太坊ETF（8月9日）数据如下：
现货比特币ETF：GBTC净流出7700万美元；BITB净流出1810万美元；BTC净流入1560万美元。
现货以太坊ETF：ETHE净流出4170万美元；ETH净流入240万美元。
