Schema „magică” de corectare a erorilor sa dovedit ineficientă în mod inerent | Revista Quanta

Dacă ați trimis vreodată un mesaj text, ați redat un CD sau ați stocat un fișier în cloud, ați beneficiat de corectarea erorilor. Această idee revoluționară datează din anii 1940, când cercetătorii și-au dat seama pentru prima dată că este posibil să rescrieți orice mesaj într-o formă care să permită inversarea cu ușurință a corupției ulterioare.

De-a lungul anilor, cercetătorii au dezvoltat multe scheme ingenioase, numite coduri de corectare a erorilor, care codifică datele în moduri diferite și folosesc diferite proceduri pentru a remedia erorile. Dar pentru informaticienii teoreticieni, puțini sunt la fel de convingătoare ca așa-numitele coduri corectabile la nivel local. Aceste coduri au două proprietăți simultane care sună aproape contradictorii: orice eroare poate fi corectată prin citirea datelor codificate în doar câteva locuri, dar niciun atacator nu poate dejuta această procedură de corectare prin modificarea selectivă a codului. Este ca și cum ai putea recupera orice pagină ruptă dintr-o carte doar aruncând o privire la alte câteva.

„Este un fenomen destul de magic”, a spus Tom Gur, un informatician la Universitatea din Cambridge. „A priori, nu este evident că un astfel de obiect matematic ar putea exista deloc.”

Dar această magie are un cost mare. Singurele exemple cunoscute de coduri corectabile local sunt extrem de ineficiente - codificarea oricărui mesaj îl face, de asemenea, mai lung exponențial. Cărți întregi codificate în acest fel ar fi mult prea greoaie.

Informaticii s-au întrebat de mult dacă sunt posibile coduri mai corecte la nivel local. S-au concentrat în special pe codurile care folosesc doar trei interogări pentru a corecta orice eroare, în speranța că această restricție severă ar putea face aceste coduri mai ușor de înțeles. Dar chiar și acest caz simplu i-a uimit pe cercetători de peste 20 de ani.

Acum, informaticianul Pravesh Kothari de la Universitatea Carnegie Mellon și studentul său absolvent Peter Manohar au în sfârșit s-au dovedit că este imposibil să construiți un cod corectabil local cu trei interogări care să evite acest cost exponențial. Poate fi un rezultat negativ, dar orice clarifică limitele corectării erorilor este interesant pentru cercetători, mai ales pentru că matematica codurilor corectabile la nivel local apare în zone departe de comunicare.

„Acest rezultat este uimitor”, a spus Shubhangi Saraf, un informatician la Universitatea din Toronto. „Este o descoperire uriașă.”

Putere în numere

Pentru a înțelege corectarea erorilor, imaginați-vă datele pe care doriți să le protejați ca o secvență de biți sau 0 și 1. O eroare, în acest model, poate fi orice răsturnare nedorită a unui 0 într-un 1 sau invers, fie că se datorează unei fluctuații aleatorii sau unei modificări deliberate.

Să presupunem că doriți să trimiteți un mesaj unui prieten, dar vă îngrijorează că erorile ar putea schimba sensul. O strategie simplă este să înlocuiți fiecare 0 din mesajul dvs. cu 000 și fiecare 1 cu 111. Dacă prietenul dvs. vede o parte a mesajului care nu conține trei biți identici la rând, va ști că a apărut o eroare. Și dacă erorile sunt aleatorii și relativ rare, atunci orice șir de 110 este mult mai probabil să fie un 111 corupt decât un 000 corupt. Un vot cu majoritate simplă în fiecare triplet va fi suficient pentru a corecta majoritatea erorilor.

Această schemă, numită codul de repetiție, are virtutea simplității, dar puțin altceva de recomandat. În primul rând, necesită triplarea lungimii fiecărui mesaj doar pentru a face față erorilor relativ rare și, dacă există o șansă decentă pentru două erori adiacente, vom avea nevoie de și mai multă redundanță. Mai rău, devine rapid inutil dacă erorile nu sunt aleatorii, cum ar fi atunci când atacatorii încearcă în mod activ să saboteze codul. În codul de repetiție, toate informațiile necesare pentru a corecta un anumit bit sunt stocate în doar câțiva alți biți, lăsându-l vulnerabil la un atac țintit.

