当前位置:  首页 →区块链技术 →正文

Monoxide原理详解:突破区块链不可能三角的极简架构

2019-01-31 14:24:23 华尔街之狼

"我们时常遇到一些令人叹为观止的机遇,却一次次地被当成不可能解决的问题”-- 約翰.加德納, 1965年

突破区块链不可能三角的极简架构

五分钟简版

Monoxide是Layer 1的区块链技术,不假设交易结构的任何局部特性,跨共识组的交易再多都无压力。性能提升包括吞吐量和状态容量,由划分的共识组个数决定。n个共识组将带来n/2倍的吞吐量提升和n倍的状态容量提升。在现在的互联网环境中,n最多可以到数万,这个是性能提升的上限。核心技术突破为一个中心,两个基本点:

一个中心是并行、异步并独立工作的多链架构(n个共识组),将网络通讯(网络)、合约计算(CPU)、状态表达(内存)和交易归档(磁盘)这个四个方面的工作量全部分片,即所谓的"全分片"。共识组是一个无锁(lock-free)的多链架构,独立完成共识,独立校验和执行交易,独立维护组内用户的状态和历史记录。

第一个基本点是高效的跨分片交易的处理。我们提出了"最终原子性",将交易中的原子操作拆分成多个,涉及不同共识组的操作,使之可以并行、交叠(interleave)地被处理。利用单链系统既有的未确认交易集合来完成各共识组之间的异步消息传递,完成一个交易的接力执行。使得跨分片交易对性能的影响最多折半,无论全网有多少个共识组。

第二个基本点是有效抵御多链结构中,算力分散的问题,即攻击者可以聚集算力攻击特定共识组(1%攻击)。我们提出了"连弩挖矿",允许一次成功的算力哈希刺探可以获得在多个共识组同时出块的权益。将物理算力(计算哈希的速度)最多提高为n倍对应的有效算力(实际出块的速度)。并且这种n倍放大之后的算力必须平均分配到各个共识组。如果攻击者企图针对特定共识组,将无法获得连弩挖矿带来的这种算力放大。从而使得对单个共识组的攻击依旧需要全网的51%物理算力。

 

原理详解完整版

先奉上一张海报:

海报

这是我们的论文要在NSDI 2019 大会会场上展示的海报,第一时间分享给各位读者朋友,便于大家更好理解「Monoxide」的设计架构和实现原理。自从我们的论文被NSDI 大会收录的消息传出,我收到了不少朋友和媒体提出的问题,希望了解具体的研究成果。我在上周撰写了一篇文章「突破区块链不可能三角: 异步共识组 Monoxide 」,介绍了「Monoxide」的基本原理和实验取得的成果,然后收到大量反馈希望了解详尽的设计和算法。所以,我决定在 NSDI 大会召开之前,顺着上面海报的逻辑,详细地介绍一下Monoxide的架构设计和算法细节。

虽然Monoxide架构可以采用不同的共识算法作为其共识组内的共识机制,而在这篇文章中,我会基于最简单、最干净的Nakamoto共识算法(Proof-of-Work)展开讨论。Monoxide将同时满足区块链的安全,性能和去中心化的需求。

第一角: 怎么样算安全 

区块链系统必须是安全的,这一点是不容妥协的,否则所有其他特性将毫无意义。具体落实到技术指标,就是在系统中构造一系列非法区块并得到全网认可的代价。这个代价就PoW共识机制而言,就是实施攻击的最小挖矿算力。Nakamoto共识算法保证恶意算力在50%以下的时候,系统是安全的。我们保证的是采用Monoxide架构之后,这个50%算力的安全边界不会显著变低。同时,我们继承了Nakamoto算法的其他安全特性,例如不要求出块节点始终在线,全节点物理IP地址仅在一个很小的范围内暴露等。

第二角: 怎么样算高性能 

Monoxide架构将完全隔离每个共识组的四大工作负荷, 即: 带宽(广播区块数据和未确认交易),计算(验证交易和更新账簿状态),内存(存储账簿的最新状态),磁盘读写(记录历史区块)。我们强调这四个方面的负荷必须全部被切分隔离,才能真正获得高伸缩性的区块链系统,而不是仅完成部分工作符合的隔离,即所谓的网络分片,交易分片和状态分片。具体落实到技术指标,性能包含两个方面的,一个是众所周知的吞吐量,即最高每秒处理多少笔交易 (TPS),而另一个是全网表达账簿状态的总有效内存总量。前者是速度,后者是容量。我们实现了 吞吐量大致 n/2 倍的线性提升以及状态容量的n倍的线性提升 (以支付交易计算为例)。这里的n是共识组的个数,提升是相对于共识组内部采用的单链共识系统的性能。现在一个单链共识系统,比较轻松能达到的是几百TPS的吞吐量和数十GB的状态空间。注意,这里并不是说Monoxide可以无限提升性能,在现有的互联网平均带宽的约束下(15Mbps),共识组的个数n最高只能到数万这个量级。

