作業証明を使用せずに公平かつ効率的に行う方法
序文
序文
副題
捕虜の美しさ
Pow は、シンプルでエレガントなコンセンサス アルゴリズムです。各ノードは単純な暗号化パズルを解き、素早い推測によって解決策が得られ、最初に正しく推測した人が次のブロックの生成に選択されます。
それはとても簡単です。
この単純なアルゴリズムは、公平で分散型のブロック提案のための真のランダム性、フォークの確率を最小限に抑えてブロードキャストするのに十分な時間を確保するための一定の遅延、マイナーが正直に働くことへの既得権益。
副題
画像の説明
初期の組立ラインは並行して作業
シンプルでエレガントな PoW メカニズムの重要な問題は、その難しい問題を高度な並列処理で処理できることです。これらのパズルは通常ハッシュ関数であり、ノードはランダムな文字列を生成し続け、それらをハッシュし、結果のハッシュが特定の基準に一致するかどうかを確認します。あなたが単なるプレイヤー (例: マシン、スレッド) である場合、平均 N 秒後に答えを正しく推測できると仮定します。しかし、プレイヤーが 100 人いる場合、作業を簡単に分散できるため、正解を推測するのにかかる平均時間は N/100 秒になります。たとえば、合計 M 通りの答えがある場合、プレイヤー 1 が答え 1 をテストして M/100 になるように配置し、次にプレイヤー 2 が答え M/100 をテストして M/200 になるように配置する、というようにすることができます。
PoW ブロックチェーン システムで作業するマイナーは通常、多数の専用コンピューターまたは特定用途向け集積回路 (ASIC) を購入し、これらの ASIC の分業を調整するプログラムを呼び出して答えを推測します。彼らは、正解の方が速いだろうと推測します。時間が経つにつれて、さまざまなマイナーがチームを組んで ASIC グループの作業を共有することを決定し、それがマイニング プールになります。
ビットコインのようなネットワークでは、マイナーが答えを推測するのが早すぎる場合、答えを推測する難易度を高め、最終的にブロック生成時間を平均約 10 分に維持できる一連の内部アルゴリズムがあります。したがって、マイナーが推測する速度が速ければ速いほど、パズルは難しくなり、マイナーはスピードアップしたり、ASIC を通じてより多くの ASIC を構築したりするようになります。
マイニング マシンは高速かつ多数になり、ますます多くのエネルギーを消費するようになり、ネットワークを維持するためのエネルギー消費量が途方もなく高くなるまでになっています。
副題
設計目標: ランダムなレイテンシ
したがって、PoW ほどリソースを無駄にせず、同時にランダムな遅延を実現できるシステムを設計したい場合は、次の設計目標を達成する必要があります。
公平性と分散化を確保するための真のランダム性
エネルギー消費を最小限に抑えるために並列処理によってレイテンシを短縮することはできません
最適化する方法を見てみましょう。
画像の説明
ホワイト ノイズは自然に発生するランダム性の原因です
真のランダム性はむしろ哲学的な問題です。私たちが「ランダム」と言うとき、実際に意味するのは「予測できない」ということです。私たちのメカニズムの結果がネットワークの参加者によって予測できない場合、その結果はランダムで公平であると考えられます。
ハッシュ関数や署名メカニズムなど、多くの暗号関数はランダムな出力を生成するようです。ただし、予測不可能な出力を生成するように特別に設計されているわけではないため、観察者は十分な数のサンプルが与えられればパターンを推測できます。
1999 年に、非常に予測不可能な出力を生成するように特別に設計された検証可能なランダム関数 (VRF) について説明した Micali、Rabin、Vadhan による論文が発表されました。その後、ミカリ教授はアルゴランド プロジェクトを設立し、その後、プロジェクトの中心メンバーであるセルゲイ ゴルブノフがより詳細でわかりやすい記事を書きました。 VRF のより技術的な扱いに興味がある場合は、上記の記事や論文を参照してください。
Taraxa のブロック DAG アーキテクチャでは、VRF はランダムな遅延に対してランダム性を提供します。 VRF の出力は次のとおりです。
ブロック DAG レベル (L): 提案者がブロックをパッケージ化するとき、ここでの「レベル」はアンカー チェーンの長さ + 1 です。したがって、あなたが提案者の場合、現在のアンカー チェーン L を計算し、ゴースト ポインター (ポインター) を構築する境界上の最後のブロックを見つけます。その場合、提案するブロック レベルは L+1 になります。ここでの定義は、よく言われる「深さ」とは異なる概念であることに注意してください。
最新の Period ブロックのブロック ハッシュ (P): これは、ブロック DAG 内の最新の完了したブロックであり、並列 PBFT プロセスを通じて真の最終確認を達成できます (次の記事で詳しく説明します)。提案者が境界上で最新の確認済みの Period ブロック (P) を受信していないことを考慮すると、プロトコルには一定の許容範囲があり、最新の Period ブロックの前のブロック ハッシュも許容されます。
ブロック提案者の秘密 VRF キー (SK): これは VRF 機能を構築するために必要です。これは、VRF を構築するために各ノードに対して特別に生成されるトランザクション署名メカニズムとは異なります。
VRF 関数の出力は 2 つの部分に分かれています。
v は、遅延の長さを決定するために使用される擬似ランダム値です。
p は、他のノードが VRF が正直かつ正しく実行されたことを検証するために使用できる証明です。これは署名と見なすことができ、提案者の VRF 公開キーを使用すると、他のノードは計算の正しさを簡単に判断できます。
最終的には、次のような簡単な方程式を書くことができます。
VRF(L, P, SK) → (v, p)
■遅延難易度シェーピング機能
VRF の出力 (遅延の難易度または遅延の長さ) を遅延に変換するには、それを特定の分布にする必要があります。分布の特徴は大まかに以下のとおりです。
適切なネットワーク ブロードキャストの時間がなければ、すぐにブロックを生成できないため、遅延は最小限にする必要があります。
ネットワーク全体が輻輳することは望ましくないし、ブロックが長時間生成されることも望まないため、最大の遅延が必要です。
一部のプロポーザーは高速ですが、残りは低速です。これは、適格なプロポーザーの数とネットワーク全体の直径 (つまり、ブロックが提案されたノードのほとんどに到達するのに必要な時間) に関係します。
画像の説明
整形機能
type 関数を S とすると、次の式が得られます。
S(v) = d
ここで d は次のステージの難易度係数です。
■ 検証可能な遅延関数のレイテンシ
トークンはバス カードのようなもので、それ自体で価値の移転を生成できますが、アライアンス チェーンにはネイティブの価値の移転がありません。国はねずみ講を取り締まっているが、実はまだまだ価値あるトークンが多く存在し、業界が発展し、社会にある程度認知されれば、質の高いパブリックチェーンがあれば画一的な状況は回避できるだろう。この時点までに、アライアンス チェーンとパブリック チェーン間の協力がさらに進む可能性があります。
一人で頑張っているのに、一緒に戦っている人はいない =(
この記事の冒頭で説明したように、PoW は優れていますが、並列処理がその「犠牲者主義」の元凶です。そこで、並列処理では加速できない遅延をシミュレートするために特別に設計された Verifiable Delay Functions (VDF) が登場しました。
関数は、次の 2 つの単純な基準を満たしている場合、厳密に VDF として分類できます。
連続的でなければなりません、この場合、PoW とは異なり、複数の並列処理を通じて VDF 関数の計算を高速化することは誰にもできません。
簡単に検証可能である必要があり、オブザーバーは、VDF の計算が正しく、適切な遅延が発生していることを確認するために簡単に検証できます (つまり、検証にかかる時間は関数の計算にかかる時間よりもはるかに短くなります)。これは PoW と同様です。
Boneh ら、Pietrzak、Wesolowski らはいずれも、これらの基準を満たす VDF を提案しました。特に、Pietrzak と Wesolowski はどちらも独立して、未知の次数のグループで二乗を繰り返す原理に基づいた非常に類似した方法を提案しました。これは並列処理に対して効果的です。
数学は非常に複雑なので、これらの関数をより高いレベルでテストしてみましょう。
これらの VDF は、各反復で前の反復からの入力が必要であり、特定の反復では将来の反復に関する情報が利用できないため、並列処理できない繰り返し二乗計算を実行するように構築されています。言い換えれば、すべての反復を実行するまで答えはわかりません。これにより、関数が確実にシーケンシャルであることが保証されます。
VDF の検証が容易になるのは、VDF の中間入力と最終出力のランダムな線形結合を使用して証明を構築できることです。これらの限定された線形結合の計算は、VDF 全体を計算するよりもはるかに少ないステップで済むため、簡単です。簡単に例えると、曲線全体のすべての値を計算する (VDF 全体を計算する) ことと、矢印を選択して数ステップ進める (VDF の有効性を証明する) ことの違いです。矢印が数ステップ進むのにかかる時間は、明らかに計算時間よりもはるかに短くなります。これにより、関数を簡単に検証できるようになります。
Taraxa では、VDF に次の入力項目を設定します。
親ハッシュ (gP)、または新しく作成したブロックがゴースト ポインターを介して指す親ブロック
すべてのトランザクションのハッシュ (Tx)、ブロックに含める予定のすべてのトランザクションのハッシュ。事前に VDF を計算することはできません。
d、前のステップの難易度係数
したがって、ノードがブロックを提案する前の VDF 関数の計算は次のようになります。
VDF(gP, Tx, d) = z
実際には、出力 z の検証が非対話型であることを保証するために、ノード提案者は、提案されたブロックに最終出力だけでなく中間証明も挿入する必要があります。
画像の説明
説明のために、これは一様分布から生成されています。
この記事の執筆時点では、VDF はまだ非常に実験的なテクノロジーであり、活発な研究とテストが行われています。 Taraxa は、オープンソース分野の優秀な人々や学術コミュニティと協力して、当社の台帳が最も安定した、効率的で安全なソリューションを確実に採用できるようにします。
