"Magisk" feilrettingsskjema har vist seg å være ineffektivt | Quanta Magazine

Hvis du noen gang har sendt en tekstmelding, spilt av en CD eller lagret en fil i skyen, har du hatt fordel av feilretting. Denne revolusjonerende ideen dateres tilbake til 1940-tallet, da forskere først innså at det er mulig å omskrive en hvilken som helst melding i en form som gjør at senere korrupsjon lett kan reverseres.

Gjennom årene har forskere utviklet mange geniale opplegg, kalt feilkorrigerende koder, som koder data på forskjellige måter og bruker forskjellige prosedyrer for å fikse feil. Men for teoretiske datavitere er det få som er så overbevisende som såkalte lokalt korrigerbare koder. Disse kodene har to samtidige egenskaper som høres nesten motstridende ut: Enhver feil kan rettes ved å lese de kodede dataene på bare noen få steder, men ingen angriper kan hindre denne korreksjonsprosedyren ved å selektivt tukle med koden. Det er som om du kan gjenopprette hvilken som helst side som er revet ut av en bok ved å bare se på noen få andre.

"Det er et ganske magisk fenomen," sa Tom Gur, en informatiker ved University of Cambridge. "A priori er det ikke åpenbart at et slikt matematisk objekt i det hele tatt kan eksistere."

Men denne magien har en høy pris. De eneste kjente eksemplene på lokalt korrigerbare koder er ekstremt ineffektive - koding av en melding gjør den også eksponentielt lengre. Hele bøker kodet på denne måten ville være altfor uhåndterlige.

Dataforskere har lenge lurt på om bedre lokalt korrigerbare koder er mulig. De har fokusert spesielt på koder som bare bruker tre spørringer for å rette eventuelle feil, i håp om at denne alvorlige begrensningen kan gjøre disse kodene lettere å forstå. Men selv denne enkle saken har forbløffet forskere i over 20 år.

Nå informatikeren Pravesh Kothari ved Carnegie Mellon University og hans doktorgradsstudent Peter Manohar har endelig beviste at det er umulig å bygge en tre-søks lokalt korrigerbar kode som unngår den eksponentielle kostnaden. Det kan være et negativt resultat, men alt som tydeliggjør grensene for feilretting er spennende for forskere, spesielt fordi matematikken til lokalt korrigerbare koder dukker opp i områder langt unna kommunikasjon.

"Dette resultatet er fantastisk," sa Shubhangi Saraf, en informatiker ved University of Toronto. "Det er et stort gjennombrudd."

Styrke i tall

For å forstå feilretting, se for deg dataene du vil beskytte som en sekvens av biter, eller 0-er og 1-ere. En feil i denne modellen kan være en hvilken som helst uønsket vending av 0 til 1 eller omvendt, enten det skyldes en tilfeldig svingning eller bevisst tukling.

Anta at du vil sende en melding til en venn, men du er bekymret for at feil kan endre betydningen. En enkel strategi er å erstatte hver 0 i meldingen din med 000 og hver 1 med 111. Hvis vennen din ser en del av meldingen som ikke inneholder tre identiske biter på rad, vil de vite at det har oppstått en feil. Og hvis feil er tilfeldige og relativt sjeldne, så er det mye større sannsynlighet for at en hvilken som helst streng på 110 er en ødelagt 111 enn en ødelagt 000. Et simpelt flertall i hver triplett vil være tilstrekkelig for å rette opp de fleste feil.

Denne ordningen, kalt repetisjonskoden, har fordelen av enkelhet, men lite annet å anbefale den. For det første krever det å tredoble lengden på hver melding bare for å håndtere relativt sjeldne feil, og hvis det er en anstendig sjanse for to tilstøtende feil, trenger vi enda mer redundans. Enda verre, det blir raskt ubrukelig hvis feil ikke er tilfeldige, for eksempel når angripere aktivt prøver å sabotere koden. I repetisjonskoden lagres all informasjonen som trengs for å korrigere en gitt bit i bare noen få andre biter, noe som gjør den sårbar for et målrettet angrep.

