Filecoin - PoREP 回路の紹介

PoREP 回路に関連するロジックは、storage-proofs/src/porep/stacked/circuit/ ディレクトリにあります。 Rust-fil-proofs コードは比較的迅速に更新されます。この記事で使用したコードの最終コミット情報は次のとおりです。

コミット 14870d715f1f6019aba3f72772659e38184378bf
著者: ロッド・ヴァッグ
日付: 2020 年 3 月 20 日金曜日 22:30:18 +1100
    feat(filecoin-proofs): filecoin_proofs::pad_reader を公開する

SDR アルゴリズムが変更されない限り、一般的な回路ロジックは大幅に変更されません。 SDR アルゴリズムに詳しくない方は、以下をご覧ください。

Filecoin - SDR はなぜこんなに遅いのですか?

PoREP 回路全体のコード フレームワークを下図に示します。

まずはStackedCircuitから始めましょう。

StackedCircuit は PoREP の全体的な回路です。 StackedCircuit は storage-proofs/src/porep/stacked/circuit/proof.rs で定義されています。

 pub struct StackedCircuit<'a, e:="" h:="" static="" g:="" hasher=""> {
    パラメータ: &'a E::Params,
    public_params:<StackedDrg<'a, g="">として ProofScheme<'a>>::PublicParams、
    replica_id: オプション
    comm_d: オプション
    comm_r: オプション
    comm_r_last: オプション
    comm_c: オプション
    証明: Vec<証明
}

で

• params - JubjubEngine関連のパラメータ、

• public_params - StackedDrg (ディープロバストグラフ) 関連のパラメータ。グラフ自体のパラメータやチャレンジの数などが含まれます。

• replica_id - セクターレプリケーションID

• comm_d – 元のデータのバイナリツリーのルート

• comm_r - comm_r_last と comm_c のハッシュ結果

• comm_r_last - エンコードされたデータの八分木のルート

• comm_c - 列ハッシュ結果の八分木のルート

• 証明 - チャレンジに対応する証明回路

回路全体の構築は、StackedCircuit の合成インターフェース関数から始まります。

 impl<'a, h:="" g:="" hasher=""> 回路
    fn 合成<CS: 制約システム

全体の合成機能は、回路を 2 つの部分に分割します: 1/ ツリー ルート検証回路 2/ チャレンジ ノード情報証明回路。その中でもツリールート検証回路は比較的単純で理解しやすいものです。 replica_id_bits、comm_d、comm_r、comm_r_last、および comm_c 変数を適用し、comm_c と comm_r_last が comm_r を正しく計算できるかどうかを確認します。

セクターサイズが 32G の場合、チャレンジの数は 144 です。つまり、チャレンジ ノード プルーフ回路全体は 144 個の小さな回路で構成されます。

 proofs.into_iter().enumerate() 内の (i, proof) に対して {
            証明.合成(
                &mut cs.namespace(|| format!("challenge_{}", i)),
                &self.params,
                public_params.layer_challenges.layers()、
                &通信番号,
                &通信番号、
                &comm_r_last_num,
                &レプリカIDビット、
            )?;
        }

証明構造 (storage-proofs/src/porep/stacked/circuit/params.rs) によって表される、各チャレンジ ノードの小さな回路。

 pub struct 証明
    pub comm_d_proof: インクルージョンパス
    pub comm_r_last_proof: インクルージョンパス
    pub レプリカ列証明: レプリカ列証明
    pub ラベル付け証明: Vec<(usize,>,
    pub エンコーディング証明: エンコーディング証明、
}

Proof の構造は比較的明確で、次のようになります。

• comm_d_proof - オリジナルデータのマークルツリー証明

• encoding_proof - エンコード結果の証明

• comm_r_last_proof - エンコード結果のマークルツリー証明

• labeling_proofs - 計算証明のラベル付け

• replica_column_proof - 列ハッシュの計算の証明

Proof の synthesize 関数は上記の証明を構築します。

元データのMerkleツリー証明回路は、comm_d_leafのノードがcomm_dをルートとするMerkleツリー上にあることを証明します。

 comm_d_leaf を comm_d_proof.alloc_value(cs.namespace(|| "comm_d_leaf")) としますか?;
comm_d_proof.synthesize() は、
    cs.namespace(|| "comm_d_inclusion"),
    パラメータ、
    comm_d.clone()、
    comm_d_leaf.clone()、
)?;

