ブロックチェーンコンセンサス概要

導入

ブロックチェーンのコンテキストでコンセンサスと呼ばれているものは、分散システムで言うところのリーダー選出と合意のアルゴリズムまたはより抽象的なスキームを意味する。バズワード的に使用されており曖昧であるため文脈には注意する必要がある。この記事では選出と合意のアルゴリズムを指すものとする。

分散システムと同様にブロックチェーンにおける整合性機構もリーダー選出 (leader election) と合意 (agreement) とに分けることができる。

1. 導入
2. 基本アルゴリズム
   1. リーダー選挙アルゴリズム
      1. Proof of Work
      2. Proof of Stake
   2. 合意アルゴリズム
      1. Bitcoin の最長優先ルール
      2. Ethereum の最重優先ルール
      3. BFT プロトコル
3. Tendermint
   1. -
      1. -
         1. Proposer Election
            1. 選出アルゴリズム
4. Polkadot
   1. BABE
   2. GRANDPA

基本アルゴリズム

リーダー選挙アルゴリズム

Proof of Work

Proof of Stake

合意アルゴリズム

Bitcoin の最長優先ルール

Ethereum の最重優先ルール

BFT プロトコル

Tendermint

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 として選出されることはない。

Polkadot

Polkadot の合意メカニズムは従来の Ethereum と同様に PoW に基づきチェーンの分岐が発生する BABE という機構と、分岐した枝のどれが採用されるかを選択する GRANDPA ^[1] という機構の 2 つに分かれている (彼らはこれをハイブリッドコンセンサスと呼んでいる)。つまり BABE が非決定的な処理シーケンスを作成し GRANDPA が合意に相当するアルゴリズムを実装する。

BABE

BABE (Blind Assignment for Blockchain Extension protocol) は Ouroboros Praos から派生したアルゴリズム。1 つのブロックを生成する単位をスロット \(sl_j\) と呼び、\(t\) を上限とするいくつかのスロットをまたいだ期間をエポック \(e_i = \{sl_1^i,sl_2^i,\ldots,sl_t^i\}\) とする。エポック \(e_i\) の開始時に、そのエポックに含まれる全てのスロット \(sl_j^i\) にランダムにスロットリーダーを割り当てる。スロットごとに選ばれる Validator はスロットリーダーが VRF を使用して秘密裏に決定し、ブロックが生成され公開された時点で初めて公開される。

BABE は全ての Validator が同じ量の Stake を持っているため、スロットリーダーの選出確率は全て同じである。

GRANDPA

他の多くの合意アルゴリズムが生成されたブロックごとに検証済みの整合性とチェーンの接続で合意するのに対して、GRANDPA は PoW により発生した分岐のどれを採用するかを決定する目的で分岐に対して合意を行う。

GRANDPA (GHOST-based Recursive ANcestor Deriving Prefix Agreement) のアルゴリズムはチェーンの分岐がツリー構造となる性質をうまく利用した投票に基づいている。PoS によって選出された委員会のメンバーそれぞれは、自身が妥当と判断した位置のブロックに投票する。チェーンの分岐は自然にツリーの形となるため、根に向かって票数を加算して行き、(想定するビザンチン数を \(f\) と仮定すると) \(2f+1\) 票以上を獲得しているブロックがファイナリティを得たものとみなす。

Fig 1 はこのスキームに従い \(f=1\)、メンバー総数 \(N=3f+1=4\) として 3 票を獲得している \(X_1\), \(Y_1\), \(Y_2\) が確定したことを示している。

委員会のメンバーはそれぞれどの分岐に投票したかについて合意しなければならない (さもなくば委員メンバーに紛れ込んだビザンチンノードがある方面には \(X\) に投票したと主張し、別の方面には \(Y\) に投票したと主張でき safety が欠落する)。このためには BFT のようなアルゴリズムを使用しなければならないが、その点に関して言及されている資料はまだ見つけていない。

• ¹ Byzantine Finality Gadgets (2019) (日本語訳)