‘Magisch’ foutcorrectiesysteem bleek inherent inefficiënt | Quanta-tijdschrift

Als u ooit een sms-bericht heeft verzonden, een cd heeft afgespeeld of een bestand in de cloud heeft opgeslagen, heeft u geprofiteerd van foutcorrectie. Dit revolutionaire idee dateert uit de jaren veertig, toen onderzoekers zich voor het eerst realiseerden dat het mogelijk is om elke boodschap te herschrijven in een vorm waarin latere corruptie gemakkelijk ongedaan kan worden gemaakt.

In de loop der jaren hebben onderzoekers veel ingenieuze schema's ontwikkeld, foutcorrectiecodes genoemd, die gegevens op verschillende manieren coderen en verschillende procedures gebruiken om fouten te herstellen. Maar voor theoretische computerwetenschappers zijn er maar weinig zo overtuigend als zogenaamde lokaal corrigeerbare codes. Deze codes hebben twee gelijktijdige eigenschappen die bijna tegenstrijdig klinken: elke fout kan worden gecorrigeerd door de gecodeerde gegevens op slechts een paar plaatsen te lezen, maar geen enkele aanvaller kan deze correctieprocedure omzeilen door selectief met de code te knoeien. Het is alsof je elke uit een boek gescheurde pagina kunt herstellen door gewoon naar een paar andere te kijken.

“Het is een nogal magisch fenomeen”, zegt hij Tom Gur, een computerwetenschapper aan de Universiteit van Cambridge. “A priori is het niet vanzelfsprekend dat zo’n wiskundig object überhaupt zou kunnen bestaan.”

Maar deze magie brengt hoge kosten met zich mee. De enige bekende voorbeelden van lokaal corrigeerbare codes zijn uiterst inefficiënt: het coderen van elk bericht maakt het ook exponentieel langer. Hele boeken die op deze manier gecodeerd zijn, zouden veel te log zijn.

Computerwetenschappers vragen zich al lang af of er beter lokaal corrigeerbare codes mogelijk zijn. Ze hebben zich vooral gericht op codes die slechts drie zoekopdrachten gebruiken om fouten te corrigeren, in de hoop dat deze strenge beperking deze codes gemakkelijker te begrijpen maakt. Maar zelfs dit eenvoudige geval heeft onderzoekers al meer dan twintig jaar met stomheid geslagen.

Nu de computerwetenschapper Pravesh Kothari van Carnegie Mellon University en zijn afgestudeerde student Peter Manohar hebben eindelijk bewezen dat het onmogelijk is om een ​​lokaal corrigeerbare code van drie vragen te bouwen die deze exponentiële kosten vermijdt. Het kan een negatief resultaat zijn, maar alles dat de grenzen van foutcorrectie verduidelijkt, is spannend voor onderzoekers, vooral omdat de wiskunde van lokaal corrigeerbare codes opduikt in gebieden die ver verwijderd zijn van communicatie.

“Dit resultaat is verbazingwekkend”, zegt hij Shubhangi Saraf, een computerwetenschapper aan de Universiteit van Toronto. “Het is een enorme doorbraak.”

Kracht in getallen

Om foutcorrectie te begrijpen, stelt u zich de gegevens die u wilt beschermen voor als een reeks bits, of nullen en enen. Een fout kan in dit model elke ongewenste omzetting van een 0 in een 1 zijn, of andersom, of dit nu het gevolg is van een willekeurige fluctuatie of van opzettelijk geknoei.

Stel dat u een bericht naar een vriend wilt sturen, maar u bent bang dat fouten de betekenis kunnen veranderen. Een eenvoudige strategie is om elke 0 in uw bericht te vervangen door 000 en elke 1 door 111. Als uw vriend een deel van het bericht ziet dat niet drie identieke bits achter elkaar bevat, weet hij of zij dat er een fout is opgetreden. En als fouten willekeurig en relatief zeldzaam zijn, is de kans veel groter dat elke reeks van 110 een corrupte 111 is dan een corrupte 000. Een gewone meerderheid van stemmen binnen elke triplet zal voldoende zijn om de meeste fouten te corrigeren.

Dit schema, de herhalingscode genoemd, heeft de deugd van eenvoud, maar heeft verder weinig aan te bevelen. Om te beginnen is het nodig om de lengte van elk bericht te verdrievoudigen om relatief zeldzame fouten te kunnen behandelen, en als er een behoorlijke kans is op twee aangrenzende fouten, hebben we zelfs nog meer redundantie nodig. Erger nog, het wordt snel nutteloos als fouten niet willekeurig zijn, bijvoorbeeld wanneer aanvallers actief proberen de code te saboteren. In de herhalingscode wordt alle informatie die nodig is om een ​​bepaald bit te corrigeren opgeslagen in slechts een paar andere bits, waardoor deze kwetsbaar wordt voor een gerichte aanval.

