[https://dl.acm.org/doi/abs/10.1145/3517209.3524042](https://dl.acm.org/doi/abs/10.1145/3517209.3524042) - [[CRDT]]を[[Byzantine Fault Tolerant]]にする - ビザンチンノードが正しいノードより多いシステムでも、CRDTの一貫性を保つことができる - 既存のCRDTに少しばかりの変更を加えるだけでOK - Operation-basedなCRDT - State-BasedでBFTなやつ: [[Merkle Search Tree]] - [[PaPoC]] '2022 - [[Martin Kleppmann]] 背景 - 既存のCRDTはP2Pシステムを想定しているにも関わらず、ビザンチン障害耐性がない - 最終的な操作(or state)の配信が期待できるか? 間にビザンチンノードがいると、達成できない - 同じバージョンベクタを持つ異なる操作(or state)を複数送信してくるビザンチンノードがいた場合、困る - 不正な更新を送り付けてくるビザンチンノードがいるかもしれない - プロトコルに明らかに沿っていない場合弾けるケースもあるけど、先行する操作に依存する操作など、受け入れてしまい収束しなくなってしまう場合もある システムモデル キーとしては、メッセージの配信が保証できて、かつ不正な更新操作を送れなければいいよね、ということ(kekeho) - 全ノードが対等なP2P - 各ノードは、ノードの全体集合を知らない、頻繁に参加したり離脱したりする - ビザンチンな挙動をするノードがいる - クラッシュもビザンチンな挙動もしないやつを正しいノードとする - メッセージは有限回の再試行のあとに受信される - 暗号学的にメッセージを認証することで、2つの正しいノードが直接通信する場合メッセージは破損していないものとみなせる - いい感じに正しいノードpと正しいノードqが直接通信できると仮定 - 間が全員Byzantineなノードだとダメなので - [[Byzantine Reliable Broadcast]] - Byzantineノードの数が1/3以下の状況しか許容できない - 投票をするらしい 仕組み hash graphの構築 - $u$: 更新 - $H$: [[暗号学的ハッシュ関数]]。耐衝突性を持つ - $H(u)$: 更新のID - すべての更新$u$は、因果的に先行するハッシュのセットを含む - 同じノードが生成した最後の更新のハッシュ・最後の更新以降に他のノードから受け取った更新のハッシュが含まれる。直前のだけ含めればいい。 - 同じノードが生成した最後の更新のハッシュ - 最後の更新以降に他のノードから受信した更新のハッシュ - 他の依存関係を介して辿れる依存関係は先行ハッシュのセットに含めないことで、小さなセットを保てる - [[DAG]]が形成される - head: 先頭の更新。他の更新の依存先になっていないやつ。leafのこと(kekeho) - 各ノードは、DAG全体のコピーをローカルに保持する Eventual Deliveryの担保 - 各ノードは、現在のヘッドを教え合い、同一だったら持っているDAGが一緒とみなせる - 一致しない場合、グラフ探索を行い、どの部分まで共通しているのかを調べ、欠けている部分を送り合う - うまいやり方: [[Byzantine Eventual Consistency and the Fundamental Limits of Peer-to-Peer Databases]] - これで、過去もらえなかった更新があったとしても取ってこれる - ビザンチンノードは、ハッシュグラフに任意のEdgeとVerticleを追加できる - ハッシュの衝突は(ハッシュ関数の衝突耐性により)作れないので、正しいノードたちが更新のセットを送り合うのを妨げることはできない - たくさんのHeadとかを作るかもしれないけど、これらの更新は別にアルゴリズムの正しさに影響与えないよね ← だってHeadだもんね。過去を書き換えるわけでもないし(kekeho) - というわけで、最終的にはすべての正しいノードたちが、他の正しいノードを介して直接・間接的に、最終的に他のすべての正しいノードと通信できるという仮定さえ置けば、配信を保証できる Unique ID - ID、多くの既存CRDTでは各ノードに信頼をおいて作っている - ビザンチンノードが同じ更新IDを持つ異なる更新を作れちゃったりして、まずいよね - 更新のID: $H(u)$ 更新の有効性検証 - 与えられた更新が有効かどうか、全ての正しいノードが合意すること(=> 収束)が必要 BFTの証明 - [[Byzantine Eventual Consistency and the Fundamental Limits of Peer-to-Peer Databases]] - これもうやってること[[IOTA]] [[Tangle]]じゃね? (kekeho) - 収束するのはうれC(kekeho) 参考 まだ観てないけど謎の勉強会の動画があった: