技術的概要：単調性消去符号

1. 問題定義

従来の消去符号（リード・ソロモン符号などの MDS 符号など）は、閾値故障仮定の下で動作します。これらのシステムでは、データを $k$ 個の断片に分割し、$n$ 個のフラグメントに符号化します。これにより、任意の $k$ 個のフラグメントがあれば復元が可能となります。このモデルは、ノードの特定のアイデンティティに関わらず、任意の $k$ 個のノードのサブセットが利用可能か故障するかは同様に確からしいと仮定しています。

しかし、ブロックチェーンや暗号通貨（Stellar、XRP レジャーなど）における現代の分散システムは、一般化された故障仮定またはビザンチンクォーラムシステムを利用しています。これらの文脈では、信頼は均一ではなく、一部のノードは他のノードよりも信頼性が高く、故障パターンは純粋にランダムではなく、特定のノードのサブセットに依存します。既存の閾値ベースの符号は、大幅なオーバーヘッドや構造的不整合なしに、これらの任意の信頼仮定を効率的に受け入れることができません。本論文は、特定のノードのサブセット（アクセス集合）がデータの復元を保証し、他のサブセットは保証しないという任意の単調アクセス構造を尊重する消去符号の必要性に対処します。

2. 手法

本論文は、任意のアクセス構造 $\mathcal{A} \subseteq 2^{\mathcal{P}}$（ここで $\mathcal{P}$ はノードの集合）で動作するように設計された、古典的な消去符号の一般化である単調性消去符号を導入します。

2.1 定義と形式化

• 単調性消去符号: Encode および Decode アルゴリズムからなる方式。Encode はファイル $f$ をフラグメントのベクトル $(g_1, \dots, g_n)$ にマップします。ここで、フラグメントは異なるサイズを持つ可能性があります。Decode は、アクセス集合 $A \in \mathcal{A}$ に対応するフラグメントの任意のサブセットから $f$ を復元します。
• 効率性: オーバーヘッド $\beta = (\mu - \kappa) / \kappa$ によって測定されます。ここで、$\kappa$ は入力ファイルのサイズ、$\mu$ はすべてのフラグメントの合計サイズです。目標は $\beta$ を最小化することです。
• 線形単調性消去符号: 符号化と復号が有限体 $\mathbb{F}_q$ 上の線形演算である特定のクラスです。符号化は、生成行列 $G$ と、$G$ の列をノードにマップするラベル付け関数 $\phi$ によって定義されます。あるノードの集合が十分であるとは、そのノードに対応する $G$ の部分行列がフルランク（$k$）を持つことを意味します。

2.2 構築アプローチ

本論文は、これらの符号を構築するための 3 つの異なる手法を提示します。

1. 基本構築（最適ではない）:

   • アクセス構造を表す単調ブール式（MBF）に基づいています。
   • アルゴリズムはアクセス木を再帰的に走査します。AND ノードの場合、ファイルはチャンクに分割されます。OR ノードの場合、ファイルは複製されます。
   • 結果: 完全性を保証しますが、木構造における冗長な複製により、しばしば高いオーバーヘッドをもたらします。

2. 効率的な線形構築（準最適）:

   • ブロックごとの MDS 行列を構築する再帰アルゴリズムを使用します。
   • 符号化行列は、閾値演算子用のヴァンデルモンド行列を、次元を揃えるためにクロネッカー積と単位行列を組み合わせて構築します。
   • 結果: 計算効率的（アクセスサイズの多項式）ですが、最小のオーバーヘッドを保証するものではありません。

3. 線形計画法による最適線形構築:

   • 一般ケース: 最適なフラグメント分布を見つける問題を**線形計画法問題（LPP）**として定式化します。目的は、すべてのアクセス集合が少なくとも $k$ 個の「ベース」フラグメント（基盤となる MDS 符号から導出）を保持するという制約の下で、ノードに割り当てられたフラグメントの重みの和を最小化することです。
   • 分割アクセス構造: 特定のクラスの構造（階層的であり、各ノードが MBF に正確に 1 回現れるもの、例：Stellar の信頼モデル）に対して、本論文は特殊な再帰アルゴリズム（アルゴリズム 2）を提供します。このアルゴリズムは、オーバーヘッドを最小化するためにどの部分木を含めるか除外するかを特定することにより、LPP を効率的に（$O(n^2)$）解き、ベースフラグメントの最適な割り当てを事実上決定します。