第三角: 怎么样算去中心化 

首先,公链必须是permissionless系统,并且系统中不存在不可替代的角色或者节点, 这是一个定性的要求。在满足这个要求之后,去中心化可以落实到具体的技术指标,即需要多少IT资源才能顺利地参与全网的监管(部分或者全部),也就是全节点的参与门槛。而这个门槛最关键的因素是带宽,高带宽只有部署在数据中心才能获得,其链路的地理位置也容易被追踪;而其他资源诸如CPU,内存,磁盘等都可以不受特定地理位置的约束,也无法追踪,花点钱就有。Monoxide架构在获得几个数量级的性能提升的同时,始终将全节点带宽消耗控制在普通家用互联网接入可以承受的范围(15Mbps),从而使得Monoxide的全节点可以像现在的以太坊全节点一样,随便在家里找个普通电脑就开起来。同时Monoxide的共识组划分了历史交易归档的工作量,使得完整同步一个全节点的时间会比现在的以太坊少几百倍。强调全节点进入门槛的原因是,只有全节点才能够在不信任其他节点的情况下,独立验证交易,重建账簿状态,而不是像云计算那样,需要依赖于信任特定的节点(或服务器),这是区块链和云计算的本质区格之一。

 

总体设计

总体设计

总体来说,Monoxide的设计哲学是尽量简单,在能满足上述三角特性的前提下,尽量不引入额外的实体,不引入额外的机制,并尽量少修改现有的机制。Monoxide网络是一个并发的多链系统,每一个链我们称之为"共识组"。每个共识组其组成部分和现在单链系统完全一致,有自己的账簿状态,区块的链条,未确认交易的集合,同步区块数据和交易数据的广播网络以及一堆全节点(包括矿工)。各个共识组之间完全对等,无主次之分,除此之外这个网络就没有任何其他的角色了,没有之前那些方案提出的母链,根链之类的,也没有任何掌控全局的调度节点或验证节点。引入这些实体会使得一些功能更容易实现(例如动态负载平衡),但是他们会牺牲去中心化特性,甚至还可能导致严重的性能瓶颈。

全网所有共识组用一个整数编号 (0到n-1),我们限定共识组的总个数为2的k次幂,即n=2^k。任何一个账簿地址,根据其地址二进制数据的前k个比特,永久地被分配在一个共识组中。每个交易则根据交易的验证方的地址 (例如转账交易的支付方),被分配在验证方所属的共识组。所以Monoxide网络的划分不需要任何中心化的机制来分配地址和交易。

Monoxide全网由各个共识组的出块过程和未确认交易集合完全独立,共识组之间完全并行、异步且无需锁定和同步,即使某一个共识组发生拥塞也不会干扰其他共识组的吞吐和出块。

Monoxide全网由各个共识组的独立广播子网所构成,但这些广播子网互相不重叠,互相不打搅。在我们的设计中,这些广播子网由DHT的Swarm实现,每一个广播子网对应一个Swarm。新启动的全节点根据其想要加入的共识组编号直接计算Swarm地址,然后利用DHT的路由机制找到同一共识组里面的其他全节点,并尝试连接并入网。全节点可以随机选择加入任意一个或多个共识组,或由上层应用来决定。例如,钱包节点通常会加入登录用户的钱包地址所在的共识组,以便实时获取其账户余额等状态。Monoxide全节点不记录任何用户登录状态或用户私钥,以避免以太网全节点之前出现的RPC接口安全隐患。除非其上层应用请求,通常一个共识组的全节点不会主动连接另一个共识组的节点。

同样矿工可以自由选择参与一个或多个共识组,进行挖矿,以期获得每一个共识组中的出块奖励。正常情况下,矿工会优先选择参与当前算力较低的共识组,以获得更高的利润,从而导致各个共识组会收敛到一致的挖矿算力和出块难度。

从这个设计,我们可以看到Monoxide架构满足区块链三角的情况。

1. 安全 只要各个共识组本身是安全的,Monoxide就会是安全的。交易的安全和正确(例如避免双花)依赖于每个共识组内部的共识算法。Monoxide全网应对女巫攻击(Sybil Attack)也依赖于共识组内部的共识算法本身的抵御能力。就PoW而言,每个共识组的安全,依赖于其内部挖矿算力。所以Monoxide架构的安全保障,核心是要能够抵御算力分散的问题,即全网算力分散到每个共识组之后,每个共识组的算力将是全网的1/n,这时单个共识组的防御壁垒将下降到 51/n %,(即所谓的1%攻击)。这将是一个完全无法接受的值。为了解决这个算力分散的问题,Monoxide引入了连弩挖矿(Chu-ko-nu Mining),使得单个共识组的防御壁垒回升到 51%。

