簡単まとめ

Ethan BuchmanのTendermint論文を覗いてみる2

更新日:

本稿について

本稿は、Tendermintホワイトペーパーの詳細版ともいえるTendermint現CTOであるEthan Buchman氏の執筆論文をもとにTendermintについて見ていくシリーズです。冒頭に筆者による「簡単まとめ」を入れ、その後にもととなった部分の日本語訳を載せるという順番で書いていきます。

論文「Tendermint: Byzantine Fault Tolerance in Age of Blockchain」の原文はこちら

今回の対象範囲は第3章「Tendemint Consensus」のうち3.2「Consensus」で、これを読むとTendermintのコンセンサスの構成と進め方について大枠のイメージを把握することができます。

原文はこちらになります。

スポンサードサーチ

要点をまとめてみる

  • コンセンサスアルゴリズムは3つの構成要素からなる。
    • 提案(proposals)
    • 投票(votes)
    • ロック(locks)
  • バリデータは公開鍵で識別できる。秘密鍵で提案や投票に署名する。また、バリデータは最初は共通のステートを持ち、ステート内にバリデータの順序付きリストを持つ。
  • コンセンサスの一番最初はラウンド0で、このラウンドの提案者は順序付きリストの先頭のバリデータである。
  • ラウンドの結果はコミットするか次ラウンドへ行くかで、次ラウンドに行く場合、別の提案者があたる。つまり、ラウンドごとに提案者が異なる。
  • TimeoutPropose以内に提案を受け取らなければ、バリデータは投票してそのラウンドの提案者をスキップできる。
    • 安全にスキップするためにいくつかのロックに関するルールが定められており、バリデータは正当性を保持しておくことが求められる。
  • コンセンサスアルゴリズムが使う主なメッセージは次の2つである。
    • ProposalMsg:任意のブロック高とラウンドにおけるブロックに対する提案で、提案者により署名されているもの。
    • VoteMsg:提案に対する署名付きの投票。

以下、今回取り扱った箇所の日本語訳なので詳細を知りたければどうぞ。

Chapter3. Tendermintコンセンサス(続き)

3.2 コンセンサス

コンセンサスアルゴリズムは以下のように分解することができる。いくらか重なる部分もある構成要素である。

  • 提案(proposals):新しいブロックは各ラウンドで正しい提案者によって提案され、他のバリデータらにゴシップで伝えられなくてはならない。提案が十分な時間内に受け取られなかった場合、その提案者はスキップされる。
  • 投票(votes):2フェーズの投票は最適なBFT(ビザンチンフォールトトレランス性)を確保するために行う必要がある。これらは事前投票(pre-vote)と事前コミット(pre-commit)と呼ばれる。2/3より多くのバリデータからの同一ラウンドの同一ブロックに対する事前コミットの集合がコミット(commit)である。
  • ロック(locks):悪意あるバリデータが1/3未満であると仮定して、Tendermintは同一ブロック高で2つのバリデータが異なるブロックをコミットしていないことを確約する。これはロックメカニズムにより達成されるものである。ロックメカニズムは、同一ブロック高における前の事前投票と事前コミットに基づいてバリデータが事前投票や事前コミットする方法を定めるものである。ライブネスを侵害しないよう、慎重にこのロックメカニズムを設計しなければならない点には留意されたい。

単一ビザンチン障害に対する耐性を与えるため、Tendermintネットワークは最小で4つのバリデータがいなければならない。各バリデータは、デジタル署名を生成するために非対称暗号鍵のペア(筆者注:公開鍵暗号ペア、要するに公開鍵と秘密鍵のペア)を持っていなければならない。バリデータは共通の初期ステートから始まり、初期ステートにはバリデータの順序付きリストLがある。各バリデータは各自の公開鍵で識別され、提案と投票は全て各自の秘密鍵で署名されていなければならない。これにより、任意の観測者がいつでも提案と投票を検証できるようになる。最大で1/3のバリデータが悪意を持っていてシステムのセーフティやライブネスを破壊すべく任意の方法で協力すると仮定しておくのは有益である。

コンセンサスはラウンド0で始まり、ここでの最初の提案者はLの最初のバリデータである。ラウンドの結果は、コミットか次ラウンドへの移行決定かのどちらかである。新しいラウンドには次の提案者があたる。複数のラウンドを使うことで、ネットワーク非同期やバリデータ故障時にバリデータにコンセンサスを形成する複数の機会を提供できる。

リーダー選出の形を要するアルゴリズムとは対照的に、Tendermintはラウンドごとに新しいリーダー(提案者)がいる。バリデータは投票を提案を受け入れるのと同じやり方で投票して次のラウンドに進み、プロトコルにメカニズムの均一性を与える。これは明示的なリーダー選出プログラムのあるアルゴリズムにはないものである。

各ラウンドの開始時は、いつ提案者をスキップするかを決定するためにローカルクロックを利用することから、同期への弱い依存がある。つまり、バリデータがラウンドの突入時からローカルに計測されているTimeoutPropose以内に提案を受け取らなければ、バリデータは投票してそのラウンドの提案者をスキップできる。このメカニズムは本来的に弱い同期の仮定を内包している。つまり、提案は最終的にはTimeoutPropose以内に伝達されて、それによって各ラウンドでインクリメントが起こるだろうという仮定である。この仮定についてはチャプター10でもっと十分に議論する。

提案後、ラウンドは完全に非同期な方法で進む。バリデータは少なくとも2/3の他バリデータからの連絡をもらった後に限り先に進める。これによりあらゆる種類の同期クロックやネットワーク遅延の制限への依存から解放されるが、1/3以上のバリデータが応答しなくなるとネットワークは停止することも示唆している。非同期的投票にフォローされる弱い同期的な提案の回路を図3.1に示す。

安全にラウンドをスキップするために少数のロックルールが導入される。このルールにより、バリデータが自身の行った投票の正当性を示すことを強制する。バリデータにリアルタイムに正当性をブロードキャストしてもらう必要はないが、十分なビザンチン故障によりセーフティが侵害された場合には証拠として提出できるよう、正当性を保持してもらうことが強く期待されている。このアカウンタビリティメカニズムにより、Tendermintは故障時に強い保証を提供できる。そして、その保証は1/3以上のバリデータがビザンチンである場合に何らの保証もないPBFTなどよりも強いものである。

バリデータはブロックチェーンやアプリケーションステート、ピアネットワーク、コンセンサスを管理するために様々なメッセージを使ってコミュニケーションする。しかし、コアとなるコンセンサスアルゴリズムはたった2つのメッセージからなる。

  • ProposalMsg:任意のブロック高とラウンドにおけるブロックに対する提案で、提案者により署名されているもの。
  • VoteMsg:提案に対する署名付きの投票。

実際には、チャプター4で議論するように、さらなるメッセージを使ってブロックデータや投票のゴシッピングを最適化する。

EthanのTendermint論文1 ←← 前)|(次 →→ EthanのTendermint論文3

免責

邦訳には誤りがある場合がございます。予めご承知おき下さい。

確実な情報を知るためには冒頭に示した原文をご参照くださいますようお願いいたします。

-簡単まとめ
-, , , , , , , , ,

Copyright© 暗号通貨界隈のメモ書きなど。 , 2019 All Rights Reserved Powered by STINGER.

%d人のブロガーが「いいね」をつけました。