论文作者：Rafael Pass，康奈尔大学计算机科学系副教授

这篇论文中，作者介绍了一个全新的算法叫做「Thunderella」。与一般状态机的共识原理不同（状态机相当于一个共识机制的抽象，对分布式网络中大量节点的请求进行确认），Thunderella使得状态机可以在实现快速异步处理的同时，在异常时还可以启动回滚机制。如此一来，状态机的相应速度与同步协议无异，在不出现「拜占庭将军问题」（及大多数人都是诚实的）的情况下，可以做到对交易的瞬间响应。

这篇论文中，作者对POW协议下，无需许可和需要许可的设定，提供了一些示例，相应速度可以达到正常上网的体验。不过正如上面所说，这一算法的前提条件是网络中的大部分节点或算力是诚实的，而这里所说的「大部分」指的是不能低于3/4。

介绍

在分布式系统中有一种叫做状态机复制的技术，在这项技术中，每一组服务器同步一个增长并且线性的日志，而这必须满足两点属性：1）一致性，日志信息必须一致。2）活跃性，当客户端提交一个交易时可以快速的包含到日志中。在这文章中，将把状态机复制简称为共识。

在区块链中会不可避免存在大量不可信的节点。然后作者列举了对于大规模设置的两大协议：

1.传统协议如PBFT和Byzantine-Paxos等，它们在正常情况下确认事务会很快;但这些协议是出了名的复杂，使得实现测试、重新配置和维护相对困难。此外，这些协议通过采用异步(或部分采用异步)来实现“快速确认”，因此，他们天生最多只能容忍1/3的腐败节点。

2.区块链式的协议，代表是中本聪的原始区块链，这些协议在概念上很简单并且容忍少数腐败节点，这些协议虽然很优秀，但是它们确认事务的时间却很慢，早期的数学分析区块链式共识的工作已经指出，这种缓慢是区块链式协议所固有的，因为必须将预期的块间隔设置得足够大，以使协议保持安全性。

这时候产生的问题是，是否有某种方法可以同时获得这两个好处。不幸的是，早期的研究给出了否定的答案，这表明在经典或无许可的模型中，被称为“响应性”的快速事务确认是难以实现对抗1/3 (即使是静态的)腐败节点的。在这篇文章中作者考虑一种叫做乐观反应的新概念，它允许我们“规避”这个较低的风险这样我们在实践中大部分时间都能达到响应性，同时又能忍受少数人腐败的最坏情况。方法在乐观的情况下(绝大一部分人是诚实的)会拥有异步协议的快速本质;然后还保留了同步协议(如区块链)的弹性及其鲁棒性(如，支持零星参与)。更准确地说，展示了如何结合快速和简单 的“异步路径”（保证一致性但不活跃）并且只有在出错时才执行，(缓慢的)同步 “回溯”路径。

Thunderella范例

然后作者描述了什么叫做“快速”或者说“及时确认”。即一个协商一致协议是任何事务对一个诚实的节点输入时得到及时确认，只取决于网络的实际延迟，而不取决于网络延迟上任何已知的上界。从今以后,我们用δ表示实际的网络延迟，使用∆表示网络的一个先验已知上界延迟，∆可能作为输入提供给协议。

接着作者给出了乐观响应的条件：

1.最坏情况条件（表示为W），协议需提供最坏情况保证，包括一致性和“慢速”确认（例如，W =大多数诚实）。

2.乐观情况条件（表示为O⊆W），协议另外提供响应确认（例如，O =“3/4以上是诚实且在线的，并且某些指定的玩家（”领导者“）是诚实的”）。

作者主要是采用任何区块链协议满足W条件下的一致性和活性的范例，并将其转换为“基本上”满足相同条件W的一致性和活性的新协议（在许多情况下，就是同一个W），并且在条件O下满足乐观响应。

为了阐述方法，作者先给出一个简单的协议：

1.有一个指定的实体：领导者或者叫“加速器”。

2.交易需要发送给领导者，领导在交易上签字(增加序列号，可以理解成一个包含很多交易的区块)，并将签署的交易发送给“委员会”。

3.委员会成员“确认”所有领导者已签署的交易，每个序列号最多只有一个交易(即诚实的委员会成员不会对相同序号不同交易进行确认)。

4.如果一个交易已收到超过3/4的委员会签名 -- 将此类交易称为公证交易。 参与者可以直接输出他们最长的连续序列（就其序列号而言）公证的交易 - 所有这些交易都得到确认。

