The Verge - Эффективная верифицируемая методика запросов Ethereum: деревья Verkle

Продвинутый5/6/2024, 9:19:56 AM
Что такое деревья Verkle, почему Ethereum нуждается в них и как деревья Verkle решают проблемы? Цель этой статьи - ответить на эти вопросы для читателей, не углубляясь слишком глубоко в криптографию и математику, помогая тем, кто имеет некоторое понимание Ethereum, быстро ухватить концепцию деревьев Verkle.

1. Введение

В последний день 2023 года Виталик поделился дорожной картой Ethereum на 2023 год в Twitter, подводя итоги прогресса Ethereum за год. Раздел "The Verge" описывает, как технология Ethereum может проверять состояния блокчейна более просто и эффективно. Одним из основных концепций, упомянутых там, являются деревья Verkle. Итак, что такое деревья Verkle, зачем нужно Ethereum и как деревья Verkle решают проблемы? Цель этой статьи - ответить на эти вопросы для читателей, не углубляясь слишком глубоко в криптографию и математику, помогая тем, кто имеет некоторое понимание Ethereum, быстро освоить концепцию деревьев Verkle.

2. Проверяемый запрос

Технология верификации запросов широко исследуется в области традиционных баз данных, в основном используется для решения проблем доверия к внешним базам данных. Во многих сценариях владельцы данных могут выбрать не хранить данные у себя, а вместо этого доверить свои потребности в базе данных третьей стороне для предоставления услуг баз данных (например, облачные базы данных). Однако, поскольку третьи стороны не всегда надежны, сложно гарантировать правдивость результатов запросов, которые они возвращают пользователям. Текущие решения верификации запросов для традиционных баз данных в основном можно разделить на две категории: те, которые основаны на ADS (аутентифицированных структурах данных) и те, которые основаны на верифицируемом вычислении.

ADS - это подтверждаемая методика запросов, широко используемая в традиционных базах данных, в основном основанная на структурах, таких как деревья Меркля или подобные накопительные структуры. С развитием криптографических инструментов многие исследователи постепенно начали исследовать использование методик подтверждаемых вычислений для решения проблем с недоверенными запросами. Некоторые схемы подтверждаемых вычислений, основанные на протоколах нулевого знания, таких как SNARKs, могут косвенно поддерживать подтверждаемые запросы для внешних баз данных. Эти схемы поддерживают широкий спектр типов запросов и генерируют меньше информации для проверки, но они имеют более высокие вычислительные издержки.

В настоящее время Ethereum использует деревья Меркля для реализации проверяемых запросов, а технология Verkle Tree также основана на технологии деревьев Меркля. Поэтому давайте сначала познакомим читателей с деревьями Меркля, чтобы помочь им понять роль проверяемых запросов на их примере.

3. Деревья Меркла

3.1. Определение и характеристики деревьев Меркла

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

Деревья Меркла имеют две важные характеристики:

  1. Устойчивость к вмешательству: Деревья Меркля обычно строятся с использованием хэш-функций, устойчивых к коллизиям, что делает вычислительно невозможным нахождение двух различных сообщений, дающих одинаковое значение хэша. Из структуры дерева Меркля видно, что любое изменение данных транзакции в листовом узле приведет к изменению корневого хэша дерева.
  2. Эффективная проверка целостности больших наборов данных: Проверяющим нужно хранить только корневой хэш дерева Меркля, чтобы проверить целостность любых данных. Это достигается без передачи полного набора данных, а путем использования соседних узлов вдоль пути от листа к корню, известных как Мерклевский путь. Эти соседние узлы могут быть использованы для восстановления корневого хэша в целях проверки.

3.2. Как построить доказательство Меркла?

В обычном проверяемом сценарии запроса есть доказательство и проверяющий. Доказывающему необходимо сгенерировать доказательство и отправить его проверяющему. Соответственно сети Ethereum, типичным сценарием применения является ситуация, когда легкий узел (клиент, который хранит только заголовки блоков) запрашивает данные о транзакциях у полного узла или архивного узла (клиенты со всей информацией) и получает доказательство Меркля для локальной проверки правильности результата запроса.

Доказательство Меркла состоит из следующих трех частей:

  1. Корневой хеш дерева Меркла для полного набора данных.
  2. Блок данных, целостность которого необходимо доказать.
  3. Путь Меркла, который включает в себя значения всех смежных узлов на пути от листового узла к корневому узлу.

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

Ниже приведен конкретный пример: когда доказывающему лицу необходимо доказать верификатору, что "4" - это блок данных, существующий в наборе данных, и верификатор хранит доверенный корневой хеш "1d25" полного дерева Меркля набора данных, тогда доказывающему лицу нужно предоставить только все данные, отмеченные синим цветом. Предполагая, что в наборе данных есть n кусков данных, для проверки правильности любого блока данных требуется не более 𝘭𝘰𝘨₂(𝘯) вычислений хеша.


Легкие узлы Ethereum синхронизируют только заголовки блоков, которые содержат корни деревьев Меркля для различных наборов данных (дерево состояния, дерево транзакций, дерево квитанций). Когда легкий узел запрашивает у полного узла данные конкретного листового узла в дереве, полный узел возвращает исходные данные вместе с соответствующим путем доказательства Меркля. Это позволяет легкому узлу доверять правильности результата запроса.

3.3. Варианты деревьев Меркля

На основе деревьев Меркля их можно объединять и изменять с другими структурами данных, чтобы достичь новых характеристик на основе различных целей. Для удовлетворения различных сценариев верификации запросов деревья Меркля могут быть расширены до различных индексированных структур данных, таких как деревья Меркля-Б (MBT). Для эффективного выполнения операций, таких как вставка, удаление и запрос, команда Ethereum предложила дерево Меркля Патриции (MPT).

