以太坊2.0的洗牌算法

作者：Ben Edgington

简介

如果你想学跳曳步舞，那就错了。但相信我，ETH2的洗牌同样令人兴奋。

洗牌列表是以太坊2.0中的一个基本操作。它主要用于每12秒时隙选择验证器组成委员会，并在每个时隙选择信标链块的提议者。

混合和洗涤似乎很简单。虽然它有一些陷阱需要注意，但它们在计算机科学中是很容易理解的。金本位可能是费希尔·叶芝洗牌。那我们为什么不在ETH2中使用它呢？我将在文章的最后详细解释它，但是简单地说，轻量级客户端。

我们使用的洗牌算法是swap还是not，而不是Fisher-Yates。这种选择是基于论文最初用来构建加密方案的。我最近在ETH2客户机teku中重写了我们的实现，所以我想趁热把它写出来。

交换或不洗牌算法

一轮手术

混洗以轮次进行。每轮的过程是一样的，因此我在下面只会演示一轮的过程，它比看上去简单多了。

1选择一个轴点并找到第一个镜像索引

首先，我们选一个轴心索引p，这是基于轮次和其他一些种子数据，通过伪随机选出的。这个轴心选出后就在该轮次里固定了。

基于这个轴心点，我们在P和0之间的中间点选择一个镜像索引M1，即M1=P/2。（为了说明，我们将忽略麻烦的一个错误舍入问题）

轴点和第一个镜像索引

2从第一个镜像索引到轴心点，是否更换

对于镜像索引m1和轴心索引p之间的每个索引，我们随机决定是否对这些元素进行替换。

例如，对于索引I1，如果我们选择不替换它，我们将继续选择下一个索引。

如果我们决定替换，我们将把I1上的list元素替换为I1’上的list元素，也就是说，它在镜像索引上的映像。也就是说，I1被I1’=M1-（I1-M1）代替，使得I1和I1’到M1之间的距离相等。

我们对M1和P之间的每个指数做相同的交换或不交换决定。

从第一个镜像索引交换还是不交换决定

3计算第二个镜像索引

在做完从m1到p的所有索引决定后，我们现在找到第二个以m2为中点的镜像索引，即到p和列表末端的距离相等的点。也就是m2=m1+n/2。

第二镜像索引

4从轴心点到第二镜像，是否更换

最后，我们重复swap-or-not的过程，考虑所有点到轴心p替换的决定，即p到第二个镜像m2的决定。如果我们选择不替换，就继续下一个。如果我们选择替换，那么我们在镜像索引m2上把j1上的元素与它在j1’上的镜像进行替换。

是否交换从数据透视到第二个镜像索引的决策

把它放在一起

本轮结束时，我们考虑了M1和M2之间的所有指数，也就是所有指数的一半，每一个指数在另一半都有一个具体的指数，不管是否被替代。因此，所有的指标都经过了一次是否换代的考虑。

下一轮通过增加（或减少）轮数打开，这样我们就有了一个新的轴索引，然后开始循环上述过程。

在同一轮中从一面镜子移到另一面镜子的过程

有什么有趣的

别出心裁的地方

当在决定要不要替换的时候，这个算法会巧妙地选择候选索引或其镜像中的更高者。意思是当在轴心之下时，被选择的是i_1而不是i_1’；当在轴心之上时，被选择的时i_k’而不是i_k。这意味着，我们可以灵活遍历列表中的索引：我们可以将0到m1和p到m2分为两个独立的循环，或将两者合在同一个从m1到m2的循环，如我在上文所描绘（和
实现）的。这两种做法的结果是一样的：无论我考虑的是i_1还是镜像i_1’都没有关系；替换与否得出的是相同的结果。

圆形

在ETH2，上述的过程会进行90次。
原始论文里提到要经历6lgN个轮次才能“开始在选择性密码攻击 (CCA) 上出现较好的安全性界限”，其中N是列表的长度。在Vitalik的
注释规范里，他说“密码学专家建议我们4log2N个轮次就能提供足够的安全性了”在ETH2里验证者数量的绝对最大值，也就是我们需要混洗的列表最大次数，大概是222 (420万)。Vitalik给出的预估值是88轮，在论文里的预估值是92轮 (假设lg是自然对数)。因此，我们现在处于一个大致正确的范围，特别是我们最后非常可能没有这么多活跃验证者。

