時間と状態の分離

多くのスマートコントラクトプラットフォーム（例：Ethereum 2.0、Polkadot、DFinity、Near Protocol、Algorand、Kadena、Spacemesh、Solana）が今後1年から2年で立ち上げられる予定です。各チームは、独自の拡大戦略を追求しています。

しかし、これらのアプローチのほとんどは、ビザンチン環境における分散型コンピューティングシステムの根本的な問題の1つであるクロック問題を解決できていません。コンセンサスに至るために、ネットワーク上のマシンの最低でも51%が、同時に同じ順序で同じトランザクションを実行する必要があります。そうするために、マシンはグローバルクロックに合意する必要があります。この「クロック問題」は、多くの疑わしいマシンにビザンチン設定のグローバルクロックに合意させるという課題です。一旦全員がグローバルクロックに合意してしまえば、各トランザクションが、同じグローバルクロックを使用してタイムスタンプを押すため、トランザクションの順序づけは、大変シンプルな問題になります。

クロック問題は、現代の暗号時代以前でも、他の大規模なネットワーク、最もよく知られているのは、無線通信の世界で既に現れていました。携帯電話の基地局は、一度に何万もの携帯電話をサポートしなければなりません。各携帯電話に個別に無線周波数を持たせて送信できるほどの帯域幅はありませんでしたので、通信会社は、同じ周波数に複数の携帯電話を押し込む「複数のアクセス技術」を必要としました。

符号分割多元接続（CDMA）は、第2次世界大戦中に発明されたものです。クロック問題に対応するため、CDMAは各電話が独自の鍵でデータを暗号化し、他の電話と同時にいくつかの周波数にわたって送信することを求め、基地局が組み合わさった信号を個別の電話に振り分けました。このスキーマの効率性は暗号スキーマの複雑さと同様のスピードで改善されます。安価なデバイスをサポートしなければならない広く利用可能なネットワークに、この改善スピードは、歴史的に見るとゆっくりですが、確実に行われてきました。

電話会社は、時分割多元接続（TDMA）を導入することで、はるかに速く効率向上を達成してきました。これは、2G携帯電話ネットワークが登場して以来、クロック問題を解決する標準ソリューションとなっています。TDMAは、基地局が各無線周波数をタイムスロットに分割し、これらのタイムスロットを各携帯電話に振り分けます。この方法で、携帯基地局は、ネットワークに世界中で利用可能なクロックを提供しています。これは、各周波数が複数の同時データチャネルをサポートし、同時に同じ周波数で交信する複数の携帯電話からの干渉を削減させることにより、限定された帯域幅の拡張性を大きく向上させています。

この記事では、異なるブロックチェーンがビザンチン設定での時間の問題をどのように対処しているかを説明します。最も効果的なクロックを構築するブロックチェーンが時間と状態をうまく分離し、安全かつ分散型の方法で何百万ものユーザーのスループットをサポートするように拡大できるようになるかについて意見を述べて結論づけるつもりです。

クロックとの分散型コンセンサス

GoogleのSpannerデータベースは、18インスタンスがすべてロックステップ方式でトランザクションを実行する世界で最大のパーフォーマンスを誇る分散型データベースの1つです。これは、5万＋TPS（1秒当たりのトランザクション）を1秒未満のTTF（ファイナリティまでの時間）でサポートします。Spannerは、1989年に初めて公開されたPaxosコンセンサスアルゴリズムを利用しています。Spannerは、パーミッションレスで信頼できるデータベースです。Paxosにより、Spannerは停電、サーバーの障害、悪意あるバグ、そして多くの他の障害に際しても稼働し続けることが可能です。

最高のスループットを誇るブロックチェーンがたった21インスタンスで5,000＋のTPSを達成するのに苦労している現在、どのようにしてPaxosはそのようなパフォーマンスを実現しているのでしょう？Googleはフルタイムのエンジニアをオンサイトで採用し、定期的に各データセンターの原子時計を大変高い精度で同期させています。グローバルに利用可能な信頼できるクロックを提供することにより、トランザクションにタイムスタンプでき、そのため各インスタンスが、トランザクションをバラバラに受け取っても、正しい順序で処理することができるのです。これは時間と状況の分離です。ピアが同じ順序で同じ行動を実行するよう互いに確認する必要なしに各インスタンスが状態をアップデートするためです。

