分布式密钥-小飞象共识算法

实用异步分布式密钥生成

​ ADKG协议有四个阶段:

1. 共享（节点启动一个ACSS方案，$$O(κn^2)$$通信复杂度）

2. 密钥集提议（节点启动一个RBC将T_i广播到所有其他节点，RBC通信复杂度$$O(n|M|+kn^2) $$，|M|为消息M的大小，κ为抗碰撞哈希函数的输出大小。）

3. 共识（节点启动n个ABA方案，ABA方案计算成本复杂度为$$O(n^2)$$，故每个节点的计算成本为$$O(n^3)$$，所有节点总的计算成本为$$O(n^4)$$）

4. 密钥派生。

​ 前三个阶段具有类似的结构，我们分别运行n个并发的ACSS、RBC和ABA实例，其中每个节点启动一个ACSS和RBC实例，每个ABA实例就相应的RBC是否终止达成一致。我们将节点i调用或关联的ACSS (RBC或ABA)称为i^th ACSS (RBC或ABA)。

A.共享阶段

​ 在共享阶段，每个节点i采样一个均匀随机的秘密s_i∈Z_q，并使用ACSS方案与所有其他节点秘密共享(算法1中的1-2行)。

​ 对于l=t+1，我们使用来自Das等人的ACSS方案，但将其Pedersen多项式承诺替换为Feldman多项式承诺，以实现同态部分承诺。这只需要使用零多项式作为Pedersens多项式承诺中的隐藏多项式。

​ 设p(·)为t次多项式，
$$
p_i(x)=s_i+a_{i,1}x+a_{i,2}x^2+…+a_{i,t}x^t
$$
​ 其中a_i,k←Z_q随机选取。由于ACSS的完备性，一旦第i个ACSS实例终止，所有诚实节点都会在p_i(·)上输出一个求值点。每个节点额外输出p_i(·)的费尔德曼承诺v_i，
$$
v_i=[g^{s_i},g^{a_{i,1}},g^{a_{i,2}},…,g^{a_{i,t}}]
$$

B.密钥集提案阶段

​ 在密钥集提案阶段，每个节点i维护已终止的ACSS实例的一组T’_i(代码第11-15行)。特别是，每当第j个ACSS在节点i处终止时，节点i将索引j添加到集合T’_i(第15行)，并将其共享s_j,i=p_j(i)(节点j选择的秘密)添加到集合S_i(第14行)。设T_i为终止于节点i的第一个t+1个ACSS实例。节点i启动RBC将T_i广播到所有其他节点(第16-18行)。直观地说，T_i是节点i对一组节点的建议，这组节点的秘密将被聚合为最终的密钥z。

​ 这里需要注意的一个关键点是，每个节点i仅在T_j⊆T’_i(第19行)之后才参与第j个RBC，此时T_j中指定的所有ACSS实例都在节点i处终止。因此，如果RBC(T_j)终止，则至少有t+1个诚实节点保证Tj中的每个ACSS实例都已终止。因此，由于ACSS的完备性，对于每一个k∈T_j，第k个ACSS实例最终会在所有诚实节点处终止，并且每个诚实节点最终都会收到一份有效的秘密s_k。

C.共识阶段

​ 在共识阶段，节点尝试将上一阶段的有效密钥集提案得到一致的子集。然后，我们使用这些密钥集提案中的元素的并集来派生最终的秘密密钥。如前所述，如果节点i中的每个ACSS实例都已终止，则节点i的密钥集提案T_i有效。为了在提案的子集上达成一致，节点启动n个并发ABA实例，其中第j个ABA实例试图确定第j个键集建议是否有效。如果第j个键集建议RBC在节点i成功终止，节点i将向第j个ABA实例输入1(第21-24行)。此外，如果第j个ABA实例需要任何共享随机性，则节点使用T_j来生成共享随机性。更具体地说，设u_j为以下值：
$$
u_j=\sum_{k\in{T_j}}S_k
$$
​ 然后，在第j个ABA实例期间，每当需要投一次硬币时，因为具有共享密钥u_j节点使用Diffie-Hellman门限投币协议(第25-26行)。节点i在u_j中的份额为
$$
u_{i,j}=\sum_{k\in{T_j}}S_k
$$
​ 我们可以使用ACSS的同态部分承诺属性允许每个节点本地计算g^u_j和g^u_i,j用于让所有i和j完成抛硬币设置。

​ 如II的challenge 2所述，如果第j个节点是恶意的，并且没有可靠地广播密钥集合，则节点将无法访问第j个ABA中的共享随机性。在这种情况下，所有诚实节点将向该ABA输入0，并且由于Good-Case-Coin-Free属性，该ABA将在不使用抛硬币的情况下终止。对于二值情况，诚实节点向ABA输入不同的值，至少有一个诚实节点向ABA输入1。这意味着至少有一个诚实节点收到了中间密钥集合。通过ACSS的完备性和RBC的完备性，所有诚实节点最终也会收到中间密钥集合。

