Что такое корень Меркла?

В статье Bitcoin wiki Vocabulary объясняется, почему существует корень Merkle:

Каждая транзакция имеет связанный с ней хэш. В блоке все хэши транзакций в блоке сами хешируются (иногда несколько раз — точный процесс сложен), и результатом является корень Меркла. Другими словами, корень Меркла — это хеш всех хэшей всех транзакций в блоке. Корень Merkle включен в заголовок блока. С помощью этой схемы можно безопасно проверить, была ли транзакция принята сетью (и получить количество подтверждений), загрузив только крошечные заголовки блоков и дерево Меркла — загрузка всей цепочки блоков не требуется. Эта функция в настоящее время не используется в биткойнах, но будет в будущем.

Как вы можете проверить, была ли транзакция проверена только с использованием корней Merkle? Как работает этот механизм?

Хотя я мог сразу понять определение Merkle Tree и Root, я изо всех сил пытался понять более широкий контекст и их использование, как и многие сообщения в этой теме, пока не провел немного больше исследований. Я пытаюсь объяснить сценарий здесь .

Ответы (6)

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

Чтобы понять это, сначала поймите концепцию дерева. Рассмотрим блок из 8 транзакций. Представьте себе каждую из этих 8 транзакций в основании пирамиды: они называются листьями. На второй ярус пирамиды положите четыре «ветви» и от каждой из них проведите по две линии к листьям так, чтобы на каждой ветке было прикреплено по два листа. Теперь соедините эти четыре ветви с двумя ветвями на уровне пирамиды 3 и с одной ветвью (которая называется корнем дерева) на вершине пирамиды. (В этом примере наше дерево растет вверх ногами.)

Теперь мы можем начать понимать процесс хеширования. Хешируйте хэши «листьев» и включите их как часть ветвей 2-го уровня, к которым прикреплены эти листья (они называются дочерними узлами и родительскими узлами). Теперь хешируйте хэши этих хэшей и включите их как часть ветвей третьего уровня. И так далее. (И если у вас было более 8 транзакций, все, что вам нужно, это больше уровней пирамиды.)

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

Так как же это поможет нам, если потенциально не потребуется весь блокчейн? Потому что мы могли бы проверять транзакции по мере необходимости. Если у нас есть транзакция, которая утверждает, что она была из блока № 234133, мы можем получить транзакции для этого блока, проверить дерево Меркла и узнать, что транзакция действительна. Мы можем сделать это, не обязательно зная все транзакции из #234132 или #234134, потому что мы знаем, что блоки защищены от несанкционированного доступа.

Еще лучше, если мы знаем, где она находится в дереве Меркла, и знаем хэши ветвей, нам даже не нужны все транзакции из #234132. (В этом блоке было 868.) Мы начинаем только с нашей транзакции и ее родственного элемента (если он есть), вычисляем хэш этих двух и проверяем, соответствует ли он ожидаемому значению. Из этого мы можем запросить родственную ветвь этого, вычислить хэш этого и проверить его. И продолжайте этот процесс вверх по дереву. Для этого требуется всего десять проверок для 868 транзакций. (Это одна из замечательных особенностей деревьев, они могут хранить множество значений с относительно небольшим количеством слоев.)

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

Короче говоря, дерево Меркла создает единственное значение, которое доказывает целостность всех транзакций под ним. Сатоши мог просто включить хэш большого списка всех транзакций в заголовок биткойна. Но если бы он это сделал, вам пришлось бы хэшировать весь список транзакций, чтобы проверить его целостность. Таким образом, даже при очень большом количестве транзакций работа, которую вам нужно выполнить (и количество хэшей, которые вам нужно запросить/загрузить), чтобы проверить целостность, составляет только журнал (O).

[Как всегда, не стесняйтесь редактировать это. Это в первую очередь просто вывод с моей стороны, исходя из спецификации.]

Заголовок блока не включает идентификаторы транзакций из транзакций в блоке, не так ли? Таким образом, в основном идея последней части цитаты будет работать только в том случае, если txid были включены в заголовки блоков.
Он читается как «заголовок блока и дерево Меркла». Это имеет больше смысла. Позволяет ли исходный протокол запрашивать деревья Меркла и/или заголовки, включающие их?
Что делать, если мы не знаем номер блока транзакции. В этом случае нам нужно перебирать все блоки в цепочке блоков? @Дэвид Огрен
Может быть, это плохой вопрос, но что, если я найду две определенные транзакции с одинаковыми хэшами с атакой дня рождения и сделаю одну из этих транзакций, а позже заявлю, что я сделал другую. Как мне доказать свою неправоту?
Слишком долго отвечать на ваш вопрос здесь @tgwtdt. Короче говоря, вы не можете выполнить атаку на день рождения, потому что у вас нет произвольного контроля над входными данными. Во-вторых, даже атака дня рождения на SHA-256 практически невозможна. Но, в целом, да, если вы сможете найти способ использовать SHA-256, то вы сможете делать в биткойне всевозможные гадости: трудность реверсирования алгоритма хеширования является основополагающим принципом. С другой стороны, безопасность хеш-алгоритма — очень хорошо изученная область.

«Рисунок 7-2. Расчет узлов в дереве Меркла» из Mastering Bitcoin показывает корень Меркла (H ABCD ) списка из четырех транзакций: Tx A, Tx B, Tx C и Tx D:Рисунок 7-2. Вычисление узлов в дереве Меркла

