Tech

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トランザクション/秒

公式サイト

用語

  • 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)

ベンチマーク

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

参考ページ

関連記事

ニュース記事

関連用語

  • 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
  • このエントリーをはてなブックマークに追加