异步共识协议是一种不依赖于任何时间假设的共识协议，其在实际应用中具有更强的竞争力及实用性。异步二元拜占庭共识算法旨在使系统中所有参与节点对某个二元值 $\{0,1\}$ 达成一致共识。比较典型的拜占庭共识协议有早期的半同步 PBFT 协议，和16年提出的异步 HoneyBadger 协议，而 HoneyBadger 是对本文将要介绍的 ABBA 协议的改进。

最近要做毕设，阅读了 ABBA 协议的原论文《Random Oracles in Constantinople: Practical Asynchronous Byzantine Agreement Using Cryptography》，其最早于2000年在顶会上被提出，之后整理发表在了 Journal of Cryptology 期刊上。我发现网上 ABBA 协议的介绍几乎没有，其中还是有一些比较新颖的思想，故写下这篇博客。

一些概念

1. 失效模型（failures model）

是对分布式系统中节点可能出现的故障类型的假设，主要包括以下两种：

• Crash failures：故障失效模型。网络中部分节点遭遇客观因素（如网络延迟、宕机）导致的故障，从而不能正常工作。这些节点在故障之前，诚实地执行算法和协议。处理这类模型的共识算法称为故障容错算法（Crash Fault Tolerance, CFT）。
• Byzantine failures：拜占庭失效模型。网络中的部分节点不遵守算法和协议的规范，也被称为任意失效模型（arbitrary failures）。这些节点被称为拜占庭节点，它们的行为往往是恶意的、有意为之的。处理这类模型的共识算法称为拜占庭容错算法（Byzantine Fault Tolerance）。

很显然， Crash failures是Byzantine failures的一个子集。

2. 网络（时序）模型

是对底层网络中消息传输时延的假设，主要包括以下三种：

• Synchronous network：同步网络。假设网络中的消息能够在一个已知的时间 $\Delta$ 内到达。即最大消息延迟是确定。Bitcoin、Ethereum等基于的Pow共识协议，一致性和活性都采用同步假设。
• Partially-synchronous network：半同步网络。网络中消息在某限定时间后到达所有共识节点的的概率与时间的关系是已知的，但最大消息延迟 $\Delta$ 仅在一个未知延迟 GST（global stabilization time）之后才能确定。比如 Raft、PBFT 都是基于半同步网络假设设计的共识协议。
• Asynchronous network：异步网络。正常节点发出消息，在一个时间间隔内可以送达目标节点，但是该时间间隔未知，即最大消息延迟 $\Delta$ 未知。

3. 问题陈述（problem specifications）

失效模型和网络模型给出了系统环境假设，下面对几个共识的概念（agreement abstraction）进行一下区分，在拜占庭容错模型中，主要包括三类问题：

• Byzantine Agreement：只有单一源节点（single source）具有初始值。特别强调是由 Lamport 等人提出的拜占庭将军问题的抽象，消息是由将军节点（the general）提出并广播给副官节点（lieutenants）的，即将军节点是单一源节点。
• Consensus：所有节点都有初始值。该问题可以看成每个节点都是一个将军节点，每个将军都对同一事件有自己的看法；或者，系统中每个节点都是一个副官节点，其初始值是由一个系统外的（可能作恶的）将军下达。因此，每个节点的初始值可能相同，也可能不同。
• Interactive Consistency：又叫 Vector Consensus，所有节点都有初始值。顾名思义，该问题最终要对一个向量值达成共识。

这些问题主要由agreement、validity、termination几个属性来定义，不同具体问题的上述几个属性的含义也不同。通俗来讲，解决一个问题的算法最终要使系统满足该问题所定义的属性，属性不同自然算法也不同。更详细的区分可以见下图：

事实上，以上三个问题是等价的，可以通过规约的方式来证明。尤其是 Byzantine Agreement 和 Consensus 界限不是很明显，在实际中也不太刻意区分，比如本文要介绍的论文虽然标题是“Byzantine Agreement”，但实际上讨论的是一种“Consensus”。一般在翻译的时候，统称为“共识”就可以了。

