ДНЕВНИК СТУДЕНТКИ: Структуры данных Блокчейн и Дерево Меркля

Давайте разберемся сегодня что такое хеш-указатель (hash pointer) и как с его помощью формируются структуры данных: "Блокчейн" и "Дерево Меркля".

Что такое хэш-указатель?

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

хранить криптографическую(зашифрованную) информацию в виде хэша H()
знать место, где именно эта информация хранится, благодаря указателю ->
запросить эту информацию обратно, когда нам надо
проверить, не изменилась ли эта информация

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

На схеме видно следующее:

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

Круто получается - мы можем хранить связанную зашифрованную и защищенную информацию.

В чем фишка?

Если вы еще не уловили, то структура блокчейн такая хитрая из-за этих хэш-указателей, что данные в ней невозможно незаметно подделать/изменить. Почему?

Давайте попробуем, как в лекции, провести эксперимент:

Допустим, какой-то злоумышленник решил заменить информацию в блоке 1 (дописать пару ноликов в транзакции, например)
Любое изменение в блоке 1 приводит к тому, что хэш-указатель в блоке 2 больше не соответствует текущему набору данных в блоке 1, помните про устойчивость хэш-функции к коллизиям? Н(х) != Н(у)
Далее, чтобы махинация не была вот так сразу обнаружена, злоумышленник решает, по логике вещей, заменить хэш-указатель в блоке 2, чтобы данные в блоке 1 соответствовали хэш-указателю на них из блока 2
Любое изменение в блоке 2 приводит к тому, что хэш-указатель в на него из блока 3 больше не соответствует текущему набору данных в блоке 2 и мы видим это
Соответственно, единственным выходом у злоумышленника, является замена информации и хэш-указателей по всей цепи, что невозможно, ведь у нас хранится как минимум один хэш-указатель
Вот так, храня у себя как минимум один хэш-указатель, мы можем обнаружить подмену в блокчейн-структуре и восстановить все исходные данные

Довольно таки просто, получается.

Дерево Меркля

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

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

С помощью этой хитрой структуры мы можем зашифровать большой массив данных в один 256-битный хэш-указатель. Как?

Все данные мы делим на блоки
Все блоки определяем в пары
Каждой паре блоков мы создаем общий "родительский" блок, в котором хранятся два хэш-указателя на нашу пару "детей" (нижняя часть схемы)
Каждый "родительский" блок соединяется с другим "родительским" блоком в общий блок с двумя хэш-указателями на нашу пару "родителей"
Так происходит объединение по два до тех пор пока мы не сформируем один хэш-указатель, "корень" нашего дерева

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

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

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

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

Если вам нравится мой стиль подачи информации и вы считаете ее полезной для себя, рекомендую к прочтению мои предыдущие публикации в цикле Bitcoin and Cryptocurrency:

Исходную и профессионально изложенную информацию вы можете получить, подписавшись на курс Bitcoin and Cryptocurrency Technologies.

Подписывайтесь на мой дневник! :)

@studentka