零知识证明(Zero—Knowledge Proof, ZKPs)于上世纪80年代由S.Goldwasser、S.Micali及C.Rackoff提出,被称为最小泄露证明系统,也是一种基于概率的验证方式

  1. 什么是零知识证明
  2. 为什么说零知识证明是一种区块链核心技术
  3. 现在零知识证明技术成熟可用了吗
  4. 零知识证明安全吗
  5. 如何入门和学习零知识证明?

1. 什么是零知识证明

大家好,我今天跟大家分享下学习零知识证明的一点心得体会。今天的讲解从澄清两个概念开始:「零知识证明系统」「通用零知识证明构造技术」这两个词。

「零知识证明系统」这是计算理论Computation Theory 中的一个关键概念,用来描述一类计算复杂性问题,是一个相当理论的概念,同时这也是现代密码学的核心之一。建议大家在自学密码学的时候,可以注意看看书里面是否包含零知识证明这一章,如果有,说明还是比较新的内容。

后者,「通用零知识证明构造技术」是我们平时讨论最多的概念,当然我们有时候会用 ZK, ZKP,或者zkSNARK 之类的词指代。对于这个词,我想从一个不同的角度来解释,大家能更容易理解。

我先介绍一个比较容易理解的概念:可验证计算,Verifiable Computation。这是一个密码学安全协议,先搞明白它,就比较好理解通用零知识证明技术了。所谓的 Verifiable Computation,是指有两方,个人用户和服务器

用户想让服务器运行一个公开的程序,然后把结果返回,假设说,这个程序运行会相当耗费资源,用户自己只有一个手机,跑不动程序,所以把这个繁重的计算任务交给服务器。

请注意,这里是需要「拜占庭容错」的,也就是说,服务器可能是会作恶的。

服务器的作弊行为就是返回一个错误的或者毫无意义的运行结果。那么由于服务器是在远程执行的,用户又没办法用摄像头监控这个运行过程,怎么能让用户放心呢?这就需要「可验证计算」这个安全协议。它可以做到:让服务器无法作弊。

可能这时候大家会好奇,这是如何做到的,我们在后面一部分再深入解释。我们姑且先认为世界上存在这么一种黑科技,用户可以用某种神奇的设备可以远程监控到整个运行过程。

接下来我们要升级下「可验证计算」这个概念,假如说服务器有一个秘密数据,之所以称之为「秘密」,就是不想让用户知道。

而用户却想让服务器在计算这个繁重的计算任务时,秘密也作为计算输入。随便想一个场景:服务器需要输入它自己的私钥对某个消息进行数字签名,而私钥是绝对不能让用户知道的。

那么,这个安全协议就会变得更复杂一些,不仅需要保证服务器不能作弊,反过来还需要向服务器保证:用户不会得到服务器上保存的秘密数据。那么想象一下,用户使用的神奇监控设备就要有选择性地致盲,凡是看到秘密的时候,就要蒙上自己的监控探头。这个大家可以想象一下,用户进行远程监控的难度更大。

这里,我们要引入「零知识」这个概念,如果是可验证计算协议是零知识的,那么就意味着,不管服务器运行多少遍计算任务,用户都无法获得哪怕一丁点关于「秘密」的知识。

请注意:这个零知识是有数学定义的,是真的「零知识」。

关于零知识的定义,是需要理解一个重要概念——「模拟」,这部分内容略有深,今天我就不介绍了,感兴趣的同学请搜索『探索零知识证明系列二』

这是一个轮廓:零知识的可验证计算。我们只要想象这么一个场景就好,一个用户,还有一台服务器。

接下来,我来用更传统的方式介绍「零知识证明」系统。

零知识证明是证明一段数据,在不泄露数据明文的情况下,证明数据满足一定的性质。

最早零知识证明的概念是与交互式证明系统的概念一起提出来的,零知识交互式证明系统是一种概率式的证明方式,证明者不需要把完整的证明过程直接公开,而是采用让验证者进行问题挑战,通过验证挑战答案的方式来确保证明者的某个论断为真。

零知识交互式证明系统能解决的问题覆盖一个很大的集合。我们常见的证明都能采用这种交互式的方式进行,同时还能保证证明过程不泄露。

这是我在知乎回答的一个问题,如何用零知识证明来证明我证明了哥德巴赫猜想。大家后面可以看看,有助于理解:

这里请注意两点:零知识证明是概率性证明,但是这个概率足够小,概率小到媲美地球毁灭。

经过密码学家们的一番努力,发现交互过程可以通过密码学手段去除。这样就得到了非交互式零知识证明。一旦证明变成非交互,那这个应用场景一下就多了起来。比如大家可以想象一下这种使用场景:

<加密数据 + 零知识证明>

