May 7, 2023

Merkle Trees and Merkle Proofs

Если вы хотите понять Bitcoin, Ethereum и технологию блокчейн, вам нужно учиться.

  • Как Merkle trees (деревья Меркла) представляют большие наборы данных
  • Как работают Merkle proof (доказательства Меркла)
  • Почему Merkle trees так эффективно

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

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

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

Также называемые hash tree, они были названы в честь Ральфа Меркле (который предложил их в 1987 году).


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

Затем два хеша объединяются и хешируются снова, создавая новый (меньший) список хешей. Цикл повторяется, пока не останется один хеш.

Верхний хеш (также называемый корневым хешем или корневой нодой/узлом) представляет собой единственное значение, которое представляет уникальную структуру Merkle tree.

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

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

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


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

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


Однако здесь возникает интересная дилемма: можно ли подтвердить, что отдельный фрагмент данных существует внутри Merkle trees?

Иначе говоря, может ли Merkle trees что-то делать, кроме проверки ВСЕГО набора данных?

Ответ: конечно!


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

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

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

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


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

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


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

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


Когда вы видите деревья Меркла в реальной жизни, помните это:

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

Оригинал

Фундаментальный Guide по Ethereum

Ethereum : Всемирный Компьютер

Основы компьютерных наук: Машины Тьюринга и полнота Тьюринга.

Виртуальная машина Ethereum (EVM)

Консенсус Ethereum

Введение в MEV

The Ethereum Blockchain

Основы компьютерных наук: Блокчейн Компьютеры

Ethereum, Оракулы и Chailink



Канал про DeFi

Чат defi degens
Чат по SocialFi, On chain games, Narrative trading