密码学专家杨光：零知识证明和可验证计算在区块链中的应用

12月15-17日，由币看BitKan和Satoshi基金会联合举办的GBDC—2018全球区块链开发者大会于香港举办，金色财经正在进行全程图文直播。会上，密码学专家杨光做了题为《零知识证明和可验证计算在区块链中的应用》的主题演讲。杨光博士是密码学专家，毕业于清华大学，主要研究方向是密码学与计算复杂性。先后在丹麦奥胡斯大学和中科院计算所工作。

---

杨光今天主要围绕实现区块链扩容需要解决的两个问题展开演讲：

一是单个节点处理能力的问题；

二是区块链数据增长较快的问题。

他在演讲中详细介绍了：

零知识证明和可验证计算。

---

以下为杨光的演讲内容：

今天很高兴在这儿有机会跟大家讲一下可验证计算在区块链中的应用。首先我们知道很多研究在讨论怎么样对区块链进行扩容，扩容里面非常重要的问题是区块链达成共识的速度是非常有限的，这也是现在区块链性能的瓶颈。

比如说比特币的TPS其实只有3到7，以太坊大概15到25，一些比较新的提案可以把这个增加了很多，比如说Algorand可以做到300tps，Conflux可以到6000tps，EOS4000tps左右，有一些项目宣称100万tps，这个目标很大，做到的话至少几年内不用性能发愁了，传统的中心化的做到tps是多少？Paypal平均200左右，峰值450多，Visa峰值1600，峰值5.6万了。淘宝峰值25.6万tps。共识部分假设在非常理想的世界里，理想环境下带宽无限的，传输没有延迟的，任何时刻可以非常快，随即选择一个领导者，大家知道这个领导者是是谁，只要有数据马上可以达成共识。即使这种环境下，是不是可以做到100万tps呢？不是，至少两个问题解决：

第一，单个节点处理能力处理不了。

第二，区块链数据增长非常快。

首先，单个节点处理能力的问题，在区块链系统中本质上要求每笔交易期望每个至少全节点要验证这笔交易的，但是通常电脑处理能力是非常有限的，不可能处理特别多的交易。如果是一个中心化的系统，这种方式、这个问题其实很好解决，只要加机器就可以，用并行计算或者分布式计算，用这种方式加一台机器，处理能力至少多个几百块。区块链系统，我们这里无法相信其他的节点。所有的东西自己都要验证一遍，所有的交易要验证是否有效，所有的智能合约的执行要验证执行结果对不对，最终导致的结果是即使有一千个节点，实际处理能力可能跟一个就点差不多，因为有一些额外的开销，实际上还不如一个节点的处理能力。

以太坊虽然是一个特别完备、全球化的计算机，但是这个计算机的性能非常低的。我们怎么解决单个节点处理能力的问题呢？一个非常简单的方式是既然解决不了干脆放弃治疗，不解决这个问题，只更新状态而不去验证每笔交易是否合法的。虽然说可以做的很快，但是在安全性上是有很大的问题。比如说在历史上2015年时发生过比特币有六个块的分叉，就是因为他们在挖矿的时候没有事先验证好矿里的交易是否有效，在无限的块上挖，六个块之后才发现，安全性问题很严重，很多地方六个块可以确认交易。

另一个很容易想到的想法，既然没有办法用一个节点处理整个网络所有的交易，就减轻每个节点的负担，很多第二层的方案都是用这种思路做，比如说分片或者用侧链的方式，用这种方式每个节点处理全网交易里面的一部分，只验证一部分交易，剩下的会交给其他的节点验证，在安全性有牺牲的，需要设立复杂的机制，确实别的分片中做的验证都是对的，如果不对的话要怎么处理，这比较复杂一点。

既然单个节点处理不够，增加处理能力这也是一个方法，当然最简单的方法是用更强的计算机。这样的问题最终有一个中心化的趋势，如果说想一下希望达到100万tps的目标，淘宝峰值4倍的交易量，需要的计算机什么规模，能运行节点的公司全世界不会太多。另外一种方式是减轻每笔交易或者验证智能合约执行时所能花的代价，这个代价降低之后同样的节点、同样的计算能力可以在短时间内处理更多的交易。

如果验证一个区块需要做哪些事？通常做了区块之后首先要验证区块头，这个代价比较小，比较多的是验证里面每笔交易，拿出来先看签名对的，每笔交易在UTXO合法，金额也是合法的，之后把UTXO更新验证下一笔交易，一笔笔做下去，这是比较慢的地方。

用这种方式实际上要重复执行整个计算，把计算整个做一遍，可以验证这个区块合法的。但是这是不是真的非常必要的一件事呢？是不是真的只能通过这种方式验证？看起来不是那么必要。

