Lo schema “magico” di correzione degli errori si è rivelato intrinsecamente inefficiente | Rivista Quanti

Se hai mai inviato un messaggio di testo, riprodotto un CD o archiviato un file nel cloud, hai beneficiato della correzione degli errori. Questa idea rivoluzionaria risale agli anni ’1940, quando i ricercatori si resero conto per la prima volta che era possibile riscrivere qualsiasi messaggio in una forma che consentisse di invertire facilmente la successiva corruzione.

Nel corso degli anni, i ricercatori hanno sviluppato molti schemi ingegnosi, chiamati codici di correzione degli errori, che codificano i dati in modi diversi e utilizzano procedure diverse per correggere gli errori. Ma per gli informatici teorici, pochi sono convincenti quanto i cosiddetti codici correggibili localmente. Questi codici hanno due proprietà simultanee che sembrano quasi contraddittorie: qualsiasi errore può essere corretto leggendo i dati codificati solo in pochi punti, ma nessun utente malintenzionato può ostacolare questa procedura di correzione manomettendo selettivamente il codice. È come se potessi recuperare qualsiasi pagina strappata da un libro semplicemente dando un’occhiata ad alcune altre.

“È un fenomeno piuttosto magico”, ha detto Tom Gur, uno scienziato informatico presso l'Università di Cambridge. "A priori, non è affatto ovvio che un simile oggetto matematico possa esistere."

Ma questa magia ha un costo elevato. Gli unici esempi conosciuti di codici correggibili localmente sono estremamente inefficienti: codificare qualsiasi messaggio lo rende anche esponenzialmente più lungo. Interi libri codificati in questo modo sarebbero troppo ingombranti.

Gli informatici si chiedono da tempo se siano possibili codici migliori correggibili localmente. Si sono concentrati soprattutto sui codici che utilizzano solo tre query per correggere eventuali errori, sperando che questa grave restrizione possa rendere questi codici più facili da comprendere. Ma anche questo semplice caso ha sconcertato i ricercatori per oltre 20 anni.

Ora l'informatico Pravesh Kothari della Carnegie Mellon University e il suo studente laureato Pietro Manohar finalmente dimostrato che è impossibile creare un codice a tre query correggibile localmente che eviti quel costo esponenziale. Potrebbe essere un risultato negativo, ma qualsiasi cosa che chiarisca i limiti della correzione degli errori è entusiasmante per i ricercatori, soprattutto perché la matematica dei codici correggibili localmente emerge in aree lontane dalla comunicazione.

"Questo risultato è sorprendente", ha detto Shubhangi Saraf, uno scienziato informatico presso l'Università di Toronto. “È un enorme passo avanti”.

Forza nei numeri

Per comprendere la correzione degli errori, immagina i dati che desideri proteggere come una sequenza di bit, o 0 e 1. Un errore, in questo modello, può essere qualsiasi capovolgimento indesiderato di uno 0 in un 1 o viceversa, sia che sia dovuto a una fluttuazione casuale o a una manomissione intenzionale.

Supponiamo che tu voglia inviare un messaggio a un amico, ma temi che gli errori possano cambiarne il significato. Una strategia semplice è sostituire ogni 0 nel messaggio con 000 e ogni 1 con 111. Se il tuo amico vede una parte del messaggio che non contiene tre bit identici di seguito, saprà che si è verificato un errore. E se gli errori sono casuali e relativamente rari, allora è molto più probabile che qualsiasi stringa di 110 sia un 111 corrotto che uno 000 corrotto. Un voto a maggioranza semplice all'interno di ciascuna tripletta sarà sufficiente per correggere la maggior parte degli errori.

Questo schema, chiamato codice di ripetizione, ha il pregio della semplicità, ma poco altro lo consiglia. Per prima cosa, è necessario triplicare la lunghezza di ogni messaggio solo per gestire errori relativamente poco frequenti, e se c’è una discreta possibilità che si verifichino due errori adiacenti, avremo bisogno di una ridondanza ancora maggiore. Peggio ancora, diventa rapidamente inutile se gli errori non sono casuali, come quando gli aggressori tentano attivamente di sabotare il codice. Nel codice di ripetizione, tutte le informazioni necessarie per correggere un dato bit vengono archiviate in pochi altri bit, rendendolo vulnerabile a un attacco mirato.

