Перейти к основному контенту

Деревья Веркла

Деревья Веркла (словослияние от «векторный коммитмент» (Vector commitment) и «деревья Меркла» (Merkle Trees)) — это структура данных, которая может использоваться для обновления узлов Эфириума, чтобы они могли перестать хранить большие объемы данных состояния без потери способности валидировать блоки.

Отсутствие состояния

Деревья Веркла — это критически важный шаг на пути к клиентам Эфириума без сохранения состояния. Клиенты без сохранения состояния — это те, которым не нужно хранить всю базу данных состояния для валидации входящих блоков. Вместо использования собственной локальной копии состояния Эфириума для проверки блоков, такие клиенты используют «свидетеля» данных состояния, который поступает вместе с блоком. Свидетель — это набор отдельных фрагментов данных состояния, необходимых для выполнения определенного набора транзакций, а также криптографическое доказательство того, что свидетель действительно является частью полных данных. Свидетель используется вместо базы данных состояния. Чтобы это работало, свидетели должны быть очень маленькими, чтобы их можно было безопасно транслировать по сети и валидаторы успевали обработать их в течение 12-секундного слота. Текущая структура данных состояния не подходит, поскольку свидетели слишком велики. Деревья Веркла решают эту проблему, позволяя создавать небольших свидетелей, устраняя один из главных барьеров на пути к клиентам без сохранения состояния.

В настоящее время клиенты Эфириума используют структуру данных, известную как префиксное дерево Меркла (Patricia Merkle Trie), для хранения данных состояния. Информация об отдельных аккаунтах хранится в виде листьев дерева, а пары листьев многократно хешируются до тех пор, пока не останется только один хеш. Этот конечный хеш известен как «корень». Для проверки блоков клиенты Эфириума выполняют все транзакции в блоке и обновляют свое локальное дерево состояний. Блок считается действительным, если корень локального дерева идентичен корню, предоставленному предлагающим блок, поскольку любые различия в вычислениях, выполненных предлагающим блок и валидирующим узлом, приведут к тому, что корневой хеш будет совершенно другим. Проблема заключается в том, что проверка блокчейна требует от каждого клиента хранения всего дерева состояний для головного блока и нескольких исторических блоков (по умолчанию в Geth данные состояния хранятся для 128 блоков, предшествующих головному). Это требует от клиентов доступа к большому объему дискового пространства, что является препятствием для запуска полных узлов на дешевом и маломощном оборудовании. Решением этой проблемы является обновление дерева состояний до более эффективной структуры (дерева Веркла), которую можно резюмировать с помощью небольшого «свидетеля» данных, которым можно делиться вместо полных данных состояния. Переформатирование данных состояния в дерево Веркла — это ступенька к переходу на клиенты без сохранения состояния.

Что такое свидетель и зачем он нужен?

Проверка блока означает повторное выполнение транзакций, содержащихся в блоке, применение изменений к дереву состояний Эфириума и вычисление нового корневого хеша. Проверенный блок — это блок, чей вычисленный корневой хеш состояния совпадает с хешем, предоставленным вместе с блоком (поскольку это означает, что предлагающий блок действительно выполнил вычисления, о которых он заявляет). В современных клиентах Эфириума обновление состояния требует доступа ко всему дереву состояний, которое представляет собой большую структуру данных, которую необходимо хранить локально. Свидетель содержит только те фрагменты данных состояния, которые необходимы для выполнения транзакций в блоке. Затем валидатор может использовать только эти фрагменты, чтобы убедиться, что предлагающий блок выполнил транзакции блока и правильно обновил состояние. Однако это означает, что свидетель должен передаваться между узлами в одноранговой сети Эфириума достаточно быстро, чтобы каждый узел мог безопасно получить и обработать его в течение 12-секундного слота. Если свидетель слишком велик, некоторым узлам может потребоваться слишком много времени на его загрузку, и они не будут успевать за цепью. Это является централизующим фактором, поскольку означает, что только узлы с быстрым подключением к интернету могут участвовать в валидации блоков. С деревьями Веркла нет необходимости хранить состояние на жестком диске; все, что нужно для проверки блока, содержится в самом блоке. К сожалению, свидетели, которые могут быть созданы из деревьев Меркла, слишком велики для поддержки клиентов без сохранения состояния.

Почему деревья Веркла позволяют создавать свидетелей меньшего размера?

Структура дерева Меркла делает размеры свидетелей очень большими — слишком большими для безопасной трансляции между узлами в течение 12-секундного слота. Это связано с тем, что свидетель представляет собой путь, соединяющий данные, которые хранятся в листьях, с корневым хешем. Для проверки данных необходимо иметь не только все промежуточные хеши, соединяющие каждый лист с корнем, но и все «родственные» узлы. Каждый узел в доказательстве имеет родственный узел, с которым он хешируется для создания следующего хеша вверх по дереву. Это очень большой объем данных. Деревья Веркла уменьшают размер свидетеля за счет сокращения расстояния между листьями дерева и его корнем, а также устранения необходимости предоставлять родственные узлы для проверки корневого хеша. Еще большая экономия места будет достигнута за счет использования мощной схемы полиномиального коммитмента вместо векторного коммитмента на основе хешей. Полиномиальный коммитмент позволяет свидетелю иметь фиксированный размер независимо от количества листьев, которые он доказывает.

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

Размер свидетеля варьируется в зависимости от количества включенных в него листьев. Если предположить, что свидетель охватывает 1000 листьев, свидетель для дерева Меркла будет весить около 3.5 МБ (при условии 7 уровней в дереве). Свидетель для тех же данных в дереве Веркла (при условии 4 уровней в дереве) будет весить около 150 КБ — примерно в 23 раза меньше. Такое уменьшение размера свидетеля позволит свидетелям клиентов без сохранения состояния быть приемлемо маленькими. Полиномиальные свидетели занимают от 0.128 до 1 КБ в зависимости от того, какой конкретно полиномиальный коммитмент используется.

Какова структура дерева Веркла?

Деревья Веркла представляют собой пары (key,value), где ключи — это 32-байтовые элементы, состоящие из 31-байтовой основы и однобайтового суффикса. Эти ключи организованы в узлы расширения и внутренние узлы. Узлы расширения представляют собой единую основу для 256 дочерних элементов с разными суффиксами. Внутренние узлы также имеют 256 дочерних элементов, но они могут быть другими узлами расширения. Главное отличие структуры дерева Веркла от дерева Меркла заключается в том, что дерево Веркла гораздо более плоское, что означает меньшее количество промежуточных узлов, связывающих лист с корнем, и, следовательно, меньший объем данных, необходимых для генерации доказательства.

Diagram of a Verkle tree data structure

Подробнее о структуре деревьев Веркла (opens in a new tab)

Текущий прогресс

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

Посмотрите, как Гийом Балле (Guillaume Ballet) объясняет тестовую сеть Condrieu Verkle (opens in a new tab) (обратите внимание, что тестовая сеть Condrieu работала на доказательстве выполнения работы (PoW) и теперь заменена тестовой сетью Verkle Gen Devnet 6).

Дополнительная литература