ブロック DAG の本当の最終性

序文

序文

最初のレベルのタイトル

ファイナリティの重要性

現在、ほとんどのブロックチェーン トポロジの最終性は確率に基づいています。つまり、トランザクションが実際に完了したことを 100% 確信することは決してできません。たとえば、ビットコイン ネットワークでは、時間の経過とともに (ビットコインの世界の言葉で言えば、ブロック数が増加するにつれて)、攻撃者がネットワークの残りの部分に追いつき、ブロックを再編成する確率は指数関数的に減少します。この指数関数的なリスク減少により、「6 ブロック」の経験主義が生まれました。言い換えれば、トランザクションを含むブロックにさらに 5 ブロックが追加された場合、トランザクションの深さは「6 ブロック」となり、統計的には、トランザクションは再配置攻撃の対象となる可能性はそれほど高くありません。

多くの場合、確率的な終了処理は問題ありません。ただし、それぞれが前のトランザクションの出力に依存する多数のトランザクションを実行している場合、または大規模なトランザクションを実行していて、このトランザクションが決して取り消されないことを確認する必要がある場合、ファイナリティはかなり重要なアップ。

最初のレベルのタイトル

DAG ファイナリティとは何を意味しますか?

初期の順序付けメカニズムの再配置リスクは主にアンカー チェーンが変更されたときに発生したことを思い出してください。

したがって、アンカー チェーンが定期的に固定されていることを確認できれば、何が起こってもアンカー チェーン上のブロックの順序を完全に決定できます。

どうすればいいでしょうか？ネットワークは、DAG 境界付近の特定のブロックに無限の重みを適用するために、ブロック DAG の構築と同期して定期的な投票を保持します。

ブロックに無限の重みが与えられると、そのブロックが直接またはゴースト ポインター (ゴースト ポインター) を介して間接的に指すすべてのブロックの重みが無限になることを意味します。これは、攻撃によってこの順序を覆すことが不可能になることを意味します。

上の図では、無限の重みを与えるためにオレンジ色のブロックを選択しました。ブロック DAG (図の濃い灰色でマーク) をポイントすることで、この無限がアンカー チェーン上のすべてのブロックに無限の重みを与えていることがわかります。 。これで、このアンカー チェーンとすべてのブロックの順序を独自のエポックで効果的に決定できました。

最初のレベルのタイトル

PBFT のようなアルゴリズムによる定期的なブロック選択

ファイナライズのために DAG 内のブロックを選択するには、PBFT (Practical Byzantine Fault Tolerance) アルゴリズムと同様のプロセスを採用します。 PBFT はよく開発され、広く導入されているアルゴリズムであることを考慮して、この記事に含まれる詳細と潜在的な障害 (障害) についてはここでは繰り返しません。

PBFT の周期ブロックのファイナライズ プロセスは、以下の非常に簡略化された図に示すように、大きく 4 つのステップに分かれています。

副題

1. 新しいブロックを提案する

• VRF を通じて適格性を計算します (SK、previous_PBFT_block_hash、current_vote_type、current_round_number、current_step_number) = (e, π)。ここで、e は適格性の値、π は VRF が正しく計算されたことの証明です。

• 「e < しきい値の場合、このラウンドで PBFT ブロックを提案する資格がある」を決定します。

• 最終確認のために境界上ではないが境界に近いDAGブロック候補、つまり現期間(Period)のブロック候補Ptを選択します。

• Pt と P(t-1) の間のサイクルを作成し (詳細は後述)、このサイクルに含まれるすべてのブロックを検索します。

• コンカレントスケジューラCSの作成

• (Pt、CS) およびタイムスタンプ、署名、受益者などのその他の情報を含む PBFT ブロック候補 (Pc) を作成します。

• Pcのハッシュを計算(ハッシュ)

• 副題

2. リーダーに投票する

• VRF を通じて資格を再度計算し (current_round_number プラス 1 と現在の投票タイプを取り込む)、別の (e, π) を生成します。

• 「e < しきい値の場合、このラウンドの対象となる」を決定します。

• 2 λ 待ちます。ここで、λ はネットワークの直径、つまり、ネットワーク内の最も遠い 2 つのノード間の (時間における) 最短距離です。

• π も正しいときに観測される e の最小値を計算し、作成者がその最小値になります e が「リーダー」の場合、作成者です - このノードが次の PBFT ブロック候補を提案するノードになります

• 副題

3. ブロックへの投票

• VRF を通じて資格を再度計算し (current_round_number プラス 1 と現在の投票タイプを取り込む)、別の (e, π) を生成します。

• 「e < しきい値の場合、このラウンドの対象となる」を決定します。