Fortunatamente, molti codici di correzione degli errori funzionano meglio. Un famoso esempio, chiamato il Codice Reed-Solomon, funziona trasformando i messaggi in polinomi - espressioni matematiche come x² + 3x + 2 che consistono in termini diversi sommati insieme, ciascuno con una variabile (come x) elevato a potenza diversa. Codificare un messaggio utilizzando un codice Reed-Solomon implica costruire un polinomio con un termine per ciascun carattere del messaggio, quindi tracciare il polinomio come una curva su un grafico e memorizzare le coordinate dei punti che giacciono sulla curva (prendendone almeno un altro). punto rispetto al numero di caratteri). Gli errori potrebbero spostare alcuni di questi punti fuori dalla curva, ma se non ci sono troppi errori, solo una curva polinomiale passerà attraverso la maggior parte dei punti. Quella curva quasi certamente corrisponde al vero messaggio.

I codici Reed-Solomon sono iperefficienti: devi solo memorizzare alcuni punti extra per correggere gli errori, quindi qualsiasi messaggio codificato è solo leggermente più lungo dell'originale. Sono anche meno vulnerabili al tipo di interruzione mirata che comporterebbe un disastro per il codice di ripetizione, perché le informazioni utilizzate per correggere un errore ovunque sono distribuite nell’intero messaggio codificato.

Pensa globalmente agisci localmente

La forza del codice Reed-Solomon deriva dall'interconnessione. Ma proprio a causa di questa interconnessione, non c’è modo di correggere un singolo errore in un messaggio codificato senza leggerlo tutto. Ciò potrebbe non sembrare un problema nel contesto della comunicazione: se stai inviando un messaggio, probabilmente desideri che il destinatario lo legga tutto. Ma può rappresentare un ostacolo nell’archiviazione dei dati, un’altra importante applicazione della correzione degli errori.

Considera un'azienda che archivia le e-mail degli utenti nel cloud, ovvero su una vasta gamma di server. Puoi pensare all'intera raccolta di e-mail come a un lungo messaggio. Supponiamo ora che un server si blocchi. Con un codice Reed-Solomon, dovresti eseguire un calcolo massiccio che coinvolge tutti i dati codificati per recuperare le tue e-mail da quel server perduto. “Dovresti guardare tutto”, ha detto Zeev Dvir, uno scienziato informatico dell'Università di Princeton. "Potrebbero essere miliardi e miliardi di e-mail: potrebbe richiedere molto tempo."

I ricercatori usano il termine “locale” per descrivere codici che utilizzano solo una frazione del messaggio codificato individuare errori o correggerli. Il codice a ripetizione semplice ha qualcosa di questo carattere locale, ma è proprio questo che lo rende così vulnerabile alle manomissioni. Un codice correggibile localmente, al contrario, ottiene il meglio da entrambi i mondi: può correggere un errore in qualsiasi bit con solo poche query, il tutto senza perdere l'interconnessione che rende i codici Reed-Solomon così resilienti.

"Questa è una nozione davvero rigorosa", ha detto Kothari.

Gli esempi più famosi di codici correggibili localmente sono versioni di un venerabile codice di correzione degli errori inventato nel 1954 dai matematici David Müller ed Irving Reed (che ha anche contribuito a sviluppare i codici Reed-Solomon). Come i codici Reed-Solomon, i codici Reed-Muller utilizzano polinomi con molti termini aggiunti insieme per codificare messaggi lunghi.

I polinomi utilizzati nei codici Reed-Solomon coinvolgono una singola variabile, x, quindi l'unico modo per aggiungere più termini è utilizzare potenze di x. Ciò si traduce in una curva con molte oscillazioni che può essere definita solo osservando molti punti. I codici Reed-Muller utilizzano invece polinomi in cui ogni termine può contenere più variabili moltiplicate insieme. Più variabili significano più modi per combinarle, il che a sua volta offre un modo per aumentare il numero di termini polinomiali senza elevare alcuna variabile individuale a potenze così elevate.

