"Magiskt" felkorrigeringsschema visade sig vara ineffektivt | Quanta Magazine

Om du någonsin har skickat ett textmeddelande, spelat upp en CD eller lagrat en fil i molnet, har du dragit nytta av felkorrigering. Denna revolutionerande idé går tillbaka till 1940-talet, när forskare först insåg att det är möjligt att skriva om vilket meddelande som helst i en form som gör att senare korruption lätt kan vändas.

Under åren har forskare utvecklat många geniala system, så kallade felkorrigerande koder, som kodar data på olika sätt och använder olika procedurer för att åtgärda fel. Men för teoretiska datavetare är få så övertygande som så kallade lokalt korrigerbara koder. Dessa koder har två samtidiga egenskaper som låter nästan motsägelsefulla: Alla fel kan korrigeras genom att läsa den kodade datan på bara några få ställen, men ingen angripare kan förhindra denna korrigeringsprocedur genom att selektivt manipulera koden. Det är som om du skulle kunna återställa vilken sida som helst som rivits ur en bok genom att bara titta på några andra.

"Det är ett ganska magiskt fenomen," sa Tom Gur, en datavetare vid University of Cambridge. "A priori är det inte självklart att ett sådant matematiskt objekt överhuvudtaget skulle kunna existera."

Men denna magi kommer till en hög kostnad. De enda kända exemplen på lokalt korrigerbara koder är extremt ineffektiva - kodning av ett meddelande gör det också exponentiellt längre. Hela böcker kodade på det här sättet skulle vara alldeles för svårhanterliga.

Datavetare har länge undrat om bättre lokalt korrigerbara koder är möjliga. De har fokuserat särskilt på koder som bara använder tre frågor för att korrigera eventuella fel, i hopp om att denna allvarliga begränsning kan göra dessa koder lättare att förstå. Men även detta enkla fall har stört forskare i över 20 år.

Nu datavetaren Pravesh Kothari från Carnegie Mellon University och hans doktorand Peter Manohar har äntligen visat att det är omöjligt att bygga en lokalt korrigerbar kod med tre frågor som undviker den exponentiella kostnaden. Det kan vara ett negativt resultat, men allt som klargör gränserna för felkorrigering är spännande för forskare, särskilt eftersom matematiken för lokalt korrigerbara koder dyker upp i områden långt borta från kommunikation.

"Det här resultatet är fantastiskt," sa Shubhangi Saraf, en datavetare vid University of Toronto. "Det är ett stort genombrott."

Styrka i siffror

För att förstå felkorrigering, föreställ dig de data du vill skydda som en sekvens av bitar, eller 0:or och 1:or. Ett fel i den här modellen kan vara vilken oönskad vändning som helst av en nolla till en etta eller vice versa, oavsett om det beror på en slumpmässig fluktuation eller avsiktlig manipulering.

Anta att du vill skicka ett meddelande till en vän, men du är orolig för att fel kan ändra innebörden. En enkel strategi är att ersätta varje nolla i ditt meddelande med 0 och varje 000 med 1. Om din vän ser en del av meddelandet som inte innehåller tre identiska bitar i rad, kommer de att veta att ett fel har inträffat. Och om fel är slumpmässiga och relativt sällsynta, så är varje sträng med 111 mycket mer sannolikt att vara en skadad 110 än en skadad 111. En enkel majoritetsröst inom varje triplett kommer att räcka för att rätta till de flesta fel.

Detta schema, som kallas upprepningskoden, har fördelen av enkelhet, men lite annat att rekommendera det. För det första kräver det tredubbling av längden på varje meddelande bara för att hantera relativt sällsynta fel, och om det finns en anständig chans för två intilliggande fel, behöver vi ännu mer redundans. Ännu värre, det blir snabbt värdelöst om felen inte är slumpmässiga, till exempel när angripare aktivt försöker sabotera koden. I upprepningskoden lagras all information som behövs för att korrigera en given bit i bara några andra bitar, vilket gör den sårbar för en riktad attack.

