"Maagiline" veaparandusskeem osutus oma olemuselt ebatõhusaks | Ajakiri Quanta

Kui olete kunagi saatnud tekstisõnumi, mänginud CD-d või salvestanud faili pilve, on vigade parandamisest kasu olnud. See revolutsiooniline idee pärineb 1940. aastatest, mil teadlased mõistsid esimest korda, et mis tahes sõnumit on võimalik ümber kirjutada kujul, mis võimaldab hilisemat korruptsiooni lihtsalt tagasi pöörata.

Aastate jooksul on teadlased välja töötanud palju geniaalseid skeeme, mida nimetatakse veaparanduskoodideks, mis kodeerivad andmeid erineval viisil ja kasutavad erinevaid protseduure vigade parandamiseks. Kuid teoreetiliste arvutiteadlaste jaoks on vähesed nii veenvad kui nn lokaalselt parandatavad koodid. Nendel koodidel on kaks samaaegset omadust, mis kõlavad peaaegu vastuoluliselt: iga viga saab parandada, lugedes kodeeritud andmeid vaid mõnes kohas, kuid ükski ründaja ei saa seda parandusprotseduuri rikkuda koodi valikulise rikkumisega. Näib, nagu saaksite mõne raamatust väljarebitud lehekülje taastada, kui heidate pilgu mõnele teisele.

"See on üsna maagiline nähtus," ütles Tom Gur, Cambridge'i ülikooli arvutiteadlane. "A priori pole ilmne, et selline matemaatiline objekt võiks üldse eksisteerida."

Kuid see maagia maksab tohutult. Ainsad teadaolevad näited kohalikult parandatavatest koodidest on äärmiselt ebaefektiivsed – mis tahes sõnumi kodeerimine muudab selle ka eksponentsiaalselt pikemaks. Terved sel viisil kodeeritud raamatud oleksid liiga kohmakad.

Arvutiteadlased on pikka aega mõelnud, kas paremad lokaalselt korrigeeritavad koodid on võimalikud. Nad on keskendunud eriti koodidele, mis kasutavad vigade parandamiseks ainult kolme päringut, lootes, et see tõsine piirang võib muuta need koodid paremini mõistetavaks. Kuid isegi see lihtne juhtum on teadlasi seganud juba üle 20 aasta.

Nüüd arvutiteadlane Pravesh Kothari Carnegie Melloni ülikoolist ja tema magistrandist Peeter Manohar on lõpuks ometi tõestatud et on võimatu luua kolme päringuga lokaalselt parandatavat koodi, mis väldib seda eksponentsiaalset kulu. See võib olla negatiivne tulemus, kuid kõik, mis selgitab vigade parandamise piire, on teadlastele põnev, eriti seetõttu, et kohalikult parandatavate koodide matemaatika ilmneb suhtlusest kaugel asuvates piirkondades.

"See tulemus on hämmastav," ütles Shubhangi Saraf, Toronto ülikooli arvutiteadlane. "See on tohutu läbimurre."

Tugevus numbrites

Veaparanduse mõistmiseks kujutage ette, et andmed, mida soovite kaitsta, on bittide või 0-de ja 1-de jada. Selles mudelis võib viga olla 0 soovimatu ümberpööramine 1-ks või vastupidi, olenemata sellest, kas see on tingitud juhuslikust kõikumisest või tahtlikust võltsimisest.

Oletame, et soovite saata sõnumi sõbrale, kuid olete mures, et vead võivad tähendust muuta. Üks lihtne strateegia on asendada sõnumis iga 0 000-ga ja iga 1 asendada 111-ga. Kui teie sõber näeb sõnumist osa, mis ei sisalda järjestikku kolme identset bitti, saab ta teada, et ilmnes viga. Ja kui vead on juhuslikud ja suhteliselt haruldased, siis on iga 110-string palju tõenäolisem rikutud 111 kui rikutud 000. Enamiku vigade parandamiseks piisab iga kolmiku lihthäälteenamusest.

Selle skeemi, mida nimetatakse korduskoodiks, eeliseks on lihtsus, kuid vähe muud, mida seda soovitada. Esiteks nõuab see iga sõnumi pikkuse kolmekordistamist, et tulla toime suhteliselt harva esinevate vigadega, ja kui on korralik kahe kõrvuti asetseva vea tõenäosus, vajame veelgi rohkem koondamist. Mis veelgi hullem, muutub see kiiresti kasutuks, kui vead pole juhuslikud, näiteks kui ründajad üritavad koodi aktiivselt saboteerida. Korduskoodis salvestatakse kogu antud biti parandamiseks vajalik teave vaid mõnes teises bitis, mis jätab selle sihitud rünnaku suhtes haavatavaks.

