Celestia: что такое parity check и как работает стирающий код
В нашей последней статье мы рассказывали, как Celestia решает проблему доступности данных. Мы сосредоточились на взаимодействии лёгкимх клиентов и полных нод, объяснили, как работает запрос доступности данных, и лишь кратко упомянули применение стирающего кода (erasure code) в Celestia.
В официальной документации можно прочитать, что Celestia использует двухмерную схему кодирования Рида-Соломона для кодирования данных в каждом блоке. Это улучшает способность сети передавать данные и снижает эффективность data withholding атак. К сожалению, это довольно продвинутая технология, и людям без бэкграунда в ИТ или математического опыта может быть сложно её понять. Именно поэтому сегодня мы хотим попробовать простыми словами объяснить что такое стирающий код, какую роль играет parity check, в общем дать вам общее представление о механизме.
Начнём с самого начала: в 1950 году Ричард Хэмминг опубликовал то, что сейчас известно как код Хэмминга — семейство методов для обнаружения и исправления ошибок в данных, которое стало основой для более сложных алгоритмов, таких как схема Рида-Соломона, используемая в Celestia. В основе кода Хэмминга лежит элементарная математика, поэтому принципы его работы можно объяснить буквально на пальцах.
Предположим, у нас есть сообщение из 16 битов, давайте представим его в виде матрицы 4x4, где каждая ячейка представляет собой один бит, который, в свою очередь, может принимать значения либо 0 либо 1. Заполним эту матрицу случайными значениями и посмотрим на неё.
Допустим, что это блок в блокчейне. Что можно сделать, чтобы light client мог убедиться, что это оригинальный блок и данные в нём не подверглись случайному или намеренному изменению? Возьмём первый бит и сделаем его ответственным за ответ на вопрос: является ли количество единиц в остальных 15 ячейках чётным или нечётным? Если количество единиц чётное, первая ячейка должна содержать 0, если нечётное — 1, таким образом в любом случае общее количество единиц во всех 16 ячейках должно быть чётным. Если пересчитать единицы из нашего примера, то можно легко убедться что их 7, поэтому мы изменяем первый бит на 1.
Отлично! Теперь light client может взглянуть на первый бит, затем посчитать количество единиц в оставшихся битах и сделать вывод о достоверности информации. Например, если первый бит содержит 0, а общее количество единиц в блоке нечётное, это явно указывает на ошибку — один из битов был изменён.
Подведём краткий итог того, чего мы достигли на данный момент. С помощью одного избыточного бита мы получили способ обнаруживать, произошла ли одна или любое нечётное количество ошибок. Кстати, этот избыточный бит называется parity bit, а процесс подсчёта единиц и сравнения их числа с битом чётности называется parity check. Следует сразу упомянуть, что этот подход не позволяет обнаружить ни конкретный бит, в котором произошла ошибка, ни ситуацию, при которой произошло две или любое чётное количество ошибок. Итак, давайте посмотрим, что можно сделать для улучшения нашей схемы.
На этом шаге нам нужно временно забыть о нашем первом parity bit и разделить биты на четыре группы, как показано на рисунке ниже.
Пусть каждая группа имеет свой parity bit, который выделен на схеме красным, и parity check для каждой группы будет эквивалентна вопросу: есть ли ошибка среди битов этой конкретной группы или нет? Если ошибка есть, последовательное выполнение parity check для всех групп позволит нам обнаружить конкретный бит с ошибкой методом исключения и после обнаружения нужно будет просто изменить его значение на противоположное, чтобы исправить. Таким образом, мы можем не только обнаружить ошибку и её местоположение, но и исправить её. Однако, следует признать, что данный подход по-прежнему не способен обнаружить любое четное количество ошибок.
На самом деле, если вы внимательно посмотрите на схему выше, вы увидите один существенный недостаток, а именно: невозможно обнаружить ошибку в самом первом бите. Действительно, последовательный parity check по всем четырем группам не дает нам никакой информации о статусе самого первого бита. Но мы можем использовать это в свою пользу: нам просто нужно объединить два предыдущих подхода, и, в дополнение к четырём группам с их собственными parity bit, использовать первый бит в качестве глобального parity bit для всего блока. Теперь, если глобальный parity check не обнаружил ошибку, но parity check в четырёх группах обнаружили её, это означает, что произошло две или любое другое чётное количество ошибок.
В итоге у нас есть схема, которая способна обнаруживать любое количество ошибок. Если ошибка только одна, её место можно легко идентифицировать а саму ошибку исправить. Однако цена этого — сокращение пространства памяти для основной информации: вместо 16 битов мы используем только 11, а 5 parity bit служат для избыточности.
Теперь, когда мы поняли концепцию parity, давайте кратко рассмотрим схему Рида-Соломона, используемую Celestia. Этот алгоритм основан на более сложной математике, чем то, что мы видели до сих пор в этой статье, поэтому мы объясним его общими словами. Код Рида-Соломона преобразует сообщение длиной k символов в более длинное сообщение длиной n символов, где n > k. Можно считать эти дополнительные символы эквивалентными parity bit в коде Хэмминга, но это более мощный алгоритм, и он разработан таким образом, чтобы исходное сообщение можно было восстановить из любого подмножества n символов. Другими словами, если m = n - k, и вы потеряли вплоть до m символов (оставив как минимум n символов), сообщение можно полностью восстановить.
А что это за сообщение из k символов? Можно представить его как сложную математическую функцию. Эта функция, как и любая другая, имеет график и формулу, и эту формулу можно извлечь, выполнив определённые математические операции с нашим первоначальным сообщением из n символов. Но интересная особенность схемы Рида-Соломона заключается в том, что эта формула может быть точно также восстановлена из любых n символов нашего расширенного сообщения с избыточными символами длинной k, используя методы интерполяции. Таким образом, если мы потеряли несколько битов, но всё ещё можем восстановить формулу, мы просто выполняем вычисления и восстанавливаем потерянные биты, решая математическое уравнение.
Вот и всё, чем мы хотели с вами поделиться. Надеемся, вам было интересно. Если эта тема вас заинтересовала, рекомендуем ознакомиться с официальной документацией Celestia и с её white paper. Если у вас есть дополнительные вопросы, не стесняйтесь обращаться к нам в чат — мы всегда рады помочь!
Желаем удачи и успешного стейкинга!