Merkle root

Статьи про концепцию майнинга (PoW варианта) написал уже практически каждый первый «эксперт». Я не считаю себя экспертом, мне просто нравится разбираться в технологиях и создавать свои, но про майнинг я писать пока не хочу, потому что вы все и так знаете что там с чем едят. Подробнее я хотел остановиться на алгоритме merkle root и на том, почему и как он связан с майнингом и SPV.

Основа

Merkle root переводится как «корень дерева Меркла» и действительно, общая концепция основана на графах очень похожа на деревья. Допустим у нас есть 4 элемента:

A, b, c, d

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

hash(a,b) = ab

Таким образом, получаем следующие хеши пар:

A,b = ab

C,d = cd

Далее сцепляем следующий уровень пар, в нашем случае:

Ab, cb

до тех пор, пока не останется один элемент (в нашем случае третий уровень – окончательный, и корнем является abcd), он и будет являться корнем дерева. И действительно, если нарисовать эту схему снизу вверх, получится следующая картина:

 Abcd

   /  \

Ab   cd

/\     /\

A  b c  d

А вот то, для чего нам нужен abcd я объясню ниже.

Майнинг и корни дерева

В концепции майнинга есть понятия заголовка блока. Это 80 байт информации, из которых, путем перебора вариантов (для PoW майнинга) ищется хеш, меньший, чем значение target (т.е. сложности сети).

Заголовок состоит их следующих данных:

• Версия сети
• хеш предыдущего блока
• описываемый в этой статье merkle_root
• время блока, в формате unixtimestamp
• bits (т.е. target сложность сети, ниже которого должно быть значение этого хеша заголовка блока, в экспоненциальном формате записи)
• число, которое перебирается в процессе майнинга

Этот список образует 80 байт, из которых и считается хеш. Т.е. майнеры триллионы раз в секунду производят операцию хеширования над этими данными. Как видите - тут нет списка транзакций, ведь если бы майнеры хешировали еще и весь список транзакций, количество которых может доходить до 3 тысяч в одном блоке – время хеширования бы сильно увеличилось.

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

Именно эти проблемы и решает merkle_root. Он позволяет описывать список транзакций одним хешем с помощью простого алгоритма получения корня (abcd в нашем примере и есть корень дерева, получить который, можно зная все элементы. Если изменить хотя бы один элемент – корень получится другим). При этом позволяя майнерам сконцентрироваться на их любимом nonce, а для проверки списка транзакций на подмену – достаточно собрать новое дерево из полученного списка транзакций и сверить его корень с тем, что прислали в блоке.

Корни и spv

Но, как оказалось позже (хотя я подозреваю, что Сатоши предполагал использование концепции, описанной в BIP 37). – merkle root решает еще одну проблему – а именно, позволяет легким spv нодам не скачивать весь блокчейн, и не организовывать тотальную проверку всех записей из реестра.

А так, как spv кошельки, при обновлении базы получают не сообщение block, содержащий полный избыточный блок с кучей ненужной этой ноде информации, а merkleblock, содержащий необходимые транзакции и так называемые merkle branch, т.е. ветви дерева меркла.

Вернемся к нашему примеру:

 Abcd

  /  \

?   cd

/\     /\

? ?  c  d

Представим, что нам пришла транзакция c, и нам необходимо узнать, имеется ли она в дереве транзакций. Так как spv ноды всё-таки скачивают заголовки всех блоков, то они знают merkle_root блока, в котором находилась транзакция с. Для того, чтобы проверить вхождение транзакции c в дерево abcd, нам необходимо знать ветви – d, cd. Именно эти ветви и называются merkle branch и передаются вместе с транзакцией c в сообщении merkleblock. Зная корень дерева, и узлы d,сd – можно легко и просто установить – была ли транзакция в блоке на момент майнинга.

Конечно, этот пример утрирован, так как в криптовалютах применяется другая функция хеширования, к примеру в биткоине она представляет из себя двойной sha-256 хеш от байтовой последовательности суммы байт первого и второго хеша, но это уже детали.

Жизнь-боль

Кстати забавный факт, когда я первый раз запустил тестовую сеть своей ново-написанной криптовалюты – я забыл протестировать функцию, получающую этот самый корень. Вернее, я забыл протестировать её на более-чем одном элементе (так как корень дерева из одного элемента является этим одним элементом), поэтому для одного элемента (а пустой блок содержит только coinbase транзакцию, как мы знаем) эта функция отдавала верное значение, но стоило мне начать отправлять в сеть новые транзакции – они не смогли быть проверены в новом блоке и сеть не смогла расти, а я к тому моменту намайнил уже более 500 блоков, что заняло у меня порядка недели времени. Пришлось начинать всё с genesis блока опять.

Заключение

Итак, merkle_root является одним из важнейших элементов цепных криптовалют и решает массу проблем и неудобств. Теперь я понял, что нужно было в универе побольше времени уделять графам. На самом деле, концепция децентрализованных хранилищ ценности, коими являются криптовалюты - представляет из себя просто сундук с разными, полезными технологиями, применимыми не только в этой отрасли, но и во многих других. Хоть у меня и не особо много криптовалюты - мне очень нравится заниматься разработкой и исследованиями в этой отрасли, потому что это позволяет постоянно развиваться и увеличивать количество известных мне технологий и алгоритмов. Думаю, что зацикливаться на денежной составляющей не всегда является правильным вариантом, а особенно в такие просадки рынка, а вот технологии от нас уже никуда не денутся.