区块链简介 | 探索零知识证明系列（一）：初识“零知识”与“证明”

简介 我认为区块链算不上是一种“技术”。 它更像是一个领域，包罗万象。 或者从形而上的角度来说，区块链更像是一个有机体，融合了各种理论技术。

零知识证明是建立信任的重要技术，是区块链有机体不可或缺的组成部分。

零知识证明是连接链上数据和链下计算的关键技术，也是实现链上数据隐私保护的重要途径

要解释“零知识证明”，我们需要先解释“证明”，再解释什么是“知识”，最后再解释什么是“零知识”。

《证明》前世今生什么是证明？ 很多人可能和我一样。 看到这两个字，他们不禁会想到中学试卷上各种类似三角形的几何图形。 当老师神奇地画出一条辅助线时，证明过程顿时一目了然，然后后悔自己怎么没想到。 古希腊：“证明”==“洞察力” 数学证明起源于古希腊。 他们发明（发现）了公理和逻辑，他们通过证据而不是权威说服了对方。 这是彻头彻尾的“权力下放”。 自古希腊以来零知识证明 比特币，这种方法论就影响了整个人类文明进程。

上图是“勾股定理”的巧妙证明。 历史上出现过许多巧妙的证明、神奇的想法、天才的灵感。 一个命题一旦被证明，神就无能为力了。 嗯，顺便说一句，还有“上帝不是万能的”证明：上帝无法创造出他搬不动的石头。

一个数学证明往往隐藏着极为深刻的“见解”。 相信很多人都看过《费马大定理》的故事[1]。 我写不下来”，几代人的匠心才让怀尔斯登上了顶峰。最近，比如“庞加莱猜想”，有点年代感的“哥德巴赫猜想”，华裔科学家张我很敬佩的伊唐，经过十年的努力，在认真研究了“Goldston-Pintz-Yıldırım”和“Bombieri-Friedlander-Iwaniec”的证明“洞察力”之后，证明了“素数之间的有界区间” ” [2]。

从十七世纪的莱布尼茨开始，人们就梦想找到一种机械的方法来自动完成证明，而不是依靠灵光一现。

二十世纪初：“证明”==“符号推理” 十九世纪末，康托尔、布尔、弗雷格、希尔伯特、罗素、布劳、哥德尔等人定义了形式逻辑符号系统。 而“证明”就是用形式逻辑的符号语言写成的推理过程。 逻辑本身合理吗？ 逻辑本身是“自洽的”吗？ 逻辑推理本身是否正确？ 可以证明吗？ 这导致数学家/逻辑学家/计算机科学家发明（发现）符号系统、句法与语义、可靠与完整、递归与无限。 （这部分精彩故事请参考《逻辑引擎》一书[3]）。

1910年，罗素出版了洪（zhuan）黄（tou）的巨著《数学原理》。 在书中，罗素和怀特海试图将数学完全“形式化”。 如果能够实现这样的目标，所有的数学结果都将以经过验证的方式建立在坚实的基础上。 下图是《数学原理（第2卷）》中的一页：

其中，110.643是一个命题：“1+1=2”，然后就是这个定理的证明。 你可能想知道，1+1还需要证明吗？ 是的，在数学原理这本书里，数字0、1、2、……是有严格定义的，“加法”、“乘法”、“等于”也必须严格定义，然后每一步推理都需要需要指出的是。 证据是什么意思？ 证明可能极其繁琐，但每一步推理都是严谨而正确的。 书中大量校样是机械的。 根据公理和推理规则，进行了一种证明构造。 找证明就好像交给一个人，然后他不假思索地机械地在公理和推理规则的集合中寻找。

看来，人们离“自动定理证明”已经不远了。

不幸的是，哥德尔在1931年证明了“哥德尔不完备性定理”[4]，图灵在1936年证明了图灵机停机问题的不可判定性[5]。 这些结果结束了这个有着数百年历史的幻想。 无论公理系统设计得多么巧妙，它都无法捕捉到所有的真理。

