厳選!知っておきたい市場ニュース!!

ブロックチェーン・シャーディング PART2

ブロックチェーン・シャーディングのPART2を和訳しました。全文の中から日本人でも理解がしやすいように筆者独自の表現に変換している部分が多々ありますのでご了承ください。こちらの記事を読んでいただくことで、シャーディングの課題であるデータの有効性と可用性について学ぶことができます。


前回のブロックチェーン・シャーディング PART1を読まれていない方は、先にこちらを読んで頂くとことで、より理解を深めて頂けます。

また、NEAR Protocolの日本版テレグラムはこちらから参加頂けます。

 

シャーディング・ブロックチェーンの課題

PART1では、Sharding(以下 シャーディング)に関する主要な概念について説明しました。 この記事では、2種類の課題であるデータの可用性とデータの有効性を含む、より高度な側面からシャーディングについて説明します。

基本的な考え方として、ネットワークに参加している個人は、検証のためにシャードをまたいでブロックの履歴全体をダウンロードすることはできません。この性質によりシャーディングには大きな課題があります。それは、シャード同士の相互作用(コミュニケーション)によって生成されているブロックが正しい結果なのか否かを確信することができないというものです。

この問題を解決するためにどのような提案がされているのかについて説明していきたいと思います。

 

悪意のあるフォークの作成と無効なブロック生成

例えば、ネットワーク全体で数千人のバリデータが存在しており、そのうち悪意のある又はオフラインになっているバリデータが20%以下と仮定します。次に、200個のバリデータをサンプリングした場合、1/3を超える数が悪意あるバリデータである可能性は限りなくゼロとみなすことができます。

シャード内のバリデータは、そのシャードを正規チェーンとしてブロックを生成します。ブロックは同じバリデーションによって、正規チェーンの先頭に構築されます。生成されたブロックは帰納法によりチェーン全体を有効な状態として考えることができます。

しかし、正常なバリデータが機能していないと仮定した場合、この単純な解決策通りにはいきません。

プロトコルのセキュリティーとして、シャーディングブロックチェーンはそうでないブロックチェーンと比較して、はるかに耐性が低く安価な攻撃が可能です。したがって、プロトコルのセキュリティはシャードの数とともに直線的に減少します。適応型敵対者が存在する場合、悪意のあるフォークの作成と無効なブロック生成が実行できてしまいます。

悪意のあるフォークは、一般的にシャードチェーンよりもかなり高いセキュリティを持つように設計されているビーコンチェーンへのクロスリンクによって対処できます。しかし、無効なブロック生成への対応は大きな課題となっています。

 

データの有効性

1つ目の課題はデータの有効性です。

次の図で、シャード#1が破損し、悪意のある参加者が無効なブロックBを作成したとします。このブロックBでは、アリスのアカウントで1000トークンがマイニングされたとします。次に、悪意のある参加者は、無効なブロックBを難読化して、有効なブロックCを(Cのトランザクションが正しく適用されるという意味で)Bの上に生成し、Shard2でボブのアカウントへのクロスシャードトランザクションを開始します。これによって、不適切に作成されたブロックは完全に有効なシャード#2のブロックチェーンに存在することになります。

この問題に対する解決策としていくつか方法があります。

1.Shard2のバリデータによってトランザクションが開始されたブロックの検証をします。しかし、上図のように完全に有効化されたブロックCには対応できません。

2.シャード#2のバリデータがトランザクションが開始されたブロック以前のブロックを検証します。しかし、シャードによって検証されたN個のブロックに対して、悪意のあるバリデータが生成した無効ブロック上にN + 1個の有効ブロックを作成することができます。

この問題を解決するための有望なアイデアは、他の各シャードに接続されたUndirectedグラフにシャードを配置し、隣接するシャード間でクロスシャードトランザクションの許可をすることです。隣接していないシャード同士のコミュニケーションが必要な場合、そのようなトランザクションは複数のシャードを介して経路が指定されます。この設計では、各シャード内のバリデータは、シャード内のすべてのブロックと、隣接するすべてのシャード内のブロックを検証することが期待されています。各ノードは4つの隣接するノードを持ち、クロスシャード通信に2つ以上のホップを必要とする以下の図を考えてみてください。

