Каков канонический способ создания ветвей дерева merkle?
В настоящее время я изучаю создание нескольких ветвей дерева Merkle, чтобы доказать, что данный хэш был включен в данный корень merkle. Моя первоначальная мысль состояла в том, чтобы перечислить лист, корень merkle и все хеши, с которыми был связан данный лист, чтобы сделать корень merkle.
Итак, в этом примере:
1 ответ
Изменить: посмотрите MSG_MERKLEBLOCK . Включенная информация: Block Header, Transaction Count, Hash Count, hashes, flag byte count и flags.
hashes включить все от листа к корню, а flags
дает положение листа в дереве Меркле.
Так как индекс транзакции дает его положение слева от листьев в дереве Merkle, в дополнение к счету транзакции достаточно вывести, является ли он левым или правым партнером в каждой конкатенации.
(Старый ответ ниже.)
Листья дерева Merkle слева направо в том же порядке, что и список транзакций блока. Каждый вышеописанный слой формируется путем объединения дочерних элементов, а затем выполнения объявления double SHA-256. Когда в слое остается только одна запись, мы называем это корнем Merkle.
Если транзакция не имеет партнера, она вместо этого соединяется с самим собой.
HASH(Hash(AB)Hash(CC))
/ \
Hash(AB) HASH(CC)
/ \ / \
A B C -
Legend: A,B,C are txid; Hash is short for SHA-256d.
Это означает, что позиция каждой транзакции в дереве полностью определяется только его индексом в списке транзакций. Таким образом, позиция своих партнеров на каждом уровне вычитается из этого только: если вы пишете индексы транзакций (начиная с 0) в двоичном формате, вы получаете следующее:
A: 00
B: 01
C: 10
Чтение с обратной стороны, каждый 1 означает «правильное положение» и каждый 0 означает «левое положение».
Пример: B(01), B Последняя позиция 1, а B - правильный партнер A. B 'вторая в последней позиции 0 и HASH (AB) является левым партнером HASH (CC).
Поэтому достаточно добавить индекс в список транзакций и количество транзакций в блоке к предлагаемому «Листу, корню, узлам».
К сожалению, я не знаю, какой стандарт используется для передачи этой информации. Возможно, вы можете найти его в коде Bitcoin Core, обслуживая запросы клиентов опроса SPV для информации.