Filecoin - NSEアルゴリズムの詳細な理解

PoREP アルゴリズムがウィンドウ SDR から SDR に変更されるまでに、それほど時間はかかりませんでした。新しい PoREP アルゴリズム NSE はすでに開発中です。 NSE アルゴリズムの正式名称: N arrow S tacked Expander PoRep。 NSE アルゴリズムの実装は、rust-fil-proofs の feat/nse ブランチで確認できます。

この記事で使用したソースコードの最終コミット情報は次のとおりです。

コミット af4bdcb6da4b371230eed441218c459e99d32068 (HEAD -> feat/nse、origin/feat/nse)
マージ: 7e7eab2 578d12c
著者: porcuquine <[email protected]>
日付: 2020 年 5 月 20 日水曜日 12:11:43 -0700

    filecoin-project/feat/nse-update-neptune-alt からプルリクエスト #1118 をマージしました
    
    Feat/nse アップデート ネプチューン alt

NSE アルゴリズムを理解するには、まず storage-proofs/porep/src/nse/vanilla/porep.rs の NarrowStackedExpander 構造の複製関数から始めることができます。

NSE は N が Narrow (狭い) の略であるため NSE と呼ばれます。狭いというのは、以前の SDR アルゴリズムよりも狭く、データが処理されるたびにウィンドウが狭くなることを意味します。

各ウィンドウは、処理のレイヤーを経て対応するレプリカを生成します。すべてのウィンドウに対応する各レイヤーのデータは、Merkle ツリーにまとめて構築されます。すべてのウィンドウに対応するレプリカのデータも、Merkle ツリーに構築されます。これら 2 つのツリーのルートの Poseidon ハッシュの結果が comm_r として使用されます。 comm_d と comm_r はチェーンにアップロードする必要があるデータです。

各ウィンドウは、マスク レイヤー、エクスパンダー レイヤー、バタフライ レイヤーに分かれた多くのレイヤーの処理を経る必要があります。コアロジックは、storage-proofs/porep/src/nse/vanilla/labels.rs の encode_with_trees 関数にあります。

Expander/Butterflyのレイヤー数の構成や一部のパラメータ構成は未定です。テストコードの構成から:

        num_windows = 1 とします。

        rng = &mut XorShiftRng::from_seed(crate::TEST_SEED); とします。
        replica_id = <PoseidonHasher as Hasher>::Domain::random(rng); とします。
        config = Config { を設定します。
            k: 8,
            num_nodes_window: (セクターサイズ / num_windows) / NODE_SIZE、
            度数展開: 384,
            度数_バタフライ: 16,
            num_expander_layers: 8,
            蝶のレイヤー数: 7,
            セクターサイズ、
        };

ウィンドウは 1、エクスパンダーの依存関係は 384、バタフライの依存関係は 16 に設定されています。合計 15 フロアがあります。

マスクレイヤー

マスク レイヤーは特定のデータとは関係ありませんが、ウィンドウ番号/ノード番号に関連しています。

エキスパンダーレイヤー

Expander レイヤーは、ExpanderGraph に基づいて、依存する前のレイヤーのノードのデータを生成します。これらのデータの sha256 結果といくつかの番号情報は、新しいノードのデータとして使用されます。次に例を示します。

親ノードの計算については、storage-proofs/porep/src/nse/vanilla/expander_graph.rs の ExpanderGraphParentsIter 構造体の update_hash 関数と next 関数を参照してください。

 pub構造体ExpanderGraph{
    /// 単一の親を識別するために必要なビット数。
    pubビット: u32、
    /// バッチハッシュ係数。
    pub k: u32、
    /// グラフの次数。
    pub 度: 使用サイズ、
 }
        
        
 // ノードインデックス - 4 バイト
self.hash[..4].copy_from_slice(&self.node.to_be_bytes());
 // カウンター - 4 バイト
self.hash[4..8].copy_from_slice(&self.counter.to_be_bytes());
 // パディング 0 - 24 バイト
i が 8..32 の場合
     自己ハッシュ[i] = 0;
 }

 mut hasher = Sha256::new() とします。
 hasher.input(&[&self.hash[..], &[0u8; 32]]);
ハッシュ関数は、次のように記述します。

簡単に言えば、各ノードが依存する親の数は degree*k です。親は、ノード番号と親のシーケンス番号のハッシュ結果によって決定されます。

