这个算法的闪光点在于，假如我们只存眷少数几个索引，我们不需要对整个列表的混洗举办计较。事实上，我们可以将这个算法用于单个索引，来找出哪个索引将会被替换。
混洗好像相当简朴。尽量它有一些隐患需要留意，这些隐患在计较机科学里长短常容易领略的。个中的黄金尺度或许就是Fisher-Yeats shuffle了。那我们为什么不在Eth2里利用它呢？我将在文末具体表明，但简朴来说就是——轻客户端。
我们不那样做的原因只是由于抉择swap-or-not需要一次性生成一个256位的哈希，且就这样丢弃255位是很挥霍的。假如我们利用1位的哈希或预言，混洗列表中一个元素的效率与混洗整个列表相去无几。
基于这个轴心点，我们在p和0的中间点选出一个镜像索引m1，即m1=p/2。（为了利便表明，我们将忽略贫苦的差一错误舍入问题）
从第一个镜像索引到轴心点，替换与否
组合起来
因此，假如我们想知道索引217的元素被混洗到那边了，我们可以运行只针对该索引的算法，而无需混洗整个列表。另外，相反地，假如我们想知道是什么元素被混洗到索引217，我们可以将算法倒过来运行来找到元素217 (倒过来的意思是从高到低运行轮次，而不是从低到高)。
从轴心点到第二个镜像，替换与否
在Eth2，我们必定会从一个种子值发生随机性，由此这同一个种子总会发生同一个混洗功效。
假如你像我一样喜欢GitHub的考古特性，你可以在这里查察最初为Eth2寻求混洗算法的接头，这里发布了最后的胜出者。
对单一元素举办混洗
总之，我们可以在恒按时间内计较出元素 i 被混洗到那边，也可以计较出元素 i 的源头在那边 (用反向操纵)，计较时间并不取决于列表的长度。Fisher-Yates混洗并不具有这种特性，且不能对单个索引举办混洗，它们往往需要反复混洗整个列表。
效率
最后
一轮的操纵进程
(伪) 随机
简介
我们对每个m1和p之间的索引都做沟通的swap-or-not的抉择。
假如效率不高，为什么要选择这个实现？
在Eth2类型里写的就是关于如何将算法应用到对单个索引举办混洗。事实上，一次性混洗整个列表只是它的一种优化！假如我们想的话，我们可以轮番只对列内外的一个元素举办混洗：(反向) 运行混洗来找出哪个元素最终落在索引0，再运行一次混洗找出哪个元素最终落在索引1，如此举办下去。
下一轮以增加 (或淘汰) 轮次开启，这样我们会有一个新的轴心索引，然后开始轮回上述的进程。Swap-or-Not混洗算法
好比对付索引i1，假如我们选择不替换，那么我们就继承选下一个索引。
巧妙的处所
用来抉择是否要替换元素的抉择性数位从以下几个元素中提取：种子的SHA256哈希、轮次、列表上元素的索引。
对付镜像索引m1和轴心索引p之间的每个索引，我们随机抉择是否对这些元素举办替换。
假如想从另一个角度看swap-or-not混洗算法，可以看一下Protolambda颁发的一个更可视化的表明。
在一轮的最后，我们都已经思量了m1到m2之间所有的索引，即所有索引的一半，且无论替换与否，每个索引都在另一半有一个特定的索引。因此，关于替换与否，所有的索引都已被思量过一次了。
混洗以轮次举办。每轮的进程是一样的，因此我在下面只会演示一轮的进程，它比看上去简朴多了。☺
这张图片是2019年我在EthCC上一边听Justin Drake讲swap-or-not混洗，一边在Teku客户端 (其时它还叫Artemis) 中实现初版swap-or-not混洗。假如我们抉择替换，那么我们将i1上的列表元素与i1’上的替换，即它在镜像索引上的图像。也就是i1与i1’=m1-(i1-m1)替换，这样i1和i1’到m1的间隔是相等的。
这个特性之所以有意义，原因全在于轻客户端。轻客户端相当于是Eth2信标链和分片链的视察者，他们不储存整个状态，但但愿可以安详地会见链上的数据。要对他们的数据正确性举办验证，，即没有产生欺诈，个中的须要一步就是对质明数据的委员会举办计较。
也就是要用到混洗算法，且我们并不但愿轻客户端必需存储或是混洗整个验证者列表。通过swap-or-not混洗，他们可以只对他们需要的一小部门委员会成员举办计较，这样将在整体上大幅提高效率。
计较第二个镜像索引
假如你想学鬼步舞 (shuffle dance) 的话，那你就走错处所了。但相信我，Eth2里的混洗 (shuffle) 也一样让人欢快。
选择一个轴心点并找出第一个镜像索引
当在抉择要不要替换的时候，这个算法会巧妙地选择候选索引或其镜像中的更高者。意思是当在轴心之下时，被选择的是i_1而不是i_1’；当在轴心之上时，被选择的时i_k’而不是i_k。这意味着，我们可以机动遍历列表中的索引：我们可以将0到m1和p到m2分为两个独立的轮回，或将两者合在同一个从m1到m2的轮回，如我在上文所描画（和实现）的。这两种做法的功效是一样的：无论我思量的是i_1照旧镜像i_1’都没有干系；替换与否得出的是沟通的功效。
混洗列表是2.0里一个根基运算。它主要用于在每12秒的slot里伪随机挑选验证者来构成委员会，以及在每个slot里选出信标链区块的提议者。
汗青
做到真正的“轻”客户端
在Eth2里验证者数量的绝对最大值，也就是我们需要混洗的列表最大次数，或许是222 (420万)。Vitalik给出的预估值是88轮，在论文里的预估值是92轮 (假设lg是自然对数)。因此，我们此刻处于一个大抵正确的范畴，出格是我们最后很是大概没有这么多活泼验证者。
我们用的混洗算法是swap-or-not，而不是Fisher-Yates。这个选择是基于这篇原来用于构建加密方案的论文。我最近在Eth2客户端Teku中重写我们的实现，因此我想趁热把它写出来。
有趣之处
为什么选择swap-or-not这种算法
最后，我们反复swap-or-not的进程，思量所有点到轴心p替换的抉择，即p到第二个镜像m2的抉择。假如我们选择不替换，就继承下一个。假如我们选择替换，那么我们在镜像索引m2上把j1上的元素与它在j1’上的镜像举办替换。
在做完从m1到p的所有索引抉择后，我们此刻找到第二个以m2为中点的镜像索引，即到p和列表结尾的间隔相等的点。也就是m2=m1+n/2。轮次
在Eth2，上述的进程会举办90次。原始论文里提到要经验6lgN个轮次才气“开始在选择性暗码进攻 (CCA) 上呈现较好的安详性边界”，个中N是列表的长度。在Vitalik的注释类型里，他说“暗码学专家发起我们4log2N个轮次就能提供足够的安详性了”。
首先，我们选一个轴心索引p，这是基于轮次和其他一些种子数据，通过伪随机选出的。这个轴心选出后就在该轮次里牢靠了。有意思的是，当Least Authority审计信标链的类型时，他们一开始发此刻选择区块提议者的混洗中是有偏倚的 (参考Issue F)。但功效是他们错误利用了只有10轮次的混洗设置。当他们将混洗设置增加到90轮 (我们在主网利用的轮次) 时，偏倚的环境消失了。
混洗算法要求我们在每一轮里随机选一个轴心点，且在每轮里随机选择是否对每个元素举办替换。
轴心指标是由把与轮次串联的种子举办8字节的SHA2哈希发生的，轴心索引由种子值SHA2哈希的八个字节生成，该种子值与轮次相串联，因此它凡是在每轮里都有会改变。
郑重声明：本文版权归原作者所有，转载文章仅为传播更多信息之目的，如作者信息标记有误，请第一时间联系我们修改或删除，多谢。
