Ускорение валидации блоков в блокчейне с помощью аккумуляторов Utreexo

Аннотация:В этой статье получатель гранта 100x Group Келвин Ким сообщает об успехах в повышении скорости начальной загрузки блоков биткоина (IBD) с помощью клиентского приложения Utreexo. Величина повышения скорости варьируется в зависимости от используемого оборудования и проблем конкретного пользователя, но в целом начальную загрузку и проверку блоков можно ускорить на 62% по сравнению с Bitcoin Core. Поскольку многие средства оптимизации еще не реализованы, ожидается, что в дальнейшем скорость загрузки еще вырастет. Келвин также рассказывает о том, как IBD можно разделить на несколько задач, которые могут выполняться несколькими компьютерами параллельно. В конечном итоге планируется реализовать Utreexo на C++ и включить его в Bitcoin Core. Хотя до этого еще далеко, реализация на C++ уже началась.

Я рад сообщить, что проект Utreexo готов поделиться своими успехами в повышении скорости полного процесса проверки блокчейна биткоина – начальной загрузки блоков (Initial Block Download, IBD). Мы завершили реализацию альфа-версии узла проверки блоков в произвольном порядке (Out of Order Block Validating Node) на базе utcd, нашего форка btcd (узла биткоина, написанного на Go), и провели сравнительное тестирование этого узла с BItcoin Core 21.0.0.

В процессе тестирования нам удалось ускорить IBD примерно на 62% по сравнению с Bitcoin Core 21.0.0 (в режиме по умолчанию) при условии отсутствия ограничений пропускной способности сети со стороны пользователя. Мы ожидаем, что по мере реализации новых средств оптимизации разница в скорости будет увеличиваться. Наш узел проверки блоков в произвольном порядке также позволяет выполнять IBD на нескольких компьютерах, что дает уникальное преимущество по сравнению с другими существующими сегодня реализациями узлов биткоина.

В ближайшее время мы опубликуем отдельный материал, в котором объясним, как выполняем проверку блоков в произвольном порядке с помощью аккумуляторов Utreexo.

Почему повышение скорости загрузки блоков важно?

Начальная загрузка блоков (IBD) — первый шаг, который должны выполнить каждый, кто хочет присоединиться к сети биткоина в роли контролера исполнения правил. Это процесс загрузки и проверки всех блоков, начиная с генезисного блока 2009 года и заканчивая сегодняшним блоком.  Проверка каждого блока чрезвычайно важна, так как не позволяет недобросовестным пользователям нарушать правила консенсуса в сети биткоина, а именно:

1. Создавать биткоин из воздуха.

2. Изменять максимальное предложение биткоина.

3. Похищать чужие монеты.

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

Поэтому предельное снижение времени IBD как входного барьера для участия в сети в качестве контролера исполнения правил будет очень полезно как для сети, так и для пользователей. Речь идет о том, чтобы все желающие могли выполнить IBD и стать контролером исполнения правил как можно быстрее и проще. Последние результаты тестирования и успехи с аккумулятором Utreexo показывают, что входной барьер для участия в сети в качестве контролера исполнения правил будет значительно снижен.

Сравнительный анализ

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

При гигабитном соединении utcd смог выполнить IBD примерно на 36% быстрее, чем Bitcoin Core v21.0.0. Мы пока не реализовали кэширование доказательств включения элементов Utreexo (Proof) в utcd, и utcd загружает примерно 900 ГБ данных. При гигабитном соединении это займет не менее 2 часов. Из проектного документа Utreexo мы знаем, что при кэшировании Utreexo Proof необходимо будет загрузить около 450~500 ГБ данных. Ниже показаны результаты того же теста IBD, но в этом случае обслуживающий узел находился на той же машине, чтобы сымитировать производительность после реализации кэширования Utreexo Proof.

Как видно из графиков, скорость загрузки повышается примерно на 62%.

Мы также провели сравнительный анализ обоих узлов с полной проверкой подписей.

Как видим, при полной проверке подписей скорость utcd падает примерно на 15%. Это связано с тем, что проверка подписей — самый проблематичный процесс, который занимает около 80% времени проверки, как показано на приведенном ниже визуальном графике.

Поскольку libsecp256k1 вызывает и utcd, и Bitcoin Core, увеличение времени загрузки на 15% вполне логично, ведь вызов Go к C (cgo) сопряжен с весьма значительным потреблением ресурсов.

И хотя в ходе моего теста аккумуляторы Utreexo не ускорили процесс IBD при проверке всех подписей, в будущем с Taproot все будет иначе. Taproot позволяет проверять все подписи в блоке группами (это связано с характером подписей Шнорра), что значительно ускоряет процесс проверки подписей. Как следствие, со временем главная проблема будет не в проверке подписей, а в возможном зависании диска. Таким образом, хотя аккумуляторы Utreexo не ускоряют процесс проверки всех подписей, мы считаем, что в будущем это изменится.

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

Сравнительный анализ начальной загрузки блоков с использованием нескольких компьютеров

Разделение общего объема работы и использование нескольких вычислительных ресурсов (центрального процессора, графического процессора, одноядерного процессора и т. д.) для одновременного выполнения работы известно как параллельные вычисления. Аккумуляторы Utreexo позволяют выполнять IBD с помощью нескольких компьютеров. В многомашинной структуре IBD есть два ключевых компонента: координатор и исполнитель.

Задача машины-координатора — отслеживать, какие блоки уже проверены. Координатор также передает еще не проверенные блоки исполнителю (или рабочему). Исполнитель получает блоки, которые нужно проверить, проверяет их и сообщает, являются ли эти блоки действительными или нет. Этот процесс продолжается до тех пор, пока все блоки в цепочке не будут проверены.

