\( \def\vector#1{\boldsymbol{#1}} \newcommand{\argmax}{\mathop{\rm arg~max}\limits} \)

論文翻訳: The latest gossip on BFT consensus

Takami Torao 2018年の論文 #Blockchain #Tendermint
  • このエントリーをはてなブックマークに追加
Ethan Buchman, Jae Kwon and Zarko Milosevic
Tendermint

Abstract

この論文は敵対的な条件下の分散ネットワークでイベントを順序付けするための新しいプロトコルである Tendermint を紹介する。より一般的にビザンチンフォールトトレラント (BFT) コンセンサスまたはアトミックブロードキャストとして知られチエルこの問題は、ビットコインやイーサリアムなどのブロックチェーンベースのデジタル通貨が広く普及したことで、近年大きな注目を集めているが、中央機関のないパブリックな設定でこの問題を解決することに成功した。Tendermint はこの問題に関する古典的な学術研究を現代化し、ノード間のピアツーピアゴシッププロトコルに依存することにより BFT アルゴリズムの設計を簡素化している。

  1. Abstract
  2. 1 導入
  3. 2 Definitions
    1. A. Model
    2. B. State Machine Replication
    3. C. Consensus
  4. 3 Tendermint Consensus Algorithm
    1. A. Termination mechanism
  5. 4 Proof of Tendermint Consensus Algorithm
  6. 5 Conclusion
  7. Acknowledgements
  8. References
  9. 翻訳妙

1 導入

コンセンサスは分散コンピューティングにおける最も基本的な問題の一つである。これは、決定論的ステートマシンとしてモデル化できるサービスを複製するための一般的なアプローチであるステートマシンレプリケーション (SMR) において重要な役割を果たしている [1], [2]。このアプローチの重要な考え方は、サービスレプリカが同じ状態で開始し、同じ順序でリクエスト (トランザクションとも呼ばれる) を実行することで、レプリカが互いに動悸していることを保証するということである。SMR アプローチにおけるコンセンサスの役割は、全てのレプリカが同じ順序でトランザクションを受信することを保証することである。従来 SMR ベースのシステムはデータセンター (ローカルエリアネットワーク) の構成で展開され、レプリカの数が少数 (3〜7) であり、一般的には単一の管理ドメインの一部である (例えば Chubby [3])。そのため、より一般的な障害 (特に悪意のある障害またはビザンチン障害) はごく僅かな確率でしか発生しないと想定しており、良性の障害 (クラッシュ) のみを扱っている。

近年の暗号通貨やブロックチェーンシステムの成功 (例: [4], [5] は SMT ベースのシステムの設計と展開に新たな課題を提起している: これは同じ管理ドメインに属していない多数の (数百または数千) ノード間で、広域ネットワーク上で合意に達すること、そして、ノードのサブセットが悪意 (ビザンチン障害) を持って行動する可能性があるということである。さらにノードが相互に完全に接続されている以前のデータセンター展開とは異なり、ブロックチェーンシステムでのノードは他のノードのサブセットにしか接続されていないため、通信はゴシップベースのピアツーピアプロトコルによって実現される。新しい要件は、主旨の焦点が異なる設定であったため、古典的なビザンチンフォールトトレラントコンセンサス (または SMR) システムに関する学術論文 (例えば [6], [7]) に必ずしも存在しない設計とアルゴリズムを要求する。

この論文では Tendermint1 と呼ばれる BFT SMR プラットフォームのコアである新しいビザンチン耐障害性コンセンサスアルゴリズムについて説明する。Tendermint のプラットフォームは Go で記述された高性能な BFT SMR 実装、コンセンサス以上の任意の決定論的アプリケーションを構築するための柔軟なインターフェースおよび展開と管理のためのツール群で構成されている。

Tendermint のコンセンサスアルゴリズムは PBFT SMR アルゴリズム [8] および認証された障害用の DLS アルゴリズム ([6] の Algorithm 2) に触発されている。DLS アルゴリズムと同様に Tendermint はラウンド2 で進行する。各ラウンドには専用の提案者 (コーディネーターやリーダーとも呼ばれる) が存在し、プロセスは通常の処理の一部として新しいラウンドに進む (PBFT のように提案者に問題があったり多くのプロセス欠陥が疑われる場合だけではない)。各ラウンドの通信パターンは PBFT の "normal" の場合と非常によく似ている。したがって、好ましい条件 (正常な提案者、プロセス間のタイムリーで信頼性の高い通信) の下では Tendermint は (PBFT と同じ) 3 つの通信ステップで決定する。

Tendermint コンセンサスアルゴリズムの主な新規性と貢献は新しい終了メカニズムである。[9], [10] で説明されているように、部分同期システムモデルに対する既存の BFT コンセンサス (および SMR) アルゴリズムは (例えば PBFT [8], [6, [11]) は、通常、Figure 1 に示すような通信パターンに依存して終了している。Figure 1 はプロセスが新しいラウンド3を開始する際の提案者の変更中に交換されるメッセージを示している。これは、最終的に (つまりグローバル安定時間 (GST) が経過した後に) 正しい提案車を持つラウンドが存在し、システムを一本化することを保証するものである。直感的には、提案された値が全ての正しいプロセスに受け入れられ、正しいプロセス間のコミュニケーションがタイムリーで信頼できるラウンドでは、全ての正しいプロセスが決定に到達する。

Fig. 1: 提案者 (コーディネーター) 変更: \(p_1\) は新しい提案者。

提案された値が全ての正しいプロセス4で受け入れられるように、提案者は 1) 他のプロセスからのメッセージを受信してグローバルな状態を構築し 2) 提案する安全な値を選択し 3) 選択された値を、最初のステップで受信した署名付きメッセージとともに、それを支持するために送信する。正しいプロセスが次の提案者に送る値 \(v_i\) は、通常、そのプロセスが決定のために許容できると考える値に対応する:

  • PBFT [8] や DLS [6] では、値そのものではなく同じ値 ID を持つ \(2f+1\) 符号付きメッセージの集合である。
  • 高速ビザンチン Paxos [11] では、値自身が送信されている。

