„Magisches“ Fehlerkorrekturschema erwies sich als von Natur aus ineffizient | Quanta-Magazin

Wenn Sie jemals eine Textnachricht gesendet, eine CD abgespielt oder eine Datei in der Cloud gespeichert haben, haben Sie von der Fehlerkorrektur profitiert. Diese revolutionäre Idee geht auf die 1940er Jahre zurück, als Forscher erstmals erkannten, dass es möglich ist, jede Nachricht in einer Form umzuschreiben, die es ermöglicht, spätere Korruption leicht rückgängig zu machen.

Im Laufe der Jahre haben Forscher viele ausgeklügelte Schemata, sogenannte Fehlerkorrekturcodes, entwickelt, die Daten auf unterschiedliche Weise kodieren und unterschiedliche Verfahren zur Fehlerbeseitigung verwenden. Für theoretische Informatiker sind jedoch nur wenige so überzeugend wie sogenannte lokal korrigierbare Codes. Diese Codes haben gleichzeitig zwei Eigenschaften, die fast widersprüchlich klingen: Jeder Fehler kann durch das Auslesen der verschlüsselten Daten an nur wenigen Stellen korrigiert werden, doch kein Angreifer kann diesen Korrekturvorgang durch gezielte Manipulation des Codes verhindern. Es ist, als ob man jede aus einem Buch herausgerissene Seite durch einen Blick auf ein paar andere wiederfinden könnte.

„Es ist ein ziemlich magisches Phänomen“, sagte er Tom Gur, Informatiker an der Universität Cambridge. „A priori ist es nicht offensichtlich, dass ein solches mathematisches Objekt überhaupt existieren könnte.“

Doch diese Magie hat ihren Preis. Die einzigen bekannten Beispiele für lokal korrigierbare Codes sind äußerst ineffizient – ​​die Codierung einer Nachricht verlängert diese auch exponentiell. Ganze Bücher, die so kodiert wären, wären viel zu unhandlich.

Informatiker fragen sich schon lange, ob bessere lokal korrigierbare Codes möglich sind. Sie haben sich insbesondere auf Codes konzentriert, die nur drei Abfragen zur Korrektur eines Fehlers verwenden, in der Hoffnung, dass diese strenge Einschränkung das Verständnis dieser Codes erleichtern könnte. Aber selbst dieser einfache Fall hat die Forscher über 20 Jahre lang verblüfft.

Jetzt der Informatiker Pravesh Kothari der Carnegie Mellon University und sein Doktorand Peter Manohar habe endlich erwies sich dass es unmöglich ist, einen lokal korrigierbaren Code mit drei Abfragen zu erstellen, der diese exponentiellen Kosten vermeidet. Es mag ein negatives Ergebnis sein, aber alles, was die Grenzen der Fehlerkorrektur verdeutlicht, ist für Forscher spannend, insbesondere weil die Mathematik lokal korrigierbarer Codes in Bereichen auftaucht, die weit von der Kommunikation entfernt sind.

„Dieses Ergebnis ist erstaunlich“, sagte er Shubhangi Saraf, Informatiker an der University of Toronto. „Es ist ein großer Durchbruch.“

Strength in Numbers

Um die Fehlerkorrektur zu verstehen, stellen Sie sich die Daten, die Sie schützen möchten, als eine Folge von Bits oder Nullen und Einsen vor. Ein Fehler kann in diesem Modell jedes unerwünschte Umdrehen einer 0 in eine 1 oder umgekehrt sein, unabhängig davon, ob dies auf eine zufällige Schwankung oder eine absichtliche Manipulation zurückzuführen ist.

Angenommen, Sie möchten einem Freund eine Nachricht senden, befürchten jedoch, dass Fehler die Bedeutung ändern könnten. Eine einfache Strategie besteht darin, jede 0 in Ihrer Nachricht durch 000 und jede 1 durch 111 zu ersetzen. Wenn Ihr Freund einen Teil der Nachricht sieht, der nicht drei identische Bits hintereinander enthält, weiß er, dass ein Fehler aufgetreten ist. Und wenn Fehler zufällig und relativ selten sind, ist es viel wahrscheinlicher, dass es sich bei jeder Folge von 110 um eine fehlerhafte 111 als um eine fehlerhafte 000 handelt. Eine einfache Mehrheitsentscheidung innerhalb jedes Tripletts reicht aus, um die meisten Fehler zu korrigieren.