3.3.1. Дерево Меркля-Б

Дерево Меркля-Б (MBT) в основном используется для обработки проверяемых диапазонных запросов. Пусть 𝑓 будет веянием MBT (количество дочерних узлов для каждого узла). Основываясь на структуре B+ дерева, каждый внутренний узел MBT, помимо хранения 𝑓 — 1 индексного ключа и указателей на 𝑓 дочерних узлов, также поддерживает хэш-значения всех своих дочерних узлов в суммированной форме. Ниже представлена структура листовых узлов и внутренних узлов в MBT.

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

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

3.3.2. Дерево Меркля-Патрисии

Если для обеспечения возможности проверки запросов используется наивное дерево Меркля, то трудоемкий процесс пересоздания корня дерева Меркля после каждой вставки или удаления данных может стать значительным. Кроме того, это требует поддержки дополнительных деревьев поиска данных для хранения. Дерево Меркля Патрисии (MPT) объединяет атрибуты дерева радиксов (компактное префиксное дерево) и дерева Меркля, что позволяет выполнять вставки, удаления и запросы за время O(log(N)). Для полного понимания MPT читатели могут обратиться к подробным техническим статьям по этой теме. В данной статье будут представлены только некоторые базовые определения и примеры, чтобы помочь читателям быстро понять MPT.

Базовая структура Ethereum использует базу данных ключ-значение для хранения, что означает, что данные хранятся в виде пар ключ-значение. MPT также декомпозирован в пары ключ-значение для хранения. Мы определяем логическую структуру узлов MPT следующим образом:

  • индекс
  • путь
  • данные

В контексте дерева Меркла Патрисии (MPT) «индекс» относится к ключу пары ключ-значение, в то время как «путь», в сочетании с «данными», составляет значение пары ключ-значение. Индекс фактически хранит хэш узла дерева Меркла, а путь соответствует строке пути, используемой в префиксном дереве для поиска целевого узла. Ethereum использует шестнадцатеричные строки в качестве строк пути, и поэтому ширина MPT равна 16. Данные представляют собой целевые данные, соответствующие пути.

Ниже приведен пример MPT, который был оптимизирован сжатыми префиксами, хранящими следующие данные пар ключ-значение:

{

‘cab8’: ‘собака’,

‘cabe’: ‘cat’,

‘39’: ‘курица’,

'395': 'утка',

‘56f0’: ‘лошадь’

}

Чтобы найти данные «duck», используя путь «395», вы начнете с корневого хэша и продолжите через хэшA, хэшC и хэшD, чтобы в конечном итоге достичь целевых данных. Вот пошаговое руководство:

  1. Корневой хэш: Это точка входа в дерево Меркля Патрисии (MPT), и вы бы использовали его, чтобы найти первый узел.
  2. hashA: Исходя из корневого хэша, вы получите узел или содержимое, идентифицированное по хэшу A. Поскольку путь - “395”, вы ищете часть дерева, которая приведет вас к “3”.
  3. hashC: После доступа к содержимому hashA вы продолжаете следовать по пути. Следующий сегмент, «9», ведет вас к hashC.
  4. hashD: Наконец, продолжая движение по пути, последний сегмент «5» направляет вас на hashD, который содержит значение «duck».

На каждом шаге на пути MPT использует свойства как Дерева Радикс, чтобы найти правильный путь на основе ключа, так и Дерева Меркля, чтобы обеспечить целостность данных через хэш-ссылки. "Пути" в дереве обычно представлены в шестнадцатеричном кодировании, которое соответствует ветвящемуся фактору дерева 16. Каждый узел на пути включает достаточно хэш-указателей (к дочерним узлам) и значений, чтобы проверить целостность данных и перемещаться по дереву.

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

4. Векторное обязательство

Схемы обязательств[1] - это криптографические примитивы, которые обеспечивают конфиденциальность и целостность данных. Они широко используются в сценариях, таких как доказательства в нулевом знании и безопасные многопользовательские вычисления. Базовая схема обязательства делится на два этапа: этап фиксации и этап раскрытия (или открытия).

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

Векторное обязательство - это особый тип схемы обязательств, предложенной Каталино и др. [2], который позволяет обязывающему лицу сделать обязательство по упорядоченному набору сообщений 𝑚 = ⟨𝑚1 , 𝑚2 , …, 𝑚𝑞 ⟩ и раскрыть (открыть) на любой указанной позиции, чтобы доказать, что сообщение 𝑚𝑖 является i-м обязательным сообщением. В векторных обязательствах привязка означает, что никто не может открыть ту же позицию, чтобы раскрыть разные сообщения.

Типичная схема коммитмента вектора обычно состоит из следующих алгоритмов:

5. Деревья Verkle

5.1. Определение и характеристики деревьев Verkle

Определение: Деревья Verkle = Векторные обязательства + Деревья Меркла.

Пожалуйста, обратите внимание: Виталик Бутерин, сооснователь Ethereum, блогпост, посвященный исключительно представлению деревьев Verkle. Эта глава добавляет некоторый фон и математические знания на основе его блога. Некоторые данные и иллюстрации в следующем тексте происходят из его блога.

Деревья Verkle (VTs) характеризуются тем, что предоставляют более маленькие доказательства по сравнению с деревьями Merkle. Для данных в масштабе миллиардов записей дерево Merkle может генерировать доказательства размером около 1 КБ, в то время как доказательства Verkle tree могут быть менее 150 байт. Этот компактный размер доказательства представляет собой преимущество для реализации бессостоятельные клиенты”.