Heldigvis har mange feilrettingskoder det bedre. Et kjent eksempel, kalt Reed-Solomon-kode, fungerer ved å transformere meldinger til polynomer — matematiske uttrykk som x² + 3x + 2 som består av forskjellige termer lagt sammen, hver med en variabel (som f.eks x) hevet til en annen makt. Koding av en melding ved hjelp av en Reed-Solomon-kode innebærer å bygge et polynom med ett begrep for hvert tegn i meldingen, og deretter plotte polynomet som en kurve på en graf og lagre koordinatene til punktene som ligger på kurven (tar minst ett til punkt enn antall tegn). Feil kan skyve noen av disse punktene ut av kurven, men hvis det ikke er for mange feil, vil bare én polynomkurve gå gjennom de fleste punktene. Den kurven tilsvarer nesten helt det sanne budskapet.

Reed-Solomon-koder er hypereffektive - du trenger bare å lagre noen få ekstra poeng for å rette feil, så enhver kodet melding er bare marginalt lengre enn originalen. De er også mindre sårbare for den typen målrettede forstyrrelser som ville bety katastrofe for repetisjonskoden, fordi informasjonen som brukes til å rette en feil hvor som helst, er distribuert over hele den kodede meldingen.

Tenk globalt, handle lokalt

Styrken til Reed-Solomon-koden stammer fra sammenkobling. Men nettopp på grunn av den sammenkoblingen, er det ingen måte å fikse en enkelt feil i en kodet melding uten å lese hele greia. Det høres kanskje ikke ut som et problem i kommunikasjonssammenheng: Hvis du sender en melding, vil du sannsynligvis at mottakeren skal lese alt. Men det kan være et ansvar i datalagring - en annen viktig anvendelse av feilretting.

Tenk på et selskap som lagrer brukernes e-post i skyen – det vil si på et stort utvalg servere. Du kan tenke på hele samlingen av e-poster som én lang melding. Anta nå at en server krasjer. Med en Reed-Solomon-kode, må du utføre en massiv beregning som involverer alle de kodede dataene for å gjenopprette e-postene dine fra den tapte serveren. "Du må se på alt," sa Zeev Dvir, en informatiker ved Princeton University. "Det kan være milliarder og milliarder av e-poster - det kan ta veldig lang tid."

Forskere bruker begrepet "lokal" for å beskrive koder som bare bruker en brøkdel av den kodede meldingen til spot feil eller korrigere dem. Den enkle repetisjonskoden har noe av denne lokale karakteren, men det er nettopp det som gjør den så sårbar for tukling. En lokalt korrigerbar kode får derimot det beste fra begge verdener – den kan korrigere en feil i hvilken som helst bit med bare noen få spørringer, alt uten å miste sammenkoblingen som gjør Reed-Solomon-koder så motstandsdyktige.

"Dette er en veldig streng oppfatning," sa Kothari.

De mest kjente eksemplene på lokalt korrigerbare koder er versjoner av en ærverdig feilrettingskode oppfunnet i 1954 av matematikerne David Muller og Irving Reed (som også hjalp til med å utvikle Reed-Solomon-koder). I likhet med Reed-Solomon-koder, bruker Reed-Muller-koder polynomer med mange termer lagt sammen for å kode lange meldinger.

Polynomene som brukes i Reed-Solomon-koder involverer en enkelt variabel, x, så den eneste måten å legge til flere termer på er å bruke høyere krefter x. Dette resulterer i en kurve med mange vrikker som bare kan festes ved å se på mange punkter. Reed-Muller-koder bruker i stedet polynomer der hvert ledd kan inneholde flere variable multiplisert sammen. Flere variabler betyr flere måter å kombinere dem på, som igjen tilbyr en måte å øke antallet polynomledd uten å heve noen individuelle variabler til så høye potenser.

