Каков канонический способ создания ветвей дерева merkle?

В настоящее время я изучаю создание нескольких ветвей дерева Merkle, чтобы доказать, что данный хэш был включен в данный корень merkle. Моя первоначальная мысль состояла в том, чтобы перечислить лист, корень merkle и все хеши, с которыми был связан данный лист, чтобы сделать корень merkle.

Итак, в этом примере:

 введите описание изображения здесь>> </a> </p>

<p> Я бы сказал </p>

<pre><code>---- +: = 0 = + ----</code></pre>

<p> Однако, поскольку порядок узлов имеет значение для создания корня merkle, мне также нужно будет указать, был ли узел слева или справа. </p>

<p> Мне интересно - существует ли канонический способ перечисления этой информации для создания ветвей merkle? </p></body></html>

6 голосов | спросил ThePiachu 11 Jpm1000000pmMon, 11 Jan 2016 23:10:26 +030016 2016, 23:10:26

1 ответ


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 для информации.

ответил Murch 15 Jpm1000000pmFri, 15 Jan 2016 14:59:33 +030016 2016, 14:59:33

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

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

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