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

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

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


日本で初めてのNEAR ProtocolのミートアップがHashhubにて開催されます。情報の少ないNEARの最新情報を「日本語」で聞くチャンスです。席に限りがございますのでお早めにご参加ください。

前回のThe Beginner’s Guide to the NEAR Blockchain – NEAR Protocol 入門書編 – を読まれていない方は、先にこちらを読んで頂くとことで、より理解を深めて頂けます。

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

 

Blockchain・Sharding

今回の記事では、ブロックチェーン・Sharding(以下 シャーディング(*1))が直面している課題と構築方法について説明したいと思います。

*1:シャーディングという単語は、破片を意味する英単語シャード(shard)に由来しています。データベース分野では古くから使用されている単語で、データを複数のデータベースに分散配置して、データベースの負荷を分散することを意味しています。

記事執筆時点でのEthereumの処理能力は、メインチェーン上で1秒間に約20トランザクション未満であることはよく知られています。処理能力の制限とネットワークの人気が相まって、ガス価格の高騰とおよび承認時間の遅延(低スループット)をもたらしています。

この低スループットの原因は何でしょうか?

その原因は、ネットワーク内のすべてのノードがすべてのトランザクションを処理しているからです。

2つの解決策が提案されています。

  • すべての演算処理を少数の強力なノードセットに委任
  • ネットワーク内の各ノード間で分割して演算処理をする

前者を採用しているのはThunderです。単一のノードですべてのトランザクションを処理し、1200 tx /秒という(Ethereumと比較して約100倍)スループットを実現しています。より多くのトランザクションを処理するためにコンセンサスとブロックチェーン構造でさまざまな改善案がありますが、その処理能力は1つのノードの処理速度に制限されています。

トランザクションの処理がすべての参加ノード間で分割される後者のアプローチは、シャーディングと呼ばれています。これが、Ethereum Foundationが現在計画しているEthereumをアップグレードする方法です。

*2:執筆時点でシャーディングの完全な仕様は公開されていません。

そして、Near Protocolもシャーディングを構築しています。

NEAR Protocolのチームには、シャーディングの構築を担当する3人の元MemSQLエンジニア、および5名の元Googlerが在籍しており、分散型システムの構築に関する業界の専門知識を持っています。

 

シャーディングのことをBeanstalkと呼ぶ

この記事を通して、シャーディングのことをBeanstalkと呼ぶことにします。

シャーディングは、演算処理をする際に複数のノードにトランザクションを分割します。分割されたノードを「shard(以下 シャード)」と呼びます。各シャードには独自のバリデーターのセットがあります。そしてPoWのマイニングや投票による検証によってブロックを生成する参加者を、「バリデータ」と呼びます。

Beanstalkの設計は、シャーディングにおけるいくつかの課題を概説するのに十分な役割を果たします。

 

Validator partitioning and Beacon chains

シャーディングにはいくつかの課題が存在するとお伝えしました。

1つ目の課題は、分割されていないX個のバリデーターを持つ1つの大きなチェーンが10個のシャードに分割する場合、各シャードはX/10個のバリデーターを持つことになります。そして各シャードに独自のバリデータが存在することになります。しかし、各シャードの安全性がチェーン全体の1/10になったことを意味しており、1つのシャードを破壊するにはバリデータの総数の5.1%(51%/10)への攻撃で可能となってしまいます。

2つ目の課題は、それぞれのシャードに対して誰がバリデータを決定するのかということです。5.1%のバリデーターがすべて同じシャード内に入ってしまった場合大きな問題になります。バリデータがどのシャードに含まれるかを選択できないことが望ましく、システムを危険にさらす可能性が大幅に低下します。

現在提案されているシャーディングは、バリデータを各シャードに割り当てる際にランダムネスに基づいています。ランダムネスによるバリデーターの割り当てにはシャード毎に計算を必要とします。よって既存の設計では、ネットワーク全体を保持するのに必要なオペレーションの実行を委任された別のチェーンを保持しています。これらのオペレーションには、ランダムネスの生成やシャードへのバリデータの割り当てのほかに、シャードの更新とそのスナップショットの取得、PoSによるステークの処理とスラッシング、およびシャードの調整が含まれています。

このようなチェーンは、EthereumやNEAR ProtocolではBeacon chains(以下 ビーコンチェーン)、PolkaDotではRelay chain、CosmosではCosmos Hubと呼ばれています。

 

Quadratic Sharding

シャーディングはネットワークに参加しているノードの数に応じて無数に拡大するソリューションです。理論的にはそのようなシャーディングソリューションを設計することは可能ですが、ビーコンチェーンの拡張性には制限があります。ビーコンチェーンはそれ自体が単一のブロックチェーンであり、演算を実行するノードの計算能力によって制限されるため、シャードの数も自然に制限されていきます。

ネットワーク内のノードの効率が恣意的に改善され、トランザクション処理時間が短縮される場合を考えてみましょう。