Din fericire, multe coduri de corectare a erorilor se descurcă mai bine. Un exemplu celebru, numit Codul Reed-Solomon, funcționează prin transformarea mesajelor în polinoame — expresii matematice precum x² + 3x + 2 care constau din diferiți termeni adăugați împreună, fiecare cu o variabilă (cum ar fi x) ridicat la o altă putere. Codificarea unui mesaj folosind un cod Reed-Solomon implică construirea unui polinom cu un termen pentru fiecare caracter din mesaj, apoi trasarea polinomului ca o curbă pe un grafic și stocarea coordonatele punctelor care se află pe curbă (luând cel puțin încă unul punct decât numărul de caractere). Erorile pot împinge câteva dintre aceste puncte de pe curbă, dar dacă nu există prea multe erori, o singură curbă polinomială va trece prin majoritatea punctelor. Acea curbă corespunde aproape sigur cu adevăratul mesaj.

Codurile Reed-Solomon sunt hipereficiente - trebuie doar să stocați câteva puncte suplimentare pentru a corecta erorile, astfel încât orice mesaj codificat este doar puțin mai lung decât originalul. De asemenea, sunt mai puțin vulnerabili la tipul de întrerupere direcționată care ar reprezenta un dezastru pentru codul de repetiție, deoarece informațiile folosite pentru a corecta o eroare oriunde sunt distribuite în întregul mesaj codificat.

Gândiți-vă la nivel global, acționați local

Puterea codului Reed-Solomon provine din interconectare. Dar tocmai din cauza acestei interconexiuni, nu există nicio modalitate de a remedia o singură eroare dintr-un mesaj codificat fără a citi totul. Este posibil să nu sune ca o problemă în contextul comunicării: dacă trimiteți un mesaj, probabil că doriți ca destinatarul să-l citească tot. Dar poate fi o răspundere în stocarea datelor - o altă aplicație majoră a corectării erorilor.

Luați în considerare o companie care stochează e-mailurile utilizatorilor în cloud, adică pe o gamă largă de servere. Vă puteți gândi la întreaga colecție de e-mailuri ca la un mesaj lung. Acum să presupunem că un server se blochează. Cu un cod Reed-Solomon, ar trebui să efectuați un calcul masiv care implică toate datele codificate pentru a vă recupera e-mailurile de pe acel server pierdut. „Ar trebui să te uiți la toate”, a spus Zeev Dvir, un informatician la Universitatea Princeton. „Ar putea fi miliarde și miliarde de e-mailuri – ar putea dura foarte mult.”

Cercetătorii folosesc termenul „local” pentru a descrie codurile care utilizează doar o fracțiune din mesajul codificat identifica erori sau corectează-le. Codul simplu de repetiție are ceva din acest caracter local, dar tocmai asta îl face atât de vulnerabil la manipulare. Un cod corectabil la nivel local, prin contrast, obține tot ce este mai bun din ambele lumi - poate corecta o eroare în orice bit cu doar câteva interogări, totul fără a pierde interconexiunea care face codurile Reed-Solomon atât de rezistente.

„Aceasta este o noțiune cu adevărat strictă”, a spus Kothari.

Cele mai faimoase exemple de coduri corectabile local sunt versiuni ale unui venerabil cod de corectare a erorilor inventat în 1954 de matematicieni. David Muller și Irving Reed (care a ajutat și la dezvoltarea codurilor Reed-Solomon). La fel ca codurile Reed-Solomon, codurile Reed-Muller folosesc polinoame cu mulți termeni adăugați împreună pentru a codifica mesaje lungi.

Polinoamele folosite în codurile Reed-Solomon implică o singură variabilă, x, deci singura modalitate de a adăuga mai mulți termeni este să folosești puteri mai mari ale x. Acest lucru are ca rezultat o curbă cu multe mișcări care pot fi fixate doar prin privire la multe puncte. Codurile Reed-Muller folosesc în schimb polinoame în care fiecare termen poate conține mai multe variabile înmulțite împreună. Mai multe variabile înseamnă mai multe moduri de a le combina, ceea ce, la rândul său, oferă o modalitate de a crește numărul de termeni polinomi fără a ridica vreo variabilă individuală la puteri atât de mari.

