Technische Zusammenfassung: Monotone Löschr Codes

1. Problemstellung

Traditionelle Löschr Codes, wie Reed-Solomon (MDS) Codes, arbeiten unter der Annahme einer Schwellenwert-Ausfallhypothese. In diesen Systemen wird Daten in $k$ Teile aufgeteilt und in $n$ Fragmente kodiert, sodass beliebige $k$ Fragmente für die Rekonstruktion ausreichen. Dieses Modell geht davon aus, dass jede Teilmenge von $k$ Knoten gleichermaßen verfügbar ausfallen kann, unabhängig von der spezifischen Identität der Knoten.

Moderne verteilte Systeme, insbesondere in Blockchain- und Kryptowährungskontexten (z. B. Stellar, XRP Ledger), nutzen jedoch generalisierte Ausfallannahmen oder byzantinische Quorum-Systeme. In diesen Kontexten ist das Vertrauen nicht einheitlich; einige Knoten sind vertrauenswürdiger als andere, und Ausfallmuster sind nicht rein zufällig, sondern hängen von spezifischen Teilmengen von Knoten ab. Bestehende schwellenwertbasierte Codes können diese beliebigen Vertrauensannahmen nicht effizient berücksichtigen, ohne erheblichen Overhead oder strukturelle Inkompatibilität zu verursachen. Der vorliegende Beitrag adressiert die Notwendigkeit von Löschr Codes, die beliebige monotone Zugriffsstrukturen respektieren, bei denen bestimmte Teilmengen von Knoten (Zugriffsmengen) garantiert Daten rekonstruieren können, während andere dies möglicherweise nicht tun.

2. Methodik

Der Beitrag führt Monotone Löschr Codes ein, eine Verallgemeinerung klassischer Löschr Codes, die für beliebige Zugriffsstrukturen $\mathcal{A} \subseteq 2^{\mathcal{P}}$ konzipiert sind, wobei $\mathcal{P}$ die Menge der Knoten darstellt.

2.1 Definitionen und Formalismus

• Monotone Löschr Codes: Ein Schema bestehend aus Encode- und Decode-Algorithmen. Encode bildet eine Datei $f$ auf einen Vektor von Fragmenten $(g_1, \dots, g_n)$ ab, wobei Fragmente unterschiedliche Größen haben können. Decode rekonstruiert $f$ aus einer beliebigen Teilmenge von Fragmenten, die einer Zugriffsmenge $A \in \mathcal{A}$ entspricht.
• Effizienz: Gemessen durch den Overhead $\beta = (\mu - \kappa) / \kappa$, wobei $\kappa$ die Eingabedateigröße und $\mu$ die Gesamtgröße aller Fragmente ist. Das Ziel ist die Minimierung von $\beta$.
• Lineare Monotone Löschr Codes: Eine spezifische Klasse, bei der Kodierung und Dekodierung lineare Operationen über einem endlichen Körper $\mathbb{F}_q$ sind. Die Kodierung wird durch eine Generatormatrix $G$ und eine Beschriftungsfunktion $\phi$ definiert, die Spalten von $G$ auf Knoten abbildet. Eine Menge von Knoten ist ausreichend, wenn die Teilmatrix von $G$, die diesen Knoten entspricht, vollen Rang ($k$) hat.

2.2 Konstruktionsansätze

Der Beitrag stellt drei unterschiedliche Methoden zur Konstruktion dieser Codes vor:

1. Basis-Konstruktion (Nicht-optimal):

   • Basierend auf einer Monotonen Booleschen Formel (MBF), die die Zugriffsstruktur darstellt.
   • Der Algorithmus durchläuft rekursiv den Zugriffsbaum. Für einen UND-Knoten wird die Datei in Blöcke aufgeteilt; für einen ODER-Knoten wird die Datei repliziert.
   • Ergebnis: Garantiert Vollständigkeit, führt jedoch oft zu hohem Overhead durch redundante Replikation in der Baumstruktur.

2. Effiziente Lineare Konstruktion (Sub-optimal):

   • Verwendet einen rekursiven Algorithmus, der eine blockweise MDS-Matrix aufbaut.
   • Die Kodierungsmatrix wird durch die Kombination von Vandermonde-Matrizen (für Schwellenwert-Operatoren) unter Verwendung von Kronecker-Produkten und Einheitsmatrizen zur Dimensionsanpassung konstruiert.
   • Ergebnis: Rechnerisch effizient (polynomiell in der Größe des Zugriffsbaums), garantiert jedoch keinen minimalen Overhead.

3. Optimale Lineare Konstruktion (via Lineare Programmierung):

   • Allgemeiner Fall: Formuliert das Problem der Suche nach einer optimalen Fragmentverteilung als Lineares Programmierungsproblem (LPP). Das Ziel ist die Minimierung der Summe der den Knoten zugewiesenen Fragmentgewichte, unter der Bedingung, dass jede Zugriffsmenge mindestens $k$ „Basis"-Fragmente (abgeleitet aus einem zugrunde liegenden MDS-Code) enthält.
   • Partitionierte Zugriffsstrukturen: Für eine spezifische Klasse von Strukturen (hierarchisch, wobei jeder Knoten genau einmal in der MBF erscheint, z. B. das Vertrauensmodell von Stellar) stellt der Beitrag einen spezialisierten rekursiven Algorithmus (Algorithmus 2) bereit. Dieser Algorithmus löst das LPP effizient ($O(n^2)$), indem er identifiziert, welche Teilbäume ein- oder ausgeschlossen werden sollen, um den Overhead zu minimieren, und effektiv eine optimale Zuweisung von Basis-Fragmenten bestimmt.

