Survey Sharding in Blockchains 笔记

区块链分片技术综述

Sharding  的意义

• 现有区块链的性能限制：Bitcoin 每秒约 10笔交易，其最大区块大小为1MB，平均区块时间为10分钟

- 因此，Bitcoin 交易在链外处理，然后在区块链中结算。（Layer-2 scaling）

- Layer-1 scaling

1. 减少通信和计算开销

2. 向单个节点添加资源，即垂直扩展

3. 向区块链添加更多节点，即水平缩放

reducing overhead

• 例子：

- Bitcoin-NG 每个 Pow 赢家能够获得多个区块（而不是一个）

- 传统 PBFT 协议的优化

• 缺点：最多只能减少到 $O(n)$

Vertical Scaling

• 例子

- 增加单个区块中允许的交易数量/缩短区块周期——但是会消耗更多资源

- GHOST [[GRANDPA 笔记]]

- 进一步扩展到 DAG：能够并行确认事务

• 缺点：不能无限提高吞吐量——网络规模增大会需要更多带宽

Horizontal Scaling

• 分片：整个区块链划分为多个分区，并允许参与节点处理和存储几个分片的交易

• 优点：通过利用允许在单个节点上处理和存储部分事务的分片技术，整个区块链可以随着节点数量的增加实现线性增加的吞吐量

Sharding Overview

面临的问题

• 共识内安全：如何以可扩展的方式保护分区内的一致性算法，因为攻击者可以更轻松地控制单个分区，而不是控制整个网络

• 交叉分区原子性：如何以有效的方式支持交叉验证（如果实现原子安全的交叉分区事务的延迟和开销高于 $O(n)$，则效率低下；n 表示分区数或参与节点）

内共识协议

• PoW：$P>\mathbb{P}/n\times 50\%$ 即可发动攻击。$\mathbb{P}$ 是网络中的采矿权总量

• BFT：基于 BFT 的共识算法的弱可拓展性限制了分区的大小（分区内的成员数量）。太小的分区可能会降低具有严格容错性（FT）的内部一致性的安全性

$\begin{aligned} &s(k, m, p)=P[X \leq c]=\sum_{k=0}^{c}\left(\begin{array}{l} m \\ k \end{array}\right) p^{k}(1-p)^{m-k} \\ &f(k, m, p)=1-s(k, m, p) \end{aligned}$

（$X$ 是表示恶意矿工被选中次数的随机变量；$m$ 表示分区大小；$c$ 表示分区中恶意成员的数量；$p$ 表示整个网络中的总 FT；$s$ 应该大于 99%，此时 $m$ 大于 144 才能满足——但是传统的 BFT 算法不能实现）

NAKAMOTO-BASED-MONOXIDE - CHU-KO-NU MINING

• 第一个无需生成随机性、实现中本聪共识的算法

• 开始时一次性自举（one-off bootstrapping？），根据身份地址将每个节点分配到不同的分区中。

• 基于 Merkle Patricia Tree 根，由多个分区中的提议块（proposed blocks？）构成。这样就能让 $\mathbb{P}/n$ 变成 $k \times \mathbb{P}/n$（$k$ 表示特定矿工设法开采的碎片数量）——这样分散的采矿能力可以重新聚合以解决1%的攻击

• 灵感来源于合并挖矿，合并挖基于正在运行的同类PoW算法，在父链和多个辅助链之间共享挖掘能力，具有相对较小采矿功率的辅助链可以由父链的总采矿功率进行保护。Monoxide 也有类似的想法，但在没有任何层次结构的情况下跨多个并行碎片执行挖掘过程。

• Pow 表达式 $\mathbb{H}\left(\eta \| \mathbb{H}\left(x \| M P T_{M}\right)\right) \leq \gamma$（其中 $\mathbb{H}$ 表示散列函数；$\eta$ 表示 nonce；$x$ 表示报头内容，包括涉及的分片的上述信息和在正常 PoW 中定义的其他字段，以及与跨分片通信有关的入站和出站中继事务；$MPT_M$ 表示 MPT 根，包括每个相关碎片的所有提议块）

  • 因此，矿工可以随后将最终确定的区块发送给其相应的碎片，并提供满足的 $\eta$ 和证据 $\left[M P T_{M}, \eta, \mathcal{B}_{i}, \pi_{i}\right]$
    • 在混合 PoW 目标的情况下，允许矿工最终确定区块，并将其发送至任何分区 $i$ 至 $j$，其 PoW 目标已通过当前给定 $\eta$ 实现，其余碎片的目标尚未实现。在那之后，挖矿过程继续，而 $MPT_M$ 由于从碎片 $i$ 到 $j$ 的块刚刚完成而被更新。
    • 在相同 PoW 目标的情况下，矿工也可以最终确定块并将其发送到所有碎片，而不管给定 $\eta$ 是否满足 PoW 目标。除此之外，通过消除 $\pi_i$ 的需要，来自所有矿工必须参与的所有分区的全局子网主存和广播报头可以显著减少通信开销。
      【可以观察到接受/拒绝单个分片的块与其他分片的决定无关，即异步化】