Õnneks läheb paljudel veaparanduskoodidel paremini. Üks kuulus näide, mida nimetatakse Reed-Saalomoni kood, muudab sõnumid polünoomideks — matemaatilised avaldised nagu x² + 3x + 2, mis koosnevad erinevatest kokku liidetud terminitest, millest igaühel on muutuja (nt x) tõstetud teisele astmele. Sõnumi kodeerimine Reed-Solomoni koodiga hõlmab polünoomi loomist, milles on iga sõnumi tähemärgi jaoks üks liige, seejärel polünoomi joonistamine graafikule kõverana ja kõveral asuvate punktide koordinaatide salvestamine (võtab veel vähemalt ühe punkti kui märkide arv). Vead võivad mõned neist punktidest kõveralt välja lükata, kuid kui vigu pole liiga palju, läbib enamikku punkte ainult üks polünoomkõver. See kõver vastab peaaegu kindlasti tõelisele sõnumile.

Reed-Solomoni koodid on ülitõhusad – vigade parandamiseks on vaja salvestada vaid mõned lisapunktid, nii et mis tahes kodeeritud sõnum on originaalist vaid pisut pikem. Samuti on nad vähem haavatavad sihipäraste häirete suhtes, mis võivad korduskoodi jaoks katastroofi põhjustada, kuna kõikjal vea parandamiseks kasutatav teave jaotatakse kogu kodeeritud sõnumis.

Mõtle globaalselt, tegutse lokaalselt

Reed-Saalomoni koodi tugevus tuleneb vastastikusest seotusest. Kuid just selle seotuse tõttu ei saa kodeeritud sõnumis ühtegi viga parandada ilma kogu asja läbi lugemata. See ei pruugi suhtluse kontekstis tunduda probleemina: kui saadate sõnumi, soovite tõenäoliselt, et adressaat seda kõike loeks. Kuid see võib olla andmete salvestamise kohustus - veel üks oluline vigade parandamise rakendus.

Mõelge ettevõttele, mis salvestab kasutajate e-kirju pilves, st paljudes serverites. Kogu e-kirjade kogust võib mõelda kui ühele pikale sõnumile. Oletame nüüd, et üks server jookseb kokku. Reed-Solomoni koodiga peate oma e-kirjade taastamiseks sellest ühest kadunud serverist tegema tohutu arvutuse, mis hõlmab kõiki kodeeritud andmeid. "Sa peaksid kõike vaatama," ütles Zeev Dvir, Princetoni ülikooli arvutiteadlane. "See võib olla miljardeid ja miljardeid e-kirju - see võib võtta väga kaua aega."

Teadlased kasutavad terminit "kohalik", et kirjeldada koode, mis kasutavad ainult murdosa kodeeritud sõnumist koha vead või parandage neid. Lihtsas korduskoodis on midagi selle kohaliku märgi laadset, kuid just see muudab selle rikkumiste suhtes haavatavaks. Lokaalselt parandatav kood seevastu saab mõlemast maailmast parima – see võib parandada mis tahes biti vea vaid mõne päringuga, kaotamata seejuures omavahelist seotust, mis muudab Reed-Solomoni koodid nii vastupidavaks.

"See on tõesti range mõiste," ütles Kothari.

Kõige kuulsamad näited kohapeal parandatavatest koodidest on auväärse veaparanduskoodi versioonid, mille matemaatikud leiutasid 1954. aastal. David Muller ja Irving Reed (kes aitas ka Reed-Solomoni koode välja töötada). Sarnaselt Reed-Salomoni koodidele kasutavad Reed-Mülleri koodid pikkade sõnumite kodeerimiseks polünoome, millele on liidetud palju termineid.

Reed-Solomoni koodides kasutatavad polünoomid hõlmavad ühte muutujat, x, seega on ainus viis terminite lisamiseks kasutada kõrgemaid võimsusi x. Selle tulemuseks on paljude vingerdamistega kõver, mida saab kinnitada vaid paljusid punkte vaadates. Reed-Mülleri koodid kasutavad selle asemel polünoome, milles iga termin võib sisaldada mitut muutujat, mis on korrutatud. Rohkem muutujaid tähendab rohkem võimalusi nende kombineerimiseks, mis omakorda pakub võimalust suurendada polünoomiliikmete arvu, tõstmata ühtegi üksikut muutujat nii kõrgele võimsusele.

