技術共有: 安全かつ公正なブロック Dag ソーティング

序文

序文

前回の記事では、DAG トポロジで発生する可能性のある問題は、ブロックと転送の順序を定義することであると説明しました。この投稿では、ブロック DAG での順序付けを保証するだけでなく、順序付けプロセスが安全かつ公平であることも保証する Taraxa のメカニズムについて説明します。

仕分けが難しいのはなぜですか?

ブロック DAG での並べ替えの何がそんなに難しいのでしょうか?

DAG データ構造だけを見ると、部分的な順序付けしか確立できません。つまり、すべてのブロックではなく、一部のブロック間の順序関係のみを決定できます。ここに一例を示します。

上の画像では、ソートでは青いブロックが緑とオレンジのブロックよりも確実に前に来ると 100% の確信を持って言えます。なぜ？緑とオレンジのブロックは青のブロックを指しているので、オレンジと緑のブロックが作成されたときには青のブロックがすでに存在しており、そうでない場合、オレンジと緑のブロックはそれを指すことを知りません。

しかし、緑のブロックとオレンジのブロックの間の順序関係はどうやって知ることができるのでしょうか?この質問に対する明確な答えはありません。答えは使用される並べ替えアルゴリズムの種類によって異なり、アルゴリズムが異なると順序がまったく異なる場合があります。

ランキングのプロセスでは、1 つの自由度を保持するだけでなく、不正な参加者が多数派に偏らないようにする必要があるため、ランキング アルゴリズムが公平かつ安全であることを保証するために多くの選択を行う必要があります。正直なネットワーク参加者や攻撃の可能性があります。

ここで、Taraxa によって設計された Block DAG のソート アルゴリズムを見て、これらの問題をどのように解決できるかを見てみましょう。

人気コンテスト

Taraxa のブロック DAG トポロジでは、各ブロックには、単一の親ブロック (シングルチェーン トポロジの場合と同様) だけでなく、ブロック提案者が見て信じたことも指す逆方向ポインターが含まれています。 DAG 境界 (エッジ) 上のすべてのブロック。ここには多くの概念があります。1 つずつ紐解いてみましょう。

境界とは何ですか?ブロック DAG (または任意の DAG データ構造) では、フロンティアは、他のブロックが指していない最新のブロックのセットを指します。

上の画像では、青いブロックが「境界」ブロックですが、残りのブロックは境界ブロックではありません。フロンティアブロックチェーンが興味深いのは、これらのブロックがすべてのブロックのベースであり、ブロック提案者 (ブロック作成者に類似) によって作成された他のブロックがそれらの後に順序付けされるためです。ある観点から見ると、次の新しいブロックは間違いなくこれらのブロックを参照します。ただし、各ノードが異なるネットワーク伝播遅延を経験し、特定のブロックに遭遇したときに完全に異なる状況が発生するため、すべてのノードが同じ境界 (または同じブロック DAG) を認識するわけではありません。したがって、ブロック提案者は、いつでも異なる境界に基づいてブロックを作成することができます。

ポインターまたは親ブロックとは何ですか?図の矢印で表されているポインタは、別のブロックを「指す」か参照する、ブロック内に埋め込まれたデータです。 Taraxa の DAG ブロック構造では、ポインターは親ブロック セットを指します。親ブロックはポインタが指すブロックであるため、前のブロックの親として理解できます。

上の画像では、青いブロックには、緑のブロックで表される 2 つの親ブロックへの 2 つのポインターがあることがわかります。これは、提案者が青色のブロックを作成するとき、提案者はブロック DAG 境界上の 2 つのブロックを認識しており、これら 2 つのブロックが有効であると見なすため、作成された青色のブロックがそれらの両方を指すことを意味します。

これらのポインターがブロックを接続するプロセスは、実質的には人気コンテストです。単純に、どのブロックが最も多くのブロックによって指し示され、有効であるとみなされるかということです。さらに、特定のブロックを指すブロック自体が「人気」がある場合 (他の多くのブロックがそのブロックを指すことを意味します)、その「人気」はその特定のブロック (親ブロック) にも引き継がれます。

