A „mágikus” hibajavító séma eredendően nem hatékonynak bizonyult | Quanta Magazin

Ha valaha is küldött szöveges üzenetet, lejátszott egy CD-t vagy tárolt egy fájlt a felhőben, akkor a hibajavítás előnyeit élvezte. Ez a forradalmi ötlet az 1940-es évekre nyúlik vissza, amikor a kutatók először rájöttek, hogy bármilyen üzenetet át lehet írni olyan formában, hogy a későbbi korrupció könnyen visszafordítható legyen.

Az évek során a kutatók számos ötletes sémát, úgynevezett hibajavító kódot fejlesztettek ki, amelyek különböző módon kódolják az adatokat, és különböző eljárásokat alkalmaznak a hibák kijavítására. Az elméleti informatikusok számára azonban kevés olyan meggyőző, mint az úgynevezett lokálisan javítható kód. Ezeknek a kódoknak két egyidejű tulajdonsága van, amelyek szinte ellentmondásosnak hangzanak: Bármilyen hiba kijavítható a kódolt adatok néhány helyen történő leolvasásával, de egyetlen támadó sem tudja meghiúsítani ezt a javítási eljárást a kód szelektív manipulálásával. Mintha egy könyvből kiszakadt oldalakat vissza tudnánk állítani, ha csak néhány másik oldalra pillantunk.

„Ez egy egészen varázslatos jelenség” – mondta Tom Gur, a Cambridge-i Egyetem informatikusa. "A priori nem nyilvánvaló, hogy ilyen matematikai objektum egyáltalán létezhet."

De ennek a varázslatnak óriási ára van. A helyileg javítható kódok egyetlen ismert példája rendkívül hatástalan – bármilyen üzenet kódolása is exponenciálisan meghosszabbítja azt. Az így kódolt teljes könyvek túlságosan nehézkesek lennének.

Az informatikusok régóta azon töprengenek, hogy lehetséges-e jobb helyileg javítható kód. Különösen azokra a kódokra összpontosítottak, amelyek csak három lekérdezést használnak a hibák kijavításához, remélve, hogy ez a súlyos korlátozás megkönnyítheti a kódok megértését. De még ez az egyszerű eset is több mint 20 éve zavarja a kutatókat.

Most az informatikus Pravesh Kothari a Carnegie Mellon Egyetemről és végzős hallgatójáról Manohar Péter végre bizonyított hogy lehetetlen három lekérdezésből álló, helyileg javítható kódot építeni, amely elkerüli azt az exponenciális költséget. Lehet, hogy negatív eredmény, de minden, ami tisztázza a hibajavítás határait, izgalmas a kutatók számára, különösen azért, mert a lokálisan javítható kódok matematikája felbukkan a kommunikációtól távol eső területeken.

"Ez az eredmény csodálatos" - mondta Shubhangi Saraf, a Torontói Egyetem informatikusa. – Ez óriási áttörés.

A számok erőssége

A hibajavítás megértéséhez képzelje el a védeni kívánt adatokat bitek sorozataként vagy 0-ként és 1-ként. Ebben a modellben hiba lehet a 0 bármilyen nem kívánt átváltása 1-be vagy fordítva, akár véletlenszerű ingadozás, akár szándékos manipuláció miatt.

Tegyük fel, hogy üzenetet szeretne küldeni egy barátjának, de attól tart, hogy a hibák megváltoztathatják a jelentését. Egy egyszerű stratégia az, hogy az üzenetben minden 0-t 000-ra, 1-et pedig 111-re cserél. Ha barátja olyan részt lát az üzenetben, amely nem tartalmaz egymás után három azonos bitet, akkor tudni fogja, hogy hiba történt. És ha a hibák véletlenszerűek és viszonylag ritkák, akkor minden 110-es karakterlánc sokkal nagyobb valószínűséggel lesz sérült 111, mint hibás 000. A legtöbb hiba kijavításához elegendő egy egyszerű többségi szavazat mindegyik hármasban.

Ennek az ismétlési kódnak nevezett sémának megvan az egyszerűsége, de nem sok mást ajánlunk. Egyrészt minden üzenet hosszának megháromszorozása szükséges ahhoz, hogy a viszonylag ritkán előforduló hibákat kezeljük, és ha megfelelő esély van két szomszédos hibára, akkor még több redundanciára lesz szükségünk. Ami még rosszabb, gyorsan használhatatlanná válik, ha a hibák nem véletlenszerűek, például amikor a támadók aktívan megpróbálják szabotálni a kódot. Az ismétlési kódban az adott bit kijavításához szükséges összes információ csak néhány másik bitben van eltárolva, így ki van téve egy célzott támadásnak.