Gelukkig doen veel foutcorrectiecodes het beter. Een beroemd voorbeeld, genaamd de Reed-Solomon-code, werkt door berichten om te zetten in polynomen - wiskundige uitdrukkingen zoals x² + 3x + 2 die bestaan ​​uit verschillende termen bij elkaar opgeteld, elk met een variabele (zoals x) tot een andere macht verheven. Het coderen van een bericht met behulp van een Reed-Solomon-code omvat het bouwen van een polynoom met één term voor elk teken in het bericht, het vervolgens uitzetten van de polynoom als een curve in een grafiek en het opslaan van de coördinaten van punten die op de curve liggen (waarbij minstens één extra term wordt genomen). punt dan het aantal tekens). Fouten kunnen een paar van deze punten van de curve duwen, maar als er niet te veel fouten zijn, zal slechts één polynomiale curve door de meeste punten gaan. Die curve komt vrijwel zeker overeen met de ware boodschap.

Reed-Solomon-codes zijn hyperefficiënt: u hoeft slechts een paar extra punten op te slaan om fouten te corrigeren, dus elk gecodeerd bericht is slechts marginaal langer dan het origineel. Ze zijn ook minder kwetsbaar voor het soort gerichte verstoring dat een ramp zou betekenen voor de herhalingscode, omdat de informatie die wordt gebruikt om ergens een fout te corrigeren, over het gehele gecodeerde bericht wordt verspreid.

Denk globaal, handel plaatselijk

De kracht van de Reed-Solomon-code komt voort uit de onderlinge verbondenheid. Maar juist vanwege die onderlinge verbondenheid is er geen manier om één enkele fout in een gecodeerd bericht te herstellen zonder het hele bericht te lezen. Dat klinkt misschien niet als een probleem in de context van communicatie: als je een bericht verzendt, wil je waarschijnlijk dat de ontvanger het allemaal leest. Maar het kan een probleem zijn bij de gegevensopslag – een andere belangrijke toepassing van foutcorrectie.

Neem een ​​bedrijf dat de e-mails van gebruikers in de cloud opslaat, dat wil zeggen op een groot aantal servers. Je kunt de hele verzameling e-mails beschouwen als één lang bericht. Stel nu dat één server crasht. Met een Reed-Solomon-code zou u een enorme berekening moeten uitvoeren waarbij alle gecodeerde gegevens betrokken zijn om uw e-mails van die ene verloren server te herstellen. “Je zou naar alles moeten kijken”, zei hij Zeev Dvir, een computerwetenschapper aan de Universiteit van Princeton. “Dat kunnen miljarden en miljarden e-mails zijn – het kan heel lang duren.”

Onderzoekers gebruiken de term ‘lokaal’ om codes te beschrijven die slechts een fractie van het gecodeerde bericht gebruiken fouten ontdekken of corrigeer ze. De eenvoudige herhalingscode heeft iets van dit lokale karakter, maar dat maakt hem juist zo kwetsbaar voor manipulatie. Een lokaal corrigeerbare code combineert daarentegen het beste van twee werelden: hij kan met slechts een paar vragen een fout op elk gewenst moment corrigeren, zonder de onderlinge verbondenheid te verliezen die Reed-Solomon-codes zo veerkrachtig maakt.

“Dit is een heel strikt idee”, zei Kothari.

De bekendste voorbeelden van lokaal corrigeerbare codes zijn versies van een eerbiedwaardige foutcorrectiecode die in 1954 door wiskundigen werd uitgevonden. David Müller en Irving Reed (die ook hielp bij het ontwikkelen van Reed-Solomon-codes). Net als Reed-Solomon-codes gebruiken Reed-Muller-codes polynomen waarbij veel termen bij elkaar worden opgeteld om lange berichten te coderen.

De polynomen die in Reed-Solomon-codes worden gebruikt, hebben betrekking op een enkele variabele, x, dus de enige manier om meer termen toe te voegen is door hogere machten van te gebruiken x. Dit resulteert in een curve met veel kronkels die alleen kan worden vastgezet door naar veel punten te kijken. Reed-Muller-codes gebruiken in plaats daarvan polynomen waarin elke term meerdere met elkaar vermenigvuldigde variabelen kan bevatten. Meer variabelen betekenen meer manieren om ze te combineren, wat op zijn beurt een manier biedt om het aantal polynomiale termen te vergroten zonder een individuele variabele tot zulke hoge machten te verheffen.

