Merkle-CRDTs

https://arxiv.org/abs/2004.00107

• Merkle TreeにCRDTオブジェクトを埋め込む
  • Merkle Tree: データの解決／発見と自己検証を行うことができる
  • CRDT: Consensus algorithmを必要とせずにグローバルな状態収束を可能にする(Strong Eventual Consistency)
  • Merkle Tree x CRDT: 両者の特性を活かして、DAGを論理的な時計(タイムスタンプ? (kekeho))とすることができる

Contributions

• Merkle Clock
  • Merkle DAGベースの論理時計
  • CRDTで活用されるバージョンベクタ・Logical Clockのかわりに、Merkle Treeが使えることを示すンゴ
• Merkle-CRDTs
  • CRDTのペイロードのための汎用トランスポート・永続化レイヤ

詳細 Merkle Clock

• DAGは(ブロックチェーンでの使用例のように)因果関係を表すのにも使える
  • Tx AがTx Bに先行する(happend-before)を表現できる
• Merkle Clock $M$は、各ノードがEventを表すMerkle DAGである
• $M_{\alpha }$と$M_{\beta }$は以下の手順でマージできる ($\alpha ,\beta$はCID, TreeのRoot)
  • $\alpha =\beta$の場合: 同じDAGなので何もしなくていい
  • $\alpha \in M_{\beta }$の場合: $M_{\alpha }$の履歴はすでにその一部なので、$M_{\beta }$を残す (その逆もしかり)
    • これでhappend-beforeがわかるね
  • それ以外: 全然別の不連続なDAGなので、$\alpha ,\beta$という2つのノードを子に持つ$\gamma$を作る(マージ)
    • これで並行がわかるね
• ↑より、Merkle Clockは因果関係情報を含んでいるといえる。Merkle DAGがたしかにLogical Clockとして使える
  • Strict Partial Orderなので、全部のイベントについて前後がわかるわけではない、並行も存在することに注意。
• Merkle Clock DAGはG-Set CRDTとみなせるので、収束するンゴ
  • (ちゃんとした証明は元論文にある)

Merkle CRDTs

• ノードが任意のCRDTペイロードを持つMerkle-Clock
  • CRDTペイロード: CRDTのOperationとかStateを指す
  • Partial Orderなので、ディスオーダーが起きない👍
• Operation BasedなCRDTに向いてる。Stateもできるけど、ノードにStateを埋め込むことになるので、大きくなっちゃってどうだろねー
• 論文にはアンチエントロピーアルゴリズムの紹介もある

DAG-Syncer Component

• レプリカがCIDを与えられた他のレプリカからリモートでMerkle DAGのノードを取得するコンポーネント

• 以下のメソッドを持つ

  • Get(CID): Node
  • Put(Node) Broadcaster Component

• 以下のメソッドを持つ

  • Broadcast(Data)

• DAG-SyncerとBroadcasterとして、IPFSが使える

  • IPFSはDAG-Syncerとして動作し、libp2p層が提供するPubSub機構の一つがBroadcastを担当する

限界と最適化

• DAGがどんどん大きくなってしまう

アプリケーション

• Markle-CRDTsで分散KVSとか作れちゃう
  • PeerPad
  • OrbitDB
    • 多分Read/Write等の順序付けにCRDTを使ってる?(要調査)(kekeho)