Dieses Schema, Wiederholungscode genannt, zeichnet sich durch seine Einfachheit aus, es gibt aber kaum andere Gründe, die es empfehlen. Zum einen ist es erforderlich, die Länge jeder Nachricht zu verdreifachen, nur um relativ seltene Fehler zu bewältigen, und wenn die Wahrscheinlichkeit zweier benachbarter Fehler groß ist, benötigen wir noch mehr Redundanz. Schlimmer noch: Es wird schnell nutzlos, wenn Fehler nicht zufällig auftreten, beispielsweise wenn Angreifer aktiv versuchen, den Code zu sabotieren. Im Wiederholungscode sind alle zur Korrektur eines bestimmten Bits erforderlichen Informationen in nur wenigen anderen Bits gespeichert, sodass er für einen gezielten Angriff anfällig ist.

Glücklicherweise schneiden viele Fehlerkorrekturcodes besser ab. Ein berühmtes Beispiel namens Reed-Solomon-Codefunktioniert durch die Umwandlung von Nachrichten in Polynome – mathematische Ausdrücke wie x² + 3x + 2, die aus verschiedenen addierten Begriffen bestehen, jeweils mit einer Variablen (z. B x) in eine andere Potenz erhoben. Das Codieren einer Nachricht mithilfe eines Reed-Solomon-Codes umfasst die Erstellung eines Polynoms mit einem Term für jedes Zeichen in der Nachricht, das anschließende Zeichnen des Polynoms als Kurve in einem Diagramm und das Speichern der Koordinaten von Punkten, die auf der Kurve liegen (wobei mindestens ein weiteres verwendet wird). Punkt als die Anzahl der Zeichen). Durch Fehler können einige dieser Punkte aus der Kurve verschoben werden, aber wenn es nicht zu viele Fehler gibt, verläuft nur eine Polynomkurve durch die meisten Punkte. Diese Kurve entspricht mit ziemlicher Sicherheit der wahren Botschaft.

Reed-Solomon-Codes sind überaus effizient – ​​Sie müssen nur ein paar zusätzliche Punkte speichern, um Fehler zu korrigieren, sodass jede codierte Nachricht nur unwesentlich länger ist als das Original. Sie sind auch weniger anfällig für gezielte Störungen, die für den Wiederholungscode eine Katastrophe bedeuten würden, da die Informationen, die zur Korrektur eines Fehlers an einer beliebigen Stelle verwendet werden, über die gesamte codierte Nachricht verteilt sind.

Denke global, handle lokal

Die Stärke des Reed-Solomon-Codes beruht auf der Vernetzung. Aber gerade aufgrund dieser Vernetzung gibt es keine Möglichkeit, einen einzelnen Fehler in einer verschlüsselten Nachricht zu beheben, ohne die gesamte Nachricht zu lesen. Im Kontext der Kommunikation scheint das kein Problem zu sein: Wenn Sie eine Nachricht senden, möchten Sie wahrscheinlich, dass der Empfänger sie vollständig liest. Aber es kann eine Belastung bei der Datenspeicherung sein – eine weitere wichtige Anwendung der Fehlerkorrektur.

Stellen Sie sich ein Unternehmen vor, das die E-Mails der Benutzer in der Cloud speichert – also auf einer Vielzahl von Servern. Sie können sich die gesamte E-Mail-Sammlung als eine einzige lange Nachricht vorstellen. Angenommen, ein Server stürzt ab. Mit einem Reed-Solomon-Code müssten Sie eine umfangreiche Berechnung aller verschlüsselten Daten durchführen, um Ihre E-Mails von diesem einen verlorenen Server wiederherzustellen. „Man müsste sich alles anschauen“, sagte er Zeev Dvir, Informatiker an der Princeton University. „Das könnten Milliarden und Abermilliarden E-Mails sein – es könnte wirklich lange dauern.“