Szerencsére sok hibajavító kód jobban teljesít. Egy híres példa, az úgynevezett Reed-Solomon kód, úgy működik, hogy az üzeneteket polinomokká alakítja – olyan matematikai kifejezések, mint pl x² + 3x + 2, amelyek különböző kifejezésekből állnak össze, mindegyik változóval (pl x) más hatalomra emelve. Egy üzenet kódolása Reed-Solomon kóddal azt jelenti, hogy az üzenet minden karakteréhez egy-egy tagot tartalmazó polinomot készítünk, majd a polinomot görbeként ábrázoljuk egy grafikonon, és eltároljuk a görbén lévő pontok koordinátáit (legalább még egyet figyelembe véve). ponttal, mint a karakterek száma). A hibák néhány pontot letolhatnak a görbéről, de ha nincs túl sok hiba, akkor a legtöbb ponton csak egy polinomgörbe megy át. Ez a görbe szinte biztosan megfelel az igaz üzenetnek.

A Reed-Solomon kódok rendkívül hatékonyak – csak néhány plusz pontot kell tárolnia a hibák kijavításához, így a kódolt üzenetek csak kis mértékben hosszabbak az eredetinél. Kevésbé sebezhetőek az olyan célzott zavarokkal szemben is, amelyek katasztrófát okoznának az ismétlődő kódnál, mivel a hiba kijavításához használt információ bárhol eloszlik a teljes kódolt üzenetben.

Gondolj globálisan, helyi szinten járjon el

A Reed-Solomon kód ereje az összekapcsolódásból fakad. De éppen ennek az összekapcsolódásnak köszönhetően nincs mód arra, hogy egyetlen hibát is kijavítsunk egy kódolt üzenetben anélkül, hogy az egészet elolvasnánk. Lehet, hogy ez nem hangzik problémának a kommunikáció kontextusában: Ha üzenetet küld, valószínűleg azt szeretné, hogy a címzett elolvassa az egészet. Ez azonban kötelezettséget jelenthet az adattárolás során – ez a hibajavítás egy másik fő alkalmazása.

Vegyünk egy olyan vállalatot, amely a felhasználók e-mailjeit a felhőben tárolja – vagyis a szerverek széles skáláján. Az e-mailek egész gyűjteményét egyetlen hosszú üzenetnek tekintheti. Tegyük fel, hogy az egyik szerver összeomlik. A Reed-Solomon kóddal hatalmas számítást kell végrehajtania, amely magában foglalja az összes kódolt adatot, hogy visszaszerezze e-mailjeit az elveszett szerverről. – Mindent meg kellene nézned – mondta Zeev Dvir, a Princetoni Egyetem informatikusa. "Ez több milliárd és milliárd e-mailt jelenthet – ez nagyon hosszú ideig tarthat."

A kutatók a „helyi” kifejezést használják olyan kódok leírására, amelyek a kódolt üzenetnek csak egy töredékét használják fel helyszíni hibák vagy javítsa ki őket. Az egyszerű ismétlődő kódban van valami ebből a helyi karakterből, de pontosan ez teszi annyira sebezhetővé a manipulációval szemben. Ezzel szemben a helyileg javítható kód mindkét világból a legjobbat hozza ki – néhány lekérdezéssel bármely bitben kijavíthat egy hibát, mindezt anélkül, hogy elveszítené azt az összekapcsolódást, amely a Reed-Solomon kódokat olyan rugalmassá teszi.

„Ez egy nagyon szigorú fogalom” – mondta Kothari.

A helyileg javítható kódok leghíresebb példái a matematikusok által 1954-ben feltalált tiszteletreméltó hibajavító kód változatai. David Muller és a Irving Reed (aki szintén segített a Reed-Solomon kódok kidolgozásában). A Reed-Solomon kódokhoz hasonlóan a Reed-Muller kódok is polinomokat használnak sok kifejezéssel a hosszú üzenetek kódolásához.

A Reed-Solomon kódokban használt polinomok egyetlen változót tartalmaznak, x, így az egyetlen módja annak, hogy több kifejezést adjunk hozzá, az az, hogy magasabb hatványait használjuk x. Ennek eredményeként egy görbe sok ingadozással jár, amelyet csak sok pontra nézve lehet rögzíteni. A Reed-Muller kódok ehelyett polinomokat használnak, amelyekben minden tag több változót is tartalmazhat, összeszorozva. A több változó több módot jelent ezek kombinálására, ami viszont lehetőséget kínál a polinomiális tagok számának növelésére anélkül, hogy az egyes változókat ilyen nagy hatványokra emelnénk.

