"我们时常遇到一些令人叹为观止的机遇，却一次次地被当成不可能解决的问题”-- 約翰．加德納, 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）
在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倍，并且在协议的数据结构层面约束了这种放大后的有效算力必须平均分配到各个共识组，从而规避了这种算力聚焦的攻击模型。
连弩挖矿允许矿工同时参与多个编号连续的共识组 (例如从编号b到b+m-1)，每次出块的时候哈希函数将覆盖多个将要出块的块头进行计算，同时这些块头将共用一个Nonce。具体做法是将这个m个块头按序排列，构造Merkle树。然后算力哈希计算将覆盖下列数据结构:
出块时，下列数据结构会被广播到特定的共识组 i (b≤i
其中MerkleTreePath_i是Block_i在Merkle树路径上的左右兄弟节点的哈希值，需要32 × log_2 m 个字节。注意这里没有显式给Block_i在Merkle树中的位置，而是需要Block_i中的共识组编号减去b推算出来，这样做是为了约束连弩挖矿出块的时候，每个共识组只能出一个块。
从这个结构中可以看到，即使在连弩挖矿的情况下，各个共识组也不会受到其他共识组出块情况的影响。连弩挖矿并不要求各个共识组同步接受这些块，甚至有些块最终被认为是无效分叉，也不会影响其他块在其他共识组中被接受。同时，这个结构允许连弩挖矿包含算力难度不同的共识组，一旦部分共识组的挖矿难度被满足，这些的块就可以先发出去。
连弩挖矿将矿工有效算力放大，同时也放大了单位物理算力可以获得的出块奖励，同样的物理算力，同样的能源消耗，参与到越多的共识组挖矿，所获得的出块奖励也会越多。所以，全网会收敛到主流的矿工都会采用连弩挖矿，并且参与到所有的共识组中。从而，使得全网的有效算力达到 H × n，单个共识组的有效算力达到 H 。这样使得攻击单个共识组的物理算力要求和攻击全网的物理算力相当，有效抵御算力聚焦的攻击。
同时参与到多个共识组挖矿，需要更多的IT资源用来同步和验证每个共识组的交易和区块(不仅仅是块头)，也需要更多的磁盘存储和内存。基于去中心化的考虑，参与连弩挖矿与否，以及参与的共识组个数是一个矿工可以自行配置的选项，Monoxide并不要求所有矿工都参与所有共识组的挖矿。
诚然，参与更多的共识组会需要有线性增加的IT资源开销，但是在成本上来说这些和大型矿场的矿机开销来说，就可以忽略不计了。在技术上来说，矿场从来都不是一个节点，而是一个又成百上千台矿机组成的集群。得益于共识组独立性，一个参与所有共识组挖矿的矿场，很容易在其公司内部实现一个可伸缩的挖矿数据中心，用不同的主机监控各个共识组，用不同主机确认交易构造新区块，然后在内部的高速网络中汇总这些块头的哈希(Merkle的叶节点)，并送给矿机集群。所以，即使要求矿池同步和处理所有共识组的交易和状态，也没有损害系统的伸缩性。
最后，顺便提一下联合挖矿(Merge Mining)，在允许矿工同时参与多条链的挖矿这一点上，是有类似的地方。但是连弩挖矿设计初衷和工作场景和联合挖矿完全不同，前者是为了放大有效算力，并强制放大后的算力均分在各个共识组，以防止算力集中攻击特定共识组。而后者是为了借用大算力的链，来保证小算力链的安全。
最终原子性 （Eventual Atomicity）
在Monoxide中，我们采用非常简单的和去中心化的方式将用户和交易分配到共识组，并不企图减少跨共识组交易发生概率，我们认为利用交易结构的局域性是Layer 2技术的事情。全网性能越高，共识组数量越多，跨共识组交易发生概率一定会越高，这不是一个可以回避的问题。在我们的实验中，当共识组数量达到64的时候，跨共识组交易的比例已经超过了95% (实验的测试数据为以太坊ERC20的完整历史交易记录)。Monoxide引入了最终原子性来实现高效的跨共识组交易处理，使得每个跨共识组交易带来的额外开销是一个很小的常数，并且和共识组数量n无关。
区块链系统，每一个交易都是一个原子操作。在单链系统中，就好比单线程，这个原子操作并没有被强调，因为交易本来就是被一个一个地确认和处理，系统无需做任何额外的事情，原子性就自然有保障。而在Monoxide中，不同地址的状态在不同共识组中维护，互相不可见，其状态的更新也被两个不同的链驱动，就好比多线程。一个原子操作要在这样的架构下正确安全地完成，就不是一个简单的事情了。通常为了协同多线程，我们有两种办法，一个是互相对所涉及的资源加锁，另一个则是借由消息传递。我们选择了后者，一方面是因为加锁会阻塞对应的共识组的吞吐，严重影响性能，另一方面是因为所有的单链区块链天生就有一个消息传递机制(未确认交易集合)，从而避免引入新的实体。
我们先以最简单的支付交易为例，介绍我们的设计。一个数量为x的从地址A到地址B的支付交易，并且A和B处于不同的共识组。这是一个原子操作，其中包含一个扣款操作，这个操作有条件，并且不同的执行顺序会导致不同的状态。另一个是存款操作，这个操作无条件，并且不同的执行顺序不会导致不一致的最终状态。
对于这样的交易逻辑，Monoxide将先现在共识组A中，尝试完成扣款操作。如果成功，则将向共识组B转发一个接力交易，一种特殊的未确认交易。接力交易和普通未确认交易一样，描述了用什么参数，调用哪个智能合约里面的函数。和普通未确认交易不同的是权限校验方式。普通未确认交易，通常由钱包签发，通过其携带数字签名来校验权限。而接力交易携带的是来自另一个共识组的出块证明:
为了校验这个接力交易，共识组的块头将包含两个MerkleRoot，一个是之前就有的覆盖所有被本块确认的交易的Merkle树，另一个是新增的覆盖由本块中的交易发出去的所有接力交易。后者将被其他共识组接收，并用于校验由其发出去的接力交易。
默认情况下，构造和转发接力交易由确认初始交易的那个矿工(在共识组A)完成。万一这个转发失效，共识组A中任何一个全节点，都有能力从交易历史中根据那个初始交易重新构造并转发丢失的接力交易，无需额外的共识或证明。
无论是接力交易，还是普通的未确认交易，都将以类似的方式在目标共识组的广播子网中传播，并被暂存在未确认交易的集合中。矿工在出块的时候，将同等对待接力交易和未确认交易，通常根据其手续费多少来排优先级。任何产生一个或多个接力交易的初始交易，其手续费会以一定比例分配给初始交易和多个接力交易，给到最终在其他共识组确认这些交易的矿工。在Monoxide中，这个分配比例可以由智能合约代码控制。
从上述流程中，我们可以看到在Monoxide系统中交易原子性并没有得到立即满足，而是要等到所有接力交易被确认和执行之后，才最终得以完成。我们将此称为最终原子性，而不是要求即时的原子性。最终原子性使得跨共识组的交易可以被无阻塞地在多个共识组间接力执行，使得多个原子交易可以完全并行地重叠交错执行，使得多个交易可以完全并行地重叠交错执行，这样 Monoxide 系统的全网吞吐能力就得以完全释放，即使再多的跨共识组的交易也不会显着影响性能。
我们即使假设100%的交易都是跨共识组的交易，一个支付交易将会变成两个交易，粗略地说，会使吞吐量减半。但是这个开销，和共识组的总数无关。当全网性能获得几个数量级的提升时，这个开销始终是吞吐量减半。故而，在我们的实验中，2048个共识组能够获得近1000倍的吞吐量提升。基于最终原子性的执行逻辑，需要初始操作和接力操作满足前述的正确性约束，否则可能导致不一致的最终状态。诚然，这会对Monoxide平台上的智能合约开发带来一些难度。不过我们认为这是一个不可避免的代价，就好像给GPU写代码，给OpenMP写代码或者是给Hadoop写代码，就是会比给单机单线程的CPU写代码要困难一些，思路上要绕一些。当然，结合恰当的合约语言模型、形式化验证工具，以及开发和调试工具的支持，开发的难度也会大大减少。
Oxidation语言是Monoxide平台的智能合约语言，一种基于函数编程(Functional programming)的语言。这个语言模型的设计并不是论文的一部分，这部分工作也尚未全部完成。这里给出一个类似ERC20代币合约的极度简化示例代码。这里比较特殊的是系统调用yield。这个调用将在合约执行的过程中生成接力交易，如果b为一个跨共识组的地址的话。代码中可以出现多个yield调用，也可以有条件地调用yield，但是yield调用不允许重入。
伸缩性的上限: 为什么说区块链不可能三角被突破了
为了正确完成跨共识组交易，接力交易的权限校验需要接收到发起方所在的共识组的对应的块头。这件事情成为了Monoxide全网伸缩性的最主要瓶颈。这意味着，每个全节点都需要同步并跟踪所有共识组中的块头，同时加上连弩挖矿机制，这个同步消耗的带宽为:
( BlockHeadSize + 32 × log_2 n ) × n / BlockInterval
BlockHeadSize为块头的元数据，大致120字节。这个部分不定长，是因为Monoxide采用可变长度的Nonce，以适配不同的挖矿难度。32 × log_2 n 部分为连弩挖矿机制引入的算力证明，即前文的 MerkleTreePath_i。BlockInterval为出块间隔。基本上，这是一个 O(n log_2 n)的开销，只要n大到一定程度，性能的提升会低于这个开销的增加，从而定义了伸缩性的天花板。
既然，每个全节点都需要同步并跟踪所有共识组中的块头，我们将给出另一种连弩挖矿的出块数据结构，改为一次出所有的块头，而不是按逐个共识组出块头，不可用的块头(哈希难度未达到挖矿难度的)用其哈希值代替。当然区块本身仍旧是逐个共识组分开广播的。同时为了实现这个优化，我们将引入一个全局的特殊广播子网，仅用来传播块头或者成批的块头，并要求所有全节点和挖矿节点加入这个特殊的广播子网。这样就可以省去原先每个块头的算力证明部分，将带宽消耗将降到 O(n):
BlockHeadSize × n / BlockInterval
即使优化之后，对于每个全节点来说，这仍旧是一个不容忽视的开销。n总能大到一定程度，使得本地带宽被耗尽。
那么我们来推演一下这个天花板到底是多少。假设约束全节点带宽为15Mbps，即上限为1.88MB/s。以Bitcoin协议为基础，我们设定其出块间隔为1分钟，出块大小为8MB。这样单个共识组单链吞吐量将约为560 TPS，区块传输开销为 0.13MB/s。当共识组数量为65536个的时候，全网块头传输开销也为0.13MB/s。加起来也远小于带宽上限，也远小于带宽上限，有足够的剩余带宽用于下行广播。然后，这个时候全网吞吐量约为15M TPS 左右，状态容量在几百 TB 的数量级。无论是再多的共识组总量，还是再高的共识组单链吞吐量，都会逐渐使得全节点本地带宽显得局促。
所以，我们认为Monoxide的伸缩性天花板大致在这个水平，千万TPS的吞吐量和几百TB的状态容量。千万TPS这个数量级，已经可以应付大部分互联网级别应用的峰值流量，同时仍旧满足区块链对安全和去中心化的要求，这就是为什么我们说，区块链不可能三角被突破了。 当然，要伸缩到这个程度，也需要整个社区的总参与节点数到达百万数量级。
末了，欢迎大家通过我的微信公众号「王嘉平」和知乎专栏「去中心化数字世界随想」，就这个话题展开更多讨论。
作者简介: 王嘉平博士原为微软总部雷德蒙研究院主管研究员，专注分布式系统，计算机图形学和视觉以及用于机器学习的GPU集群等领域的研究，有数十项研究成果发表于ACM SIGGRAPH/ToG顶级国际期刊，已授权的美国专利十项余项。他师从沈向洋博士(现微软全球执行副总裁)，在中科院计算所获得博士学位。他的博士论文获得2009年度全国百篇优秀博士论文奖，是该年唯一一名计算机科学专业的获奖者。
本文为作者个人观点，与就职单位无关。
