原文标题：《零知识证明最简介绍：历史、原理、实现》
密码学可以说是区块链技术的基石，而其中的零知识证明更是因为深度契合区块链的技术特点，而得到了广泛的应用和关注。
本文旨在用最简单的语言和形式，向大家介绍零知识证明相关的历史、概念、原理、技术实现以及发展现状。
那么让我们开始吧。
历史和起源
密码学是一门可以追溯到2000多年前的古老学问，其发展历史主要可以划分为以下几个阶段：
古典密码学
这一时期的密码学主要被应用于军事领域，如何有效的传递密文，又能防止被敌人截获后破解，是其主要考量。16世纪由法国人发明的「维吉尼亚密码」是古典密码理论发展上的一个重要里程碑，它使用一个词组作为密钥，词组中每一个字母都将确定一个替换表，「维吉尼亚密码」循环的使用每一个替换表完成明文字母到密文字母的变化。
明文：ilovebitcoin
密钥：satoshi
对于第一个字母i，取第i行第s列，得到A；第二个字母l，取第l行第a列，得到L…依次循环，最后得到密文：ALHJWIQLCHWF。可见，在不知道密钥的前提下，不借助计算机已经非常难以破解这样的密码。
近代密码学
这一阶段真正的开始源于香农在20世纪40年代末发表的一系列论文，特别是1949年的「CommunicationTheoryofSecrecySystems」，把已有数千年历史的密码学推向了基于信息论的科学轨道，密码学终于从艺术转向科学。
这一时期的重要突破是DES的出现，直至今日也只能用穷举法对其进行破解。DES加密算法风行世界，并在金融等商业领域得到了广泛的应用。
现代密码学
1977年，麻省理工学院的RonRivest、AdiShamir、LeonardAdleman提出的非对称加密算法RSA，有效的解决了密钥传送的问题，标志着密码学进入了百家争鸣的现代阶段。
1989年，由麻省理工学院研究人员Goldwasser、Micali及Rackoff提出了「零知识证明」的概念，当时的他们一定不曾想到，若干年后出现的区块链技术彻底激活了零知识证明的应用，而零知识证明则为区块链技术提供了一种绝佳的解决方案。零知识证明的方法特点和区块链技术的系统特点达成了完美的契合。
零知识证明及zkSNARK
零知识证明是指，在不揭晓我所知道或拥有的某样东西的前提下，向别人证明我有很大概率确实知道或拥有这样东西。
zkSNARK则是在区块链中应用最广泛的一种零知识证明，其全称是「zero-knowledgeSuccinctNon-InteractiveArgumentsofKnowledge」。
光听定义，大家一定一头雾水，本节将借用一个例子，尽可能接地气的向大家介绍这两个概念。
Alice、Bob和Charlie都是数独爱好者，所谓数独是这样一种游戏，玩家需要根据9×9盘面上的已知数字，推理出所有剩余空格的数字，并满足每一行、每一列、每一个粗线宫的数字均含1到9，且不重复。
有一天Alice设计了一道巨难的数独题目来考Bob和Charlie，Bob苦思冥想了几天也做不出，便向Alice抱怨这肯定是道无解的题目。Alice不想将实际的解告诉Bob，但是又需要证明她确实知道解，于是她设计了一种巧妙的「零知识证明」的方式。
证明（TheProof)
Alice拿出81张空白的卡片，并在每张纸上写上1-9中的一个数字，接着她将代表谜面的卡片数字面朝上、代表谜底的卡片数字面朝下都放在桌上，并组成了9x9的矩阵。
随机挑战
接下来怎么让Bob确认这就是正确的解呢？很简单，由Bob随机选择行、列或是粗线宫中的一种进行验证，假如选择行，则将这81张卡片按9行分别放到9个麻布袋中，摇匀并确保卡片次序打乱。
验证
简洁
虽然数独游戏有3种情况需要验证，但每次验证时Bob实际只需要验证其中的一种，这有效减少了验证工作量，提供给验证者的实际是一个比原命题小的多的证明，这就是所谓的简洁。
重复
之后重复这个随机验证步骤，我们假设Alice运气很好，每次都能提前猜中Bob会选择哪种验证方式，并以此来模拟一个解，那么她通过1次验证的概率为1/3，通过2次验证的概率为1/9，通过10次验证概率就只有1/59049了。在不厌其烦的进行了20次验证之后，Bob无奈的承认，Alice是真的知道这个答案的解，因为Alice凭运气通过验证的概率只有35亿分之一！
模拟
这个时候，Charlie也来向Alice抱怨这个题目的无解，Alice和Bob又重复了刚才的证明，没想到却没有得到Charlie的认可。Charlie提出了这个证明中的漏洞，如果Bob和Alice是一伙的，每次Bob都会提前告诉Alice他要选择的验证方式，那么Alice就可以很容易的在没有解的情况下模拟出一个证明来通过这些测试。
非交互式证明
不可能让每个持有这种怀疑的人都重复一遍Bob进行的随机验证，于是三个小伙伴设计了一台神奇的机器，Alice只需要提交一次卡片，这台机器就可以按照初始设置好的验证序列，自动化的对这些卡片进行重复验证。验证从交互式的，变成了非交互式的。这里我们要注意，并不是说非交互式证明就没有重复随机实验这个过程。实际上，只不过是随机点不由验证者给出，而是由一个可信的第三方在初始化阶段就给出，这样一来，证明者就可以直接给出证明，验证者只需要验证证明即可，验证者和证明者之间不再需要交互。
可信设置仪式
其中最有趣也最重要的环节就是验证序列的初始设置。在机器启动前，会有一排设置旋钮，通过这些旋钮可以选定每一轮的验证方式。在设置这些旋钮时，每个人依次进入放置机器的房间，选择一个旋钮并设置好，之后就用一个铁盒子彻底焊死这个旋钮，让其他人无法看见也无法改变这个旋钮的选择。为了让初始设置尽可能的可信，小伙伴们邀请了镇长、小学校长和警察局长这三位小镇上最德高望重的长者来参加设置仪式，大家都相信他们绝对不可能参与作假，因此他们称之为「可信任的初始设置仪式」。
一台数独游戏的简洁非交互式零知识证明机，诞生了！
zkSNARK的技术实现
通过上一节我们已经弄明白了零知识证明和zkSNARK的基本概念和原理，这一节我们再来一窥zkSNARK的技术实现。可以说整个实现过程相当的繁琐晦涩，且需要一定的背景知识，因此本小节只力图讲清楚其核心思想，而不拘泥于过分复杂的数学推导。
我们从一个方程式开始，X^3+X+5=35，显然解是3。那么现在，证明者如何向验证者证明自己知道方程的解是3，而又不告诉验证者这个解呢？
首先，我们将方程转化为计算机语言，这很容易实现：
y=x*3returnx+y+5
接着，我们将上面的代码拍平。所谓将代码拍平，是指让代码一次只做一件事，形如x=yopz。
拍平后，代码变成以下语句：
sym_1=x*xy=sym_1*xsym_2=y+x~out=sym2+5
然后，我们引入R1CS一阶约束系统，R1CS是一个由三向量组组成的序列，同时有一个解向量s，s满足s·a*s·b-s·c=0。
在本例中，s的结构为，可见其由一个特殊的~one、方程的解x、方程的输出~out和一系列中间变量构成，其顺序不重要，只要保证有序即可。
我们把语句变换成如下形式，来方便我们求解abc：
x*x-sym_1=0sym_1*x-y=0y+x-sym_2=0sym_2+5-~out=0
我们很容易得出第一个式子对应的三个向量：
a=b=c=
推导过程其实很简单，我们知道要满足s·a*s·b-s·c=0，那么对应第一个式子x*x-sym_1=0，只需要s·a=x、s·b=x、s·c=sym_1即可，而s=，那么a只要在x的位置等于1，其余位置等于0，即得出。
大家可能对上面一系列眼花缭乱的变换感到莫名其妙，我们究竟在做什么？这里要揭晓谜底了，我们对每个式子验证s·a*s·b-s·c=0，其本质是在验证每一步都得到了正确的计算，也即如果我们可以验证每一步都是正确的，那么最终结果也一定是正确的。
以上的每一步，看似都在舍近求远，因为s里本身就包含了方程的解x，验证者只需把x代入就能进行验证。但从另一个角度看，通过这一系列的转换，我们构建了一种将证明和验证分离的方式。在证明过程中，证明者需要知道解并生成一系列中间结果，而验证者则只需要验证其一系列结果构成的解向量是否满足一系列约束，而不需要关心这个解到底是多少。
现在只剩一个问题留待解决，就是能否通过一种方式，让验证者看不到裸着的解x，同时依然可以进行验证过程。答案是肯定的，借由椭圆曲线、双线性对运算和指数知识假设这一系列数学手段我们就可以做到这一点，因为其推导过程过于复杂，本文不做赘述。整个zkSNARK的技术实现流程参见下图，需要了解更多细节的同学可以阅读参考资料中给出的Vitalik的文章。
零知识证明发展现状
零知识证明协议
零知识证明目前有如下几种协议，每个协议代表一条实现零知识证明的道路，不同道路最后会产生不一样的效果。
其中，安全性最高的是STARKs算法，其不依赖数学难题假设，具有抗量子性，并实现了透明通用字符串；Proofsize最小的snarks协议是groth16算法；Plonk是SNARK协议中的一个算法，Proofsize和安全性处于适中状态。
SNARKs协议算法
作为区块链技术中应用最广泛的SNARKs，已经发展出了诸多各具特点的协议算法：
Groth16：Groth16是目前最快、数据量最小的zk-SNARK，被用于Zcash等。Groth16的CRS不是通用的，其设置需要绑定到一个特定的电路。由于其速度和证明的小数据量，因此常常被新的zk-SNARK拿来比较性能。
Groth16论文链接
Sonic：Sonic是一种早期的通用zk-SNARK协议，支持通用、可升级的参考字符串，论文发表于2019年1月。Sonic的证明大小固定，但是验证成本高，理论上可以将多个证明分批验证以获得更好的性能。下面列举的许多新的zk-SNARK都是基于Sonic。
Sonic论文链接
Fractal：Fractal是一种允许递归的zk-SNARK。通过对电路的预处理实现了透明设置。证明最大250KB，这比其他构建生成的证明都要大的多。
Fractal论文链接
Halo：Halo支持递归证据组织，无需可信设置，与其他新的zk-SNARK构建不同，Halo的验证时间是线性的。
Halo论文链接
SuperSonic：Sonic的改进版，是第一个在验证时间和证明数据量方面实用化的透明zk-SNARK。
SuperSonic论文链接
Marlin：Sonic的改进版，证明时间缩短10倍，验证时间缩短4倍。
Marlin论文链接
Plonk：Sonic的改进版，证明时间缩短5倍。
Plonk论文链接
硬件成本
当前零知识证明缺乏专用硬件，导致硬件成本偏高，租用云服务器满负荷下成本约为0.002元/笔，有空载情况下约为0.02元/笔。Vitalik曾提出一个设想，当以太坊共识机制改为PoS，不需要那么多挖矿硬件后，这些算力可以经改造后转向支持零知识证明，这可能有效降低零知识证明的运行成本。
写在最后
如今，零知识证明已经在区块链领域大放异彩，包括第一个实现zkSNARK的匿名加密货币Zcash、Layer2的主要解决方案zkRollup等等。
DeGate团队也将在产品实现中大量应用零知识证明，藉由其强大特性，我们将Orderbook的撮合交易转到MatchNode中进行，使用户可以实时的挂单、撤单和成交，且其中挂单撤单免费；之后再将订单批量结果生成证明，传回Layer2上进行验证，这让DeGate在继承以太坊安全性的同时，既可以隐藏下单关键信息又可以有效降低Layer2上的Gas费消耗。而我们的最终目标是，无论在操作体验上，还是手续费消耗上，都使DeGate达到媲美中心化交易所的水平。
郑重声明： 本文版权归原作者所有， 转载文章仅为传播更多信息之目的， 如作者信息标记有误， 请第一时间联系我们修改或删除， 多谢。