Префиксное дерево

Что такое префиксное дерево?

Префиксное дерево (trie) — это древовидная структура данных, используемая для хранения и извлечения данных типа «ключ — значение» путем последовательного прохождения частей ключа.

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

Слово trie происходит от retrieval («извлечение») и обычно произносится как «трай».

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

Каждый шаг по этому пути сужает поиск, пока система не достигнет значения, связанного с полным ключом.

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

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

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

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

Наиболее известный криптовалютный пример — модифицированное дерево Меркла — Патрисии Ethereum, которое используется на уровне исполнения для организации данных типа «ключ — значение» детерминированным и криптографически проверяемым способом.

Почему префиксные деревья важны в криптоиндустрии

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

Состояние — это текущее состояние блокчейна, включая балансы аккаунтов, код смарт-контрактов, значения хранилища и другие данные реестра.

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

Корень состояния — это компактная криптографическая сводка полного состояния.

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

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

Ethereum.org поясняет, что дерево Меркла — Патрисии является детерминированным и криптографически проверяемым, а любая попытка изменить состояние с другими значениями приводит к иному хешу корня состояния, согласно документации по дереву Меркла — Патрисии.

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

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

Как работает базовое префиксное дерево

Базовое префиксное дерево хранит данные, разделяя ключи на меньшие символы.

Например, префиксное дерево для слов может хранить «cat», «car» и «cap», используя общие первые две буквы «ca», а затем разветвляясь на последней букве.

Такая структура с общими префиксами уменьшает повторное хранение данных, когда многие ключи начинаются одинаково.

В криптосистемах ключи обычно не являются простыми английскими словами.

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

Префиксное дерево проходит ключ по частям, пока не достигнет значения.

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

Теоретически такая структура может обеспечивать быстрый поиск, вставку и удаление.

Однако обычное префиксное дерево может быть неэффективным, если ключи длинные и многие пути содержат лишь одного потомка.

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

Префиксное дерево и обычное дерево

Префиксное дерево является разновидностью дерева, но оно построено вокруг ключей и префиксов.

Обычное дерево может организовывать значения по сравнению, иерархии или отношениям «родитель — потомок».

Префиксное дерево организует значения путем прохождения символов ключа.

Это делает такие деревья особенно полезными, когда множество ключей имеют общие префиксы.

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

Префиксное дерево позволяет сделать путь к значению напрямую зависимым от самого ключа.

Это полезно, когда нодам необходимо детерминированное поведение.

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

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

Каждая полная нода должна иметь возможность вычислить одинаковый корень из одинаковых данных.

Префиксное дерево и дерево Меркла

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

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

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

Префиксное дерево полезно тем, что поддерживает эффективный поиск по ключу и значению.

Дерево Меркла — Патрисии объединяет эти идеи.

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

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

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

Обычное дерево Меркла может доказывать принадлежность, но не всегда предназначено для эффективных обновлений данных типа «ключ — значение».

Дерево Меркла — Патрисии предоставляет системам в стиле Ethereum способ управлять изменяющимся состоянием, сохраняя проверяемое корневое обязательство.

Что такое дерево Патрисии?

Дерево Патрисии — это оптимизированное префиксное дерево, сжимающее пути при наличии длинных участков без разветвлений.

PATRICIA означает Practical Algorithm To Retrieve Information Coded in Alphanumeric.

Цель состоит в том, чтобы не расходовать место на узлы, указывающие только на один следующий узел.

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

Дерево Патрисии может компактнее хранить общий сегмент пути.

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

Ethereum.org поясняет, что структура данных Ethereum заимствует свойства PATRICIA, поскольку предназначена для эффективного извлечения элементов, составляющих состояние Ethereum, в своем руководстве по дереву Меркла — Патрисии.

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

Это важно, потому что состояние блокчейна может включать миллионы аккаунтов и еще больше записей хранилища.

Меньшая и более эффективная структура помогает нодам обрабатывать изменения состояния с меньшими накладными расходами.

Что такое дерево Меркла — Патрисии?

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

Иногда его сокращенно называют MPT.

Ethereum использует модифицированное дерево Меркла — Патрисии для важных данных уровня исполнения.

