Vitalik: 暗号学、コンセンサス理論、経済学の進歩に関するレビュー
2014 年に、私は仮想通貨 (当時そう呼んでいました) の分野が進む方向に重要だと考えた、数学、コンピューター サイエンス、経済学の難しい問題のいくつかをリストアップした記事を発表し、講演しました。重要。過去 5 年間で多くのことが変わりました。しかし、当時重要だと考えていたことについて、私たちはどれだけ進歩しましたか? どこで成功し、どこで失敗し、どこで何が重要なのかについて考えを変えましたか? このエッセイでは、私たちは次のことを振り返ります。 2014 年からの 16 の問題を 1 つずつ取り上げて、今日のそれぞれの課題がどこまで進んでいるかを確認してください。最後に、2019 年のパズルの新しいピックを決めます。
これらの問題は、次の 3 つのカテゴリに分類できます。
したがって、解決できる場合は、純粋に数学的手法を使用して解決する必要があります。
コンセンサス理論。プルーフ・オブ・ワークとプルーフ・オブ・ステークを大幅に改善します。
経済的には、さまざまなアクターにインセンティブを与える構造を作成する必要があり、これにはプロトコル層ではなくアプリケーション層が関与することがよくあります。
最初のレベルのタイトル
副題
ブロックチェーンのスケーラビリティ
今日の暗号通貨スペースが直面している最大の問題の 1 つは、スケーラビリティの問題です。[非常に大規模なブロックチェーン] の主な問題は信頼です。少数のエンティティのみがフル ノードを実行できる場合、それらのエンティティは共謀して同意する可能性があります。他のユーザーは、ブロック全体を自分で処理しない限り、ブロックが無効であることを自分の目で確認することはできません。
問題: ビットコインのようなセキュリティ保証を維持するブロックチェーン設計を作成しますが、ネットワークの実行を継続するために必要な最も強力なノードの最大サイズは本質的にトランザクション数に対して線形以下です。
ステータス: 理論的には大きな進歩があり、さらなる現実世界での評価が待たれます。
スケーラビリティは技術的な問題ですが、理論的には大きな進歩を遂げました。 5 年前にはシャーディングについて考える人はほとんどいませんでしたが、現在ではシャーディング設計が一般的になっています。 Ethereum 2.0以外にもOmniLedger、LazyLedger、Zilliqaがあり、毎月研究論文が出ているようです。私の意見では、現時点でのさらなる開発は漸進的です。基本的に、コンセンサスがあればバリデーターのグループが単一のバリデーターよりも多くのデータを安全に処理できるようにする技術や、クライアントがブロックテクノロジーの完全な有効性と可用性を間接的に検証できるようにする技術をすでに多数持っています。攻撃力51%。
おそらく最も重要なテクノロジーは次のとおりです。
ランダム サンプリング。ランダムに選択された小さな委員会がバリデーターの完全なセットを統計的に代表できるようにします: https://github.com/ethereum/wiki/wiki/Sharding-FAQ#how-can-we-solve-the-single-調整されていない多数派モデルでのシャード乗っ取り攻撃
不正行為の証明。障害を認識した単一ノードがその存在を他のすべてのノードに伝播できるようにします: https://bitcoin.stackexchange.com/questions/49647/what-is-a-fraud-proof
Proof of Custody により、検証者が一部のデータを個別にダウンロードして検証したことを確率的に証明できるようになります: https://ethresear.ch/t/1-bit-aggregation-Friendly-custody-bonds/2236
データの可用性の証明。ヘッダーが存在するブロック本体が利用できないかどうかをクライアントが検出できるようにします: https://arxiv.org/abs/1809.09044。更新されたマークル ツリー エンコーディングの提案を参照してください。
他にも、レシートを介したクロスシャード通信のような小規模な開発や、BLS 署名集約のような「定数要素」の機能強化があります。
タイムスタンプ
タイムスタンプ
問題: ブロックチェーン上のオーバーレイであっても、独自のブロックチェーンであっても、現在時刻を高精度に維持する分散インセンティブ対応システムを作成する。すべての正当なユーザーの時計は、通常、標準偏差 20 秒の「真の」時刻付近に分布しています。 2 つのノードの間隔が 20 秒を超えることはありません。
このソリューションでは、「N ノード」という既存の概念に依存することができます。実際には、これはプルーフ オブ ステークまたは非 Sybil トークンを通じて実装されます。システムは 120 秒未満 (可能であればそれより短く) 配信を継続し、正直な参加ノードの >99% の内部クロック内に収まるようにする必要があります。外部システムは最終的にこのシステムに依存する可能性があるため、動機に関係なく、ノードの 25% 未満を制御する攻撃者からこのシステムを安全に保つ必要があります。
ステータス: ある程度進んでいます。
実際、イーサリアムは 13 秒のブロック時間で十分に存続しており、特に高度なタイムスタンプ技術はありません。クライアントがクライアントのローカル時間でのブロックよりも古い宣言されたタイムスタンプを受け入れないという単純な技術を使用しています。ただし、これは深刻な攻撃では検証されていません。最近のネットワーク調整されたタイムスタンプの提案は、クライアントが現在時刻を高精度に知ることができない場合に、クライアントのコンセンサスによって時刻を決定できるようにすることで現状を改善しようとしていますが、これはテストされていません。
最初のレベルのタイトル
任意の計算の証明
問題: 問題: POC_PROVE が入力 I でプログラム P を実行し、プログラム出力 O とを返すようなプログラム POC_PROVE(P,I) -> (O,Q) および POC_VERIFY(P,O,Q) -> { 0, 1 } を作成します。 a Q と POC_VERIFY が P、O、Q を取得することを計算して証明し、P を使用して POC_PROVE アルゴリズムによって Q と O が正当に生成されるかどうかを出力します。
現状: 理論と実践の両方で大きな進歩が見られました。
これは基本的に、SNARK (または STARK、SHARK、または…) を構築することを意味します。やった! SNARK は現在、ますます理解されており、複数のブロックチェーン (イーサリアムの tornado.cash を含む) で使用されています。 SNARK は、プライバシー テクノロジ (Zcash および tornado.cash を参照) としても、スケーラビリティ テクノロジ (ZK Rollup、STARDEX、および STARKing Erasure Coded Data Roots を参照) としても非常に便利です。
副題
コードの難読化
聖杯は、任意のプログラム P が与えられた場合に、難読化ツールが 2 番目のプログラム O(P) = Q を生成できるように難読化ツール O を作成し、同じ入力が与えられた場合、P と Q が同じ出力を返すようにすることです。重要です。はい、Q P の内部については何も示されていません。パスワードや秘密の暗号化キーを Q に隠すことも、Q を単にアルゴリズム自体の独自の作業を隠すために使用することもできます。
ステータス: 進行が遅い。
簡単に言えば、問題は、暗号化されたプログラムが同じ入力に対して同じ出力を提供しながら、プログラムの「内部」が隠蔽されるように、プログラムを「暗号化」する方法を見つけたいということです。難読化の使用例としては、秘密キーを含むプログラムが挙げられます。このプログラムでは、秘密キーによる特定のメッセージの署名のみが許可されます。
コードの難読化に対するソリューションは、ブロックチェーン プロトコルにとって非常に役立ちます。チェーン上の難読化ツールがコピーされ、チェーン自体とは異なる環境で実行される可能性に対処する必要があるため、ユースケースはデリケートですが、可能性はたくさんあります。私が個人的に興味があるのは、オペレーターをプルーフオブワーク難読化プログラムに置き換えることによって、共謀防止ガジェットから集中オペレーターを削除することです。これにより、さまざまな入力を使用して複数の実行が可能になります。個々のアクターのアクションを決定するコストは非常に高くなります。高い。
副題
ハッシュベースの暗号化
問題: セキュリティの仮定に依存せず、代わりにハッシュのランダムなオラクル特性に依存し、古典的なコンピューターの最適なサイズやその他の特性に対して 160 ビットを安全に保つ署名アルゴリズムを作成します。
ステータス: ある程度の進捗。
2014 年以来、この方向に 2 つの進歩が見られました。 SPHINCS は「ステートレス」 (つまり、ナンスなどの情報を何度も使用するために記憶する必要がない) 署名スキームであり、この「難しい問題」リストの直後にリリースされ、純粋にハッシュベースの署名を提供します。サイズは約 41 KB のスキーム。さらに、同様のサイズの署名を作成できる STARK が開発されました。実際、署名だけでなく普遍的なゼロ知識証明もハッシュによって実装できるようになったのですが、これは 5 年前にはまったく予想していなかったことで、とても満足しています。そうは言っても、サイズは依然として問題であり、証明のサイズを縮小する進歩が続いています（最近の DEEP FRI など）が、さらなる進歩は段階的に行われるように見えます。
最初のレベルのタイトル
副題
ASIC耐性のプルーフ・オブ・ワーク
この問題を解決する 1 つの方法は、特化するのが非常に難しいタイプの計算に基づいて、プルーフ・オブ・ワーク アルゴリズムを作成することです。詳細については、https://blog.ethereum.org/2014/06/ を参照してください。 - ASIC 耐性ハードウェア 19/mining/ に関する詳細な議論。
状況：最善を尽くしました。
「困難な問題」リストが公開されてから約 6 か月後、イーサリアムは ASIC 耐性のあるプルーフ オブ ワーク アルゴリズムである Ethash に落ち着きました。 Ethash はメモリハードアルゴリズムとみなされます。一般的なコンピュータのランダム アクセス メモリはすでに十分に最適化されているため、特殊なアプリケーションでそれを改善するのは難しいという理論です。 Ethash の目標は、メモリ アクセスを PoW 計算の実行の主要部分にすることで、ASIC 耐性を実現することです。
Ethash は最初のメモリハード アルゴリズムではありませんが、革新性を追加しています。2 レベルの DAG で擬似ランダム ルックアップを使用し、関数を 2 つの方法で計算できるようにします。まず、DAG 全体 (約 2 GB) があれば、迅速に計算できます。これは、メモリを必要とする「高速パス」です。第 2 に、DAG の最上位層のみがある場合、計算ははるかに遅くなります (それでも個々の解を迅速にチェックできます)。これはブロックの検証に使用されます。
副題
有用な作業証明
Proof of Work を有用なものにする一方で、プロジェクト候補の 1 つは Folding@home です。これは、ユーザーがタンパク質の折り畳みをシミュレートするソフトウェアをコンピューターにダウンロードし、研究者に病気の治療に役立つ大量のデータを提供する既存のプログラムです。
ステータス: 1 つの例外を除いて、おそらく実現不可能です。
有用なプルーフ・オブ・ワークの課題は、プルーフ・オブ・ワークのアルゴリズムには多くのプロパティが必要であることです。
計算するのが難しい
簡単に検証できる
大量の外部データに依存しない
小さな「一口サイズ」のブロックで効率的に計算できます。
残念ながら、これらのプロパティをすべて保持する有用な計算はそれほど多くありません。また、これらのプロパティすべてで「役立つ」計算のほとんどは、それらを基にして暗号通貨を構築するには非常に短い時間のみ「役立つ」だけです。
ただし、ゼロ知識証明の生成という例外が 1 つあります。ブロックチェーンの有効性のゼロ知識証明 (データ可用性ルートなど) は計算が困難ですが、検証するのは簡単です。さらに、それらは常に計算が困難でした。「高度に構造化された」計算の証明が簡単になりすぎた場合は、仮想マシンとランダム メモリ アクセスをモデル化する必要があるため、ブロックチェーンの状態遷移全体の検証に簡単に切り替えることができます。非常に高価です。
賭け金の証拠
賭け金の証拠
マイニングの集中化の問題を解決する別の方法は、マイニングを完全に排除し、他のメカニズムを使用してコンセンサスの各ノードの重みを計算することです。議論の中で断然最も人気のある代替案は「プルーフ・オブ・ステーク」です。つまり、コンセンサス モデルを「1 単位の CPU パワー、1 票」として見るのではなく、「1 通貨単位、1 票」と見なします。
ステータス: 理論的には大きな進歩があり、さらなる現実世界での評価が待たれます。
2014 年の終わり頃、プルーフ オブ ステーク コミュニティは、ある種の「弱い主観」が避けられないことを明らかにしました。経済的安全性を維持するために、ノードは最初に同期するときに最新のチェックポイント追加合意を取得する必要があり、また、数か月以上オフラインになっている場合は、チェックポイント追加合意を再度取得する必要があります。これは飲み込むのが難しい薬です。PoW チェーンではチェーンの「先頭」が発見され、信頼できるソースからのデータはブロックチェーン クライアント ソフトウェア自体だけであるため、多くの PoW 支持者は依然として PoW に固執しています。しかし、PoS の支持者は、信頼要件の増加は重要ではないと信じているため、この薬を喜んで飲み込みます。それ以来、長期預金によるプルーフ・オブ・ステークへの道が明確になりました。
現在の興味深いコンセンサス アルゴリズムのほとんどは基本的に PBFT に似ていますが、固定のバリデーター セットを、誰でもシステム レベルのスマート コントラクト (時間ロックされた引き出し付き) にトークンを送信できる動的リストに置き換えます。この動的リストに参加してください。場合によっては、引き出しが完了するまでに最大 4 か月かかる場合があります）。多くの場合（イーサリアム 2.0 を含む）、これらのアルゴリズムは、プロトコルに違反するアクションを実行するバリデーターを特定の方法で罰することで「経済的目的」を達成します。
現在のところ、（他の多くのアルゴリズムの中でも）次のものが用意されています。
Casper FFG：https：//arxiv.org/abs/1710.09437
Tendermint：https：//tendermint.com/docs/spec/consensus/consensus.html
HotStuff：https：//arxiv.org/abs/1803.05069
Casper CBC：https：//vitalik.ca/general/2018/12/05/cbc_casper.html
副題
保管の証明
この問題を解決する 3 番目の方法は、コンピューティング能力や通貨以外の希少なコンピューティング リソースを使用することです。この点に関して、提案されている 2 つの主な代替案は、ストレージと帯域幅です。原則として、帯域幅が与えられた、または使用されたというイベント後の暗号証明を提供する方法はありません。そのため、帯域幅の証明は、後で説明するソーシャル証明のサブセットと考えるのが最も正確ですが、ストレージの証明は確かに計算可能です。 Proof of Storage の利点の 1 つは、完全に ASIC 耐性があることです。ハード ドライブ内のストレージはすでに最適に近い状態になっています。
現状: 多くの理論は進歩していますが、やるべきことはまだ多く、現実世界でのさらなる評価が必要です。
副題
経済的側面
価値が安定した暗号資産
ビットコインの大きな問題は価格の変動です。問題: 価格が安定した暗号資産を構築します。
ステータス: ある程度進んでいます。
MakerDAO は現在稼働しており、ほぼ 2 年間安定して実行されています。同社は原資産担保資産（ETH）の価値が93％下落しても生き残り、現在1億ドルを超えるDAIの残高を抱えている。これはイーサリアム エコシステムの主力となっており、多くのイーサリアム プロジェクトがそれに統合されているか、統合されています。 UMA などの他の合成トークン プロジェクトも急速に支持を集めています。
ただし、MakerDAO システムは 2019 年の厳しい経済情勢を乗り切りましたが、それは起こり得る最も厳しいシナリオではありませんでした。ビットコインは過去2日間で75％下落したが、将来的にはイーサリアムやその他の担保資産にも同じことが起こるだろう。基盤となるブロックチェーンへの攻撃は、特に同時に価格下落によってさらに悪化した場合、未検証のさらに大きなリスクとなります。
副題
分散型公共財インセンティブ
経済システム全般が直面する課題の一つに「公共財」の問題があります。たとえば、完了までに 100 万ドルかかる科学研究プロジェクトがあり、それが完了すると、研究結果によって 100 万人が 1 人あたり 5 ドル節約できることがわかっているとします。全体として、社会的利益があることは明らかです...[しかし]誰の観点から見ても、寄付は無意味です...
これまでのところ、公共財に関する問題のほとんどは中央集権化に関係しています。追加の前提条件と要件: 特定の公共財タスクが完了したかどうかを判断する、完全に信頼できるオラクルが存在します (実際にはこれは誤りですが、それは別の問題領域です)。
ステータス: ある程度進んでいます。
公共財への資金調達の問題は、一般に 2 つの問題に分けられると理解されています。資金調達問題 (公共財はどこから資金調達されるのか) と選好集計問題 (個人のペットではなく実際に公共財であるものをどのように判断するか) です。プロジェクト）。この質問は、後者が解決されていることを前提として、前者に特に焦点を当てています (この問題の取り組みについては、「分散型貢献メトリクス」セクションを参照してください)。
全体として、この分野では新たな大きな進歩はありません。主な解決策は 2 つあります。まず、個人の貢献に対して社会的な報酬を与えることで、個人の貢献を動機付けることができます。限界価格差別による慈善活動に対する私自身の提案はその一例であり、もう 1 つはピーペスの反マラリア寄付バッジです。第二に、ネットワーク効果を利用してアプリケーションから資金を集めることができます。ブロックチェーンの範囲内で、これを実行できるものがいくつかあります。
コインを発行する
プロトコル レベルでトランザクション手数料の一部を請求します (例: EIP 1559 経由)
一部のレイヤー 2 アプリケーション (たとえば、Uniswap、一部のスケーラブルなソリューション、またはイーサリアム 2.0 の実行環境のステート レントなど) から
その他の料金が適用されます (ENS 登録など)
副題
評判システム
問題: スコア rep(A,B) -> V (V は A の観点から見た B の評判)、ある当事者が別の当事者から信頼される確率を決定するメカニズム、および評判を更新するメカニズムから構成される正式な評判システムを設計します。特定の公開または最終的なインタラクションの記録が与えられる。
ステータス: 進行が遅い。
2014 年以降、評判システムに関する研究はあまり行われていません。おそらく、これを行うための最良の方法は、トークン エスクロー レジストリを使用して、信頼できるエンティティ/オブジェクトの保管リストを作成することです。Kleros ERC20 TCR (はい、これは正規の ERC20 トークンのレジストリです) がその一例であり、代替の Ninja さえあります。 Uniswap (http://uniswap.ninja) をバックエンドとして使用し、そこからトークン、トークンコード、および ID のリストを取得します。
副題
優秀さの証明
トークン配布問題には、興味深いがほとんど未開発の解決策があります (そのため、これを簡単にマイニングに使用することはできません)。これは、社会的には役立つものの、原始的な人間の創造的な努力と才能を必要とするタスクを使用します。たとえば、特定の定理の数学的証明を考え出したプレイヤーに報酬を与える「証明の証明」コインを考え出すことができます。
状況: 進展はなく、問題はほとんど忘れ去られています。
副題
アンチウィッチシステム
レピュテーション システムに関連する問題の 1 つは、「独自の ID システム」、つまり ID が Sybil 攻撃の一部ではないことを証明するトークンを生成するシステムを作成するという課題です。ただし、「1 ドルのシステム」よりも優れたシステムが存在することを願っています。投票」、より平等なシステムであり、おそらく、1 人 1 票が理想的でしょう。
ステータス: ある程度進んでいます。
かなり多くの人がこの人間特有の問題を解決しようと試みてきました。試してみたいことは次のとおりです (すべてを網羅しているわけではありません!)
HumanityDAO：https：//www.humanitydao.org/
Pseudonym parties：https：//bford.info/pub/net/sybil.pdf
POAP (「出席証明書プロトコル」): https://www.poap.xyz/
BrightID：https：//www.brightid.org/
副題
分散型貢献指標
残念ながら、公共財の生産を奨励することだけが中央集権化によって解決される問題ではありません。もう 1 つの問題は、第一に、どの公共財が生産する価値があるかを判断すること、第二に、ある種の努力が公共財の生産を実際に達成する程度を判断することである。この課題では後者の質問を扱います。
ステータス: 焦点が変わり、ある程度の進歩。
公益寄付の価値を決定する最近の研究では、タスクの決定と完了の質の決定を分離しようとはしていませんが、その理由は、この 2 つを実際に区別することが難しいためです。特定のチームによって行われる作業は多くの場合、かけがえのないものであり、十分に主観的なものであるため、最も合理的なアプローチは、タスクの関連性とパフォーマンスの品質を 1 つのパッケージとして考慮し、同じ手法を使用して両方を評価することです。
幸いなことに、特に二次補助金の発見により、この点に関しては多くの進歩が見られました。二次助成金では、個人がプロジェクトに寄付することができ、寄付者数と寄付金額に基づいて、数式を使用して、それらが互いに完全に一致した場合に寄付する金額 (つまり、いくら) を計算します。彼らは寄付しました）。お互いの利益を考慮し、コモンズの悲劇の餌食にならなかった）。
どのプロジェクトでも、寄付された可能性のある金額と実際に寄付された金額との差額が、中央の資金プールから補助金としてそのプロジェクトに与えられます。注意しなければならないのは、このメカニズムは、誰かがそれを気にするかどうかに関係なく、特定の目標を満たすのではなく、特定のコミュニティの価値観を満たすことに重点を置いているということです。値の問題は複雑であるため、このアプローチは未知の未知のものに対してより堅牢である可能性があります。
副題
分散型の成功指標
問題: 現実世界の数値変数を測定するための分散型手法を提案して実装します...システムは、現在人間が大まかな合意に達することができるもの (資産価格、気温、地球規模の CO2 濃度など) を測定できる必要があります。
ステータス: ある程度進んでいます。
これは現在、一般に「オラクル問題」と呼ばれています。分散型オラクルの既知の最大の実行インスタンスは Augur で、数百万ドルのステーキング結果を処理します。 Token の Kleros TCR などのトークン キュレーション レジストリも別の例です。ただし、これらのシステムでは、非常に物議を醸している問題または 51% 攻撃の試みのため、フォーク メカニズムの実際のテストはまだ行われていません。 「ピアツーピア予測」文献の形で、ブロックチェーン空間の外で発生するオラクル問題に関する研究もあります。
もう 1 つの差し迫った課題は、人々がこれらのシステムに依存して、システムのネイティブ トークンの経済的価値を超える資産量の移転をガイドしたいと考えていることです。この場合、理論的には、トークン所有者は資金を盗むために共謀して間違った答えを与えるインセンティブを持つことになります。
最初のレベルのタイトル
新しい質問
2019 年にもう一度パズルのリストを書くとしたら、一部は上記の質問の続きになるでしょうが、重点は大幅に変更され、素晴らしい新しい質問があったでしょう。
以下にいくつかの質問があります。
パスワードの難読化: 上記の項目 4 と同じ。
ポスト量子暗号における進行中の作業: ハッシュベースおよびポスト量子で安全な「構造化された」数学的オブジェクト。楕円曲線の構成…
共謀防止インフラストラクチャ: 進行中の作業と改良点 https://ethresear.ch/t/minimal-anti-collusion-infrastruction/5413。これには、オペレーターに対するプライバシーの追加、最も実用的な方法でのマルチパーティ計算の追加などが含まれます。
オラクル: 上記の #16 と同じですが、「成功指標」を重視せず、一般的な「現実世界のデータの取得」問題に焦点を当てています。
固有の人間のアイデンティティ (または、より現実的には、半固有の人間のアイデンティティ): 上記の #15 で書かれたものと同じですが、「絶対的」ではない解決策を強調します: 2 つのアイデンティティを取得することは、1 つを取得するよりも優れているはずです はるかに困難ですが、複数のアイデンティティを取得できなくなりますたとえ成功したとしても、それは不可能であり、有害な可能性があります。
準同型暗号化とマルチパーティ計算: 実用化するには、継続的な改善がまだ必要です。
分散型ガバナンス メカニズム: DAO は優れていますが、現在の DAO はまだ非常に原始的であり、もっと改善できるはずです。
PoS 51% 攻撃に対する完全に正式化された対応: https://ethresear.ch/t/responding-to-51-ATTACKS-in-casper-ffg/6363 を参照してください。
公共財のためのより多くの資金源: ネットワーク効果のあるシステム内で輻輳したリソース (取引手数料など) に課金するのが理想的ですが、分散型システムで課金するには公的正当性が必要です。したがって、これは社会問題でもあります。考えられる情報源を見つけるという技術的な問題でもあります。
評判システム: 上記の #12 と同じ。
一般に、ベース層の問題はゆっくりと、しかし確実に減少していますが、アプリケーション層の問題はまだ始まったばかりです。
Source：https://www.google.com/search?q=%E7%BF%BB%E8%AF%91&oq=%E7%BF%BB%E8%AF%91&aqs=chrome..69i57j0i512j0i433i512l2j46i131i199i433i465i512l2j0i131i433i512j0i433i512l2j46i433i512.1125j0j15&sourceid=chrome&ie=UTF-8