それでは、各ブロックの人気を測定してみましょう。

体重 - 人気スコア

各近隣の人気を測定するために、Zohar と Sompolinsky によって提案された GHOST プロトコルを採用します。 GHOST は、ブロック DAG に埋め込まれたポインターに基づいて各ブロックの重み (各ブロックの「人気度」) を計算するのに役立ちます。

「重さ」とは何ですか？ブロック DAG が横に回転されている場合、各子ブロックとその子孫は親ブロックから分離されていると考えることができるため、GHOST の下にあるブロックの重みは、ブロックとそのすべての子孫の重みの合計になります。

重みは、たとえこの取り組みが調整されておらず、複数の子孫に分散している場合でも、そのブロックの上に他のブロックを徐々に構築しようとするすべての試みの集合的な取り組みを表します。

>GHOST プロトコルは非常にシンプルで、

>各ブロック自体の重みは当然 1 です。

>各ブロックの重みは、それ自体の重み (1) に、それを指すすべてのブロックの重みを加えたものになります。

DAG ブロックの境界から開始して逆方向に測定します

ここに一例を示します。

境界ブロックから始めて、各ブロックに重みを割り当てることができます。青いブロックは DAG の境界にあり、それを指すブロックがないため、重みは 1 です。緑のブロックには、それを指すブロックが 1 つだけ (青のブロック) あるため、緑のブロック自体のブロックの重み (1) とその重みを指すブロック (1) を加算すると、2 が得られます。これが緑の新しい重みです。ブロック。さらに進むと、オレンジ色のブロックは 3 つのブロックを指しているため、その重みは 3 つのブロックの重みに自身の重み 1 を加えた合計になります: 5+20+12+1=38。

良さそうですが、なぜ重量で並べ替えることができないのでしょうか?まあ、完全ではありません。この単純な戦略には非常に微妙な問題がいくつかあるので、さらに調査してみましょう。

順序を混同する方法

ソートメカニズムの論理的基盤として重み値を使用するだけでは十分ではない理由を理解するために、簡単な例を見てみましょう。

上の画像では、シナリオ (a) から始めます。

(a) オレンジ色のブロックが 2 つあり、どちらも重み値が 1 であるため、順序があいまいであることがわかります。

(b) 前の 2 つのブロックを指す別のブロックが追加されますが、両方の重み値は 2 であり、順序はまだあいまいです。

(c) さらにいくつかのブロックを追加しても、オレンジ色のブロックの問題は解決せず、重さは依然として同じです。それだけでなく、さらに悪いことに、黄色のブロックの順序があいまいになるという新たな問題が生じています。

上の例では、全員が正直であると仮定していますが、それでも問題が発生する可能性があります。悪意のあるプレーヤーを導入した場合はどうなりますか? そのプレーヤーは、ブロック DAG 構造上の順序を積極的に難読化することができます。以下に例を見てみましょう。

この例では、(b) から始めます。

(b) 順序があいまいなオレンジ色のブロックが 2 つあります。

(d) 別のブロックが登場して問題が解決され、明確な順序が決まりました。長生きしてください！

(e) しかし、長くは続きません...悪意のあるプレイヤーは積極的にあいまいな順序を維持しようとして、境界ブロックと重みを以前の状態に戻すブロック (赤) を作成します。問題は、2 つのオレンジ色のブロックが再び発生します。秩序が整っていない。

この攻撃のもう 1 つの意味は、悪意のあるプレイヤーがあいまいな順序を維持するだけでなく、ブロックを追加する前後で順序を切り替えて、ネットワークを継続的な混乱状態に置く可能性があることです。

これらは非常に単純な例ですが、このような問題は、ブロックのクラスター全体が不定の順序状態のままになる、より大規模な場合に発生する可能性があります。

では、この問題をどのように解決すればよいのでしょうか? 次に、アンカー チェーンとゴースト ポインターの概念を紹介します。

アンカーチェーン - 最も人気のあるルート

