"Maaginen" virheenkorjausjärjestelmä osoittautui luonnostaan ​​tehottomaksi | Quanta-lehti

Jos olet joskus lähettänyt tekstiviestin, toistanut CD-levyä tai tallentanut tiedoston pilveen, olet hyötynyt virheenkorjauksesta. Tämä vallankumouksellinen ajatus juontaa juurensa 1940-luvulle, jolloin tutkijat ymmärsivät ensimmäisen kerran, että mikä tahansa viesti on mahdollista kirjoittaa uudelleen sellaiseen muotoon, että myöhempi korruptio voidaan helposti kääntää.

Vuosien varrella tutkijat ovat kehittäneet monia nerokkaita järjestelmiä, joita kutsutaan virheenkorjauskoodeiksi ja jotka koodaavat tietoja eri tavoin ja käyttävät erilaisia ​​menetelmiä virheiden korjaamiseen. Mutta teoreettisille tietojenkäsittelytieteilijöille harvat ovat yhtä vakuuttavia kuin niin kutsutut paikallisesti korjattavat koodit. Näillä koodeilla on kaksi samanaikaista ominaisuutta, jotka kuulostavat melkein ristiriitaisilta: Kaikki virheet voidaan korjata lukemalla koodattu data vain muutamasta paikasta, mutta kukaan hyökkääjä ei voi estää tätä korjausmenettelyä muokkaamalla koodia valikoivasti. Tuntuu kuin voisit palauttaa minkä tahansa kirjasta revityn sivun vain vilkaisemalla muutamaa muuta.

"Se on aika maaginen ilmiö", sanoi Tom Gur, tietojenkäsittelytieteilijä Cambridgen yliopistosta. "A priori ei ole selvää, että tällainen matemaattinen objekti voisi olla olemassa."

Mutta tämä taika maksaa jyrkät kustannukset. Ainoat tunnetut esimerkit paikallisesti korjattavista koodeista ovat äärimmäisen tehottomia - minkä tahansa viestin koodaus pidentää myös eksponentiaalisesti. Tällä tavalla koodatut kokonaiset kirjat olisivat aivan liian raskaita.

Tietojenkäsittelytieteilijät ovat pitkään pohtineet, ovatko paremmat paikallisesti korjattavat koodit mahdollisia. He ovat keskittyneet erityisesti koodeihin, jotka käyttävät vain kolmea kyselyä virheiden korjaamiseen, toivoen, että tämä vakava rajoitus voisi tehdä näistä koodeista helpompia ymmärtää. Mutta tämäkin yksinkertainen tapaus on hämmästyttänyt tutkijoita yli 20 vuoden ajan.

Nyt tietojenkäsittelytieteilijä Pravesh Kothari Carnegie Mellonin yliopistosta ja hänen jatko-opiskelijansa Peter Manohar on vihdoin osoittautui että on mahdotonta rakentaa kolmen kyselyn paikallisesti korjattavaa koodia, joka välttää eksponentiaaliset kustannukset. Se voi olla negatiivinen tulos, mutta kaikki, mikä selventää virheenkorjauksen rajoja, on tutkijoille jännittävää, etenkin koska paikallisesti korjattavien koodien matematiikka tulee esiin alueilla, jotka ovat kaukana viestinnästä.

"Tämä tulos on hämmästyttävä", sanoi Shubhangi Saraf, tietojenkäsittelytieteilijä Toronton yliopistosta. "Se on valtava läpimurto."

Vahvuus numeroissa

Ymmärtääksesi virheenkorjauksen, kuvittele suojattavat tiedot bittijonona tai 0:na ja 1:nä. Virhe tässä mallissa voi olla mikä tahansa ei-toivottu 0:n kääntäminen 1:ksi tai päinvastoin, johtuupa se sitten satunnaisesta vaihtelusta tai tahallisesta peukaloitumisesta.