В системе должен быть только один координатор, к которому можно подключить несколько машин-исполнителей.

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

Многомашинную структуру IBD можно использовать в тех случаях, когда мы не пользуемся своими телефонами и ноутбуками. Например, можно использовать телефон в ночное время для синхронизации узла Raspberry PI. Семья также может использовать все имеющиеся у нее гаджеты в тандеме для выполнения IBD.

Ниже приведены результаты теста для структуры из двух машин, вместе выполняющих IBD.

Машина 1

Машина 2

Используя две машины, мы смогли выполнить IBD с полной проверкой подписей быстрее, чем Bitcoin Core v21.0.0.

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

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

Еслипараллельные временные затратывелики (т.е. если координация занимает много времени), это ограничивает возможности распараллеливания рабочей задачи.

В случае проверки блоков в произвольном порядкепараллельными ресурсными затратамиявляется загрузка заголовков. При гигабитном соединении загрузка заголовков заняла 4,403 секунды. Поскольку на весь процесс IBD было потрачено в общей сложности 426 минут (с полной проверкой подписей), распараллелить можно 99,982% работы. Мы можем использовать эту информацию, чтобы определить прогнозируемое максимальное ускорение процесса IBD при использовании большего количества компьютеров на основе закона Амдала.

При использовании разумного количества компьютеров с AMD Ryzen 3600 скорость будет почти идеальной (добавление каждой новой машины ускоряет процесс в 1x). Приведенный ниже линейный график хорошо это демонстрирует.

Загрузка заголовков — единственная последовательно выполняемая часть процесса IBD с использованием аккумуляторов Utreexo — необходима для обеспечения медианы прошедшего времени по транзакциям с проверкой последовательности (Check Sequence Verify)(помимо прочего). В текущей реализации  все машины, используемые в многомашинной структуре IBD, выполняют загрузку заголовков по отдельности. Мы планируем добавить эти данные в Utreexo Proof, чтобы устранить загрузку заголовков машинами-исполнителями (чтобы ее выполнял только узел-координатор). Это позволит ускорить процесс при использовании еще большего количества вычислительных ресурсов.

Ограничения проверки блоков в произвольном порядке

Поскольку процесс IBD с аккумуляторами Utreexo требует передачи дополнительных данных (около 20%), это может увеличить время, затрачиваемое на IBD пользователями, у которых есть проблемы со скоростью интернета. Но пользователи, не испытывающие проблем со скоростью  интернет-соединения и способные принять эти дополнительные 20%, очень выиграют от начальной загрузки блоков в произвольном порядке.  Мы также совершили прорыв в исследованиях аккумулятора Utreexo, который позволит значительно уменьшить количество дополнительных загружаемых данных. Подробнее об этом см. ниже, в разделе «Дальнейшая работа».

Future work

Уменьшение размера доказательств Utreexo (Utreexo Proof)

Главный недостаток аккумулятора Utreexo в том, что доказательства использования Utreexo (т.н. Proof) имеют совсем не маленький размер. Это увеличивает размер архива, который должен храниться в узле Utreexo, и повышает трафик в узлах Utreexo. Недавняя статья Болтона Бейли и Сурьянараяны Санкагири показывает, что эффективность пакетной обработки доказательств Utreexo можно повысить. В своей работе они показывают, что смогли уменьшить размер доказательств в 4,6 раза. Это сжатие позволило бы уменьшить использование места и трафика.

Тадж Дрыя уже разработал новый дизайн аккумулятора Utreexo на основе выводов, сделанных Болтоном Бейли и Сурьянараяной Санкагири. В этом году мы будем заниматься внедрением этого нового дизайна.

Прогностическое кэширование

Существующий алгоритм кэширования, рассмотренный в проектном документе Utreexo, сокращает загрузку дополнительных данных примерно на 20%. Но мы можем добиться большего, используя теоретически оптимальный алгоритм кэширования,или алгоритм «ясновидящего» (прогностического) кэширования. Этот алгоритм обычно невозможно реализовать, так как он требует осведомленности о будущих событиях. Однако в процессе IBD пиры, к которым мы подключаемся, точно знают, что произойдет дальше, поэтому этот алгоритм может быть реализован. В настоящее время над этим проектом работают Клэр Бао и Тадж Дрыя.

Реализация на C++

Конечной целью проекта Utreexo является включение функциональности аккумуляторов Utreexo в Bitcoin Core. Но поскольку референсная кодовая база аккумулятора Utreexo написана на языке Go, необходимо написать реализацию на C++. Этот проект называется libutreexo, им руководит Никлас Гёгге. Он также работает над форком Bitcoin Core с libutreexo и изучает, как вписать аккумуляторы Utreexo в кодовую базу Bitcoin Core.

Проверка моих утверждений

Код, который я использовал для выполнения сравнительных тестов, можно найти здесь: github.com/mit-dci/utcd. Информацию о том, как повторить проведенные мной тесты, см. в файле readme в репозитории.

Заключение

Возможность проверки всех блоков за всю историю блокчейна биткоина чрезвычайно важна, так как повышает безопасность как отдельных пользователей, так и сети биткоина в целом. Я считаю, что с помощью аккумуляторов Utreexo мы можем облегчить пользователям эту задачу. Хотя еще многое предстоит сделать, прежде чем эта технология попадет к конечному пользователю, мы уже достигли существенных успехов. Присоединяйтесь к нам на github.com/mit-dci/utreexo, если хотите помочь нам ускорить процесс проверки блокчейна.