不难看出这个协议必须满足条件W' = “1/2的委员会是诚实的”。同时，它在条件O =“领导者诚实，委员会的3/4是诚实的”下满足乐观反应的活性。事实上，在这些乐观条件下，我们只需要两轮交流就可以确认一笔交易！这种方法非常实用，事实上，这个协议在实践中经常被使用。

然而，这种方法的问题是协议在W' 的条件下不能满足活跃性(甚至“低”活跃性)。如果领导有欺骗行为(或被直接撤职)，协议将暂停。

为了克服这个问题，作者利用底层(缓慢的)区块链协议，它满足 W =“大多数节点诚实”条件下的稳定性和活跃性。通俗的说，当参与者注意到交易没有得到领导者或委员会的确认，一些“证据”就会发送到底层区块链里面。然后我们会进入一个“冷静”时期，委员会成员会停止验证来自领导者的消息，但允许参与者广播到目前为止他们已经看到的经过公证的交易。冷静时期的区块长度(k块，k是安全参数)由底层区块链计算。最后，在冷静时期结束后，我们会安全的进入一个“缓慢时期”，在此期间内交易只允许在底层区块链中得到认证。下一步，如果需要我们可以重新筛选出一个领导者，然后进入一个新的乐观协议时期。

之所以要有冷静时期的原因是：如果没有这个时期，参与者可能不同意在进入“慢速模式”之前已经确认的一组交易，因此最终可能会出现不一致的情况。冷却期间，诚实的节点可以张贴所有他们看到的已公证的事务到(缓慢的)底层区块链，因此(缓慢的)将这类交易达到一致性;一旦我们(在冷却结束时)达成了这个一致的观点，我们就可以在区块链上完全切换到新的已确认的交易之上。

收集欺骗证据  如果一个节点注意到他的交易没有正被领导者或者委员会确认，他可以发送这个交易到底层区块链中，并且指示领导者确认它在区块链上看到的所有交易。

现在如果参与者们看到一些区块链上面在一个足够长的时间(时间长度(n块)由底层区块链计算)内没有得到认证的交易，他们就会知道领导者/委员会一定在欺诈或者不在线，于是应该进入冷静时期。（请注意，只要领导者可以在底层区块链上创建n个区块之前确认交易，他就不会被“错误地指责”;并且，由于底层区块链的安全性，这些区块不能创建得太快）

选择委员会  作者指出了两条路径：

1.让所有参与者变为委员会成员。最简单的方法。这种情况下，W' = W ,并且通常在W下具有一定的弹性。有一种基于这种方法的变种方法(增加了通讯复杂度)是在参与者集合中随机抽取出一些委员会成员(随机数的生成需要使用一个随机的oracle，Phil Daian, Rafael Pass, and Elaine Shi. Snow white: Provably secure proofs of stake. Cryptology ePrint Archive, Report 2016/919, 2016.)，并且定期更改委员会(已确保自适应安全)，但是只有在腐败“缓慢”时才能确保安全协议（确保攻击者在委员会被切换之前没有时间腐败整个委员会）。如果使用VRF和随机oracle“秘密地”进行子采样，我们还可以确保生成的协议在具有擦除的模型(甚至 “瞬间腐败”的模型)中自适应安全。

作者提到如果使用Thunderella构建加密货币，这些方法也可用于无许可设置：那么可以使用最近的“利益相关者”（也可能是“利益相关者”的子样本）组成委员会。

2.让“近期旷工”充当委员会成员。使用此方法需要注意的是要确保底层区块链是“公平的”，因为诚实开采区块的比例接近诚实玩家的比例。中本聪的原始区块链不是这种情况，但任何区块链都可以变成合理的区块链。 如果我们使用这种方法，生成的协议将是一致的，并且是在条件W（即，多数诚实）下，在条件O下也满足乐观的活跃度。(同样，这仅在“缓慢”腐败下提供安全性，所以近期矿工要在被腐败之前变化得足够快。)

不许可的Thunderella 如果我们使用第二种方法选择委员会成员，我们会得到如下定理：

定理1：(Thunderella在不许可的环境中，非正式定义)，假设有一个工作量证明的随机oracle，那么存在一个在非许可环境下有一致性和（无响应的）活跃性的状态机复制协议，只要攻击者在每一轮中的总在线计算能力不超过，其中是任意小的常数，而且对手需要很短的时间来自适应地破坏节点。此外，如果超过3/4的在线计算能力是诚实的和在线的，那么该协议在领导者诚实和在线的任何“时代”中实现响应性（在短期无响应的预热时段之后）。

许可的Thunderella 对于允许的环境也可以显示类似的定理("sleep model"或者"classic model"中。)

