The authoritative guide to Blockchain Sharding, part 1（和訳）

zacky

著:Alexander Skidanov

画像1

 このブログ記事は、ブロックチェーン・シャーディングに関する2つのシリーズの最初のものです。このブログ記事を読めば、なぜシャーディングが将来性のあるブロックチェーンプロトコルへの道であるのか、今日シャーディングがどのように構築されているのか、すべてのシャーディングされたプロトコルがどのような課題に直面しているのか、そしてそのような課題にどのように対処できるのかがわかるでしょう。2つ目の記事では、データの可用性、データの有効性、シャードの破損など、より高度なトピックを取り上げます。

 本稿執筆時点で最も利用されている汎用ブロックチェーンであるEthereumは、メインチェーン上で1秒間に20未満のトランザクションしか処理できないことはよく知られています。この制限は、ネットワークの人気と相まって、高いガス価格（ネットワーク上で取引を実行するためのコスト）と長い確認時間につながっています。この記事を書いている時点では、約10～20秒ごとに新しいブロックが生成されているにもかかわらず、ETH Gas Stationによると、取引がブロックチェーンに追加されるまでに実際にかかる平均時間は1.2分です。スループットの低さ、価格の高さ、レイテンシーの高さのすべてが、Ethereumを、採用に合わせて拡張する必要のあるサービスの運営には適していないと言えるでしょう。

 Ethereumのスループットが低い主な理由は何でしょうか？その理由は、ネットワーク内のすべてのノードがすべてのトランザクションを処理する必要があるからです。スループットの問題をプロトコルレベルで解決するために、開発者は多くのソリューションを提案してきました。これらの解決策は主に、すべての計算を少数の強力なノードに委ねるものと、ネットワーク内の各ノードが総作業量のサブセットのみを行うものに分けられます。前者の極端な例としては、1つのノードですべてのトランザクションを処理するThunderがあり、Ethereumの100倍にあたる1200tx/secを達成したと主張しています（ただし、私はThunderを支持していませんし、彼らの主張の正当性を証明するものでもありません）。Algorand、SpaceMesh、Solanaはすべて前者のカテゴリーに当てはまり、コンセンサスやブロックチェーン自体の構造に様々な改良を加えて、大幅に多くのトランザクションを実行していますが、それでも（非常に強力ではあるものの）1台のマシンが処理できる範囲に制限されています。

 後者の、参加しているすべてのノードに作業を分割する方法は、シャーディングと呼ばれています。これが、Ethereum Foundationが現在計画しているEthereumのスケーリング方法です。この記事を書いている時点では、完全な仕様はまだ公表されていません。私はEthereumのシャードチェーンの詳しい概要と、そのBeaconチェーンのコンセンサスをNearのものと比較した記事を書きました。

 Near Protocolはシャーディングの構築も行っています。Nearのチームには、シャーディング、クロスシャードトランザクション、分散JOINの構築を担当した3人の元MemSQLのエンジニアと、5人の元Googleのエンジニアがおり、分散システムの構築に関する業界の大きな専門知識を持っています。

 この記事では、Nearと他のシャーディングプロトコルの大半がベースにしている、ブロックチェーンシャーディングの中核的な考え方をまとめました。次の記事では、シャーディングのより高度なトピックについて説明します。

 web3スペースの起業家の方は、同スペースのTier1企業や投資会社のメンターが参加する私たちのアクセラレータへの参加をご検討ください。http://openwebcollective.com/。市場の特定、BD、マーケティング、資金調達など、ビジネスを構築するためのあらゆる側面をサポートします。

最もシンプルなシャーディング、通称Beanstalk

 まずは最もシンプルなシャーディングのアプローチから始めましょう。本稿ではBeanstalkと呼びます。これは、Vitalikがこのプレゼンテーションで"scaling by a thousand altcoins"と呼んでいるものでもあります。

 このアプローチでは、1つのブロックチェーンを運用するのではなく、複数のブロックチェーンを運用し、それぞれのブロックチェーンを"シャード"と呼ぶことにします。各シャードはそれぞれのバリデータを持ちます。以下では、取引を検証したり、ブロックを生成したりする参加者を総称して"バリデータ"と呼びます。ここでは、各シャードが互いに通信しないものと仮定すします。

 Beanstalkのデザインはシンプルですが、シャーディングの主要な課題を説明するには十分です。

バリデータのパーティショニングとビーコンチェーン

