当前位置:  首页 →区块链百科 →正文

如何应用可验证计算提高区块链性能?「干货」

2018-12-16 23:27:23 区块链百科

可验证计算 Verifiable Computing 是指在分布式计算和云计算环境下,解决任务分包以及任务委托计算中产生的计算结果可信性问题的方法,是计算机科学和密码学领域较前沿的研究方向。随着分布式计算、尤其是区块链技术的发展,对可信计算 Trusted Computing 和无需信任计算 Trustless Computing 提出更高需求,不少团队开始探索将可验证计算用于区块链领域,以解决目前区块链网络的性能瓶颈。

 

「区块链性能瓶颈亟需突破」

很多研究者在讨论如何对区块链进行扩容,这个话题中非常重要的一个问题是,区块链达成共识的速度非常有限——这是现在区块链性能的瓶颈。

硬核:如何应用可验证计算提高区块链性能?

比如说,比特币的 TPS 其实只有 3~7,以太坊大概 15~25,一些比较新的提案可以把这个增加了很多,比如说 Algorand 可以做到 300tps,Conflux 可以到 6000tps,EOS 则做到了 4000tps 左右。还有有一些项目宣称可以达到 100 万 tps——这个目标很大,如果可以做到,至少几年内不用为性能发愁了。

传统的中心化网络能达到怎样的 TPS?Paypal 平均的 TPS 为 200 左右,峰值可以达到 450 多;Visa 平均为 1600,峰值可以达到 5.6 万;淘宝峰值为 25.6 万 TPS。

硬核:如何应用可验证计算提高区块链性能?

假设我们在一个非常理想的世界里,在这个理想环境下,带宽无限,传输没有延迟,任何时刻可以非常快选择一个领导者,大家知道这个领导者是谁,只要有数据,马上可以达成共识。

即使在这种理想环境中,是不是可以做到 100 万 TPS 呢?实际并不是,因为我们至少需要解决两个问题:

第一,单个节点处理能力处理不了。
第二,区块链数据增长非常快。

硬核:如何应用可验证计算提高区块链性能?

让我们先来看看单个节点处理能力的问题。

在区块链系统中,本质上要求每笔交易都能被每个全节点进行验证。但是通常电脑处理能力非常有限,不可能处理特别多的交易。

如果是一个中心化的系统,这个问题其实很好解决,只要加急器就可以,用并行计算或者分布式计算,用这种方式加一台机器,处理能力至少多个几百块。

但是在区块链系统中,无法相信其他的节点,所有都要验证一遍,即所有的交易要验证是否有效、所有智能合约的执行要验证执行结果对不对。这样最终导致的结果是,即使有一千个节点,实际处理能力可能跟一个就点差不多,因为有一些额外的开销,实际上还不如一个节点的处理能力。比如,以太坊虽然是一个图灵完备、全球化的计算机,但是这个计算机的性能非常低。

硬核:如何应用可验证计算提高区块链性能?

如何解决单个节点处理能力的问题呢?一个非常简单的方式是既然解决不了,干脆放弃治疗,不解决这个问题,只更新状态而不去验证每笔交易是否合法的。

虽然说这样性能可以更高,但是在安全性上有很大的问题。比如说在 2015 年时发生过比特币有六个块的分叉,就是因为矿工在挖矿的时候没有事先验证好矿里的交易是否有效,挖了六个块之后才发现问题。这样的情况下,安全性问题很严重,需要六个块才可以确认交易。

硬核:如何应用可验证计算提高区块链性能?

另一个很容易想到的想法是,既然没有办法用一个节点处理整个网络所有的交易,就减轻每个节点的负担。

很多第二层的方案都是用这种思路做,比如说分片或者用侧链的方式。用这种方式,每个节点处理全网交易里面的一部分,只验证一部分交易,剩下的会交给其他的节点验证,在安全性有部分牺牲的情况下,设立复杂的机制,确保别的分片中做的验证都是对的。可是,如果不对的话要怎么处理,这就比较复杂了。

第三种方法是,既然单个节点处理不够,增加处理能力这也可以是一个方法。

当然最简单的方法是用更强的计算机。这样的问题最终有一个中心化的趋势,如果说想一下希望达到 100 万 tps 的目标,即淘宝峰值 4 倍的交易量,需要计算机的性能非常强,能运行这样节点的公司全世界不会太多。

