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

9 месяцев назад
67 в образование

Давайте разберемся сегодня что такое хеш-указатель (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

Авторы получают вознаграждение, когда пользователи голосуют за их посты.
Голосующие читатели также получают вознаграждение за свой голос.
Порядок сортировки:  Популярное

Это действительно отличный пост.
Теперь никто не может сказать, что он не знает, как блокчейн работает.

·

спасибо, я старалась :)

Я новичок, так что для меня это информация очень полезная и нужная.

·

ура-ура :) продолжение следует!

Весьма интересный и полезный пост. Особенно полезен тем людям, которые только осваивают принцип работы блокчейна

·

спасибо!

Вам надо идти преподавателем в университет, и преподавать студентам действительно полезные вещи=)

·

я чувствую, что пока мое место среди студентов, но получить такой комментарий очень приятно :)

·
·

Всему свое время+