Oletetaan, että haluat lähettää viestin ystävälle, mutta olet huolissasi siitä, että virheet voivat muuttaa merkitystä. Yksi yksinkertainen strategia on korvata viestisi kukin 0 numerolla 000 ja kukin 1 luvulla 111. Jos ystäväsi näkee viestin osan, joka ei sisällä kolmea identtistä bittiä peräkkäin, hän tietää, että on tapahtunut virhe. Ja jos virheet ovat satunnaisia ​​ja suhteellisen harvinaisia, mikä tahansa 110-merkkijono on paljon todennäköisemmin viallinen 111 kuin vioittunut 000. Yksinkertainen enemmistöäänestys kussakin kolmiossa riittää korjaamaan useimmat virheet.

Tämän toistokoodiksi kutsutun järjestelmän etuna on yksinkertaisuus, mutta vain vähän muuta suositella sitä. Ensinnäkin se vaatii kolminkertaistamaan jokaisen viestin pituuden vain suhteellisen harvoin esiintyvien virheiden käsittelemiseksi, ja jos on kunnollinen mahdollisuus kahdelle vierekkäiselle virheelle, tarvitsemme vielä enemmän redundanssia. Mikä vielä pahempaa, siitä tulee nopeasti hyödytöntä, jos virheet eivät ole satunnaisia, kuten esimerkiksi silloin, kun hyökkääjät yrittävät aktiivisesti sabotoida koodia. Toistokoodissa kaikki tietyn bitin korjaamiseen tarvittavat tiedot tallennetaan vain muutamaan muuhun bittiin, jolloin se on alttiina kohdistetulle hyökkäykselle.

Onneksi monet virheenkorjauskoodit pärjäävät paremmin. Yksi kuuluisa esimerkki, nimeltään Reed-Solomon koodi, toimii muuntamalla viestit polynomeiksi - matemaattisiksi lausekkeiksi, kuten x² + 3x + 2, jotka koostuvat eri termeistä, jotka on yhdistetty yhteen, ja jokaisessa on muuttuja (kuten x) korotettu eri tehoon. Viestin koodaaminen Reed-Solomon-koodilla edellyttää polynomin rakentamista, jossa on yksi termi jokaiselle viestin merkille, sitten polynomin piirtämisen käyränä kuvaajalle ja käyrällä olevien pisteiden koordinaatit tallentamiseen (ottaen vähintään yhden lisää pistettä kuin merkkien määrä). Virheet saattavat työntää muutaman näistä pisteistä pois käyrästä, mutta jos virheitä ei ole liikaa, vain yksi polynomikäyrä kulkee useimpien pisteiden läpi. Tuo käyrä vastaa lähes varmasti todellista viestiä.

Reed-Solomon-koodit ovat erittäin tehokkaita - sinun tarvitsee vain tallentaa muutama lisäpiste virheiden korjaamiseksi, joten mikä tahansa koodattu viesti on vain vähän pidempi kuin alkuperäinen. Ne ovat myös vähemmän alttiita kohdistetuille häiriöille, jotka aiheuttaisivat katastrofin toistokoodille, koska tiedot, joita käytetään virheen korjaamiseen missä tahansa, jakautuvat koko koodatun viestin yli.

Ajattele maailmanlaajuisesti, toimita paikallisesti

Reed-Solomon-koodin vahvuus johtuu keskinäisestä yhteydestä. Mutta juuri tämän keskinäisen yhteyden vuoksi ei ole mahdollista korjata yhtä virhettä koodatussa viestissä lukematta koko asiaa. Se ei ehkä kuulosta ongelmalta viestinnän yhteydessä: Jos lähetät viestin, haluat luultavasti vastaanottajan lukevan sen. Mutta se voi olla vastuuta tietojen tallentamisessa - toinen tärkeä virheenkorjaussovellus.

Harkitse yritystä, joka tallentaa käyttäjien sähköpostit pilveen – eli laajalle valikoimalle palvelimia. Voit ajatella koko sähköpostikokoelmaa yhdeksi pitkäksi viestiksi. Oletetaan nyt, että yksi palvelin kaatuu. Reed-Solomon-koodilla sinun on suoritettava valtava laskenta, joka sisältää kaikki koodatut tiedot, jotta voit palauttaa sähköpostisi yhdeltä kadonneelta palvelimelta. "Sinun pitäisi katsoa kaikkea", sanoi Zeev Dvir, tietojenkäsittelytieteilijä Princetonin yliopistosta. "Se voi olla miljardeja ja miljardeja sähköposteja - se voi viedä todella kauan."