背景

以上介绍的是一些共识算法研究的通用概念，那么 ABBA 协议是什么失效模型？什么网络模型？解决的是什么问题呢？从论文 《Random Oracles in Constantinople: Practical Asynchronous Byzantine Agreement Using Cryptography》 标题中我们就可以得出答案：ABBA 协议是一个在有拜占庭节点的异步网络中，解决拜占庭共识（Byzantine Agreement / Consensus）问题的一种算法。

早在1985年，Fischer, Lynch and Patterson 三位作者发表了著名的 FLP 不可能原理：

在网络可靠，但允许节点失效（即便只有一个）的最小化异步模型系统中，不存在一个可以解决一致性问题的确定性共识算法。

FLP 不可能原理告诉我们：如果要在异步网络中解决一致性问题，只能在算法中引入随机性，简单来说就是当协议无法达成共识的时候，借助上帝抛骰子的方式随机选择一个结果作为最终结果；或者，可以放宽一致性的要求，用确定性算法解决所谓的“弱一致性”问题。

ABBA 协议没有放宽对一致性的要求，那么自然是引入了随机性。这导致了它的运行轮数（round）是不确定的，很可能要运行很多很多轮，但经过证明，运行轮数的期望值是 $O(1)$ 的。这也说明，该算法是“Practical”的，实际可行的，后面也会对这一点做具体分析。

协议流程

先来介绍 ABBA 协议所涉及到的角色，包括可信第三方（the dealer）、诚实节点、腐化节点，它们的数量关系及能力如下：

• 可信第三方（the dealer）：$1$ 个。负责初始化各节点状态，即分发密钥。
• 诚实节点：$n-f$ 个。诚实地执行协议的各个步骤，拥有多项式时间的计算能力。
• 腐化节点：$f$ 个。不诚实地执行协议，对网络拥有绝对控制权（分发、修改、插入消息），拥有多项式时间计算能力。

其中，$n$ 为网络中的节点总数。此外，还有一个参数 $t$ 代表敌手最多腐化节点的个数，显然有 $f \leq t$ ，一般认为 $f=t$ 即可。

整个协议分为 pre-processing、pre-vote、main-vote、check for decision、common coin 五个步骤，依次记为 $step_0\ -\ step_4$。除了 $step_0$ 在初始阶段执行一次外，其余四个步骤在每轮循环执行，如下图所示。

该协议最终要达成的目的是让系统中所有的诚实节点（$n-t$ 个）对某一个事件 $ID$ 达成一个二元共识。不同的协议实例可以处理不同的事件，例如系统中的实例1处理事件 $ID_1$，实例2处理 $ID_2$。可以类比计算机里程序与进程之间的关系，一台电脑可以运行很多个word，处理不同文档。只不过我们这里的“计算机”是分布式的。

简单起见，我们只考虑单个事件 $ID$。系统中节点记为 $P_i$，每个节点拥有针对该事件有一个二元初始值 $V_i \in \{0,1\}$，可以认为是节点对事件 $ID$ 的意见。显然，诚实节点之间的初始值 $V_i$ 也可能是不同的。下面我们以 $P_i$的视角看系统如何通过 ABBA 协议达成共识。

1. 预处理 pre-processing

假设可信第三方（the dealer）已经将密钥分发，即 $P_i$ 拥有了门限签名的公私钥、消息认证码密钥等，在该步骤它执行以下算法：

1. 对消息 $(ID,pre-process,V_i)$ 使用门限签名算法 $S_0$ 进行签名，得到自己的签名份额 $sign\ share$，广播$(ID,pre-process,V_i,sign\ share)$。
2. 收到 $2t+1$ 个 $pre-process$ 消息后，选出至少 $t+1$ 个对同一个二元值 $b \in \{0,1\}$ 的签名份额，将 $b$ 作为第一轮 $pre-vote$ 的值。