I codici Reed-Muller sono molto flessibili. Puoi codificare messaggi più lunghi aumentando la potenza massima che appare nel polinomio, aumentando il numero di variabili o entrambi. Per rendere un codice Reed-Muller correggibile localmente, è sufficiente limitare la potenza massima di ciascuna variabile a un valore costante piccolo e gestire messaggi più lunghi aumentando solo il numero di variabili.

Nello specifico, per un codice correggibile localmente a tre query, la potenza massima è fissata a 2. Quindi, per quanto riguarda ogni singola variabile, il polinomio che codifica il messaggio traccia una semplice parabola. Per determinare la forma esatta di quella parabola, devi solo esaminare la curva in tre punti. Inoltre, con molte variabili esistono molte parabole di questo tipo, ognuna delle quali può essere utilizzata per correggere gli errori. Questo è ciò che rende i codici Reed-Muller così resilienti.

Sfortunatamente, il codice Reed-Muller presenta un grave inconveniente: il numero di bit richiesti per codificare un messaggio aumenta esponenzialmente con il numero di variabili. Se desideri un codice altamente locale che corregga gli errori con solo una manciata di query, avrai bisogno di molte variabili per messaggi lunghi e il codice Reed-Muller diventerà rapidamente inutile nella pratica.

“L’esponenziale in questo caso è pessimo”, ha detto Dvir. Ma è inevitabile?

Correggibile o decodificabile?

Mentre gli informatici tentavano, senza riuscirci, di trovare codici più efficienti correggibili localmente, cominciarono a sospettare che tali codici non fossero affatto possibili. Nel 2003, due ricercatori dimostrato che non c'è modo di battere il codice Reed-Muller usando solo due query. Ma questo è quanto si è ottenuto.

"Una volta arrivati ​​a tre, la nostra conoscenza diventa molto approssimativa", ha detto Kothari.

La svolta successiva non fece altro che complicare ulteriormente le cose. In due articoli pubblicati in 2008 ed 2009, gli scienziati informatici Sergey Yekhanin e Klim Efremenko hanno mostrato come costruire codici a tre query che erano più efficienti dei codici Reed-Muller, ma questi codici non erano correggibili del tutto localmente. Avevano invece una proprietà leggermente diversa chiamata decodificabilità locale.

Per comprendere la differenza, immaginiamo ancora una volta un provider di archiviazione cloud che combini i dati degli utenti in un unico lungo messaggio e li protegga utilizzando un codice di correzione degli errori. Sia i codici correggibili localmente che i codici decodificabili localmente possono correggere un errore in qualsiasi parte del messaggio originale con poche query.

Ma ogni codice di correzione degli errori richiede anche bit aggiuntivi che non erano nel messaggio originale: ecco perché la codifica di un messaggio lo rende più lungo. I due tipi di codici differiscono nel modo in cui trattano questi bit aggiuntivi. I codici decodificabili localmente non fanno promesse sul numero di query necessarie per correggere gli errori in questi bit. Ma in un codice correggibile localmente, un errore in uno qualsiasi dei bit aggiuntivi può essere corretto esattamente nello stesso modo di un errore in qualsiasi bit del messaggio originale.

"Tutto ciò che archivi, che si tratti dei dati originali degli utenti o della ridondanza e delle informazioni di controllo, tutto questo può essere corretto localmente", ha affermato Madhu Sudan, uno scienziato informatico dell'Università di Harvard.

Sebbene diverse in linea di principio, la correggibilità locale e la decodificabilità locale sono sempre sembrate intercambiabili nella pratica prima del 2008: ogni codice decodificabile localmente conosciuto era anche correggibile localmente. La scoperta di Yekhanin ed Efremenko ha sollevato la possibilità di una differenza fondamentale tra le due condizioni. O forse era possibile modificare i codici di Yekhanin ed Efremenko per renderli correggibili localmente. Ciò metterebbe le due condizioni ancora una volta su un piano di parità, ma significherebbe anche che i ricercatori si sono sbagliati su quanto potrebbero essere efficienti i codici a tre query correggibili localmente. In ogni caso, la saggezza convenzionale dovrebbe cambiare.

Logica del prestito

