Текст книги "Основы блокчейна: вводный курс для начинающих в 25 небольших главах"

Глава 10
Хэширование данных
Идентификация данных по их цифровым отпечаткам пальцев

В этой главе рассматривается одна из наиболее важных технологий, лежащих в основе блокчейна: хэш-значения (hash values). Здесь обсуждаются важные свойства криптографических хэш-функций и демонстрируются типовые примеры применения хэш-функций к данным.

Метафора

Отпечатки пальцев – это следы контакта с какой-либо поверхностью складок кожи всех или некоторых пальцев человеческой руки. Считается, что с помощью отпечатков пальцев можно однозначно идентифицировать человека. Исследование отпечатков пальцев применяется при расследовании преступлений, для установления личности правонарушителей и для оправдания невиновных. В этой главе вводится концепция идентификации данных, которую можно рассматривать как цифровой аналог отпечатков пальцев. Эта концепция называется криптографическим хэш-значением (cryptographic hash value), и технология блокчейна активно ее использует. Таким образом, понимание криптографического хэширования является обязательным условием для понимания технологии блокчейна.

Цель

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

Как это работает

Хэш-функции – это небольшие компьютерные программы, которые выполняют преобразование любого типа данных в число определенной длины вне зависимости от размера исходных данных [38]. Хэш-функции получают доступ только к одному фрагменту данных в любой рассматриваемый момент времени, используют этот фрагмент как входные данные и создают хэш-значение (hash value) на основе значений битов и байтов, составляющих исходные данные. Хэш-значения могут содержать начальные незначащие нули для обеспечения требуемой длины числа. Существует много версий хэш-функций, отличающихся друг от друга длиной генерируемых ими хэш-значений. Важная группа хэш-функций носит название криптографические хэш-функции (cryptographic hash functions). Эти функции создают цифровые отпечатки пальцев для любых типов данных. Криптографические хэш-функции обладают следующими свойствами [31]:

• быстрая генерация хэш-значений для любого типа данных;

• детерминированность;

• обеспечение псевдослучайности хэш-значений;

• односторонние функции;

• устойчивость к коллизиям.

Быстрая генерация хэш-значений для любого типа данных

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

Детерминированность

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

Обеспечение псевдослучайности хэш-значений

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

Односторонние функции

Односторонняя функция (one-way function) не позволяет никаким способом получить входные данные из возвращаемого значения. То есть одностороннюю функцию невозможно использовать в обратном порядке. Другими словами, невозможно восстановить исходные данные по полученному хэш-значению. Это означает, что хэш-значения ничего не сообщают о содержимом входных данных – точно так же, как отдельный отпечаток пальца ничего не говорит о человеке, оставившем его. Односторонние функции также называют необратимыми (noninvertible).

Устойчивость к коллизиям

Хэш-функцию называют устойчивой к коллизиям (collision resistant), если очень трудно найти два или более различных фрагмента данных, для которых она выдает одинаковые хэш-значения. Другими словами, если вероятность получения одинаковых хэш-значений для различных фрагментов данных мала, то такая хэш-функция является устойчивой к коллизиям. В этом случае можно считать, что хэш-значения, генерируемые этой хэш-функцией, уникальны и могут использоваться для однозначной идентификации данных. Если получены одинаковые хэш-значения для различных фрагментов данных, то налицо коллизия хэш-функции. Коллизия хэш-функций (hash collision) представляет собой цифровой эквивалент наличия двух людей с одинаковыми отпечатками пальцев. Устойчивость к коллизиям является обязательным условием для хэш-значений, применяемых в качестве цифровых отпечатков пальцев. Внутренняя реализация устойчивости к коллизиям в хэш-функциях не рассматривается в данной книге, но вы можете быть уверенными в том, что разработчики затратили немало усилий для снижения вероятности возникновения хэш-коллизий.

Проверка на практике

