DAGベースの仮想通貨
SoK論文を参考に、DAGベースの仮想通貨についてまとめる サーベイ(SoK)論文
システムモデル
有向非巡回グラフ$ \mathcal{G} = (\mathcal{E}, \mathcal{V}) 点集合$ \mathcal{V} = \{ u | u \in \{\mathcal{T} \cup \mathcal{B} \cup \mathcal{E} \}\}
$ uはunit。unitは、トランザクション$ \mathsf{Tx} \in \mathcal{T}, ブロック$ \mathsf{B} \in \mathcal{B}, イベント$ \mathsf{E} \in \mathcal{E}としてインスタンス化される
ここいらは個別のDAGで異なるということ? まとめてunitとよんでいるということっぽいkekeho.icon
辺集合$ \mathcal{E} = \{ (u, v) | u \leftarrow v \land \{u, v\} \subseteq \mathcal{V} \}
2点$ u, vの部分順序関係を表すペア
unit表現の種類
$ 1^{od}: ピアからのリクエストを待たずに、受診される度に即座に処理されるリクエスト
トランザクション、トリガーイベントなど
$ 2^{od}: さらなる処理が必要なリクエスト。事前計算、マイナー、バリデータなどによってパッケージ化される
ブロックなど
グラフトポロジーの種類
Divergence($ \hat D): Unitがあらかじめ決められた順序を持たずに、予測不能な方向に発散していく
Parallel($ \hat P): Unitが複数のチェーンの形で維持される
Convergence($ \hat C): Unitが決定的な順序で組織化されている・収束する
これ気になるkekeho.icon
table:システムモデルによる分類
Divergence Parallel Convergence
1od IOTA, Graphchain, Avalanche Nano, Caper, Vite, Chainweb, Hashgraph, DLattice, Aleph, Jointgraph, Lachesis Byteball, Haootia, JHdag 2od Spectre, Phantom, Meshcash Prism, Blockmania, Blockclique, OHIE, Sphinx, Eunomia, DEXON, PARSEC GHOST, Inclusive, CDAG, Conflux, StreamNet $ 1^{od}かつConvergenceなやつが気になるkekeho.icon
台帳モデルによる分類
UTXO-based: すべての操作がAtomicなトランザクションによって完了する。UTXOをたどっていけば残高の計算ができる。 構造による分類
In/Out degree: DAGのUnitの結合の仕方。InはUnitの後ろに繋がるUnitの数。OutはUnitの祖先の数。
コンセンサスの仕組みによる分類
Openess: 任意のノードが、Permissionがなくともコンセンサスアルゴリズムを実行できるかどうか。Permission lessかPermissionedかどうか。
Unit allocation: UnitをDAGのどこに位置づけるか?
Parallel: 2次元座標で表せる
Convergence: ポジションが決まる
Extension rule: DAGの枝をどう拡張していくか? 同点をどう解消するか? (フォークの解消とかを指している)
DAGでよく使われるテクニック
Unitの相互参照によりチェーンをねじれさせて、スループットの向上、高いスケーラビリティ、低いConfirmation時間を狙う
Orphan Unitを巻き取りやすい
相互参照とはどういう意味? 相互参照というより、複数の親Unitを指す子が複数いていい感じに束ねてくれている、ということかな? それによってなぜスループット向上、スケーラビリティ向上、Confirmation時間の低減につながる? kekeho.icon
Trusted Authorityを置く
通常のn-for-1ではなく2-for-1の投票選択
スループットを上げるために複数チェーンに分ける
トランザクションのハッシュ値の末尾とかでチェーン割り当てを決めたりする
DAGで用いられるアルゴリズム
祖先となるユニットがどのように後続のトランザクションを選択するか、トランザクションがどのように祖先にアタッチされるか
各ラウンドのOutputが徐々に安定した値に近づいていくアルゴリズム群
BFT-style
線形順序の実現は困難
BFT-styleとAsynchronous BAの統合
Sorting algorithm
線形順序を決定する
コンセンサスアルゴリズムのProperty analysis
Trusted Authorityがいるモデル、メインチェーンがあるものだと達成しやすい
Blockchainもこれ
確率: 累積信頼度(信頼度=深さ、スコア、重さ…)に反比例する
Unitは一度システムに取り込まれると、恒久的にconfirmされる
TRの選出に色々レパートリーがある
セキュリティ: 攻撃の種類
敵対者が十分なパワーを持っている、Probablistic Finalityの場合に起こる
Sybil attack: ノード間でチャネルを切断したり、ネットワーク全体を支配するために複数のIdentityを生成する DAGのプライバシー保護も重要な研究課題? あまりない?kekeho.icon
パフォーマンス
Throughput($ \lambda): ネットワーク上で確認されたunitの最大レート
Latency($ \tau): unit propagation time, confirmation timeの2つから構成される
Scalability ($ \phi ): 多数のノードを追加したときに、どれくらいthroughputを達成できるか
メモ
5.1
iota qubicを調べる