Tendermintにおける二段階投票
Tendermintではなぜ2回投票するのか？
ポイント
Tendermintでは1/3（ハイパーパラメータ）までのビザンチンな振る舞いにのみ耐性がある。
２つ以上のブロックに投票するという、（１つブロックにのみ投票するというプロトコルにおいて）ビザンチンな振る舞いをするノードが1/3以下の場合は、二つ以上のブロックが2/3より多い投票を得ることはない。
二重投票・二つのブロックの提案などのビザンチンな振る舞いはpunishmentの仕組みでインセンティブをなくしている
投票が2回必要になる根本の問題は「ネットワークの状態によって他ノードが署名したという情報がちゃんと伝播しないこともあるよね」というもの
用語
コミット: 各ノードがあるブロックが承認されたと認識してブロックチェーンにつなぐこと
「2/3以上」を「+2/3」と書く。
バリデーターで投票して回ることを投票の1「ステップ」とする
一定の割合（Tendermintの場合）+2/3の投票が一定時間で集まらなかった場合はバリデーターの支持が得られなかったとしてその投票ステップを「棄却」する
ブロック提案から、投票を何ステップかやってブロックのコミットor再提案までを1「ラウンド」とする
ナイーブな1ステップ投票
要約
投票行為の情報が上手く伝播しなかった場合にフォークが起きる（ビザンチンな振る舞いがなくても）
実際には+2/3の投票が集まっていたとしても、その事実を確認できてコミットするバリデータと、その事実がうまく伝わらずに棄却するバリデータがでてしまう
棄却してしまったバリデーターたちで新しいブロックが提案され+2/3の投票を集めてそれがコミットされると、フォークが起きたことになる
問題点
問題は、自分が投票したブロックが棄却された場合に以下の２つの区別がつかないこと
実際には+2/3の投票を得たが自分がその情報を確認できていないだけパターン: 以下では「伝播ミス」と呼ぶ
制限時間切れの後に投票の事実を知っても、それが制限時間以内の投票かは判別できないので棄却は覆さない
+2/3の投票を得られなかったパターン: 以下では「落選」と呼ぶ
具体例: バリデーターが４ノードで、A, B, C, Dと呼ぶ時
あるブロックが提案された
Aが反対して署名せず、B, Cが署名して、その段階ではB, Cもまだ2/3以下の投票しか得られてないと認識し、Dが署名してようやく+2/3に達した時、Dが署名したという事実が投票の制限時間以内にB, Cに伝わらない可能性がある。
Dはコミットするが、BとCはこのブロックは落選したと認識し棄却、次のラウンドに進む
次のラウンドではブロック提案者が変わり、当然ながら別のブロックを提案する可能性があり、A, B, Cが投票したとする。そして今回は問題なくお互いの投票の情報が伝わったとすると、A, B, Cはそのブロックをコミットする。
DとA, B, Cの間でフォークが起きている
1ステップ投票にロックの仕組みの導入
要約
ロックのルール
本来、+2/3の投票を得ている時点で「正当な」ブロックなので、伝播ミスで棄却してしまったバリデーターが出た場合に、
彼らが次ラウンドでそれをコミットできるようにしたい
他のブロックが+2/3の投票を集めることを防ぎたい
そこで、下記のように、投票したバリデーターはブロックに「ロック」されるルールにする
① 次ラウンドでブロック提案者の場合は必ず前ラウンドで自分が投票したブロックを提案する
② 次ラウンドは自分が前回ラウンドで投票したブロックのみに投票可能
前ラウンドの+2/3の票が次ラウンドで他ブロックに流れなければ、新しいブロックが+2/3の投票を集めることはありえないし、元のブロックが必ず+2/3の票を確保できる
問題点
このルールだと、伝播ミスの場合は良いが、落選のブロックにバリデーターがロックされたままになってしまう
落選のブロックは②だけでは+2/3の投票が確保されないので、当然また落選する可能性がある
一方、新しいブロックが提案されてまた落選した時に、その新しいブロックにロックされるバリデーターも出る
新しいブロックが提案され落選するのが何度も繰り返された場合に、毎回バリデーターが様々なブロックにロックされて、ロックされていないバリデーターの数が2/3以下になってしまう（永遠にチェーンが伸びなくなる）
2ステップ投票
ここまでの背景
新しいブロックが提案された時、ロックされているバリデーターが、前ラウンドは落選だったのだと認識できないと、他ブロックに投票が流れることを防ぐための②を解除できない
そこで、もう1ステップ投票を挟む
そのブロックが落選していたという事実を示し、落選のブロックにロックされたバリデーターを解除したい
ルール
投票を2ステップにし、ロックの仕組みを以下のように改良する
① 前回ラウンドのステップ2で投票し、かつ前ラウンドでブロックを棄却したバリデーターは、自分がブロック提案者の場合は必ず自分がロックされているブロックを提案する
② 前回ラウンドのステップ2で投票したバリデーターは、次ラウンドのステップ1は自分が前回ラウンドで投票したブロックのみに投票可能
アンロック
ステップ1の投票で新しいブロックが+2/3の署名を集めた場合、ステップ2の投票に参加できる
ステップ1の投票で、②のルールの下、前ラウンドと異なるブロックが+2/3の署名を集めた場合は、前ラウンドでそのブロックが棄却されていたということが確認できる
前ラウンドで+2/3の投票が集まっていた場合、latencyがよほど大きくない限り+2/3の投票を確認できずにロックされるバリデーターは、次のラウンドで+2/3の投票が集まるのを妨げるほどいない
まとめ
バリデーターをロックするブロックを常に1種類にとどめ、ロックされたバリデーターの数を1/3以下にできる
ステップ1での制限時間切れはフォークを引き起こさないので、ロックする必要がない
つまるところ「ロック」とは複数のブロックに投票しないために仕組み
（①②のルールに関して1/3以下のビザンチンな振る舞いがあり得るが割愛）
結論
「ロック」は複数のブロックに投票しないようにする仕組み
1段階目の投票は、ブロックが棄却された場合に、それが伝播ミスなのか普通に棄却されたのかを区別するためのもの
参考