异步共识协议中的不可能三角问题

这篇文章描述在异步共识协议研究中的一个具体问题。在作为研究对象的异步网络中，网络带宽是主要的稀缺资源之一。节点在网络中选择性广播可以节省网络带宽，在这种情况下，出现了交易打包率，交易丢失率，和交易重复率的不可能三角。

感谢 Eric Zhang 和 Songjian Cai 在相关研究问题中的讨论。

在现有的异步共识中，共识算法在设计之初通常假设交易发送者发送到异步网络的交易会广播给所有的节点（gossip 协议或其他广播协议）。基于此，交易发送者发送到异步共识网络中的每笔合法交易都会被诚实节点收到，这可以有效避免拜占庭节点审查合法交易——让合法交易迟迟无法上链（本文将其描述为交易丢失）。假设当前异步共识网络生成区块的时间间隔为，每一个共识节点将上一个收到的交易放入他们本地维护的交易池中。设此时的区块编号为，时间戳为。在～之间，异步共识网络不仅仅在生成第个区块，同时每个共识节点还在接收交易发送者们发送到异步共识网络中的新的合法交易。在时刻，第个区块被生成，且每个共识节点在他们自己本地维护的交易池中积累了笔交易，其中 $，$ 为节点的序列号，为异步共识网络的共识节点总数。共识节点从交池中的笔交易中随机选择笔交易打包到他们的子块，其中为节点的交易池中交易的总数。然而，基于该假设，现有的共识协议存在两个问题——

问题 1：所有异步共识节点的交易池就会具有一定的相似性。

现在，我们来定量的讨论各个节点交易池在时刻的相似度。首先，我们定义交易池相似度：

定义 1：交易池相似度

每两个共识节点的交易池相似度为，其中为两个节点的交易池中相同的交易数量，为每个节点的交易池中总的交易数量。

我们先不考虑各个节点在时刻之前收到的交易，只考虑在～之间收到的交易；同时，我们假设每个共识节点的带宽能力是相同的，因此每个节点在该时间段内都可以接收笔交易，以及每个节点的交易池中的交易数是相同的。基于此，我们假设在～时间段内，交易发送者们总共发送了笔交易到异步共识网络，其中。当时，在使用 gossip 协议或其他类似的广播协议的背景下，每个节点的交易池在时刻的相似度为。这是因为在每个节点的交易池在该时间段内能够接收最多笔交易的情况下，发送到异步网络中的笔交易都会被所有节点接收。这导致所有节点的交易池完全相同，比如当时，所有节点的交易池都为。当时，由于每个节点的交易池数量最大只能为，随着的增大，各个节点的交易池中的相似度会降低（比如，当时，节点 1 的交易池为，节点 2 的交易池为），如下图所示：

问题 2：gossip 协议或其他类似的广播协议会消耗异步共识网络的共识节点的大量带宽。

因为每笔交易都会发送给所有的共识节点，当时，每个共识节点在～时间段内都会消耗的带宽，其中为每笔交易的平均字节数。进一步，随着交易需求的不断增大，也就是的不断增大，虽然交易池相似度会降低，交易被打包到区块的平均延时也会随着的增大而增大。具体来说，我们用交易打包率来定义交易延时。

定义 2：交易打包率

现在，我们设每个节点的交易池中的交易总数为，其中当时，，当时，。假设每个节点会从他们的交易池中随机选择笔交易，并将选择的交易放入进他们的子块中，因此，个节点的个子块合并成一个区块后，总交易数为，有效交易总数为（有效交易总数代表在笔交易中去除掉重复的交易，比如在这笔交易中，交易出现了两次，那么最终的有效交易中只包含了一笔）。交易打包率可以用公式表示，其中为交易打包率。下图展示了与交易打包率之间的关系：

从该图可以看出，交易打包率在时约为左右，这是因为当时，由于所有节点的带宽能力运行他们的交易池收到最多笔交易，所有共识节点都会收到笔交易。因此，所有节点的交易池样本空间在时相同，这导致了当时，交易打包率维持在一个恒定值附近（即）。当时，所有节点的交易池的交易数为，但有笔交易发送到了全网，随着的不断增大，的分母不断增大，而的最大值是有上限的（上限为），这导致了交易打包率随着的不断增大而减小，每个节点这意味着一笔交易上链的平均延时随着的不断增大而增大。

与此同时，我们进一步计算交易重复率。