どちらの場合でも、我々のシステムモデル (すなはちゴシップベースネットワークの多数のノード) でこのメカニズムを使用すると、プロセスの数とともに通信複雑性が高くなる: 最初のケースではプロセスの総数に応じたメッセージが送信され、2つ目のケースではそれぞれのプロセスによって値 (トランザクションのブロック) が送信される。最初のステップで受信したメッセージのセットは、通常、選択された値 \(x\) の選択を正当化するために提案メッセージ (Figure 1 で \([v_{1..4}]\) で示される) に便乗している。

我々は、我々が検討しているシステムモデルにより適した Tendermint の新しい終了メカニズムを設計した。これは追加の通信を必要とせず (新しいメッセージを送信したり、既存のメッセージに情報を便乗させたりする必要もない) PBFT [8] の normal の場合と非常によく似た通信パターンに基づいている。したがって Tendermint の実行モードは単一であり、他の PBFT ライクなプロトコル ([8], [12], [13] など) に見られるような normal モードとリカバリーモードの分離は存在しない。これにより Tendermint の理解と実装がよりシンプルとなり、正しく実装できるようになると考えている。

BFT コンセンサスアルゴリズムのスケーラビリティと分散化 (プロセス数) を向上させるためにメッセージの複雑性を減らすための直行的なアプローチは、例えば SBFT [15] で行われているような高度な暗号 (例えば Boneh-Lynn-Shacham (BLS) 署名 [14]) を使用することであることに注意。

論文の残りの部分は以下の通りである。セクション 2 ではシステムモデルを定義し問題を定義する。セクション 3 では Tendermint コンセンサスアルゴリズムを提示し、セクション 4 でその証明を提示する。最後にセクション 5 で結論を述べる。

  • 1 Tendermint プラットフォームは https://github.com/tendermint/tendermint でオープンソースとして公開されている。
  • 2 Tendermint は [6] の基本的なラウンドモデルには含まれていない。さらに [6] とは異なる用語としてラウンドを用いている。
  • 3 分散コンピューティングの用語には論理単位 (logical unit) に対応する通信ステップのシーケンスの命名に関する一貫した用語は存在しない。ラウンド、フェーズ、ビューと呼ばれることもある。
  • 4 BFT アルゴリズムにおいて、提案された値が正しいプロセスによって盲目的に受け入れられることはない。コンセンサスの安全性特性が侵害されないように、提案された値が安全に受け入れられるかどうかを正しいプロセスは常に検証する。

2 Definitions

A. Model

B. State Machine Replication

C. Consensus

3 Tendermint Consensus Algorithm

A. Termination mechanism

4 Proof of Tendermint Consensus Algorithm

5 Conclusion

Acknowledgements

