Asynchronous Verifiable Information Dispersal with Low Space and Communication Complexity

In de enorme, onzichtbare infrastructuur die de moderne wereld aandrijft, wordt data constant geschreven, opgeslagen en opgehaald via netwerken van computers. Deze systemen moeten robuust genoeg zijn om informatie veilig te houden, zelfs wanneer individuele machines falen, crashen of worden gecompromitteerd door kwaadwillende actoren. Om dit te bereiken, breken ingenieurs een enkel bestand vaak op in vele stukjes en verspreiden deze over verschillende locaties, een techniek die bekend staat als informatieverspreiding (information dispersal). Dit zorgt ervoor dat als sommige stukjes verloren gaan, het originele bestand nog steeds kan worden gereconstrueerd uit de resterende fragmenten. Het is echter een hardnekkige uitdaging geweest om de kosten van deze bescherming in balans te houden. Het veilig opslaan van data vereist meestal het bewaren van extra kopieën, wat ruimte verbruikt, terwijl het verplaatsen van die data om kapotte stukjes te herstellen of het te gebruiken voor consumptie, aanzienlijke bandbreedte verbruikt. Jarenlang waren de meest efficiënte methoden voor het opslaan van data traag en duur om te repareren, terwijl de snelste methoden voor het herstellen van defecte nodes ongelooflijk verspillend waren aan opslagruimte.

Onderzoekers Thomas Locher en Yvonne-Anne Pignolet hebben een nieuwe methode ontwikkeld die deze afweging doorbreekt, en biedt een manier om data te bewaren, te verspreiden en te herstellen die efficiënt is over al deze dimensies tegelijkertijd. Hun werk richt zich op een specifiek type systeem genaamd asynchrone verifieerbare informatieverspreiding, waarbij computers er niet voor hoeven te zorgen dat ze het exacte tijdstip van berichten overeenstemmen om correct te functioneren, maar toch nog steeds kunnen verifiëren dat de data die ze bevatten geldig en consistent is. Het team introduceerde een nieuw protocol dat data organiseert in een rasterachtige structuur, waardoor nodes net genoeg informatie kunnen delen om ontbrekende stukjes te reconstrueren zonder hele bestanden te hoeven downloaden. Deze aanpak vermindert aanzienlijk de hoeveelheid data die moet worden opgeslagen en de bandbreedte die nodig is om een gefaalde computer te herstellen, terwijl de snelheid behouden blijft die nodig is om informatie op te halen wanneer daarom wordt gevraagd.

De kern van dit nieuwe systeem ligt in de manier waarop de data wordt gerangschikt voordat deze wordt verzonden. In plaats van de informatie te behandelen als een eenvoudige lijst van fragmenten, coderen de onderzoekers het in een tweedimensionale matrix, of een rooster van rijen en kolommen. Stel je de data voor als een grote spreadsheet waarin elke cel een klein stukje van het originele bestand bevat. Het systeem past vervolgens een wiskundig proces toe om de lege cellen van dit rooster in te vullen, waardoor een web van redundantie ontstaat. Elke computer in het netwerk krijgt een specifieke rij en een specifieke kolom uit dit rooster toegewezen. De computer slaat alleen de data op die bij die rij en die kolom hoort, samen met een klein cryptografisch bewijs dat verifieert dat de data correct is. Deze structuur is de sleutel tot de efficiëntie van het systeem. Omdat elke computer een deel van de rij en kolom van elke andere computer bevat, kunnen ze elkaar helpen de gaten op te vullen als een machine faalt, zonder een centrale autoriteit te hoeven contacteren of de volledige dataset te hoeven downloaden.

Wanneer een nieuw stuk data moet worden opgeslagen, begint het proces met een cliënt die de initiële roosterinformatie naar het netwerk stuurt. De onderzoekers hebben een slim handshake-mechanisme ontworpen om ervoor te zorgen dat dit snel gebeurt en zonder bandbreedte te verspillen. De cliënt stuurt de benodigde data naar elke computer en wacht op bevestiging dat de data is ontvangen. Als een computer niet reageert, stuurt de cliënt niet simpelweg het volledige bestand opnieuw naar iedereen. In plaats daarvan stuurt het een kleine, gerichte update met alleen de ontbrekende stukjes naar de specifieke computers die ze nodig hebben. De andere computers in het netwerk, die al een fragment van de ontbrekende data in hun eigen opslag hebben, sturen die specifieke stukjes vervolgens door naar de moeizame nodes. Deze coöperatieve stap betekent dat het netwerk het opslagproces kan voltooien met veel minder totale databeweging dan eerdere methoden, die vaak de volledige dataset meerdere keren moesten verzenden om te garanderen dat iedereen een kopie had.