Tutkijat käyttävät termiä "paikallinen" kuvaamaan koodeja, jotka käyttävät vain murto-osaa koodatusta viestistä pistevirheitä tai korjaa ne. Yksinkertaisessa toistokoodissa on jotain tämän paikallisen luonteen kaltaista, mutta juuri se tekee siitä niin alttiita peukalointille. Paikallisesti korjattava koodi sitä vastoin saa molempien maailmojen parhaat puolet – se voi korjata minkä tahansa bitin virheen vain muutamalla kyselyllä menettämättä keskinäistä yhteyttä, joka tekee Reed-Solomon-koodeista niin joustavia.

"Tämä on todella tiukka käsite", Kothari sanoi.

Tunnetuimmat esimerkit paikallisesti korjattavista koodeista ovat versioita arvostetusta virheenkorjauskoodista, jonka matemaatikot keksivät vuonna 1954. David Muller ja Irving Reed (joka myös auttoi kehittämään Reed-Solomon koodeja). Kuten Reed-Solomon-koodit, Reed-Muller-koodit käyttävät polynomeja, joissa on useita termejä yhdistettynä pitkien viestien koodaamiseen.

Reed-Solomon-koodeissa käytetyt polynomit sisältävät yhden muuttujan, x, joten ainoa tapa lisätä termejä on käyttää suurempia tehoja x. Tämä johtaa käyrään, jossa on monia heilutuksia, jotka voidaan kiinnittää vain katsomalla monia pisteitä. Reed-Muller-koodit käyttävät sen sijaan polynomeja, joissa jokainen termi voi sisältää useita muuttujia kerrottuna yhteen. Enemmän muuttujia tarkoittaa enemmän tapoja yhdistää niitä, mikä puolestaan ​​tarjoaa tavan lisätä polynomitermien määrää ilman, että yksittäinen muuttuja nousee niin suuriin potenssiin.

Reed-Muller koodit ovat erittäin joustavia. Voit koodata pidempiä viestejä lisäämällä polynomissa näkyvää suurinta tehoa, lisäämällä muuttujien määrää tai molempia. Jotta Reed-Muller-koodista tulee paikallisesti korjattava, rajoitat vain kunkin muuttujan maksimiteho pieneen vakioarvoon ja käsittelet pidempiä viestejä lisäämällä vain muuttujien määrää.

Erityisesti kolmen kyselyn paikallisesti korjattavalle koodille maksimiteho asetetaan arvoon 2. Sitten kunkin yksittäisen muuttujan osalta viestiä koodaava polynomi jäljittää yksinkertaisen paraabelin. Tämän paraabelin tarkan muodon määrittämiseksi sinun tarvitsee vain tutkia käyrä kolmessa pisteessä. Lisäksi monilla muuttujilla on monia sellaisia ​​paraabeleja, joista mitä tahansa voidaan käyttää virheiden korjaamiseen. Tämä tekee Reed-Muller-koodeista niin joustavia.

Valitettavasti Reed-Muller-koodilla on vakava haittapuoli: viestin koodaamiseen tarvittavien bittien määrä kasvaa eksponentiaalisesti muuttujien määrän myötä. Jos haluat erittäin paikallisen koodin, joka korjaa virheet muutamalla kyselyllä, tarvitset paljon muuttujia pitkille viesteille, ja Reed-Muller-koodi tulee nopeasti hyödyttömäksi käytännössä.

"Eksponentiaalinen tässä tapauksessa on erittäin huono", Dvir sanoi. Mutta onko se väistämätöntä?

Korjattavissa vai dekoodattavissa?

Kun tietotekniikan tutkijat yrittivät löytää tehokkaampia paikallisesti korjattavia koodeja, he alkoivat epäillä, että tällaiset koodit eivät olleet ollenkaan mahdollisia. Vuonna 2003 kaksi tutkijaa osoittautui että Reed-Muller-koodia ei voi voittaa vain kahdella kyselyllä. Mutta se on niin pitkälle kuin kukaan pääsi.