Forscher verwenden den Begriff „lokal“, um Codes zu beschreiben, die nur einen Bruchteil der codierten Nachricht nutzen Fehler erkennen oder korrigieren Sie sie. Der einfache Wiederholungscode hat etwas von diesem lokalen Charakter, aber gerade das macht ihn so anfällig für Manipulationen. Im Gegensatz dazu bietet ein lokal korrigierbarer Code das Beste aus beiden Welten: Er kann einen Fehler in jedem Bit mit nur wenigen Abfragen korrigieren, ohne die Vernetzung zu verlieren, die Reed-Solomon-Codes so widerstandsfähig macht.

„Das ist eine wirklich strenge Vorstellung“, sagte Kothari.

Die bekanntesten Beispiele für lokal korrigierbare Codes sind Versionen eines ehrwürdigen Fehlerkorrekturcodes, der 1954 von Mathematikern erfunden wurde David Müller und Irving Reed (der auch an der Entwicklung der Reed-Solomon-Codes beteiligt war). Wie Reed-Solomon-Codes verwenden Reed-Muller-Codes Polynome mit vielen addierten Termen, um lange Nachrichten zu kodieren.

Die in Reed-Solomon-Codes verwendeten Polynome umfassen eine einzelne Variable, xDaher besteht die einzige Möglichkeit, weitere Begriffe hinzuzufügen, darin, höhere Potenzen von zu verwenden x. Dies führt zu einer Kurve mit vielen Schwankungen, die nur durch Betrachtung vieler Punkte bestimmt werden können. Reed-Muller-Codes verwenden stattdessen Polynome, bei denen jeder Term mehrere miteinander multiplizierte Variablen enthalten kann. Mehr Variablen bedeuten mehr Möglichkeiten, sie zu kombinieren, was wiederum eine Möglichkeit bietet, die Anzahl der Polynomterme zu erhöhen, ohne eine einzelne Variable auf solch hohe Potenzen zu erhöhen.

Reed-Muller-Codes sind sehr flexibel. Sie können längere Nachrichten kodieren, indem Sie die höchste im Polynom vorkommende Potenz erhöhen, die Anzahl der Variablen erhöhen oder beides. Um einen Reed-Muller-Code lokal korrigierbar zu machen, begrenzen Sie einfach die maximale Leistung jeder Variablen auf einen kleinen konstanten Wert und verarbeiten längere Nachrichten, indem Sie nur die Anzahl der Variablen erhöhen.

Insbesondere für einen lokal korrigierbaren Code mit drei Abfragen wird diese maximale Leistung auf 2 festgelegt. Was jede einzelne Variable betrifft, zeichnet das Polynom, das die Nachricht kodiert, eine einfache Parabel nach. Um die genaue Form dieser Parabel zu bestimmen, müssen Sie die Kurve nur an drei Punkten untersuchen. Darüber hinaus gibt es bei vielen Variablen viele solcher Parabeln, von denen jede zur Korrektur von Fehlern verwendet werden kann. Das macht Reed-Muller-Codes so widerstandsfähig.

Leider hat der Reed-Muller-Code einen gravierenden Nachteil: Die Anzahl der zum Kodieren einer Nachricht erforderlichen Bits steigt exponentiell mit der Anzahl der Variablen. Wenn Sie einen hochlokalen Code wünschen, der Fehler mit nur wenigen Abfragen korrigiert, benötigen Sie für lange Nachrichten viele Variablen, und der Reed-Muller-Code wird in der Praxis schnell unbrauchbar.

„Exponentiell ist in diesem Fall sehr schlecht“, sagte Dvir. Aber ist es unvermeidlich?

Korrigierbar oder dekodierbar?

Als Informatiker erfolglos versuchten, effizientere lokal korrigierbare Codes zu finden, begannen sie zu vermuten, dass solche Codes überhaupt nicht möglich seien. Im Jahr 2003 zwei Forscher erwies sich dass es keine Möglichkeit gibt, den Reed-Muller-Code mit nur zwei Abfragen zu schlagen. Aber das ist alles, was irgendjemand sagen kann.