证明不仅仅是严密的推理，而是凝聚了看似难以机械化的创造性思维。 证明中蕴含着大量的“知识”，每一次突破都将我们的认知提升到一个新的高度。 无论是在推理过程中构建的“见解”还是“算法”，定理证明的内涵往往远远超出定理结论本身。

1960 年代：“证明”==“程序”

半个世纪后，在1960年代，逻辑学家Haskell Curry和William Howard相继在“逻辑系统”和“计算系统——Lambda演算”中发现了许多“神奇对应”，后来被命名为“Curry-Howard Correspondence”。 这个发现让大家恍然大悟，“写程序”和“写证明”其实在概念上是完全统一的。 此后50年，相关理论和技术的发展，使得证明不再停留在草稿纸上，而可以用程序来表达。 这个同构映射很有意思：程序的类型对应于证明的定理； 周期对应归纳； ...（这里推荐一本书：《软件基础》（Software Foundations 中文译本）[6]）。 在直觉主义框架中，证明就是构造算法，而构造算法实际上就是写代码。 （反之亦然，嗯，编码器编码的不是代码，而是数学证明，:P）

目前，在计算机科学领域，许多理论的证明已经从纸上草图转变为代码形式。 比较流行的“证明编程语言”包括 Coq、Isabelle、Agda 等。 使用编程构造证明，证明的正确性检查可以由程序机械地完成，许多重复性劳动可以由程序辅助完成。 与计算机软件一样，数学理论的证明大厦也在一步步建造。 1996年12月，W. McCune用自动定理证明工具EQP证明了一个有63年历史的数学猜想“罗宾斯猜想”。 《纽约时报》随后发表了一篇题为《计算机数学证明显示推理能力》的文章[7]，再次讨论了机器能否取代人类创造性思维的可能性。

使用机器辅助确实可以有效帮助数学家的思维触及更多未知空间，但“寻找证明”仍然是最具挑战性的工作。 “验证证明”必须是一项简单、机械和有限的任务。 这是一种天然的“不对称”。

1980 年代：“证明”==“互动”

1985年，乔布斯刚刚离开苹果，S. Goldwasser博士毕业后来到麻省理工学院，与S. Micali和Rackoff合写了一部可以载入计算机科学史册的经典之作：“The knowledge in the interactive证明系统复杂性”[8]。

他们重新诠释了“证明”一词，提出了交互式证明系统的概念：通过构造两台图灵机进行“交互”而不是“推理”，来证明一个命题在概率上是否为真。 “证明”的概念又被扩大了。

交互式证明的形式是两个（或多个图灵机）“对话脚本”，或 Transcript。 并且在这个对话过程中，有一个明确的“验证者”角色和一个明确的“验证者”。 其中，证明者向验证者证明一个命题成立，同时“不公开任何其他知识”。 这称为“零知识证明”。

上面的例子是一个“交互式证明”。 假设 Alice 知道方程的解 f(w) = 0，Alice 如何让 Bob 相信她知道 w？ 爱丽丝在“黑科技阶段”告诉了鲍勃很多信息。 那么，关键问题是，Bob能否从Alice所说的大量信息中猜出w是什么，或者他能否分析出关于w的线索呢？ 如果 Bob 有这个能力，Bob 可能不需要支付，因为他已经获得了这个有价值的信息。

请注意，如果 Alice 和 Bob 之间的对话是“零知识”，那么 Bob 除了 w 是 f(w)=0 的解之外无法获得关于 w 的任何其他信息。 这很重要，它符合爱丽丝的利益。

现在复习一下“Zero-Knowledge Proof”这个词，英文叫做“Zero-Knowledge Proof”。 这个词有三个关键部分： 你可能已经对它有了感觉，那么让我们试着破译一下：

零知识证明有什么用？ 提到零知识证明技术，很多人都会想到匿名币，比如Monero，比如ZCash。 事实上，这些硬币很好地普及了零知识证明。 我自己是通过 ZCash 第一次听说零知识证明这个词的。 但是在对这项技术有了更深入的了解之后，我深深地感受到这项技术的强大远不止于此。