Reed-Mülleri koodid on väga paindlikud. Pikemaid sõnumeid saate kodeerida, suurendades polünoomi suurimat võimsust, suurendades muutujate arvu või mõlemat. Reed-Mülleri koodi lokaalselt parandatavaks muutmiseks piirate lihtsalt iga muutuja maksimaalset võimsust väikese konstantse väärtusega ja käsitlete pikemaid sõnumeid, suurendades ainult muutujate arvu.

Konkreetselt kolme päringuga lokaalselt parandatava koodi puhul on see maksimaalne võimsus seatud väärtusele 2. Iga üksiku muutuja puhul jälgib sõnumit kodeeriv polünoom lihtsa parabooli. Selle parabooli täpse kuju määramiseks peate kõverat uurima ainult kolmes punktis. Veelgi enam, paljude muutujatega on palju selliseid paraboole, millest kõiki saab kasutada vigade parandamiseks. See teebki Reed-Mülleri koodid nii vastupidavaks.

Kahjuks on Reed-Mulleri koodil tõsine puudus: sõnumi kodeerimiseks vajalike bittide arv suureneb plahvatuslikult muutujate arvuga. Kui soovite väga lokaalset koodi, mis parandab vead vaid käputäie päringutega, vajate pikkade sõnumite jaoks palju muutujaid ja Reed-Mülleri kood muutub praktikas kiiresti kasutuks.

"Sel juhul on eksponentsiaal väga halb," ütles Dvir. Aga kas see on vältimatu?

Parandatav või dekodeeritav?

Kuna arvutiteadlased püüdsid leida tõhusamaid kohapeal parandatavaid koode, kuid neil ei õnnestunud leida, hakkasid nad kahtlustama, et sellised koodid pole üldse võimalikud. 2003. aastal kaks teadlast tõestatud et Reed-Mülleri koodi pole võimalik ületada ainult kahe päringu abil. Kuid see on nii kaugele, kui keegi on jõudnud.

"Kui lähete kolmele, muutuvad meie teadmised väga visandlikuks," ütles Kothari.

Järgmine läbimurre muudab asjad veelgi keerulisemaks. aastal avaldatud kahes artiklis 2008 ja 2009, näitasid arvutiteadlased Sergei Jehanin ja Klim Efremenko, kuidas konstrueerida kolme päringuga koode, mis olid tõhusamad kui Reed-Mülleri koodid, kuid need koodid ei olnud päris lokaalselt parandatavad. Selle asemel oli neil veidi erinev omadus, mida nimetatakse kohalikuks dekodeeritavaks.

Erinevuse mõistmiseks kujutame taas ette pilvesalvestuse pakkujat, mis ühendab kasutajate andmed üheks pikaks sõnumiks ja kaitseb neid veaparanduskoodi abil. Nii lokaalselt parandatavad koodid kui ka lokaalselt dekodeeritavad koodid võivad vaid mõne päringuga parandada vea algsõnumi mis tahes bitis.

Kuid iga veaparanduskood nõuab ka lisabitte, mida algses sõnumis ei olnud – seepärast muudab sõnumi kodeerimine selle pikemaks. Kaht tüüpi koodid erinevad selle poolest, kuidas nad neid täiendavaid bitte käsitlevad. Kohalikult dekodeeritavad koodid ei anna lubadusi nende bittide vigade parandamiseks vajalike päringute arvu kohta. Kuid lokaalselt parandatavas koodis saab viga mis tahes lisabitis parandada täpselt samamoodi nagu viga algsõnumi mis tahes bitis.

"Kõik, mida te salvestate, olgu need kasutajate algandmed või koondamisteave ja kontrolliteave – seda kõike saab kohapeal parandada," ütles ta. Madhu Sudaan, Harvardi ülikooli arvutiteadlane.

Kuigi põhimõtteliselt erinevad, tundus kohalik korrigeeritavus ja kohalik dekodeeritavus praktikas alati enne 2008. aastat omavahel asendatavad – iga teadaolev lokaalselt dekodeeritav kood oli ka lokaalselt parandatav. Jehanini ja Efremenko avastus tõstatas võimaluse, et nende kahe tingimuse vahel on põhimõtteline erinevus. Või äkki oli võimalik muuta Yekhanini ja Efremenko koode, et muuta need kohapeal parandatavaks. See seaks need kaks tingimust taas võrdseks, kuid tähendaks ka seda, et teadlased olid eksinud selles, kui tõhusad kolme päringuga kohalikult parandatavad koodid võiksid olla. Mõlemal juhul peaks tavapärane tarkus muutuma.

Laenamise loogika