第一の課題は、各シャードがそれぞれのバリデータを持つことで、各シャードの安全性がチェーン全体の10倍になってしまうことです。つまり、X個のバリデータを持つ非シャード化チェーンがハードフォークでシャード化チェーンに移行し、X個のバリデータを10個のシャードに分割した場合、各シャードにはX/10個のバリデータしかなく、1つのシャードを破損させるには、バリデータ総数の5.1%(51% / 10)を破損させればよいことになる。

 ここで2つ目のポイント、"誰が各シャードのバリデータを選ぶのか"にたどり着きます。5.1%のバリデータを支配することは、その5.1%のバリデータがすべて同じシャードにいる場合にのみダメージを与えます。バリデータがどのシャードで認証するかを選べない場合、5.1%のバリデータをコントロールしている参加者が、すべてのバリデータを同じシャードに集める可能性は非常に低く、システムを危険にさらす能力は大幅に低下するでしょう。

画像2

 今日、ほとんどのシャーディングの設計は、バリデータをシャーディングに割り当てるために、何らかのランダム性のソースに依存しています。ブロックチェーン上のランダム性自体は非常に難しいテーマであり、後日、別のブログ記事を書くべきでしょうが、今のところ、使用できるランダム性のソースがあると仮定しましょう。

 ランダム性とバリデーターの割り当てには、特定のシャードに依存しない計算が必要です。この計算のために、既存のデザインでは、ネットワーク全体の維持に必要な処理を行うブロックチェーンを別に用意しています。これらのオペレーションには、乱数の生成やバリデーターのシャードへの割り当ての他に、シャードからのアップデートの受信やスナップショットの取得、Proof-of-Stakeシステムでのステークやスラッシュの処理、その機能がサポートされている場合のシャードのリバランスなどが含まれることが多いです。このようなチェーンは、EthereumやNearではBeaconチェーン、PolkaDotではRelayチェーン、CosmosではCosmos Hubと呼ばれています。

 この記事では、このようなチェーンをBeaconチェーンと呼ぶことにします。Beacon チェーンの存在により、次の興味深いトピックである二次シャーディングが登場します。

二次シャーディング

 シャーディングは、ネットワーク運用に参加するノードの数に応じて無限にスケールするソリューションとしてよく宣伝されています。理論的にはそのようなシャーディングソリューションを設計することは可能ですが、Beaconチェーンの概念を持つソリューションは、無限のスケーラビリティを持ちません。その理由を理解するために、Beaconチェーンは、バリデータのシャードへの割り当てやシャードチェーンブロックのスナップショットなど、システム内のシャード数に比例した帳簿計算を行わなければならないことに注意してください。Beaconチェーンはそれ自体が1つのブロックチェーンであり、それを運用するノードの計算能力によって計算が制限されるため、シャードの数は当然制限されます。

 しかし、シャード化されたネットワークの構造は、そのノードの改善に乗算効果を与えます。例えば、ネットワーク内のノードの効率を任意に向上させ、トランザクション処理時間を短縮した場合を考えてみましょう。

Beaconチェーンのノードを含め、ネットワークを運用するノードが4倍速くなれば、各シャードは4倍多くのトランザクションを処理できるようになり、Beaconチェーンは4倍多くのシャードを維持できるようになります。システム全体のスループットが4×4＝16倍になることから、Quadratic Shardingと名付けられました。

 今日、どれだけの数のシャードが実行可能であるかを正確に測定することは困難ですが、予見可能な将来において、ブロックチェーンユーザーのスループットニーズが2次シャードの限界を超えることはないと思われます。このような量のシャードを安全に運用するために必要なノードの数は、現在すべてのブロックチェーンを運用しているノードの数を合わせても、桁違いに多いのです。

 しかし、将来性のあるプロトコルを構築したいのであれば、この問題に対する解決策の研究を今日から始める価値があるかもしれません。現時点で最も発展している提案は、エクスポネンシャルシャーディングです。これは、シャード自身がツリーを形成し、それぞれの親シャードが一連の子シャードを指揮し、自身も他のシャードの子になることができるというものです。

 Vlad Zamfirは、ビーコンチェーンを使わないシャーディングの設計に取り組んでいることで知られています。私は彼と一緒にプロトタイプの1つを作りましたが、その詳細な概要はこちらです。

State Sharding

 これまでは、ネットワークがシャードに分割されたときに、具体的に何が分離され、何が分離されないのか、あまりよく定義されていませんでした。具体的には、ブロックチェーンのノードは、1）取引を処理するだけでなく、2）検証された取引や完了したブロックを他のノードに中継する、3）ネットワーク全体の台帳の状態や履歴を保存する、という3つの重要なタスクを実行しています。これらの3つのタスクは、それぞれネットワークを運用するノードに増大する要求を課しています。