Reed-Muller-koder er veldig fleksible. Du kan kode lengre meldinger ved å øke den høyeste potensen som vises i polynomet, øke antallet variabler eller begge deler. For å gjøre en Reed-Muller-kode lokalt korrigerbar, begrenser du bare den maksimale kraften til hver variabel til en liten konstant verdi, og håndterer lengre meldinger ved å bare øke antallet variabler.

For en tre-spørrings lokalt korrigerbar kode spesifikt, er den maksimale effekten satt til 2. Når det gjelder hver enkelt variabel, sporer polynomet som koder for meldingen ut en enkel parabel. For å bestemme den nøyaktige formen til den parabelen, trenger du bare å undersøke kurven på tre punkter. Dessuten, med mange variabler er det mange slike paraboler, som alle kan brukes til å rette feil. Det er det som gjør Reed-Muller-koder så spenstige.

Dessverre har Reed-Muller-koden en alvorlig ulempe: Antallet biter som kreves for å kode en melding øker eksponentielt med antall variabler. Hvis du vil ha en svært lokal kode som korrigerer feil med bare en håndfull spørringer, trenger du mange variabler for lange meldinger, og Reed-Muller-koden vil raskt bli ubrukelig i praksis.

"Eksponentiell i dette tilfellet er veldig dårlig," sa Dvir. Men er det uunngåelig?

Korrigerbar eller avkodbar?

Da informatikere prøvde og ikke klarte å finne mer effektive lokalt korrigerbare koder, begynte de å mistenke at slike koder ikke var mulige i det hele tatt. I 2003, to forskere beviste at det ikke er noen måte å slå Reed-Muller-koden ved å bruke bare to spørringer. Men det er så langt noen har kommet.

"Når du går til tre, blir kunnskapen vår veldig skisse," sa Kothari.

Det neste gjennombruddet kompliserte saken ytterligere. I to artikler publisert i 2008 og 2009, viste informatikerne Sergey Yekhanin og Klim Efremenko hvordan man konstruerte trespørringskoder som var mer effektive enn Reed-Muller-koder, men disse kodene var ikke helt lokalt korrigerbare. I stedet hadde de en subtilt annen egenskap kalt lokal avkodbarhet.

For å forstå forskjellen, la oss igjen forestille oss en skylagringsleverandør som kombinerer brukernes data til en lang melding og beskytter den ved hjelp av en feilkorrigerende kode. Både lokalt korrigerbare koder og lokalt dekodbare koder kan korrigere en feil i hvilken som helst del av den opprinnelige meldingen med bare noen få spørsmål.

Men hver feilkorrigerende kode krever også ekstra biter som ikke var i den opprinnelige meldingen - det er grunnen til at koding av en melding gjør den lengre. De to typene koder er forskjellige i hvordan de behandler disse tilleggsbitene. Lokalt dekodbare koder gir ingen løfter om antall spørringer som trengs for å rette opp feil i disse bitene. Men i en lokalt korrigerbar kode kan en feil i alle de ekstra bitene rettes på nøyaktig samme måte som en feil i en hvilken som helst bit av den opprinnelige meldingen.

"Alt du lagrer, enten det er de opprinnelige dataene til brukere eller redundansen og sjekkinformasjonen - alt dette kan korrigeres lokalt," sa Madhu Sudan, en informatiker ved Harvard University.

Selv om det er forskjellig i prinsippet, virket lokal korrigerbarhet og lokal dekodbarhet alltid utskiftbare i praksis før 2008 - hver kjente lokalt dekodbare kode var også lokalt korrigerbar. Yekhanin og Efremenkos oppdagelse reiste muligheten for en grunnleggende forskjell mellom de to forholdene. Eller kanskje det var mulig å endre Yekhanin og Efremenkos koder for å gjøre dem lokalt korrigerbare. Det ville stille de to forholdene på lik linje igjen, men det ville også bety at forskere hadde tatt feil av hvor effektive tre-spørrings lokalt korrigerbare koder kunne bli. Uansett ville konvensjonell visdom måtte endres.

Lånelogikk