Het ophalen van de data is even gestroomlijnd. Wanneer een gebruiker een bestand wil lezen, vraat hij een voldoende aantal computers om hun rijdata. Vanwege de manier waarop het rooster is geconstrueerd, kan de gebruiker het originele bestand reconstrueren vanuit deze rijen alleen, zonder contact te hoeven leggen met elke node in het netwerk. Het systeem verifieert de integriteit van de data met behulp van de cryptografische bewijzen die naast de fragmenten zijn opgeslagen, waardoor wordt gegarandeerd dat er geen gecorrumpeerde of kwaadwillende informatie wordt geretourneerd. Dit ophaalproces is even efficiënt als de beste bestaande methoden, wat betekent dat de snelheid van het lezen van data niet is opgeofferd om de andere verbeteringen te verkrijgen.

Misschien wel de meest significante vooruitgang is hoe het systeem omgaat met reparaties wanneer een computer faalt. In oudere systemen vereiste het vervangen van een defecte node vaak dat de nieuwe machine de volledige dataset van het netwerk moest downloaden om zijn aandeel te herbouwen, een proces dat dagen kon duren voor grote bestanden en enorme hoeveelheden bandbreedte verbruikte. In dit nieuwe protocol hoeft een vervangende node slechts contact op te nemen met een paar andere computers om zijn specifieke rij- en kolomdata te herstellen. Deze buren sturen precies de kleine stukjes informatie die snijden met de positie van de nieuwe node in het rooster. De nieuwe node gebruikt deze fragmenten vervolgens om zijn volledige opslagdeel wiskundig te reconstrueren. Dit vermindert de hoeveelheid overgedragen data tijdens een reparatie met een aanzienlijke marge, waardoor het systeem levensvatbaar is voor grootschalige, real-world toepassingen waar nodes regelmatig het netwerk betreden of verlaten.

De onderzoekers hebben hun protocol geanalyseerd ten opzichte van bestaande standaarden en vonden dat het er consequent beter presteert op alle fronten. Voor een netwerk van honderd computers die een bestand van één gigabyte opslaan, vereist hun methode dat elke node slechts dertig megabyte opslaat, terwijl een leidende alternatieve methode vijfenveertig megabyte vereist. Dit verschil lijkt klein voor een enkel bestand, maar wanneer het wordt geschaald naar petabytes aan data over een mondiaal netwerk, vertaalt dit zich naar een vermindering van anderhalve petabyte aan totale opslagvereisten. Op dezelfde manier vereist een nieuwe node wanneer een node faalt, om zichzelf te repareren, veertig terabyte aan data te downloaden, vergeleken met vijfenzeventig terabyte onder de vorige beste methode. Dit bespaart dertig terabyte aan verkeer, wat bij de volledige netwerkcapaciteit bijna drie dagen aan reparatieverkeer betekent dat niet langer nodig is.

Het team heeft ook een variatie van hun protocol verkend die gebruikers in staat stelt de parameters van het systeem af te stemmen op basis van hun specifieke behoeften. Door één enkele parameter aan te passen, kunnen beheerders ervoor kiezen om de gebruikte opslagruimte nog verder te minimaliseren, ten koste van een iets hogere bandbreedtevereiste voor reparaties en ophalen. Deze flexibiliteit maakt het protocol geschikt voor een breed scala aan scenario's, van gedecentraliseerde archieven die prioriteit geven aan langetermijnopslag-efficiëntie tot high-performance systemen die snelle toegang tot data nodig hebben. Het werk toont aan dat het mogelijk is om gedistribueerde opslagsystemen te ontwerpen die niet alleen theoretisch optimaal zijn in één gebied, maar praktisch efficiënt zijn over de gehele levenscyclus van data, van het moment dat het wordt geschreven tot het moment dat het wordt gerepareerd of opgehaald.

Dit onderzoek biedt een concrete weg voorwaarts voor de volgende generatie gedistribueerde opslagsystemen, door de knelpunten aan te pakken die hun schaalbaarheid hebben beperkt. Door te bewijzen dat een lage opslagoverhead, lage communicatiekosten voor schrijven en efficiënt nodeherstel naast elkaar kunnen bestaan, hebben de auteurs een belangrijke barrière weggenomen voor de implementatie van robuuste, gedecentraliseerde datanetwerken. De resultaten zijn niet louter theoretisch; de specifieke constanten die in de studie zijn afgeleid, vertalen zich direct in tastbare besparingen in operationele kosten en netwerkcapaciteit. Naarmate systemen zoals gedecentraliseerde archieven en blockchain-oplossingen blijven groeien, zullen protocollen die data efficiënt kunnen beheren zonder de betrouwbaarheid op te offeren, steeds essentiëler worden, en deze nieuwe methode biedt een gebalanceerd, hoogwaardig fundament voor die toekomst.