BrokerChain——基于“做市商账户”的区块链跨分片协议

论文信息：

Huawei Huang, Xiaowen Peng, Jianzhou Zhan, Shenyang Zhang, Yue Lin, Zibin Zheng, Song Guo, “BrokerChain: A Cross-Shard Blockchain Protocol for Account/Balance-based State Sharding”, INFOCOM, May 5, 2022.

文章目录

  • BrokerChain——基于“做市商账户”的区块链跨分片协议
    • 一、Background
      • 1. Motivation
      • 2. Challenges
      • 3. Contributions
    • 二、Preliminaries
      • 1. Sharding
      • 2. Related Work
    • 三、Solution
      • 1. Overview
        • 1.1 Two Shard
        • 1.2 Four sequential phases
      • 2. Account Segmentation
      • 3. mSST
      • 4. Handling cross-sharing TXs
        • 4.1 Broker account
        • 4.2 A success case
        • 4.3 A failure case
    • 四、Experiment
      • 1. Setting
      • 2. Main Experimental results
    • 五、Conclusion

一、Background

1. Motivation

区块链底层技术仍处于初期探索阶段，还面临着诸多问题和挑战。具体来讲，现有的区块链技术难以解决共识效率问题。例如，比特币的吞吐量为7 TXs/s 、以太坊的吞吐量也仅14 TXs/s，远低于商用级别所需的吞吐量要求。因此，需要提高区块链的可扩展性，才能扩大其使用场景，从而赋能数字经济、金融保险、政务等多个领域与行业。同时，目前区块链面临三难困境，没有一种区块链可以很好的同时实现可扩展性、安全性和去中心化。

针对区块链的可扩展性问题，研究人员提出了多种不同的技术方案，如闪电网络、DAG技术、状态通道和分片机制。其中分片机制是目前为止最有希望在保持高度去中心化特性的同时，可提高区块链可扩展性的链上扩容技术。分片机制将区块链网络划分为若干个互不相交的分片，每个分片只存储本分片内的数据而不是完整的账本状态，从而缓解存储开销；此外，多个分片间可以并行验证交易，产生区块，实现了吞吐量的近线性提升，有效提升了全网整体的事务处理性能。

2. Challenges

但是，区块链分片技术仍面临诸多挑战，片内共识、片间通信还有整个区块链分片协议等等方面还面临许多痛点难点，仍需要不断地进行研究和摸索。分片策略还停留在理论阶段，现有的分片方法依赖于UTXO（未使用的交易输出）或账户/余额交易模型。基于账户/余额模型的分片机制还存在如下主要挑战：

  1. 跨分片交易比例过高，几乎所有交易均为跨分片交易。过高的跨分片交易率不仅给系统增加了额外的交易负载，而且会造成大量的跨分片通信开销。
  2. 分片间的交易负载严重失衡，存在冷热不均的现象。我们分别称需要处理过量和少量交易的分片为热分片（Hot Shard）和冷分片（Clod Shard）。热分片由于被持续注入大量的交易，产生了交易拥挤的现象，这会增加交易的确认延迟。而冷分片内只有少量交易可以处理，所产生的区块的交易填充率不高，造成了算力、带宽等资源的浪费。

而对如上两个问题，一个难题是如何保证跨分片交易比例较低的同时保证分片间的交易负载均衡。

3. Contributions

  • BrokerChain, a cross-chard protocol
    • cross-shard TXs——broker, double nonce, and particle time state lock
    • hot-shard——state partition and account segmentation

BrokerChain利用动态的状态划分和账户分割机制，通过Broker账户处理跨分片TXs。既能在所有分片中实现交易负载均衡，也能减少跨分片TXs的比例。

二、Preliminaries

1. Sharding

目前的交易方法，主要有三种：网络分片 (network sharding)、交易分片 (transaction sharding) 以及状态分片 (state sharding)。