Spannerから何を学べますか？非ビザンチン設定でグローバルに利用可能なクロックがあるなら、コンセンサスに至るのは簡単です。残念ながら、今日のスマートコントラクトプラットフォームには、Spannerにはない余分な制約が2つあります。

1. バリデータになるには、プラットフォームの検閲耐性を維持するためにパーミッションレスである必要があります。
2. ブロックチェーンでは、バリデータの1/3までが悪意を持つものである場合でも、ユーザーの資金を安全に保たなければなりません。

世界中のどこででも、誰もがバリデータインスタンスをスピンアップできるのなら、コンセンサスアルゴリズムは、異なるハードウェアやネットワーク構成を許容できるように設計されていなければならず、悪質なバリデータに対応することも必要です。さらに、真の検閲耐性を持つために、帯域外の情報は信用できません。（いわゆるオラクル問題）

Paxosの発明から20年後、コンピュータのパーミッションレスネットワークをトランザクションの正規順序についてコンセンサスに至らせる方法を見つけた人がいます。この人こそが、Satoshi Nakamotoであり、そのソリューションがProof-of-Work（PoW）コンセンサスだったのです。

Proof of Work + タイムチェーン = クロック

つまり、Satoshiのリリース前のBitcoin Codeは、なじみのあるブロックチェーンデータストラクチャを「タイムチェーン」と呼んでいました。このタイムチェーンは、（この記事では記載していないPoWの精巧な掛かり合い、困難調整、最も長いチェーンルールを介して）平均10分毎に時を刻むよう設計されています。そこでの各動作は、グローバルの状況を更新するトランザクションのブロックの形式になります。ノードがトランザクションのブロックを実行した後、自身の有効な新しいブロックを生成する、あるいはネットワークから有効な新しいブロックを受け取るまで、いかなる状況の更新もできないようロックされます。PoWでは、時間と状態が結び付けられており、常に一緒に進んでいます。時間は、状態の更新をするまで進めません。

ブロックを「有効」にするのは何かということは、熱く議論されています。トランザクションのフォーマットとブロックサイズは、考慮される多くの品質のうちの2つにすぎません。議論に上がっていない有効なブロックの一側面は、それが前のブロックのハッシュを含む必要がありそのため、ネットワークは、そのブロックをタイムチェーンの前のブロックの後に置くことを知るのです。

画像：ブロックチェーンの各ブロックは、その後に来た証として、前のブロックのハッシュを含んでいます。

タイムチェーンの目的は、上記#2の要件を満たすことです。つまり、バリデータになるにはパーミッションレスでなければなりません。Bitcoinネットワークの現在の状態が有効であると確認する唯一の方法は、ジェネシスブロックの状態からスタートし、ジェネシスから現在の状態までの各トランザクションを実行することです。高さ12のブロックでトランザクションが起こり、高さ11のブロックでのトランザクションの後に実行されなければならないということを証明することにより、タイムチェーンは新しいバリデータが従う監査トレイルを提供します。ブロック12は、ブロック11のハッシュを含む必要があるため、ブロック12は、ブロック11の後に作成されることになるのです。このハッシュのタイムチェーンは、イレギュラーかつあまり粒度が細かくありませんが、、帯域外の情報がなければネットワーク上のいかなるバリデータも独立して検証できない、論理的、単調クロックを生成します。

オープンでパーミッションレスな設定で、この世界的に利用可能で、信頼できるクロックを作成したことは、Satoshiの最大のイノベーションです。新しいブロックでグローバルクロックが進むまで、グローバルな状態がロックされるため、拡張性の数学はシンプルです。

スループット[TPS] =ブロックサイズ[ブロック毎txs] / ブロック時間 [ブロックごとの秒数]

スループットを増やすには、プロトコルが、ブロックサイズを大きくするか、ブロック時間を小さくするかしかありません。ブロックサイズを大きくすると、ブロックプロデューサーの分散性が損なわれ、ブロック時間を短くすると、チェーンフォークの確率が増します。