В официальной документации по структурам данных Ethereum указано, что деревья Меркла — Патрисии кодируют пары «ключ — значение» в детерминированное и криптографически аутентифицированное префиксное дерево.

В Ethereum MPT позволяет сети зафиксировать крупную базу данных состояния одним корневым хешем.

Корневой хеш хранится в данных блока и действует как отпечаток состояния после исполнения транзакций.

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

Это одна из причин, по которой MPT критически важны для модели исполнения Ethereum.

Они связывают локальные обновления базы данных с глобальным консенсусом.

Они также поддерживают доказательства Меркла, способные подтвердить данные аккаунта или хранилища относительно известного корня.

Модифицированное дерево Меркла — Патрисии в Ethereum

Версию Ethereum часто называют модифицированным деревом Меркла — Патрисии.

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

Это означает, что корень дерева фиксирует полный набор состояний аккаунтов.

Состояние аккаунта включает такие данные, как nonce, баланс, корень хранилища и хеш кода.

Хранилище смарт-контрактов также организовано через структуры префиксных деревьев.

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

Это изменение влияет на родительские хеши вплоть до корня.

Итоговый корень состояния затем отражает обновленное состояние блокчейна.

Так небольшой хеш может представлять огромный объем изменяющихся данных состояния.

Модифицированное MPT — одна из причин, по которым ноды Ethereum могут независимо проверять правильность исполнения блока.

Узлы в дереве Меркла — Патрисии

Дерево Меркла — Патрисии использует несколько типов узлов.

Ethereum.org перечисляет нулевые узлы, узлы ветвления, листовые узлы и узлы расширения в своей документации MPT.

Нулевой узел представляет пустое значение.

Узел ветвления может указывать на несколько возможных следующих путей.

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

Узел расширения хранит общий сегмент пути и указывает на другой узел.

Эти типы узлов позволяют дереву эффективно хранить разреженные данные «ключ — значение».

Разреженная структура означает, что возможных ключей много, но значения есть только у некоторых из них.

Ключи Ethereum часто представлены нибблами, где один ниббл равен половине байта.

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

Такая конструкция позволяет дереву предсказуемо перемещаться по шестнадцатеричным путям ключей.

Дерево состояния

Дерево состояния — это дерево, фиксирующее мировое состояние Ethereum.

Мировое состояние включает все аккаунты и данные их аккаунтов.

Каждый аккаунт может быть внешним аккаунтом, управляемым приватным ключом, или аккаунтом контракта, управляемым кодом.

Дерево состояния сопоставляет адреса аккаунтов с закодированными данными аккаунтов.

Корень состояния — это корневой хеш данного дерева после обработки транзакций блока.

При проверке блока валидаторы повторно исполняют транзакции и вычисляют итоговый корень состояния.

На странице Ethereum.org о дорожной карте деревьев Verkle поясняется, что проверенный блок — это блок, чей вычисленный хеш корня состояния совпадает с корнем, предоставленным предлагающим блок.

Это делает дерево состояния центральным элементом валидации блоков.

Оно не является лишь деталью хранения, скрытой в клиентском ПО.

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

Дерево хранилища

Дерево хранилища хранит данные хранилища смарт-контракта для конкретного аккаунта.

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

Это дерево сопоставляет ключи хранилища со значениями хранилища.

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

Каждое из этих значений может быть представлено через слоты хранилища.

Когда пользователь переводит токен, хранилище контракта может измениться из-за обновления балансов.

Это изменение обновляет корень дерева хранилища контракта.

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

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

Именно эта цепочка делает возможными доказательства хранилища.

Дерево транзакций

Дерево транзакций фиксирует транзакции, включенные в блок.

Каждый блок имеет корень транзакций, суммирующий транзакции этого блока.

Это позволяет нодам и клиентам проверять включение транзакции по данным блока.

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

Дерево состояния изменяется, когда транзакции обновляют аккаунты и контракты.

Дерево транзакций записывает, какие транзакции включены в конкретный блок.

Это различие важно, поскольку включение транзакции и ее влияние на состояние связаны, но не идентичны.

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

Дерево транзакций может доказать включение, а дерево квитанций может показать сведения о результате исполнения.

Пользователям, проверяющим транзакцию, следует понимать, что включение в блок — лишь часть полной истории транзакции.

Дерево квитанций

Дерево квитанций фиксирует квитанции транзакций блока.

Квитанция записывает результат исполнения транзакции.

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

Квитанции важны для кошельков, обозревателей, индексаторов и децентрализованных приложений.

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

Дерево квитанций помогает фиксировать эти результаты в данных блока.

Это позволяет клиентам проверять, что определенная квитанция относится к блоку.

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

Для пользователей дерево квитанций обычно незаметно.

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

Корень префиксного дерева

Корень префиксного дерева — это хеш верхнего уровня, суммирующий все данные в дереве.

Если любое значение внутри дерева изменяется, корень также должен измениться.

Это делает корень компактным обязательством для полного набора данных.

В Ethereum заголовки блоков содержат корни, суммирующие важные структуры данных.

Корень состояния суммирует состояние после блока.

Корень транзакций суммирует транзакции блока.

Корень квитанций суммирует квитанции транзакций блока.

Эти корни помогают независимым нодам согласовывать произошедшее, не доверяя центральному серверу.

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

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

Доказательства Меркла и префиксные деревья

Доказательство Меркла — это набор данных, подтверждающий, что значение включено в более крупную структуру данных с обязательством.

В префиксном дереве доказательство обычно включает узлы вдоль пути от корня к доказываемому значению.

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

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

Это позволяет легкому клиенту или смарт-контракту проверять определенное значение, не храня полное состояние.

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

Оно также может показать, что слот хранилища смарт-контракта имел определенное значение.

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

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

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

Префиксные деревья и легкие клиенты

Легкие клиенты — это блокчейн-клиенты, которые не хранят и не обрабатывают все данные, хранимые и обрабатываемые полными нодами.

Они полагаются на компактные доказательства, заголовки и доверенные криптографические обязательства.

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

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

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

Однако текущие доказательства дерева Меркла — Патрисии в некоторых случаях могут быть большими.

Ethereum.org поясняет, что текущие свидетели дерева Меркла слишком велики для эффективной поддержки клиентов без состояния в своей документации по деревьям Verkle.

Поэтому исследователи Ethereum изучают деревья Verkle и другие улучшения обязательств состояния.

Цель — облегчить проверку без ослабления безопасности.

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

Префиксные деревья и клиенты без состояния

Клиент без состояния — это клиент, способный проверять блоки без локального хранения полного текущего состояния.

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

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

Ethereum.org поясняет, что клиенты без состояния используют свидетельство данных состояния вместо собственной локальной копии всей базы данных состояния в своей дорожной карте клиентов без состояния и деревьев Verkle.

Проблема в том, что свидетельства, основанные на текущих структурах деревьев Меркла, могут быть слишком большими.

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

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

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

Поэтому проектирование структур данных напрямую связано с децентрализацией.

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

Префиксные деревья и деревья Verkle

Деревья Verkle — это предлагаемый путь обновления структуры данных состояния Ethereum.

Дерево Verkle сходно по назначению с деревом Меркла, но использует векторные обязательства для поддержки меньших свидетельств.

Ethereum.org поясняет, что деревья Verkle могут помочь нодам перестать хранить большие объемы данных состояния, не теряя способности проверять блоки, в официальной дорожной карте деревьев Verkle.

Это важно, потому что текущее дерево состояния Ethereum велико и затрудняет легковесную валидацию.

Деревья Verkle предназначены для уменьшения свидетельств и повышения их практичности для клиентов без состояния.

Они не являются тем же самым, что деревья Меркла — Патрисии.

Они входят в ориентированные на будущее усилия по улучшению доступа к состоянию и его проверки.

Для читателей глоссария ключевой момент состоит в том, что префиксные деревья не являются окончательно решенной темой.

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

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

Префиксные деревья и затраты на газ

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

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

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

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

Перевод токена может обновить балансы в хранилище контракта.

Транзакция DeFi может обновить множество слотов хранилища в нескольких контрактах.

Каждое обновление может способствовать росту состояния и работе по поддержанию дерева.

Это одна из причин, по которой разработчики блокчейнов уделяют внимание оптимизации хранилища.

Создание эффективных смарт-контрактов связано не только с экономией комиссий пользователей.

Оно также позволяет уменьшить долгосрочную нагрузку состояния на сеть.

Префиксные деревья и хранилище смарт-контрактов

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