于此对应的另外一种方式是,减轻每笔交易或者验证智能合约执行时所能花的代价,这样,同样的节点、同样的计算能力,可以在短时间内处理更多的交易。

 

「可验证计算可以用来解决区块验证的问题」

首先,让我们看看验证一个区块需要做哪些事?

硬核:如何应用可验证计算提高区块链性能?

生产了区块之后,首先要验证区块头,这个代价比较小。代价比较大的是验证里面每笔交易,拿出来先看签名对的,每笔交易在 UTXO 合法,金额也是合法的,之后把 UTXO 更新,再验证下一笔交易,一笔笔做下去。这是比较慢的地方。

硬核:如何应用可验证计算提高区块链性能?

用这种方式实际上要重复执行整个计算,把计算整个做一遍,才可以验证这个区块合法的。这是不是必要的一件事呢?是不是只能通过这种方式验证?

看起来不是那么必要。

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

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

这就是可验证计算在研究的问题。

硬核:如何应用可验证计算提高区块链性能?

「可验证计算」这个概念是 1991 年提出的,提出的背景是需要把计算的任务外包出去,需要在这个过程中首先做到外包计算是有效的。

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

通常来说,外包计算实现的框架是,用户这边输入一个编码,把编码输入发给工作者进行计算,最后得到一个编码的输出,用户再把输出的编码变成真正的输出,并且验证结果是对的。

当然,在有的情况下,也可以把输出理解成明文的输出加上一个正确性的证明。

这种模型本身在计算能力上、计算复杂性意义上是非常强大的,可以做到交互式计算能做的事。

硬核:如何应用可验证计算提高区块链性能?

在区块链上解决单个节点处理能力的问题,把验证正确性的工作外包给出块的人做,在出块时验证正确性,这是理所当然做的,验证过以后,其他人比较方便检测验证结果就行。

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

解决这个问题的话,要把这种交互性给去掉、把私有的信息去掉,得到一个非交互式的可验证计算。

解决的方式至少有两种。下面我会讲一下解决方法究竟是什么。

 

「用非交互式可验证计算来验证区块」

第一种方法,是用非交互式可验证计算(NIVC)来验证区块。

硬核:如何应用可验证计算提高区块链性能?

如何通过非交互式可验证计算(NIVC)来验证区块呢?区块成产者可以在每个区块后面加上一个证明,证明从上一个区块头到下一个区块头,经过区块的交易状态转移合法的。

以前需要一笔笔交易验证,现在不需要单笔交易验证,只需要验证一下证明,知道整个区块的转移是合法的,接下来只是更新数据就可以了。

这样的方法最起码有两个好处:

一个好处是整体性能提高,更复杂的验证工作只做一遍,其他的只是很简单的验证证明的工作。
另外一个好处是,在激励方面是比较公平的,因为出块的人可以拿到出块的奖励,有责任做更多的计算,而作为其他的节点,验证一个不是我出的块是拿不到任何奖励的。

 

「区块链数据增长的问题如何解决?」

接下来说一下区块链如果提高 TPS,还需要解决第二个问题:区块链数据增长的问题。

硬核:如何应用可验证计算提高区块链性能?

比特币经过十年发展以后,区块数据超过 190G,接近 200G;以太坊经过三年多发展,整个区块链的数据有 120G——这还是在本身 TPS 非常低的情况下,数据已经达到这个量级了。

如果有一千倍的 TPS 的提高,例如达到了 6000TPS,一天数据就会超过 100G,一年将近 50TB 的数据,这样的数据量非常吓人。当交易量提高时,在网络上需要通讯的数据增加很多。

当然,一个比较容易想到的方法增加很多点,本质上有可能面临读到非常大规模的区块链数据的情况。另一个想法是怎么压缩这些历史,不需要存储所有的历史,只需要存储必要的一部分就可以。

硬核:如何应用可验证计算提高区块链性能?用非交互式可验证计算可以实现压缩区块链数据

首先,要理解为什么要存储、为什么要访问区块链的历史?一个很重要的原因是可以验证、同步区块链当前最新的块是哪个块,以及当前的状态是怎样的,这是最主要的需求。

可能有些人需要记住发生的每一笔交易,但是这个需求对于大多数人来说没有必要的。比如说,去年某个人在巴西或者南非买了一杯咖啡,为什么只记这笔交易呢?只需要知道账户余额多少,所以记住每笔历史不是那么必要的。