時間と状態は組み合わさっているため、これを回避する方法はありません。

無線通信の例に戻って、この問題をCDMAと比べてみましょう。CDMAでは、電波塔には、聞こえる周波数の固定帯域幅があります。つまり、どのようにブロックプロデューサーが処理できる固定のブロックサイズを持てるかに似ています。CDMAの拡張性を高めるということは、限られた帯域幅に、より多くの電話通話を行えるようにより複雑なエンコーディングスキームを創り出すということを意味します。これは、パフォーマンスの向上を可能にするより複雑なエンコードスキームである、Segwit、Lightningチャネル、Schnorr署名に似ています。

Bitcoinは、1MBのブロック、600秒ブロックタイム、250B最低トランザクションサイズを持ち、その量は、理論上最大7 TPSのスループットになります。つまり、（確率的に、非可逆的ファイナリティに到達するのに6ブロックタイムかかるため）Spannerと比較して、スループットで最大7,000倍低く、TTFで3,600倍遅いことになります。

明らかに改善の余地があります。

Proof of Stake + タイムチェーン = より高速なクロック

Bitcoinの成長は、コンセンサスアルゴリズム研究にルネッサンスを引き起こしました。CAP定理は、ネットワークパーティション時に、分散型データベースシステムは一貫性（ネットワーク停止）か、可用性（ネットワークフォーク）のどちらかを選択しなければならないと言っています。Satoshiのアルゴリズムは、そのすべてで一貫性ではなく可用性を選択する、Nakamotoコンセンサスファミリーで最初のパーミッションレス、BFTコンセンサスアルゴリズムでした。Nakamotoファミリーには、多くのコンセンサスアルゴリズムがあります。

Leslie LamportのPaxosアルゴリズムは、クラシカルコンセンサスファミリーで可用性の代わりに一貫性を優先する最初のものでした。

Paxosやクラッシカルコンセンサスファミリーの他の多くのアルゴリズムでは、コンセンサスに参加する各ノードは、状態をアップデートするたびに、同期的にネットワーク上の他の各バリデータと通信する必要があります。これにより、コミュニケーションの複雑さO(n^2)（nはバリデータカウント）を引き起こします。つまり、各状態アップデート間に必要な時間がバリデータカウントが増すにつ入れ指数関数的に増加するということです。

Jae KwonとEthan Buchmanは、クラシカルコンセンサス研究に20年を費やし、それに、安全にバリデータカウントを制限する結合型プルーフオブステーク（BPoS）と呼ばれる暗号経済のインセンティブ構成を吹き込んだ最初の人たちです。彼らの仕事の結果が、クラシカルコンセスファミリーで最初の高性能の、パーミッションレス、BFTコンセンサスアルゴリズムであるTendermintです。

Nakamotoコンセンサスと同様、Tendermintは、時間と状態の更新を結びつけるため、ブロックサイズが大きくなるか、ブロック時間が短くなる時のみ、スループットが増します。Bitcoinが2009年に発明された際、ブロックタイム10分は、十分に合理的でした。しかし、以来帯域幅が指数関数的に大きくなり、そのためTendermintチェーンではブロックタイムがたった数秒にまで縮まりました。

Tendermintは一貫性を選択したため、フォークが不可能になったので、ブロックタイムを特定のバリデータカウントのネットワークスループットボトルネックシステムパフォーマンスの限界まで縮小できます。今日、Tendermintでは、ネットワークが安全にバリデータカウントを100に制限できるようにしており、これにより十分な帯域幅を持たないノードを排除し、より大きなブロックサイズを許容するというすばらしい利点を持っています。

Tendermintは現在作成中です。（最初のTendermintライブインスタンスである）Cosmos Hubは、150KBのブロックで6秒のブロックタイムで実行しています。これにより、（250バイトのトランザクションと仮定すると）最大スループットは100 TPSになります。しかしこれは生まれて数か月にすぎず、速やかに成熟していくでしょう。理論上、5秒のブロックタイムと5MBのブロックをもつTendermintネットワークは、Bitcoinと比較して検閲耐性とパーミッションレスの犠牲を最小化したうえで、4,000 TPSに達することが可能です。これは、スループットで570倍の増加、TTFで720倍の減少です。