Структура дерева Verkle в некоторой степени аналогична структуре дерева Меркля-Патрисии (MPT). Вот пример его структуры. Узлы дерева Verkle могут быть: (i) Пустыми, (ii) Листовыми узлами, содержащими ключ и соответствующее значение, или (iii) Внутренними узлами с фиксированным количеством дочерних узлов. Это количество дочерних узлов также называется «шириной» дерева.

Основное различие между VT (Verkle Trees) и MPT (Merkle Patricia Trees) заключается в том, как ширина дерева (или ветвление, которое относится к количеству дочерних узлов узла в дереве) влияет на их эффективность. В случае MPT, если ширина больше, то это обычно менее эффективно, потому что большая ширина означает больше соседних узлов, что может привести к увеличению времени обновления для MPT и более крупным размерам доказательств. Напротив, для VT более широкая ширина дерева приводит к более маленьким доказательствам. Единственным ограничением является то, что при слишком высокой ширине время генерации доказательства может увеличиться.

В Ethereum’s @vbuterin/verkle_tree_eip">в дизайн-предложениях для VT предлагается ширина 256, что значительно больше, чем текущие 16 для MPT. Такая большая ширина возможна в VT благодаря использованию передовых криптографических техник, таких как векторные обязательства, которые обеспечивают компактные доказательства независимо от ширины дерева. Эта техника сжатия позволяет Verkle Trees масштабироваться более эффективно с точки зрения размера доказательства. В последующем тексте будут подробнее объяснены упомянутые выше особенности.

5.2. Обязательство и доказательство деревьев Verkle

Давайте посмотрим, как генерируются доказательства в MPT: Доказательство должно включать хэш-значения всех боковых узлов (или сестринских узлов) на пути от корневого узла до целевого листового узла. Возьмем, к примеру, "4ce", части, отмеченные красным на диаграмме ниже, - это узлы, которые должны быть включены в возвращенное доказательство.

В деревьях Verkle вам не нужно предоставлять соседние узлы; вместо этого вам нужно предоставить только путь вместе с некоторыми дополнительными данными в качестве доказательств.

Как сгенерировать обязательства для VT? Функция хеширования, используемая для вычислений, не является обычным хешем, а использует векторные обязательства.

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

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

В практических реализациях используются многочленные обязательства (которые могут быть реализованы просто и эффективно для векторных обязательств), позволяющие обязать многочлен. Два наиболее дружелюбных пользователю схемы обязательств по многочлену - " Обязательства KZG” и “коммитменты полиномиального типа в стиле бронежилета(первый имеет размер обязательства 48 байтов, второй - 32 байта).

Если вы используете обязательства и доказательства KZG, доказательство для каждого промежуточного узла составляет всего лишь 96 байт, что представляет экономию места почти в три раза по сравнению с базовым деревом Меркля (при условии ширины 256).

Теоретическая временная сложность для операций с деревьями Меркля и Веркля следующая:

Предложенная до сих пор схема доказательства Verkle довольно проста; фактически существуют более продвинутые стратегии оптимизации.

5.3. Оптимизация: Слияние доказательств

5.3.1. идея

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

5.3.2. Математическое обоснование

Сначала давайте познакомимся с некоторыми основными концепциями полиномов в математике: как мы выполняем уменьшение полинома, также известное как уменьшение степени полинома?

Предполагая, что мы знаем многочлен 𝑃(𝑥) и его значение 𝑦₁ при 𝑥₁, то есть 𝑃(𝑥₁) = 𝑦₁.

Теперь рассмотрим новый полиномиальный 𝑃(𝑥) - 𝑦₁, который имеет значение ноль при (𝑥 = 𝑥₁), потому что 𝑃(𝑥₁) - 𝑦₁ =𝑦₁ - 𝑦₁ = 0.

Следовательно, у многочлена 𝑃(𝑥) - 𝑦₁ есть корень при 𝑥 = 𝑥₁, что означает, что (𝑥 - 𝑥₁) является множителем 𝑃(𝑥) - 𝑦₁.

Другими словами, мы можем выразить это в следующей форме: [ 𝑃(𝑥) - 𝑦₁ = (𝑥 - 𝑥₁ )𝑄(𝑥)]

𝑄(𝑥) — это еще один многочлен, степень которого на один меньше, чем у 𝑃(𝑥). Это потому, что (𝑥 -𝑥₁ ) является линейным множителем, который уменьшает общую степень многочлена.

Как использовать KZG, чтобы доказать одно значение в векторе?

Возьмем обязательство KZG10 в качестве примера, для многочлена 𝑃(𝑥), предположим, что его многочленное обязательство - [ 𝑃(𝑠) ]₁.

Как было объяснено ранее, для полинома 𝑃(𝑥) , если 𝑃(𝑧) = 𝑦 , тогда у нас есть 𝑄(𝑥) = (𝑃(𝑥) - 𝑦 )/(𝑥 - 𝑧)

Теперь доказатель может сгенерировать доказательство того, что полином 𝑃(𝑥) удовлетворяет 𝑃(𝑧) = 𝑦: вычислите [ 𝑄(𝑠) ]₁ и отправьте его верификатору.

Проверяющему нужно проверить 𝑒( [ 𝑄(𝑠) ]₁, [ 𝑠 - 𝑧]₂ ) = 𝑒( [ 𝑃(𝑠) ]₁- [𝑦]₁, [1]₂) .

Как использовать KZG для доказательства нескольких значений в векторе?

Мы можем построить доказательство для демонстрации нескольких значений вектора следующим образом:

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

Теперь давайте рассмотрим схему дерева Verkle без оптимизации с точки зрения алгоритма обязательства KZG.