シャード#2は、自身のブロックチェーンだけでなく、シャード#1を含むすべての隣接するブロックチェーンも検証しています。 そのため、シャード#1の悪意のある参加者が無効なブロックBを作成後、その上にブロックCを構築してクロスシャードトランザクションを開始した場合でも、シャード#2はシャード#1を検証済みなのでクロスシャードトランザクションは成功しません。Shard1の履歴から無効なブロックBを識別することができます。

 

しかし、複数のシャードに対する攻撃には課題が残ります。下図のようにシャード#1とシャード#2の両方に対する攻撃を実行した場合、無効なブロックBの作成によるクロスシャードトランザクションは、シャード#3で正常に実行されてしまいます。

シャード#3は隣接するシャード#2内のすべてのブロックを検証しますが、シャード#1内のブロックは検証しません。よって悪意のあるブロックを検出する方法がないということになります。

データの有効性を解決するには、FishermenとCryptographicによる2つの証明方法があります。

 

Fisherman

Fishermenとして、ブロックヘッダーが何らかの目的でチェーン間のコミュニケーションをするときには、正直なバリデータがブロックが無効であることを証明する期間が存在します。構造上、ブロックが無効であるという証明を可能にするために、受信側ノードの通信オーバーヘッドは、フルブロックを受信するときよりもはるかに小さくなります。

このアプローチでは、シャード内に少なくとも1つの正直なバリデータが存在している限りシステムは安全と言えます。

これは、現在提案されているプロトコルの中で主流のアプローチです。ただし、この方法には2つの大きな欠点があります。

1.正直なバリデータがブロックの生成を認識すると、ダウンロードと検証がはじまり無効なブロックを発見した場合に、そのブロックを無効にするための長いチャレンジ期間が必要です。長いチャレンジ期間を導入することでクロスシャードトランザクションを遅らせることができます。

2.チャレンジ期間の存在は、悪意のあるノードに新たな攻撃経路(無意味なチャレンジ)を作ることになります。この問題に対する解決策は、チャレンジを実行する際にトークンのデポジットを義務付けておくことです(悪意がなければチャレンジ後に返還されます)。しかし、攻撃者からみてデポジットしたトークンと攻撃による利益を天秤にかけて、攻撃による利益が上回る可能性もあるため、この方法がベストプラクティスとは言えません。このような攻撃は「Griefing Attacks」と呼ばれています。

Fishermanの2つの問題に対する解決策があるわけではありませんが、Fishermanを使用することで、無効ブロックの確定に対する耐性がある点で優れていると言えます。

 

Succinct Non-interactive Arguments of Knowledge

複数のシャードに対する攻撃の解決策は、ある種のCryptographic Constructions(トランザクションの集合からのブロックの計算など)が正しく実行されたことを証明できるようにすることです。そのような構成は存在します。 zk-SNARKszk-STARKsなどのプライベートペイメントのために積極的に使用されています。このようなプリミティブな問題は計算に時間がかかることで有名です。例えば、CodaProtocolはチェーンの全てのブロックが有効であることを保証するためにzk-SNARKsを使用していますが、あるインタビューで、証明のために1トランザクションあたり30秒かかる可能性があると述べています(現在のTPS(処理速度)は向上している可能性があります)。

興味深いことに、ブロックが構築された計算の妥当性を証明するだけでなく、証明自体の妥当性も証明するので、証明自体は信頼できる当事者によって計算される必要はありません。したがって、そのような証明の計算は、少ない参加者の間で分割することができます。また、zk-SNARKsを計算する参加者がシステムの分散化を減らすことなく特別なハードウェア上で実行することも可能になります。

パフォーマンス以外でのzk-SNARKsの課題は、次のとおりです。

  • 研究とテストの回数が少ない。
  • すべての関係者が中間値を共謀して保持している場合は、偽の証明を作成できる。
  • システム設計が複雑。
  • スマートコントラクト言語を使用したプロトコルでは、チェーンの有効性を証明するためにSNARKsを使用することはできない。

多くのプロトコルがzk-SNARKsの導入を検討していますが、CodaProtocol以外に実用化されたものが確認できていません。

 

データの可用性

2つ目の課題はデータの可用性です。

通常、ノードは2つのグループに分けられます。フルノード(すべてのフルブロックをダウンロードしてすべてのトランザクションを検証するノード)とライトノード(ブロックヘッダーのみをダウンロードし、署名の一部や興味のある取引にはMerkleプルーフを使用する)です。