Lyckligtvis klarar sig många felkorrigerande koder bättre. Ett känt exempel, kallat Reed-Solomon-kod, fungerar genom att omvandla meddelanden till polynom — matematiska uttryck som x² + 3x + 2 som består av olika termer adderade, var och en med en variabel (som t.ex x) upphöjd till en annan makt. Att koda ett meddelande med en Reed-Solomon-kod innebär att man bygger ett polynom med en term för varje tecken i meddelandet, sedan ritar polynomet som en kurva på en graf och lagrar koordinaterna för punkter som ligger på kurvan (ta minst en till punkt än antalet tecken). Fel kan förskjuta några av dessa punkter från kurvan, men om det inte finns för många fel kommer bara en polynomkurva att passera genom de flesta punkterna. Den kurvan motsvarar nästan säkert det sanna budskapet.

Reed-Solomon-koder är hypereffektiva - du behöver bara lagra några extra poäng för att rätta till fel, så alla kodade meddelanden är bara marginellt längre än originalet. De är också mindre sårbara för den typ av riktade störningar som skulle innebära katastrof för upprepningskoden, eftersom informationen som används för att korrigera ett fel var som helst distribueras över hela det kodade meddelandet.

Tänka globalt, agera lokalt

Styrkan i Reed-Solomon-koden härrör från sammanlänkning. Men just på grund av den sammanlänkningen finns det inget sätt att fixa ett enda fel i ett kodat meddelande utan att läsa allt. Det kanske inte låter som ett problem i kommunikationssammanhang: Om du skickar ett meddelande vill du förmodligen att mottagaren ska läsa allt. Men det kan vara ett ansvar vid datalagring - en annan viktig tillämpning av felkorrigering.

Tänk på ett företag som lagrar användarnas e-postmeddelanden i molnet - det vill säga på ett stort antal servrar. Du kan tänka på hela samlingen av e-postmeddelanden som ett långt meddelande. Anta nu att en server kraschar. Med en Reed-Solomon-kod, skulle du behöva utföra en massiv beräkning som involverar all kodad data för att återställa dina e-postmeddelanden från den förlorade servern. "Du skulle behöva titta på allt", sa Zeev Dvir, en datavetare vid Princeton University. "Det kan vara miljarder och miljarder e-postmeddelanden - det kan ta väldigt lång tid."

Forskare använder termen "lokal" för att beskriva koder som bara använder en bråkdel av det kodade meddelandet till spotfel eller rätta till dem. Den enkla upprepningskoden har något av denna lokala karaktär, men det är just det som gör den så sårbar för manipulering. En lokalt korrigerbar kod får däremot det bästa av två världar – den kan korrigera ett fel i vilken bit som helst med bara några få frågor, allt utan att förlora den sammankoppling som gör Reed-Solomon-koder så motståndskraftiga.

"Detta är ett riktigt strikt begrepp," sa Kothari.

De mest kända exemplen på lokalt korrigerbara koder är versioner av en ärevördig felkorrigerande kod som uppfanns 1954 av matematikerna David Muller och Irving Reed (som också hjälpte till att utveckla Reed-Solomon-koder). Liksom Reed-Solomon-koder använder Reed-Muller-koder polynom med många termer som läggs ihop för att koda långa meddelanden.

Polynomen som används i Reed-Solomon-koder involverar en enda variabel, x, så det enda sättet att lägga till fler termer är att använda högre krafter x. Detta resulterar i en kurva med många vickningar som bara kan nås fast genom att titta på många punkter. Reed-Muller-koder använder istället polynom där varje term kan innehålla flera variabler multiplicerade med varandra. Fler variabler betyder fler sätt att kombinera dem, vilket i sin tur erbjuder ett sätt att öka antalet polynomtermer utan att höja någon enskild variabel till så höga potenser.