网络分片是基础，而状态分片是瓶颈。 网络分片和交易分片较早被提出，网络中的节点被分到不同的分片中，每个分片针对不同的交易子集进行处理、验证并达成共识。这样不同的交易子集可以被并行处理，各个分片之间也不必进行频繁的通讯。但是会带来存储空间消耗问题，系统的安全性也会越来越差。 因此提出了状态分片，不仅将网络和交易进行分片，将存储状态也进行分片。这样，每个节点只负责存储自己分片的数据，而不是完整的账本状态。

2. Related Work

为了提高区块链系统的可扩展性，研究人员提出了大量的区块链分片协议。Elastico被认为是第一个基于分片的区块链系统，在Elastico中每个分片并行处理TXs。现在最先进的分片解决方案，Monoxide，实现了基于账户/余额的区块链分片协议，利用新型的中继交易机制处理跨分片TXs。但是Monoxide协议还存在如下挑战：

  1. Monoxide根据账户分配机制减少TXs，根据用户账户地址的前几位划分到不同的分片中，旨在协同存储所有帐户状态。虽然这种方式可以提高系统吞吐量，但不可避免地会产生跨分片TXs。
  2. 通过引入接力交易（relay TXs）来确保分片交易的原子性。但是接力交易会导致分片的拥塞，大量TXs堵塞的碎片会造成热分片问题。在每个热分片中，TXs无法及时处理，可能会经历较长的确认延迟。
  3. 通过消息传递机制实现跨分片交易，并保证交易的原子性。但由于跨分片中继消息验证的存在，跨分片交易的延迟在理论上至少是片内交易时延的两倍。当位于目标分片内的关联交易迟迟无法上链时，跨分片交易的共识延迟有可能无限大。

为了减少跨分片TXs比例，实现分片之间的负载均衡，并且保证跨分片交易的原子性，本文旨在提出一种新的跨分片协议来提高分片区块链的吞吐量会降低交易的平均确认延迟。

三、Solution

1. Overview

BrokerChain协议以”Epoch“（时期）为单位运行区块链系统，Epoch为固定的片内共识轮次或者固定长度的时间。

1.1 Two Shard

本文采用BFT类共识协议作为片内共识协议，每个分片都通过PBFT协议来达成各自的块内共识并避免分叉。在BrokerChain中，根据职能的不同，存在两种不同类型的分片：工作分片（Mining shard，M-shard）和划分分片（Partition shard，P-shard）。它们分别负责处理不同的事务，具体分工描述如下：

  • M-shard在每个Epoch期间打包TXs，通过PBFT共识将合法的交易打包上链；
  • P-shard在每个Epoch期间以自适应的方式划分账户状态。

1.2 Four sequential phases

“>

如上图展示了本文所提出的跨分片协议的整体框架，包括4个关键步骤，具体描述如下：

  1. 交易区块共识阶段：在一个Epoch开始时，每个M-shard都会从交易池里打包交易，并通过运行PBFT协议发布多个交易块。P-shard在一个Epoch内产生的交易块数量取决于分片内的网络参数，如带宽等。而M-shard产生的第一个新交易区块遵循状态区块（也就是图2中的 B t − 1 B^{t-1} Bt−1，记录着前一Epoch的状态划分结果。
  2. 状态图分区阶段：P-shard从产生的区块中读取交易并持续更新所有账户的账户图。一旦M-shard生成了当前Epoch中的所有交易块，状态图就固定了。然后，根据Metis算法开始对状态图进行划分，以实现所有分片之间的负载平衡。
  3. 状态区块共识阶段：在前一阶段对所有账户的状态图进行分区后，BrokerChain将执行账户分割机制，后面会详细描述。为了对状态图分区和账户分割的结果达成共识，再次利用PBFT协议生成一个状态块（由表示 B t B^{t} Bt），然后将其添加到划分分片链中。
  4. 状态重配置阶段：对划分结果达成共识后，P-shard广播包含S分区的状态图的状态区块到所有相关联的M-shard。当接收到状态块 B t B^{t} Bt时，工作分片从状态块读取状态分区结果，并相应地重新配置其状态，以便可以根据新的帐户状态将下一个Epoch（第t+1个）中的交易分配到指定的分片。