零知识证明技术可以解决数据和计算的信任问题！

张三说自己有100块钱，李斯说自己是北大毕业的，王舞说要和巴菲特一起吃午饭。 空话无凭，拿证据来。

那么“零知识证明”如何解决数据信任呢？ 在之前的文章《zkPoD：区块链、零知识证明和形式化验证，实现无中介、零信任的公平交易》[9]中，提到了一个概念“模拟”：

零知识证明技术可以“模拟”第三方来保证某个断言是可信的

换句话说，当我们收到一个加密数据时，就有了一个零知识证明。 这个零知识证明说“关于数据的X断言是真的”，那么这就相当于天使在我们耳边低语，“关于数据的X断言是真的”！

对于这个X断言，可以很灵活，可以是NP复杂度算法。 用大白话来说，只要我们能写一个程序（多项式时间算法）来判断一个数据是否满足X断言，那么这个断言就可以用零知识证明来表达。 通俗地说，只要数据判断是客观的，那么零知识证明是适用的。

零知识证明的一些用途：

示例：地图三重着色问题

先说一个经典的问题，地图的三色问题。 如何用三种颜色给地图上色，使任意两个相邻区域的颜色不同。 我们将这个“地图三色问题”转化为“连通图顶点三色问题”。 假设每个区域都有一个首都（节点），然后连接相邻的节点，这样地图着色问题就可以转化为连通图顶点着色问题。

让我们设计一个交互协议：

“证明人”爱丽丝

“验证者”鲍勃

爱丽丝手中有地图的三种颜色的答案，见下图。 该图共有 6 个顶点和 9 条边。

现在爱丽丝想向鲍勃证明她有答案，但她不想让鲍勃知道答案。 爱丽丝要做什么？

Alice首先需要对染色后的图像进行一些“变换”，在颜色上做一个大的转变，比如把所有的绿色变成橙色，把所有的蓝色变成绿色，把所有的绿色变成橙色。 然后爱丽丝得到了一个新的着色答案。 这时，她用一张纸把新图的每个顶点都盖住，然后拿给鲍勃看。

看下面的图片。 这时，Bob 正要出手（见下图）。 他想随机选择一个“边”。 注意是随机的，Alice不会让提前预测的随机数。

假设 Bob 选择底边并告诉 Alice。

这时，爱丽丝揭开这条边两端的纸片，让鲍勃检查。 Bob 发现两个顶点的颜色不同，所以 Bob 认为这个测试是同构的。 此时Bob只看到了图的一部分，他能确信图其余部分的顶点着色没问题吗？ 你一定觉得这还不够，也许爱丽丝刚刚猜对了？ 其他未暴露的顶点可能会随机着色。

没关系，Bob可以让Alice再做一次，见下图

爱丽丝再次改变颜色，将蓝色变为紫色，将绿色变为棕色，将橙色变为灰色，然后用纸覆盖所有顶点。 然后Bob又选了一条边，比如上图，他选了一条垂直的边，然后让Alice把纸揭开看看。 如果 Bob 发现这条边的两端的顶点有不同的颜色，那么 Bob 就会 Time 犹豫了一下，也许 Alice 真的有这个着色的答案。 但是，两次还是不够，Bob 还想多做几次。

那么这三个步骤重复多次后，爱丽丝可以作弊并成功骗过鲍勃的概率将呈指数下降。假设经过n轮后，爱丽丝作弊的概率为

这里|E| 是图中所有边的数量。 如果n足够大，这个概率Pr就会变得非常非常小，变得“微不足道”。