Reed-Muller-koder är mycket flexibla. Du kan koda längre meddelanden genom att öka den högsta potensen som visas i polynomet, öka antalet variabler eller båda. För att göra en Reed-Muller-kod lokalt korrigerbar, begränsar du helt enkelt den maximala effekten för varje variabel till ett litet konstant värde och hanterar längre meddelanden genom att bara öka antalet variabler.

Specifikt för en lokalt korrigerbar kod med tre frågor, är den maximala effekten satt till 2. Sedan när det gäller varje individuell variabel spårar polynomet som kodar meddelandet en enkel parabel. För att bestämma den exakta formen på den parabeln behöver du bara undersöka kurvan vid tre punkter. Vad mer är, med många variabler finns det många sådana paraboler, vilka alla kan användas för att korrigera fel. Det är det som gör Reed-Muller-koder så motståndskraftiga.

Tyvärr har Reed-Muller-koden en allvarlig nackdel: Antalet bitar som krävs för att koda ett meddelande ökar exponentiellt med antalet variabler. Om du vill ha en mycket lokal kod som korrigerar fel med bara en handfull frågor, behöver du många variabler för långa meddelanden, och Reed-Muller-koden kommer snabbt att bli värdelös i praktiken.

"Exponentiellt i det här fallet är mycket dåligt," sa Dvir. Men är det oundvikligt?

Korrigerbar eller avkodningsbar?

När datavetare försökte och misslyckades med att hitta mer effektiva lokalt korrigerbara koder, började de misstänka att sådana koder inte alls var möjliga. År 2003 två forskare visat att det inte finns något sätt att slå Reed-Muller-koden med bara två frågor. Men det är så långt som någon kommit.

"När du går till tre, blir vår kunskap mycket skissartad," sa Kothari.

Nästa genombrott komplicerade bara saken ytterligare. I två tidningar publicerade i 2008 och 2009, visade datavetarna Sergey Yekhanin och Klim Efremenko hur man konstruerar tre-frågekoder som var mer effektiva än Reed-Muller-koder, men dessa koder var inte riktigt lokalt korrigerbara. Istället hade de en subtilt annorlunda egenskap som kallas lokal avkodbarhet.

För att förstå skillnaden, låt oss återigen föreställa oss en molnlagringsleverantör som kombinerar användarnas data till ett långt meddelande och skyddar den med en felkorrigerande kod. Både lokalt korrigerbara koder och lokalt avkodningsbara koder kan korrigera ett fel i valfri bit av det ursprungliga meddelandet med bara några få frågor.

Men varje felkorrigerande kod kräver också extra bitar som inte fanns i det ursprungliga meddelandet - det är därför som kodning av ett meddelande gör det längre. De två typerna av koder skiljer sig åt i hur de behandlar dessa ytterligare bitar. Lokalt avkodningsbara koder ger inga löften om antalet frågor som behövs för att korrigera fel i dessa bitar. Men i en lokalt korrigerbar kod kan ett fel i någon av de extra bitarna fixas på exakt samma sätt som ett fel i vilken bit som helst i det ursprungliga meddelandet.

"Allt du lagrar, oavsett om det är användarnas ursprungliga data eller redundansen och kontrollinformationen - allt detta kan korrigeras lokalt," sa Madhu Sudan, en datavetare vid Harvard University.

Även om det i princip var olika, verkade lokal korrigerbarhet och lokal avkodbarhet alltid utbytbara i praktiken före 2008 - varje känd lokalt avkodningsbar kod var också lokalt korrigerbar. Yekhanins och Efremenkos upptäckt lyfte möjligheten för en grundläggande skillnad mellan de två tillstånden. Eller kanske var det möjligt att modifiera Yekhanin och Efremenkos koder för att göra dem lokalt korrigerbara. Det skulle ställa de två villkoren på lika villkor än en gång, men det skulle också innebära att forskare hade misstagit sig om hur effektiva tre-frågor lokalt korrigerbara koder kunde bli. I vilket fall som helst skulle konventionell visdom behöva förändras.

Lånelogik