Когда контракт постоянно хранит данные, эти данные становятся частью состояния блокчейна.

Корень хранилища контракта фиксирует его дерево хранилища.

Каждая переменная хранилища в конечном счете представлена через слоты хранилища.

Сложные типы данных Solidity, такие как mappings и массивы, кодируются в слоты хранилища согласно правилам компилятора.

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

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

Оно является частью криптографически зафиксированной глобальной базы данных.

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

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

Префиксные деревья и обозреватели блокчейна

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

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

За интерфейсом сам блокчейн хранит состояние и данные блоков в более технических формах.

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

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

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

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

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

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

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

Префиксные деревья и роллапы

Роллапы могут использовать собственные деревья состояния или префиксные деревья для отслеживания офчейн-состояния или состояния Layer 2.

Роллапу необходим способ зафиксировать текущее состояние и доказать допустимость переходов состояния.

Некоторые роллапы используют доказательства с нулевым разглашением, доказательства мошенничества, доказательства Меркла или другие структуры обязательств.

Даже если точная структура данных не является MPT Ethereum, часто сохраняется одна и та же базовая идея.

Система фиксирует большое состояние с помощью компактного корня.

Пользователи или контракты могут проверять утверждения относительно этого корня.

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

Роллапы — это не только более дешевые транзакции.

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

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

Префиксные деревья и мосты

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

Мосту может потребоваться доказать, что транзакция произошла или что значение хранилища изменилось.

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

Однако безопасность моста зависит от гораздо большего, чем само доказательство префиксного дерева.

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

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

Поэтому пользователям не следует считать, что слово «доказательство» делает мост безрисковым.

Доказательство должно быть связано с безопасной моделью проверки.

Префиксные деревья предоставляют мощный инструмент для подтверждения включения данных, но архитектура моста должна учитывать множество дополнительных рисков.

Качественный анализ моста рассматривает полный путь доверия от состояния исходной сети до действия в целевой сети.

Префиксные деревья и безопасность

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

Если кто-то изменяет сохраненное значение, хеши вдоль пути должны измениться.

Это изменение должно привести к другому корню.

Нода, сравнивающая вычисленный корень с ожидаемым, может обнаружить несоответствие.

Это ключевая часть криптографической целостности.

Однако префиксное дерево само по себе не является полноценным решением безопасности.

Оно не может помешать пользователю подписать вредоносную транзакцию.

Оно не может исправить ошибку смарт-контракта.

Оно не может сделать некорректную цену оракула правильной.

Оно не может защитить средства, если мост доверяет неверному корню.

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

Преимущества префиксных деревьев в блокчейн-системах

Первое преимущество префиксного дерева — организованное хранение данных типа «ключ — значение».

Второе преимущество — детерминированный поиск, помогающий независимым нодам получать одинаковый результат.

Третье преимущество — сжатие общих префиксов при использовании оптимизации в стиле Патрисии.

Четвертое преимущество — криптографическая проверка при объединении дерева с хешированием Меркла.

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

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

Седьмое преимущество — совместимость с исследованиями легких клиентов и клиентов без состояния.

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

Это не просто абстрактная информатика.

Они помогают реальным сетям хранить, проверять и обновлять финансовые данные.

Ограничения префиксных деревьев

Префиксные деревья могут быть сложными для правильной реализации.

Правила кодирования необходимо соблюдать точно, иначе корни не будут совпадать.

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

Рост состояния может сделать базовую базу данных тяжелой для нод.

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

Разные реализации клиентов должны согласовывать одинаковые правила дерева.

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

Свидетели дерева Меркла — Патрисии достаточно велики, поэтому Ethereum исследует деревья Verkle как более эффективную структуру будущего.

Эти ограничения не означают, что префиксные деревья плохи.

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

Распространенные заблуждения о префиксных деревьях

Первое заблуждение состоит в том, что префиксное дерево — то же самое, что обычное дерево.

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

Второе заблуждение состоит в том, что префиксное дерево автоматически обеспечивает криптографическую безопасность.

Базовое префиксное дерево не обеспечивает безопасность доказательств, если не объединено с хешированием или другим методом обязательств.

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

Корень состояния — это лишь компактное обязательство состояния, а не сама полная база данных.

