Как реализовать дерево Merkle?

Я медленно реализую некоторые протоколы биткойнов, и я не уверен, как правильно понять Merkle Tree из вики-файла Bitcoin: https://en.bitcoin.it/wiki/Protocol_specification#Merkle_Trees У меня есть строки a, b, c, я два раза их хэш, и я получаю три листовых узла. Но я не уверен, что делать с более высокими узлами. Я дважды делаю хэш суммой результирующих байтов (рассматривая их как большие числа), или я конкатенирую (рассматривая их как строки), или, возможно, мне нужно что-то еще?

21 голос | спросил ThePiachu 16 thEurope/Moscowp30Europe/Moscow09bEurope/MoscowFri, 16 Sep 2011 22:52:27 +0400 2011, 22:52:27

2 ответа


23

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

Предположим, что у вас есть tx хэши Ha1, Ha2, Ha3, Ha4, Ha5, Ha6, Ha7

  • Первая итерация: Hb1 = Hash (Ha1 | Ha2), Hb2 = Hash (Ha3 | Ha4), Hb3 = Hash (Ha5 | Ha6), Hb4 = Hash (Ha7 | Ha7)
  • Вторая итерация: Hc1 = Hash (Hb1 | Hb2), Hc2 = Hash (Hb3 | Hb4)
  • Третья итерация: Hd1 = Hash (Hc1 | Hc2) => Корневой ключ
ответил Pieter Wuille 17 thEurope/Moscowp30Europe/Moscow09bEurope/MoscowSat, 17 Sep 2011 15:11:06 +0400 2011, 15:11:06
5

У вас есть хеши. См. Нижнюю часть https://en.bitcoin.it/wiki/Dump_format#CBlock для изображения.

ответил theymos 17 thEurope/Moscowp30Europe/Moscow09bEurope/MoscowSat, 17 Sep 2011 05:44:47 +0400 2011, 05:44: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