1.トランザクションを処理する必要があるため、処理するトランザクション数の増加に伴い、より多くの計算能力が必要になります。

2.トランザクションやブロックを中継する必要があるため、中継するトランザクションの数が増えると、ネットワークの帯域幅が必要になります。

3.データを保存する必要があるため、状態が大きくなるとより多くのストレージが必要になります。重要なのは、処理能力やネットワークとは異なり、トランザクションレート（1秒間に処理されるトランザクションの数）が一定であっても、ストレージの必要性は増大するということです。

 上記のリストを見ると、1秒あたりのトランザクション数が変わらなくても時間の経過とともに増加しているのはストレージだけなので、ストレージの要件が最も差し迫っているように見えるかもしれませんが、実際には現在最も差し迫った要件は計算能力です。この記事を書いている時点でのEthereumの全体の状態は100GBで、ほとんどのノードで簡単に管理できます。しかし、Ethereumが処理できるトランザクションの数は約20で、多くの実用的なユースケースに必要なものよりも桁違いに少ないです。

 Zilliqaは、処理はシャーディングしますがストレージはシャーディングしない最も有名なプロジェクトです。処理のシャード化は、各ノードが全体の状態を持っているので簡単な問題です。つまり、コントラクトは自由に他のコントラクトを呼び出し、ブロックチェーンからあらゆるデータを読み取ることができます。状態の同じ部分を更新する複数のシャードからの更新が衝突しないようにするには、慎重なエンジニアリングが必要です。その点、Zilliqaは非常に単純化されたアプローチをとっており、私はこの記事でそれを分析しています。

 処理のシャーディングを伴わないストレージのシャーディングは提案されていましたが、私はそれに取り組んでいるプロジェクトを知りません。したがって、実際には、ストレージのシャーディング（ステートシャーディング）は、ほとんどの場合、処理のシャーディングとネットワークのシャーディングを意味します。

 実際、ステートシャーディングでは、各シャードのノードは、そのシャードに割り当てられたグローバルステートのローカルな部分にのみ影響するトランザクションを含む独自のブロックチェーンを構築しています。したがって、シャード内のバリデータは、グローバルステートのローカルパートを保存するだけでよく、ステートのローカルパートに影響を与えるトランザクションのみを実行し、それを中継するだけでよいのです。このように分割することで、計算能力、ストレージ、ネットワークの帯域幅の要件は直線的に減少するが、データの可用性やシャード間のトランザクションなど、新たな問題が発生します。

クロスシャードトランザクション

 モデルとしてのBeanstalkは、シャーディングに対してあまり有用なアプローチではありません。なぜなら、個々のシャーディングが相互に通信できなければ、それらは複数の独立したブロックチェーンと変わらないからです。シャーディングが利用できない現在でも、様々なブロックチェーン間の相互運用性が求められています。

 ここでは、各参加者がちょうど1つのシャードにアカウントを持っているような、単純な支払い取引だけを考えてみよう。同じシャード内であるアカウントから別のアカウントに送金したい場合、 その取引はそのシャードのバリデータだけで処理することができる。しかし、シャード#1に住むアリスがシャード#2に住むボブに送金したい場合、 シャード#1のバリデータ(ボブの口座にお金を貸すことができません)も シャード#2のバリデータ(アリスの口座からお金を引き落とすことができません）も 全ての取引を処理することはできません。

 クロスシャード取引には2つのアプローチがあります。

・Synchronous:シャードを越えたトランザクションを実行する必要があるときには、複数のシャードでそのトランザクションに関連する状態遷移を含むブロックが同時に生成され、複数のシャードのバリデータが協力してそのようなトランザクションを実行することができます。私が知っている最も詳細な提案はMerge Blocksで、ここで説明されています。

