簡単まとめ

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

更新日:

本稿について

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

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

今回の対象範囲は第4章「Tendemint Subprotocols」のうち4.2「Consensus Gossip」で、これを読むとTendermintのP2Pによるブロックデータや投票のゴシップ伝送に関するプロトコルについて把握することができます。

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

スポンサードサーチ

要点をまとめてみる

  • コンセンサスでは、ステートの変更があるたびに現在のステートをブロードキャストする。
    • 周辺ピアのコンセンサスステートを記録することで、情報をまだ持っていないピアだけに情報を送信する。
    • 情報の選択ストラテジはレアレストファースト方式(筆者注:まだ出回っていない(=レアな)情報を優先する(=ファースト)方式)である。
  • ブロックをいくつかのチャンクに分割し、それぞれをハッシュ化してマークルツリーを使ってマークルルートハッシュを求め、提案にはブロック全体の代わりにマークルルートハッシュを利用することでネットワーク帯域幅の浪費を防ぎブロックの高速に伝達できるようにする。
  • コンセンサスステートマシンの各ステップでのピアの動きについて。
    • プロトコルが完了したピア ⇒ 投票またはローカルのタイムアウトを待機する。
    • 新しいブロック高にちょうど進んだばかりのピア ⇒ 前ブロックからの事前コミットを受け取る。
      • このピアが提案者であれば、次ブロックのLastCommitに事前コミットを取り込む可能性がある。
    • 事前投票は完了したが事前コミットをしていないピア ⇒ 事前投票が送られる。
    • 事前コミットは完了したが次ラウンドへ進めていないピア ⇒ 事前コミットが送られる。
    • 遅れているピア ⇒ そのピアのいるブロック高で既にコミットされたブロックに対する事前コミットが送られる。

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

Chapter4. Tendermintのサブプロトコル(続き)

4.2 コンセンサスのゴシップ伝送

コンセンサスリアクターはコンセンサスステートマシンをラップしており、ステートの変更があるたびに各ノードが全ピアに現在のステートを確実にブロードキャストする。このようにして各ノードは周りの全ピアのコンセンサスステートの記録を付けることで、メッセージのゴシップ伝送を最適化してまさにその瞬間情報を必要としているピア、つまりまだ情報を持っていないピアに対してだけ送信できるようにする。各ピアに対して、ノードは2つのルーチンを維持する。そのルーチンとは、ピアに送る新しい情報、いわゆる提案と投票を継続的に確認することである。ゴシップ伝送の効率性と一部の情報が利用不可になる可能性を最小化するために、情報は「レアレストファースト」な方法でゴシップ伝送される[62]。

4.2.1 ブロックデータ

チャプター3では、提案メッセージはブロックを含むものという前提が置かれていた。しかし、ブロックは1つのソースから発生して非常に大きくなる可能性があるので、この前提はデータを全ノードへアップロードするようブロック提案者に不当な圧力をかけてかけていることになる。つまり、ブロックをいくつかに分割してゴシップ伝送すれば、さらに早く広めることができる。

セキュアにデータをゴシップ伝送する一般的なアプローチは、様々なP2Pプロトコルで普及しているように[21, 79]マークルツリー[65]を使う方法で、データ片を全体の一部にするような短い証明(データサイズの対数の大きさ)により各データ片を一緒にすることができる。このアプローチを用いるには、ブロックをシリアル化したうえで、期待されるブロックサイズとバリデータ数に対して適切なサイズのチャンクに分割し、チャンクをハッシュ化してマークルツリーの中に入れる。署名付きの提案にはブロック全体の代わりに単にマークルルートハッシュだけが含まれ、ネットワークはチャンクのゴシップ伝送に協力できるようになる。同一チャンクをノードに複数回伝送することによる帯域幅の浪費を最小化するため、ノードは周りのピアにチャンクを受信するたびに報告する。

一度全てのチャンクが受信されると、ブロックはシリアル状態から戻されて、正しく前ブロックを参照しているか、マークルツリーとして実装されている複数のチェックサムが正しいかの検証が行われる。バリデータは提案(ブロックを含む)を受信するまで事前投票しないと以前に仮定していたが、完全なブロックを受信する前ではなく提案を受信した後にバリデータが事前投票できるようにすることで、パフォーマンス上の利点が得られる可能性がある。これはつまり、結果的に無効になってしまうブロックに対して事前投票をしても問題がないということである。しかし、無効なブロックに対して事前コミットを行うことは、常にビザンチンであるとみなされる。

追いつこうとしているピア(つまり、若いブロック高にいるピア)は自身がいるブロック高に対するチャンクを受け取って、1度に1ブロックずつ進行する。

4.2.2 投票

コンセンサスステートマシンの各ステップで、プロトコルの後、ノードは前進するために投票(またはローカルのタイムアウト)を待機している。ピアがちょうど新しいブロック高に突入すると、前ブロックからの事前コミットが送られてくるので、提案者であれば次のブロックのLastCommitに事前コミットを取り込む可能性がある。もしピアが事前投票はしたもののまだ事前コミットをしていない場合は事前投票が、または事前コミットをしたがまだ次のラウンドに進んでいてい場合は事前コミットが送られてくる。もしピアが追いつこうとしている場合、そのピアのいるブロック高でコミット済みのブロックに対する事前コミットが送られてくる。

翻訳範囲の参考文献

[21]Bram Cohen. The BitTorrent protocol specification. 2008.

[62]Arnaud Legout, Guillaume Urvoy-Keller, and Pietro Michiardi. “Rarest first and choke algorithms are enough”. In: Proceedings of the 6th ACM SIGCOMM conference on Internet measurement. ACM. 2006, pp. 203–216.

[65]Ralph C Merkle. “A digital signature based on a conventional encryption function”. In: Advances in Cryptology—CRYPTO’87. Springer. 1987, pp. 369–378.

[79]Riccardo Petrocco, Johan Pouwelse, and Dick HJ Epema. “Performance analysis of the libswift p2p streaming protocol”. In: Peer-to-Peer Computing (P2P), 2012 IEEE 12th International Conference on. IEEE. 2012, pp. 103–114.

EthanのTendermint論文9 ←← 前)|(次 →→ EthanのTendermint論文11

免責

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

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

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

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

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