2. 性能 由于各共识组的区块验证、存储和账簿状态更新完全独立,所以这三个方面将获得无代价的无限线性提升。共识组之间唯一需要打交道的地方,就是为了正确处理跨共识组的交易。这使得在数据传输方面,性能提升是有代价的,并且不是无限的。为了高效完成跨共识组交易,Monoxide引入了最终原子性(Eventual Atomicity),使得即使跨共识组交易的比例就算是接近 100%,全网仍旧可以轻松地完成交易吞吐,其性能代价为一个和共识组个数无关的常数。

3. 去中心化 根据上面的描述,Monoxide依旧是一个彻底的permessionless的系统,并且每个共识组内部的全节点的负担始终保持在同维护一个单链系统相当的水平,可以被轻松部署到大部分有互联网接入的角落。

综上,论文最重要的两大技术贡献就是 连弩挖矿(Chu-ko-nu Mining) 和 最终原子性(Eventual Atomicity)。后面我们将就这两个方面,详细展开,并以Bitcoin数据结构为蓝本,给出这两个机制对PoW共识协议的改进。

 

连弩挖矿(Chu-ko-nu Mining)

连弩挖矿(Chu-ko-nu Mining)

在PoW共识机制中,矿工需要不断随机刺探块头中的Nonce并重算哈希函数,以使得这个块头的哈希值满足当前算力难度的要求,可以最终出块。这个过程的瓶颈在于计算哈希函数的速度,所以挖矿算力被定义为哈希速率(Hashrate)。这里,我们将实际计算哈希的速度,定义为物理算力(Physical Mining Power),提高物理算力的唯一方法就是部署更多的矿机,消耗更多的电能。

然而,在PoW共识机制中,每个矿工的物理算力是无法直接知道的,这个物理算力最终体现为特定挖矿难度下的出块速度。全网算力统计也是基于这个出块速度而反算哈希速率而估计到的。在发生算力攻击的时候,无论是最长链,还是最难子树(Ghost协议),都是依据各个分叉上出块的数量和难度而定,而非各个矿工的实际哈希速率。我们将这个依据挖矿难度和出块速度反算出来的哈希速率,定义为有效算力(Effective Mining Power)。当然在单链系统中,有效算力和物理算力,在统计意义上来说是完全相等的。

前面提到的算力分散问题是这样的一个攻击模型: 在有n个共识组的Monoxide系统中,全网有效算力为H,每个共识组的有效算力为H/n。攻击者在实施攻击的时候,将其所有物理算力T分配到一个特定共识组,在这个共识组中获得有效算力T。那边当其物理算力超过 T > H/n × 51% 的时候,攻击将可以成功,并构造不一致交易(例如双花交易)。

为了抵御这个算力聚焦的攻击模型,我们的思路是强制矿工将算力分散到各个共识组,使其无法集中算力攻击特定共识组。但在一个去中心化的permissionless系统中,我们无法控制矿工如何分配其物理算力。Monoxide引入了连弩挖矿,其效果是将使得全网的有效算力放大为物理算力的n倍,并且在协议的数据结构层面约束了这种放大后的有效算力必须平均分配到各个共识组,从而规避了这种算力聚焦的攻击模型。

连弩挖矿(Chu-ko-nu Mining)

连弩挖矿允许矿工同时参与多个编号连续的共识组 (例如从编号b到b+m-1),每次出块的时候哈希函数将覆盖多个将要出块的块头进行计算,同时这些块头将共用一个Nonce。具体做法是将这个m个块头按序排列,构造Merkle树。然后算力哈希计算将覆盖下列数据结构:

<MerkleRoot, b, m, Nonce>

出块时,下列数据结构会被广播到特定的共识组 i (b≤i<b+m),仅包含该共识组的块头以及一个该块头被包含在内的证明,不涉及到其他共识组的块头。

<MerkleRoot, b, m, Nonce, Block_i, MerkleTreePath_i>

其中MerkleTreePath_i是Block_i在Merkle树路径上的左右兄弟节点的哈希值,需要32 × log_2 m 个字节。注意这里没有显式给Block_i在Merkle树中的位置,而是需要Block_i中的共识组编号减去b推算出来,这样做是为了约束连弩挖矿出块的时候,每个共识组只能出一个块。

从这个结构中可以看到,即使在连弩挖矿的情况下,各个共识组也不会受到其他共识组出块情况的影响。连弩挖矿并不要求各个共识组同步接受这些块,甚至有些块最终被认为是无效分叉,也不会影响其他块在其他共识组中被接受。同时,这个结构允许连弩挖矿包含算力难度不同的共识组,一旦部分共识组的挖矿难度被满足,这些的块就可以先发出去。

连弩挖矿将矿工有效算力放大,同时也放大了单位物理算力可以获得的出块奖励,同样的物理算力,同样的能源消耗,参与到越多的共识组挖矿,所获得的出块奖励也会