重みを計算した後の次のステップは、ブロック DAG 内のアンカー チェーンを決定することです。重みが各ブロックの人気スコアである場合、アンカー チェーンはブロック DAG を通過する最も人気のあるパスになります。パスを横断 (歩行) しているときに観察されるブロックも、ネットワークによって広く (非常に一般的に) 観察されます。

アンカー チェーンを構築する方法は? 簡単です! 開始点を選択するだけです (または、Taraxa の場合は、リアルタイム ファイナリティを持つ前のブロック (リアルタイム ファイナリティに関する記事は近日公開予定))。のブロックごとに、各ステップで最も高い重みを持つブロックが選択されます。ここに例を示します。

上の図では、ブロック G から開始して前に進むと、選択できる 3 つの重み付きブロック (381、765、381) があり、その中で最も重いブロックは 765 です。このロジックに従ってこの方向に進み続けると、G ブロックから終点までのパスが構築されたアンカー チェーン (緑色) になります。

これがアンカー チェーンの生成方法であり、ブロック DAG をパスに「固定」し、そこから並べ替えアルゴリズムを構築できるようになります。

アンカー チェーンを計算するこの方法では、各尖ったブロックの重みが同じになるという問題は解決されますが、攻撃者が依然としてアンカー チェーンを変更し続ける可能性があるため (あまり早く収束しない)、別の問題が発生します。そこで、ネットワークがより速く固定アンカー チェーンに収束できるようにゴースト ポインタを導入し、決定的な順序付けを実現します。

すべてのポインターが同じように作成されるわけではありません

ネットワークの混乱をさらに防ぐために、ゴースト ポインターと呼ばれる特別なポインターを導入します。基本的な考え方は、各ブロックが作成されるときに、そのブロックが正当なものであると確認および検証した境界上のすべてのブロックを指すということですが、そのようなブロックは特別です。

特別なブロックはアンカー チェーンの終端ブロックです。ブロック DAG の境界上にある他の正当なブロックの存在を認識することに加えて、新しく追加された各ブロックは終端ブロックのゴースト ポインタも指します。ここでの重要な変更点は、ブロック重みの計算ではゴースト ポインタが指すブロックのみが考慮され、他のポインタが指すブロックは考慮されないことです。

親ブロックは、それを指す特別なゴースト ポインターのみを持つブロックになります。 Taraxa ブロック DAG 構造では、各ブロックは 1 つの親ブロックのみを指します。他のブロックは、単にブロック ツリーの他のブロック (原文では葉がブロックとして理解できます) を観察するか、または「祖先」 (イーサリアムでは「アンクル」または「オマー」と呼ばれます) を観察します。これについては前述したこともありますが、ブロックが持つことができる親の数について非常に明確に示すこともできます。

これにより、DAG グラフで表される暗黙的な投票プロセス中に、境界上のすべてのブロックがあいまいな形式で表示されないようにする方法という基本的な問題が解決されます。

>例を簡単に見てみましょう。

>太い矢印はゴースト ポインタ (計算された重み)

細い矢印は確認ポインターです (ウェイトなし)

(a) 2 つのブロック (1.1 と 1.2) は最初のジェネシス ブロック (0) を指します。親ブロックが 1 つだけ存在し、両方のブロックがそれを指すため、太線はゴースト ポインターです。順序は現時点では曖昧ですが、(1.1) が勝ち、将来のブロックのゴースト ポインターの候補とみなされると仮定すると、比較に最も低いハッシュを使用できます。

(b) 3 つのブロックが追加されますが、ネットワーク遅延のため、これらのブロックすべてがすべての新しいブロックを同時に認識できるわけではありません。これは、一部のノードがいくつかのブロックをより速く認識できることを意味します。たとえば、物理的距離が近いためネットワーク ホップが少なくなると、ノードがブロックを認識する速度が速くなります。ブロック (2.1) とブロック (2.2) はどちらも前の 2 つのブロック (1.1 と 1.2) を認識しているため、どちらもゴースト ポインターをこれら 2 つのブロックに指し、(1.1) が終端ブロックのアンカー チェーン上にあることを正直に識別します。ただし、(2.3) は (1.1) を認識しないため、(1.2) を指すためにゴースト ポインタを使用することしかできず、他には何もできません。私たちのルールに従って、ブロックの重みは更新されていますが、ゴースト ポインタを使用してブロックを指しているサブブロックの部分だけがカウントされることに注意してください。