• 缺点：

  • 然而，为了满足 $k \times \mathbb{P}/n \simeq \mathbb{P}$ 的要求，Monoxide 需要大多数矿工在尽可能多的碎片上进行 CHU-KO-NU MINING，即在最佳情况下 $k=n$。然而，这意味着，如果矿工仅在 $n$ 个碎片中的 $k$ 个上采矿，则预期放大有效采矿能力的因素将太小，无法确保采矿过程的安全，从而降低攻击成本。
  • 另一方面，理性的矿工倾向于在所有 $n$ 个碎片上进行挖掘以获取最大利润，这也可能导致权力集中，因为只有专业的采矿设施才能负担得起带宽、磁盘存储和计算处理器的巨大成本

BFT-BASED-ELASTICO

• 将基于 BFT 的算法用于内部一致性是绕过基于中本聪共识漏洞的一种替代方法

• Elastico 在每个纪元开始时，根据不可预测的 PoW 解决方案的不同最低有效位均匀（重新）分配潜在的验证者，然后运行 PBFT 进行内部共识。挖矿过程中使用的随机性是由一个提议的分布式提交和异或方案产生的。

  • 由于 PBFT 的弱可伸缩性，即使扩展到更大规模网络，Elastico仍会产生 2.76%的故障概率。这一安全问题一直阻碍着Elastico的实际应用【传统的不可扩展PBFT会导致不可接受的高故障概率，除非扩大共识小组的规模，但是这样效率又低了】
    • OmniLedger 和 RapidChain 极大地解决和改进了这一问题

• 随机性生成——分布式提交和异或方案

  • 一种提交然后显示方案
  • 具有弱可用性和鲁棒性，除非支付更多的通信开销，否则它不是一个完全无偏的随机生成器

BFT-BASED-CHAINSPACE

• 使用了 Mod-SMaRt —— PBFT 的最佳实现，但是并没有扩展PBFT来解决 1% 攻击的问题

• 它将通信和共识原语解耦，而它仅以不变的开销减少后者的开销 $O(n^2)$ 通过将流程替换为经过验证且可证明的共识（VP-Consensus）。

• Elastico 内部共识的高失败概率也在 Chainspace 中生效，同样限制了Chainspace在大规模网络中的使用。

BFT-BASED-OMNILEDGER

• OmniLedger 将 RandHound 和基于 Algorand 的 VRF 结合起来，在25% 范围内产生不可预测和无偏的随机性，用于每个分区的重新分配和领导人选举。

• 此外，通过优化 ByzCoin，提出了一种新的可扩展的基于 BFT 的一致性算法ByzCoinX，通过将分区大小增加到数百到1000，解决了基于BFT的1%攻击的难题

BFT-BASED-RAPIDCHAIN

• RapidChain 实现了一个基于 VSS 的分布式随机生成（DRG）协议，以同意无基础随机性。在DRG协议的基础上，RapidChain 通过引入确定性随机图来解决【RandHound 和VRF 的组合源于对 genesis 区块中预先定义的第三方初始随机性的依赖】问题

• RapidChain 通过将内部一致性协议的 FT 增加到50%，解决了基于BFT的一致性算法在分片中的困境

• 但是：RapidChain 提出的 DRG 协议只实现了一个基本的 VSS 共享方案，仍然遇到了与其他典型 VSS 方案类似的问题——不可伸缩性（只适合小型分片中的 50% BFT）

BFT-BASED POS-ETHEREUM 2.0

• 讨论的是 Shaper + Casper-FFG ——此时 Casper-CBC 仍然尚待实现
  • 基于 BFT 的 PoS 共识算法
  • Shasper 为共识内部提供了比任何其他考虑的分片机制更灵活的分配，但是产生更大的开销
  • 将成员分配和共识过程解耦，这导致分片中的内部共识也涉及来自其他分片的验证者作为证明者。与特定分片关联的证明者组的成员可以在每个槽中更新。

交叉分区的原子性

Monoxide 中继交易

• 无锁设计（为了减少锁定和解锁的开销导致的的跨分片性能下降），提出了“最终原子性”（Eventual Atomicity），通过简单的消息交换实现无锁异步跨分片交易

• 缺点：与智能合约不兼容、额外延迟、意外重放

Elastico 无跨分片交易

• Elastico 不提供全局分类跨账分片的原子性

OmniLedge ATOMIX协议

• 为了简化跨分区的原子性，OmniLedger 提出了一个基于 UTXO 的客户端驱动的 Atomix 协议。这样客户端充当网关，将通信开销被转移到分片之外。

• 缺点：Atomix 协议是一个“创口贴”（牺牲了轻量级客户端的支持）；同时，随着分区数量增大，Atomix 协议对基于 UTXO 的跨分片交易的支持较差，无法充分利用 UTXO 格式

RapidChain 三向确认