2. Account Segmentation

强制用户设立多个账户是不合理的，因此设计了一种账户分割机制（ account segmentation mechanism）。这个机制在区块链架构的协议层工作。

提出的账户分割机制具有以下优点：

  1. 不强制用户开立多个帐户。

  2. 用户帐户的状态可以轻松划分并存储在多个分片中。

  3. 通过这种用户透明的方式，可以方便地实现所有分片的工作负载平衡，从而消除热分片。

如下，通过一个划分账户的例子，理解账户分割机制。假设现在有三个账户以及三笔要处理的交易。假设现在有两个分片，shard#1 和shard#2。账户A，B分别存储在两个分片中。那么不妨假设C设立在分片2中。如果用Monoxide的分片方法，这三笔交易会产生四个跨分片交易。而如果采用BrokerChain的方法，那跨分片交易会减少到两个。

在这里插入图片描述”>

表面上看，BrokerChain好像就是把一个账户分割了成了两个账户，分配存款后放入不同的分片。但值得注意的是，这两个账户的地址是相同的。也就是说，BrokerChain协议在某个分片上存储着另一个分片上的帐户存款，并且他们具有相同的账户地址。研究者采用以太坊的计数器机制（帐户状态的nonce）来识别位于另一个分片上的帐户的多个状态。

3. mSST

要启用状态图分区和帐户分割操作，BrokerChain必须强制每个分片了解所有帐户的存储映射。因此，基于以太坊的MPT状态树设计了一种改进的分片状态树（mSST），以存储帐户状态。与MPT树不同，BrokerChain的mSST构建在所有帐户的存储映射上。定义如下：
Font metrics not found for font: .
其中每个e都是一个布尔值，然后S是M-shard的数量。BrokerChain需要为每个帐户配置存储映射。 e i e_i ei​为1代表这个账户的状态被分片 i 给存储了，如果在中有多个元素被置为1，代表该账户被多个对应的分片存储了状态。

如果某个用户的账户状态表示为：

S μ = { X μ ∣ Ψ , η , ω , ζ } \mathbb{S}_{\mu}=\left\{X_{\mu} \mid \boldsymbol{\Psi}, \eta, \omega, \zeta\right\} Sμ​={Xμ​∣Ψ,η,ω,ζ}
其中， X μ X_{\mu} Xμ​是用户 μ \mu μ的账户地址， η \eta η表示nonce字段，以及 ω \omega ω表示值字段，显示用户的存款。 ζ \zeta ζ是账户类型字段，包括用户帐户和智能合约帐户。

对于某个特定的账户而言，不同的分片为这个账户维护的不同的mSST。这些状态树的区别在于值，nonce以及代码。如果目标帐户不再存储在分片中，则这些字段与此相对应分片的MSST将被删除。而且该碎片只需要更新目标帐户的状态。目标帐户状态的任何更改都会导致MSST的状态变化。因此，很容易保持帐户状态在相关的分片中的一致性。

4. Handling cross-sharing TXs

4.1 Broker account

尽管账户分割机制能够将一个账户细分为多个较小的账户，但问题是区块链系统需要招募一些愿意充当中介的账户，以帮助处理跨分片交易。我们称这些中介机构为做市商账户，简称为broker。

成为broker的一个基本要求是其账户拥有足够数量的货币。对于打算成为broker的系统用户，他们可以请求将其资产抵押给受信任的第三方或特殊的智能合约。然后，BrokerChain协议为那些感兴趣的系统用户提供了代理资格。broker的状态会被系统分割成两部分或多个部分，分别存储在两个或多个分片中，从而参与到若干个跨分片交易的协调当中。broker的协调机制可以减少基于转账类型的交易的跨分片通信，因此可以减少跨分片交易的延迟，从而提高跨分片交易执行的效率。

4.2 A success case