2.3 Protokollanwendung: GAVID

Der Beitrag integriert diese Codes in ein verteiltes Protokoll namens General Asynchronous Verifiable Information Dispersal (GAVID).

• Verallgemeinerung: Erweitert das klassische AVID-Protokoll (Cachin und Tessaro) von Schwellenwert-Systemen auf allgemeine byzantinische Quorum-Systeme.
• Mechanismus: Verwendet das Kernsystem des Quorum-Systems als Zugriffsstruktur für den monotonen Löschr Code.
• Schlüsselkonzepte: Führt Zuverlässige Mengen (Mengen, die einen Kern enthalten, der disjunkt zu jeder fehlerhaften Menge ist) ein, um Verfügbarkeit und Konsistenz im asynchronen Setting sicherzustellen.
• Optimierung: Schlägt GAVID-H vor, das den vollständigen Verifikationsvektor durch eine Merkle-Baum-Wurzel ersetzt, wodurch die Kommunikationskomplexität reduziert wird.

3. Hauptbeiträge

1. Definition von Monotonen Löschr Codes: Der Beitrag definiert formell ein neues Kodierungs-Primitiv, das klassische Löschr Codes auf beliebige monotone Zugriffsstrukturen verallgemeinert und nicht-uniforme Vertrauensannahmen ermöglicht.
2. Konstruktionsalgorithmen:
   • Bietet eine rechnerisch effiziente Methode zum Aufbau linearer monotoner Löschr Codes für jede Zugriffsstruktur (wenn auch nicht immer optimal im Overhead).
   • Bietet eine Methode zur Konstruktion optimaler linearer monotoner Löschr Codes durch Lösen eines aus der Zugriffsstruktur abgeleiteten linearen Programmierungsproblems.
3. Partitionierte Zugriffsstrukturen: Analysiert den spezifischen Fall partitionierter Zugriffsstrukturen (in der Praxis üblich) und stellt einen effizienten Algorithmus zur Konstruktion optimaler Codes für diese bereit, wobei deren Overhead charakterisiert wird.
4. GAVID-Protokoll: Formuliert ein allgemeines asynchrones verifizierbares Informationsdispersions-Protokoll (GAVID), das monotone Löschr Codes nutzt, um kommunikationseffiziente byzantinische zuverlässige Broadcasts für beliebige Quorum-Systeme zu erreichen.

4. Ergebnisse und Analyse

• Overhead-Schranken: Für eine allgemeine Zugriffsstruktur mit minimaler Zugriffsmengengröße $\tau$ ist der Overhead $\beta$ eines optimalen linearen monotonen Löschr Codes für große $k$ durch $\beta \le (n - \tau)/\tau$ beschränkt. Dies impliziert, dass, wenn die kleinste Zugriffsmenge nahe an der Gesamtzahl der Knoten liegt, der Overhead gegen null geht.
• Effizienz der Partitionierten Konstruktion: Der spezialisierte Algorithmus für partitionierte Zugriffsstrukturen läuft in $O(n^2)$ Zeit, was signifikant schneller ist als das direkte Lösen des allgemeinen LPP, wenn die Anzahl der Zugriffsmengen exponentiell ist.
• Protokollkomplexität:
  • GAVID Disperse: Nachrichtenkomplexität $O(n^2)$; Kommunikationskomplexität $O(n(1+\beta)|f| + n^3|H|)$.
  • GAVID-H (Merkle-optimiert): Reduziert die Kommunikationskomplexität auf $O(n(1+\beta)|f| + n^2(\log n)|H|)$ und die Speicherkomplexität auf $O((1+\beta)|f| + n(\log n)|H|)$.
• Korrektheit: Der Beitrag beweist, dass GAVID die Eigenschaften Terminierung, Einigung, Verfügbarkeit und Korrektheit für jedes byzantinische Quorum-System erfüllt, sofern ein monotoner Löschr Code für die Kernstruktur des Systems existiert.

5. Bedeutung und Behauptungen

Der Beitrag behauptet, dass monotone Löschr Codes ein entscheidender Enabler für vertrauensbewusste verteilte Systeme sind. Durch die Überwindung des starren „beliebige $k$ von $n$"-Schwellenwertmodells ermöglichen diese Codes Systemen:

• Redundanz zu reduzieren: Speicher- und Kommunikations-Overhead zu optimieren, indem mehr Daten vertrauenswürdigen Knoten und weniger Daten riskanten Knoten zugewiesen werden, anstatt alle Knoten gleich zu behandeln.
• Komplexe Vertrauensmodelle zu unterstützen: Die in realen Blockchain-Netzwerken (wie Stellar) vorkommenden Vertrauensannahmen direkt zu implementieren, wo Vertrauen hierarchisch und nicht-uniform ist.
• Protokolle zu verallgemeinern: Ein grundlegendes Primitiv (GAVID) bereitzustellen, das es bestehenden effizienten Broadcast- und Konsensprotokollen ermöglicht, unter allgemeinen byzantinischen Quorum-Systemen zu funktionieren und nicht nur unter einfachen Schwellenwertmodellen.

Die Autoren weisen darauf hin, dass sie zwar eine effiziente Konstruktion für partitionierte Strukturen bereitstellen, das Problem der Konstruktion eines optimalen monotonen Löschr Codes für eine beliebige Zugriffsstruktur (gegeben als MBF mit exponentiell vielen Mengen) jedoch eine offene Frage bleibt. Sie schlagen zudem zukünftige Arbeiten zu dynamischen Codes und die Anwendung anderer Kodierungstheorie-Techniken (z. B. rateless Codes) auf dieses Setting vor.