A Reed-Muller kódok nagyon rugalmasak. A hosszabb üzeneteket a polinomban megjelenő legnagyobb teljesítmény növelésével, a változók számának növelésével vagy mindkettővel kódolhatja. A Reed-Muller kód helyileg javíthatóvá tételéhez egyszerűen korlátozza az egyes változók maximális teljesítményét egy kis állandó értékre, és a hosszabb üzeneteket csak a változók számának növelésével kezeli.

Egy három lekérdezésből álló, helyileg javítható kód esetében ez a maximális teljesítmény 2-re van beállítva. Ekkor az egyes változókat illetően az üzenetet kódoló polinom egy egyszerű parabolát nyom ki. A parabola pontos alakjának meghatározásához csak három ponton kell megvizsgálni a görbét. Ráadásul sok változónál sok ilyen parabola létezik, amelyek bármelyike ​​felhasználható a hibák kijavítására. Ez teszi a Reed-Muller kódokat olyan rugalmassá.

Sajnos a Reed-Muller kódnak van egy komoly hátránya: Az üzenet kódolásához szükséges bitek száma exponenciálisan növekszik a változók számával. Ha egy erősen lokális kódot szeretne, amely csak néhány lekérdezéssel javítja ki a hibákat, akkor sok változóra lesz szüksége a hosszú üzenetekhez, és a Reed-Muller kód gyorsan használhatatlanná válik a gyakorlatban.

„Az exponenciális ebben az esetben nagyon rossz” – mondta Dvir. De vajon elkerülhetetlen?

Javítható vagy dekódolható?

Ahogy az informatikusok megpróbáltak hatékonyabb, helyileg javítható kódokat találni, de nem sikerült nekik, gyanakodni kezdtek, hogy ilyen kódok egyáltalán nem lehetségesek. 2003-ban két kutató bizonyított hogy nincs mód a Reed-Muller kód legyőzésére csak két lekérdezéssel. De idáig mindenki eljutott.

„Ha háromra megyünk, a tudásunk nagyon vázlatossá válik” – mondta Kothari.

A következő áttörés csak tovább bonyolítja a dolgokat. ben megjelent két közleményben 2008 és a 2009Szergej Jehanin és Klim Efremenko informatikusok megmutatták, hogyan lehet három lekérdezésből álló kódokat létrehozni, amelyek hatékonyabbak voltak, mint a Reed-Muller kódok, de ezek a kódok nem voltak teljesen helyileg javíthatók. Ehelyett volt egy finoman eltérő tulajdonságuk, az úgynevezett helyi dekódolhatóság.

Hogy megértsük a különbséget, képzeljünk el ismét egy felhőalapú tárolási szolgáltatót, amely egyetlen hosszú üzenetben egyesíti a felhasználók adatait, és hibajavító kóddal védi azokat. Mind a helyileg javítható kódok, mind a helyileg dekódolható kódok néhány lekérdezéssel kijavíthatják az eredeti üzenet bármely bitjének hibáját.

De minden hibajavító kódhoz olyan extra bitekre is szükség van, amelyek nem voltak az eredeti üzenetben – ezért az üzenet kódolása meghosszabbítja azt. A két kódtípus különbözik abban, hogy hogyan kezelik ezeket a további biteket. A lokálisan dekódolható kódok nem tesznek ígéretet a bitek hibáinak kijavításához szükséges lekérdezések számával kapcsolatban. De egy lokálisan javítható kódban az extra bitek bármelyikének hibája pontosan ugyanúgy javítható, mint az eredeti üzenet bármely bitjének hibája.

„Minden, amit tárol, legyen az a felhasználók eredeti adatai, vagy a redundancia és a csekkinformációk – mindez helyben javítható” – mondta. Madhu Szudán, a Harvard Egyetem informatikusa.

Bár elvileg eltérőek voltak, a helyi javíthatóság és a helyi dekódolhatóság a gyakorlatban mindig felcserélhetőnek tűnt 2008 előtt – minden ismert lokálisan dekódolható kód helyileg is javítható volt. Jehanin és Efremenko felfedezése felvetette a két feltétel közötti alapvető különbség lehetőségét. Vagy talán lehetséges volt Jehanin és Efremenko kódjait úgy módosítani, hogy azok helyileg javíthatóak legyenek. Ez ismét egyenrangúvá tenné a két feltételt, de azt is jelentené, hogy a kutatók tévedtek azzal kapcsolatban, hogy a három lekérdezésből álló, helyileg javítható kódok milyen hatékonyak lehetnek. Akárhogy is, a hagyományos bölcsességnek meg kell változnia.

Logika kölcsönzése