​ 最后，为了确保不是所有的ABA都以0结束，我们将使用Ben-Or等人的精妙想法。简而言之，每个诚实节点向所有密钥集提议阶段成功结束的ABA输入1，避免向任何ABA输入0直到至少一个ABA以1结束(第29-31行)。一旦一个ABA以1结束，每个节点将向所有尚未输入任何内容的剩余ABA输入0。使用类似于Ben-Or等人的分析，我们在Lemma 1（第V节分析中的内容）中表明，至少有一个ABA将以1终止。

D. 密钥派生阶段

​ 如果第j个ABA以1结束，我们说第j个键集提议被接受。设T为至少包含在一个可接受的密钥集提议中的节点集(第29-30行)。注意|T|≥t +1。然后，我们使用T导出最终的ADKG KEY为：
$$
z=\sum_{j\in{T}}s_j
$$
​ 为了计算最终的ADKG公钥h^z，每个节点i在本地计算h^z_i，其中
$$
z_i=\sum_{j\in{T}}s_{j,i}
$$
​ z_i是的密钥z的一部分份额。每个节点i还计算一个NIZK证明(非交互零知识证明)π_i(第43行)，
$$
\log_{g}g^{z_i}=\log_{h}h^{z_i}
$$
​ 这里log_g和log_h分别表示以g和h为底的离散对数。为此，我们对这个提案使用ChaumPedersen协议的非交互式变体。注意，对于任何给定的i，由于ACSS的同态部分承诺，所有诚实节点都可以使用T中包含的ACSS实例的部分承诺来计算g^z_i。

​ 最后，每个节点i将<KEY,h^z_i,π_i>发送给所有其他节点。节点接收到有效的<KEY,h^z_i,π_i>消息后，利用拉格朗日插值法计算出每个j∈[n]的公钥h^z和门限公钥h^z_j(第49-51行)。

共识算法

​ HB-BFT（Honey Badger异步拜占庭协议）通过模块化的方式解决了拜占庭环境下的原子广播（Atomic Broadcast，ABC）问题，即如何保证在异步和拜占庭环境下，各个节点按相同顺序收到相同的消息。

​ HB-BFT 首先将 ABC 分解成一个核心模块，异步共同子集（Asynchronous Common Subset，ACS）。之后将 ACS 分解成了 RBC(Reliable Broadcast) + ABA(Asynchronous Binary Agreement)两个子模块，并且分别针对这两个子模块找到了两个比较优化的实现。

​ 每个节点首先将本地的 proposal 通过 RBC 发送到其它节点，之后每个节点针对每个 RBC 的实例成功与否（0 或 1）执行一次 ABA。也就是说，每个节点都要并行运行 N 个 ABA 的示例（每个节点的 proposal 一个），每个 ABA 的输出 0 或 1 表示是否所有正确节点都认为这个 proposal 最终应该成为区块的一部分。

RBC(Reliable Broadcast)

​ 可靠广播 RBC 可以确保源节点能够可靠地将消息发送到网络中的所有节点。

​ Cachin 等人在 2005 年提出了基于纠删码的 RBC 实现，将通信复杂度降低到了 $$O(N|v|+\lambda N2\log{N}) $$。HB-BFT 就是采用了这种优化的 RBC。当 |v| 远大于$$\lambda N\log{N}$$的时候，其通信复杂度可以近似表示为 $$O(N|v|)$$ 。由于$$|v|=|B|/N$$ ，则 HB-BFT 整体的通信复杂度可以表示为 $$O(|B|)$$ （|B|为整个区块的大小），也就是渐进于理论最优。

ABA(Asynchronous Binary Agreement)

​ 异步二元共识就是要在异步环境下让所有节点对于 0 或 1 达成共识。在 HB-BFT 中，每个节点都会针对其他所有节点的 RBC 是否成功进行一次二元共识，也就是说，每轮共识都要并行地执行 N 个 ABA 的实例。

​ ABA 的实现原理就是当节点无法达成一致的时候借助一个外部的随机源做决定。这个随机源就是 ABA 的核心组件（Common Coin，CC），我们也可以将 CC 理解成上帝掷骰子，只不过这个骰子只有 0 和 1 两个值。虽然只掷一次骰子可能还是无法达成共识，那么就不停掷，最终会出现所有人都达成一致的结果。Common Coin 有很多实现方案，HB-BFT 针对其模块化的设计，采用了基于阈值签名的 CC 方案。每个节点对一个共同的字符串进行签名并广播给其它节点，当节点收到来自其它 f+1 个节点的签名时，就可以将这些签名聚合成一个签名，并将这个签名作为随机源。

