Тимур Машнин - Введение в технологию Блокчейн

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

Используя id из большого распределения, нужно найти x, чтобы хэш id и x попадал в заранее определенное распределение y.

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

И мы будем использовать это позже, когда мы поговорим о майнинге биткойнов.

Это своего рода вычислительная загадка, которую мы будем использовать.

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

Она принимает сообщение, которое вы хешируете, и она разбивает его на блоки размером 512 бит.

Сообщение не обязательно кратно размеру блока, поэтому мы должны добавить в конце дополнение. И это дополнение будет состоять из, в конце дополнения, поля длиной 64 бит, которое является длиной сообщения в битах.

И затем до этого находится один бит, за которым следует некоторое количество нулевых бит.

И вы выбираете число нулевых бит, чтобы выйти точно в конец блока.

После того как вы разбили сообщение на блоки, вы начинаете вычисление.

Вы начинаете с 256-битного начального значения и берете первый блок сообщения.

Затем вы берете эти 768 полных битов, и обрабатываете специальной функцией сжатия, которая на выходе дает 256 бит.

Вы берете полученные 256 бит и следующие 512 бит сообщения, снова пропускаете через функцию сжатия и так далее, пока не обработаете все блоки сообщения.

Таким образом вы получите хэш, как 256-битное значение.

И нетрудно показать, что если эта функция сжатия, C, является свободной от коллизий, то вся эта хэш-функция также будет свободна от коллизий.

Далее мы поговорим о хэш указателях и их применении.

Хэш указатель – это вид структуры данных, которая указывает где хранится некоторая информация.

И в которой вместе с указателем хранится криптографический хэш самой информации.

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

И мы можем использовать хэш указатели для создания всех видов структур данных.

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

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

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

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

Эта структура не только позволяет хранить данные, но и защищать их.

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

Мы это легко обнаружим, сравнив хэш указатель и данные блока.

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

Поэтому злоумышленнику придется изменить хэш-указатели всей цепочки до конца.

Таким образом, один хэш-указатель защищает весь список от этого блока и до конца.

Начальный блок такого списка называется блоком генезиса.

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

Идея в том, что у нас есть куча блоков данных, которые показаны внизу.

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

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

И мы можем быть уверены, что данные не будут подделаны.

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

Таким образом, мы защищаем всю структуру данных, просто запомнив один хэш.

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

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

И это занимает около log n элементов.

Поэтому при очень большом числе блоков данных в дереве Merkle мы можем проверить членство данных за относительно короткое время.

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

И мы можем проверить принадлежность к дереву за логарифмическое время.

Также есть вариант Merkle дерева – это сортированное дерево Merkle.

В этом дереве мы берем блоки данных внизу и сортируем их в некотором порядке.

Алфавитном, лексикографическом, числовом порядок или каком-либо другом порядке.

И как только мы отсортировали дерево Merkle, мы можем доказать, что конкретный блок не находится в дереве Merkle.