Tendermint
最近ブロックチェーン業界で少しはやってきている、Cosmos SDKのコンセンサスエンジンです。
以下Whitepaperのコンセンサス部分日本語訳です
Tendermintは、DLSコンセンサスから派生した、部分的に同期されたBFTコンセンサスプロトコルです。Tendermintのシンプルさ・パフォーマンス・フォーク耐性が注目に値します。Tendermintのコンセンサスプロトコルは、それぞれ公開鍵によって区別された、固定のバリデータセットが必要です。バリデータは、ある時間において、トランザクションのリストとしての1つのブロックについて、合意に到達しようとします。同意に達するための投票は、複数のラウンドで進みます。それぞれのラウンドには、ブロックを提案する、ラウンドリーダーまたはプロポーザーが存在します。それぞれの段階において、バリデータは、提案されたブロックに対して同意するか、もしくは次のラウンドに進むかを投票します。各ラウンドの提案者は、Voting Powerの保有量に応じて並べられたリストから、決定論的に選出されます。
Tendermintのセキュリティは、スーパーマジョリティ(2/3以上のVoting Power)とロッキングメカニズムを通した最適なビザンチン耐性を根拠としています。
同時に、それは以下のことを保証します。
・2つ以上の値をコミットし、セキュリティを破るためには、1/3以上のビザンチン(悪意あるノード)が必要
・コンフリクトするブロックへの投票や、悪意のある投票を含む、セキュリティを脅かす行動をしたノードは、プロトコルによって特定される
このような強い安全性にも関わらず、Tendermintは非常に高いパフォーマンスを誇る。5大陸7データセンターに分散する、一般的なクラウドインスタンスを使った64のノードで、Tendermintは、1 ~ 2秒のコミットレイテンシで、数千ものトランザクションを捌ける。そしてそれは、クラッシュしたノードや、悪意のあるデータをブロードキャストするノードが含まれていても維持できることにも、言及しておくべきだろう。
※ コミットレイテンシ... ブロックのコミットによる遅延(のことだと思う)。
Tendermintは、1/3以上悪意のノードがいなければ、堅牢でハイパフォーマンスなブロックチェーン運用ができるということですね。
今回は、上記の引用に登場するDLSコンセンサスについて、簡単にまとめていきたいと思います。
DLS Consensus
下記の論文の内容をベースにしています。
Consensus in the Presence of Partial Synchrony
アブストラクトだけ載せます。
The concept of partial synchrony in a distributed system is introduced. Partial synchrony lies between the cases of a synchronous system and an asynchronous system. In a synchronous system, there is a known fixed upper bound A on the time required for a message to be sent from one processor to another and a known fixed upper bound % on the relative speeds of different processors. In an asynchronous system no fixed upper bounds A and @ exist. In one version of partial synchrony, fixed bounds A and Cp exist, but they are not known a priori. The problem is to design protocols that work correctly in the partially synchronous system regardless of the actual values of the bounds A and Cp. In another version of partial synchrony, the bounds are known, but are only guaranteed to hold starting at some unknown time T, and protocols must be designed to work correctly regardless of when time T occurs. Fault-tolerant consensus protocols are given for various cases of partial synchrony and various fault models. Lower bounds that show in most cases that our protocols are optimal with respect to the number of faults tolerated are also given. Our consensus protocols for partially synchronous processors use new protocols for fault-tolerant “distributed clocks” that allow partially synchronous processors to reach some approximately common notion of time.
この論文では、部分的同期システムにおいて、合意に達することを目的としています。同期システムというのは、異なるプロセッサー(ノード)間でデータを同期するシステムで、この場合、メッセージをノード間で送信するのに、固定の上限値が存在し、これはプロセッサーの処理速度による上限 Δ と、ネットワーク通信にかかる時間の上限 Φ によって表現されます。
そして、部分的同期について、2つの場合を仮定しています。
シチュエーション1: メッセージ送信にかかる上限時間に、固定時間が存在するが、それは事前に知られていない。
シチュエーション2: メッセージ送信にかかる上限時間は既知であるが、同期開始時刻 Tはわからない。
DLSコンセンサスは、合意を複数のラウンドによって形成します。さらに、各ラウンドは、
- 送信サブラウンド
- 受け取りサブラウンド
- 計算サブラウンド
の3つのサブラウンドから成ると考えます。
送信サブラウンド -> 各ノードは、任意の複数ノードに、メッセージを送信する。
受け取りサブラウンド -> 送られたメッセージを受信し、それを送信します。
計算サブラウンドでは -> 受け取ったメッセージを元に、ステートを更新します。
このとき、全てのメッセージが受信されることを保証する必要はなく、一部は失われる可能性もありますが、未来におけるどこかのタイミングで、全てのメッセージはいつか受信されると仮定します。このメッセージが完全に受信されるタイミングをGSTとします。GSTに到達する前には、メッセージの送信・受信漏れを許します。
上記の仮定の元、各ラウンドには、同期するべき値vを提案するプロポーザー p がいます。あるラウンドにおいて、p が値vをproposeする場合、最低でもN-t のノードからその値vが正しい値であるということを伝達される必要があります。(Nはノードの総数、tは障害を許容するノードの数)
一定数のノード(N-t)から、vを受け取ったら、pはvをロックして、その情報を他のノードにブロードキャストします。ロックされたvを受け取った他のノードは、その情報を受け取ったことをpに対して通知します。pは、少なくともt+1以上のノードから、vを受け取った通知がきた段階で、vを確定させ、コミットします。その後、pはvが確定したことを他のノードに通知し、それを受け取ったノードはvを確定し、コミットします。
まとめると、各ラウンドにおいて、プロポーザーpが存在し、少なくともN-tのノードが正常に動いている場合に
- 各ノードは、自分が正しいと許容できる値を他のノードに送信し合う
- pは、N-t以上のノードから送られてきたvという値を正しい値としてvをロックし、propose(提案)する
- ロックされたvを受け取った他のノードは、その情報を受け取ったことをpに通知する
- t+1以上のノードから通知が来た場合、pはその値を確定させ、コミット、他のノードブロードキャスト
- 4の通知を受け取ったノードは、vを確定させ、コミットする
上述したサブラウンドでいうと、
1 -> 送信サブラウンド
2,3 -> 受け取りサブラウンド
4,5 -> 計算サブラウンド
ということだと思います。
この処理を繰り返すことで、部分的に最終的にGSTに達した時には全てのデータの同期が取れる、というわけですね。
Tendermintは、このDLSコンセンサスをベースとしていて、プロポーザーpはATOMの保有量に応じて決定論的に決まっていき、ブロック単位で投票を行うことで同期を取っていく、ということですね。