王嘉平x 林嘉怡
介绍：
近一两年，不少自称区块链3.0的公链项目都声称已经克服了所谓的不可能三角，但总体而言，尚未出现令人信服且被广泛接受的解决方案。不过，分布式系统专家王家平等人提出的Monoxy扩容方案近日被计算机顶级学术会议NSDI 2019收录。这是继2017年著名的AlgoRand项目在SOSP会议上提出后，近两年来第二次向计算机会议提交公共区块链论文。
王家平是原微软总部研究院首席研究员，专注于分布式系统等领域的研究。 2016年起担任创新工场执行董事，负责区块链、人工智能等投资方向。曾领投比特大陆首轮机构投资，成为三大投资人之一。去年，他发表了《区块链有什么了不起》等一系列文章，梳理了为什么他认为区块链是一项了不起的技术，引起了业界的广泛反响。 DeepTech很荣幸邀请王家平博士成为DeepHash的专栏作家。这是他第一次在个人公众号以外的媒体上开设专栏。在他的第一篇专栏中，他将披露Monoxy如何突破区块链的不可能三角，包括他在研究中提出的“持续挖矿”和“终极原子性”两项重要创新。
Monoxy：突破区块链不可能三角的极简架构
文/王家平
图| Monoxy：通过异步共识组扩展区块链（来源：王家平）
上图是我们的论文将在NSDI 会场的海报展示会上使用的海报。本文将顺着发帖者的逻辑，介绍一下Monoxy的设计架构和实现原理。虽然Monoxy架构可以使用不同的共识算法作为其共识组内的共识机制，但本文将基于最简单、最干净的Nakomoto共识算法（工作量证明）进行讨论。
Monoxy将同时满足区块链安全、性能和去中心化三大需求。这里需要强调的是，Monicide是Layer 1区块链技术，并没有假设交易结构有任何局部特征，也没有假设跨共识组的交易会减少。
什么是区块链不可能三角？角一：如何确保安全
区块链系统必须安全，这一点不容妥协，否则所有其他功能都将毫无意义。具体落实到技术指标上，就是在系统中构建一个非法区块并得到全网认可所需的价格。就PoW（Proof of Work）共识机制而言，这个价格就是实施攻击所需的最低算力。 Nakomoto共识算法保证恶意算力低于50%时系统安全。我们保证的是，采用Monoxy架构后，50%算力的安全裕度不会变得明显降低。同时，我们继承了Nakomoto算法的其他安全特性，不需要出块节点始终在线，全节点的物理IP地址仅在小范围内暴露。
第二角度：如何计算高性能
Monoxy架构将每个共识组的四大工作负载完全隔离，分别是：带宽（广播区块数据和未确认交易）、计算（验证交易和更新账本状态）、内存（存储账本最新状态）、磁盘读取写入（记录历史区块）。我们强调这四个方面的负载必须全部进行划分和隔离，才能真正获得高扩展性的区块链系统，而不是只完成部分工作来满足隔离的要求，即所谓的网络分片、交易分片和状态分片。片。
具体落实到技术指标上，性能包括两个方面。一个是众所周知的吞吐量（TPS），另一个是整个网络中代表账本状态的总有效内存。前者是速度，后者是容量。
我们在吞吐量方面实现了大约n/2 倍的线性改进，在状态容量方面实现了n 倍的线性改进。这里n是共识组的数量。该改进是相对于共识组内使用的单链共识系统的性能而言的。现在可以轻松实现几百TPS的吞吐量和几十GB的状态空间。请注意，这并不意味着Monoxy 可以无限提高性能。在现有互联网平均带宽（15Mbps）的限制下，共识组n的数量最多只能达到数万个。
第三角：如何计算去中心化
首先，公链必须是一个无需许可的系统，系统中不存在不可替代的角色或节点。这是一个质的要求。满足这个要求后，去中心化可以落实到具体的技术指标上，即需要多少IT资源才能成功参与整个网络（部分或全部）的监管，这就是全节点的参与门槛。
该阈值中最关键的因素是带宽。只有部署在数据中心才能获得高带宽，并且也可以轻松跟踪其链路的地理位置。其他资源，如CPU、内存、磁盘等，则不受特定地理位置的限制。约束也是无法追踪的，并且只需花费一点钱即可获得。
在实现几个数量级性能提升的同时，Monoxide架构始终将全节点的带宽消耗控制在普通家庭上网可以承受的范围内（15Mbps），使得Monoxide全节点可以像全节点一样在任何地方使用以太坊。家里找一台普通电脑启动就可以了。同时，Monoxy的共识组划分了历史交易归档的工作量，使得完全同步一个全节点的时间将比当前以太坊缩短数百倍。之所以强调全节点的进入门槛，是因为只有全节点才能独立验证交易并重构账户状态，而不需要信任其他节点，而不是像云计算那样依赖于信任特定的节点（或服务器）。这是区块链和云计算的本质区别之一。
下注：Monoxy整体设计
图| Monoxy总体设计（来源：王家平）
总的来说，Monoxy的设计理念是尽可能简单，在满足上述三角特性的同时，尽量不引入额外的实体或机制。 Monoxy网络是一个并发的多链系统，每条链被称为“共识组”。
每个“共识组”的组成部分与当前的单链系统完全相同。它有自己的账本状态、区块链、一组未确认的交易、用于同步区块数据和交易数据的广播网络，以及一堆全节点（包括矿工）。每个共识组都是完全平等的，没有优先级。除此之外，该网络中没有其他角色。不存在之前计划提出的母链、根链等，也没有人掌控全局。调度节点或验证节点。引入这些实体会让一些功能更容易实现（例如动态负载均衡），但它们会牺牲去中心化特性，甚至可能造成严重的性能瓶颈。
全网所有共识组均以整数（0到n-1）编号。我们将共识组的总数限制为2的k次方，即n=2^k。任何账本地址都会根据其地址二进制数据的前k位永久分配到一个共识组中。每笔交易都会根据该交易的验证人地址（如转账交易的付款人）分配到该验证人所属的共识组。因此，Monoxy网络的划分不需要任何中心化机制来分配地址和交易。
整个Monoxy网络完全独立于每个共识组的区块生产和未确认交易集。共识组是完全并行和异步的，无需锁定和同步。即使某个共识组拥塞，也不会干扰其他共识组的吞吐量和输出。片。
整个Monoxy网络由每个共识组的广播子网组成，但这些广播子网彼此不重叠或干扰。在我们的设计中，这些广播子网是由DHT的Swarm实现的，每个广播子网对应一个Swarm。新启动的全节点利用DHT的路由机制，根据自己的共识组号寻找同一共识组内的其他全节点，并尝试连接。
全节点可以随机选择加入任意一个或多个共识组，也可以由上层应用决定。例如，钱包节点通常会加入登录用户钱包地址所在的共识组，以维护其账户余额等状态。 Monoxy不会记录任何用户登录状态或用户私钥，以避免以太网全节点之前出现的RPC接口安全风险。除非上层应用需要，通常一个共识组的全节点不会主动连接另一共识组的节点。
同样，矿工可以自由选择参与一个或多个共识组进行挖矿，以获得每个共识组的区块奖励。一般情况下，矿工为了获得较高的收益，会优先参与当前算力较低的共识组，导致各个共识组收敛到相同的挖矿算力和区块难度。
Monoxy如何突破区块链不可能三角？从这个设计中，我们可以看出，Monoxy架构满足了区块链三角。
1.安全性：只要每个共识组本身是安全的，Monoxy就是安全的。交易的安全性和正确性（例如避免双重支出）依赖于每个共识组内的共识机制。 Monoxy全网对Sybil Attack的抵抗力还依赖于共识组内共识机制本身的抵抗力。就PoW 而言，各个共识组的安全依赖于其内部算力。因此，Monoxy架构的安全保障核心是能够抵抗算力分散的问题。即全网算力分配到各个共识组后，每个共识组的算力将是全网的1/n。此时，单个共识组的防御壁垒将下降至51/n%。这将是一个完全不可接受的值。为了解决分布式算力的这个问题，Monoxy推出了“Chu-ko-nu Mining”，将单个共识组的防御壁垒提升至51%。
2.性能：由于每个共识组的区块验证、存储和账本状态更新是完全独立的，因此这三个方面将在不产生任何成本的情况下获得无限的线性改进。共识组之间唯一需要处理的就是正确处理跨共识组的交易。在数据传输方面，性能的提高是有代价的。为了高效地完成跨共识组交易，Monride 引入了最终原子性（Eventual Atomicity），使得即使在全网跨共识组交易比例接近100% 的情况下，交易吞吐量仍然可以轻松完成，具有性能上的优势。丢失一个和共识组与数字无关的常数。
3、去中心化：根据上面的描述，Monoxy仍然是一个完全无需许可的系统，每个共识组内的全节点的负担始终保持在与维护单链系统相同的水平，并且可以轻松部署。
因此，论文最重要的两个技术贡献是“Chu-ko-nu Mining”和“Eventual Atomicity”。稍后我们将详细展开这两方面的内容，并利用比特币数据结构蓝图来呈现这两种机制对PoW 共识协议的改进。
“Chu-ko-nu Mining”（Chu-ko-nu Mining），放大有效算力
在PoW共识机制中，矿工需要不断随机探测区块头中的Nonce（随机值）并重新计算哈希函数，使区块头的哈希值满足当前算力难度要求，最终才能出块产生的。这个过程的瓶颈是计算哈希函数的速度，因此挖矿算力定义为哈希率（Hashrate）。这里，我们将哈希计算的实际速度定义为物理算力。提高物理算力的唯一途径就是部署更多的矿机，消耗更多的能源。
然而，在PoW共识机制中，每个矿工的物理算力无法直接获知。这种物理算力最终体现在特定挖矿难度下的出块速度。全网算力统计也是根据出块速度和算力反算来估算的。
当算力攻击发生时，无论是最长链还是最难子树（Ghost协议），都是根据每个分叉上产生的区块数量和难度来决定的，而不是根据每个矿工的实际算力来决定的。我们将根据挖矿难度和区块生成速度计算出来的算力定义为Chu-ko-nu Mining。当然，在单链系统中，有效算力和物理算力，从统计上来说，是完全一样的。
前面提到的算力分散问题是一种攻击模型：在有n个共识组的Monoxy系统中，全网的有效算力为H，每个共识组的有效算力为H/n。当攻击者进行攻击时，他将自己所有的物理算力T分配给特定的共识组，并获得该共识组中的有效算力T。当其物理算力超过T H/n 51%时，攻击就会成功，并构造出不一致的交易（例如双花交易）。
为了抵御这种以算力为中心的攻击模型，我们的想法是迫使矿工将算力分散到各个共识组，而不能将算力集中到特定的共识组。但在去中心化的无许可系统中，我们无法控制矿工如何分配他们的物理计算能力。
因此，Monoxy引入了链奴挖矿，具有将全网有效算力放大到物理算力n倍的效果，并进一步将这种放大的有效算力约束在协议的数据结构层面上进行平均。分配给各个共识组，从而规避这种以算力为中心的攻击模型。
链奴挖矿允许矿工同时参与多个连续编号的共识组（例如编号b到b+m-1）。每次生成一个区块时，哈希函数都会覆盖多个要生成的区块头进行计算，同时这些区块会共享一个Nonce。具体方法是将m个区块头排列起来，构建一棵Merkle树。计算哈希计算将覆盖以下数据结构：
MerkleRoot、b、m、Nonce
当一个区块产生时，会向特定的共识组i（bib+m）广播如下的数据结构，该数据结构只包含该共识组的区块头以及包含该区块头的证明，并不包含该共识组的区块头和包含该区块头的证明涉及其他共识组的区块头。
MerkleRoot、b、m、Nonce、Blocki、MerkleTreePathi
其MerkleTreePathi是Blocki左右兄弟节点在Merkle树路径上的哈希值，需要32log2m字节。请注意，这里没有明确给出Blocki 在Merkle 树中的位置。相反，它是通过从Blocki 中的共识组编号中减去b 来计算的。这样做是为了限制连奴挖矿生产区块。每个共识组只能产生区块。一个街区。
这里需要提到合并挖矿，它很相似，就是允许矿工同时参与多条链的挖矿。然而，连奴挖矿的初衷和工作场景与联合挖矿完全不同。前者是放大有效算力，强制放大后的算力均匀分布在各个共识组中，防止集中算力攻击特定共识组。后者是借用算力大的链来保证算力小的链的安全。
从这个结构可以看出，即使在连奴挖矿的情况下，每个共识组也不会受到其他共识组出块的影响。链奴挖矿并不要求每个共识组同时接受这些区块。即使某些区块最终被认为是无效分叉，也不会影响其他共识组中其他区块的接受。同时，这种结构使得链努挖矿可以包含不同计算难度的共识组。一旦满足部分共识组的区块难度，可以先释放这些部分区块。
链努挖矿放大了矿工的有效算力，也放大了单位物理算力所能获得的区块奖励。在物理算力相同、能耗相同的情况下，参与挖矿的共识群体越多，获得的奖励就越多。区块奖励也会更大。因此，整个网络将趋于一致，主流矿工将使用链努进行挖矿并参与所有共识组。使得全网有效算力达到Hn，单个共识组有效算力达到H。这使得攻击单个共识组所需的物理算力相当于攻击单个共识组所需的物理算力来攻击整个网络。
同时参与多个共识组挖矿需要更多的IT资源来同步和验证每个共识组的交易和区块（不仅仅是区块头），也需要更多的磁盘存储和内存。基于去中心化的考虑，是否参与链努挖矿以及参与的共识组数量是矿工可以自行配置的选项。 Monox并不要求所有矿工都参与所有共识组的挖矿。
同时，得益于共识组的独立性，参与所有共识组挖矿的矿场内部可以轻松实现分布式挖矿数据中心，使用不同的主机来监控每个共识组，并使用不同的主机来确认交易结构产生新的区块，然后这些区块头（Merkle 叶子节点）的哈希值在内部高速网络中汇总并发送到矿机集群。参与更多的共识组会线性增加开销，但这与大型矿场的矿机开销相比，可以忽略不计。
“最终原子性”。在Monoxy 中，我们使用一种非常简单且去中心化的方式将用户和交易分配给共识组。我们并不试图降低跨共识组交易的概率。我们认为，使用事务结构局部性是第2 层技术的问题。全网性能越高、共识组数量越多，跨共识组交易的概率就越高。这不是一个可以回避的问题。
在我们的实验中，当共识组数量达到64个时，跨共识组交易的比例已经超过95%（实验的测试数据是以太坊ERC20的历史交易记录）。 Monoxy引入最终原子性来实现高效的跨共识组交易处理，使得每个跨共识组交易带来的额外开销是一个常数，与共识组数量n无关。
在区块链系统中，每笔交易都是一个原子操作。在单链系统中，就像单线程一样，并不强调这种原子操作，因为交易本来就是一笔一笔的确认和处理。系统不需要任何额外的东西，原子性自然就得到了保证。在Monoxy 中，不同地址的状态保存在不同的共识组中，并且彼此不可见。它的状态更新也是由两个不同的链驱动的，就像多线程一样。
在这样的架构下，要正确、安全地完成一个原子操作，并不是一件简单的事情。通常为了协调多线程，我们有两种方法，一种是相互锁定涉及的资源，另一种是传递消息。我们选择后者，不仅因为锁定会阻塞相应共识组的吞吐量并严重影响性能，还因为所有单链区块链本质上都具有消息传递机制（未确认的交易集），从而避免引入新的实体。
我们首先以最简单的支付交易为例介绍我们的设计。从地址A到地址B的一笔金额为x的支付交易，且A和B属于不同的共识组。这是一个原子操作，其中包含一个演绎操作。这个操作是有条件的，不同的执行顺序会导致不同的状态。另一个是存款操作，它是无条件的，不同的执行顺序不会导致最终状态不一致。
对于这个逻辑，Monoxy 现在将进入共识组A 并尝试完成推演操作。如果成功，B共识组会产生中继交易，一种特殊的未确认交易。中继交易与普通的未确认交易相同。它们描述了要使用哪些参数以及要调用智能合约中的哪些函数。与普通的未确认交易不同的是权限验证方式。普通的未确认交易通常由钱包发出，钱包带有数字签名以验证权限。中继交易携带来自另一个共识组的区块证明：
ZoneId、高度、RelayMerklePatht、t
为了验证这个中继交易，共识组的区块头将包含两个MerkleRoot。一种是现有的Merkle 树，覆盖该区块确认的所有交易，另一种是新的Merkle 树，覆盖该区块发送的交易。所有中继交易。后者将被其他共识组接收并用于验证它们发送的中继交易。
默认情况下，构建和转发中继交易是由确认初始交易的同一个矿工（在共识组A 中）完成的。如果转发失败，共识组A 中的任何全节点都有能力基于该初始交易从交易历史中重建和转发丢失的中继交易，而无需额外的共识或证明。
无论是中继交易还是普通的未确认交易，都会以类似的方式在目标共识组的广播子网中传播，并暂时存储在未确认交易集合中。矿工在生产区块时，会平等对待中继交易和未确认交易，通常会根据手续费进行优先级排序。对于任何生成一笔或多笔中继交易的初始交易，费用将在初始交易和多笔中继交易之间分配给最终在其他共识组中确认这些交易的矿工。在Monoxy 中，这个分配比例可以通过智能合约代码来控制。
从上面的过程我们可以看出，Monix系统中的交易原子性并不是立即满足的，而是在所有中继交易都被确认并执行之后才最终完成。我们称之为最终原子性，而不是要求立即原子性。
极致的原子性使得跨共识组的交易可以在多个共识组之间间接执行而不会阻塞，允许多个原子交易完全并行、重叠和交错执行，从而充分释放Monicide 系统的全网吞吐能力，即使没有金额跨共识组的交易量将显着影响性能。
即使我们假设100% 的交易都是跨共识组交易，一笔支付交易也会变成两笔交易，粗略地说，吞吐量会减半。但这个开销与共识组的总数无关。当整个网络的性能提高几个数量级时，这个开销总是使吞吐量减半。
因此，在我们的实验中，2048个共识组能够实现近1000倍的吞吐量提升。基于最终原子性的执行逻辑要求初始操作和中继操作满足前述的正确性约束，否则可能导致最终状态不一致。诚然，这会给Monoxy平台上智能合约的开发带来一些困难。然而，我们认为这是不可避免的代价。就像为GPU、OpenMP或Hadoop编写代码一样，比为单机单线程CPU编写代码更困难，而且思维需要复杂一些。当然，结合适当的合约语言模型、形式化验证工具以及开发调试工具的支持，开发难度也会大大降低。
Oxidation 语言是Monride 平台的智能合约语言，是一种基于函数式编程的语言。这个语言模型的设计并不是论文的一部分，这部分工作还没有完成。以下是类似于ERC20 代币的合约示例代码。这里的特别之处在于系统调用收益。如果b 是跨共识组的地址，则此调用将在合约执行期间生成中继交易。代码中可以出现多个yield调用，yield可以有条件调用，但yield调用不允许重入。
可扩展性上限—— 为什么说区块链不可能三角已经被打破？为了正确完成跨共识组交易，中继交易的权限验证需要接收发起者所在共识组对应的区块头。这件事情已经成为整个Monoxy网络可扩展性的主要瓶颈。这意味着每个全节点需要同步和跟踪所有共识组中的块头。同时，加上连奴挖矿机制，本次同步消耗的带宽为：
(BlockHeadSize + 32 log2 n ) n/块间隔
BlockHeadSize是块头的元数据，大约120字节。这部分是可变长度的，因为Monoxy使用可变长度Nonce来适应不同的挖矿难度。 32log2n部分是连奴挖矿机制引入的算力证明，也就是上面提到的MerkleTreePathi。 BlockInterval 是块间隔。基本上，这是一个O(n log2 n) 开销。只要n足够大，性能的提升就会低于这个开销的增加，从而定义了可扩展性的上限。
由于每个全节点需要同步跟踪所有共识组中的区块头，因此我们将修改链努挖矿的区块数据结构，一次性产生所有区块头，而不是逐一产生区块头。不可用区块头（哈希难度未达到挖矿难度）被其哈希值替换。当然，区块本身仍然是为每个共识组单独广播的。同时，为了实现这种优化，我们将引入一个全局特殊广播子网，该子网仅用于传播区块头或批量区块头，并要求所有全节点和挖矿节点加入这个特殊广播子网。这样就可以省略每个区块头的原始算力证明部分，带宽消耗将降低至O(n) :
区块头大小 n/区块间隔
优化后，这对于每个全节点来说仍然是不可忽视的开销。 N 总是足够大，以致本地带宽耗尽。那么我们来推断一下这个上限是多少。全节点带宽限制为15Mbps，即上限为1.88MB/s。基于比特币协议，我们设置出块间隔为1分钟，块大小为8MB。
这样，单个共识组的单链吞吐量将约为560 TPS，块传输开销为0.13MB/s。当共识组数量为65536时，网络块头传输总开销也为0.13MB/s。加起来后远小于带宽上限，有足够的剩余带宽用于下行广播。那么，此时整个网络的吞吐量约为15M TPS，状态容量在数百TB量级。无论共识组总数有多大，或者共识组的单链吞吐量有多高，全节点的本地带宽都会逐渐变得局促。
因此，我们认为Monoxy的可扩展性上限大致在这个水平，吞吐量可达数千万TPS，状态容量可达数百TB。在千万级TPS的量级上，已经可以处理大部分互联网级应用的峰值流量，同时仍然满足区块链的安全性和去中心化要求。这就是为什么我们说区块链不可能三角已经被打破了。当然，要扩展到这个级别，整个社区的参与节点总数需要达到百万量级。
本文为作者个人观点，与所在单位无关。
王家平
王家平博士曾任微软总部研究院首席研究员。他专注于分布式系统、计算机图形和视觉以及用于机器学习的GPU 集群领域的研究。数十项研究成果发表在ACM/ToG顶级期刊上并获得美国专利。师从沉向阳博士，并于中国科学院计算技术研究所获得博士学位。其博士论文荣获2009年全国百篇优秀博士论文奖，也是当年计算机专业唯一获奖者。王家平博士现任创新工场执行董事，投资方向为区块链和人工智能。曾领投比特大陆首轮机构投资，并成为其首轮三大投资人之一。
关于DeepHash专栏/每周二
文/林嘉怡
“区块链技术非常复杂，存在很多误解。更可怕的是，很多人自以为了解区块链技术，但实际上却表现出无知。学术机构肩负着培养下一代创新者的巨大责任。 ”在杜克大学商学院教授区块链课程的坎贝尔·哈维教授曾感慨地说。
每一项新兴技术的发展都有其周期。技术越有可能带来重大变革，这种循环就越明显。正当区块链技术进入所谓的“幻灭低谷”时，DeepTech认为，下一个行业趋势现在就在每一所顶尖大学的实验室里，在各国央行和监管机构的研究实验室里，在工业界里。组织。研讨会中酝酿。
DeepTech DeepTech认为，现在是关键时刻。
为一家坚持深入报道科学科技产业的专业媒体与科技服务提供者，我们有责任也有必要，在这个时点上有带领读者去拨开迷雾、厘清误解，培养对区块链技术的更深刻认知。
因此我们于每周二固定推出 DeepHash 专栏，由 DeepTech 资深编辑林佳谊，邀集千人学者兼天德链创始人蔡维德、分布式系统专家王嘉平、物联网区块链初创 Biilabs 创始人朱宜振等专家学者共同维护，每周一次，带领读者在技术研发、在法规政策、在行业标准，在国际趋势，方方面面深入挖掘未来 3-5 年真正具有产业化潜力的区块链知识。