但是，Bob 每次看到的局部着色都是 Alice 变换的结果。 无论鲍勃看多少次，他都无法拼出一个完整的三色答案。 事实上，虽然鲍勃在这个过程中获得了很多“信息”，但他并没有获得真正的“知识”。 Information vs. Knowledge 在地图三色问题的交互证明中，经过多次重复交互，Bob 得到了很多信息，但这就像 Alice 给 Bob 发了一堆随机数，Bob 并不“知道”更多的信息事物。 例如，如果爱丽丝告诉鲍勃“1+1=2”，鲍勃得到了这个信息，但鲍勃并没有得到更多的“知识”，因为每个人都知道这个事实。

如果爱丽丝告诉鲍勃这个数 2^2^41-1 是一个素数，显然这是“知识”，因为要计算出这个数是否是素数需要大量的计算能力。

如果爱丽丝告诉鲍勃一共有两个顶点是绿色的，那么鲍勃就获得了宝贵的“知识”，因为根据他刚刚获得的信息，鲍勃可以用图灵机在更短的时间内解决这三个顶点。 染色问题。 如果 Alice 向 Bob 揭示最左边顶点的颜色是橙色，那么显然，这个“信息”并不能实质性地帮助 Bob 解决问题。

我们可以尝试定义，如果Bob在交互过程中获得的“信息”能够帮助提高Bob直接破解Alice秘密的能力，那么我们就说Bob“获得了知识”。 可见知识这个词的定义与Bob的计算能力有关。 如果这些信息没有增加 Bob 的计算能力，那么这些信息就不能称为“知识”。 例如，在爱丽丝和鲍勃的交互过程中，爱丽丝每次抛硬币，然后将结果告诉鲍勃。 从信息的角度来看，Bob得到的信息只是一个“事件”，而Bob并没有得到任何“知识”，因为Bob完全可以自己掷硬币。

下面引用《密码学基础——基本工具》一书中的总结 [10] “知识”与“计算难度”有关，而“信息”不是“知识”，与公众已知的事物有关，“ “信息”主要关注的是部分公开的东西：曾经有人问我这里的信息和知识的定义是否与Kolmogorov复杂度有关。根据算法信息论，一个字符串的信息量可以用长度来衡量生成字符串的最小程序 这道题不是很懂，希望路过的专业人士留言 可验证计算与电路可满足性问题 看完上面的地图三色问题，你是不是觉得这只是一个学术问题，如何将它与实际问题联系起来？地图三着色问题是一个NP-Complete问题，这是“计算论”中的一个术语。另一个叫做“Circu it Satisfiable Problem”也是一个 NP-Complete 问题。 NP-Complete 是一种问题。 它的求解过程很难在多项式时间内完成，即“难解”，但验证解的过程却可以在多项式时间内完成，即“易验证”。

那么什么是电路呢？ 这是三种不同的“算术电路”：

可以看出，一个电路由许多门组成，包括加法门和乘法门。 每个门都有几个输入引脚和几个输出引脚。 每个门执行加法运算或乘法运算。 别看这么简单，我们平时运行的代码（没有死循环）都可以用算术电路来表示。

这是什么意思？ 让我们尝试结合“零知识证明”和“电路可满足性问题”来解决数据隐私保护问题。

接下来请想一个场景：Bob给Alice一段代码P和一个输入x，让Alice运行一次，然后把结果告诉Bob。 可能这个计算需要消耗资源，Bob把计算过程外包给了Alice。 然后爱丽丝又跑了一遍，得到了结果y。 然后告诉Bob y。 问题来了：

如何让Bob在不运行代码的情况下相信运行代码P的结果一定是y？

下面是思考时间，大家可以思考五分钟……

（五分钟后……）

爱丽丝的一个方法是用手机拍下整个计算过程。 这个视频包含了电脑的CPU、内存零知识证明 比特币，以及整个运行过程中各个晶体管的状态。 这样做显然是不现实的。 那么有没有更可行的方案呢？

答案是 Bob 将程序 P 转换成一个完全等效的算术电路，然后将电路交给 Alice。 Alice只需要计算电路，然后这个过程可以用手机拍下来，或者用纸写下来，如果电路规模不是那么大的话。 爱丽丝只需要将参数6输入到电路中，然后记录电路运行过程中连接到门的所有引脚的值。 而最终电路输出引脚的值等于y，则Bob可以确定Alice确实进行了计算。 爱丽丝需要把电路所有门的输入和输出写在一张纸上，交给鲍勃。 这张纸是计算的证明。