Используя метод построения из раздела «Как использовать KZG для доказательства одного значения в векторе», верификатор может построить обязательства для исходных и частных полиномов для каждого полинома 𝑓ᵢ(𝑥), что приводит к общему количеству 𝟐﹡𝑚 обязательств KZG. Верификатор отправляет все эти обязательства в качестве доказательства для верификации.

Однако, как упоминалось ранее, этот подход требует создания нескольких доказательств, и верификатору также необходимо выполнить несколько вычислений проверки. Нам нужно найти способ сжать несколько доказательств обязательств.

Объединение доказательств

Доказатель отправляет доказательство [ 𝑞( 𝑠 )]₁ верификатору для проверки.

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

  1. Доказательство постоянного размера
  2. Данные листьев, которые будут доказаны (пары ключ-значение)
  3. Значения обязательств всех узлов на пути от листа к корню (предполагая ширину дерева 256 с 2³² узлами, то средняя глубина составляет 4, требуется только 3 значения обязательств)

Обратите внимание, что 𝑥ᵢ и 𝑦ᵢ не обязательно должны быть явно предоставлены; все они могут быть вычислены.

5.3.3. производительность

Относительно схемы слияния доказательств для деревьев Verkle, конкретный размер сгенерированного доказательства следующий (Единица измерения строки - миллиард).

Данные выше предполагают использование дерева шириной 256, использующего схему обязательства KZG (с размером обязательства 48 байтов) и максимизирующего использование дерева. На практике для полностью случайных распределений информации глубина дерева увеличится примерно на 60%, а размер каждого элемента увеличится на 30 байтов. Если используется схема bulletproof, то размер обязательства составит 32 байта.

5.4. Нагрузка вычислений доказывающего и проверяющего лиц

  1. Генерация доказательства: стоимость генерации доказательств со стороны доказывающего связана с шириной дерева, но каждая атомарная операция требует относительно низкой вычислительной стоимости, поэтому деревья Verkle с шириной от 256 до 1024 хорошо работают с точки зрения алгоритмов.
  2. Проверка подтверждения: Виталик указал, что алгоритм верификации очень быстрый и обычно может быть завершен за 100 мс, даже если нужно проверить несколько тысяч значений.
  3. При обновлении деревьев Веркле: обновление дерева требует пересчета всех промежуточных значений обязательств вдоль пути из-за изменений значений или структуры. Однако Виталик упомянул, что благодаря некоторым свойствам алгоритма полиномиального обязательства можно разработать метод, который предварительно вычисляет альтернативные значения обязательств и сохраняет их, тем самым сокращая вычислительные затраты времени во время обновлений, что в сущности обменивает пространство на время.

6. Заключение

Ниже приведены оригинальные слова блога Виталика, мы добавили абзац в конце в качестве дополнения。

Деревья Verkle - это мощное обновление доказательств Merkle, которые позволяют существенно сократить размеры доказательств. Вместо необходимости предоставлять все «сестринские узлы» на каждом уровне доказательства, доказывающему стороне нужно предоставить только одно доказательство, доказывающее все родительские-дочерние отношения между всеми обязательствами по путям от каждого листового узла к корню. Это позволяет уменьшить размеры доказательств на коэффициент ~6–8 по сравнению с идеальными деревьями Merkle и на коэффициент более 20–30 по сравнению с шестнадцатеричными деревьями Patricia, которые использует Ethereum сегодня (!!).

Для их реализации требуется более сложная криптография, но они предоставляют возможность для значительного увеличения масштабируемости. В среднесрочной перспективе SNARKs могут улучшить ситуацию дальше: мы можем использовать уже эффективный проверяющий доказательство Verkle для уменьшения размера свидетельства практически до нуля, либо вернуться к SNARKed Merkle доказательствам, если/когда SNARKs станут намного лучше (например, через GKR, или очень дружественные к SNARK хэш-функции, или ASICs). Далее, с появлением квантовых вычислений потребуется переход к STARKed Merkle доказательствам с хэшами, так как линейные гомоморфизмы, от которых зависят деревья Verkle, станут небезопасными. Но на данный момент они дарят нам те же преимущества в масштабировании, которые мы получили бы с использованием более современных технологий, и у нас уже есть все необходимые инструменты для их эффективной реализации.

В настоящее время многие клиенты Ethereum предоставили реализацию дерева Verkle и связанные тестовые сети. Сообщество все еще обсуждает время запуска деревьев Verkle на основной сети. Скорее всего, это будет реализовано в рамках обновления жесткого вилки в 2024 или 2025 году. Для получения подробной информации о деревьях Verkle на Ethereum см. https://verkle.info/ .

7. Ссылка

[1]. BRASSARD G, CHAUM D, CRÉPEAU C. Минимальные доказательства знания[J]. Журнал компьютерных и системных наук, 1988, 37(2): 156–189.

[2]. CATALANO D, FIORE D. Векторные обязательства и их применения[C]//Public-KeyCryptography–PKC 2013: 16-я Международная конференция по криптографии на открытом ключе, Нара, Япония, 26 февраля – 1 марта 2013 года. Сборник научных трудов 16. Springer, 2013: 55–72.

Отказ от ответственности:

  1. Эта статья взята из [ZAN], Все авторские права принадлежат оригинальному автору [AntChain Open Labs и ZAN]. Если есть возражения против этого переиздания, пожалуйста, свяжитесь с Gate Учитькоманда, и они незамедлительно справятся с этим.
  2. Отказ от ответственности: Взгляды и мнения, высказанные в этой статье, являются исключительно мнением автора и не являются инвестиционным советом.
  3. Переводы статьи на другие языки выполняются командой Gate Learn. Если не указано иное, копирование, распространение или плагиат переведенных статей запрещены.

The Verge - Эффективная верифицируемая методика запросов Ethereum: деревья Verkle

