如果有人很直接地问你：怎样才能拓展状态机复制（区块链）系统呢？

你应该反问：你系统遇到的瓶颈是什么？数据？共识？还是执行？

1. 数据：数据是将所有指令传输给所有状态机副本的载体。举个例子，如果一个区块包含 1MB 的指令，那么你就需要把 1MB 的数据发送给所有负责验证的副本。显然，这种情况下，系统的通道容量（带宽）是系统可拓展的瓶颈。

2. 共识：指令到达本地之后，状态机们就会参与共识协议（就像这里所讨论的部分同步或者同步协议）。举个例子，如果一个共识协议需要两次消息往返，而参与验证的状态机分布在全球各地，那么，这里明显的瓶颈在——由光速和地球大小而导致的延迟。

3. 执行：指令到达、共识在指令排序上达成共识后，副本需要执行指令。执行引擎是一个接受旧状态并应用指令来计算新状态（并计算输出）的函数。又举个例子，如果执行需要许多密码学计算，那么很明显啦，这里的瓶颈就是副本要重复执行的密码学计算。

需要注意的是，这三个瓶颈不是追求一种折衷，也不是两难的困境，也不是三难困境。它们是彼此独立的。所有状态机复制系统的可拓展能力都受到这三种因素的限制（而且像木桶原理一样，受制于其中条件最差的那一个）。本文将介绍一些解决这些瓶颈的方案。

1. 从数据上提高可拓展性

更好的网络解决方案

对比特币等密码学货币而言，扩展吞吐量的能力取决于减少延迟——因为某个矿工挖出的区块需要经过一定的延迟才能传播给所有其他矿工。像 FIBRE、 Falcon、 bloXroute 这些系统会通过使用 专用通道（pipelining）来降低延迟，并使用 前向纠错码（foward error correction code） 来传播区块。提高数据可拓展性的另一个办法是通过 内容可寻址网址（content addressable network）来发现对等节点并访问内容。具体可参考 Kademlia，它不仅启发了以太坊的 RLPx 编码规范，并在 libp2p 上得到了推广。

把数据迁移到 layer-2

另一种思路是，既然瓶颈源于需要复制所有指令到所有状态机，那我不复制不就完啦！像 Lightning、 Plasma 和其他 Layer-2 解决方方案都是如此——把中间命令传播给一个较小的半公开团体以减少数据复制、定期向整个系统报告总结（详情可看我们关于支付通道的文章）。自然而然地，这种方法的不足在于：不复制所有数据会造成数据的可用性问题（data availability problem）。而安全性依赖于每个拥有数据的半公开团体内至少有一个诚实参与者能及时地作出反应。

2. 从共识上提高可拓展性

吞吐量和延迟之间的权衡

有人将每秒处理交易数（TPS）作为衡量协议可拓展性的标准。TPS 是对吞吐量的度量，人们存在一个误解——以为对它单独优化就可以实现共识可拓展性。共识可拓展性的解决方案必须同时关注 吞吐量 和 确认时延 这两个因素。

通过 成批处理 来提高共识的吞吐量（但提高延迟）很简单：只需要一天一次，而不用每隔几秒一次，就可以让人们就被批处理的所有数据的哈希值达成共识。显然，由于一天只达成一次共识，成本会被分摊，仅就吞吐量而言，共识过程就不再是阻碍实现拓展性的瓶颈了。显然，批处理虽然能提高共识协议的吞吐量，但也会提高交易确认的时延，并不是什么扩展共识协议性能的万灵丹。

PBFT journal version 一文充分地讨论了 BFT 状态机复制的延迟和吞吐量。

对基于 Nakamoto Consensus 的协议而言，有很多协议都试图增加吞吐量及时延，如：Bitcoin-NG、 Fruitchains 和 Prism。

性能和安全性之间的权衡

有人建议在更小的状态机副本小组内达成共识，以优化共识过程的性能。降低验证状态机小组的规模的确可以提高性能，但这是以降低降低安全性为代价的。所以，真正的挑战在于不减少参与状态机的数量同时提高共识过程的性能。

提高 共识协议的复杂性 有望鱼和熊掌兼得，例如：减少轮数，或者说 改变消息传递的复杂度，使呈平方级增长的消息数量可以变为线性增长。本文讨论了一些部分同步中的协议改进和同步中的协议改进。

可拓展性和适应性之间的权衡

基于 PBFT 视图范式的共识协议容易受到攻击者的适应性攻击（adaptive attack）。共识协议的安全性不仅和攻击者的规模（由状态机副本总数决定）相关，而且和对手的适应性能力相关。

处理适应性对手的协议通常会导致更高的成本，也会在可拓展性上遇到更大的难题。Algorand 建议用基于轮次的密码抽样来拓展拜占庭共识，使其免受适应性攻击者的攻击。这种方法的模拟结果看起来很不错。适应性对手可以使用 拒绝服务攻击（Denial-of-Serivice attack）来阻止系统推进。HoneyBadger 提出了第一个实用的 异步 BFT 协议——该协议在不做任何时序假设的情况下，也能保证活性。

避免对所有命令进行全排序

如果所有指令都相互依赖，那么除了对所有指令进行全排序外，别无他选。但是在许多工作负载中，指令不会彼此依赖和彼此干扰。举个例子，在某些情况下，A 给 B 支付的指令和 C 给 D 支付的指令就不会相互干扰；在这种情况下，我们没有必要浪费昂贵的共识资源为这两笔指令进行 内部 排序，没有理由让它成为系统的瓶颈。在 epaxos 非拜占庭模型中就采用了这种（不在所有时候都搞全排序的）办法。像 Avalanche 和其他基于 DAG 的协议，会通过允许并发提交互不干扰的指令来增加共识的吞吐量。

分片

抽象一点来看，分片是对状态和状态机副本集合进行 分区。每一分片控制状态的某个部分，且共识过程是由验证状态机总体的某个部分来完成的。这当然也需要一些跨分片交互机制。以太坊的 “Sharding FAQ” （编者注：中译本见文末）资源正是一个很全面的资源。

分片是并行化处理 数据、共识 和 执行 这三大瓶颈的方法。实现数据和执行并行化的关键在于工作负载的低 状态竞用（contention）。从共识的角度来看，分片本质上就是在性能和安全之间取舍：不是用所有状态机副本去保障一个状态，分片技术创建了多个分区，每个验证者副本会各自保护它们自己的分区。

（如果状态竞用程度较低）划分许多分区会显著地提高性能。但是，因为每一分区的验证状态机都变得更少，安全性自然就降低了。

想了解使用分片技术，请参阅 Omniledger 和 Ethereum 2.0 。以太坊 2.0 计划将每个分区的低安全性和全局链的高安全性结合起来。就像 Layer-2 方案一样，低安全性的分片可以定期上传自己的状态到高安全性的全局链上，并将状态更新确定下来。这也是在安全性和延迟之间取舍——想获得高安全性，就得等待全局链的周期性敲定。

3. 从执行上提高可拓展性

共识和执行的分离是状态机复制系统的基本架构设计之一（可参见 Base 20013）。分离的好处可参见 Yin et al 2003。在传统的状态机复制系统（SMR）中，命令不仅要复制并传播到所有副本，还得在所有副本上执行。

在很多系统中，可拓展性的瓶颈是 执行 指令的成本。对 SMR 系统的一种主要拒绝服务攻击工段是发出合法的命令，让整个系统浪费时间在执行上（详情请参阅：例 1 和例 2）。很多系统通过设计领域专用语言来（Domain Specific Language）避免攻击。比特币用比特币脚本，小心翼翼地限制每笔交易的计算复杂性。以太坊用 gas 机制来限制执行的复杂性，并用效率来激励人们对 Gas 的使用。