定义 3：交易重复率

交易重复率可以定义为一个区块的总交易数减去一个区块的有效交易数比上一个区块的总交易数。用公式可以表示为，其中为交易重复率。

由上图可知，当时，发送到异步网络中的笔交易都会被所有节点收到，因此所有节点的交易池中的交易是完全相同的。在此基础上，每个节点随机从他们的交易池中选择笔交易时，由于每个节点的样本空间完全相同，交易重复率的平均值会维持在左右。当时，根据之前的分析，交易池相似度会下降。当交易池相似度下降时，如节点 1 从交易池中随机选择两笔交易，节点 2 从交易池中随机选择 2 笔交易，相比于相同的交易池中随机选择（比如所有的节点的交易池都为），交易重复率自然会下降。我们还发现，随着的不断增大，交易重复率下降的同时，交易打包率也在降低。换句话说，交易重复率和交易平均延时呈现负相关。

方法

有一个方法可以用来解决上面提到的两个问题，即不要让交易发送者发送的每笔交易都传递给异步共识网络中的每个节点。相反，一笔交易只需要发送给个异步共识节点中的个共识节点，其中。这样做会带来以下好处：

节省全网的带宽：相比于传统的 gossip 协议，假设全网在一个时间段内收到了笔不同的交易，那么，每个节点终将通过 gossip 协议收到这笔交易。这样一来，全网消耗的带宽为。相对来说，如果只将一笔交易发送给个节点，全网只会消耗的带宽。如果可以让远小于，则全网的带宽可以节省一个量级及以上。
降低节点的交易池相似度：我们还是假设在～时间段内，全网收到了笔合法交易。我们做了以下对比：第一种情况，这笔合法交易中的每笔交易都会发送给全网所有个共识节点；第二种情况，这笔合法交易中的每笔交易都会随机选择全网个共识节点中的个节点，每笔交易会发送给被其自己选择出的个节点，比如，交易 1 随机选择了节点 4 和节点 6，交易 2 随机选择了节点 1 和节点 3。在这两种情况下，通过调整值和值，我们得出了下图：

当且时，每个节点的交易池中并没有达到笔交易，每个节点的交易池中平均只有笔交易。同时，由于一笔交易只发送给了个节点，这使得一个节点的交易池中的某些交易一定不存在于另一个节点。因此，即使在时，任意两个节点的交易池相似度也不会达到。

安全性

我们将上述方法暂且称为 m out_of n 方法。然而，上述方法和传统方法相比，引入了一个新的问题：如果，则一笔交易选择的个节点全都是拜占庭节点。这样一来，拜占庭节点可以审查这笔交易，从而使得该笔交易永远都不会被打包到区块中。

定义 4：单笔交易丢失率

我们定义单笔交易的交易丢失率为，其中　。

对做一些必要的解释: 首先，由于我们假设异步网络有个节点，其中有个拜占庭节点，那么，根据上面的分析，如果，选择的个节点可能都是拜占庭节点。基于此，我们可以计算选择的个节点都是拜占庭节点的概率：第一个选择的节点是拜占庭节点的概率为，第一个和第二个选择的节点是拜占庭节点的概率为，以此类推，得到了这个公式。显然，单笔交易的交易丢失率为选择的个节点全是拜占庭节点的概率。另外，当时，交易丢失率为，这是因为至少会有一个诚实节点会收到该笔交易，从而收到该笔交易的诚实节点一定会在未来的某一时刻打包该笔交易。

基于此，如果足够大，足够小，则单笔交易的交易丢失率可以表示为。同时，我们发现，当比大十倍以上时，的变化对交易丢失率不会有太大影响。

因此，我们使用来近似计算交易丢失率:

定义 5：交易丢失率

假设异步网络中收到了笔交易，每笔交易都随机选择了个节点。其中有笔交易选择的个节点全部都是拜占庭节点。此时，交易丢失率定义为。

当笔交易发送到异步共识网络时，总共会丢失的交易笔数服从二项分布。而交易丢失率可以通过计算二项分布的累积得到。因此，我们可以计算二项分布的累积公式来近似代替交易丢失率。

当为不同值时，在一个时间段内发送到笔合法交易的交易丢失率可以通过下图来表示：