Продвинутый5/6/2024, 9:19:56 AM
Что такое деревья Verkle, почему Ethereum нуждается в них и как деревья Verkle решают проблемы? Цель этой статьи - ответить на эти вопросы для читателей, не углубляясь слишком глубоко в криптографию и математику, помогая тем, кто имеет некоторое понимание Ethereum, быстро ухватить концепцию деревьев Verkle.

1. Введение

В последний день 2023 года Виталик поделился дорожной картой Ethereum на 2023 год в Twitter, подводя итоги прогресса Ethereum за год. Раздел "The Verge" описывает, как технология Ethereum может проверять состояния блокчейна более просто и эффективно. Одним из основных концепций, упомянутых там, являются деревья Verkle. Итак, что такое деревья Verkle, зачем нужно Ethereum и как деревья Verkle решают проблемы? Цель этой статьи - ответить на эти вопросы для читателей, не углубляясь слишком глубоко в криптографию и математику, помогая тем, кто имеет некоторое понимание Ethereum, быстро освоить концепцию деревьев Verkle.

2. Проверяемый запрос

Технология верификации запросов широко исследуется в области традиционных баз данных, в основном используется для решения проблем доверия к внешним базам данных. Во многих сценариях владельцы данных могут выбрать не хранить данные у себя, а вместо этого доверить свои потребности в базе данных третьей стороне для предоставления услуг баз данных (например, облачные базы данных). Однако, поскольку третьи стороны не всегда надежны, сложно гарантировать правдивость результатов запросов, которые они возвращают пользователям. Текущие решения верификации запросов для традиционных баз данных в основном можно разделить на две категории: те, которые основаны на ADS (аутентифицированных структурах данных) и те, которые основаны на верифицируемом вычислении.

ADS - это подтверждаемая методика запросов, широко используемая в традиционных базах данных, в основном основанная на структурах, таких как деревья Меркля или подобные накопительные структуры. С развитием криптографических инструментов многие исследователи постепенно начали исследовать использование методик подтверждаемых вычислений для решения проблем с недоверенными запросами. Некоторые схемы подтверждаемых вычислений, основанные на протоколах нулевого знания, таких как SNARKs, могут косвенно поддерживать подтверждаемые запросы для внешних баз данных. Эти схемы поддерживают широкий спектр типов запросов и генерируют меньше информации для проверки, но они имеют более высокие вычислительные издержки.

В настоящее время Ethereum использует деревья Меркля для реализации проверяемых запросов, а технология Verkle Tree также основана на технологии деревьев Меркля. Поэтому давайте сначала познакомим читателей с деревьями Меркля, чтобы помочь им понять роль проверяемых запросов на их примере.

3. Деревья Меркла

3.1. Определение и характеристики деревьев Меркла

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

Деревья Меркла имеют две важные характеристики:

  1. Устойчивость к вмешательству: Деревья Меркля обычно строятся с использованием хэш-функций, устойчивых к коллизиям, что делает вычислительно невозможным нахождение двух различных сообщений, дающих одинаковое значение хэша. Из структуры дерева Меркля видно, что любое изменение данных транзакции в листовом узле приведет к изменению корневого хэша дерева.
  2. Эффективная проверка целостности больших наборов данных: Проверяющим нужно хранить только корневой хэш дерева Меркля, чтобы проверить целостность любых данных. Это достигается без передачи полного набора данных, а путем использования соседних узлов вдоль пути от листа к корню, известных как Мерклевский путь. Эти соседние узлы могут быть использованы для восстановления корневого хэша в целях проверки.

3.2. Как построить доказательство Меркла?

В обычном проверяемом сценарии запроса есть доказательство и проверяющий. Доказывающему необходимо сгенерировать доказательство и отправить его проверяющему. Соответственно сети Ethereum, типичным сценарием применения является ситуация, когда легкий узел (клиент, который хранит только заголовки блоков) запрашивает данные о транзакциях у полного узла или архивного узла (клиенты со всей информацией) и получает доказательство Меркля для локальной проверки правильности результата запроса.

Доказательство Меркла состоит из следующих трех частей:

  1. Корневой хеш дерева Меркла для полного набора данных.
  2. Блок данных, целостность которого необходимо доказать.
  3. Путь Меркла, который включает в себя значения всех смежных узлов на пути от листового узла к корневому узлу.

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

Ниже приведен конкретный пример: когда доказывающему лицу необходимо доказать верификатору, что "4" - это блок данных, существующий в наборе данных, и верификатор хранит доверенный корневой хеш "1d25" полного дерева Меркля набора данных, тогда доказывающему лицу нужно предоставить только все данные, отмеченные синим цветом. Предполагая, что в наборе данных есть n кусков данных, для проверки правильности любого блока данных требуется не более 𝘭𝘰𝘨₂(𝘯) вычислений хеша.


Легкие узлы Ethereum синхронизируют только заголовки блоков, которые содержат корни деревьев Меркля для различных наборов данных (дерево состояния, дерево транзакций, дерево квитанций). Когда легкий узел запрашивает у полного узла данные конкретного листового узла в дереве, полный узел возвращает исходные данные вместе с соответствующим путем доказательства Меркля. Это позволяет легкому узлу доверять правильности результата запроса.

3.3. Варианты деревьев Меркля

На основе деревьев Меркля их можно объединять и изменять с другими структурами данных, чтобы достичь новых характеристик на основе различных целей. Для удовлетворения различных сценариев верификации запросов деревья Меркля могут быть расширены до различных индексированных структур данных, таких как деревья Меркля-Б (MBT). Для эффективного выполнения операций, таких как вставка, удаление и запрос, команда Ethereum предложила дерево Меркля Патриции (MPT).

3.3.1. Дерево Меркля-Б

Дерево Меркля-Б (MBT) в основном используется для обработки проверяемых диапазонных запросов. Пусть 𝑓 будет веянием MBT (количество дочерних узлов для каждого узла). Основываясь на структуре B+ дерева, каждый внутренний узел MBT, помимо хранения 𝑓 — 1 индексного ключа и указателей на 𝑓 дочерних узлов, также поддерживает хэш-значения всех своих дочерних узлов в суммированной форме. Ниже представлена структура листовых узлов и внутренних узлов в MBT.

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

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

3.3.2. Дерево Меркля-Патрисии

Если для обеспечения возможности проверки запросов используется наивное дерево Меркля, то трудоемкий процесс пересоздания корня дерева Меркля после каждой вставки или удаления данных может стать значительным. Кроме того, это требует поддержки дополнительных деревьев поиска данных для хранения. Дерево Меркля Патрисии (MPT) объединяет атрибуты дерева радиксов (компактное префиксное дерево) и дерева Меркля, что позволяет выполнять вставки, удаления и запросы за время O(log(N)). Для полного понимания MPT читатели могут обратиться к подробным техническим статьям по этой теме. В данной статье будут представлены только некоторые базовые определения и примеры, чтобы помочь читателям быстро понять MPT.

Базовая структура Ethereum использует базу данных ключ-значение для хранения, что означает, что данные хранятся в виде пар ключ-значение. MPT также декомпозирован в пары ключ-значение для хранения. Мы определяем логическую структуру узлов MPT следующим образом:

  • индекс
  • путь
  • данные

В контексте дерева Меркла Патрисии (MPT) «индекс» относится к ключу пары ключ-значение, в то время как «путь», в сочетании с «данными», составляет значение пары ключ-значение. Индекс фактически хранит хэш узла дерева Меркла, а путь соответствует строке пути, используемой в префиксном дереве для поиска целевого узла. Ethereum использует шестнадцатеричные строки в качестве строк пути, и поэтому ширина MPT равна 16. Данные представляют собой целевые данные, соответствующие пути.

Ниже приведен пример MPT, который был оптимизирован сжатыми префиксами, хранящими следующие данные пар ключ-значение:

{

‘cab8’: ‘собака’,

‘cabe’: ‘cat’,

‘39’: ‘курица’,

'395': 'утка',

‘56f0’: ‘лошадь’

}

Чтобы найти данные «duck», используя путь «395», вы начнете с корневого хэша и продолжите через хэшA, хэшC и хэшD, чтобы в конечном итоге достичь целевых данных. Вот пошаговое руководство:

  1. Корневой хэш: Это точка входа в дерево Меркля Патрисии (MPT), и вы бы использовали его, чтобы найти первый узел.
  2. hashA: Исходя из корневого хэша, вы получите узел или содержимое, идентифицированное по хэшу A. Поскольку путь - “395”, вы ищете часть дерева, которая приведет вас к “3”.
  3. hashC: После доступа к содержимому hashA вы продолжаете следовать по пути. Следующий сегмент, «9», ведет вас к hashC.
  4. hashD: Наконец, продолжая движение по пути, последний сегмент «5» направляет вас на hashD, который содержит значение «duck».

На каждом шаге на пути MPT использует свойства как Дерева Радикс, чтобы найти правильный путь на основе ключа, так и Дерева Меркля, чтобы обеспечить целостность данных через хэш-ссылки. "Пути" в дереве обычно представлены в шестнадцатеричном кодировании, которое соответствует ветвящемуся фактору дерева 16. Каждый узел на пути включает достаточно хэш-указателей (к дочерним узлам) и значений, чтобы проверить целостность данных и перемещаться по дереву.

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

4. Векторное обязательство

Схемы обязательств[1] - это криптографические примитивы, которые обеспечивают конфиденциальность и целостность данных. Они широко используются в сценариях, таких как доказательства в нулевом знании и безопасные многопользовательские вычисления. Базовая схема обязательства делится на два этапа: этап фиксации и этап раскрытия (или открытия).

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

Векторное обязательство - это особый тип схемы обязательств, предложенной Каталино и др. [2], который позволяет обязывающему лицу сделать обязательство по упорядоченному набору сообщений 𝑚 = ⟨𝑚1 , 𝑚2 , …, 𝑚𝑞 ⟩ и раскрыть (открыть) на любой указанной позиции, чтобы доказать, что сообщение 𝑚𝑖 является i-м обязательным сообщением. В векторных обязательствах привязка означает, что никто не может открыть ту же позицию, чтобы раскрыть разные сообщения.

Типичная схема коммитмента вектора обычно состоит из следующих алгоритмов:

5. Деревья Verkle

5.1. Определение и характеристики деревьев Verkle

Определение: Деревья Verkle = Векторные обязательства + Деревья Меркла.

Пожалуйста, обратите внимание: Виталик Бутерин, сооснователь Ethereum, блогпост, посвященный исключительно представлению деревьев Verkle. Эта глава добавляет некоторый фон и математические знания на основе его блога. Некоторые данные и иллюстрации в следующем тексте происходят из его блога.

Деревья Verkle (VTs) характеризуются тем, что предоставляют более маленькие доказательства по сравнению с деревьями Merkle. Для данных в масштабе миллиардов записей дерево Merkle может генерировать доказательства размером около 1 КБ, в то время как доказательства Verkle tree могут быть менее 150 байт. Этот компактный размер доказательства представляет собой преимущество для реализации бессостоятельные клиенты”.