Этот раздел поможет вам приобрести уверенность при использовании хэш-функций. Для этого приводится простой пример. Я предлагаю читателям посетить веб-сайт, предоставляющий инструментальное средство создания хэш-значений для простых текстовых данных: http://www.blockchain-basics.com/HashFunctions.html.

После перехода на эту веб-страницу в браузере вы увидите панель ввода и панель вывода, как показано на рис. 10.1. Введите текст «Hello World!» в панели ввода слева и щелкните по кнопке с надписью «Calculate Hash Value» (Вычислить хэш-значение), расположенной ниже текстового поля ввода. Будьте внимательны и точно наберите текст в поле ввода, иначе выведенные результаты будут отличаться от показанных на рис. 10.1.

Рис. 10.1 Вычисление хэш-значений короткого фрагмента текста

После щелчка по кнопке в панели вывода справа появятся хэш-значения для введенного текста, вычисленные с помощью четырех различных хэш-функций. Хэш-значения часто рассматриваются как хэш-числа, поскольку в них используются не только цифры от 0 до 9, но и буквы латинского алфавита от A до F, представляющие значения от 10 до 15 соответственно. Такие числа называются шестнадцатеричными (hexadecimal numbers). ИТ-специалисты используют эти числа по причинам, которые мы не будем здесь обсуждать. Отметим, что показанные на рисунке хэш-значения неодинаковы из-за различий в подробностях реализации хэш-функций, генерирующих эти значения. Будем считать доказанной правильность этих значений, иначе можно просто заблудиться в хитросплетениях обширной темы реализации хэш-функций.

Длина криптографических хэш-значений достаточно велика, поэтому они трудны для чтения, тем более для сравнения человеком. Но по ходу текущей главы мы все же будем сравнивать различные методы хэширования данных, применяя для этого чтение и сравнение хэш-значений. Подобные действия с криптографическими хэш-значениями быстро становятся утомительной задачей. Поэтому в учебных целях я воспользовался укороченной версией криптографического хэш-значения SHA256 в оставшейся части главы. Все хэш-значения можно воспроизвести с помощью инструментального средства, предоставленного страницей вебсайта: http://www.blockchain-basics.com/Hashing.html.

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

Рис. 10.2 Вычисление укороченного хэш-значения для текста

Шаблоны хэширования данных

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

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

• независимое хэширование;

• повторяющееся хэширование;

• комбинированное хэширование;

• последовательное хэширование;

• иерархическое хэширование.

Независимое хэширование

Независимое хэширование (independent hashing) означает применение хэш-функции к каждому фрагменту данных независимо друг от друга. На рис. 10.3 схематически показана эта концепция, согласно которой отдельно вычисляется укороченное хэш-значение для двух различных слов.

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

Рис. 10.3 Схема независимого хэширования двух различных фрагментов данных

Вам уже известно, что хэш-функции выполняют преобразование любого произвольного фрагмента данных в хэш-значение. Само хэш-значение может рассматриваться как фрагмент данных. Поэтому существует возможность передачи хэш-значения как входных данных в хэш-функцию и вычисления нового хэш-значения. Это действительно работает. Повторяющееся хэширование – это повторное применение хэш-функции к ее собственным выходным данным. На рис. 10.4 схематически изображена концепция повторного вычисления укороченного хэш-значения. Для текста «Hello World!» генерируется хэш-значение 7F83B165, которое, в свою очередь, дает укороченное хэш-значение 45A47BE7.

Рис. 10.4 Схема повторного вычисления хэш-значений

Комбинированное хэширование

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

