«Волшебная» схема исправления ошибок оказалась по своей сути неэффективной | Журнал Кванта

Если вы когда-либо отправляли текстовое сообщение, проигрывали компакт-диск или сохраняли файл в облаке, вы получили пользу от исправления ошибок. Эта революционная идея восходит к 1940-м годам, когда исследователи впервые поняли, что можно переписать любое сообщение в форме, позволяющей легко обратить вспять последующие искажения.

За прошедшие годы исследователи разработали множество изобретательных схем, называемых кодами исправления ошибок, которые кодируют данные разными способами и используют разные процедуры для исправления ошибок. Но для ученых-теоретиков в области информатики немногие из них являются столь же привлекательными, как так называемые локально корректируемые коды. Эти коды одновременно обладают двумя свойствами, которые кажутся почти противоречивыми: любую ошибку можно исправить, прочитав закодированные данные всего в нескольких местах, но ни один злоумышленник не сможет помешать этой процедуре исправления, выборочно подделав код. Это как если бы вы могли восстановить любую страницу, вырванную из книги, просто взглянув на несколько других.

«Это совершенно волшебное явление», — сказал Том Гур, ученый-компьютерщик из Кембриджского университета. «Априори неочевидно, что такой математический объект вообще может существовать».

Но за это волшебство приходится платить высокую цену. Единственные известные примеры локально корректируемых кодов крайне неэффективны — кодирование любого сообщения также делает его экспоненциально длиннее. Целые книги, закодированные таким образом, были бы слишком громоздкими.

Ученые-компьютерщики уже давно задаются вопросом, возможны ли лучшие локально корректируемые коды. Особое внимание они уделили кодам, которые используют только три запроса для исправления любой ошибки, надеясь, что это строгое ограничение облегчит понимание этих кодов. Но даже этот простой случай ставит исследователей в тупик уже более 20 лет.

Теперь ученый-компьютерщик Правеш Котари из Университета Карнеги-Меллон и его аспирант Питер Манохар наконец доказанный что невозможно создать локально корректируемый код из трех запросов, который бы избежал таких экспоненциальных затрат. Это может быть отрицательный результат, но все, что проясняет пределы исправления ошибок, интересно исследователям, особенно потому, что математика локально корректируемых кодов возникает в областях, далеких от связи.

«Этот результат потрясающий», — сказал Шубханги Сараф, ученый-компьютерщик из Университета Торонто. «Это огромный прорыв».

Сила в цифрах

Чтобы понять, как исправлять ошибки, представьте себе данные, которые вы хотите защитить, как последовательность битов или 0 и 1. Ошибкой в ​​этой модели может быть любое нежелательное изменение 0 на 1 или наоборот, независимо от того, вызвано ли это случайным колебанием или преднамеренным вмешательством.

Предположим, вы хотите отправить сообщение другу, но опасаетесь, что ошибки могут изменить его значение. Одна из простых стратегий — заменить каждый 0 в вашем сообщении на 000, а каждую 1 — на 111. Если ваш друг увидит часть сообщения, которая не содержит трех одинаковых битов подряд, он поймет, что произошла ошибка. А если ошибки случайны и относительно редки, то любая строка из 110 с гораздо большей вероятностью будет искаженным 111, чем искаженным 000. Простого большинства голосов внутри каждого триплета будет достаточно для исправления большинства ошибок.

Эта схема, называемая кодом повторения, отличается простотой, но ее мало что можно рекомендовать. Во-первых, требуется утроить длину каждого сообщения только для того, чтобы справиться с относительно редкими ошибками, а если существует приличная вероятность появления двух соседних ошибок, нам понадобится еще большая избыточность. Хуже того, он быстро становится бесполезным, если ошибки не являются случайными, например, когда злоумышленники активно пытаются саботировать код. В коде повторения вся информация, необходимая для исправления данного бита, хранится всего в нескольких других битах, что делает его уязвимым для целенаправленной атаки.

К счастью, многие коды, исправляющие ошибки, работают лучше. Один известный пример, названный Код Рида-Соломона, работает путем преобразования сообщений в полиномы — математические выражения, такие как x² + 3x + 2, которые состоят из разных терминов, сложенных вместе, каждый из которых имеет переменную (например, x) возведен в другую степень. Кодирование сообщения с помощью кода Рида-Соломона включает в себя построение полинома с одним членом для каждого символа сообщения, затем построение полинома в виде кривой на графике и сохранение координат точек, лежащих на кривой (принимая как минимум еще одну точки, чем количество символов). Ошибки могут сместить некоторые из этих точек с кривой, но если ошибок не слишком много, через большинство точек пройдет только одна полиномиальная кривая. Эта кривая почти наверняка соответствует истинному сообщению.

Коды Рида-Соломона сверхэффективны: для исправления ошибок нужно сохранить всего несколько дополнительных точек, поэтому любое закодированное сообщение лишь незначительно длиннее исходного. Они также менее уязвимы к целенаправленным нарушениям, которые могут привести к катастрофе для кода повторения, поскольку информация, используемая для исправления ошибки в любом месте, распределяется по всему закодированному сообщению.

