Как сжать Биткойн

Питер Чиппер (Peter Tschipper) проводит очень скрупулёзные исследования на тему того, как можно сжать данные при их передаче в Биткойн-сети. Если удалось бы как следует сжать содержимое Биткойн-транзакции, то это дало бы увеличение эффективности путем принятия сетью блоков большего размера (в количестве байтов на блок), и при этом, размер отправляемых блоков остался бы на сравнительно низком уровне.

Безрадостный Вывод

Но на текущий момент результаты Питера не слишком вдохновляют. Он говорит о 30% инфляции (под «инфляцией» здесь подразумевается, что пакеты после сжатия получаются больше, чем несжатые. Это нормально, когда размер данных, взятых для компрессии, слишком мал) для пакетов размером в 1 килобайт. Для пакетов относительно большего размера в 1-2 MB удалось достичь достаточно скромного сжатия в 30%.

Почему Биткойн не сжимается лучше

Я думаю, что эти проблемы происходят от выбора семейства типовых компрессионных алгоритмов Лемпеля — Зива — Велча (далее LZ).

Хотя я и не знаю, какие конкретно движки сжатия Питер испытывал в каждом конкретном случае, алгоритмы компрессии LZ, как правило, основаны на «компрессионных таблицах». По сути, они назначают короткий уникальный номер каждой новой подпоследовательности, с которой они сталкиваются. И когда алгоритм вновь встречают такую последовательность, как «ab» в «abcdfdcdabcdfabcdf», он заменяет её коротким целым числом (скажем, в данном случае, 9-битной константой 256). Таким образом, взятая для примера последовательность превратится в «abcdfd<258 для cd><256 для ab><258 для cd>f<261 для abc><259 для df>», что значительно меньше, чем оригинальная последовательность. Обратите внимание, что последовательность «abc» была добавлена в таблицу только после того, как она дваджы была обнаружена во входных данных.

Все это замечательно, и прекрасно работает для текста на английском, где определенные последовательности букв (например, «th», «the», «thi», и т.п.) часто повторяются, равно как и для сжатия текста на русском, где наиболее часто повторяемые слова «и, не, в, что, он, я, на, с, она, как, но, его, это, к, а, все, её, было, так, же, то» и т.д, но это ни в какое сравнение не идет с тем, какого сжатия можно достичь на основе двоичных данных. Есть возможность для гораздо лучшего сжатия благодаря структуре использования определенных последовательностей байт в протоколе проведения транзакций Биткойна.

Возможность для лучшего сжатия

В процессе проведения транзакции можно наблюдать несколько связанных транзакций, которые перебрасывают монеты между определенными адресами, и, следовательно, происходит повторное использование 20-байтных адресов отправителей и получателей. Или же, можно видеть, как проходит 200-байтная транзакция, следом за которой идет точно такая же транзакция, включаемая в тот же самый блок. В идеале, хотелось бы заранее узнать о последовательностях, которые повторятся позже, и заменить их коротким числом, которое ссылалось бы на длинную последовательность. Если бы мы знали, что «abcdf» это та последовательность, которая повторится с большой вероятностью, можно было бы включить её в компрессионную таблицу целиком, вместо того, чтобы полагаться на повторение перед тем, как последовательность символов попадет в таблицу. Это позволило бы сжать первоначальную цепочку до «abcdfd<257 для cd><256 для abcdf><256 для abcdf>» с самого начала.

При этом, известные мне варианты компрессии LZ, потребовали бы повторения 200-байтной последовательности 199 раз перед тем, как создать единую 200-байтную последовательность в компрессионной таблице, которую впоследствии можно было бы использовать.

Таким образом, Биткойн-компресор может работать значительно лучше, но будет ли это лучше на самом деле? Давайте рассмотрим обе стороны монеты:

Аргументы Против

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

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

Аргументы За

Природа LZ компрессоров наводит меня на мысль, что можно было бы достичь гораздо более высокого сжатия, если сделать специальный компрессор, который бы учитывал специфику Биткойна. Навскидку, я бы сказал, что возможна двухкратная степень сжатия, а в некоторых случаях может быть даже и больше. Я основываю это мнение на том, что транзакции иногда передаются дважды — первый раз при распространении в сети, второй раз уже в составе блока. В некотором смысле, идея «O(1) распространении блока«, не так давно предложенная Гэвином, может рассматриваться как яркий пример компрессора, заточенного под Биткойн, хотя она и накладывает ограничения на порядок транзакций в блоке.

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

Как это сделать

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

Автор: Emin Gün Sirer

Источник: Hacking, Distributed