设想我们填了一张表格,里面有各种信息,包括手机号,家庭住址,身份证号,相信我们每个人在填这个表的时候,心里都犯嘀咕,这些数据会不会泄露给打骚扰电话的人。

而且反复各种填表之后,我们已经变得麻木了……  往往就在这时候就埋下了危机的种子。

再设想一下,如何在未来我们只要填一张表就够了,而且不泄露隐私,那该多好。

表里面有很多很多的个人信息,我们可以把这个表格加密起来,我们保管好私钥,监管方也保存好一份私钥。然后当我们需要暴露一些信息给第三方时,我们可以只提交<加密后的表格 + 零知识证明>,只向第三方暴露我们想暴露的信息,比如我们可以证明自己的年龄小于45岁,证明自己身体健康,证明毕业于某所学校,并且成绩合格,我们可以证明自己拥有的不动产超过某个数额等等。但是第三方除了得到这些信息之外,其它的信息都无从获得(因为零知识)。最大限度地平衡个人隐私保护与享受第三方的服务。

更激进的方法可以让第三方服务提供一个计算函数,然后我们用自己的手机来进行计算,向对方证明自己的信息满足对方要求,但是对方得不到其它任何有价值的信息。


2. 为什么说零知识证明是一种区块链核心技术

我最近一直在强调,零知识证明是区块链的一种「不可或缺的」核心技术。我来解释下为什么这么说。

零知识证明在学术界静悄悄地研究了30多年,在区块链领域一下子得到了广泛的应用。

区块链技术发展至今,存在一些难以处理的问题,比如区块存储越来越大,区块链上的数据存储过于昂贵,交易的性能比较差(TPS比较小),上链的信息都是明文处理。突然有一天,我意识这些问题似乎都可以直接或间接的方式用零知识证明来解决。

我们先从性能开始:

以太坊上最近有一个名词特别火,叫做 zkRollup,V神称之为准二层协议。它是通过智能合约来构造一个虚拟的区块链,然后链下的一个服务节点处理业务,当然这个业务处理是需要经过零知识证明的,然后服务节点定期把证明和业务状态提交到智能合约,形成一个区块链的结构。

由于零知识证明有压缩计算的功效,这样可以把链下的许多个业务处理过程压缩成一个很小的证明,然后智能合约只需要通过检查证明就能保证服务节点没办法作弊。

这样就相当于实现了一个高性能的去中心化应用,经过这种方式,在现有以太坊架构上,实现几千 TPS 并不困难。想起之前很多号称高 TPS 的公链方案,看看现实情况,有没有种piapia打脸的感觉。

