Tendermint

2019年7月16日 Tendermint 0.32 #Blockchain #Tendermint

概要

アルゴリズム

Tendermint-BFT

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

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

Proposer Election

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

i

Voting Power

s_i

Priority

p_i

Proposer

Frequency

Round

t=

0 , Total Voting Power

S=

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

選出アルゴリズム

※この記述は Tendermint 0.32 のソースコードより読み解いたものであり、Whitepaper で説明している内容とは異なる可能性がある点に注意。

基本的な選出方針は、ラウンドごとに各 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 として選出されることはない。

参照

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