"Kun siirryt kolmeen, tietomme muuttuu erittäin epämääräisiksi", Kothari sanoi.

Seuraava läpimurto vain mutkistaa asioita. Kahdessa vuonna julkaistussa artikkelissa 2008 ja 2009Tietojenkäsittelytieteilijät Sergei Jehanin ja Klim Efremenko osoittivat, kuinka rakennettiin kolmen kyselyn koodeja, jotka olivat tehokkaampia kuin Reed-Muller-koodit, mutta nämä koodit eivät olleet aivan paikallisesti korjattavissa. Sen sijaan niillä oli hienovaraisesti erilainen ominaisuus, jota kutsutaan paikalliseksi dekoodatavuudeksi.

Eron ymmärtämiseksi kuvitellaan jälleen pilvitallennuspalvelun tarjoaja, joka yhdistää käyttäjien tiedot yhdeksi pitkäksi viestiksi ja suojaa sitä virheenkorjauskoodilla. Sekä paikallisesti korjattavat koodit että paikallisesti dekoodattavat koodit voivat korjata virheen missä tahansa alkuperäisen viestin bitissä vain muutamalla kyselyllä.

Mutta jokainen virheenkorjauskoodi vaatii myös ylimääräisiä bittejä, joita ei ollut alkuperäisessä viestissä – siksi viestin koodaus pidentää sitä. Nämä kaksi koodityyppiä eroavat siitä, miten ne käsittelevät näitä lisäbittejä. Paikallisesti dekoodattavat koodit eivät lupaa näiden bittien virheiden korjaamiseen tarvittavien kyselyjen määrää. Mutta paikallisesti korjattavassa koodissa minkä tahansa ylimääräisen bitin virhe voidaan korjata täsmälleen samalla tavalla kuin virhe missä tahansa alkuperäisen viestin bitissä.

"Kaikki mitä tallennat, olipa kyseessä käyttäjien alkuperäiset tiedot tai redundanssi- ja tarkistustiedot - kaikki tämä voidaan korjata paikallisesti", sanoi Madhu Sudan, tietojenkäsittelytieteilijä Harvardin yliopistossa.

Vaikka paikallinen korjattavuus ja paikallinen dekoodattavuus olivat periaatteessa erilaisia, ne tuntuivat käytännössä aina keskenään vaihdettavissa olevilta ennen vuotta 2008 – jokainen tunnettu paikallisesti purettava koodi oli myös paikallisesti korjattavissa. Jehaninin ja Efremenkon löytö nosti esiin perustavanlaatuisen eron mahdollisuuden näiden kahden ehdon välillä. Tai ehkä oli mahdollista muokata Yekhaninin ja Efremenkon koodeja, jotta ne olisivat paikallisesti korjattavissa. Tämä asettaisi nämä kaksi ehtoa jälleen tasa-arvoon, mutta se merkitsisi myös sitä, että tutkijat olisivat olleet erehtyneet sen suhteen, kuinka tehokkaita kolmen kyselyn paikallisesti korjattavat koodit voisivat olla. Joka tapauksessa perinteisen viisauden pitäisi muuttua.

Lainauslogiikka

Kothari ja Manohar lopulta ratkaisivat tämän jännityksen soveltamalla tekniikkaa toiselta tietojenkäsittelytieteen alueelta: niin kutsuttujen rajoitustyytyväisyysongelmien tutkimuksesta. Illallissuunnitelmien sovittaminen ystäväryhmän kanssa on eräänlainen tyytyväisyysongelma. Jokaisella on valintoja, jotka hän hyväksyy, ja valintoja, joita he kieltävät. Sinun tehtäväsi on joko löytää suunnitelma, joka tyydyttää kaikkia, tai jos sellaista ei ole, selvittää se mahdollisimman pian.

Näiden kahden mahdollisen tuloksen välillä on luontainen epäsymmetria. Hyväksyttävää ratkaisua ei ehkä ole helppo löytää, mutta kun se on, on helppo vakuuttaa muut siitä, että se toimii. Mutta vaikka tietäisitkin, että ongelma todella on "tyydyttymätön", esimerkkiä ei välttämättä löydy todisteeksi.