现在大部分的节点只是需要验证这里面的东西合法的，这个工作在区块的时候打包者已经做过一遍了，其他的人并不是非要重复这个工作的，一个比较简单的直觉是通常来说验证一个计算的结果比真正做这个计算花的代价可以小很多的。比如说看到这样一个方程，让你解这个方程花的计算量比较高，因为三次方程不是那么容易解的，如果告诉你这个方程的根是什么，验证是不是对的，这是容易的。

既然验证可以比计算简单这么多，为什么不是让区块打包者生成一个证明，其他人只需要验证一个比较短的证明，只需要知道这个东西对的，不需要把所有的签名验证、状态更新都跑一遍，特别是智能合约的执行花的代价比较高。

现在看到的是可验证计算研究的问题，这个概念是1991年提出的，提出的是需要做外包计算的任务，需要在这个过程中首先做到外包计算是有效的，把计算承包给不那么可信的工作者以后，工作者的计算代价不要比自己计算高太多，高太多不经济的。

另一方面，需要保障计算的正确性，神经网络的模型和数据扔到亚马逊的云上跑机器训练的模型最后再给一个结果，怎么知道结果确实在模型上跑数据得到的，而不是自己随便生成的一个。如果真的跑数据可能花一些硬件的成本，包括时间、电费花的成本，随便告诉一个结果不知道对还是错的，这样的话外包计算完全没有意义了。

通常来说，外包计算实现的框架用户这边输入一个编码，把编码输入发给工作者进行计算，计算的时候编码输入上进行计算，最后得到一个编码的输出，用户再检查输出的编码变成真正的输出，并且验证结果是对的。当然，在有的情况下你也可以把输出理解成明文的输出加上一个正确性的证明。

这种模型本身在计算能力上、计算复杂性意义上是非常强大的，可以做到交互式计算能做的事。在区块链上实际上现在任何解决单个节点处理能力的问题，做的事是把正确性的工作外包给出块的人做，出块时验证正确性，这是理所当然做的，验证过以后其他人比较方便检测验证结果就行。如果直接用可验证计算还是不太够的。

因为最开始的版本可验证计算中需要有交互性，而且需要有输入这边，用户需要有一些私有的信息，这样的话导致如果可验证计算包给区块的人做，我可以验证这个计算结果是对的，但是另外一个人也需要验证的话，需要让区块的人再跑一遍再用私有的输入重新跑一遍，实际上还是非常不经济的。

解决这个问题的话，我们要把这种交互性给去掉，把私有的信息去掉，得到一个非交互式的可验证计算，解决的方式至少有两种，稍候讲一下是什么样的。

有了非交互式可验证计算，可以把区块链的验证做到什么样？这样的话会作每个区块后面加上一个证明，这个证明从上一个区块头到下一个区块头，经过区块的交易状态转移合法的。以前需要一笔笔交易验证，现在不需要单笔交易验证，只需要验证一下证明，知道整个区块的转移合法的，接下来只是更新数据就可以。这样的好处是整体性能高，更复杂的验证工作只做一遍，其他的只是很金丹的验证证明的工作。

在激励方面是比较公平的，因为出块的人可以拿到出块的奖励，有责任做更多的预算，而作为其他的节点，验证一个不是我出的块是拿不到任何奖励的，可以保证正确性，既然拿不到奖励，尽可能做一些工作，道理上也想得通。

接下来说一下区块链如果提高tps还需要第二个解决的问题：区块链数据增长的问题。比特币经过十年发展以后，区块数据190多G，接近200G，以太坊经过三年多以后，整个区块链的数据额有120G，这还是本身TPS非常低的情况下数据达到这个量级了。如果考虑一下有一千倍的TPS的提高。如果6000TPS，一天数据100多G，一年将近50个TB，这个数据量非常吓人。这样对新加入的人非常好，晚一年加入下载很多TB进行验证才能跟上这个状态。当交易量提高时，在网络上需要通讯的数据增加很多。当然，一个比较容易想到的方法增加很多点，本质上有可能面临读到非常大规模的区块链数据的情况。

另一个想法是怎么压缩这些历史，不需要存储所有的历史，只需要存储必要的一部分就可以。用可交互预算可以压缩历史的。

