Quorum QBFT コンセンサスアルゴリズムとそのパラメータについて

# 概要
本記事では、 ConsenSys 社が開発しているエンタープライズ向けプライベートブロックチェーン (またはコンソーシアムブロックチェーン) の基盤ソフトウェア [**Quorum** (**GoQuorum**)](https://github.com/Consensys/quorum/) におけるコンセンサスアルゴリズムの一種 **QBFT** を運用する際に必要となる各種概念および重要なパラメータを説明します。

全パラメータを網羅することは目的ではなく、 QBFT によるプライベートブロックチェーンを運用を開始する際に特に検討が必要、つまりパフォーマンスに影響したりする重要なものについて、重点的に説明を行います。

執筆時点での最新版 v23.4.0 時点ではブロック報酬やガス代を有効化することも可能になっていますが、プライベートブロックチェーンの文脈で説明を行い、ガス代およびブロック報酬は使用しないものとします。

Quorum におけるトランザクションプールの挙動や、マイニングそのものの仕組みについては長くなるため、この記事では詳細を省略します。

# コンセンサスアルゴリズムの選定
どのようにして参加者同士でブロックを積み重ねていくのかは、チェーンにより様々です。  
Quorum では、そのブロックを皆で積み上げていくための方法 (**コンセンサスアルゴリズム**) として、主に次のような選択肢があります[^1]。
- Raft
- IBFT (Istanbul Byzantine Fault Tolerant)
- QBFT

[^1]: このほか、 Clique (単に PoA と呼ばれることもあるが、すべてのノードを管理者または管理団体の配下に置くことを前提にしているコンセンサスアルゴリズム全般のことも PoA と呼ぶので注意) と呼ばれるコンセンサスアルゴリズムも選択自体は可能です。しかし、 Clieque は仕組み上チェーンが**フォーク**する (一度取りこんだブロックが取り消され、別のブロックが正式なものとして採択され直されてしまう) おそれがあることから、エンタープライズ用途には向いておらず、ここでは選択肢にあげません。  
一方、 Raft, IBFT, QBFT は、ブロックを取り込むことを一度決定すると、その決定が覆ることはありません。

2023年現在、 ConsenSys は QBFT の利用を推奨しています。特に Raft に関しては、ドキュメントにて[**本番環境では使用しないよう警告がされています**](https://docs.goquorum.consensys.net/tutorials/private-ｔnetwork/create-a-raft-network)。

Raft は、
- トランザクションが送信されるまで無駄なブロックが生成されない
- ブロック間隔が非常に短い (最短 40ms) ためレスポンスに優れる

といった、開発者にとって魅力的な部分がある一方で、
- 高負荷状況下でスプリットブレインに陥ることがあり、最悪の場合ブロックデータが破損して復旧が困難になる [^2]
- リーダーを一度決めるとリーダーがダウンしない限りはリーダーの言うことを聞き続ける仕組みになっているため、悪意あるノードに対しての耐性を持っていない
- Raft ではブロックの `timestamp` の単位が細かいため一般的な Ethereum の秒単位のタイムスタンプと互換性がなく、 Ethereum 関係の OSS を利用する際、 IBFT/QBFT に比べてより手間がかかる確率が高い

[^2]: Raft のドキュメントには単に「非推奨」としか書かれていないため、私が ConsenSys 公式 discord でこの詳細について質問した際に、主要な開発者の一人から帰ってきた回答です。残念ながら quorum チャンネルは現在では
閉鎖され、中身を確認できないことから、出典のリンクはありません。  
実際、 Raft クラスタに対して極端な負荷をかけた場合、コンセンサスが停止し、再起動しても治らない (データロス) する事象が発生したことがあるので、正確な原因は不明ですが、本当だと思います。

といった問題点があります。

IBFT はこれに対して悪意あるノードに対しての一定の耐性 (`3F+1`台のノードであれば `F`台の悪意あるノードに耐性を持つ) を持っており、よりブロックチェーンに適しています。しかし、ブロック間隔は一定であり、トランザクションが送信されなくても空のブロックが生成され、リソースを消費します。さらに、ブロック間隔は秒単位であり、最小の 1 秒であっても、Raft よりレスポンス性は落ちてしまいます。

QBFT は IBFT を改良したアルゴリズムで、空ブロックの生成間隔を抑えられたり、その他追加の機能や柔軟なパラメータ変更が行えるため、新規で作るのであれば QBFT が強く推奨されています。そのため、この記事では QBFT に関しての説明のみ行います。

# ノードの役割
QBFT においては、ノードは次の役割に分かれます。

- **validator** (バリデータ)
自分でブロックを生成、または他の validator が作ったブロックを承認する権利があるノード。  
後から追加および削除することも可能。
初期の validator ノードの一覧は `genesis.json` の `extraData` に、一定のフォーマットでバイナリエンコードして記載する。この値の生成は手動では困難なので [quorum-genesis-tool](https://github.com/Consensys/quorum-genesis-tool) などを使用する。
- **non-validator** (非バリデータ, またはメンバノード)
ブロックを生成および承認する権利がなく、単にブロックを受け取って同期することのみが可能なノード。  
トランザクションは接続中の全ノードにブロードキャストされる仕組みのため、直に validator に RPC コールを投げることなく間接的に伝搬させるプロキシのような役割を持たせたり、読み込みのみのリクエスト負荷を validator からオフロードするために、必要に応じて設置する。  
不特定多数のノードから接続されることを防ぐため、`static-nodes.json` (または Enhanced Permissioning と呼ばれるより高度な機能) で接続可能なノードを限定することも可能。

基本的には validator ノードをコンセンサスで必要とされている台数だけ設置した上で、 non-validator ノードを要件に従って追加で設置します。

また、 validator の中から、 **proposer** (プロポーザー) がブロック毎に決定されます。 PoW のように、早い者勝ちで皆が競ってブロックをマイニングしている訳ではありません[^4]。  
ブロック毎に決定された proposer のみがブロックを生成する権利を持っており、残りの validator はそれを承認します。ブロックそのものとは違い、 proposer 自体の決定には承認を必要とせず、後述の proposer policy に従って決定的に定まります。
[^4]: Quorum の実装上は `--mine` オプションが付いていると自分が proposer か否かにかかわらず、必ず毎ブロックマイニング自体は試行します。しかし、マイナースレッドからコンセンサス側に採掘したブロックを報告する際、コンセンサス側で自分が proposer かどうか判定しており、 proposer でなければ暗黙のうちに捨てられます。なので、実装から厳密に言えば "マイニング自体は全員行うが、コンセンサス側が捨てている" となります。


validator の中からブロックごとに自動で proposer が選択され、その proposer がブロックを生成し、一定数以上の validator から承認されると、正式なブロックとして確定します。この繰り返しです。

### コンセンサスに必要な台数
QBFT においては、不正なノードが `F` 台存在しても正常にコンセンサスが継続できる valivadator ノードの最小台数は `3F + 1` 台です。  
これは、不正なノードが存在している状況下で正しく承認を行うために必要な台数`M`が、総台数`N`に対して `M > (2N/3)` となっているからです。  
上記のように等号が入っていないため、 2/3 ちょうどでは不足となり、 4 台が必要になります。

|validator の台数|許容できる不正なノードの最大数|
|---|---|
|1|0|
|2|0|
|3|0|
|4|<font color="red">**1**</font>|
|5|1|
|6|1|
|7|<font color="red">**2**</font>|
|8|2|
|9|2|
|10|<font color="red">**3**</font>|

このように、例えば 1 台でも 2 台でも、許容できる不正なノードの最大数は 1 台もなく、冗長性はありません [^3]。  
従って原則 4 台、または 7 台構成となります。

冗長性を高めたければ 10 台や 13 台, ... としても問題ありませんが、コミュニケーションコストが増加してパフォーマンスが悪化する可能性があるため、よほどの理由がない限り、4 台か 7 台になると思います。

[^3]: 例えば 1 台と 2 台は不正なノードへの耐性 (ビザンチン耐性) の観点では耐性なしといえますが、Quorum ではベースとしている go-ethereum (geth) 同様、予期しない終了の仕方 (**unclean shutdown**) をすると、データロスが発生し得ます。もし 2 台いれば、クラスタとして冗長性はなくても、片方が unclean shutdown した場合、別のノードにデータを取り寄せて同期 (復旧) を試みることが可能なため、データロスしたときに助かる確率は高まります。 開発用といえども 1 台だけにするかはこの点を考慮した方がよいでしょう。

### sequence と round
QBFT では、ブロックごとに proposer が定まり、担当となった proposer はブロックのマイニングを行います。  
マイニングを行ったら、それを皆に提案し、一定以上の承認を得ると、最終的に皆で取り込んでそのブロックの処理を終え、次に行きます。 

しかし、様々な要因により、この一連のプロセスを終えられない場合があります。  
典型的なのは、そのブロックで proposer になるはずだった validator がダウンしている場合です。

このような場合に備え、 QBFT では一定のタイムアウト期間が設けられており、それが超過すると同じブロック番号で「仕切り直し」を行います。この「仕切り直し」のことを **round change** と呼び、そのブロック番号で round change が発生した累計回数のことを **round** と呼びます。  
従って round は `0` から始まり、次のブロックに移ることができれば round はまた `0` になります。

また、 QBFT コンセンサスの用語では、ブロック番号のことは **sequence** と呼んでいます。 QBFT 関連のログを見ると `seq=xxx` のようにブロック番号が表記されているのがわかると思います。今後、この 2 つの用語は文脈次第で入れ替え可能なものとして扱います。

### proposer の決定方法 (proposer policy)
ブロックとは違い、proposer は承認プロセスを経ることなく、決定的に定まります。  
QBFT では、 proposer を決定するための方式を **proposer policy** と呼んでおり、`genesis.json`で`qbft`フィールド配下の`qbft.policy`に以下の値を入れることで、方式を変えることができます。

|値|名前|決め方|
|---|---|---|
|`0` (default)| round robin | sequence ごとに、validator の中から決まった順番で回す。<br />round が進んだ場合も順番に回していくが、次の sequence に遷移した場合は、前の sequence でかかった最終的な round ではなく round `0` の時の validator 対して次の順番のものが proposer になる。 |
|`1` | sticky | 一度 proposer になった場合はノードがダウンしない限りそのノードが proposer になり続ける。 round が進んだ場合は順番に交代する。 |

現時点ではラウンドロビンか sticky の 2 つしかありません。 sticky は同一ノードが proposer になり続けられれるため、 Raft と同様、ブロックチェーンの信頼性の観点から、避けた方がよいでしょう。

このように、 proposer policy は `(sequence, round)` の組によって一意に定まるため、コンセンサスを取る必要はなく、ノードの状態が遷移すればオフラインで決定できます。

そこまで重要ではないと思いますが、参考に round robin proposer policy 時の proposer の遷移の仕方を以下に掲載します。4 台構成で、ノード `A, B, C, D` の順番で proposer が交代していくものとし、ブロック `N` では `A` が proposer であるものとします。

|sequence|round 0|1|2|3|4|5|...|
|---|---|---|---|---|---|---|---|
|`N`|`A`|`B`|`C`|`D`|`A`|`B`|`...`|
|`N+1`|`B`|`C`|`D`|`A`|`B`|`C`|`...`|
|`N+2`|`C`|`D`|`A`|`B`|`C`|`D`|`...`|
|`N+3`|`D`|`A`|`B`|`C`|`D`|`A`|`...`|
|`N+4`|`A`|`B`|`C`|`D`|`A`|`B`|`...`|

# コンセンサスの流れ
QBFT では、内部的にいくつかのステートが存在しています。コンセンサス内でメッセージをブロードキャストしあって、内容を確かめつつ次のステートに遷移していきます。

|ステート|メッセージ|意味|次に遷移する条件|
|---|---|---|---|
|`AcceptRequest`|`PRE-PREPARE`|proposer からのブロックの提案を待っている状態。<br />proposer 自身の場合、マイナースレッド側からマイニングが完了するのを待っている状態。|proposer のマイニングが完了し、その提案内容を `PRE-PREPARE` メッセージとして受け取った場合。|
|`Preprepared`|`PREPARE`|proposer から提案内容を受け取ったので、他のノードからも受け取りの確認待ち。|validator 同士で `PREPARE` メッセージをブロードキャストし、`2N/3` を超えるメッセージを受け取った場合。|
|`Prepared`|`COMMIT`|実際にこのブロック検証して、取り込んでよいことを決定する。|validator 同士で `COMMIT` メッセージをブロードキャストし、 `2N/3` を超えるメッセージを受け取った場合。|
|`Committed`|なし|ブロックの取り込みが正式に決定し、取り込み中。|取り込みが完了する。|
|`FinalCommitted`|なし|取り込みが完了して、次に進む準備が整った。|sequence, round を更新して次に進む。|
|常時|`ROUND-CHANGE`|request timeout に達してノードが仕切り直しを行った|round を進めて `AcceptRequest` に進む。|

メッセージの観点で言うと
- proposer がマイニングし次第 `PRE-PREPARE` を送信し、受け取ると `Preprepared`
- 受け取った印として `PREPARE` を送信し、一定数集まると `Prepared`
- 取り込みを確定してよいとする印 `COMMIT` を送信し、一定数集まると `Committed`
- 実際にブロックを取り込み、取り込み終わったら `FinalCommitted -> AcceptRequest` に遷移 [^6]

[^6]: 内部実装上、 proposer はすでにマイニング時にステート遷移をすべて計算済みなので内容がキャッシュされており、取り込みは他の validator よりも早く終了し、先に `FinalCommitted` に遷移しやすいです。

となります。


# ブロック間隔
QBFT の場合、ブロック生成間隔はチェーンのパラメータとして設定することができ、固定値を指定します。 `genesis.json` に `blockperiodseconds` という項目があり、そこで指定します。秒単位で指定を行い、最小値は`1`です。ここで指定した間隔ごとに、ブロック生成を試みます。

ブロック間隔は、実装上はあくまでブロックに記録されているブロックの生成時刻 (`timestamp`) の前のブロックからの差分がが少なくともこの秒数以上であることを保証するだけのものであり、重いトランザクションなどが多い状況では `blockperiodseconds` 以上の処理時間がかかることがあります。当然、障害があればブロック生成は停止したり、遅れが出ます。したがってぴったりこの秒数ごとにブロックが生成されるという厳密な保証はないので、注意が必要です。

何秒にするかは悩ましい所ですが、レスポンス時間を最小化したいのであれば、`1` に設定します。  
一方で、レスポンス時間を短くすると、相対的にブロック生成自体のオーバーヘッドが大きくなるので、余裕があるのであれば`5`や`10`など、多めの秒数の方が良いでしょう。

## 高負荷時の挙動との関係
QBFT においては、ブロック間隔以内にマイニングを完了することが前提となっています。ノードがダウンしているなどでコンセンサスが進まないまま一定時間が経過するとタイムアウトすると書きましたが、実はノードに異常がないにも関わらず、所定時間内にマイニングを完了することができなかった場合、 round change とは別の挙動が引き起こされます。具体的には、
- 時間がかかるトランザクションが含まれている
- 単純にトランザクションの数が多い
- RPC コールなどの影響でノードの負荷が高まっておりマイニングに十分な CPU 時間を割けない

といった要因で、この問題が発生します。

具体的には、 proposer がトランザクションプールに保有しているすべてのトランザクション処理をブロック時間以内に終えることができなかった場合、 proposer は途中経過ではなく**空のブロックを提案**してしまいます。具体的には、次のような一連の事象が発生し、最終的には障害となります。

1. ノード 1 が proposer になる
2. ノード 1 はブロック間隔以内にマイニングを完了できず、空ブロックを提案し、承認される。
3. 空ブロックが承認された結果、新しいブロックがノード 1 にも取り込まれ、終了していなかったマイニングは強制的にキャンセル (内部的には `commitInterruptNewHead` と呼ばれるシグナルを受信する) される
4. ノード 2 が proposer になるが、ノード 1 と同じトランザクションを保有しているので、やはり処理を完了できない。
5. 以下、**空ブロック提案ループ**に陥り、トランザクションの処理が永久に進まない。

このような事態を避けるためには、
- ブロック間隔に余裕を持たせる
- トランザクションプールを小さくする (`--txpool.globalslots` および `--txpool.globalqueue`)
- block gas limit を適切に抑える
block gas limit を超過した場合は、例外的に処理を切り上げて途中経過を報告する実装になっているためです。

といった対策が挙げられます。
なお、非公式ながらもこの問題は後述の `emptyblockperiodseconds` でも緩和できることが、私の調査によって判明しています。

## `emptyblockperiodseconds`
IBFT/QBFT では、`blockperiodseconds` 秒おきにブロック生成を試み、トランザクションが何も送信されていなくても空のブロックが生成されます。生成されたブロックは消せない情報として永遠に蓄積され続けるため、このリソースの無駄を抑えるためのパラメータが `emptyblockperiodseconds` です。

現在マイニングしようとしているブロックにおいて、Proposer のトランザクションプールに何もトランザクションがなかった場合、追加で `emptyblockperiodseconds - blockperiodseconds` 秒待機してから空ブロックを提案することで、リソースの消費を抑えます。

しかしながら v23.4.0 時点までの実装では、 `emptyblockperiodseconds` を有効にした場合、[低確率でチェーンがフォークしてコンセンサスが停止してしまう致命的な現象](https://github.com/Consensys/quorum/issues/1630)が知られており、安全に使用するためには[私が作成した修正内容](https://github.com/Consensys/quorum/commit/65de7ae6bef51f22e703cc270d8024681d2fde4a) (執筆時点で `master` に取り込まれている) を適用する必要があります。

このオプションを有効にした場合、ブロック間隔は最大 `emptyblockperiodseconds` までの間で、不定になります。`1ブロック = N秒` のような仮定をアプリケーション側でおいている場合、注意が必要です。

また、高負荷時にブロック間隔以内に proposer がマイニングを終えられないと空ブロックが提案されると書きましたが、 `emptyblockperiodseconds` を有効にすると空ブロック提案までの時間が延長される仕様を逆手に取って、あえてこのパラメータを有効にすることで高負荷時に発生するスタックを緩和する (ブロック間隔中にマイニングが終えられなければ `emptyblockperiodseconds` の効力によりその制限時間が延長されるようになる) というテクニックも考えられます[^5]。
[^5]: あくまで実装を利用したハックに近いものなので、仕様変更により使えなくなる可能性は否定できません。この場合は今後アップデートしていく際、仕様変更についてより敏感になる必要があります。

# request timeout と round change
QBFT では、コンセンサスアルゴリズム上の内部ステートがいくつか存在しており、互いに確認し合って次のステートへと進んで最初のステートに戻る、ということを繰り返し、ブロック生成を進めています。

このステート遷移には制限時間が設けられており、その制限時間に間に合わない場合は現在の proposer は正常でないとみなし、現在のブロックは生成できていないのでブロック番号が同じまま、 proposer を交代して仕切り直しをしようとします。この仕切り直しのことは **round change** と呼ばれており、round change が発生するとブロック番号が同じまま仕切り直し回数 (**round**) が増え、 proposer を交代した上で、一連のステート遷移が最初からやり直されます。  

このタイマーはすべてのステート遷移ごとにリセットされる訳ではありません。仕様として明示されている訳ではありませんが、 v23.4.0 時点の実装上は

1. `blockperiodseconds` 、または有効になっている場合は　`emptyblockperiodseconds` が経過した後
2. `Prepared` 遷移時

でリセットされます。

`genesis.json` の `requesttimeoutseconds` にて、 round change が発生するまでのタイムアウト秒数を指定します。なお、`requesttimeoutseconds` は round が進むごとに**2の指数関数によるバックオフ**が行われ、``requesttimeoutseconds * 2**round`` と計算されます。  

コンセンサスが進められる範囲内の台数がダウンした場合、 proposer は持ち回り制のため、落ちたノードに到達するたびに必ず `requesttimeoutseconds` だけ待たされる挙動となります。`blockperiodseconds`を小さな値にした場合、相対的なパフォーマンス劣化を抑えるために、`requesttimeoutseconds` はデフォルト値よりも小さくした方がよいでしょう。

## `maxrequesttimeoutseconds`
`requesttimeoutseconds` は、ラウンドが進むごとに、つまり順番に proposer をあたっても生きているノードにたどり着かない場合、タイムアウト秒数を倍に伸ばしていきます。障害が起きた際、ラウンドが進みすぎると、次のラウンドに進むまでに数分～数十分要するようになってしまい、長時間待機するか全ノードを再起動するしか復旧の手段がなくなってしまうことも考えられます。

これを回避するために、 `requesttimeoutseconds` の上限値を抑えるためのパラメータ `maxrequesttimeoutseconds` が存在しています。この値が指定されている場合は、バックオフを続けていったとしても、この秒数以上になることはありません。

しかし、v23.4.0 時点では、 `maxrequesttimeoutseconds` を有効化した場合、[一定のラウンド経過後に request timeout 秒数がマイナスまたは 0 秒になってしまい、即時 round change が発生し続けて復旧不能になる不具合](https://github.com/Consensys/quorum/issues/1664)が知られています。この機能を安全に使用するには、現時点で `master` に取り込まれている[私が作成した修正内容](https://github.com/Consensys/quorum/pull/1665)を取り込む必要があります。

## `PREPARE` justification
実装上 validator は自分が proposer でない時でも、すべてのブロックにおいてマイニングを試みます。これには意味があり、障害が起きるなどして round が進み、自分が proposer になった時に、あらかじめマイニングしておいたものを即時提案できるようにする目的があります。

また、すでに `PREPARE` メッセージを十分な数受け取り `Prepared` にいったん遷移すると、その内容は **`PREPARE` justification** として保管されます。 round change が発生すると、 `ROUND-CHANGE` メッセージに、これを justification と呼ばれるパラメータとして添付します。十分な `ROUND-CHANGE` メッセージが集まると、次の proposer はその proposal を引き継ぎ、自分自身が独自にマイニングし直すオーバーヘッドを削減します。

# まとめ
本字記事では、 Quorum で QBFT コンセンサスを利用したプライベートブロックチェーンを運用する際に必要な基本的な用語を整理し、コンセンサスの流れを説明しました。また、運用に必要となる主要なパラメータについても整理しました。

内容について問題点や疑問がある場合は Twitter アカウントに連絡するなどしてください。