„Sobald man bei drei angelangt ist, wird unser Wissen sehr dürftig“, sagte Kothari.

Der nächste Durchbruch machte die Sache nur noch komplizierter. In zwei Artikeln veröffentlicht in 2008 und 2009Die Informatiker Sergey Yekhanin und Klim Efremenko zeigten, wie man Drei-Abfrage-Codes konstruiert, die effizienter als Reed-Muller-Codes waren, aber diese Codes waren nicht ganz lokal korrigierbar. Stattdessen verfügten sie über eine subtil andere Eigenschaft namens lokale Dekodierbarkeit.

Um den Unterschied zu verstehen, stellen wir uns noch einmal einen Cloud-Speicheranbieter vor, der Benutzerdaten in einer langen Nachricht zusammenfasst und diese mithilfe eines Fehlerkorrekturcodes schützt. Sowohl lokal korrigierbare Codes als auch lokal dekodierbare Codes können mit nur wenigen Abfragen einen Fehler in jedem Teil der ursprünglichen Nachricht korrigieren.

Aber jeder Fehlerkorrekturcode erfordert auch zusätzliche Bits, die nicht in der ursprünglichen Nachricht enthalten waren – deshalb wird eine Nachricht durch die Codierung länger. Die beiden Arten von Codes unterscheiden sich darin, wie sie diese zusätzlichen Bits behandeln. Lokal dekodierbare Codes machen keine Zusagen über die Anzahl der Abfragen, die zur Korrektur von Fehlern in diesen Bits erforderlich sind. Aber in einem lokal korrigierbaren Code kann ein Fehler in einem der zusätzlichen Bits auf genau die gleiche Weise behoben werden wie ein Fehler in einem beliebigen Bit der ursprünglichen Nachricht.

„Alles, was Sie speichern, ob es sich um die Originaldaten der Benutzer oder die Redundanz- und Prüfinformationen handelt – all dies kann lokal korrigiert werden“, sagte er Madhu Sudan, Informatiker an der Harvard University.

Obwohl prinzipiell unterschiedlich, schienen lokale Korrigierbarkeit und lokale Dekodierbarkeit vor 2008 in der Praxis immer austauschbar zu sein – jeder bekannte lokal dekodierbare Code war auch lokal korrigierbar. Die Entdeckung von Jechanin und Efremenko ließ die Möglichkeit eines grundlegenden Unterschieds zwischen den beiden Bedingungen erkennen. Oder vielleicht war es möglich, die Codes von Jechanin und Efremenko zu modifizieren, um sie lokal korrigierbar zu machen. Das würde die beiden Bedingungen wieder auf Augenhöhe bringen, aber es würde auch bedeuten, dass sich die Forscher darüber geirrt hätten, wie effizient lokal korrigierbare Codes mit drei Abfragen sein könnten. In jedem Fall müsste sich die herkömmliche Meinung ändern.

Logik ausleihen

Kothari und Manohar lösten diese Spannung schließlich, indem sie eine Technik aus einem anderen Bereich der Informatik adaptierten: die Untersuchung sogenannter Constraint Satisfaction Problems. Der Versuch, Pläne für ein Abendessen mit einer Gruppe von Freunden zu koordinieren, ist eine Art Problem mit der Befriedigung von Zwängen. Jeder hat Entscheidungen, die er akzeptiert, und Entscheidungen, gegen die er sein Veto einlegt. Ihre Aufgabe besteht darin, entweder einen Plan zu finden, der alle zufriedenstellt, oder, falls es keinen solchen Plan gibt, ihn so schnell wie möglich herauszufinden.

Zwischen diesen beiden möglichen Ergebnissen besteht eine inhärente Asymmetrie. Eine akzeptable Lösung ist vielleicht nicht leicht zu finden, aber wenn man sie erst einmal hat, ist es einfach, andere davon zu überzeugen, dass sie funktionieren wird. Aber selbst wenn Sie wissen, dass das Problem wirklich „unlösbar“ ist, gibt es möglicherweise kein Beispiel, das den Beweis liefert.

