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

Биткойн wiki Словарь статьи объясняет, почему существует корень Merkle:

  

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

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

45 голосов | спросил Steven Roose 2 Mayam13 2013, 02:49:32

6 ответов


50

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

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

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

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

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

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

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

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

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

ответил David Ogren 2 Mayam13 2013, 06:13:46
21

"Рисунок 7-2. Вычисление узлов в дереве merkle" из Освоение биткойна показывает Merkle Root (H ABCD ) списка из четырех транзакций: Tx A, Tx B, Tx C и Tx D:  Рисунок 7-2. Вычисление узлов в дереве merkle


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

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

Если H K приводит к правильному корню Merkle, то T K был в списке транзакций.

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

ответил Geremia 4 J000000Saturday15 2015, 06:36:45
3

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

ответил Eyal 2 Mayam13 2013, 11:30:54
1

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

ответил Bitripple 2 Mayam13 2013, 05:21:43
1

ЗНАЙТЕ! Корень merkle важен для разработки. поскольку корень merkle является хэшированным значением всех хэшей транзакций из блока, значение корня merkle берется заранее, когда шахтеры выполняют свою работу. См .: https://en.bitcoin.it/wiki/Block_hashing_algorithm . В вики есть ошибка для предыдущего хэша:

81cd02ab7e569e8bcd9317e2fe99f2de44d49ab2b8851ba4a**308**000000000000

неверно, это должно быть:

81cd02ab7e569e8bcd9317e2fe99f2de44d49ab2b8851ba4a**3a8**000000000000

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

>>> import hashlib
>>> header_hex = ("01000000" +
 "81cd02ab7e569e8bcd9317e2fe99f2de44d49ab2b8851ba4a3a8000000000000" +
 "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'

Прежде всего, все значения здесь в маленькой концевой нотации, поэтому вы должны иметь готовый байт на каждый байт справа налево (помните, что один байт - ДВА символов). Таким образом, первое значение - это превалирующий блочный хэш, затем THE MERKLE ROOT, затем время создания, а затем бит. Чтобы сравнить значения, просто взгляните на: https://blockexplorer.com/block/00000000000000001e8d6829a8a21adc5d38d0a473b144b6765798e61f98bd1d

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

ответил Erhard Dinhobl 30 J0000006Europe/Moscow 2017, 16:10:49
-1

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

ответил HenryDorsettCase 11 WedEurope/Moscow2013-12-11T01:37:47+04:00Europe/Moscow12bEurope/MoscowWed, 11 Dec 2013 01:37:47 +0400 2013, 01:37:47

Похожие вопросы

Популярные теги

security × 330linux × 316macos × 2827 × 268performance × 244command-line × 241sql-server × 235joomla-3.x × 222java × 189c++ × 186windows × 180cisco × 168bash × 158c# × 142gmail × 139arduino-uno × 139javascript × 134ssh × 133seo × 132mysql × 132