本稿について
本稿は、Tendermintホワイトペーパーの詳細版ともいえるTendermint現CTOであるEthan Buchman氏の執筆論文をもとにTendermintについて見ていくシリーズです。冒頭に筆者による「簡単まとめ」を入れ、その後にもととなった部分の日本語訳を載せるという順番で書いていきます。
論文「Tendermint： Byzantine Fault Tolerance in Age of Blockchain」の原文はこちら。
今回の対象範囲は第3章「Tendemint Consensus」のうち3.4「Safety」で、これを読むとTendermintの「セーフティ」についてやや詳しい内容が分かります。
原文はこちらになります。
スポンサードサーチ
要点をまとめてみる
- Tendermintは有効性（validity）、合意（agreement）、完全性（integrity）、完全な順序（total order）の全てを満たすので、アトミックブロードキャストを満たす。
- 有効性（validity）：正しいプロセスがmをブロードキャストするならば、最終的に正しいプロセスはmを伝送する。
- ブロックではなくトランザクションのまとまりかトランザクションにmを入れれば有効性は満たせる。
- 合意（agreement）：正しいプロセスがmを伝送するならば、全ての正しいプロセスはmを伝送する。
- 完全性（integrity）：mは一度限り伝送され、それは、mの送信者によりブロードキャストされる場合に限られる。
- 完全性を満たす実装は複数考えられるので、Tendermintでは定めずアプリケーション開発者が仕様を決められるようにする。
- 完全な順序（total order）：正しいプロセスpとqがmとm'を伝送するならば、qがm'の前にmを伝送することはpがm'の前にmを伝送することの必要十分条件である。
- 有効性（validity）：正しいプロセスがmをブロードキャストするならば、最終的に正しいプロセスはmを伝送する。
以下、今回取り扱った箇所の日本語訳なので詳細を知りたければどうぞ。
Chapter3. Tendermintコンセンサス（続き）
3.4 セーフティ
Tendermintがアトミックブロードキャストを満たすことについて、簡単な証明を描いてみよう。これは、以下を満たすこととして定義される。
- 有効性（validity）：正しいプロセスがmをブロードキャストするならば、最終的に正しいプロセスはmを伝送する。
- 合意（agreement）：正しいプロセスがmを伝送するならば、全ての正しいプロセスはmを伝送する。
- 完全性（integrity）：mは一度限り伝送され、それは、mの送信者によりブロードキャストされる場合に限られる。
- 完全な順序（total order）：正しいプロセスpとqがmとm'を伝送するならば、qがm'の前にmを伝送することはpがm'の前にmを伝送することの必要十分条件である。
もしブロックにmを入れる場合、Tendermintは有効性を満たすわけではない点に注意されたい。なぜならば、提案されたブロックが最終的にコミットされる保証はないからである。というのも、バリデータは新しいラウンドに進んで異なるブロックをコミットする可能性があるためである。もしmをブロック内のトランザクションのまとまりに入れる場合、バリデータにそのまとまりがコミットされるまで再提案してもらうことで有効性を満たす。しかし、完全性の前半部分を満たすためにはさらなるルールを付け加えねばならない。そのルールとは、正しいバリデータがブロックを提案することや、既にコミットされたトランザクションのまとまりを含むブロックに対して事前コミットすることを禁ずるというものである。幸いにもマークルルートでまとまりをインデックス付けすることができ、提案や事前コミットの前に検索が実行される。
その代わりにもしトランザクションにmを入れる場合、mempool上の永続性（persistence）という特性、すなわちmempool内のトランザクションはコミットされるまでそこに存在するという特性を行使することで有効性を満たすことができる。しかし、完全性の前半部分を満たすためには、所与のトランザクションは一度限り有効であるなどのトランザクションに対するいくつかのルールセットをアプリケーションに頼って強制せねばならない。これは例えば、Ethereumがやっているようにアカウントにシーケンス番号を割り振ったり、Bitcoinがやっているように一度限り使用可能な未使用リソースのリストを保持しておくなどの方法によりなしうる。複数のアプローチがあるので、Tendermintそれ自体はメッセージが一度のみ伝送されることを確実にはしないが、アプリケーション開発者が仕様を規定できるようにする。正しい提案者が提案したブロックに含まれるトランザクションだけがコミットされうることから、完全性の後半部分が満たされることは自明である点に注意されたい。
Tendermintが残りの特性（筆者注：agreementとtotal order）を満たすことを示すため、ステートマシンセーフティ（state machine safety）という新しい特性を導入し、ステートマシンセーフティを満たすプロトコルは合意と完全な順序を満たすことを示す。ステートマシンセーフティは、正しいバリデータがどこかのブロック高Hでブロックをコミットするならば、他のいかなる正しいバリデータもブロック高Hで別のブロックをコミットすることはできないというものである。あらゆるメッセージは最終的に受け取られることを考慮すれば、速やかに合意は導かれる。というのも、正しいバリデータがブロック高HでブロックBをコミットするならば、他全ての正しいバリデータは他のどんなブロックもコミットすることができないので、最終的にブロックBがコミットされてmが伝送されるからである。
さて、まだステートマシンセーフティが完全な順序を満たすこと、Tendermintがステートマシンセーフティを満たすことの証明が残っている。前者について確認するため、バリデータpとqにより伝送されるメッセージmとm'を考える。ステートマシンセーフティは、qがブロック高Hmでmを伝送することを必要十分条件としてpがブロック高Hmでmを伝送すること、qがブロック高Hm'でm'を伝送することを必要十分条件としてpがブロック高Hm'でm'を伝送することを確約する。ここで、ブロック高は厳密に増加するので、Hm < Hm'としても一般性を失わない。qがm'の前にmを伝送することを必要十分条件としてpがm'の前にmを伝送すると言える。これはまさしく完全な順序を表す。
最後に、バリデータの1/3未満がビザンチンである場合にTendermintがステートマシンセーフティを満たすことを背理法により証明する。Tendermintがステートマシンセーフティを満たさないと仮定すると、同一ブロック高で1つ以上のブロックをコミットすることができる。次に、そのようなことが起こるためには少なくとも1/3のバリデータがビザンチンでなくてはならないことを示し、仮定に矛盾することを示す。
ブロック高HのラウンドRである正しいバリデータがブロックBをコミットしたとする。ブロックのコミットは、そのバリデータがラウンドRのブロックBに対して2/3より多くのバリデータからの事前コミットを目撃したことを意味する。ブロック高Hで別のブロックCがコミットされたと仮定する。ここで、考えうるケースは2通りである。つまり、ブロックCがラウンドRでコミットされたか、ブロックCがラウンドS > Rでコミットされたかのいずれかである。
ブロックCがラウンドRでコミットされたとすると、2/3より多くのバリデータがラウンドRでブロックCに事前コミットしていなくてはならない。これは少なくとも1/3のバリデータがラウンドRのブロックBとブロックCの両方に事前コミットしていることを意味しており、これらは明らかにビザンチンである。ブロックCがラウンドS > Rでコミットされたとする。2/3より多くがブロックBに事前コミットしたので、それらのバリデータはラウンドSでブロックBにロックされている。従って、ラウンドSでブロックBに事前投票する。ブロックCに事前コミットするためには、ブロックBにロックされているバリデータはブロックCに対するポルカを目撃せねばならず、それには2/3より多くのバリデータがブロックCに対して事前投票する必要がある。しかし、2/3より多くのバリデータはブロックBにロックされていて事前投票せねばならないので、ブロックCに対するポルカには少なくとも1/3のバリデータがPrevote-the-Lockに違反する必要があり、これらは明らかにビザンチンである。従って、ステートマシンセーフティを侵害するには、少なくとも1/3のバリデータがビザンチンでなければならない。（筆者注：いずれの場合も、バリデータの1/3未満がビザンチンであるという仮定に矛盾する。）ゆえに、ビザンチンなバリデータが1/3未満であれば、Tendermintはステートマシンセーフティを満たす。
以上より、Tendermintはアトミックブロードキャストを満たす。
将来の研究で、Tendermintのセーフティ特性に関する形式的な証明を与えることを計画している。
（EthanのTendermint論文5 ←← 前）｜（次 →→ EthanのTendermint論文7）
免責
邦訳には誤りがある場合がございます。予めご承知おき下さい。
確実な情報を知るためには冒頭に示した原文をご参照くださいますようお願いいたします。