仍以图三为例。假设C是一个broker，其帐户被分割并存储在shard#1和shard#2中。现在，我们有了一个原始交易，即发送方A通过C向接收方B传输v个货币。这里，我们将shard#1称为源分片，将shard#2称为此发送的目标分片。利用图5，我们介绍了跨分片发送处理的成功和失败案例。

“>

Op1: Create a raw transaction

账户A首先选择一个适当的锁定tokens时间 H l o c k H_{lock} Hlock​, 这个时间是从 θ r a w \theta_{\rm raw} θraw​产生到解锁tokens的区块产生间隔的时间。

θ r a w \theta_{\rm raw} θraw​的定义如下：
θ r a w : = \theta_{\rm raw} := θraw​:=<B,v,C,Hlock​,ηsender​,ηbroker​,σC​>
η s e n d e r , η b r o k e r \eta_{sender}, \eta_{broker} ηsender​,ηbroker​分别表示发送方账户A和做市商账户C的nonce； σ C \sigma{C} σC是发送方账户A的签名，由ECDSA算法计算得出。然后，A将原始交易 θ r a w \theta{\rm raw} θraw发送给C。

Op2: Create the first-half cross-shard TX

收到 θ r a w \theta_{\rm raw} θraw​之后，C生成跨分片TXs的前半部分交易 θ 1 \theta_1 θ1​。此时，shard#1的块高为 H c u r r e n t H_{current} Hcurrent​。

θ 1 \theta_1 θ1​的定义如下：
θ 1 : = \theta_1 := θ1​:=<Type1,θraw​,Hcurrent​,σC​>
其中，Type1是 θ 1 \theta_1 θ1​的标志， σ C \sigma{C} σC是做市商账户C的签名。

随后， θ 1 \theta_1 θ1​被广播到区块链网络中。当其他分片中的所有节点收到了 θ 1 \theta_1 θ1​，他们依次执行以下操作：

  1. σ C \sigma{C} σC和 σ A \sigma{A} σA用确认 θ 1 \theta_1 θ1​；
  2. 获取发送方的公钥并使用签名 σ A \sigma{A} σA计算发送方的账户地址；
  3. 通过查询mSST，分片节点知道这笔交易的源分片和目标分片；
  4. 利用Kademlia路径选择协议，转发 θ 1 \theta_1 θ1​到shard#1和shard#2。在确认 η s e n d e r \eta_{sender} ηsender​是正确的以及发送方A的账户余额是充足的情况下， θ 1 \theta_1 θ1​会被添加到shard#1的交易池中，然后等待被打包上链。

Op3: Confirm θ 1 \theta_1 θ1​

广播结束后，shard#1中的区块链节点把 θ 1 \theta_1 θ1​写入区块，此时区块高为 H s o u r c e H_{source} Hsource​。然后发送方A把v个tokens转账给做市商账户C，这些tokens在区块高为 H s o u r c e − H s o u r c e + H l o c k H_{source}-H_{source}+H_{lock} Hsource​−Hsource​+Hlock​时被锁定。发送方A的nonce将+1以防重播攻击。

Op4: Create the second-half cross-shard TX

当做市商账户C认为 θ 1 \theta_1 θ1​已经被确认之后，C将会生成后半部分跨分片交易 θ 2 \theta_2 θ2​，其定义如下：
θ 2 : = \theta_2 := θ2​:=<Type2,θraw​,σC​>
其中，Type1是 θ 1 \theta_1 θ1​的标志， σ C \sigma{C} σC是做市商账户C的签名。 θ 2 \theta_2 θ2​会被广播到区块链网络中，最终到达目标分片shard#2。在确认 η b r o k e r \eta_{broker} ηbroker​是正确的以及做市商账户C的账户余额是充足的情况下， θ 2 \theta_2 θ2​会被添加到shard#2的交易池中，然后等待被打包上链。

Op5: Confirm θ 2 \theta_2 θ2​