残念ながら、クラシカルコンセンサスアルゴリズムの同期性の性質により、Spannerとのマッチングは、システムの検閲耐性やパーミッションレスプロパティに悪影響をもたらすでしょう。より大きなブロックは、ネットワークを伝わるのにより時間がかかり、バリデータが確認するのにも時間がかかるのは避けらず、ブロックタイムの引き下げに歯止めを掛けます。クロックスピードを上げるためには、バリデータの数を大幅に減らす必要があり、すべてを同じファイバーネットワークに直接つなげる必要があります。これにより、バリデータの結託の可能性と、新しいバリデータの参加の障壁の両方を増すことになり、また、ファイバーネットワークのオペレーターを中央集権型のポイントにすることになります。

ブロックチェーンコンセンサスの次の進化は、時間と状態を分離し、大きなスループットの増加を得る一方で、コストがかなり高くなるという、重要な進展を遂げることです。

シャーディング +タイムチェーン = 独立クロック

BPoSを用い、Tendermintは、検閲耐性をバリデータの数から切り離し、それによりネットワークのクロックを600秒毎から5秒毎に速め、大きなパフォーマンス改善を行いました。しかし、クロックが打つ間、全体のグローバル状態がグローバルコンシスタント状態を維持するためにロックされます。

この問題を緩和する1つの方法は、グローバル状態をより小さな欠片の塊に分け、それぞれ独立したクロックで個別にそれぞれ進行させることです。これらのシャードは、互いにやり取りする必要がない限り、各シャードのパフォーマンスは変わらず、すべてのシャードにわたる総スループットはシャードの数と比例して増加します。

Cosmosは、並行して存在する多くの独立したネットワークを思い描いています。これらのネットワークは互いに価値を転送可能だが、ほとんどの取引は同じシステム内で行われるというものです。各ネットワークが、4,000 TPS処理可能で、13の異なるネットワークが存在すれば、システム全体では、Spannerを上回る52,000 TPSが可能です！しかし、このアプローチには2つの問題があります。

1. Proof-of-Stakeのブロックチェーンのセキュリティは、33%のステークされたトークンを獲得し、無効なトランザクションを承認するコストにより測定されます。単一のトークンを供給する代わりに、13の別々のネットワークがあれば、特定のネットワークの33%の獲得コストは、大幅に削減されます。これは、安全性がはるかに低く、ブロックチェーンの価値命題を大きく損ないます。ブロックチェーンでは安全性がネットワークの価値の機能なのです。
2. ネットワーク間の転送のTTFは、ネットワーク内の転送に比べ、最低でも4倍に増加します。ネットワークは、クロックを同期させるために何度も通信し、AliceがBobにトークンを送る際、Aliceのネットワークでトークンを焼却する前にBobのネットワークでBobが確実にその価値を受け取れるようにしなければなりません。

Cosmosは、Ethereum2.0、Polkadot、Algorand、Dfinity、Near Protocolといった自身のセキュリティを管理する多くのソブリンネットワークとともに、世界が少なくともシャードのセキュリティ問題（上記#1）を是正するシステムを構築していくと見ています。各チームのアプローチには少々の違いはありますが、基本となるアーキテクチャは、双方とも他のネットワークにクロックを提供する単一のビーコンチェーンを含み、シャードにまたがって安全にバリデータをシャッフルし、そのため全員で共通のセキュリティプールをします。Cosmosのように、スループットを増やすことは簡単です。ただ、もっとシャードを追加すればいいのです。

画像：Ethereum2.0のシングルチェェーンとシャード状態

残念ながら、ネットワーク間転送の高TTF問題（上記#2）は依然存在します。ビーコンチェーンが、グローバルクロックを提供しても、各シャードは、ローカルクロックを定期的にビーコンチェーンのクロックと同期します。AliceがトークンをシャードAから、BobのシャードBに送信するためには、シャードAにあるバリデータがシャードBのバリデータが、Bobのために、同量のトークンをミントする前に、Aliceのトークンを焼却したことを証明する必要があるのです。Ethereum 2.0の現在の設計では、このプロセスに6分かかります。これは、シャード間ブロックタイムの60倍の時間です。