首先，为什么要存储、为什么要访问区块链的历史？一个很重要的原因是可以验证、同步区块链当前最新的块是哪个块，以及当前的状态是怎样的，这是最主要的需求。可能有些人有需求需要记住需要发生每一笔交易，这个需求对于大多数人来说没有必要的。比如说去年某个人在巴西或者南非买了一杯咖啡，为什么只记这笔交易呢？只需要知道账户余额多少，所以记住每笔历史不是那么必要的。如果有可验证计算证明可以做同步，大部分的节点只关心当前的状态怎么样，而不是关心历史上的交易，让其他某个人生成证明，花很长时间预算验证状态做证明，检查时只需要证明就可以。当然，能达到压缩历史的目的，需要证明本身短，太长没有太大意义的，本身问题是证明到底有多短。这个证明其实可以做非常短的，在这里讲一下概率可验证证明。概率可验证证明92年有一个证明，所有的NP命题都可以写成概率可验证证明，NP的命题实际上可以比较复杂的，比如说可以说现在的区块币是从创始块到现在经过多少的高度，总难度多少达到这个状态。当然如果说整个区块链的历史给出来可以验证这件事的。这个定律说的是只要有这样的命题、这样的证明只需要检查这个证明中三位就可以有50%以上的知信度。如果这个证明是对的，检查三位之后总会接受这个证明，如果证明本身不对的，并没有说从创始块到当前块，经过这么多的高度有中间这么多的区块，50%以上的概率会拒绝这个证明。

当然，50%的概率不是特别理想。50%的概率离安全性差很多，但是好处是可以重复很多次，比如说重复10遍，一共看证明30倍，如果一个证明错的，通过10次每次都是让我认为对的，这样的概率大概1/1024，99.9%以上的概率会拒绝错误的证明。如果觉得还不够高，可以重复20、30次，重复很多次之后错误的证明概率非常低。结果只需要看证明中常数位，可以非常高的概率验证这个证明是不是对的。

其实PCP的证明并不能直接用在区块链中，这个证明中证明本身还是非常长的，只是我需要看的位数比较少，只需要看里面三十位，证明本身长度长很多，而且是交互性的证明，只有通过交互才能把需要看的位数降低下来，怎么样把PCP证明变成非交互式的证明。

刚才说了可以把计算外包出去，现在把验证的任务也可以外包出去，这个证明者说我可以替你问这些问题，我自问自答，你看我自问自答的表演就可以了，这样的话证明者会模拟一个虚拟的验证者，虚拟的验证者负责提出问题，证明者按照它的PCP证明回答问题，把通讯的过程写下来，可以当做一个证明来看。

但是，用这种方式实际上没有太大意义的，因为证明者这边如果自己可以控制验证者，可以在问问题的时候作弊，非常容易作弊，因为知道回答什么样的答案验证者会接受，把自己答案设计就可以，这是验证非交互式首先要解决的问题。

当然，第一种方案是在SNARK里面应用这个方案，引入可信的第三方，让可信的第三方生成要问的问题， 现在这些问题全是公开的，证明者依然很容易作弊，为了解决这个问题，可以用同态加密的方式，可信的第三方生成问题时，用同态加密的方式加密一下再把密钥和一开始生成的问题扔掉，所有的人谁都不知道问题长什么样，但是他们知道这个问题加密过以后的样子，可以在同态加密的方式下去计算问题的答案，最后也可以验证是不是对的。这种方式下证明者可以模拟验证者，以同态加密的方式问这个问题，再以同态加密的方式回答这个问题，包括最后验证。同态加密即使个数变得长一点，但是整体比较短。还要引入可信的第三方，有时候不是那么可信，如果不相信可信的第三方，应该怎么做？

现在看到的是STARK的解决方案， 虽然不相信第三方，要相信密码学、相信函数，如果不相信密码学不需要做区块链的任何事。现在证明者要生出一个PCP的证明，要生成一个纠错码，生成Merkle root，把这个问题做一个承诺。验证者问的问题就是从Merkle root生成的，回答问题时要包含这个证明把这些证明记录下来生成新的证明。不能修改证明，修改证明Merkle root也会改，Merkle root改了以后问题也会变，修改没有意义了。这是STARK的解决方案。

如果有比较简短的可验证区块的证明，简短的区块后面有一个证明，上一个区块和这个区块中间存在一个交易使得这个合法的。这样的话我们去验证当前的状态以及更新状态时，其实就只需要验证区块头的转移是合法的，验证后面对的就可以了。

当然，进一步可以把很多证明压缩到关于证明的证明里面。一千个块出一个证明，这样验证的东西更少。

可验证计算本身跟零知识证明可以合在一起，本身零知识证明比较少，可以用可验证计算解决。 还有一些其他应用，比如说用这种方式可以把每个交易的大小缩小，现有的情况下提高10到20倍。现在处理效率很低，可验证计算虽然可行，代价非常高，高的基本没有任何意义。

多方计算，可验证计算也会有帮助，可验证计算可以理解数字签名更高的标准，数字签名验证一个文本一个消息，可验证计算是做的计算、做的行为是对的。

我的演讲到这里，谢谢大家！