• 引入路由表，优化了 OmnLedge 的 Atomix 协议，显著降低通信开销，即使分区数量大的基于 UTXO 的跨分区事务也能保持较好性能。

• 缺点：通过污染特定路由表的 Eclipse 攻击成为问题

Ethereum 2.0使用收据（RECEIPTS）

• 通过实现全局（由所有验证者存储）信标链来交换基本消息，即收据和证明，从而引入了基于账户的跨分片交易

  • 可以看作是 OmniLedger 和 RapidChain 中实现的同步锁定/解锁方案的变体

• 缺点：到目前为止，Shasper 只能支持基于账户（而不是基于UTXO）的简单支付交易

Chainspace $\mathcal{S}-BAC$

• $\mathcal{S}-BAC$：Sharded Byzantine Atomic Commit 分片拜占庭原子提交，其内部使用最优 PBFT —— Mod-SMaRt 来处理内部共识过程

• 类似于 OmniLedger 中的 Atomix 协议，具有关键的优化，其中必须执行BFT共识过程，而不是简单的客户端驱动模型

• 缺点：随着分区数量增大，Atomix 协议对基于 UTXO 的跨分片交易的支持较差，无法充分利用 UTXO 格式

一般改进

减少事务延迟

• 可以通过实现可扩展的 BFT 共识来解决，例如 OmniLedger 和Ethereum 2.0，或者在单个分片中增加 FT，例如 RapidChain

• RapidChain 实现了基于信息分散算法（IDA）的八卦协议，可以更有效地传输大型有效载荷

通信间协议

• 与实现原子性跨分片的协议不同，互连协议侧重于分片之间数据传输的开销

• 主要两种类型

  • 充当消息分发器的全局根链： Ethereum 2.0、Elastico、Monoxide
  • 瓶颈由于单链结构而不是分片结构而转移到全局根链上
  • 全网连接：OmniLedge、Chainspace
    • 会产生相当大的开销
    • RapidChain 利用路由表绕过全网连接

分片账本修剪

• OmniLedger 提出了状态块

分散式引导

• RapidChain提出了一个以采样图选举网络的形式分散的引导

保护 Epoch 重新配置

• Elastico 和 Chainspace 没有提供这样的解决方案

• Ethereum 2.0通过频繁更新参与每个分片内部共识协议的成员来解决具有全局验证器池的内部共识

• OmniLedger 实现了一个随机排列方案来交换验证器

• RapidChain 提出了一种基于布谷鸟规则（Cuckoo Rule）的轻量级重新配置协议

分片智能合约

• 仅 Chainspace 引入

评估

吞吐量的上限

比较和讨论

• RapidChain 和 Ethereum 2.0实现了优化，减少了Elastico和OmniLedger的限制，这使得RapidChain 和 Ethereum 2.0在吞吐量和成本方面是最先进的基于BFT的分片机制。

• 另一方面， Monoxide 将吞吐量的上限推到了百万级，并为基于中本聪的分片机制开辟了新的方向。

• Chainspace 在分片智能合约方面有足够的性能改进空间。

---

未来的趋势

降低开销的未来趋势

• 现有分片机制中三个缺陷阻止了系统水平扩展到理论上限
  1. 需要由所有参与矿工/验证者存储的现有全局链
  2. 要求矿工/验证器存储来自其他分区的账本
  • 潜在的解决方案之一可能是欺诈证明（fraud proof），使light节点与完整节点一样安全，而无需存储整个分类账
  3. 根据业务需求将参与节点分配给分片，以避免过度使用分片技术（按业务分片）

加强安全性和原子性的未来趋势

• 内部共识

  • 在具有尽可能少的第三方硬编码设置的大规模网络中扩展无偏和不可预测的随机数生成器
    • 无偏和不可预测的随机性在基于BFT的内部共识设计中起着重要作用
  • 改进基于PoW的内部共识，并将其推广到其他类型的基于中本聪的共识算法中

• 高效原子性：实现高效的条件跨分片交易，实现面向合约的操作。

  • 到目前为止，只有 Chainspace 和 Ethereum 2.0 的未来阶段声称支持这种条件的跨分片交易，但代价是不可接受的开销和延迟

总结

• Monoxide 首次提出了一种基于中本聪的分片机制，但代价是存储所有分片的标头，以保证最大的共识内安全性。

• Elastico 和 Chainspace 中使用的传统 PBFT 由于其可伸缩性较弱而不能保证内部共识安全性。而基于BFT 的分片机制，即 OmniLedger，Rapidchain 和 Ethereum 2.0，在扩展传统PBFT或增加传统PBFT容错的意义上提高了共识内的安全性。

• 本文中所有考虑的分片机制的随机性生成器都需要严格的网络设置，否则缩放网络中的不可预测性和无偏性将受到损害。

• Monoxide、OmniLedger、Rapidchain 和 Ethereum 2.0 都针对跨分片交易问题提出了自己的解决方案，没有一个可以支持跨分片智能合约。只有 Chainspace 提出了一种面向智能合约的分片机制，但代价是吞吐量低。