Начало работы с деревом Меркла

Базовые знания криптографии

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

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

Алгоритм хеширования, используемый в битах, — это SHA (Secure Hash Algorithm), а его длина дайджеста составляет 256 бит, то есть 32 байта, поэтому он называется SHA256, и двойной sha256 выполняется в заголовке блока.

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

состав блоков

Блок состоит из заголовка блока и тела блока. Тело блока представляет собой совокупность всех транзакций, а заголовок блока состоит из пяти частей.В этой статье мы сосредоточимся на корне merkle. Остальные элементы будут описаны в отдельной статье, связанной с майнингом, позже.

Предыдущая зона хэша, предыдущий хеш. Двойной SHA256 выполняется заголовком блока верхнего блока. 32 байта.
Отметка времени, отметка времени. 4 байта.
Целевое значение сложности майнинга. 4 байта.
Доказательство работы одноразового номера, одноразового номера. Майнер достигает определенной цели через одноразовый номер, и сложность достижения этой цели со временем будет увеличиваться.
merkle root, merkle root можно просто понимать как уникальный хэш-идентификатор набора транзакций. 32 байта.
версия. 4 байта.

Заголовок блока состоит из следующего:

02000000 ........................... Block version: 2

b6ff0b1b1680a2862a30ca44d346d9e8
910d334beb48ca0c0000000000000000 ... Hash of previous block's header
9d10aa52ee949386ca9385695f04ede2
70dda20810decd12bc9b048aaab31471 ... Merkle root

24d95a54 ........................... Unix time: 1415239972
30c31b18 ........................... Target: 0x1bc330 * 256**(0x18-3)
fe9f0864 ........................... Nonce

Механизм биткойн SPV (упрощенная проверка платежей) гарантирует, что каждый раз необходимо загружать только заголовок блока (80 байтов), а не весь блок целиком. В среднем каждая транзакция занимает не менее 250 байт, а каждый блок содержит в среднем 2000 транзакций. Таким образом, блок, содержащий завершенную транзакцию, в 4 000 раз больше, чем заголовок блока.

Список хешей в загрузках BitTorrent

отдельный файл

Когда мы переходим к загрузке файла, за ссылкой для скачивания предоставляется MD5 (MD5 также является хеш-алгоритмом), чтобы мы могли вычислить MD5 файла после загрузки.Если MD5 равен предоставленному MD5, это означает что файл не поврежден или не взломан злонамеренно.

несколько файлов

Например, в p2p, когда мы загружаем торрент BT, если файл относительно большой, например, при загрузке фильма, состоящего из одного шага, большой файл фильма будет разделен на несколько небольших блоков данных (блоки данных). Эти небольшие блоки данных будут загружены с нескольких разных машин.Как убедиться, что блоки данных, загруженные с других машин, не были изменены?

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

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

Дерево Меркла в биткойнах

Как показано на рисунке выше, Lx может быть транзакцией в блокчейне.

Есть пять шагов, чтобы подтвердить, является ли транзакция законной в биткойнах:

Получите и сохраните все заголовки блоков для самой длинной цепочки из сети.
Убедитесь, что блок, в котором находится эта транзакция, находится в самой длинной цепочке выше в соответствии с заголовком блока. Заголовок блока получается в блоке Merkle.
Для получения нужного хэша аутентификации Merkle из пути Block Merkle.
Корень Меркла рассчитывается на основе этих хеш-значений. Если рассчитанное значение Merkle Root равно Merkle Root в заголовке блока.

p.s: узел SPV хочет знать о предстоящем платеже на биткойн-адрес в своем кошельке. Узел установит фильтр Блума на канале связи между узлами, ограничивая его приемом только транзакций, содержащих целевой биткойн-адрес. Когда одноранговый узел обнаруживает, что транзакция соответствует фильтру Блума, он отправляет блок в виде сообщения Merkleblock.Сообщения Merkleblock содержат заголовки блоков и путь Merkle, соединяющий целевую транзакцию с корнем Merkle.

Давайте сосредоточимся на шаге три выше.

Как показано на рисунке выше, мы проверяем, является ли транзакция K легальной или нет, то есть входит ли она в блок. Путь Меркла, возвращаемый в Merkleblock, будет содержать H(L), H(IJ), H(MNOP), H(ABCDEFGH). В соответствии с этими пятью хеш-значениями можно определить корень Меркла. По сравнению с использованием хэш-списка существует нет необходимости хэшировать все маленькие хэши один раз, то есть вам нужно получить только четыре пути ниже пути Меркла плюс хэш самой транзакции. Вам не нужно получать все действия транзакции. В сценариях практического применения, когда количество транзакций в блоке очень велико, скорость проверки очень высока и растет логарифмически.

Merkleblock

Когда я прочитал эту часть впервые, было два запутанных вопроса. Я перечисляю их здесь. Если эти два вопроса можно ответить, основные принципы проверки SPV Vectory of Bitcoin's Tree Merkle будут похожими.

spv знает адрес транзакции, но как он узнает, в каком блоке находится транзакция?
Зная заголовок блока, соответствующий транзакции, как получить путь Меркла, то есть H(L), H(IJ), H(MNOP), H(ABCDEFGH)?

Сам SPV не имеет информации о блоке, она получена со всех узлов. В запросе getdata, если тип инвентаря указан как MSG_MERKLEBLOCK, полный узел ответитMerkleBlock.

Процесс разбора SPV MerkleBlock выглядит следующим образом:

Дерево Меркла в Ethereum

Эфириум использует Merkle Patricia Tree, которое сильно отличается и сложнее, чем Биткойн, о чем будет подробно рассказано в следующей статье. Как правило, транзакции в биткойнах не имеют состояния. Например, мы не можем напрямую проверить баланс счета. Баланс, который мы обычно видим, генерируется и рассчитывается самим клиентом кошелька, связанного с биткойнами. Транзакции хранятся в блокчейне не только в одном дереве Меркла, а в трех деревьях Меркла:

Дерево транзакций.
Приемное дерево. Панель данных, показывающая влияние каждой транзакции.
Государственное дерево.