(c) 次の層のブロックが出現し、(3.1) ブロックは (2.1) と (2.2) ブロックを同時に認識し、(3.2) ブロックは (2.1) と (2.3) ブロックを同時に認識します。時刻、ブロック (3.3) はブロック (2.1、2.2、および 2.3) を同時に切断しました。起動時に、各ブロックは、表示されるアンカー チェーン上の終端ブロックを選択し、そのゴースト ポインタをそこにポイントし、続行します。

ゴースト ポインターは、アンカー チェーンと併せて、ネットワークを強制的にアンカー チェーンに収束させ、全体の順序を安定させるのに役立ちます。次に、ブロックがアンカー チェーンに基づいて最終的にどのように順序付けされるかを説明します。

アンカーで並べ替え

ゴースト ポインターを使用して、前のブロック DAG の例の重みを再計算してみましょう。ゴースト ポインタが指すブロックのみがその重みを計算して親ブロックに組み込むことにもう一度注意してください。

アンカー チェーンが描画されたら、アンカー チェーン上の各ブロック (アンカー ブロック) の周囲にエポックを構築します。エポックは、アンカー ブロックが観察できるブロックの数、またはアンカー ブロックが直接的または間接的に指すブロックの数です。非常に人気のあるアンカー ブロックの友達と考えてください。

上の図では、赤い点線を使用して各アンカー ブロック エポックをプロットしています。残念ながら、ウェイト 25 の最初のアンカー ブロックはエポック自身のみです。重み 21 の次のアンカー ブロックには、それ自体と、それが観察できる重み 1 の他の 2 つのブロックを含む、epoc があります。 3 番目のアンカー ブロックの重みは 18 で、アンカー ブロックは 1 つだけ観察できます。次のブロックの重みは 17、エポックは 3 です。これには、直接観測できる重み 1 のブロックと、間接的に観測できる重み 2 の別のブロックが含まれます。このようにして、各アンカー ブロックのエポックが描画されるまで微分を続けます。

これで、ブロックを並べ替える準備ができました! ブロックは、まずエポック順に古いものから新しいもの (左から右) に並べられます。各エポックでは、重み値を使用して、どのブロックがどのブロックを指しているかを調べて、どのブロックが最初に来るかを決定します。または、この方法が失敗した場合は、アンカーブロックと同じ距離のブロックの判定方法としてブロックハッシュを使用します。

エポックグラフを見ると、Gが最初の(1)です。次のエポックにはブロックが 1 つだけあるため、重み 25 のこのブロックが 2 番目のブロック (2) になります。次のエポックに移動すると、重み値 1 の 2 つのブロックが重み 21 のアンカー ブロックの前にあります (重み 21 のブロックを指しているため)。これら 2 つのブロックを比較する方法は、どちらのハッシュかを比較することです。 (3)と(4)を決定すると、5番目のブロック(5)は重み値が21のブロックになります。すべてのエポックのすべてのブロックがソートされるまで作業を続けます。

以下に示すように、各ブロックの数字は重みではなく順序を示します。

ついに終わりました！

しかし、本当に終わったのでしょうか? 並べ替えられなかったブロックはどうなるのでしょうか?epochブロック DAG 構造の境界近くには、アンカー チェーンに属さないいくつかのブロックが常に存在します。

の一部。ただし、境界にブロックが追加されると、最終的には境界に含まれるようになるので、心配しないでください。

アンカー チェーン (および結果として生じる順序) は時間の経過とともに変化しませんか?はい! ブロック DAG 構造内で順序が変更されるリスクがあります。このリスクは時間の経過とともに指数関数的に減少しますが、完全に排除されることはありません。そのため、Taraxa はリアルタイムのファイナリティ プロセスを実装する必要があります (記事は近日公開予定)。

真のリアルタイム ファイナリティは、並べ替えのリスクなしでブロック DAG 構造に導入され、ネットワーク内で DApp を構築するための基礎となります。