Чтобы убедиться, что транзакция, например, с хэшем HK, является действительной транзакцией (т. е. частью списка из 16 транзакций в этом примере с хэшами H A , H B , ... H P ), нужно только выполнить не более 2*log 2 (N) < N хэшей, как показано на пути Меркла здесь:

Рисунок 7-5. Путь Меркла, используемый для подтверждения включения элемента данных

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

А путь Меркла , необходимый для проверки того, что H k соответствует корню Меркла, в приведенном выше примере содержит только 4 хэша. Путь Меркла занимает гораздо меньше места, чем хранение всех транзакций в блоке. (В приведенном выше примере: 4 хэша занимают гораздо меньше места, чем 16.) Вот почему SPV легче.

В этом случае N = 16, а 2*log 2 (16) = 5,55… действительно меньше 16.

Чтобы убедиться, что транзакция: Как мы узнаем точное местоположение Hk на дереве Меркла? @Geremia
@Avatar Чтобы построить пути Меркла с нуля, необходимо знать все транзакции. Кроме того, подделать поддельный путь Меркла, соответствующий заданному корню Меркла, будет даже сложнее, чем взломать SHA256.
Например, из корня, когда мы следуем: вправо, влево, вправо, влево, мы достигаем Hk, что мы хотим проверить. Но откуда мы могли знать, что должны следовать по этому пути? @Geremia
@Avator Проверка пути Merkle продолжается от листового узла к корню Merkle.
Теперь стало намного яснее. Но опять же, как алгоритм может знать, с какого листа он должен начать. В вашем примере есть 16 листьев, так как мы можем определить начальную точку Hk на листьях дерева. @Geremia
@Avatar Извините, я хотел сказать, что нужно просто найти транзакцию в «списке транзакций».
Как я понимаю, мы знаем индекс всех транзакций, на каком листе они расположены. @Geremia
ссылка на обсуждение кажется мертвой ... до сих пор не нашел объяснения: если он ищется из «списка транзакций», если позиция основана, не означает ли это, что эта транзакция является действительной транзакцией?
@limboy Сервер SPV отправляет путь Merkle транзакции облегченному клиенту; этого достаточно для облегченного клиента, чтобы убедиться, что транзакция действительна, при этом легковесному клиенту не требуется список всех транзакций.
2-я диаграмма - единственное, что вам нужно, чтобы все понять. «Зеленый» хэш H_K — это /требование/, данное получателю платежа (у которого также есть корень Merkle). VERIFIER (полный узел) отправляет «синие» хэши как /proof/, потому что их можно использовать для вычисления всех хэшей с «синими штрихами» вплоть до корня Merkle. Если вычисленный корень Меркла совпадает с известным корнем Меркла, H_K находится в блоке. Очевидно, что «синие» хэши представляют собой небольшое подмножество ВСЕХ хэшей, т. е. 2*log_2(N) меньше, чем весь набор N для N > 4. Нарисуйте его сами на desmos.com, с y=2log(N)/log(2)vs y=N.

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

Это может быть хорошим введением. Ripple может использовать дерево Меркла, но я не уверен: http://en.m.wikipedia.org/wiki/Hash_tree Также проверьте это: https://stackoverflow.com/questions/5486304/explain-merkle-trees-for -использование-в-событии-согласованность

Merkle Root, как я понимаю, это в основном хэш множества хэшей (Хороший пример здесь ) — для создания Merkle Root вы должны начать с двойного хэша SHA-256 байтовых потоков транзакций в блоке. Однако что это за данные (потоки байтов), как они выглядят и откуда берутся, для меня остается загадкой.

БУДЬТЕ ОСТОРОЖНЫ! Корень меркла важен для майнинга. поскольку корень меркла представляет собой хешированное значение ВСЕХ хэшей транзакций из блока, значение корня меркла учитывается заранее, когда майнеры выполняют свою работу. См.: https://en.bitcoin.it/wiki/Block_hashing_algorithm . Предыдущий хэш:

81cd02ab7e569e8bcd9317e2fe99f2de44d49ab2b8851ba4a308000000000000

Вот выдержка из алгоритма там:

>>> import hashlib
>>> header_hex = ("01000000" +
 "81cd02ab7e569e8bcd9317e2fe99f2de44d49ab2b8851ba4a308000000000000" +
 "e320b6c2fffc8d750423db8b1eb942ae710e951ed797f7affc8892b0f1fc122b" +
 "c7f5d74d" +
 "f2b9441a" +
 "42a14695")
>>> header_bin = header_hex.decode('hex')
>>> hash = hashlib.sha256(hashlib.sha256(header_bin).digest()).digest()
>>> hash.encode('hex_codec')
'1dbd981fe6985776b644b173a4d0385ddc1aa2a829688d1e0000000000000000'
>>> hash[::-1].encode('hex_codec')
'00000000000000001e8d6829a8a21adc5d38d0a473b144b6765798e61f98bd1d'

Прежде всего, все значения здесь представлены в записи с прямым порядком байтов, поэтому вам нужно подготовить байт за байтом справа налево (помните, что один байт — это ДВА символа). Таким образом, первое значение — это хэш предыдущего блока, затем КОРЕНЬ МЕРКЛА, затем время создания и затем биты. Чтобы сравнить значения, просто взгляните на: https://blockexplorer.com/block/00000000000000001e8d6829a8a21adc5d38d0a473b144b6765798e61f98bd1d .

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

Значение в вики правильное, так как любой может проверить, посмотрев на хэш заголовка предыдущего блока или запустив ваш код, который не даст заявленных вами значений.
Ах да, я неправильно прочитал байты.
Что такое корень Меркла?
СпросиСетьПолитика конфиденциальности1y, 0v