Kothari och Manohar löste slutligen den spänningen genom att anpassa en teknik från ett annat område inom datavetenskap: studiet av så kallade problem med tillfredsställelse med begränsningar. Att försöka samordna middagsplaner med en grupp vänner är ett slags tillfredsställelseproblem. Alla har val de kommer att acceptera och val de kommer att lägga in sitt veto. Ditt jobb är att antingen hitta en plan som tillfredsställer alla, eller, om det inte finns någon sådan plan, ta reda på det så snart som möjligt.

Det finns en inneboende asymmetri mellan dessa två möjliga utfall. En acceptabel lösning kanske inte är lätt att hitta, men när du väl har den är det lätt att övertyga någon annan om att det kommer att fungera. Men även om du vet att problemet verkligen är "otillfredsställande", kanske det inte finns ett exempel som ger bevis.

2021 gjorde Kothari och Manohar tillsammans med Venkatesan Guruswami från University of California, Berkeley, en stora genombrott i studiet av problem med tillfredsställelse av begränsningar med hjälp av en ny teoretisk teknik för att identifiera de knepiga otillfredsställande fallen. De misstänkte att den nya metoden skulle vara ett kraftfullt verktyg för att lösa andra problem också, och Guruswamis doktorand Omar Alrabiah föreslog att de skulle titta på tre-frågor lokalt avkodningsbara koder.

"Det här var en spik med en hammare i vår hand, så att säga," sa Kothari.

Yekhanin och Efremenkos överraskande resultat hade visat att lokalt avkodbara koder med tre frågor kunde vara mer effektiva än Reed-Muller-koder. Men var deras koder de bästa möjliga, eller skulle lokalt avkodningsbara koder med tre frågor bli ännu effektivare? Kothari, Manohar, Guruswami och Alrabiah trodde att deras nya teknik skulle kunna bevisa gränser för hur effektiva sådana koder kan bli. Deras plan var att bygga en logisk formel som omfattar strukturen av alla möjliga tre-frågor lokalt avkodningsbara koder av en given storlek, och bevisa att den inte är tillfredsställande, och därmed visa att ingen sådan kod kunde existera.

De fyra forskarna tog ett första steg i den riktningen 2022 och satte ett ny gräns om den maximala effektiviteten för lokalt avkodningsbara koder med tre frågor. Resultatet gick långt utöver vad forskare hade kunnat uppnå med andra tekniker, men det uteslöt inte att alla koder var effektivare än Yekhanin och Efremenkos.

Kothari och Manohar misstänkte att de kunde gå längre. Men framstegen avstannade tills Manohar skrev ner en snabb bak-av-kuvert-beräkning som indikerade att tekniken kan fungera ännu bättre för lokalt korrigerbara koder än för lokalt avkodningsbara.

Några månader senare, efter många fler falska starter som fick dem att frukta att de hade varit för optimistiska, höll tekniken äntligen sitt löfte. Kothari och Manohar bevisade att som forskare hade misstänkt är det omöjligt för någon lokalt korrigerbar kod med tre frågor att fungera avsevärt bättre än Reed-Muller-koder. Den exponentiella skalningen är en grundläggande begränsning. Deras resultat var också en dramatisk demonstration av att lokal korrigerbarhet och lokal avkodbarhet, även om de är ytligt lika, verkligen skiljer sig åt på en grundläggande nivå: den senare är otvetydigt lättare att realisera än den förra.

Kothari och Manohar hoppas nu kunna utöka sina tekniker för att studera koder som tillåts göra mer än tre frågor, eftersom mycket lite är känt om dem nu. Och framsteg inom teorin om felkorrigering har ofta implikationer på andra till synes orelaterade områden. I synnerhet gör lokalt korrigerbara koder överraskande framträdanden överallt från problemet med privata databassökningar i kryptografi till bevis för satser i kombinatorik. Det är för tidigt att säga hur Kothari och Manohars teknik kommer att påverka dessa olika områden, men forskarna känner sig optimistiska.

"Det finns en riktigt vacker ny idé här," sa Dvir. "Jag tror att det finns mycket potential."