作者：郭宇
引言我认为区块链很难说是一种“技术”。它更像是一个领域，包罗万象。或者，形而上学地说，区块链更像一个有机体，集成了各种理论和技术。
零知识证明是建立信任的重要技术，也是区块链不可或缺的一部分。
零知识证明是连接链上数据和链下计算的关键技术，也是保护链上数据隐私的重要方法。
解释“零知识证明”，首先需要解释“证明”，然后是什么是“知识”，最后是什么是“零知识”。
前世的‘证明’。什么是证明？很多人可能和我一样。看到这两个字，他们会不由自主地想到中学试卷上各种类似三角形的几何图形。当老师神奇的画了一条辅助线，证明过程就豁然开朗了，然后他们就会后悔为什么没想到。
古希腊：“证明”==“洞察力”
数学证明起源于古希腊。他们发明(发现)公理和逻辑，他们用证明来说服对方，而不是依靠权威。这完全是“去中心化”。从古希腊开始，这种方法论就影响了人类文明的整个进程。
上图是勾股定理的巧妙证明。历史上有过很多精致的证明，神奇的想法，天才的灵感。命题一旦被证明，上帝也无能为力。嗯，对了，还有“上帝不是万能的”的证明：上帝做不出自己举不起的石头。
一个数学证明往往隐藏着深刻的见解。相信很多人都看过费马大定理[1]的故事。这个定理的证明跨越了400年，从费马写下“这里的空间太小了，我写不下去了”到怀尔斯最后登顶，耗费了许多代人的聪明才智。最近如庞加莱猜想，有点时间感的哥德巴赫猜想，还有我很佩服的中国科学家张在仔细研究了Goldston-Pintz-YLDRM和Bombieri-弗里兰德-Iwaniec的证明后，证明了“素数之间的有界区间”。[
自17世纪莱布尼茨以来，人们一直梦想找到一种机械手段来自动完成证明，而不是依靠天才的灵感。
20世纪初：“证明”==“符号推理”
19世纪末，康托尔、布尔、弗雷格、希尔伯特、罗素、布劳伊、哥德尔等人定义了形式逻辑的符号系统。“证明”是用形式逻辑的符号语言写成的推理过程。逻辑本身可靠吗？逻辑本身是“自我正确”的吗？逻辑本身对吗？能证明吗？这使得数学家/逻辑学家/计算机科学家能够发明(发现)符号系统、语法对语义、可靠性对完整性、递归对无限。(这个精彩的故事请参考《逻辑的引擎》[3]一书)。
1910年，罗素出版了由祝安和窦所著的巨著《数学原理》。在书中，罗素和怀特海试图将数学完全形式化。如果能实现这样的目标，所有的数学成就都将以证明的形式建立在坚实的基础上。是下面《数学原理(第二册)》中的一页：
其中110.643这是一个命题：“1 1=2”，然后这个定理的证明就来了。你可能在想，你还需要证明1 1吗？是的，在数学原理书中，数字0，1，2，都是严格定义的，“加”、“乘”、“等于”都要严格定义，然后每一步的推理都需要指出依据。证明什么？证明可以很繁琐，但是每一步推理都是严格正确的。书中大量的证明都是机械的，一种证明是根据公理和推理规则构造的。找一个证明就好像可以给一个人，然后他没有大脑在那套公理和推理规则中机械地搜索。
看来人们离“定理自动证明”不远了。
可惜哥德尔在1931年证明了“哥德尔不完全性定理”[4]，图灵在1936年证明了图灵机关机的不确定性[5]。这些成就彻底终结了这个长达几个世纪的幻想。公理系统再精致，也不能把握所有的道理。
证明不仅是一种严格的推理，也是一种看似难以机械化的创造性思维的凝结。证明包含了很多“知识”，每一次突破都把我们的认知提升到一个新的高度。无论是推理过程中构建的“洞察力”还是“算法”，证明一个定理的内涵往往远远超出定理本身的结论。
60年代：“证明”==“程序”
半个世纪后的20世纪60年代，逻辑学家哈斯克尔库里(Haskell Curry)和威廉霍华德(William Howard)相继在《逻辑系统》和《计算系统——演算》中发现了许多“神奇的对应”，后来被命名为“库里-霍华德对应”。这个发现让我们恍然大悟，“写程序”和“写证明”其实在概念上是完全统一的。在接下来的50年里，相关理论和技术的发展使得证明不再停留在草稿纸上，而是可以用程序来表达。这个同构映射很有意思：程序的类型对应被证明的定理；循环对应归纳；……(这里推荐一本书：《软件基础》(软件基础的中译本)[6])。在直觉主义的框架下，证明就是构造一个算法，其实就是写代码。(反过来也是如此。嗯，不是编码农民的代码，是数学证明，P)
目前在计算机科学领域，很多理论证明已经从纸上的草图变成了代码。流行的“证明编程语言”有Coq、Isabelle、Agda等。证明是通过编程来构造的，证明的正确性可以由程序机械地检查，很多重复性的任务可以由程序来辅助。像计算机软件一样，被数学证明的大厦正在一步步建造。1996年12月，W. McCune利用自动定理证明工具EQP证明了一个已有63年历史的数学猜想“朗宾斯猜想”。《纽约时报》随后发表了一篇题为《显示推理能力的计算机数学证明》[7]的文章，再次讨论了机器能否取代人类创造性思维的可能性。
利用机器的辅助确实可以帮助数学家的思维到达更多未知的空间，但“寻找证明”仍然是最具挑战性的工作。“核查和认证”必须是一项简单、机械和有限的任务。这是天生的不对称。
80年代：“证明”==“互动”
1985年，乔布斯刚刚离开苹果，而S. Goldwasser博士毕业后去了麻省理工学院，与S. Micali和Rackoff一起写了一本可以载入计算机科学史册的经典：《交互式证明系统中的知识复杂性》[8]。
他们重新解释了“证明”一词，提出了交互证明系统的概念：通过构造两个图灵机进行“交互”而不是“推理”，可以证明一个命题在概率上是否成立。“证明”的概念又被扩大了。
交互证明的表述是两台(或多台)图灵机的“对话脚本”，或抄本。在这个对话过程中，有一个明确的“证明者”角色和一个明确的“验证者”。其中，证明者向验证者证明一个命题，同时“不透露任何其他知识”。这叫“零知识证明”。
还是那句话，证明凝结了“知识”，但证明过程并没有揭示“知识”。同时，证明验证过程仍然是简单的、机械的和有限的。这听起来是不是有点“反直觉”？
互动证明爱丽丝：我想向你证明我有一个方程的解，` w 3-(w 1) 27=0 `(方程的解：` w=3 `)
鲍勃：好的，我在听。
艾丽斯：但是我不会告诉你X到底是多少。除非你愿意付钱，否则我不会告诉你。
鲍勃：当然，但是在我给你钱之前，你必须证明你有这个方程的解。
爱丽丝：@ # $%(黑科技)
鲍勃：(黑科技)
爱丽丝：*#$@！(黑科技)
鲍勃：(黑科技)
.(续黑科技)
艾丽斯：好，就这样。
鲍勃：好吧，你确实有方程的解，但是如果我付钱，你会告诉我答案吗？
艾丽斯：废话少说，付钱吧！
上面的例子就是一个“互动证明”。假设爱丽丝知道方程的解，f(w)=0，爱丽丝如何让鲍勃相信她知道w？爱丽丝在“黑科技阶段”告诉了鲍勃很多信息。好了，关键问题是，Bob能从Alice说的大量信息中猜出W是什么吗，或者能分析出关于W的线索吗？如果Bob有这个能力，Bob可能不用付钱，因为他已经获得了这个有价值的信息。
请注意，如果爱丽丝和鲍勃的对话是“零知识”，那么鲍勃除了W是f(w)=0的解之外，得不到任何其他关于W的信息。这对于保护爱丽丝的利益非常重要。
现在回头看看“零知识证明”这个词，英文叫“零知识证明”。这个词包含三个关键部分：
零知识证明你可能已经有感觉了。我们来试着解读一下：
零：爱丽丝透露了关于W的“零”知识，即她没有透露任何知识。知识：这是指w .证明：是爱丽丝和鲍勃对话的“黑科技部分”。好了，证明就是黑科技部分还没提。别急，官员们，且听我慢慢道来。
零知识证明有什么用？提到零知识证明技术，很多人会想到匿名币，比如Monero和ZCash。的确，这些硬币把零知识证明普及得非常好，也正是通过ZCash，我第一次听到了零知识证明这个词。但是在对这项技术有了更深入的了解之后，我深深的感觉到这项技术的力量远不止于此。
零防技术可以解决数据和计算的信任问题！
张说自己有100块钱，李说自己北大毕业，王五说要和巴飞特一起吃午饭。空谈，拿出证据来。
那么如何理解“零知识证明”可以解决数据的信任问题呢？在上一篇文章《zkPoD:区块链，零知识证明和形式化验证，实现无中介、零信任的公平交易》[9]中，我提到了一个概念“仿真”:
零证明技术可以“模拟”第三方来保证某个断言是可信的。
换句话说，当我们接收到一个加密数据时，那么就存在一个零知识证明。这个零知识证明的意思是“关于数据的X断言成立”，那么这就相当于一个天使在我们耳边低语，“关于数据的X断言成立”！
对于这个X断言，可以非常灵活，可以是NP复杂的算法。一般来说，只要我们能写一个程序(一个多项式时间算法)来判断一个数据是否满足X断言，那么这个断言就可以用零知识证明的形式来表达。一般来说，只要数据判断是客观的，那么零知识证明是适用的。
零知识证明的一些用途：
数据的隐私保护：在一个数据表中，或多或少都有一些你不想暴露的信息，比如我的成绩单。我只是想向人证明我考上了，但我不想让别人知道我考了61分还是62分，那样会很尴尬。我没有心脏病，但是保险公司需要知道这个，但是我不想让保险公司知道我的私人信息。我可以向保险公司证明我没有心脏病，但是所有的病历都不需要曝光。我是企业，想向银行贷款。我只是想向银行证明我有健康的业务和还款能力，但我不想让银行知道我们的一些商业秘密。压缩和区块链扩展：在众多区块链扩展技术中，Vitalik采用的zkSNARK技术可以为现有以太坊框架带来数十倍的性能提升。因为计算的证明，不需要多次重复同样的计算。在传统的区块链架构中，同样的计算要重复很多次，比如签名验证、交易合法性验证、智能合约执行等等。这些计算过程可以通过零知识证明技术进行压缩。端到端的通信加密：用户可以互相发送消息，但不用担心服务器获取所有的消息记录。同时，消息可以根据服务器的要求显示相应的零知识证明，比如消息的来源和目的地。认证：用户可以向网站证明自己有私钥或者知道只有用户知道的秘密答案，但网站不需要知道。但是，网站可以通过验证这个零知识证明来确认用户的身份，从而分散存储：服务器可以向用户证明他们的数据被妥善保管，没有泄露数据的任何内容。信用记录：信用记录是另一个可以充分发挥零知识证明优势的领域。用户可以选择性地向对方展示自己的信用记录，一方面可以选择性地展示符合对方要求的记录分数，同时证明自己信用记录的真实性。构建一个完全公平的网上数字商品交易协议[9]。更多的例子可以是任何形式的数据共享、数据处理和数据传输。
比如：地图的三着色问题。先说一个经典问题，地图的三着色问题。如何用三种颜色染一张地图，保证任意两个相邻区域是不同的颜色？我们把这个“地图三着色问题”转化为“连通图的点三着色问题”。假设每个区域都有一个首都(节点)，然后把相邻的节点连接起来，这样地图着色问题就变成了连通图的顶点着色问题。
下面让我们设计一个交互协议：
“证明者”爱丽丝“验证者”BobAlice手里拿着一张地图三色答案。请看下图。这个图总共有6个顶点和9条边。
现在爱丽丝想向鲍勃证明她有答案，但她不想让鲍勃知道答案。爱丽丝打算做什么？
爱丽丝首先要在染好的画面上做一些“变换”，在颜色上做一个大的转移，比如把所有的绿色变成橙色，所有的蓝色变成绿色，所有的绿色变成橙色。然后爱丽丝得到了一个新的着色答案。这时，她用一张纸盖住新图形的每个顶点，并给鲍勃看。
看下图。这时候Bob要出手了(请看下图)。他必须随机选择一方。注意是随机的，不允许爱丽丝提前预测随机数。
假设鲍勃选择底边，然后告诉爱丽丝。
这时，爱丽丝揭开了这一面两端的纸片，让鲍勃检查。鲍勃发现这两个顶点的颜色不同，于是鲍勃认为这个测试是同构的。这时，鲍勃只看到了图表的一部分。他能确信图的剩余顶点的着色是正确的吗？你一定认为这远远不够。也许爱丽丝只是猜对了？其他未暴露的顶点可能被随机染色。
没关系，鲍勃可以让爱丽丝再做一遍。看下图。
爱丽丝又换了颜色，把蓝色换成紫色，绿色换成棕色，橙色换成灰色，然后把所有的顶点都用纸盖住。然后鲍勃选择了另一条边。比如像上图，他选了一个竖边，然后让爱丽丝揭开那张纸看一看。如果这时候鲍勃又发现这条边两端的顶点颜色不一样，那么这时候鲍勃已经有点动摇了。也许爱丽丝真的有这个染色答案。然而，两次还是不够，鲍勃想再做一次。
那么在反复重复这三个步骤后，爱丽丝能够出轨并成功忽悠鲍勃的概率就会成倍下降。假设n回合后，爱丽丝作弊的概率是
这里|E|是图中所有边的数目。如果n足够大，这个概率Pr就会变得非常非常小，“无足轻重”。
然而鲍勃每次看到当地的染色情况，都是爱丽丝改造的结果。鲍勃再怎么看，也拼不出一个完整的三重染答案。实际上，鲍勃在这个过程中获得了很多“信息”，但他并没有获得真正的“知识”。
Vs .知识信息“信息”知识“在地图3着色问题的交互证明中，经过多次反复交互，鲍勃得到了很多信息，但这就像爱丽丝给鲍勃发了一堆随机数一样，鲍勃并没有“知道”更多的东西。例如，如果Alice告诉Bob“11=2”，Bob得到了这个信息，但是Bob没有得到更多的“知识”，因为这个事实是众所周知的。
如果Alice告诉Bob数字2 2 41-1是一个质数，很明显这是“知识”，因为要算出这个数字是不是质数需要很大的计算能力。
如果爱丽丝告诉鲍勃有两个顶点是绿色的，那么鲍勃将获得有价值的“知识”，因为基于他刚刚获得的信息，鲍勃可以使用图灵机在更短的时间内解决三色问题。如果爱丽丝向鲍勃透露最左边顶点的颜色是橙色，那么显然，这个“信息”并没有帮助鲍勃解决问题。
我们可以尝试定义，如果鲍勃在交互过程中获得的“信息”能够帮助提高鲍勃直接破解爱丽丝秘密的能力，那么我们就说鲍勃“获得了知识”。因此，知识这个词的定义与鲍勃的计算能力有关。如果信息不能增加鲍勃的计算能力，那么信息就不能称为“知识”。比如在爱丽丝和鲍勃互动的过程中，爱丽丝每次都会扔一个硬币，然后把结果告诉鲍勃。从信息的角度来看，鲍勃获得的信息只是一个“事件”，而鲍勃并没有获得任何“知识”，因为鲍勃可以自己抛硬币。
下面引用《密码学基础3354基本工具》[10]一书中的摘要。
1.知识与计算难度有关，信息则无关。2.知识与公众已知的东西有关，而信息主要与部分公开的东西有关。
注：曾经有人问我，这里的信息和知识的定义是否与Kolmogorov复杂度有关。根据算法信息论，一个字符串的信息量可以用生成该字符串的最小程序的长度来衡量。这个问题我不太明白。希望路过的专业人士留言。
可验证计算和电路可满足性问题。看了上面图中的三个着色问题，有没有觉得这只是一个学术问题？怎么能和现实问题扯上关系呢？地图的三色问题是一个NP完全问题，是“计算理论”中的一个术语。另一个问题叫做“电路可满足性问题”，也是一个NP完全问题。NP-Complete是一类问题，其求解过程很难在多项式时间内完成，即“难解”，但验证解的过程可以在多项式时间内完成，即“简单验证”。
什么是电路？以下是三种不同的“运算电路”:
可以看出，一个电路由许多门组成，包括加法门和乘法门。每个门有几个输入引脚和几个输出引脚。每个门做加法或乘法。别看这么简单，我们平时运行的所有代码(没有无限循环)都可以用算术电路来表示。
这是什么意思？下面结合“零知识证明”和“电路可满足性问题”来尝试解决数据隐私保护问题。
请考虑以下场景：Bob给Alice一段代码P，和一个输入X，让Alice再运行一次，然后把运行结果告诉Bob。可能这个计算需要消耗资源，Bob把计算过程外包给了Alice。然后Alice又运行了一次，得到的结果是y，然后告诉Bob y，问题来了：
如何在不运行代码的情况下，让Bob相信代码P运行的结果一定是Y？
这是思考的时间。你可以思考五分钟.
(五分钟后.)
爱丽丝的方法之一是用手机拍下整个计算过程。这个视频包含了电脑的CPU和内存，以及整个运算过程中各个晶体管的状态。显然，这样做是不现实的。那么有没有更可行的方案呢？
答案是Bob把程序P转换成完全等价的算术电路，然后把电路交给Alice。爱丽丝只需要计算这个电路，然后这个过程就可以用手机拍下来，或者写在纸上，如果电路规模没有那么大的话。Alice只是将参数6输入到电路中，然后在电路运行过程中记录所有连接到门的管脚上的值。并且最后一个电路的输出引脚的值等于Y，那么Bob可以确定Alice进行了计算。爱丽丝需要把电路所有门的输入输出写在一张纸上，交给鲍勃。本文是计算证明。
这样，鲍勃就可以完全验证这张纸上的证明是否正确，而不需要重复计算电路。验证过程非常简单：
鲍勃依次检查每个门的输入和输出是否能满足一个加法方程或一个乘法方程。
比如门1是加法门，它的两个输入是3，4，输出是7，那么很容易知道这个门的计算是正确的。当Bob检查了所有的门后，他可以确定：
爱丽丝做了计算，没有作弊。
这篇论文的内容是运算电路“p”的一种解法。
所谓电路可满足性，是指存在满足电路的解。如果这个解的输出值等于某个值，那么这个解就可以“代表”电路的计算过程。
就爱丽丝而言，如果鲍勃这样验证，她就没有作弊的余地了。但是这种方法显然有一个缺点：
缺点一：电路大，那么证明就大，Bob检查证明的工作量也大。缺点：Bob在验证过程中知道电路操作的所有细节，包括输入。未来科技
让我们对刚才爱丽丝和鲍勃的场景做些改变。假设爱丽丝有自己的秘密，比如网银密码。Bob想知道Alice的网上银行密码是否为20位。而爱丽丝想了一下，告诉他密码长度应该问题不大。这时，鲍勃把一个计算字符串长度的代码转换成一个电路Q并发送给爱丽丝。爱丽丝用电路Q算出了自己的密码，然后把电路所有门的管脚和运算结果20一起发给鲍勃。
瓦伊.t这是有问题的。鲍勃在得到所有电路操作的内部细节后，不知道密码吗？是的，爱丽丝显然做不到。那么爱丽丝应该怎么做呢？
答案是有很多方法。热爱区块链技术的读者最熟悉的是zkSNARK[11]、zkSTARK[12]、防弹[13]以及一些相对小众的技术，可以帮助爱丽丝做：
Alice以一种零知识的方式向Bob证明，她已经计算了电路，并且使用了她的秘密输入。
换句话说，这些“零知识电路可满足性证明协议”为Alice提供了一个有力的武器，向Bob证明她的网银密码长度为20，除此之外，Bob再也得不到任何其他有用的信息。除了网银密码，爱丽丝理论上可以向鲍勃证明她的任何私人数据的某些特征，但不暴露任何其他信息。
“零知识电路可满足性证明协议”提供了保护隐私/敏感数据的最直接的技术。
近年来，零知识证明的构造技术发展迅速，在区块链技术领域得到越来越多的应用。最新的零知识证明技术，其中一些可以让Bob高速验证证明(在移动设备上毫秒级完成验证)；有些技术可以让所有吃瓜人帮忙验证(非交互零知识证明)；一些技术支持非常小的证明大小(小到几十个字节)。后续文章我们会逐步介绍。
最后无论是巧妙的数论定理，还是地图的三着色问题，还是回路可满足性问题。存在证明的意义是什么？所有的证明都表现出“证明”和“验证”的不对称。证明可能是一个非常计算或精神密集的活动。无论是耗时数百年的费马大定理，还是比特币中的POW证明，这些证明都凝聚了寻找证明过程中所消耗的能量。证明的过程可能会格外复杂，偶尔需要诞生一个天才。并且验证过程必须(或者应该)是非常简单的机械活动，可以在(多项式)有效时间内终止。从某种意义上说，这种不对称确实体现了证明的意义，显示了零知识证明的价值。
粗略地说，证明是逻辑的产物，但逻辑和计算是密切相关的。你可能隐约感觉到证明和计算的关系，贯穿始终，比如机械推理，证明表达，交互计算。这是一个有趣但更大的哲学问题。
提醒：文章内容难免不准确或不严谨。请花时间改正它。
参考文献[1]西蒙，歌手，米雪。费马大定理：一个困扰世界智者358年的谜[M]。上海译文出版社，1998年。
[2]亚历克威尔金森。张一堂解决了一个纯数学之谜。《纽约客》。2015年2月。
[3]马丁，戴维斯，张。逻辑的引擎[M]。湖南科学技术出版社，2012。
[4]雷蒙德斯穆利安。哥德尔的不完全性定理，牛津大学出版社，1991年。
[5]图灵，艾伦。可计算的数字，以及对Entscheidungsproblem的应用。伦敦数学学会会议录2.1 (1937): 230-265。
[6] Pierce，Benjamin C .等人，“软件基础”中文翻译：https://github.com/Coq-zh/SF-zh
[7]科拉塔，吉娜。计算机数学证明显示了推理能力。数学地平线4.3 (1997): 22-25。
[8]戈德瓦瑟、沙菲、希尔维奥米卡利和查理斯拉科夫。交互式证明系统的知识复杂性。SIAM计算机杂志18.1 (1989): 186-208。
[9] zkPoD:区块链，零知识证明和形式化验证，实现无中介、零信任的公平交易。安比实验室。2019.
[10]奥德，德意志帝国。密码学基础基本工具。(2001).
[11] Gennaro，Rosario等人，“二次跨度程序和无PCP的简洁NIZKs”年刊
密码技术理论与应用国际会议。施普林格柏林，海德堡，2013。
[12] Ben-Sasson，Eli等人，“可扩展、透明和后量子安全计算完整性”IACR密码学ePrint档案2018 (2018): 46。
[13] Bnz，Benedikt等，“Bulletproofs:机密交易的简短证明及其他”2018 IEEE安全与隐私研讨会(SP)。IEEE，2018。
(作者：SECBIT Lab，其内容来自开放内容平台“GetNo。”的链条；本文仅代表作者观点，不代表链家官方立场)