Структура дерева Verkle в некоторой степени аналогична структуре дерева Меркля-Патрисии (MPT). Вот пример его структуры. Узлы дерева Verkle могут быть: (i) Пустыми, (ii) Листовыми узлами, содержащими ключ и соответствующее значение, или (iii) Внутренними узлами с фиксированным количеством дочерних узлов. Это количество дочерних узлов также называется «шириной» дерева.

Основное различие между VT (Verkle Trees) и MPT (Merkle Patricia Trees) заключается в том, как ширина дерева (или ветвление, которое относится к количеству дочерних узлов узла в дереве) влияет на их эффективность. В случае MPT, если ширина больше, то это обычно менее эффективно, потому что большая ширина означает больше соседних узлов, что может привести к увеличению времени обновления для MPT и более крупным размерам доказательств. Напротив, для VT более широкая ширина дерева приводит к более маленьким доказательствам. Единственным ограничением является то, что при слишком высокой ширине время генерации доказательства может увеличиться.

В Ethereum’s @vbuterin/verkle_tree_eip">в дизайн-предложениях для VT предлагается ширина 256, что значительно больше, чем текущие 16 для MPT. Такая большая ширина возможна в VT благодаря использованию передовых криптографических техник, таких как векторные обязательства, которые обеспечивают компактные доказательства независимо от ширины дерева. Эта техника сжатия позволяет Verkle Trees масштабироваться более эффективно с точки зрения размера доказательства. В последующем тексте будут подробнее объяснены упомянутые выше особенности.

5.2. Обязательство и доказательство деревьев Verkle

Давайте посмотрим, как генерируются доказательства в MPT: Доказательство должно включать хэш-значения всех боковых узлов (или сестринских узлов) на пути от корневого узла до целевого листового узла. Возьмем, к примеру, "4ce", части, отмеченные красным на диаграмме ниже, - это узлы, которые должны быть включены в возвращенное доказательство.

В деревьях Verkle вам не нужно предоставлять соседние узлы; вместо этого вам нужно предоставить только путь вместе с некоторыми дополнительными данными в качестве доказательств.

Как сгенерировать обязательства для VT? Функция хеширования, используемая для вычислений, не является обычным хешем, а использует векторные обязательства.

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

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

В практических реализациях используются многочленные обязательства (которые могут быть реализованы просто и эффективно для векторных обязательств), позволяющие обязать многочлен. Два наиболее дружелюбных пользователю схемы обязательств по многочлену - " Обязательства KZG” и “коммитменты полиномиального типа в стиле бронежилета(первый имеет размер обязательства 48 байтов, второй - 32 байта).

Если вы используете обязательства и доказательства KZG, доказательство для каждого промежуточного узла составляет всего лишь 96 байт, что представляет экономию места почти в три раза по сравнению с базовым деревом Меркля (при условии ширины 256).

Теоретическая временная сложность для операций с деревьями Меркля и Веркля следующая:

Предложенная до сих пор схема доказательства Verkle довольно проста; фактически существуют более продвинутые стратегии оптимизации.

5.3. Оптимизация: Слияние доказательств

5.3.1. идея

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

5.3.2. Математическое обоснование

Сначала давайте познакомимся с некоторыми основными концепциями полиномов в математике: как мы выполняем уменьшение полинома, также известное как уменьшение степени полинома?

Предполагая, что мы знаем многочлен 𝑃(𝑥) и его значение 𝑦₁ при 𝑥₁, то есть 𝑃(𝑥₁) = 𝑦₁.

Теперь рассмотрим новый полиномиальный 𝑃(𝑥) - 𝑦₁, который имеет значение ноль при (𝑥 = 𝑥₁), потому что 𝑃(𝑥₁) - 𝑦₁ =𝑦₁ - 𝑦₁ = 0.

Следовательно, у многочлена 𝑃(𝑥) - 𝑦₁ есть корень при 𝑥 = 𝑥₁, что означает, что (𝑥 - 𝑥₁) является множителем 𝑃(𝑥) - 𝑦₁.

Другими словами, мы можем выразить это в следующей форме: [ 𝑃(𝑥) - 𝑦₁ = (𝑥 - 𝑥₁ )𝑄(𝑥)]

𝑄(𝑥) — это еще один многочлен, степень которого на один меньше, чем у 𝑃(𝑥). Это потому, что (𝑥 -𝑥₁ ) является линейным множителем, который уменьшает общую степень многочлена.

Как использовать KZG, чтобы доказать одно значение в векторе?

Возьмем обязательство KZG10 в качестве примера, для многочлена 𝑃(𝑥), предположим, что его многочленное обязательство - [ 𝑃(𝑠) ]₁.

Как было объяснено ранее, для полинома 𝑃(𝑥) , если 𝑃(𝑧) = 𝑦 , тогда у нас есть 𝑄(𝑥) = (𝑃(𝑥) - 𝑦 )/(𝑥 - 𝑧)

Теперь доказатель может сгенерировать доказательство того, что полином 𝑃(𝑥) удовлетворяет 𝑃(𝑧) = 𝑦: вычислите [ 𝑄(𝑠) ]₁ и отправьте его верификатору.

Проверяющему нужно проверить 𝑒( [ 𝑄(𝑠) ]₁, [ 𝑠 - 𝑧]₂ ) = 𝑒( [ 𝑃(𝑠) ]₁- [𝑦]₁, [1]₂) .

Как использовать KZG для доказательства нескольких значений в векторе?

Мы можем построить доказательство для демонстрации нескольких значений вектора следующим образом:

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

Теперь давайте рассмотрим схему дерева Verkle без оптимизации с точки зрения алгоритма обязательства KZG.

