„Magiczny” schemat korekcji błędów okazał się z natury nieskuteczny | Magazyn Quanta

Jeśli kiedykolwiek wysłałeś wiadomość tekstową, odtworzyłeś płytę CD lub zapisałeś plik w chmurze, skorzystałeś z korekcji błędów. Początki tego rewolucyjnego pomysłu sięgają lat czterdziestych XX wieku, kiedy badacze po raz pierwszy zdali sobie sprawę, że każdy przekaz można przepisać w formie umożliwiającej łatwe odwrócenie późniejszego zepsucia.

Na przestrzeni lat badacze opracowali wiele genialnych schematów, zwanych kodami korekcji błędów, które kodują dane na różne sposoby i wykorzystują różne procedury do naprawiania błędów. Jednak dla informatyków-teoretycznych niewiele z nich jest tak przekonujących jak tak zwane kody poprawialne lokalnie. Kody te mają dwie jednoczesne właściwości, które wydają się niemal sprzeczne: każdy błąd można skorygować, czytając zakodowane dane w zaledwie kilku miejscach, jednak żaden atakujący nie jest w stanie udaremnić tej procedury korekty poprzez selektywne manipulowanie kodem. To tak, jakbyś mógł odzyskać dowolną stronę wyrwaną z książki, po prostu rzucając okiem na kilka innych.

„To dość magiczne zjawisko” – powiedział Tomek Gur, informatyk na Uniwersytecie w Cambridge. „A priori nie jest oczywiste, że taki obiekt matematyczny w ogóle może istnieć”.

Ale ta magia ma wysoką cenę. Jedyne znane przykłady kodów, które można lokalnie poprawić, są wyjątkowo nieefektywne — kodowanie dowolnej wiadomości również wydłuża ją wykładniczo. Całe książki zakodowane w ten sposób byłyby zbyt nieporęczne.

Informatycy od dawna zastanawiali się, czy możliwe są lepsze, lokalnie korygowane kody. Skoncentrowali się szczególnie na kodach, które wykorzystują tylko trzy zapytania do poprawienia dowolnego błędu, mając nadzieję, że to poważne ograniczenie ułatwi zrozumienie tych kodów. Ale nawet ten prosty przypadek wprawia badaczy w zakłopotanie od ponad 20 lat.

Teraz informatyk Pravesh Kothari z Carnegie Mellon University i jego absolwentem Piotr Manohar w końcu okazały że nie jest możliwe zbudowanie lokalnie poprawialnego kodu składającego się z trzech zapytań, który pozwoliłby uniknąć wykładniczych kosztów. Może to być wynik negatywny, ale wszystko, co wyjaśnia granice korekcji błędów, jest ekscytujące dla badaczy, zwłaszcza że matematyka kodów lokalnie korygowanych pojawia się w obszarach odległych od komunikacji.

„Ten wynik jest niesamowity” – powiedział Shubhangi Saraf, informatyk na Uniwersytecie w Toronto. „To ogromny przełom”.

Siła w liczbach

Aby zrozumieć korekcję błędów, wyobraź sobie dane, które chcesz chronić, jako sekwencję bitów, czyli zer i jedynek. W tym modelu błędem może być dowolna zamiana 0 na 1 lub odwrotnie, niezależnie od tego, czy jest to spowodowane przypadkową fluktuacją, czy celową manipulacją.

Załóżmy, że chcesz wysłać wiadomość do znajomego, ale obawiasz się, że błędy mogą zmienić jej znaczenie. Prostą strategią jest zastąpienie każdego 0 w wiadomości liczbą 000 i każdej 1 liczbą 111. Jeśli Twój znajomy zobaczy część wiadomości, która nie zawiera trzech identycznych bitów z rzędu, będzie wiedział, że wystąpił błąd. A jeśli błędy są losowe i stosunkowo rzadkie, wówczas istnieje znacznie większe prawdopodobieństwo, że dowolny ciąg 110 będzie uszkodzonym numerem 111 niż uszkodzonym 000. Do skorygowania większości błędów wystarczy zwykła większość głosów w każdej trójce.

Schemat ten, zwany kodem powtórzeń, ma tę zaletę, że jest prostotą, ale nie ma nic więcej, co by go polecał. Po pierwsze, wymaga to potrojenia długości każdej wiadomości, aby poradzić sobie ze stosunkowo rzadkimi błędami, a jeśli istnieje przyzwoite prawdopodobieństwo wystąpienia dwóch sąsiadujących ze sobą błędów, będziemy potrzebować jeszcze większej redundancji. Co gorsza, szybko staje się bezużyteczny, jeśli błędy nie są przypadkowe, na przykład gdy atakujący aktywnie próbują sabotować kod. W kodzie powtórzeń wszystkie informacje potrzebne do poprawienia danego bitu są przechowywane w zaledwie kilku innych bitach, przez co jest on podatny na ukierunkowany atak.