Мыслить глобально действовать локально

Сила кодекса Рида-Соломона проистекает из взаимосвязанности. Но именно из-за этой взаимосвязанности невозможно исправить ни единой ошибки в закодированном сообщении, не прочитав его целиком. В контексте общения это может не показаться проблемой: если вы отправляете сообщение, вы, вероятно, хотите, чтобы получатель прочитал его все. Но это может стать проблемой при хранении данных — еще одно важное применение исправления ошибок.

Рассмотрим компанию, которая хранит электронную почту пользователей в облаке, то есть на огромном количестве серверов. Вы можете думать обо всей коллекции электронных писем как об одном длинном сообщении. Теперь предположим, что один сервер выходит из строя. Используя код Рида-Соломона, вам придется выполнить масштабные вычисления, включающие все закодированные данные, чтобы восстановить ваши электронные письма с этого единственного потерянного сервера. «Вам придется все посмотреть», — сказал Зеев Двир, ученый-компьютерщик из Принстонского университета. «Это могут быть миллиарды и миллиарды электронных писем — это может занять очень много времени».

Исследователи используют термин «локальный» для описания кодов, которые используют только часть закодированного сообщения для выявлять ошибки или исправить их. В простом коде повторения есть что-то от локального характера, но именно это делает его столь уязвимым для взлома. Локально исправляемый код, напротив, берет лучшее из обоих миров — он может исправить ошибку в любом бите всего за несколько запросов, и все это без потери взаимосвязанности, которая делает коды Рида-Соломона такими устойчивыми.

«Это действительно строгое понятие», — сказал Котари.

Самыми известными примерами локально исправимых кодов являются версии почтенного кода, исправляющего ошибки, изобретенного математиками в 1954 году. Дэвид Мюллер и Ирвинг Рид (который также участвовал в разработке кодов Рида-Соломона). Как и коды Рида-Соломона, коды Рида-Мюллера используют полиномы со множеством членов, сложенных вместе, для кодирования длинных сообщений.

Полиномы, используемые в кодах Рида-Соломона, включают одну переменную: x, поэтому единственный способ добавить больше членов — это использовать более высокие степени x. В результате получается кривая со множеством изгибов, которую можно определить, только рассмотрев множество точек. Вместо этого в кодах Рида-Мюллера используются полиномы, в которых каждый член может содержать несколько переменных, умноженных вместе. Больше переменных означает больше способов их объединения, что, в свою очередь, дает возможность увеличить количество полиномиальных членов без возведения какой-либо отдельной переменной в такие высокие степени.

Коды Рида-Мюллера очень гибки. Вы можете кодировать более длинные сообщения, увеличивая максимальную степень полинома, увеличивая количество переменных или и то, и другое. Чтобы сделать код Рида-Мюллера локально корректируемым, вы просто ограничиваете максимальную степень каждой переменной небольшим постоянным значением и обрабатываете более длинные сообщения, увеличивая только количество переменных.

В частности, для локально корректируемого кода с тремя запросами эта максимальная степень устанавливается равной 2. Тогда, что касается каждой отдельной переменной, полином, кодирующий сообщение, очерчивает простую параболу. Чтобы определить точную форму этой параболы, вам нужно всего лишь изучить кривую в трех точках. Более того, при многих переменных существует множество таких парабол, любую из которых можно использовать для исправления ошибок. Вот что делает коды Рида-Мюллера такими устойчивыми.

К сожалению, у кода Рида-Мюллера есть серьезный недостаток: количество битов, необходимых для кодирования сообщения, увеличивается экспоненциально с увеличением количества переменных. Если вам нужен высоколокальный код, который исправляет ошибки с помощью всего лишь нескольких запросов, вам понадобится много переменных для длинных сообщений, и код Рида-Мюллера быстро станет бесполезным на практике.

«Экспонента в данном случае — это очень плохо», — сказал Двир. Но неизбежно ли это?

Исправимое или декодируемое?

Поскольку учёные-компьютерщики безуспешно пытались найти более эффективные локально корректируемые коды, они начали подозревать, что такие коды вообще невозможны. В 2003 году два исследователя доказанный что невозможно обойти код Рида-Мюллера, используя только два запроса. Но это все, что кто-либо мог сделать.

«Как только вы дойдете до трех, наши знания станут очень отрывочными», — сказал Котари.

Следующий прорыв еще больше усложнил ситуацию. В двух статьях, опубликованных в 2008 и 2009Ученые-компьютерщики Сергей Еханин и Клим Ефременко показали, как создавать трехзапросные коды, которые были более эффективными, чем коды Рида-Мюллера, но эти коды не были полностью локально корректируемыми. Вместо этого у них было немного другое свойство, называемое локальной декодируемостью.

Чтобы понять разницу, давайте снова представим себе поставщика облачного хранилища, который объединяет данные пользователей в одно длинное сообщение и защищает их с помощью кода, исправляющего ошибки. Как локально корректируемые коды, так и локально декодируемые коды могут исправить ошибку в любом бите исходного сообщения всего за несколько запросов.