ここで、comm_d_leaf は回路内の変数です。 comm_d_proof は、storage-proofs/src/porep/stacked/circuit/params.rs で定義されている InclusionPath 構造です。 InclusionPath 回路のコア ロジックは、合成関数にあります。

 pub fn synthesize<CS: ConstraintSystem
    自己、
    cs: CS、
    パラメータ: &
    ルート: num::AllocatedNum
    リーフ: num::AllocatedNum
) -> 結果<(), synthesiserror=""> {
    InclusionPath { auth_path, .. } = self; とします。
    root = Root::from_allocated:: とします。
    値をRoot::from_allocated::とします。
    PoR回路::
}

取得を証明するすべての回路は PoRCircuit を通じて実装されていることがわかります。つまり、現在の PoR は Merkle ツリーを通じて実装されています。 PoRCircuit 回路は、storage-proofs/src/gadgets/por.rs で定義されています。 PoRCircuit 回路は、リーフ ノードとパス情報を組み合わせて、最終的に「計算された」ルートが指定されたルートと一致しているかどうかを確認します。具体的な関連ロジックはご自身でご確認いただけます。

ラベリング計算の証明回路は、特定のノードが SDR アルゴリズムに従って正しく計算されていることを証明することです。

 labeling_proofs.into_iter() 内の (レイヤー、証明) について {
    raw = replica_column_proof.c_x.get_node_at_layer(レイヤー);
    ラベル付きノード =
         num::AllocatedNum::alloc(cs.namespace(|| format!("label_node_{}", レイヤー)), || {
                    生のマップ(Into::into)
                        .ok_or_else(|| 合成エラー::割り当て不足)
                })?;
    証明.合成(
         cs.namespace(|| format!("labeling_proof_{}", レイヤー)),
         パラメータ、
         レプリカID、
         &labeled_node,
    )?;
}

あるレイヤー上のノードのラベリング結果データは、replica_column_proof.c_x.get_node_at_layer(layer) を通じて取得できます。 Labeling の計算回路は、LabelingProof 構造体の合成関数によって実装されます。

 pub fn synthesize<CS: ConstraintSystem
        自己、
        ミュート cs: CS、
        パラメータ: &
        レプリカID: &[ブール値],
        exp_encoded_node: &num::AllocatedNum
    ) -> 結果<(), synthesiserror=""> {
        LabelingProof { ノード、親 } = self;
        キーをSelf::create_label(
            cs.namespace(|| "create_label"),
            パラメータ、
            レプリカID、
            ノード、
            両親、
        )?;
        // 平等を強制する
        制約::equal(&mut cs, || "equality_key", &exp_encoded_node, &key);
        わかりました（（））
    }
}

create_label 関数は、create_label_circuit と sha256_circuit の 2 つの回路で構成されています。つまり、これら 2 つの回路は、依存 (親) ノード データに対して sha256 計算を実行します。 constraint::equal は、「計算された」ノード データが提供されたノード データと一致しているかどうかを確認するために使用されます。

エンコード計算は、最終層のノードデータと元のデータをエンコードすることです。エンコードの計算方法は、大きな数値の加算です。具体的な計算は storage-proofs/src/gadgets/encode.rs ファイルにあります。

エンコーディング証明.合成(
            cs.namespace(|| format!("encoding_proof_{}", レイヤー)),
            パラメータ、
            レプリカID、
            &comm_r_last_data_leaf、
            &comm_d_leaf、
        )?;

エンコーディング証明回路全体は、EncodingProof の合成関数によって実装されます。簡単に言うと、エンコードの回路検証プロセスでは、まずラベル付けを計算し、次に comm_d_leaf に対してエンコード計算を実行し、その結果が comm_r_last_data_leaf と一致するかどうかを判断します。

元のデータの Merkle ツリー証明回路証明と同様に、comm_r_last_data_leaf が comm_r_last の Merkle ツリー上にあることを証明します。ただ、この木は八分木です。

 comm_r_last_proof.合成(
     cs.namespace(|| "comm_r_last_data_inclusion"),
     パラメータ、
     comm_r_last.clone()、
     comm_r_last_data_leaf、
)?;

