Проверка блоков в произвольном порядке с помощью аккумуляторов Utreexo

Аннотация. В этой статье получатель гранта BitMEX Келвин Ким объясняет, почему порядок проверки (валидации) блоков не имеет значения при использовании технологии Utreexo. Снимки неизрасходованных выходов (UTXO) практичны, так как экономят место на диске, что, в свою очередь, позволяет распараллелить проверку блоков в блокчейне биткоина. Келвин объясняет, что проверить действительность входящей транзакции можно, проверив доказательство включения элементов аккумулятора (Proof), что избавляет от необходимости обращаться к набору UTXO. Это позволяет узлам Utreexo устранить необходимость обращения к диску, вместо этого увеличив объем хэширования, что может стать отличным компромиссом. В заключение Келвин рассказывает, как технология Utreexo может изменить наше представление о проверке блоков.

В отдельном материале мы привели сравнительные результаты, показывающие ускорение проверки блоков блокчейна на нашем узле, использующем аккумуляторы Utreexo, по сравнению с Bitcoin Core v21.0.0. Нам удалось это сделать благодаря параллельной проверке блоков с помощью аккумуляторов Utreexo.

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

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

Аккумуляторы Utreexo представляют собой разновидность деревьев Меркла. Их интерфейс состоит из четырех действий: «добавить», «удалить», «доказать», «подтвердить». Вы можете добавлять и удалять элементы из аккумуляторов Utreexo, а также генерировать доказательство использования элемента аккумулятора (Proof), чтобы доказать пользователю, что такой элемент существует. Другой пользователь может проверить это доказательство. Все эти действия можно выполнять, используя только корни всех деревьев Меркла, которые мы называем корнями Utreexo. Более подробную информацию можно найти в проектной документации Utreexo.

Если узел блокчейна биткоина использует аккумуляторы Utreexo, сохранять набор UTXO нет необходимости. Вместо этого можно просто сохранить корни Utreexo, так как для проверки нужны только они. Желающие потратить UTXO должны предоставить всего две вещи. Во-первых, доказательство использования аккумулятора, содержащее все элементы, необходимые для хэширования корней Utreexo. Во-вторых, данные UTXO, подтверждающие, что они могут потратить UTXO (главным образом это цифровые подписи). Мы называем эту информацию доказательством Utreexo Proof.

Доказательство Utreexo Proof для хэша 0-0 в приведенном выше дереве будет таким: Hash 0-0, Hash 0-1, Hash 1. Чтобы проверить это доказательство, мы делаем следующее:

  1. Переводим Hash 0-0 и Hash 0-1 в SHA256 и получаем Hash 0
  2. Переводим Hash 0 (который мы вычислили) и Hash 1 в SHA256, чтобы получить корень.
  3. Проверяем, совпадает ли полученный с помощью вычислений корень с сохраненным корнем. Если корни не совпадают, то доказательство Utreexo Proof неверно, и мы отклоняем транзакцию.
  4. Проверяем все данные UTXO. Если какие-либо данные недействительны или недопустимы, доказательство Utreexo Proof неверно, и мы отклоняем транзакцию.

Как проверить один блок с помощью аккумуляторов Utreexo?

Для проверки одного блока с помощью аккумуляторов Utreexo необходимые следующие данные:

  1. Данные самого блока.
  2. Доказательства Utreexo Proof всех UTXO, которые расходуются в блоке.
  3. Корни набора UTXO.

Мы получаем данные блока от пиров. В этом случае мы также получаем доказательство Utreexo Proof для полученного блока. Действительность блока зависит (помимо прочих правил консенсуса) от действительности всех транзакций в этом блоке.

Действительность одной транзакции узла Utreexo зависит от действительности доказательства Utreexo Proof, которое состоит из двух элементов:

  1. Действительность доказательства использования аккумулятора.
  2. Действительность цифровой подписи, доказывающей, что вы владеете одним или несколькими UTXO.

Обратите внимание, что элемент (1) другой. В текущих узлах блокчейна биткоина нужно было проверить наличие определенного UTXO в наборе UTXO. Это требует обращения к диску. В узлах с Utreexo нужно просто проверить доказательство использования аккумулятора и убедиться в его действительности. Для этого требуется хэширование SHA256. Обратите внимание: использование аккумуляторов Utreexo позволяет заменить обращение к диску хэшированием SHA256 (это важно!).

Аккумуляторы Utreexo устраняют необходимость обращения к диску путем увеличения объема хэширования SHA256 во время проверки tx.

Этот просто фантастическое достижение, ведь хэширование SHA256 можно выполнить очень быстро. Это занимает гораздо меньше времени, чем обращение к диску (даже при использовании самых быстрых дисков от NVMe), которое можно ускорить лишь незначительно.

Изменение представления о проверке блокчейна

Многие считают, что блокчейн — это место, где хранятся все монеты, которые можно потратить. Но это не совсем так. Информация, необходимая для проверки нового блока или транзакции, заложена в наборе UTXO. На самом деле, полнорежимные узлы биткоина, в которых удаляются старые, ненужные данные блока, уже существуют. Они называются «обрезанными» (pruned) узлами.

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

Если блок биткоина — это одно изменение состояния набора UTXO, то цепочка блоков — это несколько измерений состояния набора UTXO. Ниже показана схема блокчейна биткоина, если рассматривать блокчейн как серию изменений набора UTXO.

Почему блоки нужно проверять в последовательном порядке?

Проверку блоков необходимо начинать с блока 0 и проверять все блоки по одному потому, что транзакция в блоке 500 может ссылаться на набор UTXO, созданный в блоке 499. Если у нас нет данных о состоянии UTXO после изменения блока 499, мы можем потенциально пометить действительную транзакцию как недействительную и окажемся выброшенными из сети биткоина.