我们以的概率范畴为统计区间来得到丢失交易数不大于的值（即丢失笔交易的总概率之和为）。换句话说，丢失交易数大于的概率不到，小概率事件几乎可以忽略不计。我们可以发现，当时，交易丢失率降到了 1% 以内，也就是说，一千笔交易的丢失数量最多大约为九笔（换句话说，一千笔交易中丢失交易数小于等于九笔的概率为）。当时，交易丢失率约为，也就是说一千笔交易的丢失数量最多大约为三笔。

与 gossip 协议的性能对比

m out_of n 方法与传统的 gossip 协议相比，在性能上也有所提升。在带宽上的提升是显而易见的，我们不对此进行过多分析。在这里，我们主要分析另外两个性能指标，及交易重复率和交易打包率。重申一下，交易重复率是指，当一个新的区块生成后，区块中的总交易数减去有效交易数除以区块中的总交易数，即。交易打包率（我们依旧假设全网在～时间段内会收到笔不同的交易，其中为每个节点在该时间段内可以接收交易的上限数量）。

我们首先来分析在 m out_of n 方法与传统的 gossip 协议方法这两种方法的情况下，共识节点的交易池的交易数情况。在 m out_of n 方法中，由于在～时间段内，有笔不同的交易会发送到异步共识网络，因此，全网总共收到了笔交易。这样一来，每个共识节点平均就收到了笔交易。在传统的 gossip 协议中，全网总共收到了笔交易。这样一来，每个共识节点平均就收到了笔交易。当时，m out_of n 方法中的节点交易池并没有达到饱和，每个节点的交易池中只有笔交易。对于传统的 gossip 协议，每个节点的交易池中的交易数为。在 m out_of n 方法中，当时，共识节点的交易池的交易数才达到饱和。而在传统的 gossip 协议中，共识节点的交易池早在时已经达到饱和。这意味着，当时，在 m out_of n 方法中，所有发送到异步共识网络中的交易可以全部被共识节点接收；相反，在传统的 gossip 协议中，有不多于笔交易是无法被共识节点接收并放入交易池的。因此，在逻辑上就可以推导出 m out_of n 方法相比于传统的 gossip 协议可以有效提升交易打包率，从而降低交易延时。实验分析如下图所示：

由上面的图可以发现，虽然使用 m out_of n 方法后的交易打包率相比使用 gossip 协议后的交易打包率有所提升，随着的增大，两种方法所呈现的效果变得接近，且呈现的规律相同。

另外，在 m out_of n 方法中，由于一笔交易不需要发送给所有节点，而是发送给个节点，这使得任意两个节点的交易池相似度会低于在传统的 gossip 协议模式下的任意两个节点的交易池相似度（之前的图已经证实这一点）。这使得在 m out_of n 方法下的交易重复率也比传统的 gossip 协议方法下的交易重复率更低，正如我们的实验分析结果所示：

我们可以看到，使用 m out_of n 方法时的交易重复率比使用 gossip 方法的交易重复率要低；同时，使用 m out_of n 方法时的交易打包率比使用 gossip 方法的交易打包率要高。然而，当使用 m out_of n 方法时，这两个性能指标的提升并不显著。对于交易重复率，提升不显著的原因是：

当增大时（），即使使用 gossip 协议，每个共识节点的交易池的相似度也不会达到 %，这是因为全网总共有笔交易，每个节点只会从笔交易交易中随机收到最多笔交易。
当时，m out_of n 方法中的共识节点的交易池中的交易数并没有达到饱和值，而是。相反，当时，使用 gossip 协议下的节点的交易池的交易数已经达到了饱和值。因此，由于传统 gossip 协议的共识节点的交易池的样本空间更大，如果在使用两种方法时，都只是从交易池中挑选出相同的交易数，从更大的样本空间中进行挑选会比从较小的样本空间中挑选在交易重复率上会更有优势。因此，在这一点上，基于 gossip 协议的方法在一定程度上缓解了其模式下交易池相似度过高的弊端。

不可能三角