We would like to thank Anton Kaliaev, Ismail Khoffi and Dahlia Malkhi for comments on an earlier version of the paper. We also want to thank Marko Vukolic, Ming Chuan Lin, Maria Potop-Butucaru, Sara Tucci, Antonella Del Pozzo and Yackolley Amoussou-Guenou for pointing out the liveness issues in the previous version of the algorithm. Finally, we want to thank the Tendermint team members and all project contributors for making Tendermint such a great platform.

References

  1. L. Lamport, “Time, clocks, and the ordering of events in a distributed system,” Commun. ACM, 1978.
  2. F. B. Schneider, “Implementing fault-tolerant services using the state machine approach: a tutorial,” ACM Comput. Surv., vol. 22, no. 4, Dec. 1990.
  3. M. Burrows, “The chubby lock service for loosely-coupled distributed systems,” in OSDI, 2006, pp. 335–350.
  4. S. Nakamoto, “Bitcoin: A peer-to-peer electronic cash system,” 2009. [Online]. Available: http://www.bitcoin.org/bitcoin.pdf
  5. V. Buterin, “Ethereum: A next-generation smart contract and decentralized application platform,” https://github.com/ethereum/wiki/wiki/White-Paper, 2014, accessed: 2018-07-11. [Online]. Available: https://github.com/ethereum/wiki/wiki/White-Paper
  6. C. Dwork, N. Lynch, and L. Stockmeyer, “Consensus in the presence of partial synchrony,” JACM, 1988.
  7. M. Castro and B. Liskov, “Practical byzantine fault tolerance and proactive recovery,” ACMTCS, 2002.
  8. ——, “Practical byzantine fault tolerance and proactive recovery,” in Proceedings of the 3rd Symposium on Operating Systems Design and Implementation, Feb. 1999.
  9. Z. Milosevic, M. Hutle, and A. Schiper, “Unifying Byzantine consensus algorithms with Weak Interactive Consistency,” to appear in OPODIS 2009.
  10. O. R ütti, Z. Milosevic, and A. Schiper, “Generic construction of consensus algorithms for benign and byzantine faults,” in DSN, 2010, pp. 343–352.
  11. J.-P. Martin and L. Alvisi, “Fast Byzantine consensus,” TDSC, 2006.
  12. G. S. Veronese, M. Correia, A. N. Bessani, and L. C. Lung, “Spin one’s wheels? byzantine fault tolerance with a spinning primary,” in SRDS, 2009.
  13. A. Clement, E. Wong, L. Alvisi, M. Dahlin, and M. Marchetti, “Making byzantine fault tolerant systems tolerate byzantine faults,” in NSDI, 2009, pp. 153–168.
  14. D. Boneh, B. Lynn, and H. Shacham, “Short signatures from the weil pairing,” in Proceedings of the 7th International Conference on the Theory and Application of Cryptology and Information Security: Advances in Cryptology, ser. ASIACRYPT ’01. Berlin, Heidelberg: Springer-Verlag, 2001, pp. 514–532. [Online]. Available: http://dl.acm.org/citation.cfm?id=647097.717005
  15. G. Golan-Gueta, I. Abraham, S. Grossman, D. Malkhi, B. Pinkas, M. K. Reiter, D. Seredinschi, O. Tamir, and A. Tomescu, “SBFT: a scalable decentralized trust infrastructure for blockchains,” CoRR, vol. abs/1804.01626, 2018. [Online]. Available: http://arxiv.org/abs/1804.01626
  16. A. Demers, D. Greene, C. Hauser, W. Irish, J. Larson, S. Shenker, H. Sturgis, D. Swinehart, and D. Terry, “Epidemic algorithms for replicated database maintenance,” in Proceedings of the Sixth Annual ACM Symposium on Principles of Distributed Computing, ser. PODC ’87. New York, NY, USA: ACM, 1987, pp. 1–12. [Online]. Available: http://doi.acm.org/10.1145/41840.41841
  17. T. Crain, V. Gramoli, M. Larrea, and M. Raynal, “Leader/randomization/signature-free byzantine consensus for consortium blockchains,” CoRR, vol. abs/1702.03068, 2017. [Online]. Available: http://arxiv.org/abs/1702.03068

翻訳妙

Tendermint のコンセンサスに関する 2018 年の論文。

  1. Ethan Buchman, Jae Kwon and Zarko Milosevic (2018) The latest gossip on BFT consensus