Monoxide - Scale Out Blockchain with Asynchronous Consensus Zones

| 分类 论文笔记  | 标签 区块链  分片技术 

Author: Jiaping Wang, Hao Wang. Link: https://www.usenix.org/conference/nsdi19/presentation/wang-jiaping

0x00 摘要

本文提出了一种新型的针对区块链系统的分片技术,并通过实验表明,在1200台虚拟机上运行48000个节点能够达到1000倍+的吞吐量和2000倍+的容量,相对于比特币和以太坊网络而言。所谓分片技术实际上就是将一条区块链中的数据进行分开存储,使得每个节点需要保存的数据变少。而本文提出的技术不仅能够降低每个节点的存储空间,同时还降低了通信和内存的开销,并且解决了两个核心问题:

  1. 跨区域交易验证,即交易的原子性。当一笔交易进行跨区域转账时,如何保证交易的原子性。
  2. 算力削减问题。按照一般的分片技术而言,矿工的算力被平均分配到了n个区域当中,每个区域的算力也就减少了,矿工只需更少的算力就可以控制整个区域的交易。

0x01 背景介绍

区块链性能提升需要解决的主要问题:

  • 区块之间有比较大的传输时间,用来保证网络的安全性,例如比特币中是10min,以太坊中是15s;
  • 所有的全节点都需要保存所有的交易、区块和整个网络的信息,提升了对全节点的要求,一定程度上会降低去中心化;

Asynchronous Consensus Zones (异步共识区域)

主要的想法是将整个区块链系统分割成多个独立并行的区域,称之为共识区域Consensus Zones)。整个网络的状态都将按照区域进行划分,所有的交易和区块都只在所属区域内进行传播,包括挖矿在内,每个区域都相当于是一条独立的链。这种设计有两个挑战:

  1. 在处理跨区域的交易时如何保证高吞吐量。
  2. 由于区域的划分导致矿工算力的分散,如何保证系统的安全性。

Cross-Zone Atomicity (跨区域原子性)

由于每个区块时相互独立的,如果一个交易只涉及到本区域内的地址,那么直接更新对应的地址的余额就可以;但是如果涉及到了两个区域的地址,例如从区域A的地址a发送到另一个地址b,但b属于区域B,那么就需要采用别的方法来保证交易的正确执行。

0x02 系统设计

首先来简要描述跨区域交易的主要过程,假设一笔交易要从区域A中的某一个地址向区域B中的某一个地址转一笔账,那么这笔交易会被分为两个部分:

  • Initiative transaction包含从区域A中的地址进行取款的操作;
  • Relay transaction包含从区域B中的地址进行存款操作。

其中Initiative transaction只存在于区域A,Relay transaction只存在于区域B,分别由两个区域内的矿工进行确认。采用这种方式可以使得跨区域的交易得到异步的验证,从而提升系统吞吐量。

区域划分和命名

在本系统中,每个用户都由一个地址来表示,系统将地址空间划分为$2^k$个区域,每个区域可以通过一个分片规模k和区域索引s来确定,其中$s \in {0,1,…,2^k-1 }$。每个用户所属的区域就可以直接通过地址的前k比特对应的数值来确定。

高效跨区域原子性

为了降低网络通信负载,系统将原来的一个区块分为两部分:

  • Chaining-block
    • 只包含原先区块的头部数据,例如前一个区块的hash,pow算出来的nonce等等;
  • Transaction-block
    • 交易的具体内容。

其中Transaction-block是由每个区域内部所有全节点保存,而Chaining-block则是由所有区域的所有的全节点保存。

那么现在我们可以来描述一个跨区域交易的详细过程,假设是从区域A中的地址a发送到区域B中的地址b,$\rho$ 表示取款操作,$\phi$ 表示存款操作,那么一个交易处理的流程如下:

  1. 首先由用户a在区域A中发起交易$<\rho,a,\phi,b>$,然后由区域A中的矿工验证该交易并开始构造区块;
  2. 区块的构造包含两部分:Chainning-block和Transaction-block,构造完成之后,区域A中的矿工便开始进行pow工作;
  3. pow解决之后,矿工便将Chainning-block在所有区域节点进行广播,将Transaction-block在区域内部广播;
  4. 跨区域交易中的$\rho$将被执行,并同时产生发向区域B的relay transaction $\psi := <\phi,b,\gamma>$,其中$\gamma$表示该交易在原始区块中的位置。

