notes.kekeho.net

最近の記事

DAGベースの仮想通貨

8 min read

SoK論文を参考に、DAGベースの仮想通貨についてまとめる

サーベイ(SoK)論文

システムモデル

  • 有向非巡回グラフ

    • 点集合
      • はunit。unitは、トランザクション, ブロック, イベントとしてインスタンス化される
      • ここいらは個別のDAGで異なるということ? まとめてunitとよんでいるということっぽい(kekeho)
    • 辺集合
      • 2点の部分順序関係を表すペア

  • unit表現の種類

    • : ピアからのリクエストを待たずに、受診される度に即座に処理されるリクエスト
      • トランザクション、トリガーイベントなど
    • : さらなる処理が必要なリクエスト。事前計算、マイナー、バリデータなどによってパッケージ化される
      • ブロックなど

  • グラフトポロジーの種類

    • Divergence(): Unitがあらかじめ決められた順序を持たずに、予測不能な方向に発散していく
    • Parallel(): Unitが複数のチェーンの形で維持される
    • Convergence(): Unitが決定的な順序で組織化されている・収束する
      • これ気になる(kekeho) システムモデルによる分類 ,,, ,,, ,,, かつConvergenceなやつが気になる(kekeho)

  • 台帳モデルによる分類

    • UTXO-based: すべての操作がAtomicなトランザクションによって完了する。UTXOをたどっていけば残高の計算ができる。
    • Account-based: ユーザーはアカウント(ステート)を保持して、トランザクションはそのフィールドの変更に用いられる

  • 構造による分類

    • In/Out degree: DAGのUnitの結合の仕方。InはUnitの後ろに繋がるUnitの数。OutはUnitの祖先の数。
      • 例: IOTA: In: x, Out: 2

  • コンセンサスの仕組みによる分類

    • Openess: 任意のノードが、Permissionがなくともコンセンサスアルゴリズムを実行できるかどうか。Permission lessかPermissionedかどうか。
    • Unit allocation: UnitをDAGのどこに位置づけるか?
      • Divergence: Blockchainにおけるheightのような概念に乏しい
      • Parallel: 2次元座標で表せる
      • Convergence: ポジションが決まる
    • Extension rule: DAGの枝をどう拡張していくか? 同点をどう解消するか? (フォークの解消とかを指している)

DAGでよく使われるテクニック

  • Unitの相互参照によりチェーンをねじれさせて、スループットの向上、高いスケーラビリティ、低いConfirmation時間を狙う
    • Orphan Unitを巻き取りやすい
    • 相互参照とはどういう意味? 相互参照というより、複数の親Unitを指す子が複数いていい感じに束ねてくれている、ということかな? それによってなぜスループット向上、スケーラビリティ向上、Confirmation時間の低減につながる? (kekeho)
  • Trusted Authorityを置く
  • Pairwise Vote
    • 通常のn-for-1ではなく2-for-1の投票選択
    • Pairwise comparisonのことかな? 勝者が決まらないこともあると思うけど…(kekeho)
    • Spectrumのコンセンサスで採用
  • Sharding
    • スループットを上げるために複数チェーンに分ける
    • トランザクションのハッシュ値の末尾とかでチェーン割り当てを決めたりする DAGで用いられるアルゴリズム
  • Tip selection algorithm
    • 祖先となるユニットがどのように後続のトランザクションを選択するか、トランザクションがどのように祖先にアタッチされるか
  • Recursive algorithm
  • Consensus algorithm
  • Sorting algorithm
    • 線形順序を決定する

コンセンサスアルゴリズムのProperty analysis

  • Consistency, Ordering, Finalityの3つのプロパティを分析
    • Consistency
      • Strict Consistency: 正直なノードはそれぞれ、台帳上の与えられたPositionに対して同じ決定を下す。Unitはシステム内で正確に位置づけられる
        • Trusted Authorityがいるモデル、メインチェーンがあるものだと達成しやすい
      • Partial Consisntency: 関連するノードのみが同じ決定を持ち、関係のないノードの決定はお互いに未知である。関連するトランザクションの数は2〜複数
    • Ordering
    • Finality
      • Probablistic Finality: システムに追加されたunitは、常に覆される可能性がある
        • 確率: 累積信頼度(信頼度=深さ、スコア、重さ…)に反比例する
        • Nakamoto Consensusとかはこれ
      • Deterministic Finality
        • Unitは一度システムに取り込まれると、恒久的にconfirmされる
        • PBFTとかはこれ
      • DAGベースだと、Trusted Rolesに依存する事が多い
        • TRの選出に色々レパートリーがある

セキュリティ: 攻撃の種類

  • Parasite chain attack: 正直な部分グラフを別の部分グラフに置き換える攻撃
  • Balance attack(liveness attack):
  • Large weight attack: 競合するheavyなトランザクションが、最近confirmされたトランザクションを無効にする(heavy: スコア・信頼度・重みが重い)
    • 敵対者が十分なパワーを持っている、Probablistic Finalityの場合に起こる
  • Censorship attack: PermissionedなDAGにおいて、委員会メンバーが談合をする
  • Sybil attack: ノード間でチャネルを切断したり、ネットワーク全体を支配するために複数のIdentityを生成する
  • DAGのプライバシー保護も重要な研究課題? あまりない?(kekeho)
    • BitcoinにおけるMoneroやZCashみたいなのはあるんだろうか(kekeho)

パフォーマンス

  • DAGにおけるパフォーマンス評価指標:
    • Throughput(): ネットワーク上で確認されたunitの最大レート
    • Latency(): unit propagation time, confirmation timeの2つから構成される
    • Scalability (): 多数のノードを追加したときに、どれくらいthroughputを達成できるか

メモ

  • 5.1
  • iota qubicを調べる

グラフビュー

バックリンク