CosmosJapanのブログ

Cosmosについてガチ解説していくブログです

Tendermintの広がり - BFTベースのPoSをパブリックチェーンへ -

この記事は、「Tendermint Explained — Bringing BFT-based PoS to the Public Blockchain Domain」の邦訳です。Keita Nakamuraさんに翻訳して頂いたものを、一部編集して掲載しました。

f:id:benicchi:20180530184722j:plain

前提

はじめに

現状、Tendermint、Cosmosネットワーク、そしてその両者の共通分野について新たに議論を始めようとすると情報過多に感じるでしょう。これまで、CosmosのTendermintスタックについて高いレベルで書いてきましたが、このポストでは、Tendermint Coreのコンセンサス層とネットワーキング層について少し詳しく説明します。以前に述べたTendermintソフトウェアスタックは、アプリケーション層(Cosmos-SDK)、コンセンサス層、およびネットワーキング層(Tendermint Core)で構成されています。TendermintはP2P伝搬プロトコルとコンセンサス層を非常に斬新な方法で結びつけています。モノリシックなアーキテクチャを使用することは、コードのコンポーネントを再利用することが難しくなり、結果としてコードベースのフォークのためのメンテナンス手順が複雑になるため、コンピュータサイエンスでは一般的に良くない方法とされています。

f:id:benicchi:20180530195536j:plain
トップダウン:アプリケーション層(Cosmos-SDK)、ブロックチェーン・インターフェース・アプリケーション(ABCI)、Tendermint Coreスタック(コンセンサス・アルゴリズム+P2Pネットワーキング・プロトコル)

まずはじめに、語彙について説明しておきます。ソフトウェアの一部である“Tendermint Core”という単語は、Tendermint CoreとCosmosネットワーク・ソフトウェアスタックを実装している“Tendermint”と同義語として使用されています。技術的には、Tendermitn Coreは低レベルのプロトコルで、実際にはコンセンサス・アルゴリズムとP2Pネットワーキング・プロトコルの2つのプロトコルで1つに構成されています。RaftとPBFTの設計目標にインスパイヤーされたJae KwonとEthan Buchmanは、アルゴリズム的に複雑なシステムエンジニアリングを行う一方で、分かりやすく、開発者にとって優しいアルゴリズムとしてTendermintを提唱しました。 新世代のBFT Proof-of-Stake(PoS)コンセンサス・アルゴリズムは、Tendermint のBFT合意形成アルゴリズムの要素を抜き出し、パブリック・ブロックチェーン領域へ対応させたものです。私たちはこの合意形成アルゴリズムのことをTendermit-BFTと呼んでおり、より一般的に言うと、BFTベースのProof-of-Stakeに分類されます(チェーンベースのProof-of-Stakeとは対照的に)。チェーンベースのPoSとBFTベースのPoSの議論については、Casper対Tendermintを参照してください。 話題が脇道に逸れましたが、本題に入りましょう! Tendermintとは何か?そして、それはどのようにして高レベルで機能するのか?見ていきましょう。

Tendermint-BFTのスタック

f:id:benicchi:20180530195813p:plain

Bitcoinは、今日私たちが親しんでいるブロックチェーンベース暗号システムの知的祖先です。Tendermintプロトコルは、2つのプロトコルがチェーン上で全てを記録するという点でBitcoinと共通しており、“コンセンサス問題”もしくは“合意形成問題”とも呼ばれる“ビザンチン将軍問題”への独自のソリューションをそれぞれ提供しています。Tendermintの元となる概念は、分散コンピューティング分野とビザンチン・フォールト・トレラント(BFT)の学術文献にさかのぼります(Ethan Buchmanの論文を参照)。一方Bitcoinには、多くの電子現金システムが失敗したこと(PayPalを除いて)を経て、これらの失敗を克服した検閲耐性のある分散型通貨システムとして誕生したという経緯があります。 Bitcoinプロトコルは、主要機能である支払いシステムのため非常に検閲耐性を最適化しています。一方Tendermintは、数百のノード(ノード数が多い)が存在するするような広域ネットワーク(WAN:Wide Area Network)の中で一般的なビザンチン・フォールト・トレラント型分散アプリケーションとデータ処置を最適化しています。これらの区別は微妙であり、より深い調査を行うに値します。 背景として、学術的な世界におけるWAN用のBFTシステムに関しての研究はごくわずかなもので、最大でも4〜7の少数のノードについてのみの研究しか行われておらず、大抵1つの管理ドメインについてのみでした。ですので、複数の管理ドメインにわたる多数のノードで構成されたWAN用のBFTシステムは、実際の現場では広く採用されていないのが現状です。 Bitcoinがパラダイムシフトとなる技術(ブロックチェーンの概念)を世界に示した2009年以前まで、大量のノード数に対するWAN用のコンセンサス問題はほとんど解決されていませんでした。Bitcoinは、Two Generals(二人の将軍問題)を解決したにもかかわらず、分散システムの研究分野における純粋な理論上の意味での、真にコンセンサス問題を解決するアルゴリズムではありませんでした。BFT領域の完全な問題解決には至っていなかったのです。 2014年、コンピュータサイエンスとシステムエンジニアリングのバックグラウンドを持つJae Kwonは、基本的なセキュリティメカニズムとしてProof-of-Stake(PoS)を使用することで、無制限に数百ノードの規模に拡張する純粋にBFTに基づくプロトコルを構想しました。こうしてTendermintが作られました。その結果、このシステムモデルがWANの検証ノード上でセキュリティメカニズムとしてPoSを活用するよう設計されたため、パブリック・ブロックチェーンとしての実装に約4年を要する非常に複雑な開発となりました。そのパブリック・ブロックチェーンは、Cosmosとして来たる2018年夏に開始する予定です。

モデル

Tendermintは、ネットワークの遅延と個々のプロセス自体の遅延の範囲内でスループットを達成するような部分的同期を行う決定論的プロトコルとしてモデル化されています。Vlad Zamfirの三角形の紫で示された部分を見てください。Tendermintは、左辺に沿って収束します。

f:id:benicchi:20180530195938j:plain
フォールト・トレラント・コンセンサス・プロトコルのためのVlad Zamfir’s Tradeoff Traangle

FLPの不可能性定理

定理:「…本論文で示す驚くべき結果は、たとえ1つのプロセスが急に停止したとしても、それを許容することが出来る完全に非同期なコンセンサス・プロトコルがないということだ」 1つでもプロセスが故障している場合、決定論的なプロトコルを持つ純粋な非同期ネットワークではコンセンサス問題を解決することはできないのです。 Dwork、Lynch、およびStockmeyerは、“Consensus in the Presence of Partial Synchrony(部分的同期の存在におけるコンセンサス)”という論文で以下のように定義しています。 「部分的同期は同期システムと非同期システムの間に存在します。同期システムでは、メッセージがあるプロセッサから別のプロセッサに送信される際に必要な時間の“既知の固定された上限値”と、異なるプロセッサの相対速度の“既知の固定された上限値”が存在します。非同期システムでは、“既知の固定された上限値”は存在しません。問題は、システム間の実際の値に関係なく、部分的同期システムで正しく動作するプロトコル設計することです…」 Tendermintはこの問題を解決しようとして生まれました。つまり、Tendermintは前述のDLSプロトコル(部分的同期プロトコル)の修正版なのです。

コンセンサス・アルゴリズム

部分的同期、同期、非同期のコミュニケーション

参考までに、同期的に動作するケースについて、よく知られているBitcoinプロトコルを使って見ていきましょう。 Bitcoinには、“既知の固定された上限値”があります。これは、10分のブロック生成時間をもとにしています。Bitcoinプロトコルは、ネットワークがブロックを生成し繋いでいくために、ノードネットワーク全体がピアごとの繋がりを介して伝搬するトランザクションをリッスンし、収集、検証、拡散するのに10分という時間を与えることで、人工的に時間設定を行います。 Ethereumは、平均ブロック生成時間が15秒という同期時間を設定するプロトコルの別例です。15秒は10分よりもはるかに高速であり、Ethereumネットワークに高いスループットをもたらすというメリットがあります。一方で、これはマイナーを犠牲にし、孤立したブロックを増やしてしまいます。トランザクションがネットワークを介して全体に伝搬するには時間が足りないのです。 Tendermintは、部分的同期コミュニケーションの下でコンセンサス問題を解決するプロトコルの1つです。部分的同期システムモデルは、同期時間およひ同時時間を交互に繰り返すもので、このモデルのことを“弱い同期”と呼ぶこともあります。これは、Tendermintがブロックを繋いでいくために時間設定に頼っているということを表します。ただし、同期システムとは異なり、進行速度はシステムパラメータに依存せず、実際のネットワーク速度に依存します。