Kothari és Manohar végül úgy oldotta fel ezt a feszültséget, hogy a számítástechnika egy másik területéről származó technikát adaptált: az úgynevezett kényszer-elégedettségi problémák tanulmányozását. A vacsoraterveket egy baráti társasággal egyeztetni egyfajta kényszer-elégedettségi probléma. Mindenkinek vannak választási lehetőségei, amelyeket elfogad, és olyan döntéseket, amelyeket megvétóz. Az Ön feladata, hogy vagy olyan tervet találjon, amely mindenkit kielégít, vagy ha nincs ilyen, akkor a lehető leghamarabb kitalálja.

A két lehetséges eredmény között eredendő aszimmetria van. Lehet, hogy nem könnyű elfogadható megoldást találni, de ha egyszer megvan, könnyű meggyőzni másokat arról, hogy működni fog. De még ha tudod is, hogy a probléma valóban „kielégíthetetlen”, előfordulhat, hogy nincs olyan példa, amely bizonyítaná.

2021-ben Kothari és Manohar Venkatesan Guruswamival, a Kaliforniai Egyetemről (Berkeley) közösen készített egy jelentős áttörés a kényszer-elégedettségi problémák tanulmányozásában egy új elméleti technikát alkalmazva azon bonyolult, kielégíthetetlen esetek azonosítására. Azt gyanították, hogy az új módszer más problémák megoldására is hatékony eszköz lesz, és Guruswami végzős hallgatója, Omar Alrabiah azt javasolta, hogy nézzenek meg három lekérdezésből álló, helyileg dekódolható kódokat.

„Ez egy szög volt kalapáccsal a kezünkben, hogy úgy mondjam” – mondta Kothari.

Yekhanin és Efremenko meglepő eredményei azt mutatták, hogy a három lekérdezéssel helyileg dekódolható kódok hatékonyabbak lehetnek, mint a Reed-Muller kódok. De vajon a kódjaik a lehető legjobbak voltak, vagy a három lekérdezéssel helyileg dekódolható kódok még hatékonyabbak lehetnek? Kothari, Manohar, Guruswami és Alrabiah úgy gondolta, hogy új technikájuk képes bizonyítani az ilyen kódok hatékonyságának korlátait. Az volt a tervük, hogy olyan logikai képletet hoznak létre, amely magában foglalja az összes lehetséges, három lekérdezéssel helyileg dekódolható, adott méretű kód struktúráját, és bebizonyítják, hogy ez nem kielégítő, ezzel megmutatva, hogy ilyen kód nem létezhet.

A négy kutató 2022-ben tette meg az első lépést ebbe az irányba, és a új limit a három lekérdezéssel helyileg dekódolható kódok maximális hatékonyságáról. Az eredmény jóval meghaladta azt, amit a kutatók más technikákkal el tudtak érni, de nem zárta ki az összes Jehaninnál és Efremenkónál hatékonyabb kódot.

Kothari és Manohar gyanította, hogy tovább tudnak menni. A fejlődés azonban megtorpant, amíg Manohar feljegyzett egy gyors, a boríték hátulsó számítását, jelezve, hogy a technika még jobban működhet a helyileg javítható kódoknál, mint a helyileg dekódolható kódoknál.

Néhány hónappal később, sok újabb hamis indítás után, amelyek attól tartottak, hogy túl optimisták, a technika végül beváltotta ígéretét. Kothari és Manohar bebizonyította, hogy ahogy a kutatók gyanították, lehetetlen, hogy bármely három lekérdezésből álló, helyileg javítható kód érezhetően jobban működjön, mint a Reed-Muller kódok. Ez az exponenciális skálázás alapvető korlát. Eredményük annak is drámai bizonyítéka volt, hogy a lokális javíthatóság és a lokális dekódolhatóság bár felületesen hasonló, de alapvetően különbözik egymástól: az utóbbi egyértelműen könnyebben megvalósítható, mint az előbbi.

Kothari és Manohar most azt reméli, hogy kiterjeszthetik technikáikat olyan kódok tanulmányozására, amelyek háromnál több lekérdezést hajthatnak végre, mivel jelenleg nagyon keveset tudunk róluk. A hibajavítás elméletének fejlődése pedig gyakran más, látszólag nem kapcsolódó területekre is kihat. Különösen a helyileg javítható kódok okoznak meglepetést mindenütt a problémából privát adatbázis keresések kriptográfiában a bizonyítékokig tételek a kombinatorikában. Túl korai még megmondani, hogy Kothari és Manohar technikája milyen hatással lesz ezekre a különböző területekre, de a kutatók optimisták.

„Van itt egy nagyon szép új ötlet” – mondta Dvir. – Szerintem bőven van benne lehetőség.