Tendermint

概要

アルゴリズム

Tendermint-BFT

Tendermint には BFT に基づいた合意アルゴリズムが実装されている。

1. Proposer から開始し各ノードが Pre-vote をブロードキャストする。
2. 各ノードは他の \(\frac{2}{3}\) 以上のノードから同じブロックの pre-vote メッセージを受信すると pre-commit をブロードキャストする。
3. 受信できない場合、ノードは待機時間を延長し、

Proposer Election

Tendermint は Validator 集合からラウンドごとに Proposer を選択する。このアルゴリズムは、それぞの Validator が持つ票数 (voting power) で重み付けられた Round Robin アルゴリズムであり Proof of Stake の一種と言える。具体的な実装アルゴリズムは Priority Queue で要素を選択する方法と同じである。

\(t = S\) となる時にそれぞれの Validator の選出頻度が概ね Voting Power \(s_i\) と一致することが分かるだろう。

選出アルゴリズム

基本的な選出方針は、ラウンドごとに各 Validator の Proposer Priority に Stake を加算してゆき、最も大きい Priority を持つ Validator を次のラウンドの Proposer とする。Proposer に選出されると Priority は最下位程度まで減算される。ラウンドロビン設計だが、ラウンドごとに Stake を累積してゆくことで Stake 保有量が多く長期間保有している Validator が高い頻度で選出される構造になっている。また実際には加算によってオーバーフローしないように正規化 (再スケーリング) を行っている。

ある Validator 集合 \(\vector{V}\), \(|\vector{V}| = N\) に含まれる Validator \(V_i\) が持つ票数 (voting power \(\simeq\) Stake) を \(s_i\)、ラウンド \(t\) における \(V_i\) の Priority を \(p_{i,t}\) とすると Priority の初期状態は以下のように表される。\[ \begin{equation} p_{i,0} = - C S + s_i \label{initial_priority} \end{equation} \] ここで \(S\) は \(\vector{V}\) 全体の総評数 \(\sum_{i=i}^{N} s_i\)、\(C \simeq 1.125\) は定数である。式 (\(\ref{initial_priority}\)) より初回は Validator の持つ票数の多さで Proposer が選択されることが分かる。また途中から合意に参加する Validator もこの初期値から始まる。

ラウンド \(t\) の各 \(p_{i,t}\) は概ね 0 を中心に \(\pm S\) となるように正規化される。より正確には \(\max p - \min p = 2S\) となるように線形返還され、さらにそれぞれから平均値を減算する。正規化後、Validator ごとに \(q_{i,t+1} = p_{i,t} + s_i\) を求め、最も大きい \(q_{i,t+1}\) を持つ Validator が \(t+1\) ラウンドでの Proposer となる。\[ \begin{array}{rcl} r & = & \left\lceil \frac{\max p_t - \min p_t}{2S} \right\rceil \\ \bar{p}_t & = & \frac{r}{N} \sum_{i=1}^N p_{i,t} \\ q_{i,t+1} & = & (r \ p_{i,t} - \bar{p}) + s_i \\ P_{t+1} & = & \argmax_i q_{i,t+1} \end{array} \] Proposer に選出された Validator の \(q_{P_{t+1},t+1}\) からは \(S\) が減算されて次のラウンドの Proposer Priority となる。\[ p_{i,t+1} = \left\{ \begin{array}{ll} q_{i,t+1} - S \ \ & \mbox{if} \ \ i = P_{t+1} \\ q_{i,t+1} \ \ & \mbox{otherwise} \end{array} \right. \]

\(q_{i,t} = q_{j,t}\) となるような Validator \(i\), \(j\) が存在する場合、そのアドレスのバイナリ表現が小さい方が優先される。票を持たない \(s_i=0\) の Validator は初期状態で最下位であり累積も行われないため (\(S \ne 0\) ならば) Proposer として選出されることはない。

参照

1. Tendermint 公式ドキュメント
2. Yackolley Amoussou-Guenou, Antonella Del Pozzo, Maria Potop-Butucaru, and Sara Tucci-Piergiovanni, Dissecting Tendermint (2019)