Vuonna 2021 Kothari ja Manohar tekivät yhdessä Venkatesan Guruswamin kanssa Kalifornian yliopistosta Berkeleystä merkittävä läpimurto rajoitteiden tyytyväisyysongelmien tutkimuksessa käyttämällä uutta teoreettista tekniikkaa näiden hankkien epätyydyttyvien tapausten tunnistamiseen. He epäilivät, että uusi menetelmä olisi tehokas työkalu myös muiden ongelmien ratkaisemiseen, ja Guruswamin jatko-opiskelija Omar Alrabiah ehdotti, että he tutkisivat kolmen kyselyn paikallisesti purettavia koodeja.

"Tämä oli naula vasaralla kädessämme", Kothari sanoi.

Yekhaninin ja Efremenkon yllättävät tulokset olivat osoittaneet, että kolmen kyselyn paikallisesti purettavat koodit voisivat olla tehokkaampia kuin Reed-Muller-koodit. Mutta olivatko heidän koodinsa parhaita mahdollisia, vai voisivatko kolmen kyselyn paikallisesti purettavat koodit olla vielä tehokkaampia? Kothari, Manohar, Guruswami ja Alrabiah ajattelivat, että heidän uusi tekniikkansa voisi todistaa rajoja, kuinka tehokkaita tällaiset koodit voisivat olla. Heidän suunnitelmansa oli rakentaa looginen kaava, joka kattaa kaikkien mahdollisten kolmen kyselyn tietyn kokoisten paikallisesti purettavien koodien rakenteen ja osoittaa, että se ei ole tyydyttävä, mikä osoittaa, ettei sellaista koodia voisi olla olemassa.

Neljä tutkijaa ottivat ensimmäisen askeleen tähän suuntaan vuonna 2022 ja asettivat a uusi raja kolmen kyselyn paikallisesti purettavien koodien maksimitehokkuudesta. Tulos ylitti huomattavasti sen, mitä tutkijat olivat voineet saavuttaa muilla tekniikoilla, mutta se ei sulkenut pois kaikkia koodeja tehokkaampia kuin Jehaninin ja Efremenkon.

Kothari ja Manohar epäilivät voivansa mennä pidemmälle. Mutta edistyminen pysähtyi, kunnes Manohar kirjoitti muistiin nopean kirjekuoren taustalaskennan, joka osoitti, että tekniikka saattaa toimia jopa paremmin paikallisesti korjattavissa olevissa koodeissa kuin paikallisesti purettavissa olevissa koodeissa.

Muutamaa kuukautta myöhemmin, useiden väärien aloitusten jälkeen, jotka saivat heidät pelkäämään olevansa liian optimistisia, tekniikka lunasti lopulta lupauksensa. Kothari ja Manohar osoittivat, että kuten tutkijat olivat epäillyt, mikään kolmen kyselyn paikallisesti korjattava koodi on mahdotonta toimia huomattavasti paremmin kuin Reed-Muller-koodit. Tuo eksponentiaalinen skaalaus on perustavanlaatuinen rajoitus. Heidän tuloksensa oli myös dramaattinen osoitus siitä, että paikallinen korjattavuus ja paikallinen dekoodattavuus, vaikkakin pintapuolisesti samankaltaiset, todellakin eroavat perustasolla: jälkimmäinen on yksiselitteisesti helpompi toteuttaa kuin edellinen.

Kothari ja Manohar toivovat nyt laajentavansa tekniikoitaan tutkimaan koodeja, jotka voivat tehdä enemmän kuin kolme kyselyä, koska niistä tiedetään nyt hyvin vähän. Ja virheenkorjauksen teorian edistyminen vaikuttaa usein muilla näennäisesti toisiinsa liittymättömillä aloilla. Erityisesti paikallisesti korjattavat koodit yllättävät kaikkialla ongelmasta yksityiset tietokantahaut kryptografiassa todisteisiin kombinatoriikan lauseet. On liian aikaista sanoa, kuinka Kotharin ja Manoharin tekniikka vaikuttaa näille eri aloille, mutta tutkijat ovat optimistisia.

"Tässä on todella kaunis uusi idea", Dvir sanoi. "Mielestäni potentiaalia on paljon."