CRDT Logical_Clock 論理時計 Monotonicity

  • https://dl.acm.org/doi/10.1145/3642976.3653034
  • PaPoC 2024
  • ビザンチン環境下での論理時計の条件を定義
    • 最近のHashgraph作って論理時計作ろう系 (Merkle-CRDTsとか) の総括
    • 因果的過去が改ざんできない
    • しかし依然として並行を差し込み続けることは可能…なので、全順序なクロックを作ろうと思うと無理がある。あくまで半順序のLogical Clock用(kekeho)

以下読みながらのメモ

  • この論文での用語の定義
    • monotonicity
      • について、以下の条件を満たすときmonotoneである
      • Posets
      • 複数の入力があるものも同様
      • 順序関係の保存を保証(kekeho)
    • inflation
      • Endomorphism は以下の条件を満たすときinflationである
      • 入力値を(型は一緒で)そのままか大きくする関数?(kekeho)
    • : イベント
    • : レプリカ
    • : タイムスタンプ
    • : クロック関数
    • : genesis event
    • : 因果的過去。不変
    • : 因果的未来。不変。
  • 従来のLogical Clock(Lamport Clock, Vector Clock等)はmonotone functionだけど、レプリカがイベントに全順序を割り当てるという仮定があるので、Byzantine Fault Tolerantとはいえない
    • 協調無しで検証ができない
  • ビザンチンレプリカの攻撃ベクトル
    • Malformation
      • confluent invariantに違反するメッセージを送る
      • 構文的に不正なメッセージや、無効な署名を持つメッセージを送るなど
      • フィルタリングできるのでヨシ
    • Omission
      • メッセージを一部のレプリカに送らない
      • Gossip Protocol等を使って状態の収束を図れば問題にならない
    • Equivocation ← これが厄介
      • 2つの異なる有効な入力を作成し、別々のレプリカに送る
      • 同じタイムスタンプを異なるイベントにつけて、別々のレプリカに送るなど
      • 仮想通貨のdouble spend的な? (kekeho)
  • Replicated Chronicle Problem
    • イベントの順序付けはイベントが発生したレプリカによって定義づけられる
    • イベントのcausal pastは、常にoriginレプリカのknowledgeの下界である
      • つまり、イベントを発生させたレプリカ(origin replica)は、そのcausal pastに含まれるすべてのイベントを知っているということ(kekeho)
    • Chronicle:
      • イベントだけでなく、その先行イベントとその間の因果関係も普遍的に含まれる
      • すべてのイベントが、同じGenesisイベントに繋がる
      • 半順序関係がある
        • Chronicle CがC’の部分集合であるための必要十分条件は、Cに含まれるすべてのイベントがC’にも含まれており、かつそれぞれのイベントのcausal pastが両方のchronicleで同じであること
    • 効率的でByzantine Fault Tolerantな複製を可能にする論理時計関数を見つける
    • Safety
      • Chronicality: The local state is always a chronicle, i.e., a causal event set that is downward-closed and directed at the minimal event of global state
        • (すべてのレプリカ, そのレプリカのChronicleである内の全てのイベント、およびグローバルchronicle 内の全てのイベントにおいて、の関係は以下のいずれかである)
          • (の関係は、前後関係 or 並行)
          • (もしより前であれば、に含まれる)
          • (これはGenesisイベントの定義)
      • Monotonicity: Next local chronicle は、をinflationさせたものである
    • Liveness: