Введение в технологию Блокчейн - стр. 4
Поэтому злоумышленнику придется изменить хэш-указатели всей цепочки до конца.
Таким образом, один хэш-указатель защищает весь список от этого блока и до конца.
Начальный блок такого списка называется блоком генезиса.
Теперь, еще одна полезная структура данных, которую мы можем построить с помощью хеш-указателей, является двоичным деревом.
Идея в том, что у нас есть куча блоков данных, которые показаны внизу.
И используя пары блоков, мы строим структуры данных с двумя хеш-указателями, по одному на каждый из этих блоков.
Затем мы переходим на другой уровень, и здесь этот блок будет содержать хэш-указатель этих двух детей. И так далее, вплоть до корня дерева, единственный хэш которого мы и запоминаем.
И мы можем быть уверены, что данные не будут подделаны.
Потому что злоумышленнику придется изменять хэши на всех уровнях, пока он не доберется до вершины дерева, но здесь он не сможет изменить хэш, так как мы его запомнили.
Таким образом, мы защищаем всю структуру данных, просто запомнив один хэш.
Теперь еще одна приятная особенность деревьев Merkle заключается в том, что в отличие от ранее рассмотренной цепочки блоков, если кто-то хочет доказать нам, что конкретный блок данных является членом этого дерева Merkle, все, что им нужно, это показать эти данные.
Мы вычисляем хэш этих данных и поднимается вверх до корня дерева, так как мы помним только корень дерева, проверяя соответствие хэш-указателям.
И это занимает около log n элементов.
Поэтому при очень большом числе блоков данных в дереве Merkle мы можем проверить членство данных за относительно короткое время.
Таким образом, деревья Меркле имеют преимущества в том, что даже если дерево содержит много элементов, нам просто нужно запомнить хеш корня дерева, который составляет всего 256 бит.
И мы можем проверить принадлежность к дереву за логарифмическое время.
Также есть вариант Merkle дерева – это сортированное дерево Merkle.
В этом дереве мы берем блоки данных внизу и сортируем их в некотором порядке.
Алфавитном, лексикографическом, числовом порядок или каком-либо другом порядке.
И как только мы отсортировали дерево Merkle, мы можем доказать, что конкретный блок не находится в дереве Merkle.
Мы можем сделать это, просто указав путь к элементу, который находится непосредственно перед местом, где этот элемент должен быть, и сразу после того, где он будет.
И тогда мы можем доказать, что оба эти элемента находятся в дереве Merkle последовательно.
И поэтому между ними нет места для элемента, который мы ищем.
Цифровые подписи
Далее мы поговорим о цифровых подписях.