王嘉平 林佳谊
导言：
过去一两年有许多号称区块链 3.0 的公链项目都宣称克服了所谓不可能三角，但大体而言，至今尚未出现一个具信服力、并广为接受的解方。不过，由分布式系统专家王嘉平等人提出的 Monoxide 扩容方案，近日获计算机顶级学术会议 NSDI 2019 收录。这是继 2017 年著名的 AlgoRand 项目登上 SOSP 大会后，睽违近两年再有区块链公链论文投中计算机顶会。
王嘉平为微软总部研究院前主管研究员，专注于分布式系统等领域研究。2016 年起他在创新工场担任执行董事，负责区块链和人工智能等投资方向，曾主导了对比特大陆的首轮机构投资，成为三大主要投资方之一。去年他曾发表“区块链到底有什么了不起”等系列文章，梳理出为什么他相信区块链是一项了不起的技术，在行业内引发广大回响。DeepTech 很高兴邀请到王嘉平博士成为 DeepHash 专栏作者，这是他除了个人公众号外首度在媒体上开设专栏。他将在以下的首篇专栏文章中，披露 Monoxide 具体是如何突破区块链不可能三角的，包含其研究中提出的“连弩挖矿”与“最终原子性”两个重要创新。
文/王家屏
图| mono:用异步共识组扩展区块链(图片来源：王家屏)
上图是我们的报纸，将用于NSDI场馆海报展示环节的海报。本文将根据poster的逻辑介绍mono的设计架构和实现原理。虽然mono架构可以采用不同的共识算法作为其共识组中的共识机制，但本文将基于最简单、最干净的Satoshi Nakomoto共识算法(Proof-of-Work)进行讨论。
mono将满足安全,性能和去中心化.这三个区块链的需求。这里应该强调的是，mono是第1层的区块链技术，它不假设事务结构的任何本地特征，也不假设跨共识组的事务会更少。
第一角：怎么样算安全
同时，区块链系统必须是安全的，这一点是不容妥协的，否则所有其它特性将毫无意义。具体落实到技术指标，就是在系统中构造一个非法区块并得到全网认可所需付出的代价。这个代价就 PoW （工作证明）共识机制而言，就是实施攻击的最小挖矿算力。Nakomoto 共识算法保证恶意算力在50% 以下的时候，系统是安全的。我们保证的是采用 Monoxide 架构之后，这个 50% 算力的安全边界不会显着变低。,我们继承了Nakomoto算法的其他安全特性，所以不要发现block节点一直在线，所有节点的物理IP地址只在小范围内暴露。
第二角：怎么样算高性能
Monoxide 架构将完全隔离每个共识组的四大工作负荷，即：带宽（广播区块数据和未确认交易）、计算（验证交易和更新账簿状态）、内存（存储账簿的最新状态）、磁盘读写（记录历史区块）。我们强调这四个方面的负荷必须全部被切分隔离，才能真正获得高伸缩性的区块链系统，而不是仅完成部分工作符合的隔离，即所谓的网络分片，交易分片和状态分片。
具体落实到技术指标，性能包含两个方面。一个是众所周知的吞吐量，即 TPS，而另一个是全网表达账簿状态的总有效内存总量。前者是速度，后者是容量。
这里，我们实现了吞吐量大致 n/2 倍的线性提升以及状态容量的 n 倍的线性提升。中的n是共识组的数量，改进是在共识组中使用的单链共识系统的性能。现在实现几百TPS，几十GB状态空间的吞吐量，还是比较容易的。注意，这并不是说一氧化碳可以无限地提高性能。在现有平均互联网带宽(15Mbps)的约束下，共识群N的数量最高只能达到数万。
第三角：怎么样算去中心化
首先，公链必须是 permissionless 系统，并且系统中不存在不可替代的角色或者节点，这是一个定性的要求。在满足这个要求之后，去中心化可以落实到具体的技术指标，即需要多少 IT 资源才能顺利地参与全网的监管（部分或者全部），也就是全节点的参与门槛。
而这个门槛最关键的因素是带宽，高带宽只有部署在数据中心才能获得，其链路的地理位置也容易被追踪；而其它资源诸如 CPU、内存、磁盘等，都可以不受特定地理位置的约束，也无法追踪，花点钱就有
。Monoxide 架构在获得几个数量级的性能提升的同时，始终将全节点带宽消耗控制在普通家用互联网接入可以承受的范围（< 15Mbps），从而使得 Monoxide 的全节点可以像以太坊全节点一样，随便在家里找个普通电脑就开起来。同时 Monoxide 的共识组划分了历史交易归档的工作量，使得完整同步一个全节点的时间会比现在的以太坊少几百倍。强调全节点进入门槛的原因是，只有全节点才能够在不信任其它节点的情况下，独立验证交易，重建账簿状态，而不是像云计算那样，需要依赖于信任特定的节点（或服务器），这是区块链和云计算的本质区隔之一。
小标：Monoxide 的总体设计
图｜ Monoxide 总体设计（来源：王嘉平）
总体来说，Monoxide 的设计哲学是尽量简单，在能满足上述三角特性的前提下，尽量不引入额外的实体，不引入额外的机制。Monoxide 网络是一个并发的多链系统，每一个链我们称之为"共识组"。
每个"共识组"其组成部分和现在单链系统完全一致，有自己的账簿状态，区块的链条，未确认交易的集合，同步区块数据和交易数据的广播网络以及一堆全节点（包括矿工）。各个共识组之间完全对等，无主次之分，除此之外这个网络就没有任何其它的角色了，没有之前那些方案提出的母链，根链之类的，也没有任何掌控全局的调度节点或验证节点。引入这些实体会使得一些功能更容易实现（例如动态负载平衡），但是他们会牺牲去中心化特性，甚至还可能导致严重的性能瓶颈。
全网所有共识组用一个整数编号（0到n-1），我们限定共识组的总个数为 2 的 k 次幂，即n=2^k。任何一个账簿地址，根据其地址二进制数据的前 k 个比特，永久地被分配在一个共识组中。每个交易则根据交易的验证方的地址（例如转账交易的支付方），被分配在验证方所属的共识组。所以 Monoxide 网络的划分不需要任何中心化的机制来分配地址和交易。
Monoxide 全网由各个共识组的出块和未确认交易集合完全独立，共识组之间完全并行、异步也无需锁定和同步，即使某一个共识组发生拥塞也不会干扰其它共识组的吞吐和出块。
Monoxide 全网由各个共识组的广播子网所构成，但这些广播子网互相不重叠、不打搅。在我们的设计中，这些广播子网由 DHT 的 Swarm 实现，每一个广播子网对应一个 Swarm。新启动的全节点根据自身所在共识组编号，利用 DHT 的路由机制找到同一共识组里面的其它全节点，并尝试连接。
全节点可以随机选择加入任意一个或多个共识组，或由上层应用来决定。例如，钱包节点通常会加入登录用户的钱包地址所在的共识组，以便维护其账户余额等状态。Monoxide 不记录任何用户登录状态或用户私钥，以避免以太网全节点之前出现的 RPC 接口安全隐患。除非其上层应用要求，通常一个共识组的全节点不会主动连接另一个共识组的节点。
同样矿工可以自由选择参与一个或多个共识组，进行挖矿，以期获得每一个共识组中的出块奖励。正常情况下，矿工会优先选择参与当前算力较低的共识组，以获得更高的利润，从而导致各个共识组会收敛到一致的挖矿算力和出块难度。
1. 安全：只要各个共识组本身是安全的，Monoxide 就会是安全的。交易的安全和正确（例如避免双花）依赖于每个共识组内部的共识机制。Monoxide 全网对女巫攻击（Sybil Attack）也依赖于共识组内部的共识机制本身的抵御能力。就 PoW 而言，每个共识组的安全，依赖于其内部挖矿算力。所以 Monoxide 架构的安全保障，核心是要能够抵御算力分散的问题，即全网算力分散到每个共识组之后，每个共识组的算力将是全网的 1/n，这时单个共识组的防御壁垒将下降到 51/n %。这将是一个完全无法接受的值。为了解决这个算力分散的问题，Monoxid 引入了”连弩挖矿”（Chu-ko-nu Mining），使得单个共识组的防御壁垒回升到 51%。
2. 性能：由于各共识组的区块验证、存储和账簿状态更新完全独立，所以这三个方面将获得无代价的无限线性提升。共识组之间唯一需要打交道的地方，就是为了正确处理跨共识组的交易。在数据传输上面，性能提升是有代价的。为了高效完成跨共识组交易，Monoxide 引入了最终原子性（Eventual Atomicity），使得即使全网跨共识组交易的比例接近 100% 的时候，仍旧可以轻松地完成交易吞吐，性能损失为一个和共识组个数无关的常数。
3. 去中心化：根据上面的描述，Monoxide 依旧是一个彻底的 permessionless 的系统，并且每个共识组内部的全节点的负担始终保持在同维护一个单链系统相当的水平，可以被轻松部署。
所以论文最重要的两大技术贡献就是”连弩挖矿”（Chu-ko-nu Mining） 和”最终原子性”（Eventual Atomicity）。后面我们将就这两个方面，详细展开，并以 Bitcoin （比特币）数据结构蓝本，给出这两个机制对 PoW 共识协议的改进。
在 PoW 共识机制中，矿工需要不断随机刺探块头中的 Nonce （随机数值）并重算哈希函数，以使得这个块头的哈希值满足当前算力难度的要求，可以最终出块。这个过程的瓶颈在于计算哈希函数的速度，所以挖矿算力被定义为哈希速率（Hashrate）。这里，我们将实际计算哈希的速度，定义为物理算力（Physical Mining Power），提高物理算力的唯一方法就是部署更多的矿机，消耗更多的能源。
然而，在 PoW 共识机制中，每个矿工的物理算力是无法直接知道的，这个物理算力最终体现为特定挖矿难度下的出块速度。全网算力统计也是基于这个出块速度而反算哈希速率而估计到的。
在发生算力攻击的时候，无论是最长链，还是最难子树（Ghost协议），都是按照依据各个分叉上出块的数量和难度而定，而非各个矿工的实际哈希速率。我们将这个依据挖矿难度和出块速度反算出来的哈希速率，定义为连弩挖矿”（Chu-ko-nu Mining）。当然在单链系统中，有效算力和物理算力，在统计意义上来说是完全相等的。
前面提到的算力分散问题是这样的一个攻击模型：在有 n 个共识组的 Monoxide 系统中，全网有效算力为 H，每个共识组的有效算力为 H/n。攻击者在实施攻击的时候，将其所有物理算力 T 分配到一个特定共识组，在这个共识组中获得有效算力T。那边当其物理算力超过 T > H/n × 51% 的时候，攻击将可以成功，并构造不一致交易（例如双花交易）。
为了抵御这个算力聚焦的攻击模型，我们的思路是强制矿工将算力分散到各个共识组，并且无法集中算力到特定共识组。但在一个去中心化的 permissionless 系统中，我们无法控制矿工如何分配其物理算力。
因此，Monoxide 引入了连弩挖矿，其效果是将使得全网的有效算力放大为物理算力的 n 倍，并且在协议的数据结构层面再约束了这种放大后的有效算力必须平均分配到各个共识组，从而规避了这种算力聚焦的攻击模型。
连弩挖矿允许矿工同时参与多个编号连续的共识组（例如从编号b到b+m-1），每次出块的时候哈希函数将覆盖多个将要出块的块头进行计算，同时这些块头将共用一个 Nonce。具体做法是将这个 m 个块头按序排列，构造 Merkle 树。然后算力哈希计算将覆盖下列数据结构：
<MerkleRoot, b, m, Nonce>
出块时，下列数据结构会被广播到特定的共识组 i （b≤i<b+m），仅包含该共识组的块头以及一个该块头被包含在内的证明，不涉及到其它共识组的块头。
<MerkleRoot, b, m, Nonce, Blocki, MerkleTreePathi>
其 MerkleTreePathi 是 Blocki 在 Merkle 树路径上的左右兄弟节点的哈希值，需要 32 × log2 m 个字节。注意这里没有显式给 Blocki 在 Merkle 树中的位置，而是需要 Blocki 中的共识组编号减去 b 推算出来，这样做是为了约束连弩挖矿出块的时候，每个共识组只能出一个块。
这里需要提一下联合挖矿（Merge Mining），在允许矿工同时参与多条链的挖矿这一点上，是很类似的。但是连弩挖矿设计初衷和工作场景和联合挖矿完全不同，前者是为了放大有效算力，并强制放大后的算力均分在各个共识组，以防止算力集中攻击特定共识组。而后者是为了借用大算力的链，来保证小算力链的安全。
从这个结构中可以看到，即使在连弩挖矿的情况下，各个共识组也不会受到其它共识组出块情况的影响。连弩挖矿并不要求各个共识组同步接受这些块，甚至有些块最终被认为是无效分叉，也不会影响其它块在其它共识组中被接受。同时，这个结构允许连弩挖矿是可以包含算力难度不同的共识组，一旦部分共识组的出块难度被满足，这些部分的块就可以优先出去。
连弩挖矿将矿工有效算力放大，同时也放大了单位物理算力可以获得的出块奖励，同样的物理算力，同样的能源消耗，参与到越多的共识组挖矿，所获得的出块奖励也会越多。所以，全网会收敛到主流的矿工都会采用连弩挖矿，并且参与到所有的共识组中。从而，使得全网的有效算力达到 H × n，单个共识组的有效算力达到 H 。这样使得攻击单个共识组的物理算力要求和攻击全网的物理算力相当。
同时参与到多个共识组挖矿，需要更多的 IT 资源用来同步和验证每个共识组的交易和区块（不仅仅是块头），也需要更多的磁盘存储和内存。基于去中心化的考虑，参与连弩挖矿与否，以及参与的共识组个数是一个矿工可以自行配置的选项，Monoxide 并不要求所有矿工都参与所有共识组的挖矿。
同时，得益于共识组独立性，一个参与所有共识组挖矿的矿场，很容易在内部实现一个分布式的挖矿数据中心，用不同的主机监控各个共识组，用不同主机确认交易构造新区块，然后在内部的高速网络中汇总这些块头的哈希（Merkle的叶节点），并送给矿机集群。参与更多的共识组会线性增加开销，但是这个和大型矿场的矿机开销来说，就可以忽略不计了。
在我们的实验中，当共识组数量达到 64 的时候，跨共识组交易的比例已经超过了 95% （实验的测试数据为以太坊 ERC20 的历史交易记录）。Monoxide 引入了最终原子性来实现高效的跨共识组交易处理，使得每个跨共识组交易带来的额外开销是一个常数，并且和共识组数量 n 无关。
区块链系统，每一个交易都是一个原子操作。在单链系统中，就好比单线程，这个原子操作并没有被强调，因为交易本来就是被一个一个地确认和处理，系统无需任何额外的事情，原子性就自然有保障。而在 Monoxide 中，不同地址的状态在不同共识组中维护，互相不可见，其状态的更新也被两个不同的链驱动，就好比多线程。
一个原子操作要在这样的架构下正确安全地完成，就不是一个简单的事情了。通常为了协同多线程，我们有两种办法，一个是互相对涉及的资源加锁，一个是借由消息传递。我们选择了后者，不仅是因为加锁将阻塞对应的共识组的吞吐，严重影响性能，也是因为所有的单链区块链天生就有一个消息传递机制（未确认交易集合），从而避免引入新的实体。
我们先以最简单的支付交易为例，介绍我们的设计。一个数量为 x 的从地址 A 到地址 B 的支付交易，并且 A 和 B 处于不同的共识组。这是一个原子操作，其中包含一个扣款操作，这个操作有条件，并且不同的执行顺序会导致不同的状态。另一个是存款操作，这个操作无条件，并且不同的执行顺序不会导致不一致的最终状态。
对于这样的逻辑，Monoxide 将现在共识组 A 中，尝试完成扣款操作。如果成功，则将向共识组 B 发生一个接力交易，一种特殊的未确认交易。接力交易和普通未确认交易一样，描述了用什么参数，调用哪个智能合约里面的函数。和普通未确认交易不同的是权限校验方式。普通未确认交易，通常由钱包签发，通过其携带数字签名来校验权限。而接力交易携带的是来自另一个共识组的出块证明：
<ZoneId, Height, RelayMerklePatht, t>
为了校验这个接力交易，共识组的块头将包含两个 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 调用不允许重入。
（ BlockHeadSize + 32 × log2 n ） × n / BlockInterval
BlockHeadSize 为块头的元数据，大致 120 字节。这个部分不定长，是因为 Monoxide 采用可变长度的 Nonce，以适配不同的挖矿难度。32 × log2 n 部分为连弩挖矿机制引入的算力证明，即前文的 MerkleTreePathi。BlockInterval 为出块间隔。基本上，这是一个 O（n log2 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/ToG顶级期刊以及已授权的美国专利。他师从沈向洋博士，在中科院计算所获得博士学位。他的博士论文获得2009年度全国百篇优秀博士论文奖，是该年唯一一名计算机科学专业的获奖者。王嘉平博士现任创新工场执行董事，投资方向为区块链和人工智能。他曾主导了对比特大陆的首轮机构投资，成为其首轮三大主要投资方之一。
关于 DeepHash 专栏 / 每周二
文／林佳谊
“区块链技术非常复杂，而且有很多误解。更可怕的是，很多人自认为了解区块链技术，但表现出的却是无知。学术机构有着巨大的责任去培养下一代的创新者。”在杜克大学商学院开设区块链课程的教授 Campbell Harvey 曾经有感而发地说。
每项新兴技术发展都有它的周期，愈是可能带来重大变革的技术，这个周期往往也愈明显。就在区块链技术步入所谓“幻灭的低谷”之时，DeepTech 深科技认为，下一个产业风口，如今正在每个顶尖高校的实验室、在各国央行与监管机构的研究室，在行业组织的研讨会中酝酿着。
DeepTech 深科技认为，此时才是关键时刻，身为一家坚持深入报道科学科技产业的专业媒体与科技服务提供者，我们有责任也有必要，在这个时点上有带领读者去拨开迷雾、厘清误解，培养对区块链技术的更深刻认知。
因此我们于每周二固定推出 DeepHash 专栏，由 DeepTech 资深编辑林佳谊，邀集千人学者兼天德链创始人蔡维德、分布式系统专家王嘉平、物联网区块链初创 Biilabs 创始人朱宜振等专家学者共同维护，每周一次，带领读者在技术研发、在法规政策、在行业标准，在国际趋势，方方面面深入挖掘未来 3-5 年真正具有产业化潜力的区块链知识。
