简介

这篇论文讨论了区块链的状态分片的设计。针对Monoxide等分片方案存在的问题——单点过热，论文提出了brokerChain，一方面通过图的分割算法分割账户，促进分片的负载均衡；另一方面通过broker账户的设计改造了跨分片事务，缩短了事务的验证延迟。
brokerChain适用于基于账户的区块链，如以太坊。

系统设计

系统将事务的处理分成一个个周期（epoch），上图展示了一个周期内进行的活动。

  1. 节点在每个周期开头完成PoW，然后根据哈希值的最后几个比特决定划分到哪个分片。分片分为M分片和P分片，前者进行正常的挖矿，后者只有一个，负责运行图算法划分账户。
  2. 随后M分片内的节点运行PBFT生成若干个区块，并发送到P分片；与此同时，P分片维护一个由所有账户组成的状态图，从到来的区块中拿出事务，并更新状态图。当状态图不再改变时，P分片将其划分，使得所有分片负载均衡。
  3. 划分状态图后，依此进行账户的分割。为了达到状态图划分和账户分割结果的共识，P分片内运行PBFT生成一个状态区块并加到链上。
  4. P分片达到共识后，状态区块被广播到M分片中。M分片根据状态划分结果增加或删除部分节点（账户）。

实现细节

  • 状态图划分

如图，每个节点表示一个账户，边上的权重表示在两节点间进行的事务的数量，节点的权重等于与节点相连的所有边的权重之和。
使用Metis算法将节点划分成不重叠的多个区域，（考虑区域间的负载平衡以及减少跨分片事务）。

  • 账户分割

    • 特性
      同一个账户可以被分割成多个拥有相同地址的账户，分别存到多个分片中（存储的币值也被分割到多个分片中）
    • 优点
      减少跨分片事务
    • mSST（Modified Shard State Tree）
      根据以太坊的状态树进行改造，每个账户有一个位图向量表示其是否存在于某个分片中。mSST的数据结构如下图。

    同一个账户在不同分片内的状态树中表示一般是不同的，差别主要体现在value、nonce和code（即图中的叶子结点中的后三个值）。如果一个账户不再存在于某个分片，该分片中对应节点的这些域的值会被清空（如图中的右下角节点）。

  • 跨分片事务的处理（broker账户）
    不同于Monoxide中提出的接力事务，这篇文章提出了broker账户。
    假设有三个账户A、B、C，A在分片1中，B在分片2中，C被分割成两个账户，分别在分片1和分片2中。接下来讨论A往B转账的处理过程。（此处细节可能存在误解，建议自行看论文）

    1. A创建一个raw事务，将其转发给C；
    2. C验证raw事务，创建事务1，然后将其广播到分片1。记此时的区块高度H0；
    3. 分片1接收到事务1后，先验证，然后将其加到事务池中等待被打包。
    4. 事务1被打包到分片1的区块中后，记当前区块高度H1。随后A向C转账v，这些转账的金额在一定的区块间隔时间lock内会被锁定，无法使用。同时，C创建事务2，并发送到分片2。
    5. 分片2接收到事务2，验证后将事务2加进事务池。
    6. 当事务2被分片2中的节点验证通过后，进行以下判断：分片1的当前高度是否小于H0 + lock/2 。如果是，将事务2打包进区块中，C的账户中v被转到B中。

分片间会互相分享区块的头部信息，其中包含了区块的高度。如果分片2在接收到分片1的区块头部后发现已经超过H0 + lock/2了，但自己仍没有收到事务2，那么很有可能是C打算私吞这笔交易的钱。此时分片2将事务1打包进区块中，然后发送一条消息到分片1让其验证；分片1验证到事务1被打包进分片2后，将这条消息打包进区块中（假设此时区块高度仍然小于H0 +lock），最后，被锁住的钱会退回到A的账户。

分析

  • 抵御双花攻击
    每个账户的状态中会有一个计数变量表示该账户发起的交易个数，以此避免双花攻击。

  • 跨分片事务的验证时间复杂度
    在成功的情况下，C需要验证事务1是否被打包进链上的区块，复杂度O（1）；
    在失败的情况下，分片1需要验证来自分片2的失败消息是否真实，复杂度O（n），n为分片1中的节点。

实验

  1. 吞吐量（TPS）、验证延迟

问题

  1. P节点从M节点发来的区块中获得交易的信息并更新状态图，但此时这些交易已经被确认了，下一阶段的交易将根据这个最新的状态图来划分和执行，但状态图只是根据历史信息提供的启发（诸如上一周期交易往来多的账户下一周期仍会有很多交易这样的逻辑），不一定适合下一周期的交易。