bitcoin и merkel tree

[lapitsky]

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

[A-Bolt]

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

[pifdec]

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

[kzv]

Блок состоит из
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)

[amaclin1]

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

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

[lapitsky]

Блок состоит из
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)

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

[Coin-1]

- получается в самом процессе создания блоков во время майнинга, меркель не используется?

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

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

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

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

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

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

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

[lapitsky]

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

[kzv]

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

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