Na szczęście wiele kodów korygujących błędy radzi sobie lepiej. Jeden znany przykład, tzw Kod Reeda-Solomona, działa poprzez przekształcanie wiadomości w wielomiany — wyrażenia matematyczne, takie jak x² + 3x + 2, które składają się z różnych terminów dodanych do siebie, każdy ze zmienną (np x) podniesione do innej potęgi. Kodowanie wiadomości przy użyciu kodu Reeda-Solomona polega na zbudowaniu wielomianu zawierającego jeden wyraz dla każdego znaku wiadomości, następnie wykreśleniu wielomianu w postaci krzywej na wykresie i zapisaniu współrzędnych punktów leżących na krzywej (biorąc pod uwagę co najmniej jeszcze jeden punkt niż liczba znaków). Błędy mogą wypchnąć kilka z tych punktów z krzywej, ale jeśli nie ma ich zbyt wiele, tylko jedna krzywa wielomianowa przejdzie przez większość punktów. Ta krzywa prawie na pewno odpowiada prawdziwemu przesłaniu.

Kody Reeda-Solomona są niezwykle wydajne — wystarczy zapisać kilka dodatkowych punktów, aby poprawić błędy, dzięki czemu zakodowana wiadomość jest tylko nieznacznie dłuższa od oryginału. Są także mniej podatne na tego rodzaju ukierunkowane zakłócenia, które mogłyby oznaczać katastrofę dla kodu powtórzeń, ponieważ informacje użyte do skorygowania błędu w dowolnym miejscu są rozproszone w całej zakodowanej wiadomości.

Myśl globalnie, działaj lokalnie

Siła kodu Reeda-Solomona wynika z wzajemnych powiązań. Ale właśnie z powodu tych wzajemnych powiązań nie ma możliwości naprawienia pojedynczego błędu w zakodowanej wiadomości bez przeczytania całości. Może to nie wydawać się problemem w kontekście komunikacji: jeśli wysyłasz wiadomość, prawdopodobnie chcesz, aby odbiorca przeczytał ją w całości. Może to jednak stanowić wyzwanie w przechowywaniu danych — kolejne ważne zastosowanie korekcji błędów.

Weźmy pod uwagę firmę, która przechowuje e-maile użytkowników w chmurze, czyli na szerokiej gamie serwerów. Możesz pomyśleć o całej kolekcji e-maili jako o jednej długiej wiadomości. Załóżmy teraz, że jeden serwer ulega awarii. W przypadku kodu Reeda-Solomona konieczne byłoby wykonanie ogromnych obliczeń obejmujących wszystkie zakodowane dane, aby odzyskać wiadomości e-mail z tego jednego utraconego serwera. „Trzeba byłoby przyjrzeć się wszystkiemu” – powiedział Zeew Dwir, informatyk na Uniwersytecie Princeton. „Mogą to być miliardy e-maili – może to zająć naprawdę dużo czasu”.

Badacze używają terminu „lokalny” do opisania kodów wykorzystujących tylko ułamek zakodowanej wiadomości wykryj błędy lub je popraw. Prosty kod powtórzeń ma coś z lokalnego charakteru, ale właśnie to czyni go tak podatnym na manipulacje. Z kolei lokalnie poprawialny kod wykorzystuje to, co najlepsze z obu światów — może skorygować dowolny błąd za pomocą zaledwie kilku zapytań, a wszystko to bez utraty wzajemnych powiązań, które sprawiają, że kody Reeda-Solomona są tak odporne.

„To naprawdę rygorystyczne pojęcie” – powiedział Kothari.

Najbardziej znanymi przykładami kodów poprawialnych lokalnie są wersje czcigodnego kodu korygującego błędy wynalezionego w 1954 roku przez matematyków Davida Müllera i Irvinga Reeda (który pomógł także opracować kody Reeda-Solomona). Podobnie jak kody Reeda-Solomona, kody Reeda-Mullera wykorzystują wielomiany z wieloma terminami dodanymi do siebie w celu kodowania długich wiadomości.

Wielomiany stosowane w kodach Reeda-Solomona obejmują pojedynczą zmienną, x, więc jedynym sposobem na dodanie większej liczby terminów jest użycie wyższych potęg x. Powoduje to powstanie krzywej z wieloma drganiami, którą można unieruchomić jedynie patrząc na wiele punktów. Zamiast tego kody Reeda-Mullera wykorzystują wielomiany, w których każdy termin może zawierać wiele zmiennych pomnożonych przez siebie. Więcej zmiennych oznacza więcej sposobów ich łączenia, co z kolei umożliwia zwiększenie liczby wyrazów wielomianowych bez podnoszenia jakiejkolwiek indywidualnej zmiennej do tak dużych potęg.

