【异步共识（3）】-“HB-BFT”ABA改进“小飞象Dumbo”原理讲解

帆说区块链

发布于 2022-04-27 09:32:58

1.7K0

发布于 2022-04-27 09:32:58

文章被收录于专栏：帆说区块链帆说区块链

影响 HB-BFT 性能的一个瓶颈是 ABA。

由于著名的FLP不可能的，ABA必须是一个随机的方案。这带来了以下缺点：尽管每个ABA协议的预期“轮”是恒定的，运行𝑛并发ABA会话的预期轮数可能很重要，即至少O(log𝑛)更严重，这些ABA实例不真正执行完全并发的方式：

（1）不是所有实例同时开始，一些实例可能开始后输入(之前的RBC)没有交付；（2）正常节点也有一个效率下降面临大规模的并发执行(没有足够的CPU内核等)。

当𝑛变大，网络不稳定时，可能会有一些ABA实例终止得非常缓慢。最慢的ABA实例决定了HoneyBadgerBFT的ACS的运行时间。

为了了解ABA协议对性能的实际影响，我们进行了HB-BFT实验，并对RBC和ABA之间的平均运行时间进行了统计。如图2所示，很明显，对于HB-BFT，ABA的成本占主导地位。当系统的规模不断增长时，这种模式就会变得更加重要。这个简单的观察结果激励我们减少ACS协议中所需的ABA实例的数量。

于是如何减少每轮共识中需要运行的 ABA 实例个数就是提高异步共识效率的关键。沿着这个思路，Dumbo 给出了两种解决方案，分别是 Dumbo1 和 Dumbo2。下面简单谈一下 Dumbo1 和 Dumbo2 的思路，具体细节和证明请看论文原文。Dumbo1 的思路非常简单（如下图所示）：既然我们的目标是选取一个共同子集，那么为什么不选取一个由 k（k<N）个成员组成的委员会，每个成员提议一个子集，这样我们只需要对每个提议进行一次二元共识不就可以了？这样就可以把运行 ABA 的实例个数从 N 减少到 k。于是 Dumbo1 的关键问题就转化成了如何随机选举一个 k 个成员组成的委员会，并且大概率能保证 k 个成员中至少有一个是诚实的。

通过对MVBA的创新使用，提出了一种甚至更快的异步BFT协议，称之为Dumbo2。它实现了渐近最优（恒定的）的运行时间，即Dumbo2只需要运行（预期的）三个连续的ABA实例，而其他复杂性保持不变5。

制定ACS的细节需要进一步的想法。由于ACS输出输入的一个子集，所以我们将首先通过RBC类型的协议，用一个输入向量来准备每个对等节点。更重要的是，我们没有将这些消息向量输入到MVBA协议，而是进一步准备了一个非常短的“指示器”（图4中的𝑊𝑖），并将其作为输入来加入MVBA协议。MVBA协议将输出一个这样的“指示器”，用于告知每个诚实的对等方选择相应的RBC实例。棘手的部分是，在MVBA协议中，诚实的对等点可能会从恶意的对等点输出输入（这里是简短的“指示器”）。

我们通过设计“指标”来解决这个问题，其中任何一个都可以作为保证，所有诚实的同行都会收到相应的信息。我们制定了一个新的原语称为可证明可靠广播(PRBC)，它增强了RBC，并进一步输出一个简洁的证明（即使是恶意节点），至少有一个诚实的对等体已经接收了输入。这可以通过对RBC索引的阈值签名来实现。MVBA内的ABA只需要重复（预期）3次。如图4所示，其中𝜋是一个随机排列。

看看它为什么能工作：实际的输入𝑊𝑖到MVBA包括一个索引集和相应的证明。当一个诚实的节点输出𝑊𝑖时，𝑊𝑖中的证明是有效的。这意味着与𝑊𝑖中的索引对应的消息都被足够多的对等点接收，其中至少包括一个诚实的对等点。然后，所有其他诚实的节点最终也会收到这些信息。我们指出，尽管小飞象2超过小飞象1在大多数情况下，我们选择保持小飞象1清晰的表示：使用每个ABA投票的想法是否输出向量的每个“委员会”成员在小飞象1，而不是每个输入HB-BFT是简单和直观的。这种更有效投票的可能性可以被视为激励投票只输出一个人的向量的想法的垫脚石，这最终导致了小飞象2使用MVBA的想法。此外，由于MVBA仍然相当复杂，在一些良性病例中，当𝑓非常小时，小飞象2可能并不比小飞象1好。