Im Jahr 2021 machten Kothari und Manohar zusammen mit Venkatesan Guruswami von der University of California, Berkeley, einen großer Durchbruch bei der Untersuchung von Constraint Satisfaction-Problemen unter Verwendung einer neuen theoretischen Technik zur Identifizierung dieser kniffligen unerfüllbaren Fälle. Sie vermuteten, dass die neue Methode auch ein leistungsstarkes Werkzeug zur Lösung anderer Probleme sein würde, und Guruswamis Doktorand Omar Alrabiah schlug vor, sich mit lokal dekodierbaren Codes mit drei Abfragen zu befassen.

„Das war sozusagen ein Nagel mit einem Hammer in unserer Hand“, sagte Kothari.

Die überraschenden Ergebnisse von Jechanin und Efremenko hatten gezeigt, dass lokal dekodierbare Codes mit drei Abfragen effizienter sein könnten als Reed-Muller-Codes. Aber waren ihre Codes die bestmöglichen oder könnten lokal dekodierbare Codes mit drei Abfragen noch effizienter werden? Kothari, Manohar, Guruswami und Alrabiah glaubten, dass ihre neue Technik möglicherweise die Grenzen der Effizienz solcher Codes aufzeigen könnte. Ihr Plan bestand darin, eine logische Formel zu erstellen, die die Struktur aller möglichen lokal dekodierbaren Drei-Abfragen-Codes einer bestimmten Größe umfasst, diese als unerfüllbar zu beweisen und so zu zeigen, dass kein solcher Code existieren konnte.

Einen ersten Schritt in diese Richtung machten die vier Forscher im Jahr 2022 und setzten einen neue Grenze über die maximale Effizienz von lokal dekodierbaren Codes mit drei Abfragen. Das Ergebnis ging weit über das hinaus, was Forscher mit anderen Techniken erreichen konnten, schloss jedoch nicht aus, dass alle Codes effizienter sind als die von Jechanin und Efremenko.

Kothari und Manohar vermuteten, dass sie noch weiter gehen könnten. Der Fortschritt geriet jedoch ins Stocken, bis Manohar eine kurze Kurzberechnung aufstellte, die darauf hindeutete, dass die Technik bei lokal korrigierbaren Codes möglicherweise noch besser funktioniert als bei lokal dekodierbaren Codes.

Ein paar Monate später, nach vielen weiteren Fehlstarts, die sie befürchten ließen, zu optimistisch gewesen zu sein, löste die Technik schließlich ihr Versprechen ein. Kothari und Manohar haben bewiesen, dass es, wie die Forscher vermutet hatten, unmöglich ist, dass ein lokal korrigierbarer Code mit drei Abfragen wesentlich besser funktioniert als Reed-Muller-Codes. Diese exponentielle Skalierung ist eine grundlegende Einschränkung. Ihr Ergebnis war auch ein dramatischer Beweis dafür, dass lokale Korrigierbarkeit und lokale Dekodierbarkeit, obwohl sie oberflächlich betrachtet ähnlich sind, sich tatsächlich auf einer grundlegenden Ebene unterscheiden: Letzteres ist eindeutig einfacher zu realisieren als Ersteres.

Kothari und Manohar hoffen nun, ihre Techniken auf die Untersuchung von Codes auszuweiten, die mehr als drei Abfragen durchführen dürfen, da derzeit nur sehr wenig über sie bekannt ist. Und Fortschritte in der Theorie der Fehlerkorrektur haben oft Auswirkungen auf andere scheinbar unabhängige Bereiche. Insbesondere lokal korrigierbare Codes tauchen überall überraschend auf Suche in privaten Datenbanken in der Kryptographie zu Beweisen von Sätze in der Kombinatorik. Es ist noch zu früh, um zu sagen, wie sich die Technik von Kothari und Manohar auf diese verschiedenen Bereiche auswirken wird, aber die Forscher sind optimistisch.

„Das ist eine wirklich schöne neue Idee“, sagte Dvir. „Ich denke, es gibt viel Potenzial.“