Четвертое заблуждение состоит в том, что доказательство Меркла доказывает что-либо навсегда без контекста.

Доказательство имеет смысл только относительно определенного доверенного корня и правильных правил сети.

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

Большинство пользователей не взаимодействует с ними напрямую, но префиксные деревья влияют на доказательства кошельков, валидацию блоков, безопасность мостов и децентрализацию сети.

Как разработчикам следует воспринимать префиксные деревья

Разработчикам следует рассматривать префиксные деревья как часть системы обязательств состояния блокчейна.

Когда они пишут смарт-контракты, они создают изменения состояния, которые в конечном счете влияют на корни деревьев.

Когда они создают кошельки или индексаторы, они могут полагаться на данные, поступающие из состояния, обеспеченного деревом.

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

При оптимизации контрактов следует помнить, что постоянное хранилище создает издержки для всей сети.

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

Эти потребности могут влиять на выбор структуры данных.

Разработчику не нужно вручную реализовывать префиксное дерево для каждого dApp.

Однако понимание таких деревьев помогает избежать ошибочных предположений о хранении данных в блокчейне.

Оно также помогает понять, почему низкоуровневые правила клиентов так важны.

Как трейдерам и пользователям следует воспринимать префиксные деревья

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

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

Они являются частью проверяемого глобального состояния.

Когда транзакция изменяет баланс, это изменение обновляет криптографические обязательства внутри сети.

Поэтому хеш транзакции, номер блока и корень состояния могут использоваться для проверки.

Практический вывод для пользователей: доверяйте ончейн-проверке больше, чем скриншотам или сообщениям.

Если депозит отсутствует, важны хеш транзакции и данные обозревателя.

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

Если кошелек отображает баланс, этот баланс в конечном счете должен быть прослеживаем до состояния сети.

Префиксные деревья делают такую проверку возможной в фоновом режиме.

FAQ

Что такое префиксное дерево в криптоиндустрии?

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

Как произносится trie?

Trie обычно произносится как «трай».

Почему Ethereum использует префиксные деревья?

Ethereum использует модифицированные деревья Меркла — Патрисии для кодирования и проверки состояния, транзакций, квитанций и хранилища смарт-контрактов через криптографические корневые хеши.

Что такое дерево Меркла — Патрисии?

Дерево Меркла — Патрисии — это структура данных, объединяющая поиск в префиксном дереве, сжатие путей Патрисии и хеширование Меркла.

Что такое дерево состояния?

Дерево состояния — это структура данных, фиксирующая текущее состояние аккаунтов и контрактов блокчейна.

Что такое дерево хранилища?

Дерево хранилища — это дерево, относящееся к конкретному контракту и фиксирующее значения хранилища аккаунта смарт-контракта.

Что такое корень префиксного дерева?

Корень префиксного дерева — это хеш верхнего уровня, суммирующий все данные, хранящиеся в дереве.

Что произойдет, если одно значение в префиксном дереве изменится?

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

Является ли префиксное дерево тем же самым, что дерево Меркла?

Нет. Префиксное дерево организует данные по путям ключей, тогда как дерево Меркла организует данные преимущественно путем повторного хеширования листьев.

Что такое доказательство Меркла?

Доказательство Меркла — это набор данных, доказывающий, что значение принадлежит более крупной структуре данных, зафиксированной известным корнем.

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

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

Что такое деревья Verkle?

Деревья Verkle — это предлагаемое обновление структуры данных состояния, способное создавать меньшие свидетельства, чем текущие структуры деревьев Меркла.

Взаимодействуют ли пользователи с префиксными деревьями напрямую?

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

Являются ли префиксные деревья безрисковыми?

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

Заключение

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

В криптоиндустрии префиксные деревья становятся особенно мощными в сочетании с криптографическим хешированием.

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

Модифицированное дерево Меркла — Патрисии Ethereum — наиболее известный пример, поскольку оно поддерживает корни состояния, хранилища, транзакций, квитанций и доказательства Меркла.

Префиксные деревья помогают независимым нодам проверять, достигли ли они одинакового состояния после обработки блока.

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

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

Эти компромиссы — одна из причин, по которой Ethereum исследует деревья Verkle для уменьшения свидетельств и улучшения поддержки клиентов без состояния.

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

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

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