zkrollup Protocol(https://github.com/matter-labs/rollup)这是zkrollup的一个实现,有兴趣的朋友可以去看看代码,清晰易懂。

零知识证明还可以实现链上数据隐私保护的问题,ZCash 相信大家都知道。以太坊上有一个 Aztec 协议,它可以实现 erc20 token 的隐私保护。

之前我们一直喊:上链!上链!上链!似乎数据上了链就可信了,其实数据上了链也就泄露了。数据不上链没信任,上了链就泄露,怎么办,上零知识证明啊。

采用零知识证明技术,可以同时做到这看似矛盾的两个方面:数据上链校验和隐私保护

Aztec Protocol ( https://github.com/AztecProtocol/AZTEC )这是代码,有兴趣的朋友直接看代码。

最近还有一个特别火的项目叫 Coda,它可以通过零知识证明技术来压缩区块。

现在以太坊的全节点磁盘占用已经奔着四个 TB 去了,感觉区块的增长速度要大于硬盘降价速度。特别是 ETH2.0 部署之后,全网数据量还会加速增长。通过零知识证明可以有效压缩区块,降低新加入的全节点的同步难度,现在没有高性能的固态硬盘,同步以太坊无比痛苦。

手机节点怎么办,有一个项目叫做Celo,它通过零知识证明技术来实现区块链轻节点,并且并不丧失安全性。

最后介绍下,路印团队开发的 去中心化交易所协议— Loopring v3

想必大家对中心化交易的问题都清楚,暗箱操作,黑客盗币,甚至于跑路。如果未来的数字资产普及开来,这里肯定会出现大问题。

路印协议可以做到,万一交易所跑路,用户的数字资产安然无恙,可以从容地提币,基本可以说,100%保证用户的数字资产安全。

路印协议是基于 zkrollup 的思想,现在初步版本的性能已经可以做到 6000 TPS,这已经千倍于之前的 DEX 协议,这都是归功于零知识证明这个强大的工具。

当然为了实现交易撮合,链下的所有业务逻辑为了做零知识证明,都是由电路逻辑来编写。电路逻辑是一种非常低级的编码语言,比写汇编还汇编。我们团队前后花了三个多月来检验这个交易所业务逻辑的可靠性,工程也是非常浩大,期待 Loopring 能早日上线,彻底解决交易的安全问题。

loopring(https://github.com/Loopring/protocols),   一言不合上代码。


3. 电路

零知识证明,需要先把需要做零知识证明的程序转换成电路,  然后在证明的时候是自动的,验证证明也是自动的。电路是一种数学概念,我一会马上讲原理部分的时候回讲到。

我们在网上看到的大多数科普文章是关于 QAP-based zkSNARK 零知识证明方案

ZCash 使用了这个方案,并且也是由于 ZCash 加速了这个技术走出密码学术小圈子,让更广大的极客人群接触到了这个黑科技。很多朋友都看过不少科普,但是论文又不易啃,大家其实对这个内部实现原理都充满了好奇。

我接下来用比较浅显易懂的方式给大家描绘一个大致的流程。我就拿一个非常简单的例子来说明:

设想我知道一个数字  `w`,然后它的哈希值正好落在10^5 和 10^6 之间。然后我要零知识地证明我知道这样一个数字 `w`。

下面按步骤介绍一个大概的直觉上的流程:

第一步:我首先写一个程序

prog(int x) { if x < 10^5 then return 0; if x > 10^6 then return 0; return 1; }然后我把这个代码编译到一种特殊的目标语言:算术电路

零知识证明郭宇讲解版插图

这个思想是来源于硬件电路,但是和硬件几乎没什么关系。这里的电路是一个数学概念,可是为什么是电路呢?而不是其他?因为电路的可满足性问题是一个 NP-complete 问题。所谓的算术电路是由许多的二输入加法门和二输入乘法门组成。门和门之间用线连起来,最左边是输入端,最后边是输出端。如果电路最右端输出 1,那么说明输入的数字满足要求;否则说明输入的数字不满足要求。第二步:我们通过算术电路来构造一个「逻辑约束」,这个约束是把所有门的输入输出关系 AND 起来,得到一个巨大的约束 `C`。一个加法门的约束就是 in1 + in2 = out;而一个乘法门的约束就是 in1 * in2 = out;in, out 这些都是所有电路门之间的连线。我们把这些看成是一组电线变量 `X`。
第三步:我们把这个秘密且珍贵的 `w` 输入到电路中,当然电路的输出应该是返回 1。同时这个电路在运行过程中,我们得到了电路中所有连线上的数值,不仅仅是输入和输出,这等于我们对变量集合 `X` 进行了完全赋值。
如果所有变量都能被赋值,并且满足巨大约束 `C`,那么我们输入的秘密数字 `w` 满足要求。第四步:如果通过电路执行的算法无误,那么这个巨大的约束应该是可以满足的,即逻辑表达式为真。这个电路满足性问题是 NP 问题,如果不老老实实把 `w` 放进来运行,是很难找到另外一组不同的变量赋值,也能满足第二步产生的巨大约束 `C`。第五步:把这个巨大约束 `C`,还有变量集合的赋值 `X` 都放到椭圆曲线上,这样所有的变量值都被加密了。同时采用一些办法,使得这个巨大约束可以在加了密的情况下仍然可以检验(同态性)。这样做的目的是为了保证变量赋值不泄露给验证者,保证零知识。第六步:验证者通过挑战一些值,对一小部分加了密的 `C` 和`X` 进行验证,从而使得证明者的作弊概率降低到一个很小的值。记住这里必须是「随机挑战」。
第七步:运用一些密码学技术,比如 Fiat-shamir 变换,把交互过程折叠起来,变成非交互式。第八步:把产生的最终零知识证明公布出来,让大家来检验。这是一个大概的流程,这个过程大家能看得出来,这就是一个零知识的可验证计算协议。这也是构造通用零知识证明技术的一般思路。


4. 零知识证明技术成熟可用了吗?有很多种零知识证明的技术,比如大家最耳熟能详的 zkSNARK,这里实际指代的是 QAP-based zkSNARK,最新的版本是Groth16,此外还有大家比较熟悉的 Bulletproof,zkSTARK。此外还有一些大家不怎么熟悉的,比如 Marlin, Plonk, Sonic, SuperSonic, Ligero, Aurora, Libra, ……大家可能会问:现在零知识证明技术成熟可用了吗?有关于零知识证明的项目从去年下半年区块链行业遇冷后,反而开始逐步壮大,可能是大家终于可以静下心来做一些有深度的研究。    以太坊早在 2017 年就加入了支持 zkSNARK 的预编译合约,支持以较低的 GAS 费用来实现链上的证明校验。但是直到今年,才涌现出了一大批的采用零知识技术的 Dapp。我想从两个方面来探讨零知识证明技术,理论上和工程上。理论上,目前各种不同的零知识证明技术正在不断的涌现,而且也有一些可以显著提高性能的密码学技巧在不断革新。可以说,在区块链行业大发展的背景下,零知识证明的理论发展过程被加速了。理论上很难说已经到达了一个成熟的阶段,我感觉可能是才刚刚开始。
另一方面是工程上,零知识证明可以说远远不成熟,这个领域到处是空白,许多理论还只是停留在纸面上,或者缺少优化版本的库,还需要社区一起努力。
目前达到产品级应用的库主要是 libsnark  bellman,后者是用 Rust 语言开发的库,仅支持 Groth16方案,这也是 QAP-based zkSNARK 方案中最流行的分支。


5. 如何入门和学习零知识证明最后谈谈大家比较关心的话题:如何入门和学习零知识证明。零知识证明是现代密码学中的一个分支,如果有上过密码学课程,会比较有帮助。需要一些代数知识,和比较简单的概率论。如果要理解透彻零知识证明背后的原理,可能需要啃一些大部头和学术论文。在这里我推荐一本书,『Foundations of Cryptography』,比较系统而且深入。如果只是想大致了解零知识证明的原理,不仅仅满足于有一个直觉上的初步认识,还想一探究竟,那么我推荐自己正在写的『探索零知识证明系列』,这个系列是从比较基础容易理解的概念讲起,讲解一些基本技术,然后逐步切入比较复杂的技术。大家可以关注我们的公众号安比实验室来看最新的文章,这个系列还在不断更新中,我有时间就会写。对于想更深入了解零知识证明基本概念的同学们,我们整理了一个文章列表,筛选了一些零知识证明科普文章,从各个维度来讲解,希望对大家能有所帮助:《零知识证明学习资源汇总》(https://mp.weixin.qq.com/s/-LU4FsFKt7ebX4sbKXNylA)。对于技术人员来说,再也没有比动手写写代码,感受来得更直观。推荐大家试试 snarkjs,性能虽然差了一点,但是可以比较简单地上手,实际感受一下零知识证明编程。
还有一部分零知识证明安全,今天有点超时了,请大家关注后续,以后找时间再讨论这部分内容。


Q&AQ: 我想问一下,零知识证明和算术电路是否一定是绑定的呢?A: 零知识证明并不是需要一定绑定算术电路。比如早期的 ZKP 研究更多关注的是布尔电路。因为布尔电路这个数学模型在理论上使用最多,也最方便,但是很明显,布尔电路在工业应用上比较低效,一个数字可能需要很多 bit 组成,如果电路采用 NAND 这种电路,计算100+100 可能就需要很多的门。在早期的 ZKP 理论研究中,大家比较关注 NPC问题,然后逐步延伸出 NP 类以外,布尔电路是最典型的NPC问题,比如我的探索零知识证明系列文章中,重点讲三染色问题,预告一下,在下一篇中,我将会讲哈密尔顿环路问题,这也是一个 NPC问题。但是为什么是电路呢?因为程序翻译到电路最直接、最方便。可以通过构造电路编译器来实现自动转换。
Q: 请问电路编译器是指从程序生成电路吗?A: 正确,电路编译器就是可以把比如 c语言写的代码变成电路代码。Q: 那mimblew,环签  这种算零知识证明吗?A: mimblewimble, ring sig 都是具有「零知识」性质的安全协议,并不属于通用零知识证明构造技术。Q: 我感觉零知识证明器是一种 特殊的 model checker (概率版的 model checker)对吗 ?A: 和model checker解决的问题不一样。ZKP是检测一个逻辑表达式是否为真,但是并不是时序的,但是逻辑表达式中的某些变量是未知的。
Q: 在手机上生成零知识证明可用性如何?Zcash 也是最近的版本才优化的A: 目前在手机上处理小数据,小规模电路是没问题的。Q: 怎么评价bulletproof的理论和实现,是否足够成熟,安全,工业可用,效率是否还有优化空间。”A: Bulletproof 的一个劣势是验证时间过长,在某些场景下还是比较合适的,没有trusted-setup的问题,理论足够成熟,安全假设都比较标准
Q: 关于bulletproof,再补充一个问题,有可以用硬件加速优化验证时间的可行性吗?A: 当然可以硬件加速,如果有硬件加速的情况下,ZKP的性能可以大幅提高,适用场景会更多。

原文作者:DoraHacks脑洞猫 发于公众号:DoraHacks

链接:《零知识证明郭宇讲解版



零知识证明郭宇讲解版插图1

关注公众号:程序新视界,一个让你软实力、硬技术同步提升的平台

除非注明,否则均为程序新视界原创文章,转载必须以链接形式标明本文链接

本文链接:http://choupangxia.com/2019/11/11/zero-knowledge-proof/