Kothari e Manohar finalmente risolsero quella tensione adattando una tecnica proveniente da un diverso settore dell'informatica: lo studio dei cosiddetti problemi di soddisfazione dei vincoli. Cercare di coordinare i programmi della cena con un gruppo di amici è una sorta di problema di soddisfazione dei vincoli. Ognuno ha delle scelte che accetterà e delle scelte a cui porrà il veto. Il tuo compito è trovare un piano che soddisfi tutti o, se non esiste un piano del genere, capirlo il prima possibile.

Esiste un’asimmetria intrinseca tra questi due possibili risultati. Potrebbe non essere facile trovare una soluzione accettabile, ma una volta ottenuta, è facile convincere qualcun altro che funzionerà. Ma anche se si sa che il problema è davvero “insoddisfacibile”, potrebbe non esserci un esempio che ne fornisca la prova.

Nel 2021, Kothari e Manohar, insieme a Venkatesan Guruswami dell'Università della California, Berkeley, hanno realizzato un grande passo avanti nello studio dei problemi di soddisfazione dei vincoli utilizzando una nuova tecnica teorica per identificare quei casi difficili e insoddisfacibili. Sospettavano che il nuovo metodo sarebbe stato un potente strumento per risolvere anche altri problemi, e lo studente laureato di Guruswami, Omar Alrabiah, suggerì di esaminare codici decodificabili localmente a tre query.

"Questo era un chiodo con un martello in mano, per così dire", ha detto Kothari.

I sorprendenti risultati di Yekhanin ed Efremenko avevano dimostrato che i codici decodificabili localmente a tre query potevano essere più efficienti dei codici Reed-Muller. Ma i loro codici erano i migliori possibili o i codici decodificabili localmente a tre query potevano diventare ancora più efficienti? Kothari, Manohar, Guruswami e Alrabiah pensavano che la loro nuova tecnica potesse essere in grado di dimostrare i limiti dell'efficienza che tali codici potevano ottenere. Il loro piano era quello di costruire una formula logica che comprendesse la struttura di tutti i possibili codici decodificabili localmente a tre query di una data dimensione e dimostrarla insoddisfacente, dimostrando così che un codice del genere non poteva esistere.

I quattro ricercatori hanno fatto un primo passo in quella direzione nel 2022, stabilendo a nuovo limite sulla massima efficienza dei codici decodificabili localmente a tre query. Il risultato è andato ben oltre ciò che i ricercatori erano stati in grado di ottenere con altre tecniche, ma non ha escluso che tutti i codici fossero più efficienti di quelli di Yekhanin ed Efremenko.

Kothari e Manohar sospettavano di poter andare oltre. Ma i progressi si sono arrestati finché Manohar non ha buttato giù un rapido calcolo che indicava che la tecnica avrebbe potuto funzionare ancora meglio per i codici correggibili localmente rispetto a quelli decodificabili localmente.

Pochi mesi dopo, dopo molte altre false partenze che fecero temere di essere stati troppo ottimisti, la tecnica finalmente mantenne la sua promessa. Kothari e Manohar hanno dimostrato che, come sospettavano i ricercatori, è impossibile che qualsiasi codice correggibile localmente a tre query funzioni sensibilmente meglio dei codici Reed-Muller. Questo ridimensionamento esponenziale è una limitazione fondamentale. Il loro risultato fu anche una dimostrazione drammatica che la correggibilità locale e la decodificabilità locale, sebbene superficialmente simili, in realtà differiscono a un livello fondamentale: la seconda è inequivocabilmente più facile da realizzare della prima.

Kothari e Manohar sperano ora di estendere le loro tecniche allo studio dei codici che consentono di effettuare più di tre query, poiché al momento si sa molto poco su di loro. E i progressi nella teoria della correzione degli errori hanno spesso implicazioni in altri campi apparentemente non correlati. In particolare, i codici correggibili localmente fanno apparizioni sorprendenti ovunque dal problema ricerche in banche dati private in crittografia alle prove di teoremi di combinatoria. È troppo presto per dire quale sarà l’impatto della tecnica di Kothari e Manohar su questi diversi campi, ma i ricercatori si sentono ottimisti.

“C’è una nuova idea davvero bellissima qui”, ha detto Dvir. “Penso che ci sia molto potenziale.”