Фонтанные коды

Original author: Nick Johnson
  • Translation
Сегодня поговорим о фонтанных кодах. Их ещё называют «кодами нефиксированной скорости». Фонтанный код позволяет взять, например, какой-нибудь файл, и преобразовать его в практически неограниченное количество закодированных блоков. Имея некоторое подмножество этих блоков, можно восстановить исходный файл, при условии, что размер этого подмножества немного превышает размер файла. Другими словами, такой код позволяет создавать «фонтан» из кодируемых данных. Получатель может восстановить исходные данные, собрав достаточно «капель» из фонтана, при этом неважно – какие именно «капли» у него есть, и какие именно он пропустил.


Замечательное свойство фонтанных кодов заключается в том, что их применение позволяет отправлять данные по ненадёжным каналам связи, например – через интернет, не полагаясь на знание уровня потери пакетов, и не требуя от получателя связываться с отправителем для восстановления недостающих фрагментов данных. Легко заметить, что подобные возможности окажутся весьма кстати во множестве ситуаций. Среди них, например, отправка информации по широковещательным каналам связи, как в системах передачи видео по запросу. К той же категории задач относится работа протокола Bittorrent и других подобных, когда фрагменты файла распространяются среди большого количества пиров.

Основные принципы


Может показаться, что фонтанные коды должны быть устроены ужасно сложно. Но это вовсе не так. Существуют разные реализации этого алгоритма, мы предлагаем начать с самой простой из них. Это – так называемый код преобразования Лаби, сокращённо его обычно называют LT-кодом, от Luby Transform Сode. При использовании этого варианта фонтанных кодов блоки кодируют так:

  1. Выбирают из диапазона 1 — k случайное число d. Диапазон соответствует количеству блоков в файле. Ниже мы поговорим о том, как лучше всего выбрать d.

  2. Выбирают случайным образом d блоков файла и комбинируют их. В нашем случае хорошо подойдёт операция XOR.

  3. Передают полученный на предыдущем шаге блок вместе с информацией о том, из каких блоков он был создан.

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

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

Процедура декодирования немного сложнее, хотя она тоже достаточно проста.

  1. Восстановить список исходных блоков, которые были использованы для создания закодированного блока.

  2. Для каждого исходного блока из этого списка, если уже его декодировали, произвести операцию XOR с закодированным блоком и убрать его из списка исходных блоков.

  3. Если в списке остались как минимум два исходных блока, добавить закодированный блок в область временного хранения.

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

0x48 0x65 0x6C 0x6C 0x6F, world!


Рассмотрим пример декодирования для того, чтобы лучше во всём разобраться. Предположим, мы получили пять закодированных блоков, каждый – длиной один байт. Так же получены сведения о том, из каких исходных блоков каждый из них сконструирован. Эти данные можно представить в виде графа.


Граф, представляющий полученные данные

Узлы слева представляют собой полученные закодированные блоки. Узлы справа – исходные блоки. Первый из полученных блоков, 0x48, как оказалось, сформирован при участии лишь одного исходного блока, первого. Таким образом, мы уже знаем, что это был за блок. Переходя в обратном направлении по стрелкам, указывающим на первый исходный блок, видим, что второй и третий закодированные блоки зависят только от первого исходного блока и от одного другого. А, так как первый исходный блок уже известен, можем произвести над полученными блоками и первым исходным блоком операцию XOR и раскодировать ещё несколько блоков.


Продолжение декодирования сообщения

Повторяя снова ту же самую процедуру, можно заметить, что теперь известно достаточно для декодирования четвёртого блока, который зависит от второго и третьего исходных блоков, каждый из которых уже раскодирован. Выполнение над ними операции XOR позволяет найти пятый, то есть, последний в списке исходные блок, что показано на рисунке ниже.


Декодированный пятый исходный блок

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


Полностью декодированное сообщение

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

Об идеальном распределении


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

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

Вот, вкратце, как работают фонтанные коды, и, в частности, LT-коды. Надо сказать, что LT-коды – это наименее эффективные из известных фонтанных кодов, но они – и самые простые для понимания.

Пиринговые сети и проблема доверия


Прежде чем мы окончим этот разговор, вот ещё одна мысль. Фонтанные коды могут выглядеть идеально для систем вроде Bittorrent, позволяя сидам генерировать и распространять практически неограниченное количество блоков, более или менее исключая проблему «последнего блока» в случаях, когда сидов немного, и обеспечивая то, что два случайно выбранных пира практически всегда обладают полезной информацией, которой могут друг с другом обмениваться. Однако, тут есть одна важная проблема. Дело в том, что очень сложно проверить данные, полученные от пиров.

Пиринговые протоколы используют функции безопасного хеширования, вроде SHA1, при этом доверенная сторона, создатель раздачи, предоставляет список достоверных хешей всем пирам. Каждый пир, пользуясь этими данными, может проверить загружаемые фрагменты файла. Однако, при использовании фонтанных кодов подобная схема работы усложняется. Нет способа вычислить, например, хеш SHA1 закодированного фрагмента, даже зная хеши отдельных фрагментов, которые приняли участие в его формировании. И мы не можем доверять другим пирам вычисление этого хеша за нас, так как они могут попросту нас обмануть. Мы можем подождать, пока соберём весь файл, а затем, пользуясь списком неправильных фрагментов, можем попытаться найти неверные закодированные фрагменты, но это сложно и ненадёжно. К тому же, при таком подходе, найти ошибки можно только в финале сборки файла, то есть – это, скорее всего, займёт слишком много времени. Одна из возможных альтернатив заключается в том, чтобы создатель раздачи опубликовал открытый ключ и подписывал каждый сгенерированный блок. Таким образом мы можем проверить закодированные блоки, но и тут есть серьёзный минус. Дело в том, что только создатель раздачи может генерировать правильные блоки, а значит мы сразу же теряем большинство преимуществ использования фонтанных кодов. Кажется, тут мы зашли в тупик. Однако, имеются альтернативы, например, весьма хитроумная схема, называемая гомоморфным хешированием. Хотя и она не идеальна.