例えば、ビーコンチェーン内のノードを含めてネットワークを運用しているノードが4倍高速になると、各シャードは4倍以上のトランザクションを処理することができ、ビーコンチェーンは4倍以上のシャードを処理できるようになります。システム全体のスループットは4 x 4 = 16倍に増加します。これがQuadratic シャーディングです。

現時点で実行可能なシャード数を正確に測定することは困難ですが、将来的にユーザーのニーズがQuadratic シャーディングの処理できる上限を上回ることは考えられません。このような量のシャードを安全にオペレートするために必要なノードの数は、現時点でネットワーク内に存在するノードの数よりも桁違いに多くなります。

Exponential シャーディングという提案も活発的に行われています。これはシャードがマークル木を形成していき各親シャードは子シャードを編成します。子シャードは他の親シャードの子になることができます。

POINTQuadratic シャーディングはメインチェーンの下に分割された単一のシャードを形成する提案で、Exponential シャーディングは、分割されたシャード(親シャード)の下にシャード(子シャード)を形成する提案です。

 

State Sharding

ブロックチェーン内のノードは3つの重要なタスクを実行します。

1)トランザクションの処理。

処理をするトランザクションの数が増えるにつれて、より多くの処理能力が必要になります。

2)検証済みトランザクションと完成したブロックを他のノードに中継。

中継されるトランザクションとブロックの数が増加するにつれて、より多くのネットワーク帯域幅が必要になります。

3)ネットワーク台帳全体のステート(状態)と履歴を格納。

ステートが大きくなるにつれてより多くのストレージが必要になります。重要なのは、トランザクションレート(1秒あたりに処理するトランザクション数)が一定の場合でも、ストレージは増大するということです。

上記よりストレージの増大が大きな問題に感じるかもしれませんが、実際の大きな問題は処理能力です。この記事の執筆時点でのEthereumの全体のステートは100GBで、ほとんどのノードで簡単に管理できています。しかし、多くのユースケースに必要な数よりも随分少なくなっています。

実際には、各シャード内のノードは割り当てられているグローバル・ステートのローカル部分にのみ影響するトランザクションを含む独自のチェーンを構築しています。したがって、シャード内のバリデーターは、グローバル・ステートのローカル部分のみを保管して、そのステート部分に影響を与えるトランザクションのみを処理する必要があります。この作業の分割は、すべての処理能力、ストレージ、およびネットワーク帯域幅に対する負担を低減しますが、データの可用性やCross shard transactions(以下 クロスシャード・トランザクション)などの新しい問題を引き起こします。

 

Cross shard transactions

事例として前述したBeanstalkは、各シャード間で相互にコミュニケーションが取れない場合、有用なアプローチとは言えません。このシャード間の相互運用性には大きな課題があります。

ネットワークの各参加者が1つのシャード内にアカウントを持ち、決済をした場合を例に考えてみましょう。同じシャード内で口座から別の口座に送金する場合は、そのシャード内のバリデーターによってトランザクションを処理することができます。しかし、シャード#1(別シャード)に住むアリスがシャード#2(別シャード)に住むボブにお金を送りたいのであれば、シャード#1のバリデーターもシャード#2のバリデーターもトランザクションを処理することができます。