Codurile Reed-Muller sunt foarte flexibile. Puteți codifica mesaje mai lungi prin creșterea celei mai mari puteri care apare în polinom, creșterea numărului de variabile sau ambele. Pentru a face un cod Reed-Muller corectabil la nivel local, pur și simplu limitați puterea maximă a fiecărei variabile la o valoare constantă mică și gestionați mesajele mai lungi prin creșterea doar a numărului de variabile.

În special pentru un cod corectabil local cu trei interogări, acea putere maximă este setată la 2. Apoi, în ceea ce privește fiecare variabilă individuală, polinomul care codifică mesajul urmărește o parabolă simplă. Pentru a determina forma exactă a acelei parabole, trebuie doar să examinați curba în trei puncte. În plus, cu multe variabile există multe astfel de parabole, oricare dintre acestea poate fi folosită pentru a corecta erori. Acesta este ceea ce face ca codurile Reed-Muller să fie atât de rezistente.

Din păcate, codul Reed-Muller are un dezavantaj serios: numărul de biți necesari pentru codificarea unui mesaj crește exponențial odată cu numărul de variabile. Dacă doriți un cod foarte local care să corecteze erorile cu doar câteva interogări, veți avea nevoie de o mulțime de variabile pentru mesaje lungi, iar codul Reed-Muller va deveni rapid inutil în practică.

„Exonențial în acest caz este foarte rău”, a spus Dvir. Dar este inevitabil?

Corectabil sau decodabil?

Pe măsură ce oamenii de știință în computer au încercat și nu au reușit să găsească coduri mai eficiente corectabile la nivel local, au început să bănuiască că astfel de coduri nu sunt deloc posibile. În 2003, doi cercetători s-au dovedit că nu există nicio modalitate de a învinge codul Reed-Muller folosind doar două interogări. Dar asta e cât a ajuns oricine.

„Odată ce ajungi la trei, cunoștințele noastre devin foarte incomplete”, a spus Kothari.

Următoarea descoperire a complicat lucrurile și mai mult. În două lucrări publicate în 2008 și 2009, informaticienii Sergey Yekhanin și Klim Efremenko au arătat cum se construiesc coduri cu trei interogări care erau mai eficiente decât codurile Reed-Muller, dar aceste coduri nu erau corect corectabile local. În schimb, aveau o proprietate subtil diferită numită decodabilitate locală.

Pentru a înțelege diferența, să ne imaginăm din nou un furnizor de stocare în cloud care combină datele utilizatorilor într-un singur mesaj lung și le protejează folosind un cod de corectare a erorilor. Atât codurile corectabile local, cât și codurile decodificabile local pot corecta o eroare în orice bit al mesajului original cu doar câteva interogări.

Dar fiecare cod de corectare a erorilor necesită, de asemenea, biți suplimentari care nu erau în mesajul original - de aceea codificarea unui mesaj îl face mai lung. Cele două tipuri de coduri diferă în modul în care tratează acești biți suplimentari. Codurile decodabile local nu fac nicio promisiune cu privire la numărul de interogări necesare pentru a corecta erorile din acești biți. Dar într-un cod corectabil local, o eroare în oricare dintre biții suplimentari poate fi remediată exact în același mod ca o eroare în orice bit al mesajului original.

„Tot ceea ce stocați, fie că este vorba despre datele originale ale utilizatorilor sau despre redundanță și informații despre verificare – toate acestea pot fi corectate local”, a spus Madhu Sudan, un informatician la Universitatea Harvard.

Deși diferite în principiu, corectabilitatea locală și decodabilitatea locală păreau întotdeauna interschimbabile în practică înainte de 2008 - fiecare cod decodabil local cunoscut era, de asemenea, corectabil la nivel local. Descoperirea lui Yekhanin și Efremenko a ridicat posibilitatea unei diferențe fundamentale între cele două condiții. Sau poate că a fost posibil să se modifice codurile lui Yekhanin și Efremenko pentru a le face corectabile la nivel local. Acest lucru ar pune cele două condiții pe picior de egalitate încă o dată, dar ar însemna, de asemenea, că cercetătorii s-au înșelat cu privire la cât de eficiente ar putea deveni codurile corectabile la nivel local cu trei interogări. În orice caz, înțelepciunea convențională ar trebui să se schimbe.

Logica de împrumut