Заключение


Мы рассказали об основах фонтанных кодов. Разновидности этого алгоритма нашли практическое применение в тех областях, где его достоинства однозначно перевешивают недостатки. Если эта тема вас заинтересовала и вы хотите в неё углубиться, почитайте этот материал по фонтанным кодам. Кроме того, полезно будет ознакомиться с Raptor-кодами, которые, немного усложняя LT-коды, значительно улучшают их эффективность. Благодаря их использованию можно снизить объёмы передаваемых данных и вычислительную сложность алгоритма.

О, а приходите к нам работать? :)
wunderfund.io — молодой фонд, который занимается высокочастотной алготорговлей. Высокочастотная торговля — это непрерывное соревнование лучших программистов и математиков всего мира. Присоединившись к нам, вы станете частью этой увлекательной схватки.

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

Присоединяйтесь к нашей команде: wunderfund.io
Wunder Fund
0.00
Мы занимаемся высокочастотной торговлей на бирже
Share post
AdBlock has stolen the banner, but banners are not teeth — they will be back

More
Ads

Comments 14

    0
    Получатель может восстановить исходные данные, собрав достаточно «капель» из фонтана, при этом неважно – какие именно «капли» у него есть, и какие именно он пропустил.
    Но в примере как минимум один блок идёт чистый. Сработает ли система при потере него?
      0
      Меня тоже смутило слово «достаточно капель»,
      И кажется мне что для скачивания всего файла целиком, если допустить потерю 10% блоков, нужно будет гораздо больше данных передать.
        0
        Собственно необходимую избыточность, естественно, тоже никто не отменял. Однако для начала нужно как-то декодировать это без сильных повреждений. Если при потере маленького кусочка мы теряем весь файл — это скорее получается система простого уничтожения данных.
        Вообще идея напоминает чем-то голографическое кодирование, когда всё перемешано со всем (условно говоря). Только там огромная избыточность была, как и во всех системах с возможностью восстановления.
          +1
          Видимо оно находит применение в сетях, гда данные только в одну сторону передаются. Без обратной связи. Там данные передаются непрерывно и покругу. К примеру teletext в телевизоре. Если бы данные просто, без кодирования передавались, то в случае потери одного блока пришлось бы ждать пока этот блок не передадут снова. В случае с фонтаном кодов вероятность того, что этот же блок участвовал в кодировании какого то другого блока выше и тем самым выше вероятность, что данные будут полученны раньше чем за два цикла передачи.
        0
        Чем это отличается от кодов Рида-Соломона?
          0
          Википедия о Tornado code говорит, что в сравнении с кодами Рида-Соломона он менее эффективен по памяти, но процессы устранения ошибок и генерации(кодов, не ошибок) проходят быстрее. В свою очередь, фонтанный код (или коды) является развитием кода торнадо(торнадного кода, трудности перевода), сохраняя, надо полагать, отличия от кодов Рида-Соломона.
          +1
          Эх, я тут ожидал увидеть инфу о работе над ПО для винницкого фонтана (на заглавном фото)
            +1
            Аналогично :)
            +1
            Зашел, не прочитав превью, с мыслями «О, наконец-то узнаю, как там внутри работает!»(на первом фото — Винницкий фонтан, вдвойне интересно было узнать о достопримечательности родного города), а тут эта… отличная статья. Отдельное спасибо за рассмотренный пример, реально помог лучше понять всю суть происходящего.

            З.Ы. Спасибо за раунд на Codeforces, хоть он и был 4 месяца назад.
              0
              приходите к нам работать? :)
              мы — молодой фонд, который занимается высокочастотной алготорговлей.

              Понятно, идём дальше.
                0
                Интересный подход, между прочим! Сколько читал про всякое шифрование (включая стеганографию), но про фонтаны слышу впервые.
                Ведь это прекрасный способ общаться без влезания спец-служб: отправляем мылом один фрагмент, другой скачиваем с файлопомойки, третий лежит на известном форуме, четвёртый с пастебина и вуаля — письмо! Немного геморно, конечно, но если посылаешь частную информацию (напр., где живут родственники, номера счетов) — имеет смысл страховаться.
                  0
                  Проще тогда ключ (пароль) разбить на части и отправить разными каналами, а файл зашифровать и отправить самым быстрым методом. Один зашифрованный файл привлечет внимания меньше, чем четыре.
                    0
                    Все 4 файла будут отправлены с разных мест, в каждом случае наблюдатель увидит только один покоцаный файл, и только тотальная слежка поможет увидеть весь процесс целиком.

                    4-й файл может быть доставлен голубиной или даже обычной почтой в виде телеграммы.
                      0
                      QR код в разделе частных объявлений Times. :) *вспоминая Холмса*

                Only users with full accounts can post comments. Log in, please.