クロスシャード・トランザクションには、2つのアプローチがあります。

  • 同期(Synchronous):クロスシャード・トランザクションが発生した際には、トランザクションに関連したステートを含む複数のシャード内のブロックがすべて同時に生成され、複数のシャードのバリデーターがトランザクションの処理に関して協力をします。
  • 非同期(Asynchronous):クロスシャード・トランザクションが発生した際に非同期で処理が実行されます。この方法は調整の容易さにより一般的になる傾向があり、現在Cosmos、Ethereum Serenity、NEAR、Kadenaなどで提案されています。問題点として、ブロックが独立して生成された場合、複数のブロックのうちの1つが孤立する可能性があるため、トランザクションが部分的にしか適用されないことがあげられます。以下の図は、2つのシャード(シャード#1 シャード#2)でハードフォーク発生後に対応したブロックAとX ‘に記録されたクロスシャードトランザクションを示しています。チェーンA-BとV’-X’Y’Z ‘が対応するシャードが正規のものとして承認された場合、トランザクションは完全にファイナライズ(確定)します。A’-B’-C’-D ‘とVXが対応するシャードが正規のものとして承認された場合、トランザクションは完全に放棄されます。しかしこれは許容範囲です。しかし、ABとVXが正規のものとして承認された場合は、トランザクションの一部がファイナライズされ、一方が破棄されて障害が発生します。

チェーン間の相互運用性(インターオペラビリティ)は、多くのプロジェクトが解決しようとしている重要な問題です。シャードとして分割されたブロックチェーンのブロック構造とコンセンサスは、シャード間で同じなので問題に対するハードルを低減しています。しかし、すべてのシャードチェーンは同じですが、様々なブロックチェーンエコシステムでは、ターゲットユースケース、分散化、およびプライバシーの保証に関してそれぞれ異なります。

 

悪意ある行動

最後に理解しておくべき重要事項があります。

それは、悪意のあるバリデータがどのような攻撃を実行できるのかということです。

悪意のあるフォーク

悪意のあるバリデータがハードフォークを試みるかもしれません。採用しているコンセンサスがBFTであるかどうかは関係ありません。バリデータの数が減少すれば常にハードフォークができるようになります。

ネットワーク全体の50%以上が破壊されてしまうよりも、単一のシャードの50%以上が破壊されてしまう可能性の方が非常に高いことを前述しました。さらにクロスシャードトランザクションは複数のシャードのステート変更を含み、そのようなステート変更を適用するシャード内のブロックはすべてファイナライズされるか、または孤立してしまう可能性があります。一般的にシャードが破損する可能性は無視できないので、シャードとバリデータ間でビザンチンの合意が得られた場合や、ステートが変化してブロックの上に多数のブロックが生成された場合でも、ハードフォークは発生しないとは言えません。

この問題には複数の解決策がありますが、最も一般的な解決策は最新のシャードチェーンからビーコンチェーンのクロスリンクです。次に、シャードチェーン内のハードフォークルールが変更されて、常にクロスリンクされているチェーンが優先され、最後のクロスリンク以降に公開されたブロックにのみシャード固有のハードフォークルールが適用されます。

次にフォークルールとは何かについて詳しく説明します。

無効なブロックの承認

一連のバリデータが、ステート遷移関数を使って誤ったブロックの作成を試みる可能性があります。たとえば、Alice10個のトークンを持ち、Bob0個のトークンを持つ状態から始めて、ブロックにはAliceからBob10個のトークンを送信するトランザクションが含まれる場合があります。

ネットワーク内のすべての参加者がすべてのブロックを検証し、そのような無効なステート遷移を持つブロックは他の両方のブロックプロデューサおよびネットワークの参加者によって拒否されるため、従来の分割されていないブロックチェーンではそのような攻撃は不可能です。たとえ悪意のあるバリデータが、正直なバリデータよりも速く無効なステート遷移を持つブロックの上にブロックを作成し続け、無効なブロックを持つチェーンが長くなったとしても、問題ありません。すべてのブロックを検証し、無効なブロックの上に構築されたすべてのブロックを破棄します。

上の図には5つのバリデータが存在しており、そのうちの3つは悪意のあるものです。彼らは無効なブロックA ‘を作成し、その上に新しいブロックを構築し続けました。2人の正直なバリデータが無効なものとしてA ‘を破棄した後に、有効なブロックとしてAをフォークしました。正直なフォークブロックにはバリデータが少ないので、チェーンは短くなっています。ただし、従来の非共有ブロックチェーンでは、何らかの目的でブロックチェーンを使用するすべての参加者は、受信したすべてのブロックを検証してステートを再計算する責任があります。したがって、ブロックチェーンに興味を持っている人なら誰でも、A ‘が無効であることを確認し、したがってB’C ‘およびD’もすぐに破棄し、チェーンABを現在の最長有効チェーンと見なします。

ただしネットワーク参加者は、シャードとして分割されたすべてのトランザクションを検証できないため、ブロックチェーン内のシャードの履歴から無効なブロックが含まれていないことを確認する方法が必要になってきます。

ビーコンチェーンにはブロックを検証する機能がないため、クロスリンクは十分な解決策ではありません。クロスリンクを用いることで、シャード内の十分な数のバリデータがブロックに署名したことを検証することができます(したがって、その正当性が証明されています)。

この問題に対する解決策が2つありますが、現時点満足できるものではありません。

  1. ステート遷移を誤って適用しようとした場合にシステムに警告する合理的なメカニズムがいくつかあります。特定のシャード内の悪意のあるバリデータの数が2/3未満である限り、各シャードが何らかのBFTコンセンサスを実行していると仮定して、少なくとも1人の正当なバリデータがブロックを証明することで、ステート遷移関数が正しく適用されます。悪意のあるノードが2/3を超えている場合は、正直な単一のノードを参加させることなく誤ったブロックをファイナライズ(確定)させることができます。シャード内の少なくとも1つのノードは悪意がないと仮定すると、そのようなノードからどのようなブロックが生成されているかをモニターし、無効なステート遷移を持つノードを検証するための十分な時間が必要になります。
  2. ブロックには、ステート遷移が正しく適用されていることを証明するのに十分な情報を入れる必要があります。

現在、バリデータローテーションとビザンチンフォールトトレラントコンセンサスを採用しているプロトコルでは、ハードフォークや無効な状態遷移を実行することは不可能であると仮定しています。これについては次回説明します。

 

日本で初めてのNEAR ProtocolのミートアップがHashhubにて開催されます。情報の少ないNEARの最新情報を「日本語」で聞くチャンスです。席に限りがございますのでお早めにご参加ください。

 

LINE@ – 友達追加 –

おかげさまで現在お友達が1057名を突破しました。仮想通貨の最新情報や重要なファンダ情報などを「プッシュ通知」にて誰よりもはやくお届けします。

CoinPicks Labってなに?

関連記事

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

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

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

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

PAGE TOP