如果有可验证计算证明可以做同步,大部分的节点只关心当前的状态怎么样,而不是关心历史上的交易,检查时只需要证明就可以。当然,能达到压缩历史的目的,需要证明本身短,太长没有太大意义。

 

「如何应用概率可验证证明?」

我还想讲一下概率可验证证明(PCP),以及在区块链中的应用。

概率可验证证明是 1992 年提出的理论,是指所有的非确定性多项式 (non-deterministic polynomial, NP) 命题都可以写成概率可验证证明。

非确定性多项式的命题实际上可以比较复杂的,比如说,现在的区块从创始块到现在经过多少的高度、总难度多少达到这个状态。这个定律说的是,只要有这样的命题,只需要检查这个证明中三位就可以有 50% 以上的知信度。如果这个证明是对的,检查三位之后总会接受这个证明;如果证明本身不对的,并没有说从创始块到当前块,经过这么多的高度有中间这么多的区块,50% 以上的概率会拒绝这个证明。

当然,50% 的概率并不是特别理想。50% 的概率离安全性差很多,但是好处是可以重复很多次,比如说重复 10 遍,一共看证明 30 倍,如果一个证明错的,通过 10 次每次都是让我认为对的,这样的概率大概是 1/1024,即 99.9% 以上的概率会拒绝错误的证明。

如果觉得还不够高,可以重复 20、30 次,重复很多次之后,错误的证明概率非常低。结果只需要看证明中常数位,可以非常高的概率验证这个证明是不是对的。

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

硬核:如何应用可验证计算提高区块链性能?

那么,如何把概率可验证证明变成非交互式的证明?

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

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

这是非交互式验证首先要解决的问题。

硬核:如何应用可验证计算提高区块链性能?

有一些方案可以解决这样的问题。

第一种方案是应用 SNARK,引入可信的第三方,让可信的第三方生成要问的问题。

现在这些问题全是公开的,证明者依然很容易作弊,为了解决这个问题,可以用同态加密的方式,让可信的第三方生成问题时,用同态加密的方式加密一下,再把密钥和一开始生成的问题扔掉,所有的人谁都不知道问题长什么样,但是他们知道这个问题加密过以后的样子,可以在同态加密的方式下去计算问题的答案,最后也可以验证是不是对的。
这种方式下,证明者可以模拟验证者,以同态加密的方式问这个问题,再以同态加密的方式回答这个问题,包括最后验证。

使用同态加密,即使个数变得长一点,但是整体比较短。

硬核:如何应用可验证计算提高区块链性能?

当引入可信的第三方时,有时候第三方并不是那么可信。如果不相信可信的第三方,应该怎么做?
可以考虑 STARK 的解决方案,虽然不相信第三方,要相信密码学、相信函数。

现在证明者要生出一个 PCP 的证明,要生成一个纠错码,生成 Merkle root,把这个问题做一个承诺。验证者问的问题就是从 Merkle root 生成的,回答问题时要包含这个证明,把这些证明记录下来生成新的证明。这个过程中不能修改证明,修改证明 Merkle root 也会改,Merkle root 改了以后问题也会变,修改就没有意义了。

 

「压缩区块历史的具体方法」

硬核:如何应用可验证计算提高区块链性能?

如果有比较简短的可验证区块的证明,简短的区块后面有一个证明,上一个区块和这个区块中间存在一个交易,使得这个合法。

这样的话,我们去验证当前的状态以及更新状态时,只需要验证区块头的转移是合法的,验证后面对,就可以了。

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

 

「非交互式可验证计算在区块链上的更多应用」

硬核:如何应用可验证计算提高区块链性能?

硬核:如何应用可验证计算提高区块链性能?

可验证计算本身可以跟零知识证明合在一起。本身零知识证明证明比较少,可以用可验证计算解决。

还有一些其他应用,比如说用 Mass validation 这种方式,可以把交易的大小缩小,现有的情况下提高 10~20 倍。现在处理效率很低,可验证计算虽然可行,代价非常高,高的基本没有任何意义。

另外,在多方计算(MPC)上,可验证计算也会有所帮助,可验证计算可以实现数字签名更高的标准。

总之,可验证证明在区块链上有很多可以探索的应用。当然,这个领域的路还很长,需要各方共同探索。

BB财经原创,作者区块链百科,转载请注明出处:http://www.bbcaijing.cn/baike/37269.html