Technische Samenvatting: Monotone Verwijderingscodes

1. Probleemstelling

Traditionele verwijderingscodes, zoals Reed-Solomon (MDS) codes, werken onder een drempeluitvalveronderstelling. In deze systemen wordt data verdeeld in $k$ stukken en gecodeerd in $n$ fragmenten, zodat elk willekeurig aantal van $k$ fragmenten voldoende is voor reconstructie. Dit model veronderstelt dat elk willekeurig subset van $k$ knopen even waarschijnlijk beschikbaar is of uitvalt, ongeacht de specifieke identiteit van de knopen.

Echter, moderne gedistribueerde systemen, met name in blockchain en cryptocurrency (bijv. Stellar, XRP Ledger), maken gebruik van gegeneraliseerde uitvalveronderstellingen of Byzantijnse quorumsystemen. In deze contexten is vertrouwen niet uniform; sommige knopen zijn betrouwbaarder dan anderen, en uitvalpatronen zijn niet puur willekeurig maar afhankelijk van specifieke subsets van knopen. Bestaande drempelgebaseerde codes kunnen deze willekeurige vertrouwensveronderstellingen niet efficiënt accommoderen zonder aanzienlijke overhead of structurele mismatch. Het artikel adresseert de behoefte aan verwijderingscodes die willekeurige monotone toegangsstructuren respecteren, waarbij specifieke subsets van knopen (toegangsets) gegarandeerd data kunnen reconstrueren, terwijl anderen dit mogelijk niet kunnen.

2. Methodologie

Het artikel introduceert Monotone Verwijderingscodes, een generalisatie van klassieke verwijderingscodes ontworpen om te werken met willekeurige toegangsstructuren $\mathcal{A} \subseteq 2^{\mathcal{P}}$, waarbij $\mathcal{P}$ de verzameling van knopen is.

2.1 Definities en Formalisme

• Monotone Verwijderingscode: Een schema bestaande uit Encode- en Decode-algoritmen. Encode mapt een bestand $f$ af op een vector van fragmenten $(g_1, \dots, g_n)$, waarbij fragmenten verschillende maten kunnen hebben. Decode reconstrueert $f$ vanuit elk subset van fragmenten dat overeenkomt met een toegangset $A \in \mathcal{A}$.
• Efficiëntie: Gemeten door overhead $\beta = (\mu - \kappa) / \kappa$, waarbij $\kappa$ de invoerbestandsgrootte is en $\mu$ de totale grootte van alle fragmenten. Het doel is om $\beta$ te minimaliseren.
• Lineaire Monotone Verwijderingscodes: Een specifieke klasse waarbij codering en decodering lineaire operaties zijn over een eindig veld $\mathbb{F}_q$. De codering wordt gedefinieerd door een generatormatrix $G$ en een labelfunctie $\phi$ die kolommen van $G$ afbeeldt op knopen. Een set knopen is voldoende als de submatrix van $G$ die overeenkomt met die knopen volledige rang ($k$) heeft.

2.2 Constructiebenaderingen

Het artikel presenteert drie onderscheiden methoden voor het construeren van deze codes:

1. Basisconstructie (Niet-Optimaal):

   • Gebaseerd op een Monotone Boolese Formule (MBF) die de toegangsstructuur vertegenwoordigt.
   • Het algoritme traverseert de toegangsboom recursief. Voor een EN-knoop wordt het bestand opgesplitst in chunks; voor een OF-knoop wordt het bestand gerepliceerd.
   • Resultaat: Garandeert volledigheid maar resulteert vaak in hoge overhead door redundante replicatie in de boomstructuur.

2. Efficiënte Lineaire Constructie (Sub-Optimaal):

   • Gebruikt een recursief algoritme dat een blokgewijze MDS-matrix bouwt.
   • Het construeert de coderingsmatrix door Vandermonde-matrices (voor drempeloperatoren) te combineren met behulp van Kronecker-producten en identiteitsmatrices om de dimensies af te stemmen.
   • Resultaat: Rekenkundig efficiënt (polynoom in de grootte van de toegangsboom) maar garandeert geen minimale overhead.

3. Optimale Lineaire Constructie (via Lineair Programmeren):

   • Algemeen Geval: Formuleert het probleem van het vinden van de optimale fragmentverdeling als een Lineair Programmeringsprobleem (LPP). Het doel is om de som van aan knopen toegewezen fragmentgewichten te minimaliseren, onderworpen aan beperkingen dat elke toegangset ten minste $k$ "basis" fragmenten bevat (afgeleid van een onderliggende MDS-code).
   • Gepartitioneerde Toegangsstructuren: Voor een specifieke klasse van structuren (hiërarchisch, waarbij elke knoop exact één keer voorkomt in de MBF, bijv. het vertrouwensmodel van Stellar), biedt het artikel een gespecialiseerd recursief algoritme (Algoritme 2). Dit algoritme lost het LPP efficiënt op ($O(n^2)$) door te identificeren welke subbomen wel of niet moeten worden opgenomen om de overhead te minimaliseren, en bepaalt effectief een optimale toewijzing van basisfragmenten.

2.3 Protocoltoepassing: GAVID