Kothari ja Manohar lahendasid lõpuks selle pinge, kohandades tehnikat teisest arvutiteaduse valdkonnast: nn piirangutega rahulolu probleemide uurimisega. Õhtusöögiplaanide kooskõlastamine sõprade seltskonnaga on omamoodi piirangutega rahuloluprobleem. Igaühel on valikud, millega nad nõustuvad, ja valikud, millele nad veto panevad. Teie ülesanne on leida plaan, mis kõiki rahuldab, või kui sellist plaani pole, siis võimalikult kiiresti välja mõelda.

Nende kahe võimaliku tulemuse vahel on omane asümmeetria. Vastuvõetavat lahendust ei pruugi olla lihtne leida, kuid kui see on olemas, on lihtne teisi veenda, et see töötab. Kuid isegi kui teate, et probleem on tõesti "rahuldamatu", ei pruugi olla näidet, mis tõestaks.

2021. aastal tegid Kothari ja Manohar koos Venkatesan Guruswami California Berkeley ülikoolist suur läbimurre piirangutega rahulolu probleemide uurimisel, kasutades uut teoreetilist tehnikat nende keeruliste mitterahuldavate juhtumite tuvastamiseks. Nad kahtlustasid, et uus meetod oleks võimas tööriist ka muude probleemide lahendamiseks, ja Guruswami kraadiõppur Omar Alrabiah soovitas neil uurida kolme päringuga lokaalselt dekodeeritavaid koode.

"See oli nii-öelda haamriga nael meie käes," ütles Kothari.

Yekhanini ja Efremenko üllatavad tulemused näitasid, et kolme päringuga lokaalselt dekodeeritavad koodid võivad olla tõhusamad kui Reed-Mülleri koodid. Kuid kas nende koodid olid parimad võimalikud või võivad kolme päringuga lokaalselt dekodeeritavad koodid veelgi tõhusamaks muutuda? Kothari, Manohar, Guruswami ja Alrabiah arvasid, et nende uus tehnika võib tõestada, kui tõhusad sellised koodid võivad olla. Nende plaan oli luua loogiline valem, mis hõlmaks kõigi võimalike antud suurusega kolme päringuga lokaalselt dekodeeritavate koodide struktuuri ja tõestada, et see ei ole rahuldav, näidates sellega, et sellist koodi ei saa eksisteerida.

Neli teadlast astusid 2022. aastal esimese sammu selles suunas, seades a uus limiit kolme päringuga lokaalselt dekodeeritavate koodide maksimaalse tõhususe kohta. Tulemus ületas tunduvalt seda, mida teadlased olid suutnud teiste tehnikatega saavutada, kuid see ei välistanud kõiki koode, mis olid tõhusamad kui Jehanini ja Efremenko omad.

Kothari ja Manohar kahtlustasid, et võivad kaugemale minna. Kuid edusammud peatusid, kuni Manohar pani kirja kiire ümbriku tagumise arvutuse, mis näitas, et see tehnika võib lokaalselt parandatavate koodide puhul veelgi paremini töötada kui lokaalselt dekodeeritavate koodide puhul.

Mõni kuu hiljem, pärast paljusid valekäivitusi, mis panid nad kartma, et nad on liiga optimistlikud, täitis tehnika lõpuks oma lubaduse. Kothari ja Manohar tõestasid, et nagu teadlased kahtlustasid, on võimatu, et ükski kolme päringuga lokaalselt parandatav kood töötaks märgatavalt paremini kui Reed-Mulleri koodid. See eksponentsiaalne skaleerimine on põhiline piirang. Nende tulemus oli ka dramaatiline demonstratsioon, et kohalik korrigeeritavus ja lokaalne dekodeeritavus, ehkki pealiskaudselt sarnased, erinevad põhimõtteliselt: viimast on ühemõtteliselt lihtsam realiseerida kui esimest.

Kothari ja Manohar loodavad nüüd laiendada oma tehnikaid, et uurida koode, millel on lubatud teha rohkem kui kolm päringut, kuna praegu teatakse nendest väga vähe. Ja vigade parandamise teooria edusammud mõjutavad sageli ka teisi näiliselt mitteseotud valdkondi. Eelkõige tekitavad kohapeal parandatavad koodid kõikjal üllatusena probleemi eraandmebaaside otsingud krüptograafias kuni tõenditeni teoreemid kombinatoorikas. On liiga vara öelda, kuidas Kothari ja Manohari tehnika neid erinevaid valdkondi mõjutab, kuid teadlased on optimistlikud.

"Siin on tõesti ilus uus idee," ütles Dvir. "Ma arvan, et potentsiaali on palju."