经典模式本质上是现有分布式系统和密码学文献采用的标准同步模型。 在这个模型中，所有节点都是预先生成的，它们的身份和公钥作为输入提供给协议; 此外，崩溃的节点被视为有缺陷并计入腐败预算。 在经典的同步网络中，我们表明经典的Dolev-Strong拜占庭协议可以扩展实现Thunderella的底层“区块链”。 在这种情况下，我们的Thunderella范例（使用第一种方法来实例化委员会）产生了以下非正式定理：

定理2：(Thunderella在许可的经典环境中(非正式定义))假设存在PKI和单向函数。存在状态机复制协议，其在经典环境中在任何f(f<n)个完全自适应的拜占庭式腐败下实现一致性和（无响应的）活跃性，其中n表示节点的总数; 此外，只要领导者是诚实的，而且个节点是诚实的，该协议就能实现响应。

Pass和Shi最近提出了"sleepy"模型，以捕捉“零星参与”在大规模许可共识中产生的要求。具体来说，"sleepy"模型实际上是受到无法分散的加密货币（如比特币）的启发，其中节点可能在协议期间频繁出入，并且协议应该保证一致性和活力，即使对于将加入的节点，或者对于有一个短暂的停机，醒来重新加入协议的节点来说也是如此。

sleepy模型本质上是“许可的”，因为已批准的协议参与者及其公钥是先验已知的并且作为输入提供给协议。 然而，与经典设置不同，1）节点被允许不参与（即，休眠）; 2）睡眠节点不被视为有缺陷; 3）协议可能事先不知道有多少节点会出现。 相比之下，在经典环境中，非参与节点被视为已经崩溃并计入腐败预算; 而且，经典协议不需要保证已经崩溃但稍后唤醒以重新加入的节点的一致性和活跃性。

在sleepy模型中，Pass和Shi表明，粗略地说，当大多数在线（即非睡眠）节点是诚实的时候，我们可以达成共识，有趣的是，与经典同步模型不同，它也证明了没有状态机复制协议可以容忍（在线节点之间）超过1/2的腐败。

Thunderella范例（再次使用第一种选择委员会的方法）可以在sleepy模型中使用sleepy共识协议作为底层区块链进行实例化。 这在sleepy环境中产生了以下非正式定理（我们假设对手可以自适应地将诚实的节点置于睡眠状态）。

定理3：(Thunderella在许可的sleepy环境中(非正式定义))假设存在PKI，增强的陷门排列(?)和公共参考字符串（CRS）。 存在一种状态机复制协议，它可以在一个有静态腐败的sleepy环境中实现一致性和（无响应）活跃度，只要个在线节点在任意小的常数下的每一轮都是诚实的，此外，如果超过3/4的节点是诚实的和在线的，该协议在任何领导者诚实和在线的时代内（在短暂的无响应预热期之后）实现了响应。

事实上，假设存在VRF和一个随机oracle，上述定理也可以延伸到使用自适应安全版本的sleepy共识作为Thunderella的底层区块链的自适应腐败(使用擦除)中。

乐观诚实阈值的下界  作者还证明了对3/4的乐观界限是没必要紧张的：对于大多数人而言，没有（最坏情况下）一个弹性的协议可以在超过1/4的节点被破坏时乐观地响应。

实际考虑事项:即时确认和可伸缩性  低延迟和中本聪的区块链协议的可伸缩性差通常被视为比特币以及其他加密货币的主要瓶颈。

作者的范例提供了一个非常实用且简单的方法来解决这个问题。Thunderella范例范例展示了如何在当前运行的区块链之上构建，以实现交易的“乐观即时确认”。此外，协议中值得注意的是节点只需要发送交易给领导者，领导者又领导委员会进行交易确认。最值得注意的是，底层区块链基本上只在出现问题时才使用，并且在确认之前不需要将块分发到整个网络; 因此，Thunderella还解决了中本聪的区块链协议的可扩展性问题。 当然，这两种保证都只是“乐观” 的，但可以说，在正常情况下，人们可以期望3/4的节点诚实行事，并且领导者可以被激励（支付）以履行其职责（如果不履行将会被踢出去）。 因此，作者的方法是一种切实可行的方法，可以规避当今加密货币的主要瓶颈。

对比  从表面上看，我们的想法是回忆古典风格的协议，如PBFT和Byzantine-Paxos。 特别是，像PBFT这样的协议也有一个非常简单的正常路径，包括O(1)轮的投票。 然而，当正常路径被卡住时，PBFT式协议又回归到“视图变化”机制，这种机制也是响应性的。并且由于需要处理异步，因此这些协议在最坏的情况下只容忍1/3的腐败。（此外，这种方法不适用于无许可设置的协议）。 作者的关键见解是在最坏的情况下回到同步路径，从而允许我们绕过部分同步的1/3下限，但在大多数情况下仍然在实践中响应。 此外，由于协议基本上是同步的，因此受益于同步协议（例如，区块链）所享有的简单性和鲁棒性。