Kothari og Manohar løste til slutt den spenningen ved å tilpasse en teknikk fra et annet område innen informatikk: studiet av såkalte constraint satisfaction-problemer. Å prøve å koordinere middagsplaner med en gruppe venner er et slags tilfredshetsproblem. Alle har valg de vil akseptere og valg de vil nedlegge veto mot. Din jobb er å enten finne en plan som tilfredsstiller alle, eller, hvis det ikke finnes en slik plan, finne ut av det så snart som mulig.

Det er en iboende asymmetri mellom disse to mulige utfallene. En akseptabel løsning er kanskje ikke lett å finne, men når du først har den, er det lett å overbevise noen andre om at det vil fungere. Men selv om du vet at problemet virkelig er "utilfredsstillende", er det kanskje ikke et eksempel som gir bevis.

I 2021 laget Kothari og Manohar, sammen med Venkatesan Guruswami ved University of California, Berkeley, en stort gjennombrudd i studiet av begrensningstilfredshetsproblemer ved å bruke en ny teoretisk teknikk for å identifisere de vanskelige utilfredsstillende tilfellene. De mistenkte at den nye metoden ville være et kraftig verktøy for å løse andre problemer også, og Guruswamis doktorgradsstudent Omar Alrabiah foreslo at de skulle se på tre-søk lokalt dekodbare koder.

"Dette var en spiker med en hammer i hånden, for å si det sånn," sa Kothari.

Yekhanin og Efremenkos overraskende resultater hadde vist at lokalt dekodbare koder med tre spørringer kunne være mer effektive enn Reed-Muller-koder. Men var kodene deres best mulig, eller kunne tre-søk lokalt dekodbare koder bli enda mer effektive? Kothari, Manohar, Guruswami og Alrabiah trodde den nye teknikken deres kunne bevise grenser for hvor effektive slike koder kunne bli. Planen deres var å bygge en logisk formel som omfatter strukturen til alle mulige tre-spørrings lokalt dekodbare koder av en gitt størrelse, og bevise den utilfredsstillende, og dermed vise at ingen slik kode kunne eksistere.

De fire forskerne tok et første skritt i den retningen i 2022, og satte en ny grense om maksimal effektivitet av lokalt dekodbare koder med tre søk. Resultatet gikk langt utover hva forskere hadde vært i stand til å oppnå med andre teknikker, men det utelukket ikke at alle koder var mer effektive enn Yekhanin og Efremenkos.

Kothari og Manohar mistenkte at de kunne gå lenger. Men fremgangen stoppet helt til Manohar noterte ned en rask bakside-av-konvolutt-beregning som indikerte at teknikken kan fungere enda bedre for lokalt korrigerbare koder enn den hadde for lokalt dekodbare.

Noen måneder senere, etter mange flere falske starter som fikk dem til å frykte at de hadde vært for optimistiske, holdt teknikken endelig løftet. Kothari og Manohar beviste at som forskere hadde mistenkt, er det umulig for en lokalt korrigerbar kode med tre spørringer å fungere betydelig bedre enn Reed-Muller-koder. At eksponentiell skalering er en grunnleggende begrensning. Resultatet deres var også en dramatisk demonstrasjon av at lokal korrigerbarhet og lokal avkodbarhet, selv om de er overfladisk like, virkelig skiller seg på et grunnleggende nivå: Sistnevnte er utvetydig lettere å realisere enn førstnevnte.

Kothari og Manohar håper nå å utvide teknikkene sine til å studere koder som har lov til å lage mer enn tre spørringer, siden svært lite er kjent om dem nå. Og fremskritt i teorien om feilretting har ofte implikasjoner på andre tilsynelatende ikke-relaterte felt. Spesielt lokalt korrigerbare koder gjør overraskende opptredener overalt fra problemet med private databasesøk i kryptografi til bevis for teoremer i kombinatorikk. Det er for tidlig å si hvordan Kothari og Manohars teknikk vil påvirke disse forskjellige feltene, men forskerne føler seg optimistiske.

"Det er en virkelig vakker ny idé her," sa Dvir. – Jeg tror det er mye potensiale.