Kody Reeda-Mullera są bardzo elastyczne. Możesz kodować dłuższe wiadomości, zwiększając najwyższą potęgę pojawiającą się w wielomianu, zwiększając liczbę zmiennych lub jedno i drugie. Aby umożliwić lokalną korekcję kodu Reeda-Mullera, wystarczy ograniczyć maksymalną moc każdej zmiennej do małej stałej wartości i obsługiwać dłuższe komunikaty, zwiększając tylko liczbę zmiennych.

W szczególności w przypadku kodu, który można lokalnie korygować z trzema zapytaniami, maksymalna moc jest ustawiona na 2. Następnie, jeśli chodzi o każdą indywidualną zmienną, wielomian kodujący komunikat wyznacza prostą parabolę. Aby określić dokładny kształt tej paraboli, wystarczy zbadać krzywą w trzech punktach. Co więcej, przy wielu zmiennych istnieje wiele takich paraboli, z których każdą można wykorzystać do skorygowania błędów. To właśnie sprawia, że ​​kody Reeda-Mullera są tak odporne.

Niestety kod Reeda-Mullera ma poważną wadę: liczba bitów wymaganych do zakodowania wiadomości rośnie wykładniczo wraz z liczbą zmiennych. Jeśli potrzebujesz wysoce lokalnego kodu, który koryguje błędy za pomocą zaledwie kilku zapytań, będziesz potrzebować wielu zmiennych dla długich wiadomości, a kod Reeda-Mullera szybko stanie się bezużyteczny w praktyce.

„Wykładniczy w tym przypadku jest bardzo zły” – powiedział Dvir. Ale czy jest to nieuniknione?

Korygowalne czy dekodowalne?

Ponieważ informatycy próbowali znaleźć skuteczniejsze, lokalnie poprawialne kody, ale nie udało im się to, zaczęli podejrzewać, że takie kody w ogóle nie są możliwe. W 2003 roku dwóch badaczy okazały że nie da się pokonać kodu Reeda-Mullera za pomocą tylko dwóch zapytań. Ale to tyle, ile ktokolwiek może osiągnąć.

„Gdy dojdziesz do trzech, nasza wiedza staje się bardzo pobieżna” – powiedział Kothari.

Następny przełom tylko jeszcze bardziej skomplikował sprawę. W dwóch artykułach opublikowanych w 2008 i 2009informatycy Siergiej Jechanin i Klim Efremenko pokazali, jak konstruować kody składające się z trzech zapytań, które były bardziej wydajne niż kody Reeda-Mullera, ale kody te nie dawały się w pełni lokalnie poprawić. Zamiast tego mieli nieco inną właściwość zwaną lokalną dekodowalnością.

Aby zrozumieć różnicę, wyobraźmy sobie ponownie dostawcę usług przechowywania w chmurze, który łączy dane użytkowników w jedną długą wiadomość i chroni je za pomocą kodu korygującego błędy. Zarówno kody lokalnie poprawialne, jak i kody lokalnie dekodowane mogą skorygować błąd w dowolnym fragmencie oryginalnej wiadomości za pomocą zaledwie kilku zapytań.

Jednak każdy kod korygujący błędy wymaga również dodatkowych bitów, których nie było w oryginalnej wiadomości — dlatego kodowanie wiadomości wydłuża ją. Te dwa typy kodów różnią się sposobem traktowania tych dodatkowych bitów. Lokalnie dekodowane kody nie obiecują liczby zapytań potrzebnych do skorygowania błędów w tych bitach. Jednak w kodzie, który można lokalnie poprawić, błąd w dowolnym z dodatkowych bitów można naprawić dokładnie w taki sam sposób, jak błąd w dowolnym fragmencie oryginalnej wiadomości.

„Wszystko, co przechowujesz, niezależnie od tego, czy są to oryginalne dane użytkowników, czy informacje o nadmiarowości i kontroli, wszystko to można poprawić lokalnie” – powiedział Madhu Sudan, informatyk na Uniwersytecie Harvarda.

Choć w zasadzie są różne, lokalna poprawność i lokalna dekodowalność zawsze wydawały się w praktyce wymienne przed 2008 rokiem — każdy znany lokalnie dekodowany kod był również lokalnie poprawiany. Odkrycie Jechanina i Efremenko podniosło możliwość istnienia zasadniczej różnicy między tymi dwoma warunkami. A może dałoby się zmodyfikować kody Jechanina i Efremenko, aby umożliwić ich lokalną korektę. To ponownie postawiłoby te dwa warunki na równi, ale oznaczałoby również, że badacze mylili się co do wydajności, jaką mogą uzyskać lokalnie poprawiane kody składające się z trzech zapytań. Tak czy inaczej, konwencjonalna mądrość musiałaby się zmienić.