根据列表的长度调整轮数可能会产生有趣的结果，但我们不会，这可能是一个不必要的优化。

有趣的是，当最小权威审核信标链的规范时，他们最初发现在选择块支持者的洗牌过程中存在偏差（见问题f）。但结果，他们错误地使用了只有10发子弹的混洗配置。当他们增加混合配置到90轮（我们在主网络上使用的轮），偏差消失。

（伪）随机

混洗算法要求我们在每一轮里随机选一个轴心点，且在每轮里随机选择是否对每个元素进行替换。

在ETH2中，我们确保从种子值生成随机性，以便相同的种子总是产生相同的洗牌结果。

轴索引由种子的8字节Sha2哈希与round相串联生成，

pivot索引由8个字节的种子值Sha2散列生成，该散列与该轮相连，因此它通常在每一轮中发生变化。

用于确定是否替换元素的决定性数字是从以下元素中提取的：seed的sha256散列、round和列表中元素的索引。

效率

这个混洗算法比Fisher-Yates算法要慢得多。如果Fisher-Yates算法需要N次混洗的话，我们的算法平均需要90N/4次。我们还要考虑伪随机性的产生，这是算法中成本最高的部分。Fisher-Yates需要接近Nlog2N数位的随机性，而我们需要90(log2N+N/2)数位，根据我们在ETH2里需要的N值范围，超出的数位是相当多的 (当N为一百万时，ETH2大约需要N的两倍)。

为什么要交换呢？

如果效率不高，为什么选择这种实现方式？

单一元素混合洗涤

这个算法的闪光点在于，如果我们只关注少数几个索引，我们不需要对整个列表的混洗进行计算。事实上，我们可以将这个算法用于单个索引，来找出哪个索引将会被替换。

因此，如果我们想知道索引217的元素在哪里被洗牌，我们可以只对该索引运行算法，而不必对整个列表进行洗牌。另外，相反地，如果我们想知道哪些元素被洗牌到索引217，我们可以反向运行算法来找到元素217。

简而言之，我们可以计算出元素I在哪里混合，元素I的来源在哪里（通过反向操作）。计算时间不取决于列表的长度。Fisher-Yates-shuffling没有这个特性，您不能对单个索引进行洗牌。他们经常需要反复地洗牌整个列表。

ETH2规范中写的是如何应用该算法来洗牌单个索引。事实上，一次洗牌整个名单只是它的一个优化！如果需要，我们可以依次洗牌列表中的一个元素：（反转）运行shuffle以找出哪个元素结束于索引0，然后再次运行shuffle以找出哪个元素最终位于索引1，依此类推。我们不这样做的原因是，我们决定是否交换需要一次生成一个256位的散列，这样丢弃255位是非常浪费的。如果我们使用1位哈希或预测，洗牌一个列表元素的效率几乎和洗牌整个列表一样有效。

做一个真正的“轻”客户

这个特性之所以有意义，原因全在于轻客户端。轻客户端相当于是ETH2信标链和分片链的观测者，他们不储存整个状态，但希望可以安全地访问链上的数据。要对他们的数据正确性进行验证，即没有发生欺诈，其中的必要一步就是对证明数据的委员会进行计算。也就是要用到混洗算法，且我们并不希望轻客户端必须存储或是混洗整个验证者列表。通过swap-or-not混洗，他们可以只对他们需要的一小部分委员会成员进行计算，这样将在整体上大幅提高效率。

历史

如果你像我一样喜欢GitHub的考古特性，你可以在
这里查看最初为ETH2寻求混洗算法的讨论，
这里公布了最后的胜出者。

如果您想从另一个角度来看待swap或not shuffle算法，可以看看protolambda发布的更直观的解释。

最后的

这张照片是在2019年，当我听Justin Drake在ETHcc上谈论交换或不洗牌时，我在teku客户端（当时也叫Artemis）中实现了第一个版本的swap or not shuffling。