Reed-Muller-codes zijn zeer flexibel. U kunt langere berichten coderen door de hoogste macht die in de polynoom voorkomt te vergroten, het aantal variabelen te vergroten, of beide. Om een ​​Reed-Muller-code lokaal corrigeerbaar te maken, beperkt u eenvoudigweg het maximale vermogen van elke variabele tot een kleine constante waarde, en handelt u langere berichten af ​​door alleen het aantal variabelen te vergroten.

Specifiek voor een lokaal corrigeerbare code met drie vragen wordt dat maximale vermogen ingesteld op 2. Vervolgens traceert de polynomiale codering van het bericht, voor zover het elke individuele variabele betreft, een eenvoudige parabool. Om de exacte vorm van die parabool te bepalen, hoef je de curve slechts op drie punten te onderzoeken. Bovendien zijn er bij veel variabelen veel van dergelijke parabolen, die allemaal kunnen worden gebruikt om fouten te corrigeren. Dat maakt de codes van Reed-Muller zo veerkrachtig.

Helaas heeft de Reed-Muller-code een ernstig nadeel: het aantal bits dat nodig is om een ​​bericht te coderen, neemt exponentieel toe met het aantal variabelen. Als je een zeer lokale code wilt die fouten corrigeert met slechts een handvol vragen, heb je voor lange berichten veel variabelen nodig, en de Reed-Muller-code zal in de praktijk snel nutteloos worden.

“Exponentieel is in dit geval erg slecht”, zei Dvir. Maar is het onvermijdelijk?

Corrigeerbaar of decodeerbaar?

Terwijl computerwetenschappers probeerden efficiëntere, lokaal corrigeerbare codes te vinden, begonnen ze te vermoeden dat dergelijke codes helemaal niet mogelijk waren. In 2003, twee onderzoekers bewezen dat er geen manier is om de Reed-Muller-code te verslaan met slechts twee query's. Maar dat is zover als iemand kon.

"Als je eenmaal naar drie gaat, wordt onze kennis erg vaag", zei Kothari.

De volgende doorbraak maakte de zaken alleen maar ingewikkelder. In twee artikelen gepubliceerd in 2008 en 2009, lieten de computerwetenschappers Sergey Yekhanin en Klim Efremenko zien hoe je codes met drie zoekopdrachten kon construeren die efficiënter waren dan Reed-Muller-codes, maar deze codes waren niet helemaal lokaal corrigeerbaar. In plaats daarvan hadden ze een subtiel andere eigenschap, genaamd lokale decodeerbaarheid.

Laten we, om het verschil te begrijpen, ons opnieuw een aanbieder van cloudopslag voorstellen die de gegevens van gebruikers combineert in één lang bericht en deze beschermt met behulp van een foutcorrectiecode. Zowel lokaal corrigeerbare codes als lokaal decodeerbare codes kunnen met slechts een paar vragen een fout in elk stukje van het oorspronkelijke bericht corrigeren.

Maar elke foutcorrectiecode vereist ook extra bits die niet in het oorspronkelijke bericht zaten. Daarom wordt het coderen van een bericht langer. De twee soorten codes verschillen in de manier waarop ze met deze extra bits omgaan. Lokaal decodeerbare codes doen geen beloftes over het aantal queries dat nodig is om fouten in deze bits te corrigeren. Maar in een lokaal corrigeerbare code kan een fout in elk van de extra bits op precies dezelfde manier worden hersteld als een fout in elk bit van het oorspronkelijke bericht.

“Alles wat je opslaat, of het nu de originele gegevens van gebruikers zijn of de redundantie en de cheque-informatie – dit alles kan lokaal worden gecorrigeerd”, zegt Madhu Soedan, een computerwetenschapper aan de Harvard Universiteit.

Hoewel ze in principe verschillend waren, leken lokale corrigeerbaarheid en lokale decodeerbaarheid in de praktijk vóór 2008 altijd uitwisselbaar: elke bekende lokaal decodeerbare code was ook lokaal corrigeerbaar. De ontdekking van Jechanin en Efremenko bracht de mogelijkheid van een fundamenteel verschil tussen de twee omstandigheden naar voren. Of misschien was het mogelijk om de codes van Jechanin en Efremenko aan te passen om ze lokaal corrigeerbaar te maken. Dat zou de twee voorwaarden weer op gelijke voet brengen, maar het zou ook betekenen dat onderzoekers zich hadden vergist in de vraag hoe efficiënt lokaal corrigeerbare codes met drie vragen zouden kunnen zijn. Hoe dan ook, de conventionele wijsheid zou moeten veranderen.

Logica van lenen

