Unsolved Problems in Blockchain Sharding（和訳）
シリーズの最初のパートでは、ブロックチェーンのシャーディングの動機を説明し、いくつかの基本的なコンセプトについて説明しました。今回の記事では、シャーディングの2つの大きな課題である"データの可用性"と"データの妥当性"を含む、シャーディングのより高度な側面について説明します。
イントロ
シャーデッド・ブロックチェーンの基本的な考え方は、ネットワークを運用・利用する参加者のほとんどが、すべてのシャードのブロックを検証できないということです。そのため、参加者が特定のシャードとやりとりする必要がある場合、一般的にはそのシャードの全履歴をダウンロードして検証することはできません。
特定のシャードの全履歴をダウンロードして検証しなければ、参加者は、相互作用している状態が有効なブロックのシーケンスの結果であり、そのようなブロックのシーケンスが実際にシャード内の正規のチェーンであることを必ずしも確信することができません。シャード化されていないブロックチェーンには存在しない問題です。
まず、多くのプロトコルで提案されているこの問題に対する簡単な解決策を提示し、この解決策がどのように壊れるか、また、どのような試みがなされているかを分析します。
web3スペースの起業家の方は、同スペースのTier1企業や投資会社のメンターが参加する私たちのアクセラレータへの参加をご検討ください。http://openwebcollective.com/。市場の特定、BD、マーケティング、資金調達など、ビジネスを構築するためのあらゆる側面をサポートします。
想定されるシンプルなソリューション
データの有効性に関するシンプルなソリューションは次のようなものであす。システム全体で数千人のバリデータが存在し、そのうち20%以上は悪意のあるものではなく、また失敗することもないと仮定します(ブロックを生成するためのオンライン状態にならないなど)。200人程度のバリデータをサンプリングした場合、実用的な目的のために ⅓人以上のバリデータが失敗する確率はゼロであると仮定できます。
⅓というのは重要な閾値です。BFTコンセンサスプロトコルと呼ばれる種類のコンセンサスプロトコルでは、クラッシュやプロトコルに違反する行為などで参加者の失敗が⅓未満である限り、コンセンサスが成立することが保証されています。
誠実なバリデータの割合を仮定すると、あるシャードの現在のバリデータ群がブロックを提供した場合、シンプルなソリューションでは、そのブロックは有効であり、 バリデータが検証を開始したときにそのシャードの正統なチェーンと信じていたものの上に構築されたものであると仮定すします。バリデータは前任のバリデータから正統なチェーンを学びました。前任のバリデータは、同じ仮定に基づいて、正統な連鎖の先頭であるブロックの上に構築しました。帰納法により、チェーン全体が有効であり、どのバリデータセットもフォークを生成していないので、素朴な解決策は現在のチェーンがそのシャードの唯一のチェーンであることも確かです。
このシンプルなソリューションは、バリデータを適応的に破損させることができると仮定した場合には機能しません。これは不合理な仮定ではありません（適応的破損についてはこちらを参照）。1000個のシャードを持つシステムで1個のシャードを適応的に破損させることは、システム全体を破損させることに比べて大幅にコストがかかります。そのため、プロトコルの安全性は、シャードの数に応じて直線的に低下します。ブロックの有効性に確信を持つためには、歴史上のどの時点においても、システム内のシャードの過半数のバリデータが結託していないことがわかっていなければなりませんが、適応型の敵がいれば、もはや確信は持てません。前節で説明したように、結託したバリデータは2つの基本的な悪意ある行動をとることができます。それはフォークの生成と無効なブロックの生成です。
悪意のあるフォークは、ブロックをシャードチェーンよりも、はるかに高いセキュリティを持つように設計されているBeaconチェーンにクロスリンクすることで対処できます。しかし、無効なブロックを生成することは、より困難な問題です。
データバリディティ
次の図では、Shard #1が破損し、悪意のある行為者が無効なブロックBを作成していると考えます。このブロックBの中で、アリスのアカウントに1000トークンが何もないところからミントされたとします。次に、悪意のある行為者は、無効なブロックBを難読化した上で、有効なブロックC（Cのトランザクションが正しく適用されるという意味で）を作成し、Shard #2へのクロス・シャード・トランザクションを開始して、これらの1000トークンをBobのアカウントに転送します。この瞬間から、不適切に作成されたトークンは、完全に有効なShard #2のブロックチェーン上に存在することになります。
この問題に取り組むためのシンプルなアプローチがあります。
1.Shard #2のバリデータは、トランザクションが開始されたブロックを検証します。上の例でも、ブロックCは完全に有効であるように見えるので、これはうまくいかないでしょう。
2.シャード#2のバリデータは、トランザクションが開始されるブロックの前にある大量のブロックを検証します。当然ながら、受信側シャードで検証された任意の数のブロックNに対して、悪意のあるバリデータは自分が作った無効なブロックの上にN+1個の有効なブロックを作ることができます。
この問題を解決する有力なアイデアは、各シャードが複数の他のシャードに接続された無向グラフにシャードを配置し、隣接するシャード間のクロス・シャード・トランザクションのみを許可することです（例えば、これはVlad Zamfirのシャーディングが本質的に機能する方法であり、同様のアイデアはKadenaのChainwebでも使用されています）。隣接していないシャード間でクロスシャード取引が必要な場合は、そのような取引は複数のシャードを経由して行われます。この設計では、各シャードのバリデータは、自分のシャードのすべてのブロックと、隣接するシャードのすべてのブロックの両方を検証することになっています。下の図では、10個のシャードがあり、それぞれが4つの隣接するシャードを持ち、シャード間の通信に2ホップ以上必要なシャードはないものとします。
Shard #3はShard #2のすべてのブロックを検証していますが、Shard #1のブロックは検証していないため、悪意のあるブロックを検出する方法がありません。
データの妥当性を適切に解決するためには、大きく分けて、フィッシャーマンとクリプトによる計算証明の2つの方向性があります。
フィッシャーマン
第1のアプローチの背景にある考え方は次のようなものです。ブロックヘッダが何らかの目的でチェーン間で通信されると（ビーコンチェーンへのクロスリンクやクロスシャード取引など）、誠実なバリデータであればそのブロックが無効であるという証明を提供できる期間があります。ブロックが無効であることを非常に簡潔に証明できる様々な構造があるので、受信ノードの通信オーバーヘッドはフルブロックを受信する場合よりもずっと小さいです。
この方法では、シャード内に少なくとも1人の誠実なバリデーターがいる限り、システムは安全です。
これは、現在提案されているプロトコルの中で、（問題を存在しないことにする以外の）主流のアプローチです。しかし、この方法には2つの大きな欠点があります。
1.チャレンジ期間は、誠実なバリデータがブロックが生成されたことを認識し、それをダウンロードして完全に検証し、ブロックが無効な場合にチャレンジを準備するのに十分な長さが必要です。このような期間を設けると、クロス・シャードの取引が大幅に遅れることになります。
2.チャレンジプロトコルの存在は、悪意のあるノードが無効なチャレンジでスパムを行う際に、新たな攻撃のベクトルを生み出します。この問題に対する明白なソリューションは、挑戦者にある程度の量のトークンを預けさせ、挑戦が有効であった場合に返却させることです。しかし、これは部分的なソリューションに過ぎません。敵対者にとっては、無効なチャレンジでシステムをスパムする（そして預託金を燃やす）ことがまだ有益であるかもしれません。このような攻撃はGriefing Attackと呼ばれています。
フィッシャーマンの2つの問題はどちらも満足できるソリューションではありませんが、無効なブロックがファイナライズされる可能性があることに比べれば、フィッシャーマンを使うことはまだ厳密には良いことです。
簡潔で非対話的な知識の論証
マルチプル・シャード・コラプションの2つ目のソリューションは、ある計算（トランザクションのセットからブロックを計算するなど）が正しく実行されたことを証明できる、ある種のクリプト構造を使用することです。このような構造は、zk-SNARKsやzk-STARKsなどいくつか存在し、現在のブロックチェーンプロトコルでは、ZCashを筆頭にプライベートペイメントに積極的に使用されています。このようなプリミティブの主な問題点は、計算に時間がかかることです。例えば、ブロックチェーン内のすべてのブロックが有効であることを証明するためにzk-SNARKを特別に使用しているCoda Protocolは、あるインタビューの中で、証明を作成するために1つのトランザクションにつき30秒かかると述べています（この数字はおそらく今では小さくなっているでしょう）。
興味深いことに、証明は信頼できる当事者によって計算される必要はありません。なぜなら、証明は、そのために構築された計算の有効性を証明するだけでなく、証明自体の有効性も証明するからです。したがって、このような証明の計算は、一部の信頼できない計算を行うために必要な冗長性を大幅に減らして、一連の参加者に分割することができます。また、zk-SNARKを計算する参加者は、システムの分散性を低下させることなく、特別なハードウェア上で実行することができます。
zk-SNARKsの課題は、性能以外にもあります。
・あまり研究されていないし、あまりテストもされていないクリプトプリミティブに依存しています。
・"有害な廃棄物" - zk-SNARKsは、複数の人がある計算を行い、その計算の中間値を廃棄するという信頼できる設定に依存しています。その手順の参加者全員が結託して中間値を保持すれば、偽の証明を作ることができます。
・システム設計に余計な手間が生じます。
・zk-SNARKは、可能な計算のサブセットに対してのみ機能するので、チューリング完全なスマートコントラクト言語を用いたプロトコルでは、SNARKを使ってチェーンの有効性を証明することはできません。
多くのプロトコルがzk-SNARKを長期的に使用することを検討していますが、私はCoda以外にzk-SNARKを使用してローンチする予定のプロトコルを知りません。
データの可用性
2つ目の問題として、データの可用性について触れます。一般的に、あるブロックチェーンを運用するノードは2つのグループに分けられます。全ブロックをダウンロードし、すべてのトランザクションを検証する"フルノード"と、ブロックヘッダーのみをダウンロードし、興味のある状態やトランザクションの一部についてMerkle証明を使用する"ライトノード"です。
フルノードの過半数が結託した場合、彼らは有効か無効かに関わらずブロックを生成し、そのハッシュをライトノードに送信することができますが、ブロックの全内容を公開することはありません。彼らが利益を得る方法は様々です。例えば、下の図を考えてみましょう。
ブロックは3つあり、前のAは誠実なバリデータが作成したもの、現在のBはバリデータが結託しているもの、そして次のCも誠実なバリデータが作成するものです（ブロックチェーンは右下に描かれています）。
あなたは商人です。現在のブロック(B)のバリデータは、以前のバリデータからブロックAを受け取り、あなたがお金を受け取るブロックを計算し、そのブロックのヘッダに、あなたがお金を持っている状態のMerkle証明(または、あなたにお金を送る有効な取引のMerkle証明)を付けてあなたに送りました。トランザクションが確定したことを確信して、あなたはサービスを提供します。
しかし、バリデータはブロックBの完全な内容を誰にも配布しません。そのため、ブロックCの誠実なバリデータはブロックを回収することができず、システムを停止させるか、Aの上に構築することを余儀なくされ、商人であるあなたからお金を奪うことになります。
各シャードのバリデータはそのシャードのすべてのブロックをダウンロードし、そのシャードのすべてのトランザクションを検証しますが、システムの他のノード（シャードチェーンをビーコンチェーンにスナップショットするノードを含む）はヘッダをダウンロードするだけです。このように、シャード内のバリデータはそのシャードにとって実質的にフルノードであり、ビーコンチェーンを含むシステム内の他の参加者はライトノードとして動作します。
先に述べたフィッシャーマンアプローチが機能するためには、正直なバリデータがビーコンチェーンにクロスリンクされたブロックをダウンロードできる必要があります。もし悪意のあるバリデータが無効なブロックのヘッダをクロスリンクした(あるいはそれを使ってシャード間取引を開始した)としても、そのブロックを配布しなかった場合、正直なバリデータはチャレンジを作成する手段を持たないことになります。
この問題を解決するために、相互に補完し合う2つのアプローチを取り上げます。
Proof of Custody
解決すべき最も直接的な問題は、公開されたブロックが利用可能かどうかということです。提案されているアイデアの1つは、ブロックをダウンロードしてダウンロードできたことを証明するだけの仕事をしているバリデータよりも、シャード間を頻繁に回るノタリーと呼ばれる人たちがいることです。バリデータと違ってシャードの状態全体をダウンロードする必要がないので、より頻繁に交代させることができます。
この素朴なアプローチの問題点は、ノタリーがブロックをダウンロードできたかできなかったかを後から証明することができないことです。そのため、ノタリーはブロックを取得しようとせずに、常にブロックをダウンロードできたことを証明することができます。これに対する一つのソリューションは、ノタリーがブロックをダウンロードしたことを証明する何らかの証拠を提供するか、一定量のトークンをステークすることです。そのようなソリューションの一つをここで説明します。
消去コード
特定のライトノードがブロックのハッシュを受信した場合、ブロックが利用可能であるというノードの信頼性を高めるために、ブロックのランダムな部分をいくつかダウンロードしようとすることができます。これは完全なソリューションではありません。というのも、ライトノードが一斉にブロック全体をダウンロードしない限り、悪意のあるブロック製作者は、どのライトノードによってもダウンロードされなかったブロックの一部を保留することを選択でき、その結果、ブロックは依然として利用できなくなるからです。
一つのソリューションは、消去コードと呼ばれる構造を用いて、ブロックの一部しか利用できない場合でも、ブロック全体を復元できるようにすることです。
PolkadotとEthereum Serenityには、この考えに基づいたデザインがあり、ライトノードがブロックが利用可能であることを合理的に確信できる方法を提供しています。Ethereum Serenityのアプローチについては、本稿で詳しく説明しています。どちらのアプローチもチャレンジに依存しているため、griefing attacksにさらされる可能性があります。
長期的な可用性、そして結論
なお、上述のアプローチはいずれも、ブロックが公開され、現在利用可能であるという事実を証明するものに過ぎません。ブロックは、ノードがオフラインになったり、ノードが意図的に過去のデータを消去したりするなど、さまざまな理由で後に利用できなくなる可能性があります。
ポリシャードは、消去コードを使用して、複数のシャードがデータを完全に失った場合でも、シャード間でブロックを利用できるようにします。残念ながら、それらのアプローチは、すべてのシャードが他のすべてのシャードからブロックをダウンロードする必要があり、非常にコストがかかります。
幸いなことに、長期的な可用性はそれほど差し迫った問題ではありません。システムの参加者の中には、すべてのシャードのすべてのチェーンを検証できる人はいないと予想されるため、シャード化されたプロトコルのセキュリティは、一部のシャードの古いブロックが完全に利用できなくなったとしても、システムが安全であるように設計する必要があります。
安全なプロトコルを設計する上で、"データの妥当性"と"データの利用可能性"という2つの問題は、まだ満足のいくソリューションが見つかっていません。私たちはこれらの問題を積極的に研究しています。今後の展開にご期待ください。
アウトロ
Near Protocolは、使いやすさを重視したシャード型の汎用ブロックチェーンを構築しています。私たちの記事を気に入っていただけましたら、twitterでフォローしていただければ、新しいコンテンツの投稿を知ることができます。
・http://twitter.com/nearprotocol
もっと参加したい方は、Discordチャンネルに参加してください。ここでは、コンセンサス、経済性、ガバナンスなど、Near Protocolの技術的および非技術的な側面をすべて議論しています。
・https://github.com/nearprotocol/nearcore
最後になりましたが、当社のニュースレターをご購読ください。隔週で最新情報をお送りしており、Near Protocolの発売に向けた進捗状況を知るには最適なチャンネルです。
Ethereum財団のJustin Drake氏、PolkadotのAlistair Stewart氏、Cosmos ProtocolのZaki Manian氏、Kadena ProtocolのMonica Quaintance氏、InterstellarのDan Robinson氏には、この記事の初期のドラフトを確認し、フィードバックをいただきました。