Используя метод построения из раздела «Как использовать KZG для доказательства одного значения в векторе», верификатор может построить обязательства для исходных и частных полиномов для каждого полинома 𝑓ᵢ(𝑥), что приводит к общему количеству 𝟐﹡𝑚 обязательств KZG. Верификатор отправляет все эти обязательства в качестве доказательства для верификации.

Однако, как упоминалось ранее, этот подход требует создания нескольких доказательств, и верификатору также необходимо выполнить несколько вычислений проверки. Нам нужно найти способ сжать несколько доказательств обязательств.

Объединение доказательств

Доказатель отправляет доказательство [ 𝑞( 𝑠 )]₁ верификатору для проверки.

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

  1. Доказательство постоянного размера
  2. Данные листьев, которые будут доказаны (пары ключ-значение)
  3. Значения обязательств всех узлов на пути от листа к корню (предполагая ширину дерева 256 с 2³² узлами, то средняя глубина составляет 4, требуется только 3 значения обязательств)

Обратите внимание, что 𝑥ᵢ и 𝑦ᵢ не обязательно должны быть явно предоставлены; все они могут быть вычислены.

5.3.3. производительность

Относительно схемы слияния доказательств для деревьев Verkle, конкретный размер сгенерированного доказательства следующий (Единица измерения строки - миллиард).

Данные выше предполагают использование дерева шириной 256, использующего схему обязательства KZG (с размером обязательства 48 байтов) и максимизирующего использование дерева. На практике для полностью случайных распределений информации глубина дерева увеличится примерно на 60%, а размер каждого элемента увеличится на 30 байтов. Если используется схема bulletproof, то размер обязательства составит 32 байта.

5.4. Нагрузка вычислений доказывающего и проверяющего лиц

  1. Генерация доказательства: стоимость генерации доказательств со стороны доказывающего связана с шириной дерева, но каждая атомарная операция требует относительно низкой вычислительной стоимости, поэтому деревья Verkle с шириной от 256 до 1024 хорошо работают с точки зрения алгоритмов.
  2. Проверка подтверждения: Виталик указал, что алгоритм верификации очень быстрый и обычно может быть завершен за 100 мс, даже если нужно проверить несколько тысяч значений.
  3. При обновлении деревьев Веркле: обновление дерева требует пересчета всех промежуточных значений обязательств вдоль пути из-за изменений значений или структуры. Однако Виталик упомянул, что благодаря некоторым свойствам алгоритма полиномиального обязательства можно разработать метод, который предварительно вычисляет альтернативные значения обязательств и сохраняет их, тем самым сокращая вычислительные затраты времени во время обновлений, что в сущности обменивает пространство на время.

6. Заключение

Ниже приведены оригинальные слова блога Виталика, мы добавили абзац в конце в качестве дополнения。

Деревья Verkle - это мощное обновление доказательств Merkle, которые позволяют существенно сократить размеры доказательств. Вместо необходимости предоставлять все «сестринские узлы» на каждом уровне доказательства, доказывающему стороне нужно предоставить только одно доказательство, доказывающее все родительские-дочерние отношения между всеми обязательствами по путям от каждого листового узла к корню. Это позволяет уменьшить размеры доказательств на коэффициент ~6–8 по сравнению с идеальными деревьями Merkle и на коэффициент более 20–30 по сравнению с шестнадцатеричными деревьями Patricia, которые использует Ethereum сегодня (!!).

Для их реализации требуется более сложная криптография, но они предоставляют возможность для значительного увеличения масштабируемости. В среднесрочной перспективе SNARKs могут улучшить ситуацию дальше: мы можем использовать уже эффективный проверяющий доказательство Verkle для уменьшения размера свидетельства практически до нуля, либо вернуться к SNARKed Merkle доказательствам, если/когда SNARKs станут намного лучше (например, через GKR, или очень дружественные к SNARK хэш-функции, или ASICs). Далее, с появлением квантовых вычислений потребуется переход к STARKed Merkle доказательствам с хэшами, так как линейные гомоморфизмы, от которых зависят деревья Verkle, станут небезопасными. Но на данный момент они дарят нам те же преимущества в масштабировании, которые мы получили бы с использованием более современных технологий, и у нас уже есть все необходимые инструменты для их эффективной реализации.

В настоящее время многие клиенты Ethereum предоставили реализацию дерева Verkle и связанные тестовые сети. Сообщество все еще обсуждает время запуска деревьев Verkle на основной сети. Скорее всего, это будет реализовано в рамках обновления жесткого вилки в 2024 или 2025 году. Для получения подробной информации о деревьях Verkle на Ethereum см. https://verkle.info/ .

7. Ссылка

[1]. BRASSARD G, CHAUM D, CRÉPEAU C. Минимальные доказательства знания[J]. Журнал компьютерных и системных наук, 1988, 37(2): 156–189.

[2]. CATALANO D, FIORE D. Векторные обязательства и их применения[C]//Public-KeyCryptography–PKC 2013: 16-я Международная конференция по криптографии на открытом ключе, Нара, Япония, 26 февраля – 1 марта 2013 года. Сборник научных трудов 16. Springer, 2013: 55–72.

Отказ от ответственности:

  1. Эта статья взята из [ZAN], Все авторские права принадлежат оригинальному автору [AntChain Open Labs и ZAN]. Если есть возражения против этого переиздания, пожалуйста, свяжитесь с Gate Учитькоманда, и они незамедлительно справятся с этим.
  2. Отказ от ответственности: Взгляды и мнения, высказанные в этой статье, являются исключительно мнением автора и не являются инвестиционным советом.
  3. Переводы статьи на другие языки выполняются командой Gate Learn. Если не указано иное, копирование, распространение или плагиат переведенных статей запрещены.
Начните торговать сейчас
Зарегистрируйтесь сейчас и получите ваучер на
$100
!