На рис. 10.5 показана схема концепции комбинированного хэширования. Сначала отдельные слова объединяются в одно слово с символом пробела между ними, после чего полученная фраза хэшируется. Полученное хэш-значение, показанное на рис. 10.5, совпадает с первым хэш-значением на рис. 10.4, что вполне объяснимо. Отметим, что хэш-значение объединенных данных напрямую зависит от способа объединения данных. На рис. 10.5 два слова были объединены простым последовательным размещением с символом пробела между ними, что в результате составило фразу «Hello World!». Иногда для обозначения места объединения данных используются специальные символы, такие как плюс (+) или хэштег (#), и это влияет на итоговое хэш-значение.

Рис. 10.5 Объединение данных и последующее вычисление хэш-значения

Последовательное хэширование

Цель последовательного хэширования – последовательное (инкрементальное) обновление хэш-значения по мере поступления новых данных. Для этого одновременно используются комбинированное и повторяющееся хэширования. Существующее хэш-значение объединяется с новыми данными, затем передается в хэш-функцию для получения обновленного хэш-значения. Последовательное хэширование особенно удобно, если нужно сопровождать единственное хэш-значение в течение некоторого времени и обновлять его сразу же после поступления новых данных. Преимущество этого типа хэширования заключается в том, что в любой момент времени имеется определенное хэш-значение, изменения которого можно проследить в обратном порядке, восстановив состояние до получения новых данных.

На рис. 10.6 схематично показана концепция последовательного хэширования, в соответствии с которой сначала отдельно обрабатывается слово Hello, и в результате получается укороченное хэш-значение 185F8DB3. После получения новых данных, представленных словом World! эти данные объединяются с существующим хэш-значением, и объединенный блок передается как входные данные в хэш-функцию. Для исходного текста World! 185F8DB3 генерируется укороченное хэш-значение 5795A986.

Рис. 10.6 Последовательное вычисление хэш-значений

Иерархическое хэширование

На рис. 10.7 показана концепция иерархического хэширования.

Рис. 10.7 Вычисление хэш-значений по иерархической схеме

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

Перспектива

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

Резюме

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

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

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

• Криптографические хэш-функции обладают следующими свойствами:

– быстрая генерация хэш-значений для любого типа данных;

– детерминированность;

– обеспечение псевдослучайности хэш-значений;

– односторонние функции;

– устойчивость к коллизиям.

• Применение хэш-функций к данным может быть выполнено по следующим шаблонам или типовым схемам:

– независимое хэширование;

– повторяющееся хэширование;

– комбинированное хэширование;

– последовательное хэширование;

– иерархическое хэширование.

Глава 11
Хэширование на практике
Рассказ о сравнении данных и создании вычислительных головоломок

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

Сравнение данных

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

Цель

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

Основная идея

Вместо явного последовательного сравнения содержимого данных по отдельным компонентам сравниваются их криптографические хэш-значения.

Как это работает

Вычисляются и сравниваются криптографические хэш-значения всех исследуемых данных. Если все криптографические хэш-значения различны, то все рассматриваемые данные также различны. Если какие-либо криптографические хэш-значения одинаковы, то соответствующие исходные данные также одинаковы [36].

Почему это работает

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

Обнаружение изменений в данных

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

Цель

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

Основная идея

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

Как это работает

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

Почему это работает

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

Обращение к данным, которые не должны изменяться

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

Цель

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

Основная идея

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

Как это работает

Ссылки на данные являются цифровым аналогом номерков (жетонов) в гардеробе. Гардеробный жетон указывает место хранения вашей куртки на гардеробных вешалках. Жетон необходим для получения своей куртки после хранения. В ИТ-области ссылки на данные работают аналогичным образом: это фрагменты данных, которые указывают (ссылаются) на другие данные. Компьютерные программы используют ссылки для обозначения мест хранения данных и последующего извлечения этих данных при необходимости. Хэш-ссылки (hash references) – это особый тип ссылок, использующих мощь криптографических хэш-значений. Для упрощения можно считать хэш-ссылки «гардеробными номерками», на которых обозначены хэш-значения вместо обычных чисел.

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

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

Схематическое описание

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

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

Рис. 11.1 Схематическое изображение корректной хэш-ссылки

На рис. 11.2 показано символическое представление поврежденной или некорректной хэш-ссылки.

Рис. 11.2 Схематическое изображение некорректной хэш-ссылки

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

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

Рис. 11.3 Схематическое изображение новой созданной хэш-ссылки после изменения данных

Почему это работает

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

Хранение данных, которые не должны изменяться

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

Цель

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

Основная идея

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

Как это работает

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

• цепочка (chain);

• дерево (tree).

Цепочка

Цепочка связанных данных, также называемая связанным списком (linked list) [9], образуется, когда каждый фрагмент данных содержит хэш-ссылку на другой фрагмент данных. Такая структура удобна для хранения и объединения данных, если не требуется одновременный доступ ко всем данным сразу, а выполняется последовательный проход по фрагментам. На рис. 11.4 показана схема этого подхода с использованием условных символьных обозначений, введенных в предыдущем разделе. Создание цепочки начинается с фрагмента данных «Данные 1» и хэш-ссылки R1. Как начальный фрагмент «Данные 1» не содержит никакой хэш-ссылки. Когда поступают новые данные, они размещаются вместе с хэш-ссылкой, указывающей на фрагмент «Данные 1». Хэш-ссылка R2 указывает на новые, только что полученные данные и на хэш-ссылку R1. Хэш-ссылка R3, которая указывает на фрагмент «Данные 3» и хэш-ссылку R2, создается точно так же.

Рис. 11.4 Данные, объединяемые в цепочку

Хэш-ссылка R3 – это все, что необходимо для доступа ко всем данным в цепочке в порядке, обратном по отношению ко времени их получения. Ссылка R3 также называется головой цепочки (head of the chain), потому что указывает на самый последний добавленный фрагмент данных. Очень важно не путать термин «голова» (head) (обозначающий фрагмент данных, который был добавлен самым последним) и термин «заголовок» (header), который будет рассматриваться в главе 14 при описании структуры данных блокчейна.

Дерево

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

Такую структуру также называют деревом Меркле (Merkle tree) [24], потому что ее впервые предложил использовать специалист по компьютерной криптографии Меркле (Merkle) и она действительно похожа на дерево, только перевернутое вверх корнем. Эта структура удобна для объединения множества различных фрагментов данных, доступ к которым обеспечивается одновременно через одну хэш-ссылку. Для формирования дерева, показанного на рис. 11.5, сначала создаются четыре фрагмента данных транзакций, изображенных в виде прямоугольников в нижней части схемы. В первую очередь создаются хэш-ссылки на отдельные фрагменты данных транзакций (R1-R4), после чего эти ссылки объединяются в пары. Далее создаются хэш-ссылки, указывающие на пары первых хэш-ссылок (R12 и R34). Процедура повторяется до тех пор, пока не будет создана единственная хэш-ссылка, которую также называют корнем (root) дерева Меркле (на схеме обозначена как R).

Рис. 11.5 Данные, объединяемые в древовидную структуру

Почему это работает

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

Выполнение долговременных вычислений

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

Цель

По причинам, которые станут понятными в следующих главах, может возникать необходимость в создании головоломок, требующих для решения определенных вычислительных ресурсов. Эти головоломки не должны решаться на основе знаний или данных, хранящихся где-либо, или с помощью мыслительных процессов, как при прохождении IQ-теста или теста, проверяющего знания в какой-либо области. Единственным способом решения таких головоломок являются использование только вычислительных мощностей и выполнение огромного объема вычислений.

Основная идея

Замок с секретным кодом – это особенный замок, открыть который можно только с помощью специальной последовательности цифр. Если такая последовательность неизвестна, то можно попытаться систематически перебирать все возможные комбинации до тех пор, пока не будет набрана правильная последовательность, открывающая замок. Эта процедура гарантирует, что замок будет открыт, но на ее выполнение затрачивается очень много времени. Систематический перебор всех возможных комбинаций не требует каких-либо знаний или логических рассуждений. Методика вскрытия кодового замка основана исключительно на усердной и кропотливой работе. Хэш-головоломки – это вычислительные головоломки, решение которых можно считать аналогом решения задачи вскрытия кодового замка методом проб и ошибок.

Как это работает

Ниже перечислены элементы хэш-головоломки [1]:

• исходные данные, которые не должны изменяться;