Logika pożyczania

Kothari i Manohar ostatecznie rozwiązali to napięcie, adaptując technikę z innego obszaru informatyki: badania tak zwanych problemów spełniania ograniczeń. Próba skoordynowania planów obiadowych z grupą przyjaciół to pewnego rodzaju problem z zaspokojeniem ograniczeń. Każdy ma wybór, który zaakceptuje i który zawetuje. Twoim zadaniem jest albo znaleźć plan, który zadowoli wszystkich, albo, jeśli takiego planu nie ma, opracować go tak szybko, jak to możliwe.

Istnieje nieodłączna asymetria pomiędzy tymi dwoma możliwymi wynikami. Znalezienie akceptowalnego rozwiązania może nie być łatwe, ale gdy już je znajdziesz, łatwo będzie przekonać innych, że zadziała. Ale nawet jeśli wiesz, że problem naprawdę jest „niezadowalający”, może nie istnieć przykład stanowiący dowód.

W 2021 roku Kothari i Manohar wraz z Venkatesanem Guruswamim z Uniwersytetu Kalifornijskiego w Berkeley przeprowadzili badanie duży przełom w badaniu problemów spełniania ograniczeń przy użyciu nowej teoretycznej techniki identyfikacji trudnych, niezadowalających przypadków. Podejrzewali, że nowa metoda będzie potężnym narzędziem do rozwiązywania również innych problemów, a absolwent Guruswamiego, Omar Alrabiah, zasugerował, aby przyjrzeć się lokalnie dekodowanym kodom składającym się z trzech zapytań.

„To był gwóźdź z młotkiem w naszej dłoni”, powiedział Kothari.

Zaskakujące wyniki Jechanina i Efremenko pokazały, że lokalnie dekodowane kody składające się z trzech zapytań mogą być bardziej wydajne niż kody Reeda-Mullera. Ale czy ich kody były najlepsze z możliwych, czy też kody lokalnie dekodowane z trzema zapytaniami mogły stać się jeszcze bardziej wydajne? Kothari, Manohar, Guruswami i Alrabiah uważali, że ich nowa technika może wykazać ograniczenia wydajności takich kodów. Ich plan polegał na zbudowaniu logicznej formuły obejmującej strukturę wszystkich możliwych lokalnie dekodowanych z trzech zapytań kodów o danym rozmiarze i udowodnieniu jej niespełnialności, pokazując w ten sposób, że taki kod nie mógłby istnieć.

Czterech badaczy zrobiło pierwszy krok w tym kierunku w 2022 r., ustanawiając nowy limit na maksymalnej wydajności lokalnie dekodowanych kodów z trzema zapytaniami. Wynik znacznie wykraczał poza to, co badacze byli w stanie osiągnąć za pomocą innych technik, ale nie wykluczył wszystkich kodów skuteczniejszych niż Jechanin i Efremenko.

Kothari i Manohar podejrzewali, że mogą pójść dalej. Jednak postęp utknął w martwym punkcie, dopóki Manohar nie zanotował szybkich obliczeń z tyłu koperty, wskazujących, że technika ta może działać jeszcze lepiej w przypadku kodów poprawialnych lokalnie niż w przypadku kodów lokalnie dekodowanych.

Kilka miesięcy później, po wielu falstartach, które wzbudziły w nich obawę, że byli zbyt optymistyczni, technika w końcu spełniła swoje obietnice. Kothari i Manohar udowodnili, że tak jak podejrzewali badacze, żaden lokalnie poprawialny kod składający się z trzech zapytań nie może działać znacznie lepiej niż kody Reeda-Mullera. To wykładnicze skalowanie jest podstawowym ograniczeniem. Ich wynikiem było także dramatyczne wykazanie, że lokalna poprawność i lokalna dekodowalność, choć z pozoru podobne, w rzeczywistości różnią się na poziomie podstawowym: to drugie jest niewątpliwie łatwiejsze do zrealizowania niż pierwsze.

Kothari i Manohar mają teraz nadzieję rozszerzyć swoje techniki na badanie kodów, które mogą wykonywać więcej niż trzy zapytania, ponieważ obecnie niewiele o nich wiadomo. Postęp w teorii korekcji błędów często ma implikacje w innych pozornie niezwiązanych dziedzinach. W szczególności kody, które można lokalnie poprawić, zaskakują wszędzie wokół problemu przeszukiwanie prywatnych baz danych w kryptografii do dowodów twierdzenia w kombinatoryce. Jest zbyt wcześnie, aby powiedzieć, jak technika Kothariego i Manohara wpłynie na te różne dziedziny, ale badacze są optymistami.

„To naprawdę piękny nowy pomysł” – powiedział Dvir. „Myślę, że jest duży potencjał”.