生存性と終結

定義:「終結プロパティとは、単にそれぞれの正常なプロセッサが最終的に決定を下さなければならないという意味である」 Nakamotoコンセンサス、Peercoin、NXT、Snow White、Ouroborosなど、同期システムモデルにおけるこれらのアルゴリズムは、プロセス終結だけでなく、安全性のためにも同期の設定に依存しています。同期システム用に設計されたこれらのアルゴリズムは、常に既知の固定値が設定され、保持されています。また、万が一保持されない場合には、コンセンサスが破綻し、チェーンがフォークします。したがって、Bitcoinの10分のブロック生成時間は、安全性の保持に関してまさしく保守的と言えるでしょう。 対照的にTendermintでは、非同期性が存在することで障害がプロセスの3分の2以上にならない限り決してフォークしません。このプロパティによりTendermitは、生存性より安全性が厳密に優先されるBFTに基づくPoSプロトコルであると言えるのです(CAP定理を参照)。結果として、Tendermintブロックチェーンは全バリデーターの超大多数である3分の2以上がコンセンサスを形成するまで一時的に停止します。 現在、純粋に非同期ネットワークで動作するコンセンサス・プロトコルがありますが、FLPの不可能性定理に従えば、同時に決定論的でないと言えます。

決定論的プロトコル vs 非決定論的プロトコル

純粋に非同期なケースでコンセンサス問題を解決する非決定論的プロトコルは、全てのコミュニケーションにとって信頼性のあるブロードキャストに頼るため、潜在的にランダムなオラクルに依存し、一般的にメッセージの複雑さによる高いオーバーヘッドを招きます。非同期環境における1つの信頼できるブロードキャストにかかるオーバーヘッドコストは、Tendermintの1ラウンドのコストとほぼ同じです。HoneyBadgerBFTのようなプロトコルは、非同期下の非決定論的プロトコルに分類されます。通常これらのプロトコルは、1回のラウンドで信頼性の高いブロードキャストの実証を3回必要とします。 代わって、Tendermintは完全に決定論的なプロトコルです。Tendermintにランダム性は全くありません。リーダーは、実装された数学的関数の定義を通して決定論的に選出されます。このようにして、そのシステムが生存しており、プロトコルによる決定が保証されていることを数学的に証明することができます。

リーダー選出のローテーション

Tendermintは、バリデーター群、つまりブロックを提案するアカウントの集合を加重ラウンドロビン方式でローテーションします。よりステークするほど、つまりバリデーターが委任した議決権である投票権が増えるほど、より多くの重みを持ち、それに比例してより多くリーダーとして選出されることになります。分かりやすく説明するために、1つのバリデーターが別のバリデーターと同じ量の投票権を持つ場合を考えます。双方ともプロトコルによって同じ回数選出されます。

アルゴリズムの仕組みを簡単に説明すると、次のようになります。

1 バリデーターの重みは事前に設定されているとします。

2 バリデーターが重みに応じて選出され、ブロックの提案を行います。

3 重みが再計算され、ラウンドが完了した後にいくらかの量が減少します。

4 各ラウンドが進むにつれて、重みは投票力に比例して段階的に増加していきます。

