Blockchain: Polkadot

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

Table of Contents

1. BABE
2. 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) (日本語訳)