如果shard#1的区块高小于 H s o u r c e + H l o c k / 2 H_{source}+H_{lock}/2 Hsource​+Hlock​/2，那么shard#2中的节点收到后会将其打包放入一个新的区块。首先C转账v个货币给接收方B，然后shard#2的的账户状态才会变化。同时C的nonce+1以抵御重放攻击。

在跨分片交易的成功案例中，一旦被成功写入目标分片的区块链（shard#2），接收方B就能收到这笔v个货币的转账。从另外一个方面讲，只有当shard#1的块高度大于 +1时，A向C支付的v个货币才能解锁，从而发给C。

4.3 A failure case

当shard#1中的区块高大于 H s o u r c e + H l o c k / 2 H_{source}+H_{lock}/2 Hsource​+Hlock​/2时，如果shard#2还未将 θ 2 \theta_2 θ2​写入区块中，我们就认为 θ 2 \theta_2 θ2​没有被shard#2承认。此失败结果很可能是由恶意的C引起，C打算盗用发送方账户A的锁定tokens。

“>

为了处理此类失败案例，BrokerChain执行以下步骤以保证跨分片交易的原子性。首先， θ 1 \theta_1 θ1​会被包含在shard#2中，而这个分片的nonce会更新。然后shard#2中的区块链节点会发送以下关于 θ 1 \theta_1 θ1​的确认信息到shard#1作为失败的证据（用表示）：
γ : = \gamma := γ:=<θ1​,dest,Hdest​,{Pdest​}>
其中， d e s t dest dest代表目标分片的标志； H d e s t H{dest} Hdest表示 θ 1 \theta_1 θ1​所在的目标分片的块的高度； { P d e s t } \{P{dest}\} {Pdest}代表默克尔树路径。包含了从默克尔树根节点到 θ 1 \theta_1 θ1​所在结点之间相关联的所有哈希值，被用来证明 θ 1 \theta_1 θ1​被shard#1中的一个区块写入。

一旦shard#1中的结点收到了失败证据并且证明了的正确性，shard#1就清楚已经被包括在shard#2中而并没有被包括进去。然后会被写进来源分片也就是shard#1的区块中，它的高度小于 + 。最后，在操作3中锁定的货币会被返还给发送方账户A。

四、Experiment

1. Setting

本文使用 python 搭建了一个分片区块链的仿真实验环境，实现了基于Metis图划分的分片调整和“做市商账户”跨分片交易机制。关于数据集，本文使用了以太坊从2015年8月7日至2016年2月13日的1,600,000条真实历史交易。在实验过程中，交易以一定的交易到达率被注入到各个分片中。每个分片的出块时间间隔设置为8秒，每个区块打包交易数量上限为2000条，分片数量为32个。实验测试了不同交易到达率和不同分片数量下的系统吞吐量和平均交易延迟。

2. Main Experimental results

如下图所示，本文提出的分片协议与 Monoxide协议采取的分片机制相比，吞吐量最大提升150%，平均交易延迟降低70%；与基于负载均衡优先（Load Balance First，LBF）的动态分片调整协议相比，吞吐量最大提升10%，平均交易延迟降低40%。可见，与 Monoxide协议提出的“中继交易”协议相比，本文提出的 BrokerChain 协议能够保证跨分片交易在较短的时间内完成，从而降低跨分片交易的交易延迟。

“>

如下图所示，与基于Metis图划分方法相比，本文提出的机制可以将跨分片交易的比例进一步降低10%。

五、Conclusion

“>

创新点总结：

  1. 提出的账户状态动态调整策略，改变了传统的状态分片通过各分片的账户状态信息进行分配的方式，实现分片间的负载均衡和跨分片TXs。
  2. “Broker”，一部分普通用户通过自愿抵押一定的资产充当Broker（做市商账户），可以参与到若干个跨分片TXs的协调中。

参考博文：

  • 基于“做市商账户”的区块链跨分片协议 —— BrokerChain_彭肖文，黄华威，2022年5月
  • – BrokerChain: A Cross-Shard Blockchain Protocolfor Account/Balance-based State Sharding_友好的Spider-man