rippleで使われるコンセンサスアルゴリズム
仮想通貨であるrippleで用いられるコンセンサスアルゴリズムについて、white paperを読んでみたのでわかったことをメモ。
まとめ
メモ
過去の研究でわかったこと
- 一つのfault nodeが存在するだけであっても、一つのconsensusに収束しない可能性は常にある
- 時間ベースのリミット（または収束しない状態での繰り返し回数最大値）が必要
- ビザンチン将軍問題＝ネットワーク内の33%以上がfaultだった場合には正しいコンセンサスは得られない（同期の場合）
- 非同期の場合でも2008年の論文により33%の耐性が作れること示された（ネットワークに追加の制約あるけど）
ripple algorithmではヒューリスティックな方法でコンセンサスを一意に保つようにした
- 各ノードが応答する時間として最低2秒が与えられる
- これによって多少ネットワークが遅延したノードでもコンセンサスプロセスに参加できる
- どのノードがどんな投票をしたかは台帳に記録されるため、悪い挙動をしたノードを検出できる
- 信頼できるノードを記録したUNLが各ノードに与えられる
- UNLのうちアクティブなノードの数を監視し、一定の数を下回った場合はトランザクションの処理を一時的に止める
- その状態で処理を進めると一つのコンセンサスに収束しないことがあるため
一意なコンセンサスに収束するための条件
個々のノードは信頼できる他のノードのリストを持っている（UNL）
response timeをモニタすることで、基準より反応の遅いノードをUNLから削除した上でコンセンサスを取る。
20%以下のfaultノードかつequation3を満たす場合に有限時間でコンセンサスは収束
|UNLi ∩ UNLj| ≥ 1/5 * max(|UNLi |,|UNLj |)∀i, j - (3)
すべてのi,jの組み合わせにおいて、node i, node jのUNLの重なる部分の数がどちらかのUNLの1/5以上であること
attackerによる攻撃の意味を少なくさせるための施策について
以下のコストを発生させることでattackerからの攻撃を防ぐ
- rippleのaccount作成には20xrpが必要
- transaction feeとして0.00001xrpかかる
どちらも正常に使う分には無視できるレベルのコスト。しかし、DoS攻撃などしようとした場合にはコストがかさむことになる。