フルノードは有効または無効のブロックを作成して、そのハッシュをライトノードに送信することができますが、ブロックの完全な内容を開示することはできません。

上図には3つのブロックがあります。ブロックBのバリデータは、前のバリデータからブロックAを受け取り後に計算がはじまり、あなたが保有している資産をステートのマークルツリー証明付きでブロックBのヘッダに送ります。

しかし、バリデータはブロックBの内容を誰にも配布しません。そのため、ブロックCのバリデータは正確なブロックを取得できず、ブロックAの情報のみを受け取りブロックCを構築することを余儀なくされ2重払いが成功します。

同じシナリオをシャードに適用すると、通常、フルノードとライトノードの役割がシャードごとに適用されます。各シャード内のバリデータは、シャード内のすべてのブロックとトランザクションを検証します。シャードチェーンはビーコンチェーンに記述され、ヘッダーのみをダウンロードします。したがって、シャード内のバリデータはそのシャードの事実上フルノードであり、ビーコンチェーンを含むシステム内の他の参加者はライトノードとして機能します。

上で議論したFishermanのアプローチを成功させるためには、正直なバリデータがビーコンチェーンにクロスリンクしているブロックをダウンロードできる必要があります。しかし、悪意のあるバリデータが無効なブロックのヘッダをクロスリンクしたり(またはクロスシャードトランザクションを開始するためにそれを使用した場合)、そのブロックを配布しなかった場合、正直なバリデータはチャレンジを作成する手段がありません。

この問題に対処するために、互いに補完する2つのアプローチを取り上げます。

 

Proof of Custody

もっとも早急に解決されるべき問題は、発行されたブロックが利用可能か否かの判別です。提案されているアイデアの1つは、シャード間で頻繁にローテーションするいわゆる公証人を持つことです。バリデータとは異なり、シャードのステート全体をダウンロードする必要がないため、より頻繁にローテーションすることができます。

このアプローチの問題点は、公証人がブロックをダウンロードできたかどうかを後で証明することが不可能であるということです。そのため、公証人はブロックのダウンロードについて虚偽の発言が可能になります。これに対する1つの解決策は、公証人が何らかの証拠を提供したり、ブロックがダウンロードされたことを証明するために、ある程度の量のトークンをステークすることです。そのような解決策の1つはこちらで議論されています。

 

Erasure Codes

特定のライトノードがブロックのハッシュを受信したときに、そのブロックが使用可能であるというノードの信頼性を高めるために、ブロックのいくつかのランダムな部分をダウンロードしようと試みることができます。ライトノードがブロック全体をまとめてダウンロードしない限り、悪意のあるブロック作成者は、どのライトノードによってもダウンロードされなかったブロックの部分を差し控えることを選択できるため、依然として無効なブロックを作成できます。

1つの解決策は、ブロック全体を回復できるようにするために消去コードと呼ばれる構造を使用することです。

 

長期的なデータ可用性と結論

上記のすべてのアプローチは、ブロックが発行されたことを証明するものであり、ノードがオフラインになる、ノードが履歴データを意図的に消去するなど、さまざまな理由でブロックが使用できなくなる可能性があります。

言及する価値のあるホワイトペーパーはPolyshardです。Polyshardは、いくつかのシャードがデータを完全に失ってもブロックをシャード間で使用できるようにするために消去コードを使用しますしかし、Polyshardのアプローチは、他のすべてのシャードからブロックをダウンロードする必要があります。

幸いなことに、長期的な可用性はそれほど差し迫った問題ではありません。システムの参加者がすべてのシャードのすべてのチェーンを検証できるとは予想されないため、シャードプロトコルのセキュリティは一部のシャードに対してシステムは安全であるように設計することが必要です。

データの有効性とデータの可用性には、安全なプロトコルを設計する上で課題が残っています。私達はこれらの問題を積極的に研究しています。アップデートをお楽しみに!!

 

原文

 

Join Lab Now

関連記事

  1. Mimblewimbleについて日本語で理解する

  2. ブロックチェーン・シャーディング PART1

  3. The Beginner’s Guide to the NEAR Blockchain –…

  4. ERC725とERC735について学びDappsのユースケースを考える

PAGE TOP