・Asynchronous:複数のシャードに影響するクロスシャードトランザクションは、それらのシャードで非同期的に実行され、"クレジット"シャードは"デビット"シャードが自分の部分を実行したという十分な証拠を得た後に、自分の部分を実行します。この方法は、シンプルで調整が容易なため、一般的に広く普及しています。現在、Cosmos、Ethereum Serenity、Near、Kadenaなどで提案されています。この方式の問題点は、ブロックが独立して生成される場合、複数のブロックのうちの1つが孤児になる可能性がゼロではないため、トランザクションが部分的にしか適用されないことにあります。下の図は、フォークに遭遇した2つのシャードと、ブロックAとX'に記録されたシャード間のトランザクションを表しています。A-BおよびV'-X'-Y'-Z'のチェーンが対応するシャードで正規のものとなった場合、そのトランザクションは完全に確定されます。A'-B'-C'-D'とV-Xが正統なものになれば、その取引は完全に放棄されたことになり、これは受け入れられます。しかし、例えばA-BとV-Xがcanonicalになった場合、トランザクションの1つの部分が確定し、1つの部分が放棄されることになり、アトミックな失敗が生じます。この問題が提案されているプロトコルでどのように対処されているかについては、第2部で、シャードプロトコルで提案されているフォークチョイスルールとコンセンサスアルゴリズムの変更について取り上げる予定です。

画像3

  なお、チェーン間のコミュニケーションは、シャード化されたブロックチェーン以外でも有用です。チェーン間の相互運用性は複雑な問題で、多くのプロジェクトが解決しようとしています。シャーデッドブロックチェーンでは、ブロック構造とコンセンサスがシャード間で同じであり、調整に使えるビーコンチェーンがあるので、問題は幾分簡単です。しかし、シャード型ブロックチェーンでは、すべてのシャードチェーンが同じであるのに対し、グローバルなブロックチェーンのエコシステムでは、対象となるユースケースや分散化、プライバシーの保証などが異なる、たくさんの異なるブロックチェーンが存在します。

 異なる特性を持ちながらも、十分に類似したコンセンサスとブロック構造を使用し、共通のビーコンチェーンを持つ一連のチェーンのシステムを構築することで、相互運用性サブシステムが機能する異種ブロックチェーンのエコシステムを実現することができます。このようなシステムでは、バリデータのローテーションが行われる可能性は低いため、セキュリティを確保するためにいくつかの特別な措置を講じる必要があります。CosmosとPolkaDotは、事実上そのようなシステムです。CosmosのZaki Manian氏によるこの記事では、2つのプロジェクトの重要な側面の詳細な概要と比較が示されています。

悪意のある行動

 これで、ビーコンチェーン、バリデータのローテーション、クロスシャードのトランザクションなど、シャーディングがどのように実装されているかを理解できたと思います。

 これらの情報を踏まえた上で、最後にもう一つ重要なことを考えてみましょう。具体的には、悪意のあるバリデータがどのような敵対行為を行うかということです。

悪意あるフォーク

 悪意のあるバリデータの集合がフォークを作ろうとするかもしれない。根本的なコンセンサスがBFTであるかどうかは問題ではなく、十分な数のバリデータを破損させれば、常にフォークを作ることができるということに注意してください。

 1つのシャードの50%以上が破損する可能性は、ネットワーク全体の50%以上が破損する可能性よりもはるかに高いと言えます（これらの確率については後編で詳しく説明します）。上述したように、クロス・シャード・トランザクションは複数のシャードで特定の状態変化を伴い、そのような状態変化を適用するシャード内の対応ブロックは、すべてがファイナライズされる（すなわち、対応するシャードの選択されたチェーンに表示される）か、またはすべてがorphanになる（すなわち、対応するシャードの選択されたチェーンに表示されない）必要があります。一般的にシャードが破損する確率は無視できないので、シャードの検証者の間でbyzantine的なコンセンサスが得られたとしても、あるいは状態が変更されたブロックの上に多くのブロックが生成されたとしても、フォークが起こらないと仮定することはできません。

 この問題には複数の解決策がありますが、最も一般的なものは、最新のシャードチェーンブロックをビーコンチェーンに時折クロスリンクさせることです。そして、シャードチェーンのフォーク選択ルールは、常にクロスリンクされたチェーンを優先し、最後のクロスリンク以降に公開されたブロックに対してのみシャード固有のフォーク選択ルールを適用するように変更されます。フォークチョイス・ルールとは何かについては、後編で詳しくお話しし、シャード型ブロックチェーンのフォークチョイス・ルール案の詳細な分析を行います。

無効なブロックの承認

 一連のバリデータは、状態遷移関数を誤って適用したブロックを作成しようとするかもしれません。例えば、アリスが10トークン、ボブが0トークンを持っている状態から始めて、ブロックにはアリスからボブに10トークンを送るトランザクションが含まれているかもしれませんが、最終的にはアリスが0トークン、ボブが1000トークンを持っている状態になります。