2.3 プロトコル応用：GAVID

本論文は、これらの符号を**一般非同期検証可能情報分散（GAVID）**と呼ばれる分散プロトコルに統合します。

• 一般化: 従来の AVID プロトコル（Cachin および Tessaro）を、閾値システムから一般的なビザンチンクォーラムシステムへと拡張します。
• メカニズム: クォーラムシステムのカーネルシステムを、単調性消去符号のアクセス構造として使用します。
• 主要概念: 非同期環境における可用性と一貫性を保証するために、任意の故障集合と共通部分を持たないカーネルを含む集合である信頼集合を導入します。
• 最適化: 完全な検証ベクトルを Merkle 木のルートに置き換えるGAVID-Hを提案し、通信複雑性を削減します。

3. 主要な貢献

1. 単調性消去符号の定義: 本論文は、古典的な消去符号を任意の単調アクセス構造に一般化し、非均一な信頼仮定を可能にする新しい符号化プリミティブを形式的に定義します。
2. 構築アルゴリズム:
   • 任意のアクセス構造に対する線形単調性消去符号を構築する計算効率的な手法を提供します（ただし、常にオーバーヘッドにおいて最適とは限りません）。
   • アクセス構造から導出された線形計画法問題を解くことで、最適な線形単調性消去符号を構築する手法を提供します。
3. 分割アクセス構造: 実用的に一般的な分割アクセス構造の特定のケースを分析し、それらに対する最適符号を構築する効率的なアルゴリズムを提示し、そのオーバーヘッドを特徴付けます。
4. GAVID プロトコル: 単調性消去符号を利用して、任意のクォーラムシステムに対する通信効率的なビザンチン信頼ブロードキャストを実現する、一般的な非同期検証可能情報分散プロトコル（GAVID）を定式化します。

4. 結果と分析

• オーバーヘッドの境界: 最小アクセス集合のサイズが $\tau$ である一般的なアクセス構造において、最適線形単調性消去符号のオーバーヘッド $\beta$ は、$k$ が大きい場合 $\beta \le (n - \tau)/\tau$ で抑えられます。これは、最小のアクセス集合がノードの総数に近い場合、オーバーヘッドがゼロに近づくことを意味します。
• 分割構築の効率性: 分割アクセス構造に特化したアルゴリズムは $O(n^2)$ の時間で実行され、アクセス集合の数が指数関数的に増える場合、一般的な LPP を直接解くよりもはるかに高速です。
• プロトコル複雑性:
  • GAVID Disperse: メッセージ複雑性 $O(n^2)$；通信複雑性 $O(n(1+\beta)|f| + n^3|H|)$。
  • GAVID-H（Merkle 最適化）: 通信複雑性を $O(n(1+\beta)|f| + n^2(\log n)|H|)$ に、記憶複雑性を $O((1+\beta)|f| + n(\log n)|H|)$ に削減します。
• 正しさ: 本論文は、システムのカーネル構造に対して単調性消去符号が存在する限り、GAVID が任意のビザンチンクォーラムシステムに対して終了性、合意、可用性、および正しさの性質を満たすことを証明しています。

5. 意義と主張

本論文は、単調性消去符号が信頼を考慮した分散システムにとって不可欠な促進要因であると主張しています。「任意の $n$ 個中 $k$ 個」という硬直的な閾値モデルを超えて移動することで、これらの符号はシステムに以下を可能にします。

• 冗長性の削減: 全てのノードを均等に扱うのではなく、信頼性の高いノードにはより多くのデータを割り当て、リスクの高いノードには少ないデータを割り当てることで、ストレージおよび通信オーバーヘッドを最適化します。
• 複雑な信頼モデルのサポート: 信頼が階層的かつ非均一である現実世界のブロックチェーンネットワーク（Stellar など）で見られる信頼仮定を直接実装します。
• プロトコルの一般化: 単純な閾値モデルだけでなく、一般的なビザンチンクォーラムシステムの下でも既存の効率的なブロードキャストおよびコンセンサスプロトコルが機能することを可能にする、基礎的なプリミティブ（GAVID）を提供します。

著者らは、分割構造に対する効率的な構築を提供している一方で、任意のアクセス構造（指数関数的に多くの集合を持つ MBF として与えられる）に対する最適な単調性消去符号を構築する問題は未解決であることを指摘しています。また、将来の課題として、動的符号や他の符号理論技術（レートレス符号など）のこの設定への応用を提案しています。