シャーディングは役立ちますが、各シェードで時間と状態が組み合わされるという事実を鑑みて基本的な拡張性の限界が予測されます。各シェードは、ブロックサイズとブロックタイムに関してTendermintが直面している同じ制約によりいまだ縛られています。

シャーディングはTDMAのある要素に類似しています。携帯電話の基地局が、帯域幅を別々のラジオ周波数とタイムスロットに分割のと同様のやり方で、状態がそれぞれ個別のクロックとともに別々のシャードに分離されます。この利点は明らかですが、シャード間のレイテンシーによって明らかにされているように、十分に利用されていません。

しかし、時間と状態の更新をパーミッションレス設定で完全に分離することができるとすればどうなのでしょうか？

時間と状態を分離する

ここまで、Satoshiがタイムチェーンデータ構造を作成し、トラストレスクロックをBitcoinネットワークに提供した方法と、KwonとBuchmanが、BPoSをPaxosに適用し、安全にバリデータの数を減らし、Tendermintネットワークのクロックスピードを上げた方法、そしてネットワークを独立したクロックとともに多くのピースにシャーディングすることにより（シャード間トランザクションが最小化される限り）スループットを大きく増加させる方法を見てきました。しかし、これらのひとつひとつの進展を通じて、状態と時間の更新がいまだ連携し続けており、状態の更新は、クロックが進むのに合わせてしか行われないこと、そしてこのことは、検閲耐性のあるパーミッションレスなコンピューティングネットワークのスループットとファイナリティまでの時間に根本的な限界をもたらしていることを記してきました。

時間と状態を分離するには、高速かつ正確で、トラストを最小化させる世界的に利用可能なクロックが必要です。このようなクロックがあれば、Spannerで行っているように、状態の更新を継続的かつ非同期的に行うことができます。グローバルクロックに全員が同意し、トランザクションがタイムスタンプされる限り、トランザクションは、ネットワークにわたって継続的に進んでいくことができます。

Solanaは、ハッシュベースのタイムチェーンを状態更新のコンセンサスから切り離すことにより、スマートコントラクトプラットフォームのトラストを最小化したクロックを構築しました。ハッシュを各ブロックにチェーンする代わりに、Solanaネットワークのバリデータは、ブロック内で継続的にハッシュ自らをハッシュします。Proof of History（PoH）と呼ばれるこのメカニズムは、同期するネットワーク上のすべてのノードに、グローバルに利用可能な、トラストを最小化した、粒度の細かいタイムチェーンを生成します。

PoHのメカニズムについての詳細は、この記事では取り扱っていません。PoHがどのように機能するかについての詳細は、SolanaのPoHのドキュメントを参照してください。

画像：Proof of Historyが標準化されたタイプスタンプをブロックチェーン上にどのように組み込むか。

この独立したタイムチェーンが存在することにより、タイムスタンプされたトランザクションが受信されるや否や、リーダーはコミュニティーに伝えることができます。タイムスタンプは、ブロックプロデューサーにより決定される任意の順序ではなく、正規順序で提供されます。ネットワーク全体で、どのトランザクションが最初に来たかに合意できるため、二重支払問題を解決するのはいまや些細なことです。

これによりすべてが変化します。

時間の流れを確認するため、バリデータに6秒から600秒ごとにコンセンサスに至るよう強制する代わりに、Solanaのバリデータは、リアルタイムでピアに状態の更新を継続的にストリーミングできます。

他のすべてのブロックチェーンのように、各バリデータが確認するのを待つ必要がなくなり、Solanaでは、（BitTorrentからヒントを得た）Turbineと呼ばれる新しいファンアウトメカニズムを使用して、O(n^2)に変わるコミュニケーションコンプレキシティO(log(n))を維持することができます。これにより、Solanaは、シャーディングを要求することなく、ファーストファイナリティを持つ単一のグローバル状態で、50,000 TPSを超える処理ができるようになります。

