Tendermint (コンセンサス・アルゴリズム)まとめ

とりあえず、重要なところだけ簡単にまとめてみた。詳細はそのうち書くかも。

最近、用語の使い方が変わった様子。

• TendermintCoreが、ブロックチェーン・コンセンサス・エンジン。
• TMSP(The Tendermint Socket Protocol):
• 社名が Tendermintから All in Bits, Inc. に変更(2017年1-3月位)

概要

現時点の最新バージョン Tendermint version 0.7 時点の説明です。

• POS型のコンセンサス・アルゴリズム(分散型合意形成アルゴリズム)
• BFT アルゴリズムをベースにしている
• ユーザが、コンセンサス・プロセスに参加するためにバリデータになるには、担保の預金を入れなければいけない
• PBFTと違って、固定のリーダーではなく、ラウンドロビン
• PBFTと違って、ダイナミックメンバーシップ制

• 1秒位でコミット

• 250バイトのトランザクションで、10,000トランザクション/秒

公式サイト

• Tendermint
• Byzantine Consensus Algorithm · tendermint/tendermint Wiki

用語

• propose: プロポーズ: 提案: Tendermintでは、次のブロックの提案
• prevote: プリボート: 前投票: Tendermintでは、次のブロックへの前投票
• precommit: プリコミット: 事前コミット: 本コミット前の仮コミット
• commit: コミット: ブロックをブロックチェーンへ入れること
• proposer: プロポーザー: ブロック提案をするノード
• heigit: 高さ: ブロックの高さ(番号)
• newHeight: 新しい高さ: 新しいブロックの高さ(番号)

大雑把な状態遷移

新しい高さ -> (プロポーズ -> プリボート -> プリコミット)+ -> コミット -> 新しい高さ ->…

(プロポーズ -> プリボート -> プリコミット)が、ラウンドと呼ばれる。

ステート・マシーン・ダイアグラム

　　                         +-------------------------------------+
                            v                                     |(`CommmitTime+timeoutCommit`まで待つ)
                      +-----------+                         +-----+-----+
         +----------> |  プロポーズ  +--------------+          | 新しい高さ |
         |            +-----------+              |          +-----------+
         |                                       |                ^
         |(それ以外, timeoutPrecommit後)         v                |
   +-----+-----+                           +-----------+          |
   | プリコミット |  <------------------------+  プリボート  |          |
   +-----+-----+                           +-----------+          |
         |(ブロック用の3分の2以上のプリコミットが発見された時)                  |
         v                                                        |
   +--------------------------------------------------------------------+
   |  コミット                                                            |
   |                                                                    |
   |  * CommitTime = nowにセット;                                           |
   |  * ブロックを待ってから、ブロックをstage/save/commit;                   |
   +--------------------------------------------------------------------+

プロポーザル

• プロポーザルは、ラウンド毎に指定されたプロポーザーによってサインされ、発行されたもの。プロポーザーは、投票力に比例してプロポーザーを選択する決定論的で、ノンチョーキング・ラウンドロビン選択アルゴリズムによって選ばれる。

Hacker News

Tendermint – The completely decentralized consensus engine | Hacker News

Tendermint vs PBFT

Tendermint vs PBFT

ラウンドロビン vs 固定リーダ

• 新しいリーダを選ぶためのラウンドロビン・スキーム
• 固定リーダの方が、スループットは高い

ダイナミック・メンバーシップ

• PBFT: 固定レプリカ/ヴァリデータ
• Tendermint: ダイナミック・メンバーシップ

DLRアルゴリズム

関連アルゴリズム

Consensus in the Presence of Partial Synchrony (1988)

• Consensus in the presence of partial synchrony

ベンチマーク

一秒にどれ位のトランザクションを処理できるか?

• Benchmarks · tendermint/tendermint Wiki

参考ページ

• Introduction · tendermint/tendermint Wiki
• Byzantine Consensus Algorithm · tendermint/tendermint Wiki

関連記事

• Consensus – 分散型コンセンサス・アルゴリズム プロトコル まとめ | block-chain.jp
• Proof of Stake とは何か? | block-chain.jp
• Nothing at Stakeとは何か? | block-chain.jp
• Proof of Stake の Stake Grinding 攻撃とは? | block-chain.jp

ニュース記事

• マイクロソフトがアジュールにテンダーミントを追加 – NewsBtc Japan

関連用語

• Tendermint: テンダーミント
• コンセンサス・アルゴリズム
• Proof of Work: プルーフ・オブ・ワーク
• Proof of Stake: プルーフ・オブ・ステイク
• BFT:　Byzantine fault tolerance
• PBFT: Practical Byzantine Fault Tolerance
• blockchain: ブロックチェーン、ブロックチェイン
• distributed shared database: 分散型データベース
• Eris Industries: エリス・インダストリーズ
• HydraChain: ハイドラチェーン、ハイドラチェイン
• Jae Kwon