画像4

  シャード化されていない古典的なブロックチェーンでは、ネットワークの参加者全員がすべてのブロックを検証しているため、このような攻撃は不可能です。このような無効な状態遷移を持つブロックは、他のブロック生産者と、ブロックを作成しないネットワークの参加者の両方から拒否されます。悪意のある検証者が、そのような無効なブロックの上に、誠実な検証者が正しいチェーンを構築するよりも早くブロックを作成し続け、その結果、無効なブロックを含むチェーンが長くなったとしても、ブロックチェーンを何らかの目的で使用しているすべての参加者がすべてのブロックを検証し、無効なブロックの上に構築されたすべてのブロックを破棄しているため、問題にはなりません。

画像5

 上の図では5人のバリデータがいますが、そのうち3人は悪意を持っています。彼らは無効なブロックA'を作成し、その上に新しいブロックを構築し続けました。誠実な2人の検証者はA'を無効と判断し、最後に確認できた有効なブロックの上に構築してフォークを作りました。誠実なフォークの方が検証者の数が少ないので、チェーンは短くなります。しかし、古典的な非シャード型ブロックチェーンでは、ブロックチェーンを何らかの目的で使用するすべての参加者が、受け取ったすべてのブロックを検証し、状態を再計算する責任を負います。したがって、ブロックチェーンに関心を持つ人は誰でも、A'が無効であることを観察し、B'、C'、D'を即座に破棄して、A-Bのチェーンを現在最も長く有効なチェーンとします。

 しかし、シャード化されたブロックチェーンでは、すべての参加者がすべてのシャードのすべての取引を検証することはできません。そのため、ブロックチェーンのどのシャードの歴史においても、無効なブロックが含まれていなかったことを確認する何らかの方法が必要となります。

 フォークの場合とは異なり、Beaconチェーンへのクロスリンクは十分な解決策ではないことに注意してください。Beaconチェーンはブロックを検証する能力を持っていないからです。Beaconチェーンが検証できるのは、そのシャードの十分な数のバリデータがブロックに署名していること(そしてそのブロックが正しいことを証明していること)だけです。

この問題に対する解決策は2つしかないと思っていますが、どちらも現在では満足できるものではありません。

1.状態遷移を誤って適用しようとした場合に、システムに警告を発する何らかの合理的なメカニズムを用意すします。各シャードがある種のBFTコンセンサスを実行していると仮定すると、特定のシャードにおける悪意のあるバリデータの数が⅔未満である限り、少なくとも1人の誠実なバリデータがブロックを認証し、状態遷移関数が正しく適用されていることを検証する必要があります。もしノードのうち⅔以上が悪意のあるノードであれば、一人の誠実なノードが参加しなくてもブロックを確定することができます。シャード内の少なくとも1つのノードが悪意を持っていないと仮定すると、そのようなノードがどのようなブロックが生成されているかを監視し、無効な状態遷移を持つノードに挑戦するのに十分な時間を確保できるようなメカニズムが必要です。

2.状態遷移が正しく適用されていることを証明するのに十分ですが、状態遷移関数を実際に適用するよりも大幅に安価に検証できる情報をブロック内に用意する必要があります。これを実現する最も近いメカニズムはzk-SNARKですが（"zk"、つまりゼロ知識の部分は本当に必要ではなく、非zkのSNARKで十分です）、現時点ではzk-SNARKの計算には時間がかかることで有名です。

アウトロ

 以上の情報により、Beaconチェーンの概念、計算対状態のシャーディング、クロスシャードのトランザクションなど、シャーディングの重要な側面のほとんどをご理解いただけたと思います。後編の"シャーディング201"では、攻撃防止についてより深く掘り下げますので、ご期待ください。

 また、Discordチャンネルでは、コンセンサス、経済性、ガバナンスなど、Near Protocolの技術的および非技術的な側面について議論していますので、ぜひご参加ください。

・https://discord.gg/nqAXT7h

 また、最近、コードをオープンソース化しました。詳しくはこちらをご覧ください。

 TwitterでNear Protocolをフォローして、Sharding 201を含む今後のブログ記事やその他の発表を見逃さないようにしてください。

・http://twitter.com/nearprotocol

・http://twitter.com/AlexSkidanov

 最後になりましたが、私たちのニュースレターをご購読ください。隔週で最新情報をお送りしており、発売に向けた進捗状況を知るには最適なチャンネルです。

 この記事の初期段階で多くの貴重なフィードバックをいただいたKadenaのMonica Quaintance氏とCosmosのZaki Manian氏に感謝します。


この記事が気に入ったらサポートをしてみませんか？