Допустим, что Алиса передала Бобу 50 биткоинов, и эта транзакция была включена в блок 499. В этом случае Бобу нужно сослаться на набор UTXO после изменения в блоке 499. Если набор UTXO не был изменен в блоке 499, мы ошибочно заключим, что 50 биткоинов по-прежнему принадлежат Алисе, а не Бобу. Когда Боб потратит свои 50 биткоинов, остальные пользователи сети подтвердят действительность этой транзакции, а мы заявим, что это не так. Это приведет к тому, что наш узел будет исключен из сети биткоина.

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

Мы знаем, что полный узел должен проверить все блоки, один за другим, с самого первого блока. Так как же тогда проверить блоки в произвольном порядке? Для этого можно просто предоставить набор UTXO, необходимый для проверки блока. В этом и заключается суть асинхронной проверки блоков assumeUTXO.

Рассмотрим простой пример проверки блоков в произвольном порядке, в котором мы проверяем блоки от 1 до 300 000.

Мы программируем набор UTXO на уровнях 100 000 и 200 000. Поскольку мы знаем, что представляют собой наборы UTXO на уровнях 100 000 и 200 000, мы можем отдельно проверить блоки в диапазонах 1–100 000, 100 000–200 000 и 200 000 –300 000. После проверки всех трех диапазонов у нас будет три рассчитанных набора UTXO: один в блоке 100 000, другой — в блоке 200 000 и третий — в блоке 300 000.

Далее мы сравниваем запрограммированный набор UTXO в блоке 100 000 с рассчитанным набором UTXO в блоке 100 000. Если они одинаковы, это подтверждает правильность запрограммированного набора UTXO. Мы повторяем эту операцию для набора UTXO в блоке 200 000. Если они также одинаковы, мы знаем, что последний набор UTXO после изменения блока 300 000 должен быть правильным. Таким образом и выполняется проверка блоков в произвольном порядке.

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

Функцию проверки блоков можно упростить и представить следующим образом:

Начальный набор UTXO (Start UTXO set ) и конечный набор UTXO (End UTXO set ) — это наборы UTXO на уровне блока n и n+1. Данные блока (Block Data) — это данные блока на уровне n, который мы будем проверять. Правила (Rules) — это обязательные правила блокчейна на этом уровне. Новые правила, которые вводятся с помощью софтфорков, также должны быть включены в эту функцию (т.е. активированы ли правила Segwit, активированы ли правила Taproot и т. д.).

Необходимость в использовании аккумуляторов Utreexo

Использование аккумуляторов Utreexo для этого типа проверки блоков необходимо по двум причинам.

  1. Аккумуляторы Utreexo имеют крошечный размер.
  2. Элементы Utreexo устраняют необходимость обращения к диску.
  1. Аккумуляторы Utreexo имеют крошечный размер

Теоретически, загрузить блоки в произвольном порядке можно и без аккумуляторов Utreexo. Но, поскольку размер набора UTXO превышает 4 ГБ, практически это неосуществимо, ведь для проверки всего блокчейна необходимо предоставить множество наборов UTXO. Проверка каждого блока в цепочке потребует 8 ГБ данных. Это значение быстро достигает огромных величин (для проверки 100 блоков требуется 800 ГБ), что делает невозможным жесткое кодирование наборов UTXO в двоичном коде.

Использование аккумуляторов Utreexo делает это возможным, ведь набор UTXO умещается в нескольких сотнях байтов. Вот реальный пример программирования корней Utreexo (Roots) в json:

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

Начальные корни Utreexo (Start Utreexo Roots ) и конечные корни Utreexo (End Utreexo Roots ) эквивалентны наборам UTXO на уровне n и n+1. Чтобы иметь возможность проверить данные блока, добавляется Utreexo Proof.

  1. Utreexo заменяет обращение к диску увеличенным объемом хэширования SHA256

Аккумуляторы Utreexo позволяют решить проблему объема данных. Но это не единственная проблема, которую решают аккумуляторы Utreexo. Аккумуляторы Utreexo устраняют необходимость обращения к диску, заменяя ее увеличением объема хэширования SHA256. Это очень важно, ведь без аккумуляторов Utreexo у нас неизбежно возникла бы проблема с вводом/выводом данных.

При использовании наборов UTXO проверка транзакции зависит от получения требуемых данных UTXO с диска. Для этого системе необходимо найти крошечный неупорядоченный фрагмент данных, а мы знаем, что это происходит не быстро. Для проверки блоков такой поиск данных на диске приходилось бы выполнять многократно. При параллельной проверке блоков количество таких обращений к диску резко возрастает. В мире не существует твердотельных накопителей, способных справиться с такой нагрузкой.

Аккумуляторы Utreexo устраняют обращение к диску, увеличивая объем хэширования SHA256 в процессе проверки транзакций. Поскольку блок — это совокупность транзакций, аккумуляторы Utreexo также устраняют необходимость в обращении к диску (заменяя его дополнительным хэшированием SHA256) при проверке блоков. Поэтому проверка блока, по сути, сводится к вычислению хэшей SHA256 (наряду с проверкой других правил консенсуса). Блокчейн — это просто серия блоков, поэтому для проверки всего блокчейна не нужно обращаться к диску, а нужно увеличить объем хэширования SHA256. Таким образом, в процессе начальной загрузки блоков (IBD) будет вычислено огромное количество хэшей SHA256. Это нормально, ведь мы знаем, как быстро вычислять хэши SHA256.

По этим причинам аккумуляторы Utreexo очень важны для параллельной проверки блокчейна. Аккумуляторы Utreexo решают две большие проблемы одновременно и позволяют выполнять параллельную проверку блокчейна.

Заключение

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