Het artikel integreert deze codes in een gedistribueerd protocol genaamd General Asynchronous Verifiable Information Dispersal (GAVID).

• Generalisatie: Breidt het klassieke AVID-protocol (Cachin en Tessaro) uit van drempelsystemen naar algemene Byzantijnse quorumsystemen.
• Mechanisme: Gebruikt het kernsysteem van het quorumsysteem als de toegangsstructuur voor de monotone verwijderingscode.
• Belangrijke Concepten: Introduceert Betrouwbare Sets (sets die een kern bevatten die disjunct is van elke defecte set) om beschikbaarheid en consistentie in de asynchrone setting te waarborgen.
• Optimalisatie: Stelt GAVID-H voor, dat de volledige verificatievector vervangt door een Merkle-boomwortel, waardoor de communicatiecomplexiteit wordt verminderd.

3. Belangrijkste Bijdragen

1. Definitie van Monotone Verwijderingscodes: Het artikel definieert formeel een nieuw coderingsprimitief dat klassieke verwijderingscodes generaliseert naar willekeurige monotone toegangsstructuren, waardoor niet-uniforme vertrouwensveronderstellingen mogelijk worden.
2. Constructiealgoritmen:
   • Biedt een rekenkundig efficiënte methode om lineaire monotone verwijderingscodes te bouwen voor elke toegangsstructuur (hoewel niet altijd optimaal in overhead).
   • Biedt een methode om optimale lineaire monotone verwijderingscodes te construeren door een lineair programmeringsprobleem op te lossen dat is afgeleid van de toegangsstructuur.
3. Gepartitioneerde Toegangsstructuren: Analyseert het specifieke geval van gepartitioneerde toegangsstructuren (veelvoorkomend in de praktijk) en presenteert een efficiënt algoritme om optimale codes voor deze te construeren, waarbij hun overhead wordt gekarakteriseerd.
4. GAVID-protocol: Formuleert een algemeen asynchroon verifieerbaar informatieverspreidingsprotocol (GAVID) dat monotone verwijderingscodes gebruikt om communicatie-efficiënte Byzantijnse betrouwbare broadcast te bereiken voor willekeurige quorumsystemen.

4. Resultaten en Analyse

• Overheadgrenzen: Voor een algemene toegangsstructuur met minimale toegangsetgrootte $\tau$, wordt de overhead $\beta$ van een optimale lineaire monotone verwijderingscode begrensd door $\beta \le (n - \tau)/\tau$ voor grote $k$. Dit impliceert dat als de kleinste toegangset dicht bij het totale aantal knopen ligt, de overhead naar nul nadert.
• Efficiëntie van Gepartitioneerde Constructie: Het gespecialiseerde algoritme voor gepartitioneerde toegangsstructuren draait in $O(n^2)$ tijd, wat aanzienlijk sneller is dan het direct oplossen van het algemene LPP wanneer het aantal toegangsets exponentieel is.
• Protocollcomplexiteit:
  • GAVID Disperse: Berichtcomplexiteit $O(n^2)$; Communicatiecomplexiteit $O(n(1+\beta)|f| + n^3|H|)$.
  • GAVID-H (Merkle geoptimaliseerd): Vermindert de communicatiecomplexiteit tot $O(n(1+\beta)|f| + n^2(\log n)|H|)$ en de opslagcomplexiteit tot $O((1+\beta)|f| + n(\log n)|H|)$.
• Correctheid: Het artikel bewijst dat GAVID voldoet aan de eigenschappen Terminatie, Akkoord, Beschikbaarheid en Correctheid voor elk Byzantijns quorumsysteem, mits er een monotone verwijderingscode bestaat voor de kernstructuur van het systeem.

5. Betekenis en Beweringen

Het artikel beweert dat monotone verwijderingscodes een kritieke enable zijn voor vertrouwensbewuste gedistribueerde systemen. Door voorbij te gaan aan het rigide "elk $k$ van $n$" drempelmodel, stellen deze codes systemen in staat om:

• Redundantie te Verminderen: Opslag- en communicatie-overhead te optimaliseren door meer data toe te wijzen aan betrouwbare knopen en minder aan risicovolle, in plaats van alle knopen gelijk te behandelen.
• Complexe Vertrouwensmodellen te Ondersteunen: De vertrouwensveronderstellingen die voorkomen in echte blockchain-netwerken (zoals Stellar) direct te implementeren, waar vertrouwen hiërarchisch en niet-uniform is.
• Protocollen te Generaliseren: Een fundamenteel primitief (GAVID) te bieden dat bestaande efficiënte broadcast- en consensusprotocollen mogelijk maakt om te functioneren onder algemene Byzantijnse quorumsystemen, niet alleen onder eenvoudige drempelmodellen.

De auteurs merken op dat hoewel ze een efficiënte constructie bieden voor gepartitioneerde structuren, het probleem van het construeren van een optimale monotone verwijderingscode voor een willekeurige toegangsstructuur (gegeven als een MBF met exponentieel veel sets) een open vraag blijft. Zij suggereren ook toekomstig werk in dynamische codes en de toepassing van andere coderingstheorie-technieken (bijv. rateless codes) op deze setting.