5 バリデーターを再び選出します。

  • 実際のコードは次の通りです:(GitHub

プロトコルはブロック提案者を決定論的に選択するため、バリデーター群と各バリデーターの投票力をいつでも知ることができ、ラウンドx、x+1、…、x+nというように次のブロック提案者が誰なのかを正確に計算できます。このため、批評的な意見としてTendermintは十分に分散されていないと言われます。リーダーが誰であるか予測的に分かってしまうと、攻撃者はこれらのリーダーをターゲットに絞ることができ、DDoS攻撃を行なって進行中のチェーンを停止させる可能性があります。私たちは、TendermintにSentry Architectureと呼んでいるものを実装することで、この攻撃進路を軽減します。

P2Pネットワーキング・プロトコル

Sentry Node Architecture

適切に設定されたバリデーターは、決してIPアドレスを公開しない、もしくは、他のバリデーターノードからの接続を一切受け付けません。正しく設定され保守されたバリデーターは、バリデーターノードの実際のロケーションを難読化するため、ネットワーク上でフルノード・プロキシーとして機能する“Sentry Node”を積極的に生成します。P2P層のIPアドレスは絶対に公開されません。 つまり、Sentry Node Architectureの利点を享受するには、フォールト・トレラントなフルノードを維持する責任をバリデーターが負うという同意が必要になります。これが、私たちが暗号経済的なインセンティブに基づいた特別なプロトコルの仮説を唱える理由です。その仮説とは、「バリデーターは、フォールト・トレラント性を保守し、利用可能な状態を維持し、最終的にはネットワークを存続させるための役割を果たせるようすべての予防措置を講じたいはずである」というものです。そうでない場合、バリデーター群から追い出され、一定時間オフラインになります。

Peer Exchamge(PEX)装置

Tendermintは、Bitcoinのピア発見プロトコルを借用しています。具体的に言えば、TendermintはGoのBitcoin代替実装であるbtcdのP2Pアドレスブックを活用しています。PEXでは、デフォルトで動的にピア発見を行うことができます。

実用でのTendermint

結局のところ、実用的なアルゴリズム設計や学術的な世界以外でTendermintは実際に役に立つのでしょうか? 悪いニュースは、エンドユーザーにとってTendermintが直接的には役に立たないことです。良いニュースは、アプリケーション開発者がプロトコルとエンドユーザー間のギャップを埋められるということです。Tendermintは、コンセンサスプロトコルの求められる公共または企業の様々な設定に合わせてカスタマイズ可能で柔軟性があるように設計されています。 Tendermintは、独自のブロックチェーン上にアプリケーションを実装したい開発者にとって理想的なのです。事前に組み立てられているため、開発者が純粋なProof-of-Stakeを目指してBFTに基づいたコンセンサスエンジンを使用したDappszoneの強化を行うことを容易にします。 ユーザーがCosmos-SDKを使用して高いレベルのビジネスロジックを実装できた時が、Tendermintの一番面白いときです。Tendermintのコンセンサス層・ネットワーキング層と接続するには、ブロックチェーン・インターフェース・アプリケーション(Application Blockchain Interface)またはABCIと呼ばれるTendermintソケットプロトコルを使用します。

現在進行中の研究

私たちは現在、Tendermintブロックヘッダーのサイズを3.2KBから64バイトに(〜100バリデーターで)減らすことが出来るように、BLS署名の研究を掘り下げて行なっています。 また、ラウンドロビン方式の提案者選出機能を安全にランダム化して、次の提案者へのDDos攻撃をより困難にする設計もありますが、最初のステップではSentry Node Architectureを採用しています。

Cosmos Academy Inaugural Meetup!!

私たちは、カリフォルニア州バークレーで、シニアBFT分散システム研究者のZarko Milosevicとのミートアップを開催し、Tendermintの全てについてQ &Aセッションを行う予定です。CosmosネットワークのYouTubeチャンネルで放送を公開します。(※Meet upは、5月26日で終了しています。)

・ ・ ・

追加情報

  • Tendermint Coreのシニアリサーチサイエンティスト、Zarko Milosevicとのインタビューはこちら

  • JepsenのKyle KingsburyがTendermint-BFTを紹介:https://youtu.be/tRc0O9VgzB0

  • Tendermintの技術スペックについては、Zach RamsayのReadthedocsをご覧ください。

  • Jae KwonのオリジナルのTendermintホワイトペーパーはこちらです。

  • Ethan BuchmanによるHistory of Distributed Stateをご覧ください。

  • Ethan BuchmanによるHistory of Distributed Stateは、デイリー・ソフトウェアエンジニアリングのPodcastでも聴けるので、ぜひ聴いてみてください。

  • 初期のブロックチェーン・エコシステムについては、Zaki ManianのBitcoinPodcastネットワークで聴いてください。