Это перевод, оригинал статьи принадлежит Husires. Спасибо за полезную информацию!
Дисклеймер: информация, содержащаяся в этой статье, является результатом моего понимания деревьев Меркла и корней Меркла и может содержать некоторые ошибки. Если найдете, то сообщите об этом.
Оглавление 1.
Что такое дерево Меркла? 2.
Криптографические хеш-функции 3.
Как работают деревья Меркла? 4.
Использование деревьев Меркла 5.
Почему они используются в BTC?
Источник: Bitcoin whitepaper
Дерево Меркла (также известное как хеш-дерево) дерево, в котором каждый листовой узел помечен криптографическим хешем блока данных, а каждый нелистовой узел помечен криптографическим хешем меток его дочерних узлов.
В дереве Меркла каждый нелистовой узел помечен хешем меток его дочерних узлов (или хешем значения листа в нижней части дерева), процесс, который повторяется, двигаясь вверх по дереву, пока остается единственный хеш: корень Меркла.
Корень Меркла: это хэш всех хэшей всех транзакций, которые являются частью блока в сети блокчейн.
Его структура используется для эффективной проверки целостности данных в группе.
Идея была создана и запатентована Ральфом К. Мерклом в 1979 году, срок действия патента истекает в 2002 году
Криптографические хеш-функцииХеш-функция - это любая функция, которая позволяет нам получать выходные данные фиксированного размера, поскольку она полностью уникальна для входных и сама функция детерминирована.
Это также приводит к значительной экономии на хранении и помогает повысить эффективность.
Вы можете узнать больше, прочитав предыдущий раздел о
хэш-функции для чайников Пример:
In-put: H
Out-put: 44bd7ae60f478fae1061e11a7739f4b94d1daf917982d33b6fc8a01a63f89c21
In-put: Husires
Out-put: 198d93f2c0bff9767d4cdc047f2191b0921d81e410c10c0744311fadfdb516f9
In-put: Today is 1/9/2020 and i used my username: Husires
Out-put: 2afbf1c88e101259002a592dbcc9340af2f0fa8f51a06e77910b6aca63a97c0c
In-put: Today is 1/9/2020 and i used my username: Husires
Today is 1/9/2020 and i used my username: Husires
Today is 1/9/2020 and i used my username: Husires
Today is 1/9/2020 and i used my username: Husires
Today is 1/9/2020 and i used my username: Husires
Out-put: 43a322d0eb09caaf26762ae18a369f5e8e06ac32c9e6a0d9fb4972aa53654db8
Что вы получили из этого примера?
Как работают деревья Меркла?Предположим, вы хотите скачать большой файл. При использовании программного обеспечения с открытым исходным кодом вы обычно хотите проверить, соответствует ли хэш загруженного файла хешу, опубликованному разработчиками. Если да, то вы знаете, что файл на вашем компьютере точно такой же, как и у них.
Если хеши не совпадают, у вас проблема. Вы либо загрузили вредоносный файл, замаскированный под программное обеспечение, либо он загрузился некорректно и, следовательно, не будет работать. В последнем случае вы, вероятно, не будете слишком счастливы, если вам придется некоторое время подождать, пока файл загрузится. Теперь вам нужно перезапустить процесс и надеяться, что он снова не будет поврежден.
Вы думаете, если бы существовал более простой способ сделать это . К счастью, именно здесь на помощь приходят деревья Меркла. С помощью одного из них ваш файл разбивается на части. Если бы это был файл размером 50 ГБ, вы могли бы разделить его на сто частей, каждый размером 0,5 ГБ. Затем он будет загружен по частям. По сути, это то, что вы делаете, когда загружаете торрент-файлы.
В этом случае ваш источник предоставит вам хеш, известный как корень Меркла . Этот единственный хеш представляет собой совокупность хешей всех частей, из которых состоит ваш файл. Корень Меркла значительно упрощает проверку данных.
Для простоты давайте рассмотрим пример, в котором мы используем файл размером 8 ГБ, разбитый на восемь фрагментов. Назовем разные фрагменты от A до H . Затем каждый фрагмент проходит через хеш-функцию, давая нам восемь различных хешей.
Хорошо, у нас есть хэш всех фрагментов, поэтому, если один из них неверный, мы узнаем, сравнив его с исходным, верно? Возможно, но это тоже невероятно неэффективно. Если в вашем файле тысячи фрагментов, действительно ли вы собираетесь хешировать их все и тщательно сравнивать результаты?
Нет. Вместо этого мы собираемся взять каждую пару хешей, объединить их, а затем хешировать вместе. Итак, мы хешируем hA + hB , hC + hD , hE + hF и hG + hH . В итоге получаем четыре хэша. Затем мы проводим еще один раунд хеширования, чтобы получить два. Наконец, мы хэшируем оставшиеся два, чтобы получить наш главный хеш - корень Меркла (или хеш-дерево).
Структура выглядит как перевернутое дерево. В нижнем ряду у нас есть листья, из которых складываются узлы и, наконец, корень.
Теперь у нас есть корень Меркла, представляющий загруженный файл. Мы можем сравнить этот корень Меркла с хешем, предоставленным источником. Если он совпадает, отлично! Но если хеши разные, мы можем быть уверены, что данные были изменены. Другими словами, один или несколько фрагментов создали другой хэш. Таким образом, любое небольшое изменение данных даст нам совершенно другой корень Меркла.
К счастью, есть удобный способ проверить, какой фрагмент изменен. В нашем случае, допустим, это hE . Вы должны начать с того, что спросите у партнера два хэша, которые создали корень Меркла ( hABCD и hEFGH ). Ваше значение hABCD должно совпадать с их значением, поскольку в этом поддереве нет ошибки. Но у hEFGH совпадений не будет, так что вы знаете, что нужно искать ошибку там. Затем вы запрашиваете hEF и hGH и сравниваете их со своими. hGH совпадет, и вы знаете, что в hEF ошибка. Наконец, вы сравниваете хеши hE и hF. Теперь вы знаете что фрагмент hE неверный, поэтому вы можете повторно его загрузить.
Подводя итог, можно сказать, что дерево Меркла создается путем разделения данных на множество частей, которые затем многократно хешируются для формирования корня Меркла. Затем вы можете эффективно проверить, что с частью данных что-то пошло не так.
https://academy.binance.com/en/articles/merkle-trees-and-merkle-roots-explainedИспользование деревьев МерклаМожет использоваться для проверки любого типа хранимых данных, помогает гарантировать, что блоки данных, полученные от других одноранговых узлов в одноранговой сети, принимаются неповрежденными и неизменными, используются в файловых системах IPFS, Btrfs и ZFS,
BTC и Ethereum, а также ряда систем NoSQL, таких как Apache Cassandra, Riak и Dynamo.
Почему они используется в BTC?Они являются неотъемлемой частью каждого блока, поскольку их можно найти в заголовках блоков.
Используйте его в SPV: Многие из нас имеют ограниченные ресурсы с точки зрения места на диске и скорости Интернета, поэтому все мы полагаемся на легких клиентов, и вместо загрузки всех транзакций блоков, вам требуется доказательство Меркла - свидетельство, предоставляемое полной нодой, подтверждающее, что ваша транзакция находится в определенном блоке.
Если мы вернемся к предыдущему примеру, мы можем проверить с помощью 3 шагов вместо 7 шагов, например, для проверки hB. Если у нас есть hA, мы можем отработать hAB, поэтому мы можем вычислить hABCD с помощью hCD и с hEFGH, мы можем проверить, что полученный корень Меркла совпадает с корнем из заголовка блока.
Только 3 шага.
Вы можете прочитать подробнее на
https://bitcoin.org/bitcoin.pdfУ него есть некоторые недостатки в случае успешной атаки 51%, о которых будет рассказано в другой теме.
Майнинг: Блок Биткойн состоит из двух частей: заголовка (фиксированного размера) и списка транзакций (переменного размера).
Часто большая часть блока остается прежней, а данные Nonce изменяются.
Корень Меркла упрощает весь процесс, майнер выбирает все транзакции, которые он хочет включить в блок, создавая дерево Меркла, и ему нужно только хешировать заголовок блока, а не весь блок.
Следовательно, любое изменение в списке транзакций приведет к изменению корня Меркла и, таким образом, отклонит блок.
Источники
https://en.wikipedia.org/wiki/Merkle_tree
https://brilliant.org/wiki/merkle-tree/
https://www.youtube.com/watch?v=fB41w3JcR7U
https://golden.com/wiki/Merkle_tree-W3DMKV
https://academy.binance.com/blockchain/merkle-trees-and-merkle-roots-explained
https://blockonomi.com/merkle-tree/