基于上面的推理，我们可以进一步发现，在使用 m out_of n 方法后，异步共识算法出现了一个新的不可能三角问题。“三角”分别为交易重复率，交易丢失率，交易打包率。在使用传统的 gossip 协议或者其他类似广播协议时，并不存在这个不可能三角问题，这是因为传统的广播协议不会存在交易丢失率这个性能指标，也就是一旦交易被发送到异步共识网络，交易一定会被打包并上链，不存在不会被上链的情况。这是牺牲了网络带宽总消耗的结果（一笔交易会发送给所有节点，因此一定会发送给诚实节点）——极致的冗余带来了 % 的安全。然而，在现实中，我们并不需要将交易丢失率降低到。相反，如果我们能够让交易丢失率维持在一个很低的概率，同时极大的降低网络带宽的消耗，也是一个不错的权衡。然而，虽然 m out_of n 方法实现了交易丢失率和网络带宽消耗之间的权衡，我们仍发现，现有的方案中，存在上述所说的不可能三角。也就是说，上面三个性能指标，想提升其中的两个指标，必须建立在牺牲另外一个指标的基础之上。

具体来说，对于这三个性能指标，我们希望在相同条件下，交易重复率越低越好，交易打包率越高越好，而交易丢失率越低越好。

对于交易重复率和交易打包率，根据上面的分析，我们发现这两个指标都与值呈负相关（这两个指标的数值随着的增大而减小）。这个现象不仅仅出现在 m out_of n 方法中，使用 gossip 协议等方法也会存在这个问题。同时，值的大小直接反映了网络中交易的活跃度。当异步共识网络的交易量激增时，值就会显著变大。这会使交易重复率这个性能指标变得更加优秀，但交易打包率（交易延时）这个指标则会显著变差。值的大小并不会影响交易丢失率这个性能指标。

根据之前的分析，我们已经得到交易丢失率的值和的大小呈现负相关。当时，交易丢失率就会为。然而，为了尽可能的降低异步共识网络中的节点的带宽需求，我们通过调节的值来达到一个最优的权衡，正如之前所说，当异步网络节点数较大的情况下，如果想让交易丢失率低于，我们需要让值不小于。我们同时也发现，的值同样会影响交易重复率和交易打包率这两个指标。当增大时，由于一笔交易需要发送给更多的节点，导致了任意两个节点的交易池相似度的增加，从而导致了交易重复率的增加。同时，虽然值的增大对交易打包率的影响较弱，值与交易打包率仍然呈现出负相关，如下图所示（）。

从该图我们可以发现，当大于时，交易重复率和交易打包率这两个性能指标并不理想。

因此，我们可以总结出，参数和是影响这三个性能指标的关键。接下来，我们进一步分析，和是如何影响交易重复率，交易打包率和交易丢失率这三个性能指标的。

如果我们想让交易重复率和交易打包率变得优秀，我们需要选择一个合理的值的同时，尽可能的让越小越好。比如，我们将的值设为时，交易重复率可以有效降低。为了进一步提升交易打包率，我们需要减小值。比如，另时，交易重复率降低到了，而交易打包率也可以达到，如下图所示。然而，在的情况下，交易丢失率却达到了约。

如果我们提高的大小，比如令，交易丢失率就降低到了，然而，交易重复率却有所提升，同时交易打包率有所下降，如下图所示。

如果我们想让交易重复率和交易丢失率变得优秀，首先我们需要让值越大越好（保证交易丢失率尽可能小）。当的值增大时，为了进一步降低交易重复率，我们需要进一步增大值。增大值的后果就是牺牲交易打包率。比如，我们让，此时交易丢失率仅为。为了进一步降低交易重复率，我们需要让值增大。当值不断增大时，虽然交易重复率降低到了以下，交易打包率也降低到了以下，如下图所示：

如果我们想让交易打包率和交易丢失率变得优秀，首先我们同样需要让值越大越好（增大保证交易丢失率变小）。当的值增大时，为了进一步降低交易打包率，我们需要进一步减小值。减小值的后果就是牺牲交易重复率，如上图所示，当时，交易打包率达到了，然而交易重复率却也高达。

综上，我们提出了 m out_of n 方法，该方法可以极大地降低异步网络中的节点在接收交易时的带宽损耗；同时，在相同参数（等参数）环境下，相比于 gossip 协议等方法，m out_of n 方法不仅降低了交易重复率，同时还提升了交易打包率。然而，m out_of n 引入了新的性能参数——交易丢失率，以及上面论述的不可能三角问题。显然，m out_of n 方法带来了诸多好处，即使引入了交易丢失率这一性能指标，在良好的变量控制下（让交易丢失率足够小的同时，去降低交易重复率和交易打包率，同时减小对带宽的消耗）因此，在基于 m out_of n 方法上，如何在维持较低的交易丢失率的情况下，进一步去减小交易重复率和增大交易打包率，是未来的重点研究方向。