接下来由区域B进行相应的操作:

  1. 区域B中的矿工收到relay transaction $\psi$,首先验证它的原始的transaction-block,然后开始构造新的chaining-block和transaction-block,其中$\psi$就会被包含在区域B中的新的transaction-block中;
  2. 矿工进行pow工作,之后广播区块,并执行$\psi$中的存款操作$\phi$。

分叉处理

在交易的确认过程中,由于relay transaction需要依赖对应的initiative transaction,所以需要等待initiative transaction先被打包进区块,然后才能验证relay transaction交易的有效性。那么就会出现这样一种情况,relay transaction验证通过了并被打包进区域B中的区块了,但此时区域A中的原始区块由于分叉而变得无效了,此时系统采用的方法是区域B中的区块依然是有效的但是其中的relay transaction变得无效了,这需要重建区域B中的交易账本。

另一个问题是,区域B中的relay transaction变得无效了,那么依赖于次交易的所有交易都将变得无效,这将涉及到众多的交易的有效性的改变。为了避免这种情况,系统将依赖于relay transaction的交易延迟$\lambda$个区块执行,也就是说,如果一个交易依赖于某一个relay transaction,那么该交易至少在包含该relay transaction的区块之后$\lambda$个区块才会被执行。

0x03 Chu-ko-nu Mining 连弩挖矿

简单来说,连弩挖矿就是利用一个pow的解在多个区域创建区块,每个区域至多创建一个区块。在一般的挖矿算法中,对于n个区块头部$A_0,…,A_{n-1}$,矿工需要计算n个随机数$\eta_0,…,\eta_{n-1}$满足

而在连弩挖矿中,矿工只需要找到一个随机数$\eta_b$满足

其中,$h_0$是$(A_0,…,A_{n-1})$构成的Merkle树的根,$C$为该批区块的描述信息。当然,该不等式成立的前提是所有区域当前的难度是相同的;如果难度不同,本文采用的一个简单的办法就是不去管它,如果某个区域内的难度不同那么也就是说明上述不等式不成立,那么其他区域矿工计算的解不适合本区域。

0x04 思考

文章的主要内容已经介绍完毕了,首先来总结一下:

  • 存储结构上,将整条链划分成不同的区域(Zones),每个区域有自己单独的链,并同时会保存其他区域的chaining-block,但保存的其他区域的chaining-block不构成链;
  • 交易处理上,区域内部的交易就直接处理,跨区域之间的交易会被分成两部分,initiative transaction和relay transaction,分别会被打包进两个区域的不同区块;
  • 分叉处理上,每个区域内部使用GHOST协议,但由于跨区域交易之间的依赖性,导致其中一个区域中的区块失效时另一个区域中的区块也会失效,此时另一个区域就需要重新构建交易账本,跳过失效的交易。

总结完那么很容易发现系统存在的缺陷:

  1. 交易的依赖性导致的重构交易账本,虽然说可以通过设置checkpoint减少重构的区块数量,但是依然是个庞大的工作;
  2. 连弩挖矿需要收集其它区域的区块,但是根据系统的描述,其它区域的区块需要解决POW之后才会广播区块,如果这属于描述上的错误的话,那么就是说其它矿工在解决POW之前就会广播区块,那么矿工本身其实是没有任何收益的,它们又有什么动力去做这件事呢?
  3. 系统中矿工承担了绝大多数的重要的工作,虽然连弩挖矿解决了算力的问题,但是每个区域内的矿工的数量其实还是减少了,一部分恶意矿工的加入就可能导致区域内部的服务混乱,例如停止转发交易、恶意构造区块,而其它区域在进行连弩挖矿时并没有验证区块内部交易的有效性。

0x05 相关技术

  • Elastico:A secure sharding protocol for open blockchains. 2016 CCS.
  • OmniLedger: OmniLedger - A secure, scale out, decentralized ledger via sharing. S&P 2018.
  • Ethereum 2.0 The beacon chain.
  • RapidChain: RapidChain - Scaling blockchain via full sharding. 2018 CCS.

上一篇     下一篇