在身份未知且动态变化的拜占庭将军中实现即时终局
作者: Dahlia Malkhi (Chainlink Labs), Atsuki Momose (UIUC), Ling Ren (UIUC)
概要
本文针对拜占庭将军问题提出了非常简单的解决方案,在参与者身份未知且动态变化的情况下实现确定性且无条件的安全保障,同时规避了PoW共识机制的能耗问题以及最长链共识协议的高延时问题。因此,我们解决了中本聪共识中最大的难题,即:概率性终局(probabilistic finality)、高延时以及PoW共识的能耗问题,并同时保留了无需许可模式的核心价值。
上述目标乍一看似乎遥不可及,当参与者不断变动,甚至连活跃的参与者数量都不得而知的时候,怎么能达成共识呢?
Pass和Shi提出了“休眠”模式(Sleepy model),摒弃了PoW机制,并借鉴了无需许可模式中的两大核心支柱。第一是连续性。要保障连续性,就需要在当前活跃的参与者之间同步传输消息,以便在参与者下线时将数据转移给别的参与者。第二是在任意时间点,活跃的(同步连接的)参与者的身份是未知且动态变化的,并且超过半数的参与者是诚实的。休眠共识(Sleepy Consensus)在这两个假设基础上(注:下文中会详述)解决了拜占庭共识问题,但仍未解决概率性安全和最长链协议的高延时问题。
Atsuki和Ren近期展开的一项研究中设定了一个类似的参与模式,其中的参与者身份未知且动态变化,不过区别是这个设定中对于同步的假设更为实际,即不存在无限缓冲。这项研究为拜占庭共识提出了全新的解决方案,实现了确定性的安全保障以及预期的恒定延时。然而,只有当参与者在一段时间内固定不变,才能保障活跃度。而且即使做到这一点,恒定延时水平仍然较高。
我们的研究将诚实参与者的门限稍微调高了一点,即:从二分之一调高至三分之二,因此针对参与者身份未知且动态变化的情景提出了一个非常简单的解决方案,可以很好地解决拜占庭共识问题。这个方案可以实现确定性且无条件的安全保障,以及(很低的)预期恒定延时,因此可以有效解决上述问题。另外这里还要强调一遍,我们的这个方案非常简单。正如下文所述,相比参与者身份已知且不变的场景中的异步式共识协议,我们的算法并没有更复杂或有明显不同。
本文将展示如何实现一次性的二元拜占庭共识(binary Byzantine agreement)。在之后的文章里,我们将1)延伸至多值共识;2)扩展至一系列共识决策(即:原子广播问题);以及3)采用领导制来改善平均每一回合的复杂度。
身份未知且动态变化的参与模式
为了方便阐述,我们暂且将时间划分为多个“回合”。实际上,这个模式可以基于连续的时间,我们的解决方案也可以扩展至连续的时间。
为了在协议中实现数据的连续性,无需许可的协议建立了一个稳健的同步假设,即:我们的回合模式中每一对诚实参与者(也称为“节点”)之间的信道传播延迟存在一个已知的上限。
同步通信——如果诚实节点p在r回合发送了一条消息,那么在r+1回合中每个活跃的诚实节点q都会收到这条消息。
无需许可的共识协议通常会假设超过半数的活跃节点都是诚实的。而我们则将诚实参与者的门限调高了一些。这样做可以极大简化构建过程。
诚实的参与者——每一回合中都有未知数量的活跃参与者,其中超过三分之二的参与者是诚实的。
在这里有必要进一步阐述一下这个参与假设。在动态情景中,每一轮都会有参与者离开,其中包括问题节点。我们必须假设如果一个问题节点下线,那么这个节点的消息不会在接下来的回合中出现。这个假设比起之前的方案来说弱了很多。之前的方案假设所有的问题节点在整个执行过程中都保持活跃状态。
身份未知且动态变化的参与模式——简而言之,我们提出了以下模式:
任意时间点的活跃节点身份未知,数量未知。这些节点在每一轮都可能全部被替代,并基于以下假设:
- PKI(公钥基础设施)——参与的节点来自有限的宇宙。每个节点的身份都绑定一枚公钥,并且节点自己持有对应私钥。
- 这里要注意的是,PKI只用于VRF和活跃度。发送消息者无需对消息签名。
- 活跃的节点——每一回合r都有一组身份未知的活跃节点,数量nr未知,并满足条件 nr ≥ 3fr + 1。
- 同步通信——在r回合中,诚实的活跃节点收到r-1回合中诚实节点广播的所有消息。
拜占庭共识问题
这个问题被多次讨论过。简而言之,就是在二元共识中,一组参与者持有初始输入值∈ {0,1},最终对输出的值达成共识,并满足以下条件:
- 安全性:两个诚实节点输出的值是相同的。
- 有效性:如果所有诚实节点一开始都是相同的输入值,那么输出的就是那个值。
- 活跃度:最终所有诚实节点都要输出一个值。
在参与者身份未知且动态变化的情况下达成二元共识
我们针对一次性的二元共识提出了一个解决方案,保障安全性并将终局回合数维持在一个较低的恒定水平。
首先,我们来看一下这个模式最关键的转移机制。
身份未知且动态变化的法定节点数量要求(Unknown and Dynamic Quorum,下文简称UDQ)——每个节点在r+1回合收到在r回合发送的一组消息。我们发现以下关键点:
- 用R来表示r+1轮中某一诚实节点收到的未知消息数量,则R ≤ nr。
- 由于是同步通信,因此这R个消息中至少有⅔nr ≥ ⅔ R 的消息被r回合的诚实节点收到。
- R条消息中有未知数量的tr≤ ⅓ R 条消息来自r回合的问题节点。
假设每条协议消息包含一个数值。那么以下保障就成立:
- UDQ-独特性——在某一回合中,如果节点p收到超过2/3的消息都包含数值b,而另一个节点q收到了超过2/3的消息都传输了数值b’,则b = b’。这里要注意,UDQ-独特性对于静态情景下的法定节点数量交集(quorum-intersection)也有同样的保障,但无法将签名过的一组消息作为收到2/3消息的证明转移出去。
UDQ-独特性是成立的,因为如果诚实节点p在r+1回合中收到超过2/3的r回合的消息,并且消息中的数值都是b,那么r回合中大多数诚实的消息中都包含数值b。依据如下:
⅔ R – tr = ⅔ (nr– fr + tr) – tr = ½ (nr – fr) + ⅙ (nr – fr – 2tr) > ½ (nr – fr) - UDQ-有效性——如果一个诚实节点在r+1回合收到超过1/3的r回合消息,并且消息中包含数值b,那么某个诚实节点就一定发送过包含数值b的消息。这一条成立的依据与上一条类似:
⅓ (R – tr) = ⅓ (nr– fr + tr) – t_r = ⅓ (nr – fr – 2tr) > 0 - UDQ-分级共识(graded-agreement,下文简称GA)——如果一个诚实节点p在r+1回合收到超过2/3的r回合消息,且消息中包含数值b,那么另一个诚实节点在r+1回合中收到至少1/3的r回合消息包含数值b。
由于UDQ的存在,因此很容易在两次广播中构建一次性二元共识协议。具体机制如下:
协议的初始回合中,节点会将输入的数据广播出去,然后就在collection-GA与decision-GA之间来回切换。在一个回合中,活跃的节点会监听输入的消息(即:上一轮广播的消息),处理消息并广播一条消息出去。
节点p的协议
初始回合——第0回合:
- 某一节点向所有节点广播(0, collect, input)
Collection-GA r+1:
- 用S-collect代表收到的消息集合(r, collect,*)
- 某一节点向所有节点广播:
如果超过2/3的S-collect是(r, collect, b),则广播(r+1, propose, b);
否则广播(r+1, propose, “empty”)。
- 同时,一个节点向所有节点广播:
(r+1, VRF, c),其中c是随机数。
Decision-GA r+2:
- 用S-propose代表收到的消息集合(r+1, propose,*)
- 节点p按照以下方式处理S-propose:
如果超过2/3的S-propose为 (r+1, propose, b),则确定b
如果超过1/3的S-propose为(r+1, propose, b),则采用vp ← b
否则,采用vp ← v值来自VRF值最高的(r+1, VRF, v)
- 节点p向所有节点广播:(r+2, collect, vp)
在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值,并被每个人采用。
针对参与者身份未知且动态变化的解决方案对比
认证方式 | 安全保障 | 延迟 | 诚实节点门限 | |
中本聪共识2008 | 工作量证明 | 概率性 | 高 | 超过半数 |
休眠共识 2016 | PKI | 概率性 | 高 | 永久失效下超过半数 |
Atsuki&Ren 2022 | PKI | 确定性 | (较高的) 恒定水平 | 永久失效下超过半数 |
本研究 2022 | 采用经过认证的信道保障安全性;采用PKI保障活跃度 | 确定性且无条件 | (较低的) 恒定水平 | 2/3 |
致谢
感谢Lorenzo Alvisi、Ittay Eyal、Jacob Leshno、Kartik Nayak和Youer Pu参与讨论,为本论文提供启发。
推荐阅读
- [Pass, Shi, 2016] The Sleepy Model of Consensus
- [Bagaria, Kannan, Tse, Fanti, Viswanath, 2019] Prism: Deconstructing the blockchain to approach physical limits.
- [Khanchandani, Wattenhofer, 2021] Byzantine Agreement with Unknown Participants and Failures
- [Lewis-Pye, Roughgarden, 2021] Byzantine Generals in the Permissionless Setting
- [Goyal, Li, Raizes, 2021] Instant Block Confirmation in the Sleepy Model
- [Deb, Kannan, Tse, 2021] PoSAT: Proof-of-Work Availability and Unpredictability, Without the Work
- [Pu, Alvisi, Eyal, 2022] Safe Permissionless Consensus
- [Guo, Ren, 2022] Bitcoin’s Latency–Security Analysis Made Simple
- [Atsuki, Ren, 2022] Constant Latency in Sleepy Consensus