Ethan BuchmanのTendermint論文を覗いてみる4

本稿について

本稿は、Tendermintホワイトペーパーの詳細版ともいえるTendermint現CTOであるEthan Buchman氏の執筆論文をもとにTendermintについて見ていくシリーズです。冒頭に筆者による「簡単まとめ」を入れ、その後にもととなった部分の日本語訳を載せるという順番で書いていきます。

論文「Tendermint： Byzantine Fault Tolerance in Age of Blockchain」の原文はこちら。

今回の対象範囲は第3章「Tendemint Consensus」のうち、3.2「Consensus」の3.2.3「Locks」と3.2.4「Formal Specification」で、これを読むとTendermintのコンセンサスの3つの構成要素のうちの「ロック」と、コンセンサスの「形式仕様」についてやや詳しい内容が分かります。

原文はこちらになります。

スポンサードサーチ

要点をまとめてみる

• ロックには2つのルールがある。これによりセーフティとライブネスを守る。
  • Prevote-the-Lock：バリデータは、自らがロックされているブロック以外のブロックに事前投票することはできない。提案者ならば、そのブロック以外のブロックを提案することはできない。
    • これによりセーフティを守ることができる。
  • Unlock-on-Polka：ロックされたラウンド以降のラウンドでポルカが確認されない限り、バリデータはロック解除されることはない。
    • これによりライブネスを守ることができる。
• 形式仕様に関して
  • chooseproposal(p)は、pが空集合でない場合に提案pを返し、事前投票を行う。そうでなければmempoolからトランザクションを収集する。
  • そのラウンドにおいてあるブロックが全体の2/3より大きな事前投票を集めた場合はそのブロックを事前コミットする。どのブロックも2/3より大きな事前投票を集めないままそのラウンドの事前投票の集合が全体の2/3より大きくなった場合は空を事前コミットする。いずれでもない場合は、他バリデータからの事前投票を待つ。後のラウンドで投票が受信される場合はそのラウンドに移行する。
  • そのラウンドにおいてあるブロックが全体の2/3より大きな事前コミットを集めた場合はそのブロックをチャネルにブロックを流してコミットし、プロトコルを終了する。どのブロックも2/3より大きな事前コミットを集めないままそのラウンドの事前投票の集合が全体の2/3より大きくなった場合は次のラウンドへ移行し、提案を行う。いずれでもない場合は、他バリデータからの事前コミットを待つ。後のラウンドで投票が受信される場合はそのラウンドに移行する。

以下、今回取り扱った箇所の日本語訳なので詳細を知りたければどうぞ。

Chapter3. Tendermintコンセンサス（続き）

3.2 コンセンサス（続き）

3.2.3 ロック

同一ブロック高の2つの異なるラウンドでコミットされた2つの異なるブロックに正当性を与えてしまうような状況は避けなければならないので、ラウンドをまたがるセーフティの確保は扱いにくいものとなるだろう。Tendermintでは、ポルカ（つまり、同一ブロックに対する2/3より多くの事前投票）を中心に展開するロックメカニズムでこの問題を解決する。本質的に事前コミットはポルカによって正当性を与えられていなければならなず、バリデータは自分が事前コミットした最後のブロックにロックされている（locked）と考えられる。ロックには2つのルールがある。

• Prevote-the-Lock：バリデータは、自らがロックされているブロックに対して事前投票をせねばならず、そして自らが提案者であるならばそのブロックを提案せねばならない。これによりバリデータは1ラウンドあたり1ブロック事前コミットすることはできなくなり、それに伴って次のラウンドの異なるブロックに対するポルカへ貢献することもできなくなるので、セーフティの侵害も防げる。
• Unlock-on-Polka：バリデータがロックから解放されるのは、ロックされているところよりも後ろのラウンドでポルカを確認した後に限られる。これにより、バリデータはネットワークの残りのバリデータがコミットしたがらないものに事前コミットしていた場合はロック解除されるので、ライブネスが守られることになる。しかし、これをセーフティを侵害しないやり方で実行する方法は、バリデータがロックされた状態になった後にあるラウンドでポルカに至った場合にロック解除を許可するという方法しかない。

簡単のため、バリデータは各ブロック高のラウンドr -1で空にロックされるものとして考えてみると、Unlock-on-Polkaは、バリデータはポルカを確認するまで新しいブロック高で事前コミットできないということを示唆する。

