作者 | Ben Edgington
簡介
如果你想學鬼步舞 (shuffle dance) 的話，那你就走錯地方了。但相信我，Eth2裡的混洗 (shuffle) 也一樣讓人興奮。
混洗列表是以太坊2.0裡一個基本運算。它主要用於在每12秒的slot裡偽隨機挑選驗證者來組成委員會，以及在每個slot裡選出信標鏈區塊的提議者。
混洗似乎相當簡單。儘管它有一些隱患需要注意，這些隱患在電腦科學裡是非常容易理解的。其中的黃金標準大概就是Fisher-Yeats shuffle了。那我們為什麼不在Eth2裡使用它呢？我將在文末詳細解釋，但簡單來說就是——輕客戶端。
我們用的混洗演算法是swap-or-not，而不是Fisher-Yates。這個選擇是基於這篇本來用於構建加密方案的論文。我最近在Eth2客戶端Teku中重寫我們的實現，因此我想趁熱把它寫出來。
Swap-or-Not混洗演算法
一輪的操作過程
混洗以輪次進行。每輪的過程是一樣的，因此我在下面只會演示一輪的過程，它比看上去簡單多了。☺
選擇一個軸心點並找出第一個映象索引
首先，我們選一個軸心索引p，這是基於輪次和其他一些種子資料，透過偽隨機選出的。這個軸心選出後就在該輪次裡固定了。
基於這個軸心點，我們在p和0的中間點選出一個映象索引m1，即m1=p/2。（為了方便解釋，我們將忽略麻煩的差一錯誤舍入問題）
軸心點和第一個映象index
從第一個映象索引到軸心點，替換與否
對於映象索引m1和軸心索引p之間的每個索引，我們隨機決定是否對這些元素進行替換。
比如對於索引i1，如果我們選擇不替換，那麼我們就繼續選下一個索引。
如果我們決定替換，那麼我們將i1上的列表元素與i1’上的替換，即它在映象索引上的影象。也就是i1與i1’=m1-(i1-m1)替換，這樣i1和i1’到m1的距離是相等的。
我們對每個m1和p之間的索引都做相同的swap-or-not的決定。
從第一個映象索引到軸心的swap-or-not決定
計算第二個映象索引
在做完從m1到p的所有索引決定後，我們現在找到第二個以m2為中點的映象索引，即到p和列表末端的距離相等的點。也就是m2=m1+n/2。
第二個映象索引
從軸心點到第二個映象，替換與否
最後，我們重複swap-or-not的過程，考慮所有點到軸心p替換的決定，即p到第二個映象m2的決定。如果我們選擇不替換，就繼續下一個。如果我們選擇替換，那麼我們在映象索引m2上把j1上的元素與它在j1’上的映象進行替換。
從軸心到第二個映象索引的swap-or-not決定
組合起來
在一輪的最後，我們都已經考慮了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是自然對數)。因此，我們現在處於一個大致正確的範圍，特別是我們最後非常可能沒有這麼多活躍驗證者。
基於列表長度來調整輪次可能會得出有趣的結果，但我們不會這麼做，這可能是不必要的最佳化。
有意思的是，當Least Authority審計信標鏈的規範時，他們一開始發現在選擇區塊提議者的混洗中是有偏倚的 (參考Issue F)。但結果是他們錯誤使用了只有10輪次的混洗配置。當他們將混洗配置增加到90輪 (我們在主網使用的輪次) 時，偏倚的情況消失了。
(偽) 隨機
混洗演算法要求我們在每一輪裡隨機選一個軸心點，且在每輪裡隨機選擇是否對每個元素進行替換。
在Eth2，我們肯定會從一個種子值產生隨機性，由此這同一個種子總會產生同一個混洗結果。
軸心指標是由把與輪次串聯的種子進行8位元組的SHA2雜湊產生的，軸心索引由種子值SHA2雜湊的八個位元組生成，該種子值與輪次相串聯，因此它通常在每輪裡都有會改變。
用來決定是否要替換元素的決定性數位從以下幾個元素中提取：種子的SHA256雜湊、輪次、列表上元素的索引。
效率
這個混洗演算法比Fisher-Yates演算法要慢得多。如果Fisher-Yates演算法需要N次混洗的話，我們的演算法平均需要90N/4次。我們還要考慮偽隨機性的產生，這是演算法中成本最高的部分。Fisher-Yates需要接近Nlog2N數位的隨機性，而我們需要90(log2N+N/2)數位，根據我們在Eth2裡需要的N值範圍，超出的數位是相當多的(當N為一百萬時，Eth2大約需要N的兩倍)。
為什麼選擇swap-or-not這種演算法
如果效率不高，為什麼要選擇這個實現？
對單一元素進行混洗
這個演算法的閃光點在於，如果我們只關注少數幾個索引，我們不需要對整個列表的混洗進行計算。事實上，我們可以將這個演算法用於單個索引，來找出哪個索引將會被替換。
因此，如果我們想知道索引217的元素被混洗到哪裡了，我們可以執行只針對該索引的演算法，而無需混洗整個列表。此外，相反地，如果我們想知道是什麼元素被混洗到索引217，我們可以將演算法倒過來執行來找到元素217 (倒過來的意思是從高到低執行輪次，而不是從低到高)。
總之，我們可以在恆定時間內計算出元素i被混洗到哪裡，也可以計算出元素i的源頭在哪裡 (用反向操作)，計算時間並不取決於列表的長度。Fisher-Yates混洗並不具有這種特性，且不能對單個索引進行混洗，它們往往需要重複混洗整個列表。
在Eth2規範裡寫的就是關於如何將演算法應用到對單個索引進行混洗。事實上，一次性混洗整個列表只是它的一種最佳化！如果我們想的話，我們可以輪流只對列表裡的一個元素進行混洗：(反向) 執行混洗來找出哪個元素最終落在索引0，再執行一次混洗找出哪個元素最終落在索引1，如此進行下去。
我們不那樣做的原因只是由於決定swap-or-not需要一次性生成一個256位的雜湊，且就這樣拋棄255位是很浪費的。如果我們使用1位的雜湊或預言，混洗列表中一個元素的效率與混洗整個列表相去無幾。
做到真正的“輕”客戶端
這個特性之所以有意義，原因全在於輕客戶端。輕客戶端相當於是Eth2信標鏈和分片鏈的觀測者，他們不儲存整個狀態，但希望可以安全地訪問鏈上的資料。要對他們的資料正確性進行驗證，即沒有發生欺詐，其中的必要一步就是對證明資料的委員會進行計算。
也就是要用到混洗演算法，且我們並不希望輕客戶端必須儲存或是混洗整個驗證者列表。透過swap-or-not混洗，他們可以只對他們需要的一小部分委員會成員進行計算，這樣將在整體上大幅提高效率。
歷史
如果你像我一樣喜歡GitHub的考古特性，你可以在這裡檢視最初為Eth2尋求混洗演算法的討論，這裡公佈了最後的勝出者。
如果想從另一個角度看swap-or-not混洗演算法，可以看一下Protolambda發表的一個更視覺化的解釋。
最後
這張圖片是2019年我在EthCC上一邊聽Justin Drake講swap-or-not混洗，一邊在Teku客戶端 (當時它還叫Artemis) 中實現初版swap-or-not混洗。☺
點選“閱讀原文”獲取文章內部連結！
原文連結：https://hackmd.io/@benjaminion/shuffling
ECN的翻譯工作旨在為中國以太坊社羣傳遞優質資訊和學習資源，文章版權歸原作者所有，轉載須註明原文出處以及ETH中文網。若需長期轉載，請聯絡[email protected]進行授權。
