在身份未知且动态变化的拜占庭将军中实现即时终局

本文针对拜占庭将军问题提出了非常简单的解决方案，在参与者身份未知且动态变化的情况下实现确定性且无条件的安全保障，同时规避了 PoW 共识机制的能耗问题以及最长链共识协议的高延时问题。因此，我们解决了中本聪共识中最大的难题，即：概率性终局（probabilistic finality）、高延时以及 PoW 共识的能耗问题，并同时保留了无需许可模式的核心价值。 

上述目标乍一看似乎遥不可及，当参与者不断变动，甚至连活跃的参与者数量都不得而知的时候，怎么能达成共识呢？

Pass 和 Shi 提出了“休眠”模式（Sleepy model），摒弃了 PoW 机制，并借鉴了无需许可模式中的两大核心支柱。第一是连续性。要保障连续性，就需要在当前活跃的参与者之间同步传输消息，以便在参与者下线时将数据转移给别的参与者。第二是在任意时间点，活跃的（同步连接的）参与者的身份是未知且动态变化的，并且超过半数的参与者是诚实的。休眠共识（Sleepy Consensus）在这两个假设基础上（注：下文中会详述）解决了拜占庭共识问题，但仍未解决概率性安全和最长链协议的高延时问题。  

Atsuki 和 Ren 近期展开的一项研究中设定了一个类似的参与模式，其中的参与者身份未知且动态变化，不过区别是这个设定中对于同步的假设更为实际，即不存在无限缓冲。这项研究为拜占庭共识提出了全新的解决方案，实现了确定性的安全保障以及预期的恒定延时。然而，只有当参与者在一段时间内固定不变，才能保障活跃度。而且即使做到这一点，恒定延时水平仍然较高。

我们的研究将诚实参与者的门限稍微调高了一点，即：从二分之一调高至三分之二，因此针对参与者身份未知且动态变化的情景提出了一个非常简单的解决方案，可以很好地解决拜占庭共识问题。这个方案可以实现确定性且无条件的安全保障，以及（很低的）预期恒定延时，因此可以有效解决上述问题。另外这里还要强调一遍，我们的这个方案非常简单。正如下文所述，相比参与者身份已知且不变的场景中的异步式共识协议，我们的算法并没有更复杂或有明显不同。

本文将展示如何实现一次性的二元拜占庭共识（binary Byzantine agreement）。在之后的文章里，我们将 1）延伸至多值共识；2）扩展至一系列共识决策（即：原子广播问题）；以及 3）采用领导制来改善平均每一回合的复杂度。

为了方便阐述，我们暂且将时间划分为多个“回合”。实际上，这个模式可以基于连续的时间，我们的解决方案也可以扩展至连续的时间。

为了在协议中实现数据的连续性，无需许可的协议建立了一个稳健的同步假设，即：我们的回合模式中每一对诚实参与者（也称为“节点”）之间的信道传播延迟存在一个已知的上限。

同步通信——如果诚实节点 p 在 r 回合发送了一条消息，那么在 r+1 回合中每个活跃的诚实节点 q 都会收到这条消息。 

无需许可的共识协议通常会假设超过半数的活跃节点都是诚实的。而我们则将诚实参与者的门限调高了一些。这样做可以极大简化构建过程。

诚实的参与者——每一回合中都有未知数量的活跃参与者，其中超过三分之二的参与者是诚实的。

在这里有必要进一步阐述一下这个参与假设。在动态情景中，每一轮都会有参与者离开，其中包括问题节点。我们必须假设如果一个问题节点下线，那么这个节点的消息不会在接下来的回合中出现。这个假设比起之前的方案来说弱了很多。之前的方案假设所有的问题节点在整个执行过程中都保持活跃状态。

身份未知且动态变化的参与模式——简而言之，我们提出了以下模式：

任意时间点的活跃节点身份未知，数量未知。这些节点在每一轮都可能全部被替代，并基于以下假设：

这个问题被多次讨论过。简而言之，就是在二元共识中，一组参与者持有初始输入值∈ {0,1}，最终对输出的值达成共识，并满足以下条件： 

我们针对一次性的二元共识提出了一个解决方案，保障安全性并将终局回合数维持在一个较低的恒定水平。

首先，我们来看一下这个模式最关键的转移机制。

身份未知且动态变化的法定节点数量要求（Unknown and Dynamic Quorum，下文简称 UDQ）——每个节点在 r+1 回合收到在 r 回合发送的一组消息。我们发现以下关键点：

假设每条协议消息包含一个数值。那么以下保障就成立：

由于 UDQ 的存在，因此很容易在两次广播中构建一次性二元共识协议。具体机制如下： 

协议的初始回合中，节点会将输入的数据广播出去，然后就在 collection-GA 与 decision-GA 之间来回切换。在一个回合中，活跃的节点会监听输入的消息（即：上一轮广播的消息），处理消息并广播一条消息出去。

初始回合——第 0 回合：

Decision-GA r+2：

在 collection-GA 回合中，节点收到包含其他节点采用的数值的消息。  在 collection-GA 回合末尾，如果一个节点收到超过 2/3 的 (collect, b) 发来数值 b，则广播 (propose, b)；否则广播 (propose, “empty”)。同时，一个节点广播 (VRF, c) ，其中 VRF 是一个独特的伪随机数值，并可以使用节点公钥和回合编号进行验证；而 c 则是在本地“抛硬币”的结果。这里要注意，在初始回合中，节点会用自己的数据输入来发送 collect 消息。

在 decision-GA 回合中，节点会收到 (propose, *)。每个收到超过 2/3(propose, b) 消息的节点都可以确定数值 b。每个收到超过 1/3(propose, b) 消息的节点都可以将 b 作为当前数值采用。其他节点在消息 (VRF, b’) 中采用随机数 b’，这条消息的（经过验证的）VRF 值是所有收到的 VRF 中最高的。在 decision-GA 回合末尾，每个节点 p 都会广播 (collect, vp)，其中包含其采用的数值。

主张 -1[独特性 - 采用]——在 decision-GA 回合中，最多有一个数值 b 必须被采用。数值要被采用，必须被上一个 collection-GA 回合中超过 1/3 的消息接收。鉴于 UDQ- 有效性，这个数值是由一个诚实的发送者发送的。不过鉴于 UDQ- 独特性，在一个 collection-GA 回合中，最多有一个数值 b 可能被诚实节点广播。

主张 -2[安全性]——如果一个诚实节点在 decision-GA 回合中确定了数值 b，那么鉴于 UDQ-GA，剩余每个诚实节点都会收到来自上一个 collection-GA 回合超过 1/3 的消息，消息中包含 (propose, b)。鉴于“独特性 - 采用”，只有 b 是必须被采用的。因此，每个诚实的节点都在 decision-GA 回合中采用 b。显而易见，collection-GA 和 decision-GA 回合的交替迭代始于所有诚实节点都采用数值 b，终于所有诚实节点都确定数值 b。   

主张 -3[终止]——如果所有诚实节点都起始于数值 b，那么终止是很容易的。如果做出了决策，那么鉴于 UDQ- 采用，最多一个数值 b 必须要被采用。在 1/2 的概率下，b 将成为最终胜出的 VRF 值，并被每个人采用。

感谢 Lorenzo Alvisi、Ittay Eyal、Jacob Leshno、Kartik Nayak 和 Youer Pu 参与讨论，为本论文提供启发。