Topic: bitcoin и merkel tree (Read 292 times)

Во время синхронизации на ноде создается отдельная база данных неизрасходованных выходов UTXO. Когда приходит новая транзакция, нода сверяется со своей базой UTXO.

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

Используется.

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

В итоге получаются ветки дерева Меркля, которые опять хешируются между собой. Допустим, если в блоке 4 транзакции, то получатся 2 ветки и 1 корень дерева Меркля.

Корень дерева Меркля (32 байта) майнер записывает в заголовок блока и только после этого начинает перебирать число nonce для поиска подходящего блока.

Вот объяснение дерева Меркля на английском языке:
https://en.bitcoin.it/wiki/Protocol_documentation#Merkle_Trees



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

Отличное объяснение!
Я бы только добавил бы вот такой момент. Мы не просто так клиентом проверяем наличие
транзакции D в блоке. У клиента есть конкретный кейс - клиент проверяет только те транзакции,
которые имеют отношение к поступлениям на адреса юзера! То есть, сеть доказывает
мне, что "транзакция D, которая прислала тебе бетховены, действительно включена в
такой-то блок, мы тебя не обманываем"

Блок состоит из
1. заголовка
2. транзакций
3. сегвит данных

Хэш Меркла находится в заголовке блока.

Допустим к вам пришла транзакция, как узнать: есть ли эта транзакция в блоке? Варианта два
1. если у вас есть все блоки целиком, то надо просто посмотреть транзакцию в нужном блоке.
2. если у вас легкий клиент и/или блоки хранятся не целиком, то вы можете проверить наличие транзакции в блоке с помощью хэша Меркла.

Алгоритм проверки я точно не знаю, но примерно он должен выглядеть так:
1. Берем из транзакции номер блока
2. Достаем из своей базы заголовок блока с нужным номером
3. Достаем из заголовка хэш Меркла - корень дерева (К)
4. Посылаем в сеть сообщение: "пришлите мне ветки и листья дерева Меркла для транзакции"
5. Когда ветки и листья присылают, можно их прохэшировать. Если хэш даст корень К, значит все хорошо.

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


На примере будет понятней.

Пусть в блоке шесть транзакций A, B, C, D, E, F
Тогда хэш Меркла формируется следующим образом
Ветка01 = хэш(A+B)
Ветка02 = хэш(C+D)
Ветка03 = хэш(E+F)

Ветка11 = хэш(Ветка01 + Ветка02)
Ветка12 = хэш(Ветка03 + Ветка03)

Корень = хэш(Ветка11 + Ветка12)

Теперь допустим надо проверить: существует ли транзакция D в блоке? У нас есть только Корень, что мы делаем?

Мы ищем в сети соседей у которых есть блоки целиком и просим: "подайте пожалуйста бедному SPV клиенту несколько веточек Меркла для транзакции D"
Добрые соседи хоть и добрые, но все таки скупые и все ветки вам не дадут ибо для проверки достаточно знать: С, Ветка01, Ветка12.

То есть в примере вместо 5 хэшей (A,B,C,E,F) вы получаете только три (С, Ветка01, Ветка12), но при этом все равно можете точно проверить наличие транзакции в блоке.

Корень = хэш(хэш(Ветка01 + хэш(C+D)) + Ветка12)

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

Я вам уже давал ссылку на книгу про Биткойн. Там есть глава "Деревья Меркле", а в её конце написано для чего понадобилось хешировать транзакции по такому алгоритму.

Подскажите, зачем надо делать для каждого блока merkel tree, вместо обычного хеша?