Kothari și Manohar au rezolvat în cele din urmă această tensiune adaptând o tehnică dintr-un domeniu diferit al informaticii: studiul așa-numitelor probleme de satisfacție a constrângerilor. Încercarea de a coordona planurile de cină cu un grup de prieteni este un fel de problemă de satisfacție. Toată lumea are opțiuni pe care le va accepta și alegeri cărora le va opune. Treaba ta este fie să găsești un plan care să mulțumească pe toată lumea, fie, dacă nu există un astfel de plan, să-ți dai seama cât mai curând posibil.

Există o asimetrie inerentă între aceste două rezultate posibile. O soluție acceptabilă poate să nu fie ușor de găsit, dar odată ce o ai, este ușor să convingi pe oricine altcineva că va funcționa. Dar chiar dacă știi că problema este într-adevăr „nesatisfăcătoare”, este posibil să nu existe un exemplu care să ofere dovezi.

În 2021, Kothari și Manohar, împreună cu Venkatesan Guruswami de la Universitatea din California, Berkeley, au făcut o descoperire majoră în studiul problemelor de satisfacție a constrângerilor folosind o nouă tehnică teoretică pentru identificarea acelor cazuri dificile nesatisfăcătoare. Ei au bănuit că noua metodă va fi un instrument puternic pentru rezolvarea altor probleme, iar studentul absolvent al lui Guruswami, Omar Alrabiah, le-a sugerat să se uite la coduri decodabile local cu trei interogări.

„Acesta a fost un cui cu un ciocan în mână, ca să spunem așa”, a spus Kothari.

Rezultatele surprinzătoare ale lui Yekhanin și Efremenko au arătat că codurile decodabile local cu trei interogări ar putea fi mai eficiente decât codurile Reed-Muller. Dar codurile lor erau cele mai bune posibile sau codurile decodabile local cu trei interogări ar putea deveni și mai eficiente? Kothari, Manohar, Guruswami și Alrabiah au crezut că noua lor tehnică ar putea fi capabilă să demonstreze limitele cât de eficiente ar putea deveni astfel de coduri. Planul lor a fost să construiască o formulă logică care să cuprindă structura tuturor codurilor decodabile local cu trei interogări posibile de o dimensiune dată și să demonstreze că este nesatisfăcătoare, arătând astfel că un astfel de cod nu ar putea exista.

Cei patru cercetători au făcut un prim pas în această direcție în 2022, stabilind a nouă limită privind eficiența maximă a codurilor decodabile local cu trei interogări. Rezultatul a depășit cu mult ceea ce cercetătorii au fost capabili să obțină cu alte tehnici, dar nu a exclus toate codurile mai eficiente decât cele ale lui Yekhanin și Efremenko.

Kothari și Manohar bănuiau că ar putea merge mai departe. Dar progresul s-a blocat până când Manohar a notat un calcul rapid din spatele plicului care indică faptul că tehnica ar putea funcționa și mai bine pentru codurile corectabile la nivel local decât pentru cele decodabile local.

Câteva luni mai târziu, după multe alte porniri false care i-au făcut să se teamă că au fost prea optimiști, tehnica și-a îndeplinit în sfârșit promisiunea. Kothari și Manohar au demonstrat că, așa cum bănuiseră cercetătorii, este imposibil ca orice cod corectabil local cu trei interogări să funcționeze considerabil mai bine decât codurile Reed-Muller. Acea scalare exponențială este o limitare fundamentală. Rezultatul lor a fost, de asemenea, o demonstrație dramatică că corectabilitatea locală și decodabilitatea locală, deși superficial similare, diferă într-adevăr la un nivel fundamental: cea din urmă este fără echivoc mai ușor de realizat decât prima.

Kothari și Manohar speră acum să-și extindă tehnicile pentru a studia codurile cărora li se permite să facă mai mult de trei interogări, deoarece se cunosc foarte puține lucruri despre ele acum. Iar progresul în teoria corectării erorilor are adesea implicații în alte domenii aparent fără legătură. În special, codurile corectabile la nivel local fac apariții surprinzătoare peste tot din problema de căutări private în baze de date în criptografie la dovezi de teoreme în combinatorică. Este prea devreme să spunem cum va afecta tehnica lui Kothari și Manohar aceste domenii diferite, dar cercetătorii se simt optimiști.

„Există o idee nouă foarte frumoasă aici”, a spus Dvir. „Cred că există mult potențial.”