例を通じてこれらのルールをもっと直観的に理解できる。4つのバリデータA、B、C、Dを考え、ラウンドRでブロックXに対する提案があると仮定する。ブロックXに対するポルカがあるが、Aはまだポルカを確認していないとすると、Aは空に事前コミットし、その他のバリデータはブロックXに事前コミットする。さて、いま他全ての事前コミットを確認する唯一のバリデータがD、一方で他全て（筆者注：A、B、C）はDの事前コミットを確認していない（彼らは2つの事前コミットとAの空に対する事前コミットのみを確認している（筆者注：A、B、C視点で確認しているのはA、B、Cの事前コミットだけ））とする。Dはいまブロックにコミットしようとするときに、一方で他のバリデータはラウンドR + 1に進む。バリデータの誰もが新しい提案者になる可能性があるので、新しいブロックYを提案し投票できるとすれば、彼らはそのブロックにコミットしてセーフティを侵害できる。なぜなら、既にDはブロックXにコミットしているからである。この例ではビザンチンなふるまいをしているものは誰一人としておらず、ただ非同期性があるだけである点に注意されたい。

他のバリデータはその事前コミットに基づいてコミットするかもしれなかった（この例のDのように）ことから、バリデータを自らが事前コミットしたブロックに縛り付けることでロックはこの問題を解決する。本質的に、ひと度2/3より多くのバリデータがあるラウンドのブロックに事前コミットすると、ネットワークはそのブロックにロックされてしまい、換言すればこの後のラウンドで異なるブロックに対する有効なポルカを生成することはできなくなる。これがPrevote-the-Lockの直接的な動機である。

しかしながら、Prevote-the-Lockは十分とは言えない。ライブネスを犠牲にしないようにロック解除する方法がなければならない。AとBがブロックXに事前コミットする一方でCとDが空に事前コミットした場合、つまり票割れの場合を考えてみよう。全員が次のラウンドに進み、ブロックYが提案されて、CとDがこれに事前投票する。Aがビザンチンであると仮定すると、AはブロックYに事前投票し（ブロックXにロックされているにも関わらず）、結果的にポルカとなる。Bはポルカを確認しておらず空に事前コミットしたとして、Aはオフラインになり、CとDはブロックYに事前コミットしたとする。彼らは次のラウンドに進むが、Bは依然としてブロックXにロックされたままであり、CとDはいまブロックYにロックされており、Aはと言えばオフラインであるので彼らがポルカを得ることは決してない。このように、1/3以下（この例の場合は、1バリデータ）のビザンチンなバリデータがいればライブネスを侵害できてしまう。

ロック解除に明確な正当性を与えるものがポルカである。BがブロックYに対するポルカ（先ほどCとDがブロックYに対する事前コミットを正当化したもの）を確認したら、Bはロック解除されなければならず、そしてブロックYに事前コミットする。これがUnlock-on-Polkaの動機である。これにより、バリデータは自身がロックされているラウンドよりも後ろのラウンドでポルカを確認したら、ロック解除（して新しいブロックへ事前コミット）することができるのである。

3.2.4 形式仕様

さて、これまで詳細にプロトコルを説明してきたので、次にπ-calculusで形式仕様を与える。

Consensus := ∏^N_i=1 Y_iは、N個のバリデータの集合に対するコンセンサスプロトコルを表し、それぞれが相互に排他的なプロセスの集合の1つY_iを実行するものとする。内部ステートs = {r, p, v}は、厳密に増加するラウンドr、このラウンドに対する提案ブロックも含む提案p、投票の集合vからなる。v¹_rはラウンドrでの事前投票の集合、v²_rはラウンドrでの事前コミットの集合を表す。また、vote :: vは集合{vote}とvの和集合（つまり、vにvoteを加えたもの）を表す。proposer(r) = r mod Nをラウンドrにおける提案者のインデックスであると定義する。プロトコル内の特定のポイントにおけるピアをY^r,p,v_iと表現する。Y_iは提案（propose）PR_i、事前投票（prevote）PV_i、事前コミット（precommit）PC_iに及ぶ。PVとPCの再帰を捉えるための追加の副次的関数を導入し、PV1、PV2などと表す。

ピア同士は、それぞれのメッセージタイプ、すなわちpropose_i、prevote_i、precommit_iごとのブロードキャストチャネルだけでなく、ある値d_iを決定あるいはコミットするためのチャネルを使って接続している。記号の濫用により、ブロードキャストチャネルxxx_i上を流れる単一の送信をxxx_i周辺の各プロセスは受け取ることができる。

2つのメッセージタイプ、すなわちproposalsとvotesのみを用いる。それぞれラウンド数、ブロック（ハッシュ）、署名を含んでおり、順にmsg.round、msg.block、msg.sigと表す。署名はブロードキャストチャネル自体の中に吸収させてしまうこともできるが、ビザンチンなふるまいがある場合には証拠として利用するために必要である点に注意されたい。

形式仕様は図3.2（Part I）、図3.3（Part II）の2パートで与えられる。

（EthanのTendermint論文3　←←　前）｜（次　→→　EthanのTendermint論文5）

免責

邦訳には誤りがある場合がございます。予めご承知おき下さい。

確実な情報を知るためには冒頭に示した原文をご参照くださいますようお願いいたします。