つまり、バリデータプールサイズは約100から1,000で、Tendermintに匹敵しますが、チェーンフォークは許可されています。チェーンフォークが現れるたびにシングルチェーン上で迅速に収束することを確実にするために、積極的なフォークマネジメントポリシーが求められ、非同期の進行と一定の可用性とのトレードオフも必要です。

もう一度無線通信の例をとりあげると、PoHは、TDMAが携帯ネットワークにもたらしたものをブロックチェーンにもたらしてくれます。Solanaの1,000のバリデータを、同期されたクロックを利用して、帯域幅を個別の時間スロットに分割する電波塔であるとイメージしてください。バリデータはコンスタントに新しいトランザクションを受け取り、それらには、それぞれ署名されたPoHハッシュが送信者によって添付されており、それらを即座に注文できる隣人にこれらのPoHハッシュを使用して転送します。リーダーはグローバルクロックに基づいて入れ替わるため、各リーダーは、オーダーされた一連のトランザクションを選択して実行し、そしてその「エントリー」をネットワークにゴシップします。バリデータは、各「エントリー」上の投票を返し、バリデータの2/3の投票を確認した時、トランザクションをファイナライズします。

ネットワークは全体として、コンスタントに、同じ順序で信じがたい量でトランザクションを処理していますが、各バリデータは独立して進行しています。他のチェーンと比較して、これは微細ではありますが、深遠なる変化です。Solanaでは、バリデータは決して進行を止めません。バリデータは、ネットワークの状況やコンセンサスにかかわらず、独立して、常に進行します。

この新しいデザインがもたらす他の直接関連しない問題（例えば、迅速なチェーンの成長、新しいプログラミングモデル、タイムチェーン、並列性の偏見を持たない能力など）がありますが、それはこの記事の範囲を超えるものです。これらは、Solanaのドキュメントで説明されています。Solanaのテストネットでは、現在5大陸をまたいだ、200のバリデータネットワーク上で、平均1.5秒のTTFで50,000 TPSに至る処理を行っています。これは、それが十分に分散型であるということを除いて、Spannerに匹敵します。

トラストを最小化し、パーミッションレスな世界のコンピュータでのこのレベルのパフォーマンスは、Solanaが時間と状態を分離したからこそ実現したのです。Solanaネットワークの世界中で利用可能なクロックにより、Spannerと同様に、各ノードが、他のどんなノードと通信する必要なく、その状態を更新することを可能にしました。

拡張性を見直す

暗号コミュニティは、拡張性とコンセンサスモデルについて嫌というほど書いてきましたが、だれも分散型クロックの問題について特に探求してきませんでした。数年にわたるそのクラスで最高のTendermint + BPoSで蓄積してきたProof-of-Stake研究と、ビーコンチェーン + 状態シャーディングアーキテクチャを中心に原則としてすべて収束する数多くのシャーディングプロポーザルにより、非同期状態で進行する粒度の細かいタイムチェーンが、一貫性よりも可用性を選択するシャーディングされていないシステムに、最高のパフォーマンスを提供します。

グローバルに利用可能なクロックを提供することにより、Solanaチームは、そうでなければ適用できない40年を超える分散型システムの研究を活用できるのです。楽観的並行性制御のようなコンセプトは1981年に発明され、長年大規模なコンピューティングプロジェクトで使用されてきましたが、時間と状態を並行して進行する必要がある場合には、適用できません。GPUを使用した並行処理は、1995年ごろから存在しましたが、NvidiaがCUDA開発環境を2007年にリリースするまで、グラフィックカードに大きく限定されてきました。しかし、トランザクションによって現在触れられているアカウントを除き、すべての状態を悲観的にロックするブロックチェーンベースのシステムで完全には利用できていません。

時間経過を理解するのは、パーミッション設定とパーミッションレス設定の両方の分散型システムのパフォーマンスにとって最重要です。時間がすべてです。Proof of Historyの形式で時間の流れをエンコードする新しい方法を用い、パーミションレスシステムは、証明済みの中央集権型クラウドコンピューティングプロバイダの性能に匹敵することができます。

この記事にフィードバックを提供してくれた、Anatoly YakovenkoとZaki Manianに感謝します。

---

スループット[TPS] =ブロックサイズ[ブロック毎txs] / ブロック時間 [ブロックごとの秒数]

#