Bitcoin Forum

 Это перевод, оригинал статьи принадлежит Husires. Спасибо за полезную информацию! (https://bitcointalk.org/index.php?topic=5272933)

---

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

---

Оглавление

      1. Что такое дерево Меркла? (#post_point1)
      2. Криптографические хеш-функции (#post_point2)
      3. Как работают деревья Меркла? (#post_point3)
      4. Использование деревьев Меркла (#post_point4)
      5. Почему они используются в BTC? (#post_point5)



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

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

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


Корень Меркла: это хэш всех хэшей всех транзакций, которые являются частью блока в сети блокчейн.

Его структура используется для эффективной проверки целостности данных в группе.
Идея была создана и запатентована Ральфом К. Мерклом в 1979 году, срок действия патента истекает в 2002 году



Криптографические хеш-функции

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

Вы можете узнать больше, прочитав предыдущий раздел о хэш-функции для чайников (https://bitcointalk.org/index.php?topic=5265882.msg54908275#msg54908275)

Пример:

Code:

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 . Затем каждый фрагмент проходит через хеш-функцию, давая нам восемь различных хешей.

https://image.binance.vision/editor-uploads/761c2fdb12a544aa873a9e9a3ada274f.png

Источник: https://academy.binance.com/blockchain/merkle-trees-and-merkle-roots-explained

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

Нет. Вместо этого мы собираемся взять каждую пару хешей, объединить их, а затем хешировать вместе. Итак, мы хешируем hA + hB , hC + hD , hE + hF и hG + hH . В итоге получаем четыре хэша. Затем мы проводим еще один раунд хеширования, чтобы получить два. Наконец, мы хэшируем оставшиеся два, чтобы получить наш главный хеш - корень Меркла (или хеш-дерево).

https://image.binance.vision/editor-uploads/3dea212055754dd2b0741845c95d3d49.png

Источник: https://academy.binance.com/blockchain/merkle-trees-and-merkle-roots-explained

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

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

К счастью, есть удобный способ проверить, какой фрагмент изменен. В нашем случае, допустим, это 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 (https://bitcoin.org/bitcoin.pdf)

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

Майнинг: Блок Биткойн состоит из двух частей: заголовка (фиксированного размера) и списка транзакций (переменного размера).
Часто большая часть блока остается прежней, а данные Nonce изменяются.

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

Следовательно, любое изменение в списке транзакций приведет к изменению корня Меркла и, таким образом, отклонит блок.

---

Источники

Code:

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/

Да какое тут нахрен понимание. Это просто пересказ этой статьи (https://academy.binance.com/en/articles/merkle-trees-and-merkle-roots-explained). Проблема в том что это пересказ двоечника, который сам нихрена в этой статье не понял, но пытается что-то промямлить по теме вопроса, чтобы ему поставили тройку.

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

zasad@ , надо признать, что как новичок и чайник я ничего не понял. Уж коле ты ищешь что-то в раздел новичков, то тема должна быть раскрыта предельно ясно. Здесь же ты схалтурил, так что присоединюсь к предыдущему оратору.
Дерево Меркла и корень Меркла?

A-Bolt и stmar спасибо за критику.

Прежде чем опубликовать  перевод по просьбе автора (https://bitcointalk.org/index.php?topic=5274219.0), я сверил все термины и прочитал дополнительно несколько статей, чтобы убедится, в правильности перевода. Базовую информацию о теме я получил. Если новичкам не понятно, они могут изучить больше материала по ссылкам в конце перевода.
Когда разбираюсь в разных вопросах, я привык читать много статей по теме. В RU форуме принято считать что все должно быть идеально, попробуйте сначала сами, потом требуйте от других и критикуйте.
Профи всегда недовольны, я с ними никогда не спорил :D

Новичкам непонятно, мне непонятно, может быть, вам понятно?

Рассмотрим характерную цитату:


Сперва речь идёт об одном большом файле: "есть большой файл размером 8 ГБ". Потом, внезапно, появляется "если каждый файл в нем совпадает со всеми данными". Большой файл превратился в несколько файлов, да ещё и "в нём". В чём, в нём? С какими "всеми данными" должен совпадать "каждый файл"?

Дальше - больше: "Вы можете сравнивать каждый файл отдельно, пока не дойдете до последнего файла". С чем сравнивать? У нас изначально был один файл и один хеш, соответствующий этому файлу. Если нужно проверить соответствие одного файла одному хешу, при чём тут остальные файлы?

Здесь написан бред - набор бессвязных бессмысленных фраз. Если вы понимаете, что здесь написано, поясните, что хотел сказать автор. Если же вы сами не понимаете написанного, значит ваш перевод подпадает под п.1 Правил: "Не размещать пустые или имеющие низкое значение сообщения или темы."

Есть такая замечательная книга под названием "Mastering Bitcoin", в которой деревьям и корням Меркла посвящена целая глава. Читайте, зачитывайтесь. Книга доступна бесплатно на русском языке здесь: https://bitcoinbook.info/wp-content/translations/ru/book.pdf Если вы чайник и после прочтения русского варианта ничего не поймёте, то ничего удивительного. При переводе на другой язык иногда теряется весь смысл. Рекомендую прочитать оригинальную версию на английском языке, она тоже доступна бесплатно здесь: https://github.com/bitcoinbook/bitcoinbook Если после прочтения оригинала вы тоже ничего не поймёте, то задумайтесь, а надо ли оно вам вообще? Использовать биткоин можно и без знания таких глубинных процессов.

A-Bolt спасибо. Исправил перевод.
Если что-то еще режет глаз, скажите.


Captain-Cryptory, несли A-Bolt  еще раз глянет, то получится хороший материал для первичного изучения

Глава "Как работают деревья Меркла?" стала нести хоть какой-то смысл, но теперь это уже не чистый перевод Husires, а винегрет из переводов из нескольких источников. Ну, хуже не стало, и ладно.

На хороший материал для изучения указал witcher_sense. Книгу "Mastering Bitcoin" написал профессионал в области IT, а её русский перевод сделан на достаточном для понимания уровне.



Во многих языках, в особенности тех, которые наследуют синтаксис языка C, для конкатенации строк используется оператор "+". Эти языки (С++, Java, JavaScript, C#, Python, Go, Rust) широко распространены и, поэтому, я не представляю, кого может ввести в заблуждение "+", в качестве оператора конкатенации.