Основы криптографических инструментов: хеш-функции и деревья Меркла
Содержание
О чем эта статья?
Блокчейны позволяют людям приходить к соглашению без посредников. Вместо доверия блокчейны используют криптографические доказательства. Для создания этих доказательств применяются криптографические примитивы. Но что это такое?
В этой статье мы рассмотрим два криптографических примитива, необходимых для криптографических доказательств в блокчейнах: хеш-функции и деревья Меркла. Мы разберем основные принципы работы хеш-функций, их роль в блокчейнах и понятие хеш-указателей. Затем рассмотрим традиционные и параллельные деревья Меркла и объясним их значение для Solana.
Что такое криптографический примитив?
Криптографический примитив — это операция или алгоритм, лежащие в основе криптографических протоколов и систем. Криптографические примитивы соотносятся с криптографическими протоколами так же, как атомы с молекулами: это строительные блоки для более сложных решений. Генераторы случайных чисел, схемы обязательств и криптография с открытым ключом — примеры криптографических примитивов.
Сами по себе криптографические примитивы весьма ограничены. В сочетании они обеспечивают базовые функции безопасности: аутентификацию, конфиденциальность и целостность. Объединение криптографических примитивов — сложный процесс, который требует тщательного планирования и глубокого понимания их взаимодействия. При этом необходимо учитывать требования безопасности и поставленные цели. Методы объединения криптографических примитивов можно разделить на следующие основные категории:
- Последовательная композиция: применение одного примитива после другого (например, цепочка хешей)
- Параллельная композиция: одновременное и независимое использование примитивов (например, одновременное шифрование и хеширование данных)
- Иерархическая композиция: использование одного криптографического примитива внутри другого (например, деревья Меркла)
Понимание того, что такое криптографические примитивы, как они работают и какие тонкости возникают при их объединении, помогает разбираться в безопасных и эффективных системах и проектировать их. Один из наиболее распространенных криптографических примитивов — хеш-функция.
Что такое хеш-функция?
Хеш-функция — это криптографическая функция, которая принимает данные любого размера и возвращает значение фиксированного размера. Возвращаемое значение называют дайджестом или хешем. К популярным алгоритмам хеширования относятся SHA-1, SHA-2, SHA-3, MD5 и Argon2. Хеш-функции используются во всех компонентах блокчейнов, поэтому важно понимать, что это такое и как они работают.
Простая аналогия
Представьте, что вы печете изысканный шоколадный торт. Он состоит из нескольких коржей, для каждого из которых нужны свои ингредиенты. Пока вы готовите, друг пишет вам и спрашивает, чем вы занимаетесь. Подробно объяснять, как вы готовили торт и какие ингредиенты использовали, было бы слишком утомительно. Поэтому вы решаете отправить другу фотографию шоколадного торта.
Здесь фотография торта служит хешем — простым и компактным представлением чего-то гораздо более сложного. Ваш друг не узнает обо всех ингредиентах торта, но получит общее представление о том, что вы испекли. Предположим, шоколадный торт был украшен малиной. Если убрать ее или заменить клубникой, фотография торта будет заметно отличаться от конечного результата. Аналогично, любое изменение хешируемых данных создает новое значение хеша.
Свойства хорошей криптографической хеш-функции
Следует признать, что приведенное выше определение хеш-функции вводит в заблуждение. Хеш-функция может возвращать хеш переменного размера. Она также может возвращать одинаковый хеш для двух разных входных значений. Кроме того, кому-то может быть очень легко восстановить исходные данные по хешу. Приведенное ранее определение относилось к хорошей криптографической хеш-функции. Но что делает криптографическую хеш-функцию хорошей?
Хорошая хеш-функция детерминирована: одинаковые входные данные всегда создают одинаковый результат. Если хешировать строку «baseball», эта хеш-функция при каждом вызове будет возвращать один и тот же хеш независимо от системы. Отчасти это также означает, что размер хеша не зависит от размера входных данных. Это важно для эффективности обработки и хранения данных. Уникальные входные данные всегда должны создавать уникальный результат фиксированного размера — это явный признак хорошей криптографической хеш-функции.
Хорошая хеш-функция устойчива к нахождению прообраза. Это означает, что восстановить входное значение по его хешу невозможно с практической точки зрения из-за вычислительной сложности. Поэтому, получив хеш, вы не должны иметь возможности определить, какие данные его создали. Отсюда также следует, что два разных набора данных не должны создавать одинаковый хеш. Хеш-функция считается устойчивой к коллизиям, если никакие два входных значения никогда не создают одинаковый хеш.
Для хорошей хеш-функции характерен лавинный эффект: небольшое изменение входных данных должно приводить к радикальному изменению хеша. Даже замена одного символа должна создавать совершенно другой хеш. Поэтому результат хеширования не должен раскрывать сведения о входных данных или содержать узнаваемые закономерности. Обратите внимание на различия между хешами на изображении выше. Фраза о том, что рыжая лиса «бежит», создает радикально иной хеш по сравнению с фразой, в которой рыжая лиса «идет». При этом ничто не указывает на то, что эти два хеша содержат почти идентичную информацию.
Хорошая хеш-функция должна быстро вычисляться. Медленные хеш-функции непрактичны для вычислений в реальном или близком к реальному времени, например при проверке транзакций. Медленная хеш-функция может стать серьезным узким местом, ограничивающим пропускную способность и производительность сети. Быстрая хеш-функция необходима для эффективной и безопасной работы блокчейна.
Почему это важно для блокчейнов?
Блокчейн — это децентрализованный распределенный реестр, который регистрирует транзакции в своей сети. Эти транзакции объединяются в блоки, надежно связанные с помощью хорошей хеш-функции. Каждый блок содержит данные транзакций, временную метку и хеш предыдущего блока. Поскольку хеш каждого блока зависит от хеша предыдущего блока, любое изменение содержимого блока изменит его хеш и сделает недействительными все последующие блоки. Такой процесс использования предыдущих хешей для создания нового называется построением цепочки хешей.
Добавление нового блока в блокчейн называется подтверждением. Подтверждение проверяет и защищает все транзакции в новом блоке, а также все предыдущие блоки. С каждым новым подтверждением изменять предыдущие блоки становится сложнее. Чтобы изменить предыдущий блок, злоумышленнику пришлось бы заново вычислить все последующие хеши. Поэтому цепочка хешей делает изменение блокчейна практически невозможным после того, как блок получит значительное количество подтверждений.
Проще говоря, блокчейн — это цепочка блоков, защищенная хеш-функциями. Но как именно один блок указывает на другой? Да, для связывания блоков используется криптографическая хеш-функция, но как тогда получить доступ к данным предыдущих блоков? Ведь хорошая криптографическая хеш-функция должна быть устойчива к нахождению прообраза.
Что такое хеш-указатель?
Указатель — это переменная, которая хранит адрес определенных данных в памяти. Доступ к данным по этому адресу получить легко, поскольку указатель «указывает» на их местоположение. Хеш-указатель — это структура данных, похожая на указатель, но дополнительно содержащая криптографический хеш данных, на которые она ссылается. Таким образом, хеш-указатель сообщает, где получить доступ к определенным данным, и позволяет проверить их целостность.
Структуру блокчейна точнее описывать как связный список, использующий хеш-указатели. Хеш предыдущего блока — это хеш-указатель на набор транзакций и хеш всех этих транзакций. Хеш-указатели обеспечивают связывание блоков, целостность каждого блока и проверку того, что новые блоки корректно следуют за предыдущими.
Хеш-указатели позволяют эффективно связывать блоки. Но как быть с транзакциями внутри блока? Если блок содержит тысячу транзакций, разве проверка каждой из них по отдельности не потребует больших затрат?
Что такое дерево Меркла?
Дерево Меркла — это структура данных для организации и проверки больших наборов данных. Данные организованы в древовидную структуру, где каждый лист, или узел, помечен хешем набора данных. Каждый узел, не являющийся листом, содержит хеш своих дочерних узлов. Деревья Меркла используются для проверки транзакций, включенных в определенные блоки, которые распространяются в блокчейне. Как это работает?
Транзакции объединяются в список, образующий блок. Каждая транзакция в списке хешируется с помощью хорошей хеш-функции. Полученные хеши становятся листовыми узлами. Затем пары листовых узлов хешируются вместе, создавая новый уровень хешей. Процесс повторяется до тех пор, пока не останется единственный хеш — корень Меркла. Корень Меркла хранится в заголовке блока и служит цифровым отпечатком всех транзакций в этом блоке. Корень Меркла также можно называть хешем блока. Поэтому, когда мы говорим, что новый блок связан с предыдущим с помощью хеша предыдущего блока, это означает, что корень Меркла предыдущего блока используется как часть хеша нового блока.
Деревья Меркла позволяют эффективно проверять отдельные транзакции внутри блока. При традиционном подходе для проверки конкретной транзакции пришлось бы проверять каждую транзакцию, что требует много времени и ресурсов. Деревья Меркла предоставляют криптографический «короткий путь» для такой проверки — доказательство Меркла. Доказательство Меркла — это путь от листового узла транзакции до корня Меркла. На изображении выше это путь от Data A к корню Меркла. В путь также входят соседние узлы: листья, смежные с каждым узлом пути, но не являющиеся частью самого пути. Проверяющая сторона может вычислить хеш по пути доказательства и сравнить его с корнем Меркла. Если полученный хеш совпадает, можно быть уверенным, что транзакция действительна и не была изменена.
Лист можно изменить, хешировав новые данные листа и заново вычислив корень Меркла. Новый корень Меркла используется для проверки изменений и делает предыдущее доказательство недействительным. В сети с высокой пропускной способностью, такой как Solana, валидаторы могут быстро и последовательно получать запросы на изменение ончейн-деревьев Меркла, например в пределах одного слота. Каждое изменение данных пришлось бы вычислять последовательно, иначе каждый последующий запрос на изменение становился бы недействительным из-за предыдущего запроса, выполненного в том же слоте. Изменение данных листа и вычисление нового корня Меркла часто встречаются в блокчейнах. Как же обрабатывать быстрые изменения?
Что такое параллельное дерево Меркла?
Параллельное дерево Меркла — это дерево Меркла, оптимизированное для одновременного чтения и записи. Оно хранит защищенный журнал последних изменений, их корневой хеш и доказательство для его получения. Этот журнал хранится ончейн в отдельном аккаунте дерева. Для него задается максимальное количество изменений, при котором корень Меркла остается действительным. Это максимальное количество изменений называется maxBufferSize. Поэтому, когда валидатор быстро и последовательно получает запросы на изменение ончейн-дерева Меркла, он может использовать этот журнал как источник достоверных данных. Это позволяет внести до maxBufferSize изменений в дерево за один слот.
Параллельные деревья Меркла совершенствуют традиционные деревья Меркла и подходят для сред с высокой пропускной способностью, таких как Solana. На размер и стоимость создания ончейн-дерева Меркла в Solana, а также на количество параллельных изменений влияют три параметра:
- Максимальная глубина
- Максимальный размер буфера
- Глубина кроны
Максимальная глубина — это максимальное количество переходов от любого листа к корню Меркла. maxDepth используется для определения максимального количества узлов, хранящихся в дереве. Его можно рассчитать по формуле: numberOfNodes = 2 ^ maxDepth. Глубину дерева необходимо задать при создании, поэтому с помощью этой формулы важно определить, сколько элементов данных должно хранить дерево.
Как уже говорилось, максимальный размер буфера — это максимальное количество изменений, которые можно внести в дерево, пока его корень Меркла остается действительным.
Глубина кроны относится к части дерева Меркла, которая хранится ончейн. Эти кешированные доказательства используются для сверки хеша с ончейн-корнем Меркла. Для проверки исходного владельца листа при записи в него необходимо использовать полный путь доказательства. Например, запись в дерево потребуется при передаче NFT. Крона позволяет сократить размер доказательства и не использовать доказательство размером maxDepth для проверки дерева. Для дерева с maxDepth, равным 20, потребуется доказательство размером 20. При кроне глубиной 15 с каждой транзакцией записи достаточно отправить доказательство размером 5. Таким образом, при большей глубине кроны вы платите больше при создании дерева, но впоследствии можете отправлять доказательства меньшего размера.
Глубина кроны — один из основных факторов, определяющих стоимость создания дерева. Чем больше глубина кроны, тем больший аккаунт требуется. Разработчики могут использовать пакет @solana/spl-account-compression, чтобы рассчитать необходимое пространство для дерева заданного размера и стоимость выделения этого пространства для ончейн-дерева. С помощью функции getConcurrentMerkleTreeAccountSize разработчики могут рассчитать необходимое пространство для аккаунта на основе его параметров, а затем применить getMinimumBalanceForRentExemption к полученному значению, чтобы определить итоговую стоимость в лампортах.
Solana использует параллельные деревья Меркла для сжатия состояния. Сжатие состояния — это метод создания хеша офчейн-данных и его хранения ончейн для безопасной проверки. Самый популярный сценарий использования сжатия состояния — сжатые NFT, поскольку оно значительно снижает стоимость выпуска. Например, выпуск миллиарда NFT в Solana обойдется в 507 $SOL вместо 12 000 000 $SOL для «обычных» NFT. Теперь у вас есть прочное понимание хеширования и деревьев Меркла. В одной из следующих статей мы подробнее рассмотрим сжатые NFT!
Заключение
Поздравляем! В этой статье мы разобрали хеш-функции и деревья Меркла — два криптографических примитива, жизненно важных для блокчейнов. Разобраться в блокчейнах непросто: это сложные распределенные системы, для понимания которых требуются обширные технические знания. Часто предполагается, что обычный разработчик, пользователь или инвестор уже обладает такими знаниями. В этой статье предварительное знакомство с криптографическими примитивами не требуется. Мы начинаем с основ, а затем переходим к более сложному обсуждению традиционных и параллельных деревьев Меркла. Эти фундаментальные знания необходимы перед изучением более сложных тем, таких как сжатые NFT. Теперь вам будет проще ориентироваться в кодовых базах и обсуждениях криптографических примитивов и более сложных криптографических решений.
Если вы дочитали до этого места, anon, спасибо!
Дополнительные ресурсы и материалы
Похожие статьи
Подпишитесь на Helius
Следите за новостями разработки на Solana и получайте уведомления о наших публикациях