Но каждый код, исправляющий ошибки, также требует дополнительных битов, которых не было в исходном сообщении — поэтому кодирование сообщения делает его длиннее. Два типа кодов различаются тем, как они обрабатывают эти дополнительные биты. Локально декодируемые коды не дают никаких обещаний относительно количества запросов, необходимых для исправления ошибок в этих битах. Но в локально корректируемом коде ошибка в любом из дополнительных битов может быть исправлена ​​точно так же, как ошибка в любом бите исходного сообщения.

«Все, что вы храните, будь то исходные данные пользователей или избыточность и проверочная информация — все это можно исправить локально», — заявили. Мадху Судан, ученый-компьютерщик из Гарвардского университета.

До 2008 года локальная корректируемость и локальная декодируемость, хотя и различались в принципе, на практике всегда казались взаимозаменяемыми — каждый известный локально декодируемый код был также локально корректируемым. Открытие Еханина и Ефременко выявило возможность фундаментального различия между этими двумя состояниями. Или, возможно, можно было модифицировать коды Еханина и Ефременко, чтобы сделать их локально корректируемыми. Это снова поставило бы эти два условия в равное положение, но это также означало бы, что исследователи ошиблись в отношении того, насколько эффективными могут быть трехзапросные локально корректируемые коды. В любом случае общепринятое мнение придется изменить.

Заимствование логики

Котари и Манохар наконец разрешили это противоречие, адаптировав метод из другой области информатики: исследования так называемых проблем удовлетворения ограничений. Попытка согласовать планы ужина с группой друзей — это своего рода проблема удовлетворения ограничений. У каждого есть выбор, который он примет, и выбор, на который он наложит вето. Ваша задача — либо найти план, который удовлетворит всех, либо, если такого плана нет, придумать его как можно скорее.

Между этими двумя возможными исходами существует присущая асимметрия. Возможно, найти приемлемое решение непросто, но как только оно у вас появится, легко убедить кого-то еще, что оно сработает. Но даже если вы знаете, что проблема действительно «неразрешима», возможно, не существует примера, подтверждающего это.

В 2021 году Котари и Манохар вместе с Венкатесаном Гурусвами из Калифорнийского университета в Беркли сделали крупный прорыв в исследовании проблем удовлетворения ограничений с использованием новой теоретической техники для выявления сложных невыполнимых случаев. Они подозревали, что новый метод станет мощным инструментом и для решения других проблем, и аспирант Гурусвами Омар Алрабия предложил им рассмотреть локально декодируемые трехзапросные коды.

«Это был, так сказать, гвоздь с молотком в руке», — сказал Котари.

Неожиданные результаты Еханина и Ефременко показали, что локально декодируемые трехзапросные коды могут быть более эффективными, чем коды Рида-Мюллера. Но были ли их коды лучшими из возможных, или же локально декодируемые по трем запросам коды могли бы стать еще более эффективными? Котари, Манохар, Гурусвами и Алрабия думали, что их новая техника сможет доказать пределы эффективности таких кодов. Их план состоял в том, чтобы построить логическую формулу, охватывающую структуру всех возможных трехзапросных локально декодируемых кодов заданного размера, и доказать ее невыполнимость, тем самым показав, что такой код не может существовать.

Четверо исследователей сделали первый шаг в этом направлении в 2022 году, установив новый лимит о максимальной эффективности трехзапросных локально декодируемых кодов. Результат значительно превосходил то, чего исследователям удалось достичь с помощью других методов, но не исключал все коды, более эффективные, чем коды Еханина и Ефременко.

Котари и Манохар подозревали, что могут пойти дальше. Но прогресс застопорился до тех пор, пока Манохар не сделал быстрый предварительный расчет, показывающий, что этот метод может работать даже лучше для локально корректируемых кодов, чем для локально декодируемых.

Несколько месяцев спустя, после еще многих фальстартов, заставивших их опасаться, что они были слишком оптимистичны, метод наконец оправдал свои обещания. Котари и Манохар доказали, что, как и подозревали исследователи, невозможно, чтобы любой локально корректируемый код с тремя запросами работал заметно лучше, чем коды Рида-Мюллера. Это экспоненциальное масштабирование является фундаментальным ограничением. Их результат также стал яркой демонстрацией того, что локальная корректируемость и локальная декодируемость, хотя и внешне схожи, на самом деле различаются на фундаментальном уровне: последнее однозначно легче реализовать, чем первое.

Котари и Манохар теперь надеются расширить свои методы для изучения кодов, которым разрешено выполнять более трех запросов, поскольку сейчас о них известно очень мало. А прогресс в теории исправления ошибок часто имеет последствия в других, казалось бы, несвязанных областях. В частности, локально корректируемые коды повсюду неожиданно появляются в задаче поиск в частной базе данных в криптографии к доказательствам теоремы комбинаторики. Пока слишком рано говорить о том, как методика Котари и Манохара повлияет на эти различные области, но исследователи настроены оптимистично.

«Здесь есть действительно красивая новая идея», — сказал Двир. «Я думаю, что здесь есть большой потенциал».