​ Dumbo 的作者们发现影响 HB-BFT 性能的一个瓶颈是ABA。由于在每轮共识中每个节点都要运行 N 个 ABA 的实例，每个实例都要验证$$O|N^2|$$个阈值签名，这对 CPU 的消耗很大。如下图所示，RBC 的运行时间相比 ABA 几乎可以忽略不计，而且随着 N 增大，运行ABA 所需要的时间越来越长。

​ 于是如何减少每轮共识中需要运行的ABA 实例个数就是提高异步共识效率的关键。沿着这个思路，Dumbo 给出了两种解决方案，分别是 Dumbo1 和 Dumbo2。下面简单谈一下 Dumbo1 和 Dumbo2 的思路，具体细节和证明请看论文原文。

​ Dumbo1 的思路非常简单：既然我们的目标是选取一个共同子集，那么为什么不选取一个由 k（k<N）个成员组成的委员会，每个成员提议一个子集，这样我们只需要对每个提议进行一次二元共识不就可以了？这样就可以把运行 ABA 的实例个数从 N 减少到 k。于是 Dumbo1 的关键问题就转化成了如何随机选举一个k个成员组成的委员会，并且大概率能保证 k 个成员中至少有一个是诚实的。

​ Dumbo2 的目标更为激进，能否将 ABA 的个数直接降到常数级别呢？有一个方法，就是使用多值拜占庭共识（Multi-value Validated Byzantine Agreement，MVBA），也就是说，我们能否让每个节点都提议一个子集（前提是这些提议要满足某个前提条件），然后从 N 个子集中选取 1 个作为共识结果（如下图所示）。问题在于，已有的 MVBA 的方案的通信复杂度较高，达到$$O(N^2|m|+\lambda N^2+N^3)$$ ，其中 |m| 为 MVBA 的输入的大小。由此可见影响 MVBA 通信复杂度的关键在于 |m| 的大小。如果 |m| 的值足够小，那么使用 MVBA（只包含常数级的 ABA 运行个数）实现 ACS 的效果就要远好于 HB-BFT 使用的 RBC 跟 ABA 的组合。Dumbo2 的解决办法就是尽可能缩小 |m| 的大小。

​ 可以看到实用异步分布式密钥使用了

• ACSS（节点启动一个ACSS方案，$$O(κn^2)$$通信复杂度$$O(κn^2)$$通信复杂度）+
• RBC（节点启动一个RBC将T_i广播到所有其他节点，RBC通信复杂度$$O(n|M|+kn^2) $$，|M|为消息M的大小，κ为抗碰撞哈希函数的输出大小。）+
• ABA（节点启动n个ABA方案，ABA方案计算成本复杂度为$$O(n^2)$$，故每个节点的计算成本为$$O(n^3)$$，所有节点总的计算成本为$$O(n^4)$$）

而异步拜占庭共识协议HB-BFT则是

• RBC（HB-BFT 就是采用了Cachin 等人在 2005 年提出了基于纠删码的 RBC 实现，将通信复杂度降低到了 $$O(N|v|+\lambda N2\log{N}) $$）+
• ABA（每个节点都要运行N个ABA的实例，每个实例都要验证$$O|N^2|$$个阈值签名），

而小飞象关于ABA部分进行提升

​ Dumbo1 ：选取一个由 k（k<N）个成员组成的委员会，每个成员提议一个子集，只需要对每个提议进行一次二元共识，这样就可以把运行 ABA 的实例个数从N减少到k。于是 Dumbo1 的关键问题就转化成了如何随机选举一个k个成员组成的委员会，并且大概率能保证 k 个成员中至少有一个是诚实的。

​ Dumbo2 ：将 ABA 的个数直接降到常数级别。有一个方法，就是使用多值拜占庭共识（Multi-value Validated Byzantine Agreement，MVBA），也就是说，我们能否让每个节点都提议一个子集（前提是这些提议要满足某个前提条件），然后从 N 个子集中选取 1 个作为共识结果（如下图所示）。问题在于，已有的 MVBA 的方案的通信复杂度较高，达到$$O(N^2|m|+\lambda N^2+N^3)$$ ，其中 |m| 为 MVBA 的输入的大小。由此可见影响 MVBA 通信复杂度的关键在于 |m| 的大小。如果 |m| 的值足够小，那么使用 MVBA（只包含常数级的 ABA 运行个数）实现 ACS 的效果就要远好于 HB-BFT 使用的 RBC 跟 ABA 的组合。Dumbo2 的解决办法就是尽可能缩小|m|的大小。