这里用到了一个 $(n,t+1,t)$ 门限签名 $S_0$，即 $n$ 个用户分享签名份额，其中有 $t$ 个恶意节点，收集 $t+1$ 个份额可以恢复出签名。和后面用到的 $(n,n-t,t)$ 的双阈值门限签名$S$不同，注意区分。

2. 预投票 pre-vote(r=1)

pre-vote 相对复杂一些，第一轮和之后的算法是不同的。$r>1$ 的情况将在最后介绍，先来看 $r=1$ 的情况：

1. 将 pre-processing 阶段选择的 $b$ 值作为投票值，构造关于消息 $(ID,pre-process,b)$ 的门限签名作为证据 $justification$。
2. 对消息 $(ID,pre-vote,r,b)$ 使用双阈值门限签名算法 $S$ 进行签名，得到自己的签名份额 $sign\ share$，广播$(ID,pre-vote,r,b,justification,sign share)$。

简单来说，$r=1$ 时，就是 pre-vote 投票值是由 pre-processing 决定的，然后需要向其他人证明你这么投是有理有据的，依据就是证明你确实在 pre-processing 阶段收到了 $t+1$ 个你这一步要投票的二元值的消息，那么只需要把签名构造出来就可以证明啦。

3. 主投票 main-vote

main-vote 阶段 $P_i$ 将根据 pre-vote 的情况决定它的 main-vote 值：

