イーサリアム 2.0 のシャッフル アルゴリズムを 1 つの記事で読む
導入
著者|導入学びたいなら
ゴーストステップダンス
（シャッフルダンス）、その場合、あなたは間違った場所にいます。しかし信じてください、Eth2 でのシャッフルも同じくらいエキサイティングです。シャッフル リストはイーサリアム 2.0 の基本操作です。これは主に、12 秒スロットごとに委員会を形成する検証者を擬似ランダムに選択し、各スロットでビーコン チェーン ブロックの提案者を選択するために使用されます。シャッフルはかなり簡単なようです。多少はあるもののFisher-Yeats shuffle隠れた危険
上。では、なぜそれを Eth2 で使用しないのでしょうか?記事の最後で詳しく説明しますが、簡単に言うと、ライトクライアントです。紙紙Teku真ん中。最近 Eth2 クライアントを使用しています真ん中
リライト
私たちの実装なので、熱いうちに書いておきたいと思いました。
スワップオアノットシャッフルアルゴリズム
作戦のラウンド
シャッフルはラウンドで実行されます。このプロセスは各ラウンドで同じであるため、以下では 1 ラウンドのプロセスのみを説明します。これは、見た目よりもはるかに簡単です。
まず、ピボット インデックス p を選択します。これは、ラウンドやその他のシード データに基づいて擬似ランダムに選択されます。軸を選択したらラウンドで固定します。
このピボット ポイントに基づいて、p と 0 の間の中点にあるミラー インデックス m1、つまり m1=p/2 を選択します。 (説明のために、面倒な 1 つ 1 つの誤差の丸めの問題は無視します)
画像の説明
ピボットポイントとファーストミラーインデックス
2. 最初のミラーインデックスからピボットポイントまで、交換するかどうか
ミラー インデックス m1 とピボット インデックス p の間の各インデックスについて、それらの要素を置き換えるかどうかをランダムに決定します。
置換する場合は、i1 のリスト要素を i1' のリスト要素 (ミラー インデックス上のイメージ) に置き換えます。つまり、i1 と i1' から m1 までの距離が等しくなるように、i1 を i1'=m1-(i1-m1) に置き換えます。
m1 と p の間の各インデックスに対して、同じ交換するかどうかの決定を行います。
画像の説明
3. 2 番目のミラーインデックスを計算します。
m1 から p まですべてのインデックスを決定した後、m2 を中点、つまり p とリストの終わりから等距離にある点を持つ 2 番目のミラー インデックスを見つけます。つまり、m2=m1+n/2となります。
画像の説明
4. ピボットポイントから 2 番目のミラーまでを交換するかどうか
最後に、すべてのポイントツーピボット p の置換決定、つまり p から 2 番目のミラー m2 への決定を考慮して、スワップするかどうかのプロセスを繰り返します。交換しないことを選択した場合は、次の交換に進みます。置換することを選択した場合は、j1 上の要素を、ミラー インデックス m2 の j1' 上のミラー イメージに置き換えます。
画像の説明
ピボットから 2 番目のミラー インデックスへスワップするかどうかの決定
ラウンドの終了時に、m1 と m2 の間のすべてのインデックス、つまりすべてのインデックスの半分が考慮され、置き換えられるかどうかに関係なく、各インデックスが残りの半分に特定のインデックスを持ちます。したがって、置き換えるかどうかについては、すべてのインデックスが一度検討されています。
次のラウンドはラウンドの増加 (または減少) から始まり、新しいピボット インデックスが得られ、その後、上記のプロセスを循環し始めます。
画像の説明
同じラウンド内で 1 つのミラーから別のミラーに移動するプロセス
独創的な場所成し遂げる置換するかどうかを決定する際、アルゴリズムは候補インデックスまたはそのミラーイメージの高い方を賢く選択します。これは、軸より下にある場合は i_1' の代わりに i_1 が選択され、軸より上にある場合は i_k の代わりに i_k' が選択されることを意味します。これは、リスト内のインデックスを柔軟に反復処理できることを意味します。本文で説明したように、0 から m1 と p から m2 を 2 つの別個のループに分けることも、m1 から m2 までの同じループ内で両方を結合することもできます。 （そして
成し遂げる
）の。結果はどちらの方法でも同じです。i_1 を考慮するか、i_1' をミラーリングするかは問題ではありません。置換してもしなくても、同じ結果が得られます。ラウンドEth2では上記の処理を90回行うことになります。原紙「選択的パスワード攻撃 (CCA) に対して十分なセキュリティ マージンを示し始める」には 6lgN ラウンドが必要であると述べられています。ここで、N はリストの長さです。ヴィタリックにて
アノテーション仕様
同氏は、「暗号学の専門家は、十分なセキュリティを提供するには4log2Nラウンドがあると示唆している」と述べた。 Eth2 のバリデーターの絶対最大数 (リストをシャッフルする必要がある最大回数) は、約 222 (420 万) です。 Vitalik によって与えられた推定値は 88 ラウンドであり、論文の推定値は 92 ラウンドです (lg を自然対数と仮定します)。したがって、特にこれほど多くのアクティブなバリデーターが最終的に存在する可能性は非常に低いため、現在はほぼ正しい範囲内にあります。Issue Fリストの長さに基づいてラウンドを調整すると興味深い結果が得られる可能性がありますが、不必要な最適化になる可能性があるため、それは行いません。
興味深いことに、最小権限機関がビーコン チェーンの仕様を監査したとき、ブロック提案者を選択するシャッフルに偏りがあることが最初に判明しました (「
）。しかし、彼らは誤って 10 ラウンドのみのシャッフル構成を使用したことが判明しました。シャッフル構成を 90 ラウンド (メインネットで使用している数) に増やしたところ、偏りはなくなりました。
(擬似)ランダム
シャッフル アルゴリズムでは、各ラウンドでピボット ポイントをランダムに選択し、各ラウンドで各要素を置き換えるかどうかをランダムに選択する必要があります。
Eth2 では、シード値からランダム性を確実に生成します。これにより、同じシードは常に同じシャッフル結果を生成します。
ピボットインジケーターは、ラウンドと連結されたシードの 8 バイト SHA2 ハッシュによって生成されます。
ピボット インデックスは、ラウンドと連結されたシード値の SHA2 ハッシュの 8 バイトから生成されるため、通常はラウンドごとに変更されます。
要素を置換するかどうかを決定するために使用される決定的なビットは、シードの SHA256 ハッシュ、ラウンド、リスト上の要素のインデックスの要素から抽出されます。
効率
このシャッフル アルゴリズムは、Fisher-Yates アルゴリズムよりもはるかに低速です。 Fisher-Yates アルゴリズムが N 回のシャッフルを必要とする場合、私たちのアルゴリズムでは平均 90N/4 回のシャッフルが必要です。また、アルゴリズムの中で最もコストがかかる部分である擬似乱数の生成についても考慮する必要があります。 Fisher-Yates は Nlog2N 桁に近いランダム性を必要とし、90(log2N+N/2) 桁が必要ですが、Eth2 で必要な N 値の範囲によれば、超過桁数はかなり多くなります (N が 100 万の場合) 、Eth2 は N の約 2 倍必要です）。
スワップ・オア・ノット・アルゴリズムを選択する理由は何ですか?
効率的でない場合、なぜこの実装を選択するのでしょうか?
単一の要素をシャッフルする
したがって、インデックス 217 の要素がどこでシャッフルされたかを知りたい場合は、リスト全体をシャッフルせずに、そのインデックスに対してのみアルゴリズムを実行できます。また、逆に、どの要素がインデックス 217 にシャッフルされたかを知りたい場合は、アルゴリズムを逆に実行して要素 217 を見つけることもできます (逆とは、ラウンドを低から高へではなく、高から低へ実行することを意味します)。
Eth2仕様
に書かれているのは、アルゴリズムを単一のインデックスのシャッフルに適用する方法についてです。実際、リスト全体を一度にシャッフルすることは、単にリストを最適化するだけです。必要に応じて、リストの 1 つの要素だけを順番にシャッフルすることもできます。(逆に) シャッフルを実行してインデックス 0 になった要素を見つけ、別のシャッフルを実行してインデックス 1 になった要素を見つけます。そうしない理由は、単にスワップの有無で一度に 256 ビットのハッシュを生成する必要があり、そのように 255 ビットを捨てるのは無駄であるという判断によるものです。 1 ビットのハッシュまたはオラクルを使用する場合、リストの 1 つの要素をシャッフルすることは、リスト全体をシャッフルするのとほぼ同じくらい効率的です。
本当の「ライト」クライアントになる
歴史ここここここEth2 のシャッフル アルゴリズムのオリジナルの探求に関するディスカッションを確認してください。
ここスワップ・オア・ノット・シャッフル・アルゴリズムを別の角度から見てみたい場合は、Protolambda によって公開されているアルゴリズムを参照してください。。
やっと
やっと
免責事項: ECN の翻訳作業は、中国のイーサリアム コミュニティに高品質の情報と学習リソースを提供することを目的としています。記事の著作権は原著者に属します。転載する場合は、原文と ethereum.cn の出典を示す必要があります。再版の場合は、ethereumcn@gmail.com までご連絡ください。
