Структуры на основе хеш-функций
Сегодня мы поговорим о структурах на основе криптографических хеш-функций, а именно о хеш-указателях, о связанном списке, который, в общем-то, является блокчейном, и о дереве Меркла.
Что такое хеш-указатель?
Хеш-указатель имеет два свойства.
- указывает на какое-то место памяти, где хранится информация
- Он несет в себе хеш информации.
Таким образом, если у нас есть хеш-указатель, мы всегда можем, во-первых, получить информацию, во-вторых, подтвердить целостность информации, что какая-то информация у нас не изменялась. Потому что если мы в информации меняем хотя бы один бит, у нас уже хеш станет совершенно другим, и сравнив хеш, который есть в указателе с хешем того, что мы получили, мы всегда можем сделать вывод о том, были изменены данные или не были.
Вторая структура – это связанный список или блокчейн, – это когда мы в каждом следующем кусочке информации даем хеш-указатель на предыдущий кусочек. Именно так и работает блокчейн, есть какой-то самый первый блок, который называется generous block, после него идет ряд других блоков. И каждый блок помимо информации, допустим о транзакции, содержит в заголовке хеш предыдущего блока.
Что это нам дает?
Если мы, допустим, в каком-то старом блоке поменяли хотя бы один бит информации, у нас не сойдется хеш-указатель следующего блока после него. Но что это нам, в свою очередь, еще даст? Так как хеш-указатель следующего после этого блока считается от информации в этом блоке и от хеш указателя на предыдущий блок, у нас не сойдется этот хеш. Таким образом, у нас не создается вся цепочка, и зная только, допустим, самый последний хеш последнего блока, мы можем подтвердить целостность всей цепочки.
Следующей структурой является дерево Меркла.
В блокчейнах, в частности в блокчейне биткоина, оно используется для распределения транзакций по блокам. То есть это содержимое блоков является транзакция. Транзакции попарно выстраиваются, сортируются. От каждых двух транзакций считаются хеш-указатели. Если у нас получилось больше чем две таких структуры, мы от них еще идем вверх, то есть, получается такое двоичное дерево, корнем которого является Меркл рут, корневой хеш, и таким образом получается такая структура.
Зачем она нужна? Опять же, если мы подделываем информацию в какой-то одной транзакции в блоке, что происходит? У нас не сходится один из хешей, непосредственно который идет после этой транзакции. Но тогда не сходится и хеш, который чуть выше, потому что он считается от этого хеша, не сходится и корневой хеш. В результате, зная только корневой хеш, мы можем всегда подтвердить целостность информации всего блока, каждой отдельной транзакции.
Зачем же нужна такая структура в принципе, почему нельзя блокчейн было бы делать каждой транзакцией в отдельном блоке? Так получется намного удобнее. Достоинством дерева Меркла является то, что можно проверить, есть ли в нем какой-то элемент с помощью сложности алгоритма логорифм N, а не M, то есть там не нужно проверять все транзакции, нам нужно проверить только эту ветку, которой транзакция принадлежит. То есть, мы предоставляем саму транзакцию, хеши, которые попали в эту ветку Меркл рут и, соответственно, имея все это, мы можем подтвердить то, что такая транзакции есть. Второе достоинство – это доказательство того, что какой-то транзакции нету в блоке, потому что даже если у нас есть две соседние транзакции, если они у нас отсортированы, нам достаточно эти две транзакции проверить, что между ними ничего нет. На этом все о дереве Меркла.
Кстати, вы можете обсудить новость в нашем Telegram чате.
______________________________________________
Подписывайся, чтобы не упустить ничего важного.
Telegram канал | YouTube канал | Facebook страница | Twitter | VK