Kothari en Manohar losten die spanning uiteindelijk op door een techniek uit een ander gebied van de computerwetenschap aan te passen: de studie van zogenaamde constraint-tevredenheidsproblemen. Proberen om de dinerplannen met een groep vrienden te coördineren, is een soort beperkingstevredenheidsprobleem. Iedereen heeft keuzes die hij of zij zal accepteren en keuzes waartegen hij zijn veto kan uitspreken. Het is jouw taak om óf een plan te vinden waar iedereen tevreden mee is, óf, als zo’n plan er niet is, daar zo snel mogelijk achter te komen.

Er is een inherente asymmetrie tussen deze twee mogelijke uitkomsten. Een aanvaardbare oplossing is misschien niet eenvoudig te vinden, maar als je die eenmaal hebt, is het gemakkelijk om iemand anders ervan te overtuigen dat deze zal werken. Maar zelfs als je weet dat het probleem werkelijk ‘onbevredigbaar’ is, is er misschien geen voorbeeld dat bewijs levert.

In 2021 maakten Kothari en Manohar, samen met Venkatesan Guruswami van de University of California, Berkeley, een grote doorbraak in de studie van beperkingentevredenheidsproblemen met behulp van een nieuwe theoretische techniek voor het identificeren van die lastige, onbevredigbare gevallen. Ze vermoedden dat de nieuwe methode ook een krachtig hulpmiddel zou zijn om andere problemen op te lossen, en Guruswami's afgestudeerde student Omar Alrabiah stelde voor om naar lokaal decodeerbare codes met drie vragen te kijken.

“Dit was als het ware een spijker met een hamer in onze hand”, zei Kothari.

De verrassende resultaten van Yekhanin en Efremenko hadden aangetoond dat lokaal decodeerbare codes met drie zoekopdrachten efficiënter konden zijn dan Reed-Muller-codes. Maar waren hun codes de best mogelijke, of konden lokaal decodeerbare codes met drie zoekopdrachten nog efficiënter worden? Kothari, Manohar, Guruswami en Alrabiah dachten dat hun nieuwe techniek de grenzen zou kunnen aantonen van hoe efficiënt dergelijke codes zouden kunnen zijn. Hun plan was om een ​​logische formule te bouwen die de structuur van alle mogelijke lokaal decodeerbare codes met drie vragen van een bepaalde grootte omvat, en deze onbevredigend te bewijzen, en daarmee aan te tonen dat zo'n code niet zou kunnen bestaan.

De vier onderzoekers zetten in 2022 een eerste stap in die richting nieuwe limiet over de maximale efficiëntie van lokaal decodeerbare codes met drie vragen. Het resultaat ging veel verder dan wat onderzoekers met andere technieken hadden kunnen bereiken, maar sloot niet uit dat alle codes efficiënter waren dan die van Yekhanin en Efremenko.

Kothari en Manohar vermoedden dat ze verder konden gaan. Maar de vooruitgang stagneerde totdat Manohar een snelle berekening maakte die aangaf dat de techniek misschien nog beter zou werken voor lokaal corrigeerbare codes dan voor lokaal decodeerbare codes.

Een paar maanden later, na nog veel meer valse starts waardoor ze vreesden dat ze te optimistisch waren geweest, maakte de techniek eindelijk zijn belofte waar. Kothari en Manohar bewezen dat het, zoals onderzoekers al vermoedden, onmogelijk is dat lokaal corrigeerbare code met drie vragen aanzienlijk beter werkt dan Reed-Muller-codes. Die exponentiële schaalvergroting is een fundamentele beperking. Hun resultaat was ook een dramatische demonstratie dat lokale corrigeerbaarheid en lokale decodeerbaarheid, hoewel oppervlakkig vergelijkbaar, werkelijk op een fundamenteel niveau verschillen: het laatste is onmiskenbaar gemakkelijker te realiseren dan het eerste.

Kothari en Manohar hopen nu hun technieken uit te breiden om codes te bestuderen die meer dan drie zoekopdrachten mogen uitvoeren, aangezien er nu nog heel weinig over bekend is. En vooruitgang in de theorie van foutcorrectie heeft vaak implicaties op andere ogenschijnlijk niet-gerelateerde terreinen. Met name lokaal corrigeerbare codes zorgen overal voor verrassingen vanwege het probleem van zoekopdrachten in privédatabases in cryptografie tot bewijzen van stellingen in de combinatoriek. Het is nog te vroeg om te zeggen hoe de techniek van Kothari en Manohar deze verschillende vakgebieden zal beïnvloeden, maar onderzoekers zijn optimistisch.

“Er is hier een heel mooi nieuw idee,” zei Dvir. “Ik denk dat er veel potentieel is.”