列ハッシュの証明回路は、ReplicaColumnProof 構造の合成によって実装されます。これは、storage-proofs/src/porep/stacked/circuit/params.rs で具体的に定義されています。

 replica_column_proof.synthesize(cs.namespace(|| "replica_column_proof"), params, comm_c)?;

一般的なロジックは、最初にチャレンジ ノードの列情報を処理し、次にベース ノードと exp 依存ノードの列情報をそれぞれ処理することです。

 // c_x
c_x.synthesize(cs.namespace(|| "c_x"), params, comm_c)?;
// ドラッグ親
drg_parents.into_iter().enumerate() 内の (i, parent) について {
     parent.synthesize(cs.namespace(|| format!("drg_parent_{}", i)), params, comm_c)?;
}
// exp 親
exp_parents.into_iter().enumerate() 内の (i, parent) の場合 {
     parent.synthesize(cs.namespace(|| format!("exp_parent_{}", i)), params, comm_c)?;
}

つまり、証明回路は 15 個の ColumnProof サブ回路で構成されます。 ColumnProof は storage-proofs/src/porep/stacked/circuit/column_proof.rs で定義されています。

 pub 構造体 ColumnProof
    列: 列、
    インクルージョンパス: インクルージョンパス
}

対応する回路生成ロジックは、ColumnProof の合成関数にあります。

 c_i = column.hash(cs.namespace(|| "column_hash"), params) とします。
leaf_num = include_path.alloc_value(cs.namespace(|| "leaf")) とします。
制約::equal(&mut cs, || "enforce column_hash = leaf", &c_i, &leaf_num);
// TODO: 現在、リーフを 2 回割り当てていますが、インクルード パスは、すでに割り当てられているリーフを取得する必要があります。
インクルージョンパスを合成する(
    cs.namespace(|| "column_proof_all_inclusion"),
    パラメータ、
    comm_c.clone()、
    葉番号、
)?;

column.hash は、列に対応するハッシュ結果を計算します。この結果が leaf_num と等しいかどうかを確認します。同時に、この leaf_num が comm_c の Merkle ツリー内にあるかどうかを確認します。

これまでのところ、回路全体の全体像が明らかになっています。

PoREP 回路全体のパブリック入力は、StackedCompound の generate_public_inputs 関数によって実装されます。この関数は、具体的には storage-proofs/src/porep/stacked/circuit/proof.rs ファイルに実装されています。

 fn パブリック入力を生成する(
    pub_in: &<スタックドDrg
    pub_params: &<スタックされたDrg
    k: オプション
) -> 結果<ベクトル

ここで、k はパーティション番号です。 32G セクターの場合、合計 9 つのパーティションがあります。

comm_d と comm_r

 comm_d = pub_in.tau.as_ref().expect("tauが見つかりません").comm_d; とします。
comm_r = pub_in.tau.as_ref().expect("tauが見つかりません").comm_r;

comm_dの存在証明に挑戦

現在、PoRCompound は、Merkle ツリーのパス情報のみを公開入力として使用します。

入力を拡張します(PoRCompound::
     &pub_inputs、
     &por_params,
     け、
)?);

一連の通信の存在証明に挑戦

comm_d の計算はバイナリ ツリーであり、comm_c の計算はオクツリーであることに注意してください。

 // c_x
inputs.extend(generate_inclusion_inputs(チャレンジ)?);
// ドラッグ親
mut drg_parents = vec![0; とします。 graph.base_graph().degree()];
graph.base_graph().parents(チャレンジ、&mut drg_parents)?;
drg_parents.into_iter() 内の親の場合 {
    inputs.extend(generate_inclusion_inputs(親をusizeとして)?);
}
// exp 親
mut exp_parents = vec![0; とします。グラフの展開度();
graph.expanded_pa​​rents(チャレンジ、&mut exp_parents);
exp_parents.into_iter() 内の親の場合 {
    inputs.extend(generate_inclusion_inputs(親をusizeとして)?);
}

comm_r_lastの存在証明に挑戦

inputs.extend(generate_inclusion_inputs(チャレンジ)?);

要約:

PoREP の回路は、ラベル付け、エンコードから列ハッシュまでのセクターの計算プロセスを検証します。セクター サイズが 32G の場合、回路には 144 個のチャレンジ ノードの計算が含まれることに注意してください。 comm_d と comm_r に加えて、回路の対応する公開入力には、各 Merkle ツリーのパス情報も含まれます。