1. 收集 $n-t$ 个有效的 pre-vote 消息，投票值 $v$ 与 pre-vote 消息的关系为$$v=\left\{\begin{aligned} 0 & & n-t\ pre-votes\ for\ 0\\1 & & n-t\ pre-votes\ for\ 1\\abstain & & pre-vote\ for\ 0\ and\ 1\end{aligned}\right.$$如果收到的消息中全都是对同一0/1值的 pre-vote，那么此时 main-vote 的值就是相应的0/1值；否则，本次 main-vote 弃权。
2. 关于 $justification$：非弃权 main-vote 的证据为对 $(ID,pre-vote,r,b)$ 的双阈值门限签名；弃权 main-vote 的证据为两个不同取值的 pre-vote 的证据的结合。
3. 对消息 $(ID,main-vote,r,v)$ 使用双阈值门限签名算法 $S$ 签名，得到自己的签名份额 $sign\ share$，广播$(ID,main-vote,r,v,justification,sign\ share)$

非弃权的情况很好理解，收到的全都是对同一值的 pre-vote，那么肯定投一样取值的 main-vote，证据也就是 $n-t$ 个 pre-vote 组成的双阈值门限签名。反之，如果 pre-vote 不全是同一值，那么就采用比较保守的策略——弃权，这时就需要证明确实收到了两个不同取值的 pre-vote，也就是需要把两者的证据结合起来作为新的证据。

4. 决策检验 check for decision

这一步将根据 main-vote 的情况来决定是否能作出决策：

1. 收集 $n-t$ 个有效的 main-vote 消息，如果它们全都是对同一二元值 $v$ 的投票，那么 $P_i$ 此时就可以对事件 $ID$ 作出断言（make decision）：事件 $ID$ 的共识值为 $v$。
2. 若 $P_i$ 做出了断言，那么再执行一轮协议就可以退出（执行完下一轮的 main-vote 就可以）；否则，继续执行若干轮。

$P_i$ 作出断言后之所以要继续执行，是为了帮助其他节点 make decision 以达成共识。事实上，可以证明下一轮所有诚实节点都将达成共识。

5. 抛硬币 common coin

common coin 是异步共识协议引入随机性常用的一种方法，在 ABBA 协议中 common coin 可以采用双阈值门限签名 $S$ 来实现，将签名值做一个哈希就可以得到硬币值。$P_i$ 在这一步执行的算法如下：

1. 针对硬币名 $ID||r$ 计算一个 $coin share$，广播消息 $(ID,coin,r,coin share)$。
2. 收集 $n-t$ 个有效的 $coin share$，构造出硬币值 $F(ID||r) \in {0,1}$。

6. 预投票 pre-vote(r>1)

走完一遍协议的第一轮后，我们再回过头来看此时的 pre-vote 步骤该怎么执行，$r>1$ 时，pre-vote 的投票值与 $r-1$ 轮的 main-vote 有关：

1. 收集 $n-t$ 个有效的 main-vote 消息，投票值 $b$ 与 main-vote 消息的关系为$$b=\left\{\begin{aligned} 0 & & there\ is\ a\ main-vote\ for\ 0\\1 & & there\ is\ a\ main-vote\ for\ 1\\F(ID||r) & & all\ main-votes\ are\ abstain\end{aligned}\right.$$如果收到的消息中存在0/1的 main-vote，那么此时 pre-vote 的值就是相应的0/1值，我们将此时的 pre-vote 称为 hard pre-vote；否则，pre-vote 的值取自 $r-1$ 轮的抛硬币结果，此时的 pre-vote 称为 soft pre-vote。
2. 关于 $justification$：hard pre-vote 的证据为对 $(ID,pre-vote,r-1,b)$ 的双阈值门限签名；soft pre-vote 的证据为对 $(ID,main-vote,r-1,abstain)$ 的双阈值门限签名。
3. 对消息 $(ID,pre-vote,r,b)$ 使用双阈值门限签名算法 $S$ 签名，得到自己的签名份额 $sign\ share$，广播$(ID,pre-vote,r,b,justification,sign\ share)$，这里与$r=1$ 时一致。

所谓 hard 和 soft 其实是区分当前 pre-vote 是对上一轮投票的继承，还是来自“听天由命”的一个抛币值。如果是 hard 的，就要证明确实收到了来自 $r-1$ 轮的一个非弃权 main-vote，那么只需要将该 main-vote 的证据继承下来即可；如果是 soft 的，就要证明收到的 $r-1$ 轮的 main-vote 全是弃权的。

以上就是对 ABBA 协议流程的完整介绍，核心思想就是一种投票选举制度，而上一步的投票结果决定了下一步的投票，并通过门限签名等密码学技术作为“投票凭证”，使得敌手不能随意投票以破坏共识过程。可能有的同学会问，按照它这个算法来，一定是对的吗？安全性有保障吗？下面我们对此进行分析。

分析

前面我们说过，共识问题一般具有 agreement、validity、termination 这几个属性，解决该问题的协议应能使其得到满足。ABBA 协议的分析便是从这个角度切入，但不同的是 ABBA 协议工作在密码学环境（cryptographic setting）中：敌手具有多项式时间计算能力、信道不安全。所以对常规属性定义做了变形，具体如下：

• validity：如果所有诚实节点对某一事件的初始值相同，那么最终能对该值达成共识。
• agreement：如果任一诚实节点对某一事件的取值作出断言（make decision），那么所有诚实节点将作出同样取值的断言并达成共识。
• liveness：所有消息送达后，所有诚实节点都能作出断言（make decision）。
• efficiency：诚实节点产生的消息数量是有限的。

可以看到，livess 和 efficiency 两个属性即构成了 termination。对上述四个属性的证明比较繁琐，篇幅有限就不展开了，其中比较有意思的是对 efficiency 的证明，规约到了证明能否对 common coin 协议的硬币值进行预测，这里直接给出结论： 诚实节点执行协议超过 $2r+1$ 轮的概率不超过 $2^{-r}+\epsilon$ ，而每轮的消息数量显然是有限的，故总的消息数量是有限的。

有兴趣的同学可以看原论文，如果有问题欢迎讨论。

总结

ABBA 协议关于已知下界在理论上和实际上都是最优的：

• 最大腐化节点个数 $t<n/3$；
• 运行期望时间是常数的（constant expected time）;
• 期望消息数量是 $O(n^2)$；
• 每条消息长度大约是一个RSA签名一倍或两倍；
• 仅在启动阶段使用一个 trusted dealer，之后可以处理几乎无限的交易。