这样，Bob 就可以在不重新计算电路的情况下验证这张纸上的证明是否正确。 验证过程非常简单：

Bob 依次检查每个门的输入和输出是否可以满足加法方程或乘法方程。

比如1号门是一个加法门，它的两个输入是3、4，输出是7，所以很容易知道这个门的计算是正确的。 当鲍勃检查了所有的门后，他可以确定：爱丽丝进行了计算并且没有作弊。

这篇论文的内容是一个“满足”运算电路P的解法“解法”。

所谓电路可满足性，就是存在满足电路的解。 如果这个解的输出值等于某个值，那么这个解就可以“代表”电路的计算过程。

对于Alice来说，如果Bob这样验证，她绝对没有作弊的余地。 但是这种方法显然有一个缺点：我们需要对刚才爱丽丝和鲍勃的场景进行一些修改。 假设，爱丽丝自己有一个秘密，比如她的网上银行密码。 Bob 想知道 Alice 的网银密码长度是否为 20 个字符。 不过爱丽丝想了想告诉他密码的长度应该问题不大。 这时，Bob将一个计算字符串长度的代码转换成一个电路Q，发送给Alice。 爱丽丝用电路Q计算出自己的密码，然后把电路所有门的引脚发给鲍勃，并带来计算结果20。

等等，这就有问题了，Bob 得到电路运行的所有内部细节后，难道他不知道密码吗？ 是的，爱丽丝显然不能那样做。 那么爱丽丝应该怎么做呢？

答案是有很多种方法。 喜欢区块链技术的读者最熟悉的是zkSNARK[11]、zkSTARK[12]、BulletProof[13]，还有一些比较小众的技术，都可以帮助Alice做到。 到达：

以零知识的方式，Alice 向 Bob 证明她计算了电路并使用了她的秘密输入。

换句话说，这些“零知识电路可满足性证明协议”为爱丽丝提供了一个强大的武器来向鲍勃证明她的网银密码长度为20，除此之外，鲍勃无法再得到任何其他有用的信息。 除了网银密码外，Alice 理论上可以向 Bob 证明她的任何私人数据的某些特征，但不会透露任何其他信息。

“零知识电路可满足性证明协议”提供最直接的隐私/敏感数据保护技术

近年来，零知识证明构建技术发展迅速，越来越多地应用于区块链技术领域。 最新的零知识证明技术，部分技术可以让Bob高速验证证明（在移动设备上几毫秒完成验证）； 有些技术可以让所有吃瓜群众帮忙验证（非交互式零知识证明）； 支持非常小的证明大小（小至几十个字节）。 我们将在后续文章中逐步介绍。 写在最后，无论是精美的数论定理，地图三色问题，还是电路可满足性问题。 证明存在的意义何在？ 所有的证明都体现了“证明”与“验证”之间的“不对称”。 证明可能是一项非常耗费计算力或脑力的活动，无论是耗时数百年的“费马大定理”，还是比特币中的 POW 证明，这些证明都浓缩了寻找证明过程中消耗的能量。 能源，证明过程可能非常复杂，有时需要天才来证明。 并且验证过程必须（或应该）是一个在（多项式）有效时间内非常简单、机械和可终止的活动。 从某种意义上说，这种不对称性真正体现了证明的意义，体现了零知识证明的价值。

粗略地说，“证明”是“逻辑”的产物，但“逻辑”与“计算”有着千丝万缕的联系。 你可能隐约感觉到“证明”和“计算”之间有某种联系。 它们贯穿始终：例如机械推理、证明表示、交互式计算。 这是一个有趣但更大的哲学问题。

文章内容难免有不准确或不严谨的描述，欢迎各位专业人士抽空指正。 参考资料