В последний день 2023 года Виталик поделился дорожной картой Ethereum на 2023 год в Twitter, подводя итоги прогресса Ethereum за год. Раздел "The Verge" описывает, как технология Ethereum может проверять состояния блокчейна более просто и эффективно. Одним из основных концепций, упомянутых там, являются деревья Verkle. Итак, что такое деревья Verkle, зачем нужно Ethereum и как деревья Verkle решают проблемы? Цель этой статьи - ответить на эти вопросы для читателей, не углубляясь слишком глубоко в криптографию и математику, помогая тем, кто имеет некоторое понимание Ethereum, быстро освоить концепцию деревьев Verkle.
Технология верификации запросов широко исследуется в области традиционных баз данных, в основном используется для решения проблем доверия к внешним базам данных. Во многих сценариях владельцы данных могут выбрать не хранить данные у себя, а вместо этого доверить свои потребности в базе данных третьей стороне для предоставления услуг баз данных (например, облачные базы данных). Однако, поскольку третьи стороны не всегда надежны, сложно гарантировать правдивость результатов запросов, которые они возвращают пользователям. Текущие решения верификации запросов для традиционных баз данных в основном можно разделить на две категории: те, которые основаны на ADS (аутентифицированных структурах данных) и те, которые основаны на верифицируемом вычислении.
ADS - это подтверждаемая методика запросов, широко используемая в традиционных базах данных, в основном основанная на структурах, таких как деревья Меркля или подобные накопительные структуры. С развитием криптографических инструментов многие исследователи постепенно начали исследовать использование методик подтверждаемых вычислений для решения проблем с недоверенными запросами. Некоторые схемы подтверждаемых вычислений, основанные на протоколах нулевого знания, таких как SNARKs, могут косвенно поддерживать подтверждаемые запросы для внешних баз данных. Эти схемы поддерживают широкий спектр типов запросов и генерируют меньше информации для проверки, но они имеют более высокие вычислительные издержки.
В настоящее время Ethereum использует деревья Меркля для реализации проверяемых запросов, а технология Verkle Tree также основана на технологии деревьев Меркля. Поэтому давайте сначала познакомим читателей с деревьями Меркля, чтобы помочь им понять роль проверяемых запросов на их примере.
Деревья Меркля - это структура, похожая на дерево, обычно используемая в криптографии, подходящая для решения проблем целостности данных. Ниже приведена типичная структура дерева Меркля: листовые узлы представляют собой исходные данные или их хэш-значения, а каждый нелистовой (внутренний) узел содержит комбинированный хэш своих дочерних узлов.
Деревья Меркла имеют две важные характеристики:
В обычном проверяемом сценарии запроса есть доказательство и проверяющий. Доказывающему необходимо сгенерировать доказательство и отправить его проверяющему. Соответственно сети Ethereum, типичным сценарием применения является ситуация, когда легкий узел (клиент, который хранит только заголовки блоков) запрашивает данные о транзакциях у полного узла или архивного узла (клиенты со всей информацией) и получает доказательство Меркля для локальной проверки правильности результата запроса.
Доказательство Меркла состоит из следующих трех частей:
Среди них корневой хэш дерева Меркля должен быть отправлен заранее верификатору по доверенному каналу, и верификатор должен доверять этому значению. В Ethereum надежность данных блока обеспечивается алгоритмом консенсуса, и корневой хэш дерева Меркля содержится в заголовке блока.
Ниже приведен конкретный пример: когда доказывающему лицу необходимо доказать верификатору, что "4" - это блок данных, существующий в наборе данных, и верификатор хранит доверенный корневой хеш "1d25" полного дерева Меркля набора данных, тогда доказывающему лицу нужно предоставить только все данные, отмеченные синим цветом. Предполагая, что в наборе данных есть n кусков данных, для проверки правильности любого блока данных требуется не более 𝘭𝘰𝘨₂(𝘯) вычислений хеша.
Легкие узлы Ethereum синхронизируют только заголовки блоков, которые содержат корни деревьев Меркля для различных наборов данных (дерево состояния, дерево транзакций, дерево квитанций). Когда легкий узел запрашивает у полного узла данные конкретного листового узла в дереве, полный узел возвращает исходные данные вместе с соответствующим путем доказательства Меркля. Это позволяет легкому узлу доверять правильности результата запроса.
На основе деревьев Меркля их можно объединять и изменять с другими структурами данных, чтобы достичь новых характеристик на основе различных целей. Для удовлетворения различных сценариев верификации запросов деревья Меркля могут быть расширены до различных индексированных структур данных, таких как деревья Меркля-Б (MBT). Для эффективного выполнения операций, таких как вставка, удаление и запрос, команда Ethereum предложила дерево Меркля Патриции (MPT).
Дерево Меркля-Б (MBT) в основном используется для обработки проверяемых диапазонных запросов. Пусть 𝑓 будет веянием MBT (количество дочерних узлов для каждого узла). Основываясь на структуре B+ дерева, каждый внутренний узел MBT, помимо хранения 𝑓 — 1 индексного ключа и указателей на 𝑓 дочерних узлов, также поддерживает хэш-значения всех своих дочерних узлов в суммированной форме. Ниже представлена структура листовых узлов и внутренних узлов в MBT.
Когда необходимо доказать, что данные, возвращенные из определенного диапазона запросов, соответствуют указанному диапазону, сервер, вычисляющий объект проверки (VO), должен сначала выполнить две операции поиска сверху вниз, чтобы найти левые и правые границы. Он также должен вернуть все данные в этом диапазоне, а также хеши всех ветвей, необходимых для построения пути к корневому хешу.
Недостатком этой структуры данных является то, что возвращенный VO может только доказать, что результаты запроса находятся в запрошенном диапазоне запроса, но не может доказать, что возвращенные результаты полны.
Если для обеспечения возможности проверки запросов используется наивное дерево Меркля, то трудоемкий процесс пересоздания корня дерева Меркля после каждой вставки или удаления данных может стать значительным. Кроме того, это требует поддержки дополнительных деревьев поиска данных для хранения. Дерево Меркля Патрисии (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, чтобы в конечном итоге достичь целевых данных. Вот пошаговое руководство:
На каждом шаге на пути MPT использует свойства как Дерева Радикс, чтобы найти правильный путь на основе ключа, так и Дерева Меркля, чтобы обеспечить целостность данных через хэш-ссылки. "Пути" в дереве обычно представлены в шестнадцатеричном кодировании, которое соответствует ветвящемуся фактору дерева 16. Каждый узел на пути включает достаточно хэш-указателей (к дочерним узлам) и значений, чтобы проверить целостность данных и перемещаться по дереву.
Обратите внимание, что в реальной MPT пути и данные будут закодированы и храниться в определенном формате, а дополнительные типы узлов (такие как расширенные узлы и листовые узлы) помогают оптимизировать структуру для эффективности в различных сценариях.
Схемы обязательств[1] - это криптографические примитивы, которые обеспечивают конфиденциальность и целостность данных. Они широко используются в сценариях, таких как доказательства в нулевом знании и безопасные многопользовательские вычисления. Базовая схема обязательства делится на два этапа: этап фиксации и этап раскрытия (или открытия).
Векторное обязательство - это особый тип схемы обязательств, предложенной Каталино и др. [2], который позволяет обязывающему лицу сделать обязательство по упорядоченному набору сообщений 𝑚 = ⟨𝑚1 , 𝑚2 , …, 𝑚𝑞 ⟩ и раскрыть (открыть) на любой указанной позиции, чтобы доказать, что сообщение 𝑚𝑖 является i-м обязательным сообщением. В векторных обязательствах привязка означает, что никто не может открыть ту же позицию, чтобы раскрыть разные сообщения.
Типичная схема коммитмента вектора обычно состоит из следующих алгоритмов:
Определение: Деревья 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 масштабироваться более эффективно с точки зрения размера доказательства. В последующем тексте будут подробнее объяснены упомянутые выше особенности.
Давайте посмотрим, как генерируются доказательства в MPT: Доказательство должно включать хэш-значения всех боковых узлов (или сестринских узлов) на пути от корневого узла до целевого листового узла. Возьмем, к примеру, "4ce", части, отмеченные красным на диаграмме ниже, - это узлы, которые должны быть включены в возвращенное доказательство.
В деревьях Verkle вам не нужно предоставлять соседние узлы; вместо этого вам нужно предоставить только путь вместе с некоторыми дополнительными данными в качестве доказательств.
Как сгенерировать обязательства для VT? Функция хеширования, используемая для вычислений, не является обычным хешем, а использует векторные обязательства.
После замены хэш-функции алгоритмом генерации обязательств от векторных обязательств так называемый корневой хэш теперь является корневым обязательством. Если данные любого узла подверглись вмешательству, это в конечном итоге повлияет на корневое обязательство.
Как сгенерировать доказательство? Как показано на схеме ниже, вам нужно предоставить только три поддоказательства, каждое из которых может доказать, что узел на пути существует в определенной позиции внутри своего родительского узла. Чем шире ширина, тем меньше слоев и, следовательно, требуется меньше поддоказательств.
В практических реализациях используются многочленные обязательства (которые могут быть реализованы просто и эффективно для векторных обязательств), позволяющие обязать многочлен. Два наиболее дружелюбных пользователю схемы обязательств по многочлену - " Обязательства KZG” и “коммитменты полиномиального типа в стиле бронежилета(первый имеет размер обязательства 48 байтов, второй - 32 байта).
Если вы используете обязательства и доказательства KZG, доказательство для каждого промежуточного узла составляет всего лишь 96 байт, что представляет экономию места почти в три раза по сравнению с базовым деревом Меркля (при условии ширины 256).
Теоретическая временная сложность для операций с деревьями Меркля и Веркля следующая:
Предложенная до сих пор схема доказательства Verkle довольно проста; фактически существуют более продвинутые стратегии оптимизации.
По сравнению с генерацией доказательства для каждого слоя обязательств на пути, характеристика полиномиальных обязательств может быть использована для достижения «доказательства родительско-дочерних отношений между всеми обязательствами на пути с доказательством фиксированного размера, которое может включать неограниченное количество элементов». Чтобы понять конкретно, как это осуществляется, необходимо ввести некоторые математические знания для объяснения. В этой статье будут использованы некоторые математические формулы, но в принципе не будут рассмотрены криптографические аспекты доказательства. Для конкретного метода обращайтесь к схема, реализующая мультидоказательства через случайную оценку.
Сначала давайте познакомимся с некоторыми основными концепциями полиномов в математике: как мы выполняем уменьшение полинома, также известное как уменьшение степени полинома?
Предполагая, что мы знаем многочлен 𝑃(𝑥) и его значение 𝑦₁ при 𝑥₁, то есть 𝑃(𝑥₁) = 𝑦₁.
Теперь рассмотрим новый полиномиальный 𝑃(𝑥) - 𝑦₁, который имеет значение ноль при (𝑥 = 𝑥₁), потому что 𝑃(𝑥₁) - 𝑦₁ =𝑦₁ - 𝑦₁ = 0.
Следовательно, у многочлена 𝑃(𝑥) - 𝑦₁ есть корень при 𝑥 = 𝑥₁, что означает, что (𝑥 - 𝑥₁) является множителем 𝑃(𝑥) - 𝑦₁.
Другими словами, мы можем выразить это в следующей форме: [ 𝑃(𝑥) - 𝑦₁ = (𝑥 - 𝑥₁ )𝑄(𝑥)]
𝑄(𝑥) — это еще один многочлен, степень которого на один меньше, чем у 𝑃(𝑥). Это потому, что (𝑥 -𝑥₁ ) является линейным множителем, который уменьшает общую степень многочлена.
Как использовать KZG, чтобы доказать одно значение в векторе?
Возьмем обязательство KZG10 в качестве примера, для многочлена 𝑃(𝑥), предположим, что его многочленное обязательство - [ 𝑃(𝑠) ]₁.
Как было объяснено ранее, для полинома 𝑃(𝑥) , если 𝑃(𝑧) = 𝑦 , тогда у нас есть 𝑄(𝑥) = (𝑃(𝑥) - 𝑦 )/(𝑥 - 𝑧)
Теперь доказатель может сгенерировать доказательство того, что полином 𝑃(𝑥) удовлетворяет 𝑃(𝑧) = 𝑦: вычислите [ 𝑄(𝑠) ]₁ и отправьте его верификатору.
Проверяющему нужно проверить 𝑒( [ 𝑄(𝑠) ]₁, [ 𝑠 - 𝑧]₂ ) = 𝑒( [ 𝑃(𝑠) ]₁- [𝑦]₁, [1]₂) .
Как использовать KZG для доказательства нескольких значений в векторе?
Мы можем построить доказательство для демонстрации нескольких значений вектора следующим образом:
Используя этот метод, независимо от количества точек данных в одном и том же векторе, которые необходимо проверить, требуется только доказательство постоянного размера.
Теперь давайте рассмотрим схему дерева Verkle без оптимизации с точки зрения алгоритма обязательства KZG.
Используя метод построения из раздела «Как использовать KZG для доказательства одного значения в векторе», верификатор может построить обязательства для исходных и частных полиномов для каждого полинома 𝑓ᵢ(𝑥), что приводит к общему количеству 𝟐﹡𝑚 обязательств KZG. Верификатор отправляет все эти обязательства в качестве доказательства для верификации.
Однако, как упоминалось ранее, этот подход требует создания нескольких доказательств, и верификатору также необходимо выполнить несколько вычислений проверки. Нам нужно найти способ сжать несколько доказательств обязательств.
Объединение доказательств
Доказатель отправляет доказательство [ 𝑞( 𝑠 )]₁ верификатору для проверки.
Доказательства, представленные этой схемой, состоят из одного обязательства, двух доказательств и одного значения с постоянным размером данных. В конечном итоге, после оптимизации слияния доказательств в дереве Verkle, верифицируемый объект данных, отправленный верификатору, включает в себя следующее:
Обратите внимание, что 𝑥ᵢ и 𝑦ᵢ не обязательно должны быть явно предоставлены; все они могут быть вычислены.
Относительно схемы слияния доказательств для деревьев Verkle, конкретный размер сгенерированного доказательства следующий (Единица измерения строки - миллиард).
Данные выше предполагают использование дерева шириной 256, использующего схему обязательства KZG (с размером обязательства 48 байтов) и максимизирующего использование дерева. На практике для полностью случайных распределений информации глубина дерева увеличится примерно на 60%, а размер каждого элемента увеличится на 30 байтов. Если используется схема bulletproof, то размер обязательства составит 32 байта.
Ниже приведены оригинальные слова блога Виталика, мы добавили абзац в конце в качестве дополнения。
Деревья 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/ .
[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.
Пригласить больше голосов
В последний день 2023 года Виталик поделился дорожной картой Ethereum на 2023 год в Twitter, подводя итоги прогресса Ethereum за год. Раздел "The Verge" описывает, как технология Ethereum может проверять состояния блокчейна более просто и эффективно. Одним из основных концепций, упомянутых там, являются деревья Verkle. Итак, что такое деревья Verkle, зачем нужно Ethereum и как деревья Verkle решают проблемы? Цель этой статьи - ответить на эти вопросы для читателей, не углубляясь слишком глубоко в криптографию и математику, помогая тем, кто имеет некоторое понимание Ethereum, быстро освоить концепцию деревьев Verkle.
Технология верификации запросов широко исследуется в области традиционных баз данных, в основном используется для решения проблем доверия к внешним базам данных. Во многих сценариях владельцы данных могут выбрать не хранить данные у себя, а вместо этого доверить свои потребности в базе данных третьей стороне для предоставления услуг баз данных (например, облачные базы данных). Однако, поскольку третьи стороны не всегда надежны, сложно гарантировать правдивость результатов запросов, которые они возвращают пользователям. Текущие решения верификации запросов для традиционных баз данных в основном можно разделить на две категории: те, которые основаны на ADS (аутентифицированных структурах данных) и те, которые основаны на верифицируемом вычислении.
ADS - это подтверждаемая методика запросов, широко используемая в традиционных базах данных, в основном основанная на структурах, таких как деревья Меркля или подобные накопительные структуры. С развитием криптографических инструментов многие исследователи постепенно начали исследовать использование методик подтверждаемых вычислений для решения проблем с недоверенными запросами. Некоторые схемы подтверждаемых вычислений, основанные на протоколах нулевого знания, таких как SNARKs, могут косвенно поддерживать подтверждаемые запросы для внешних баз данных. Эти схемы поддерживают широкий спектр типов запросов и генерируют меньше информации для проверки, но они имеют более высокие вычислительные издержки.
В настоящее время Ethereum использует деревья Меркля для реализации проверяемых запросов, а технология Verkle Tree также основана на технологии деревьев Меркля. Поэтому давайте сначала познакомим читателей с деревьями Меркля, чтобы помочь им понять роль проверяемых запросов на их примере.
Деревья Меркля - это структура, похожая на дерево, обычно используемая в криптографии, подходящая для решения проблем целостности данных. Ниже приведена типичная структура дерева Меркля: листовые узлы представляют собой исходные данные или их хэш-значения, а каждый нелистовой (внутренний) узел содержит комбинированный хэш своих дочерних узлов.
Деревья Меркла имеют две важные характеристики:
В обычном проверяемом сценарии запроса есть доказательство и проверяющий. Доказывающему необходимо сгенерировать доказательство и отправить его проверяющему. Соответственно сети Ethereum, типичным сценарием применения является ситуация, когда легкий узел (клиент, который хранит только заголовки блоков) запрашивает данные о транзакциях у полного узла или архивного узла (клиенты со всей информацией) и получает доказательство Меркля для локальной проверки правильности результата запроса.
Доказательство Меркла состоит из следующих трех частей:
Среди них корневой хэш дерева Меркля должен быть отправлен заранее верификатору по доверенному каналу, и верификатор должен доверять этому значению. В Ethereum надежность данных блока обеспечивается алгоритмом консенсуса, и корневой хэш дерева Меркля содержится в заголовке блока.
Ниже приведен конкретный пример: когда доказывающему лицу необходимо доказать верификатору, что "4" - это блок данных, существующий в наборе данных, и верификатор хранит доверенный корневой хеш "1d25" полного дерева Меркля набора данных, тогда доказывающему лицу нужно предоставить только все данные, отмеченные синим цветом. Предполагая, что в наборе данных есть n кусков данных, для проверки правильности любого блока данных требуется не более 𝘭𝘰𝘨₂(𝘯) вычислений хеша.
Легкие узлы Ethereum синхронизируют только заголовки блоков, которые содержат корни деревьев Меркля для различных наборов данных (дерево состояния, дерево транзакций, дерево квитанций). Когда легкий узел запрашивает у полного узла данные конкретного листового узла в дереве, полный узел возвращает исходные данные вместе с соответствующим путем доказательства Меркля. Это позволяет легкому узлу доверять правильности результата запроса.
На основе деревьев Меркля их можно объединять и изменять с другими структурами данных, чтобы достичь новых характеристик на основе различных целей. Для удовлетворения различных сценариев верификации запросов деревья Меркля могут быть расширены до различных индексированных структур данных, таких как деревья Меркля-Б (MBT). Для эффективного выполнения операций, таких как вставка, удаление и запрос, команда Ethereum предложила дерево Меркля Патриции (MPT).
Дерево Меркля-Б (MBT) в основном используется для обработки проверяемых диапазонных запросов. Пусть 𝑓 будет веянием MBT (количество дочерних узлов для каждого узла). Основываясь на структуре B+ дерева, каждый внутренний узел MBT, помимо хранения 𝑓 — 1 индексного ключа и указателей на 𝑓 дочерних узлов, также поддерживает хэш-значения всех своих дочерних узлов в суммированной форме. Ниже представлена структура листовых узлов и внутренних узлов в MBT.
Когда необходимо доказать, что данные, возвращенные из определенного диапазона запросов, соответствуют указанному диапазону, сервер, вычисляющий объект проверки (VO), должен сначала выполнить две операции поиска сверху вниз, чтобы найти левые и правые границы. Он также должен вернуть все данные в этом диапазоне, а также хеши всех ветвей, необходимых для построения пути к корневому хешу.
Недостатком этой структуры данных является то, что возвращенный VO может только доказать, что результаты запроса находятся в запрошенном диапазоне запроса, но не может доказать, что возвращенные результаты полны.
Если для обеспечения возможности проверки запросов используется наивное дерево Меркля, то трудоемкий процесс пересоздания корня дерева Меркля после каждой вставки или удаления данных может стать значительным. Кроме того, это требует поддержки дополнительных деревьев поиска данных для хранения. Дерево Меркля Патрисии (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, чтобы в конечном итоге достичь целевых данных. Вот пошаговое руководство:
На каждом шаге на пути MPT использует свойства как Дерева Радикс, чтобы найти правильный путь на основе ключа, так и Дерева Меркля, чтобы обеспечить целостность данных через хэш-ссылки. "Пути" в дереве обычно представлены в шестнадцатеричном кодировании, которое соответствует ветвящемуся фактору дерева 16. Каждый узел на пути включает достаточно хэш-указателей (к дочерним узлам) и значений, чтобы проверить целостность данных и перемещаться по дереву.
Обратите внимание, что в реальной MPT пути и данные будут закодированы и храниться в определенном формате, а дополнительные типы узлов (такие как расширенные узлы и листовые узлы) помогают оптимизировать структуру для эффективности в различных сценариях.
Схемы обязательств[1] - это криптографические примитивы, которые обеспечивают конфиденциальность и целостность данных. Они широко используются в сценариях, таких как доказательства в нулевом знании и безопасные многопользовательские вычисления. Базовая схема обязательства делится на два этапа: этап фиксации и этап раскрытия (или открытия).
Векторное обязательство - это особый тип схемы обязательств, предложенной Каталино и др. [2], который позволяет обязывающему лицу сделать обязательство по упорядоченному набору сообщений 𝑚 = ⟨𝑚1 , 𝑚2 , …, 𝑚𝑞 ⟩ и раскрыть (открыть) на любой указанной позиции, чтобы доказать, что сообщение 𝑚𝑖 является i-м обязательным сообщением. В векторных обязательствах привязка означает, что никто не может открыть ту же позицию, чтобы раскрыть разные сообщения.
Типичная схема коммитмента вектора обычно состоит из следующих алгоритмов:
Определение: Деревья 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 масштабироваться более эффективно с точки зрения размера доказательства. В последующем тексте будут подробнее объяснены упомянутые выше особенности.
Давайте посмотрим, как генерируются доказательства в MPT: Доказательство должно включать хэш-значения всех боковых узлов (или сестринских узлов) на пути от корневого узла до целевого листового узла. Возьмем, к примеру, "4ce", части, отмеченные красным на диаграмме ниже, - это узлы, которые должны быть включены в возвращенное доказательство.
В деревьях Verkle вам не нужно предоставлять соседние узлы; вместо этого вам нужно предоставить только путь вместе с некоторыми дополнительными данными в качестве доказательств.
Как сгенерировать обязательства для VT? Функция хеширования, используемая для вычислений, не является обычным хешем, а использует векторные обязательства.
После замены хэш-функции алгоритмом генерации обязательств от векторных обязательств так называемый корневой хэш теперь является корневым обязательством. Если данные любого узла подверглись вмешательству, это в конечном итоге повлияет на корневое обязательство.
Как сгенерировать доказательство? Как показано на схеме ниже, вам нужно предоставить только три поддоказательства, каждое из которых может доказать, что узел на пути существует в определенной позиции внутри своего родительского узла. Чем шире ширина, тем меньше слоев и, следовательно, требуется меньше поддоказательств.
В практических реализациях используются многочленные обязательства (которые могут быть реализованы просто и эффективно для векторных обязательств), позволяющие обязать многочлен. Два наиболее дружелюбных пользователю схемы обязательств по многочлену - " Обязательства KZG” и “коммитменты полиномиального типа в стиле бронежилета(первый имеет размер обязательства 48 байтов, второй - 32 байта).
Если вы используете обязательства и доказательства KZG, доказательство для каждого промежуточного узла составляет всего лишь 96 байт, что представляет экономию места почти в три раза по сравнению с базовым деревом Меркля (при условии ширины 256).
Теоретическая временная сложность для операций с деревьями Меркля и Веркля следующая:
Предложенная до сих пор схема доказательства Verkle довольно проста; фактически существуют более продвинутые стратегии оптимизации.
По сравнению с генерацией доказательства для каждого слоя обязательств на пути, характеристика полиномиальных обязательств может быть использована для достижения «доказательства родительско-дочерних отношений между всеми обязательствами на пути с доказательством фиксированного размера, которое может включать неограниченное количество элементов». Чтобы понять конкретно, как это осуществляется, необходимо ввести некоторые математические знания для объяснения. В этой статье будут использованы некоторые математические формулы, но в принципе не будут рассмотрены криптографические аспекты доказательства. Для конкретного метода обращайтесь к схема, реализующая мультидоказательства через случайную оценку.
Сначала давайте познакомимся с некоторыми основными концепциями полиномов в математике: как мы выполняем уменьшение полинома, также известное как уменьшение степени полинома?
Предполагая, что мы знаем многочлен 𝑃(𝑥) и его значение 𝑦₁ при 𝑥₁, то есть 𝑃(𝑥₁) = 𝑦₁.
Теперь рассмотрим новый полиномиальный 𝑃(𝑥) - 𝑦₁, который имеет значение ноль при (𝑥 = 𝑥₁), потому что 𝑃(𝑥₁) - 𝑦₁ =𝑦₁ - 𝑦₁ = 0.
Следовательно, у многочлена 𝑃(𝑥) - 𝑦₁ есть корень при 𝑥 = 𝑥₁, что означает, что (𝑥 - 𝑥₁) является множителем 𝑃(𝑥) - 𝑦₁.
Другими словами, мы можем выразить это в следующей форме: [ 𝑃(𝑥) - 𝑦₁ = (𝑥 - 𝑥₁ )𝑄(𝑥)]
𝑄(𝑥) — это еще один многочлен, степень которого на один меньше, чем у 𝑃(𝑥). Это потому, что (𝑥 -𝑥₁ ) является линейным множителем, который уменьшает общую степень многочлена.
Как использовать KZG, чтобы доказать одно значение в векторе?
Возьмем обязательство KZG10 в качестве примера, для многочлена 𝑃(𝑥), предположим, что его многочленное обязательство - [ 𝑃(𝑠) ]₁.
Как было объяснено ранее, для полинома 𝑃(𝑥) , если 𝑃(𝑧) = 𝑦 , тогда у нас есть 𝑄(𝑥) = (𝑃(𝑥) - 𝑦 )/(𝑥 - 𝑧)
Теперь доказатель может сгенерировать доказательство того, что полином 𝑃(𝑥) удовлетворяет 𝑃(𝑧) = 𝑦: вычислите [ 𝑄(𝑠) ]₁ и отправьте его верификатору.
Проверяющему нужно проверить 𝑒( [ 𝑄(𝑠) ]₁, [ 𝑠 - 𝑧]₂ ) = 𝑒( [ 𝑃(𝑠) ]₁- [𝑦]₁, [1]₂) .
Как использовать KZG для доказательства нескольких значений в векторе?
Мы можем построить доказательство для демонстрации нескольких значений вектора следующим образом:
Используя этот метод, независимо от количества точек данных в одном и том же векторе, которые необходимо проверить, требуется только доказательство постоянного размера.
Теперь давайте рассмотрим схему дерева Verkle без оптимизации с точки зрения алгоритма обязательства KZG.
Используя метод построения из раздела «Как использовать KZG для доказательства одного значения в векторе», верификатор может построить обязательства для исходных и частных полиномов для каждого полинома 𝑓ᵢ(𝑥), что приводит к общему количеству 𝟐﹡𝑚 обязательств KZG. Верификатор отправляет все эти обязательства в качестве доказательства для верификации.
Однако, как упоминалось ранее, этот подход требует создания нескольких доказательств, и верификатору также необходимо выполнить несколько вычислений проверки. Нам нужно найти способ сжать несколько доказательств обязательств.
Объединение доказательств
Доказатель отправляет доказательство [ 𝑞( 𝑠 )]₁ верификатору для проверки.
Доказательства, представленные этой схемой, состоят из одного обязательства, двух доказательств и одного значения с постоянным размером данных. В конечном итоге, после оптимизации слияния доказательств в дереве Verkle, верифицируемый объект данных, отправленный верификатору, включает в себя следующее:
Обратите внимание, что 𝑥ᵢ и 𝑦ᵢ не обязательно должны быть явно предоставлены; все они могут быть вычислены.
Относительно схемы слияния доказательств для деревьев Verkle, конкретный размер сгенерированного доказательства следующий (Единица измерения строки - миллиард).
Данные выше предполагают использование дерева шириной 256, использующего схему обязательства KZG (с размером обязательства 48 байтов) и максимизирующего использование дерева. На практике для полностью случайных распределений информации глубина дерева увеличится примерно на 60%, а размер каждого элемента увеличится на 30 байтов. Если используется схема bulletproof, то размер обязательства составит 32 байта.
Ниже приведены оригинальные слова блога Виталика, мы добавили абзац в конце в качестве дополнения。
Деревья 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/ .
[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.