具体的なハッシュ計算ロジックについては、storage-proofs/porep/src/nse/vanilla/batch_hasher.rs の batch_hash 関数を参照してください。

 (i, j) が (0..degree).tuples() 内にある場合 {
        k = k を u32 とします。

        (el1, el2) = (0..k).fold(とします。
            (FrRepr::from(0), FrRepr::from(0)),
            |(ミュート el1、ミュート el2)、l| {
                y1 = i + (l as usize * degree as usize) とします。
                親1を親[y1をusizeとして]とします。
                current1 を read_at(data, parent1 を usize として) にします。
                y2 = j + (l as usize * degree as usize) とします。
                parent2 = parents[y2 as usize]とします。
                current2 を read_at(data, parent2 を usize として) にします。

                add_assign(&mut el1, &current1, &modulus);
                add_assign(&mut el2, &current2, &modulus);

                (エル1、エル2)
            },
        );

        // 一度に 2 つの 32 バイトのチャンクをハッシュする
        ハッシュ関数は、文字列をハッシュ化して返します。
    }

バッチハッシュの名前はバッチに由来しています。ハッシュする前に、k 個の親をモジュラーで追加し、モジュラー追加の結果がハッシュされます。

バタフライレイヤー

バタフライ レイヤーの計算は、親を取得する方法と親のハッシュ計算を除いて、エクスパンダー レイヤーの計算と似ています。 Parents の計算は ButterflyGraph の実装によって異なります。

 pub構造体バタフライグラフ{
    /// グラフの次数。
    pub 度: 使用サイズ、
    /// ウィンドウ内のノードの数。 2 の累乗である必要があります。
    pub num_nodes_window: u32、
    /// レイヤーの合計数。
    pub num_layers: u32,
    /// 蝶の層の数。
    pub num_butterfly_layers: u32、
 }

 fn next(&mut self) -> Option<Self::Item> {
    self.pos >= self.graph.degree の場合、u32 {
        None を返します。
    }

    parent_raw = self.node + self.pos * self.factor とします。
    // モジュラスN
    親をparent_raw & (self.graph.num_nodes_window - 1)とします。

    自己位置 += 1;
    一部(親)
 }

バタフライ レイヤー内のノードは、前のレイヤー内のノードに程度によって依存します。各親番号の計算式は次のとおりです。

ノード + 位置 * 係数

このうち、node はノード番号、pos は親番号、factor は係数（レイヤー番号に関連）です。このような一定の間隔を持つ従属的な形状は、蝶の羽の縞模様に少し似ているため、バタフライ レイヤーと呼ばれます。

すべての親のハッシュ計算は比較的単純で、連結されたすべての親データのハッシュ値になります。

 // 親のハッシュを計算します。
 graph.parents(node_index, layer_index).tuples() 内の (parent_a, parent_b) について {
     parent_a = parent_a を usize とします。
     parent_b = parent_b を usize として扱います。
     parent_a_value = &layer_in[parent_a * NODE_SIZE..(parent_a + 1) * NODE_SIZE]とします。
     parent_b_value = &layer_in[parent_b * NODE_SIZE..(parent_b + 1) * NODE_SIZE]とします。
     hasher.input(&[親aの値、親bの値]);
 }

ハッシュを hasher.finish() とします。

マルチレイヤー処理が完了すると、最後のバッファフライ レイヤーが元のデータでエンコードされ、最終的なレプリカ レイヤーが生成されます。計算プロセスは、最後のバッファフライレイヤーに基づいて別のバッファフライ計算を実行し、その結果と元のデータに対して大きな数値の加算計算を実行します。詳細な計算プロセスについては、storage-proofs/porep/src/nse/vanilla/labels.rs の butterfly_encode_decode_layer 関数を参照してください。

要約:

PoREP の NSE アルゴリズムは、SDR アルゴリズムの別の試みです。単一プロセス（ウィンドウ）で処理されるデータのサイズを小さくし、ノードのフロントエンドとバックエンドの依存関係を使わないようにし（レイヤー計算は並列化できる）、単一レイヤーの依存関係を増やし、レイヤーの数を増やします。基礎となるアルゴリズムでは、引き続き sha256 アルゴリズムが使用されます。 NSE アルゴリズムは、セキュリティとパフォーマンスのバランスを取ろうとする試みとして理解できます。