有趣的是，与大多数PBFT或Paxos式协议相比，Thunderella在快速路径中也是一个更快的因子。 PBFT式协议即使在正常路径中（而Thunderella只有一个）都需要多轮投票，并且后几轮是准备改变视图的可能性所必备的。 尽管可以将正常路径压缩为单轮投票，但这通常需要牺牲弹性（例如，仅容忍1/5损坏）或通过在正常路径上添加另一个乐观层来实现。因此使得原本已经很复杂的协议变得更加复杂化。

相关工作

状态机复制：经典和区块链式方法

Pass和Shi最近的工作指出了古典风格和区块链风格共识之间的一个根本区别。 大多数经典协议，同步和异步协议，都依赖于已经收集了足够多票数的节点来取得进展; 因此，这些协议会在参与是零星的模型中失败，并且无法预先确定出现的参与者的确切数量。 更具体地说，经典的共识模型将悲观地处理未显示为故障的节点（也称为崩溃故障）; 如果没有显示太多节点，则协议无法取得进展。 相比之下，无论实际出现多少玩家，区块链式协议都可以取得进展。 此外，区块链式共识也被证明在玩家数量随时间变化的环境中是安全的。

经典的共识协议通常部署在相对小规模和许可的设置中。 由于比特币而巧妙的中本聪区块链，在未许可设置中的共识首先被经验证明是可能的。 虽然最初的中本聪区块链依赖于工作证明来解决在未许可设置中的Sybil攻击，但从那时起已经提出了其他建议，以便在未许可的环境中安全地建立身份 - 例如，股权证明是一种最常被引用的方法，其中加密货币系统的利益相关者负责对交易进行投票。 最近一些作品也探讨了在无权限的情况下采用古典风格的共识，其中诸如利益证明(pos)之类的方法可用于建立身份。

其他密切相关的工作

作者回顾了最近将经典共识和区块链结合起来的作品，尽管这些作品具有不同的性质，我们将在下面解释。在这些作品中，混合共识是唯一已知的正式正确方法，而且是唯一已知的实现响应性的方法。从理论的角度来看，我们的结果与混合共识无法比拟：我们在最坏的情况下容忍高达1/2的腐败，并且仅在乐观的情况下提供响应，但在最坏的情况下不提供；相比之下，即使在最坏的情况下，混合共识也能实现响应性，但作为交换，它们的协议只能容忍高达1/3的损坏，并且这证明是任何最坏情况响应协议所固有的，即使假设在工作量证明下。从实际角度来看，Thunderella更有可能成为现实世界实施中的首选协议，部分原因在于它的简单性 - 相比之下，混合共识需要一个完整的经典协议，如PBFT和Byzantine Paxos作为子程序，以及因此继承了这些协议的复杂性。

有一项研究研究了拜占庭协议，当条件比最坏情况的错误模式更为良性时能够提前停止：例如，实际的故障节点数量 小于最坏情况的弹性界限。 但是，这些作品的性质与我们的不同。 首先，这些早期的工作关注在同步轮次较少的时候停止，并且它不是实现响应性的目标的一部分。 其次，虽然一些已知的下界表明实际轮次的数量必须与故障处理器的实际数量成比例，但是请注意，这些下限仅适用于确定性协议，因此它们不适用于我们的设置。

最后，在早期的作品中描述了组合异步和同步的想法；其他工作也提出了组成多个BFT协议的框架。 然而，据我们所知，早期的工作都没有以我们的方式结合同步回退路径和异步乐观路径，允许我们在最坏情况下容忍超过1/3的损坏，同时在大部分的训练中仍然响应。

与以太坊目前的努力相关

以太坊是比特币紧随其后的第二大分散加密货币，它已经在研究将pos共识算法加入下一代以太坊中。以太坊在工作量证明下似乎没有立即确认机制，而是设计了一个两阶段的议程，在最初的过渡阶段，利益相关者的投票和工作证明将共存，见最近的在线 Vitalik Buterin的博客文章。 具体而言，利益相关者将对其现有的工作证明区块链上的交易或区块进行投票。 Vitalik Buterin的博客文章然后提出了一套“极小的削减条件”，以惩罚那些行为恶意的选民（例如，那些投不定票的人）。 然而，以太坊的目标不是实现乐观的即时确认。

其他人也试图在区块链中实现即时终结——然而，到目前为止都不是一种可证明的安全方法，一些民间的方法甚至显得有缺陷。