• 2 ラムダを待ちます

• 指定された e_min 時間内に 2T+1 票を受け取ったかどうかを計算します (ここで、T は最後のラウンドで適格な投票ノードの 1/3 です)

• PBFT ブロックがまだない場合は、e_min と関連するハッシュ (Pc) に対応する Pc に対してピアツーピア ポーリングを実行します。

• PC が正しく作成されたことを確認する

• 副題

4. 次のステップに進むために投票します。

• VRF を通じて資格を再度計算し (current_round_number プラス 1 と現在の投票タイプを取り込む)、別の (e, π) を生成します。

• 「e < しきい値の場合、このラウンドの対象となる」を決定します。

• 2 ラムダを待ちます

• 特定の PC が 2T+1 票を獲得したかどうかを計算します

• 優勝した PC が正しく作成されたことを確認する

• 最新の検証済み PC を計算し、結果を永続ストレージにコミットします

• 最初のレベルのタイトル

当社の PBFT についてさらに詳しくご紹介します

上に書いてあるのは極めて簡単な説明です

文章

この PBFT プロセスは安全性と拡張性が非常に高いです

ノードが発言を希望するたびに、VRF 適格値を計算して、そのラウンドで発言する資格があることを確認することに注意してください。資格のしきい値は、次の 2 つのことを保証するために設定され、動的に調整されます。

各ラウンドに参加するノードはランダムであり、異なる可能性があります。つまり、攻撃者がノードを参加者として観察してターゲットにすると、次のラウンドでは失格になる可能性があります。これは、参加者 (または委員会のメンバー) を長期間拘束し、攻撃の主なターゲットにする他の多くのアルゴリズムとは異なります。

どのラウンドでも、参加資格のあるノードの一部のみが参加するため、この PBFT プロセスは非常にスケーラブルになります。これは、ネットワーク容量が拡大し、資格のある参加者の数が増加した場合でも、ネットワーク容量に対するこれらの PBFT ラウンドの実際の参加者 (委員会のサイズ) を、線形未満の拡張を達成するように簡単に設定できることを意味します。参加者の数が少ないほど、投票プロセスは速くなります。

最初のレベルのタイトル

並列 PBFT チェーン

Taraxa の PBFT プロセスは、既存のブロックの DAG と並んで PBFT ブロックの線形チェーンを作成します。

すべての PBFT ブロックには 2 つの主な目標があります。

• 周期ブロック内の DAG ブロックのファイナライズを完了する

• 最初のレベルのタイトル

DAG ブロックの完了の完了

この PBFT プロセスでは、ブロック DAG 内の単一ブロックを確認します。したがって、PBFT プロセスを利用する他のほとんどのネットワークとは異なり、ブロックチェーン プロセス全体をチェックするための主要なコンセンサス アルゴリズムとしては機能しません。これが、Taraxa の PBFT プロセスがブロック DAG 作成プロセスと並行しており、ほとんどが非同期である理由です。

新しい DAG ブロックが完成するたびに、完成したアンカー チェーンと、アンカー チェーン上に関連するブロックのセットが作成されます (各アンカー ブロックのエポックに沿って実装されます)。ブロック全体のコレクションはピリオドと呼ばれ、最終的にソートされたブロックのクラスターのスナップショットとみなすこともできます。

最初のレベルのタイトル

同時スケジュール

同時スケジュールでは、次の方法で順序が決定されます。

• ブロックの順序付け。これは、サイクル内に多くのブロックがあるため、順序付けメカニズムによって定義されます。

• ブロック間の冗長なトランザクションをフィルターで除外します。 DAG データ構造を使用しているため、複数のブロック プロポーザーが同じトランザクション セットを異なる DAG ブロックにパッケージ化する可能性が非常に高く、その結果、ある程度のトランザクションの重複が生じます。 Taraxa は、この重複を調整するために、トランザクション調停メカニズム (後の記事で詳しく紹介します) を設計しました。この状況を最小限に抑えることを望んでいますが、ゼロではありません。そうしないと、トランザクションが過度に分離されてしまいます。

• トランザクションを同時セットと順次セットに分割します。

• これは同時 EVM 設計 (後の記事で紹介します) の重要な部分であり、一連の投機的実行アルゴリズムを使用して、トランザクションを安全に並行して実行できるトランザクションと順次実行する必要があるトランザクションに分割します。 。

  同時スケジューリングは、個々の DAG ブロックをすべて 1 つのブロックに結合し、各 PBFT ブロックを埋め込んだ結果であると考えることもできます。

コンセンサスに加えて、私たちは研究と実装の過程でさらに興味深いテクノロジーを共有し、リリースし続けます。

乞うご期待！