并行化执行

让状态机并行化执行也是一种提高执行能力的方法。当在区块中的大部分命令无状态竞用（相互独立，或者说可互换顺序）的情况下，这个方法是有效的。它的主要思想是设想一种在无竞用的条件下并行执行、在有竞用时维护安全性的协议，用该协议模拟出连续执行的结果。详情请参看 Eve 2012、 Dickerson、 Gazzillo、 Herlihy、 Koskinen 2017 和 Saraph 和 Herlihy 2019。

不在 SMR 内执行，使用经济激励和错误性证明来验证

（optimistic rollups 类型）

在这类解决方案中，指令作为数据提交到 SMR 内，但是执行不是由验证状态机副本完成的。状态机副本仅充当 数据可用性 层。

不用副本来执行指令，而用经济激励机制——玩家可以通过 发布债券 来成为执行者。锁定了保证金的执行者都可以提交执行结果，而其他人可以通过提交错误性证明来举报执行人提交了不正确的执行结果。如果这份错误性证明是正确的，执行者将受到 惩罚，而提交者将得到部分奖励。如果挑战者在错误性证明上说谎，那他的保证金就会大幅罚没。

实现高效挑战的协议起源于 Feige Kilian 2000，而 Canetti, Riva, Rothblum 2011 沿着这条道路推进，最终演化成采用链上激励的 TrueBit Teutsch, Reitwießner 2017 和 Buterin’s Off-Chain Oracles 。如今，这种方法在名为 optimistic rollups 的方案中中得到进一步发扬（详情可参看 merged consensus、Adler, Mikerah、Quintyne-Collins、Al-Bassam、Sonnino、Buterin 和 LazyLedger）。

不在 SMR 内执行、用简洁的证明来验证

（zk rollups 类型）

在本方案中，指令同样作为 数据 提交到 SMR 中，执行同样不关验证状态机副本的事。副本只是作为指令的数据可用性层。

不同于用挑战游戏和错误性证明来验证执行结果，利用 简洁的非交互式证明 也是可以的（PCP、Groth 10、Groth 16、 Ben-Sasson、Chiesa、Tromer、Virza 2013-2019 和 survey）。这些密码学技术允许验证者生成非常短的证明，同时对这些证明的验证在密码学上具有高度的可靠性和完整性。执行（和证明生成）只能由同一实体完成。有了简洁证明后，验证状态机副本只需要验证简洁证明，而不需要重新执行长交易。Zexe 用这个方法来建构了基于 nano-kernel 的证明系统，人们因此可以在 UTXO 中实现隐私交易。

Buterin 论述 zk-roll-up 的文章和 Ben-Sasson 的 podcast 强调了这种拓展交易处理量的方法。详情请查看 Buterin 的视频，进一步去了解如何将隐私（零知识）添加到简洁的证明中（zk zk rollups）中。

这种简洁的证明有很多好处：验证证据正确性的成本非常低。而短处在于构造指令执行的证明通常比单单去执行指令的成本要高得多。还有一个坏处在于这些协议增加了大量的复杂性。此外，某些协议还需要繁复的受信任初始设置仪式。

点击即可查看近期 optimistic and zk rollups 的调查/比较（编者注：中译本见文末）。需要注意的是，以上介绍的方法意在克服执行可拓展性的瓶颈，而不在改变数据可拓展性的瓶颈。

感谢

我们想借此机会感谢 Ling Ren、Kartik Nayak、 Alin Tomescu、 Pratyush Mishra、Louis Guthmann 和 John Adler。感谢他们给本文提供了富有教益的反馈。

（完）

（文内提供了许多超链接，请点击阅读原文到 EthFans 网站上获取）

原文链接:

https://decentralizedthoughts.github.io/2019-12-06-dce-the-three-scalability-bottlenecks-of-state-machine-replication/

作者: Ittai Abraham

翻译 & 校对: ViloaH & 阿剑