Криптографические основы блокчейн-технологий

Евгения Александровна Ищукова,
Сергей Петрович Панасенко,
Кирилл Сергеевич Романенко,
Вячеслав Дмитриевич Салманов

КриптографичесКие основы 

блоКчейн-технологий

Москва, 2022

УДК 004.338
ББК 65.050.253
И98

Ищукова Е. А., Панасенко С. П., Романенко К. С., Салманов В. Д.
И98 Криптографические основы блокчейн-технологий. – М.: ДМК Пресс, 
2022. – 302 с.: ил.

ISBN 978-5-97060-865-4

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

Дизайн обложки разработан с использованием ресурса freepik.com

УДК 004.338
ББК 65.050.253

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

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

© Ищукова Е. А., Панасенко С. П., Романенко К. С.,  
   Салманов В. Д., 2022
© Оформление, издание, ДМК Пресс, 2022
ISBN 978-5-97060-865-4

Оглавление

Предисловие ........................................................................................ 6

Введение ...............................................................................................7

Глава 1. Алгоритмы хеширования .................................................... 9
1.1 Основные понятия и определения ............................................................10
1.1.1 Структура алгоритмов хеширования .................................................10
1.1.2 Надстройки над алгоритмами хеширования .....................................14
1.2 Методы криптоанализа и атаки на алгоритмы хеширования .................18
1.2.1 Цели атак на алгоритмы хеширования ..............................................19
1.2.2 Атаки методом «грубой силы» ............................................................21
1.2.3 Словарные атаки и цепочки хеш-кодов .............................................22
1.2.4 Радужные таблицы...............................................................................26
1.2.5 Парадокс «дней рождения» и поиск коллизий ..................................27
1.2.6 Дифференциальный криптоанализ ...................................................30
1.2.7 Алгебраический криптоанализ ...........................................................34
1.2.8 Атаки, использующие утечки данных по побочным каналам ..........35
1.2.9 Другие виды атак .................................................................................35
1.3 Наиболее известные алгоритмы хеширования ........................................38
1.3.1 Алгоритмы семейства MD ...................................................................38
1.3.2 Алгоритмы семейства RIPEMD ...........................................................59
1.3.3 Алгоритмы семейства SHA ..................................................................69
1.3.4 Отечественные стандарты хеширования ...........................................84

Глава 2. Алгоритмы электронной подписи  
на эллиптических кривых ............................................................... 91
2.1 Математические основы ............................................................................91
2.2 Эллиптические кривые ...............................................................................95
2.2.1 Определение эллиптической кривой .................................................95
2.2.2 Основные операции над точками эллиптической кривой ...............96
2.2.3 Основные характеристики эллиптической кривой...........................99
2.2.4 Примеры эллиптических кривых .....................................................101
2.2.5 Задача дискретного логарифмирования в группе точек  
эллиптической кривой ...............................................................................105
2.2.6 Альтернативные формы представления эллиптических кривых ... 107
2.3 Основные алгоритмы электронной подписи .........................................111
2.3.1 Алгоритм ECDSA ................................................................................111
2.3.2 ГОСТ Р 34.10–2012 .............................................................................112

2.3.3 Некоторые особенности алгоритмов ECDSA  
и ГОСТ Р 34.10–2012 ...................................................................................114
2.3.4 Алгоритм EdDSA .................................................................................116
2.3.5 Алгоритм BLS .....................................................................................118

Глава 3. Основные принципы работы блокчейн-технологий ...122
3.1 Базовые механизмы блокчейн-систем ....................................................123
3.1.1 Транзакции .........................................................................................123
3.1.2 Упаковка транзакций в блоки ...........................................................127
3.1.3 Применение деревьев Меркля при формировании блоков ............130
3.2 Механизмы консенсуса ............................................................................131
3.2.1 Консенсус доказательства работы Proof of Work .............................131
3.2.2 Консенсус доказательства владения долей Proof of Stake ...............135
3.2.3 Консенсус на основе решения задачи византийских генералов ....136
3.2.4 Другие механизмы достижения консенсуса ....................................137
3.3 Выстраивание цепочки блоков ................................................................139
3.3.1 Принципы формирования цепочки .................................................139
3.3.2 Ветвления цепочки блоков ................................................................142
3.4 Смарт-контракт .........................................................................................145
3.5 Основные виды блокчейн-систем ...........................................................148
3.5.1 Публичный блокчейн .........................................................................148
3.5.2 Приватный блокчейн .........................................................................149
3.6 Криптовалютные кошельки .....................................................................150
3.6.1 Программы-кошельки .......................................................................150
3.6.2 Аппаратные кошельки .......................................................................152

Глава 4. Основные блокчейн-платформы ...................................153
4.1 Биткойн .....................................................................................................153
4.1.1 Введение в устройство блокчейн-системы Биткойн .......................154
4.1.2 Особенности механизма консенсуса в системе Биткойн ................156
4.1.3 Форки в системе Биткойн .................................................................156
4.1.4 Транзакции .........................................................................................159
4.1.5 Кошельки в системе Биткойн ............................................................203
4.1.6 Создание и использование иерархических  
детерминированных ключей .....................................................................206
4.2 Эфириум ....................................................................................................209
4.2.1 Глобальное состояние ........................................................................209
4.2.2 Консенсус ............................................................................................210
4.2.3 Газ ........................................................................................................211
4.2.4 Адреса и кошельки .............................................................................212
4.2.5 Транзакции .........................................................................................213
4.2.6 Структура блока .................................................................................213
4.2.7 Эволюция системы Эфириум ............................................................214
4.2.8 Основная и тестовые сети платформы Эфириум ............................218
4.2.9 Запуск сети Эфириум .........................................................................219
4.2.10 Смарт-контракты в системе Эфириум ...........................................234
4.3 Hyperledger ................................................................................................245

4  
Оглавление

4.3.1 Основные особенности системы ......................................................245
4.3.2 Проекты экосистемы Hyperledger .....................................................246
4.3.3 Архитектура Hyperledger Fabric ........................................................247
4.3.4 Пример смарт-контракта для Hyperledger .......................................248
4.4 Обзор других платформ ...........................................................................253
4.4.1 EOSIO ..................................................................................................253
4.4.2 Краткий обзор прочих блокчейн-платформ ....................................255
4.4.3 Обзор отечественных решений ........................................................257

Приложение 1. Таблицы констант алгоритмов хеширования ....261
П1.1 Таблица замен алгоритма MD2 .............................................................261
П1.2 Индексы используемых в итерациях слов блока  
сообщения алгоритма MD4 ............................................................................262
П1.3 Константы алгоритма MD5 ....................................................................263
П1.4 Константы алгоритма MD6 ....................................................................267
П1.5 Константы алгоритмов семейства SHA-2 .............................................268
П1.6 Раундовые константы алгоритмов семейства SHA-3 ..........................270
П1.7 Константы алгоритма ГОСТ Р 34.11–2012 ............................................271

Список сокращений ........................................................................275

Перечень рисунков .........................................................................281

Перечень таблиц .............................................................................286

Перечень источников .....................................................................289

Оглавление  5

Предисловие

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

Сергей Васильевич Матвеев,
эксперт ТК-26 «Криптографическая защита информации»

Введение

С момента появления блокчейн-технологий прошло менее 15 лет, но их активное 
развитие в течение этого времени предопределило вхождение данных 
технологий в весьма различные сферы деятельности.
Основной сферой применения блокчейн-технологий можно считать финансовую: 
они лежат в основе криптовалют, которые, похоже, уже достаточно 
прочно вошли в нашу жизнь. Буквально в последний год мы могли наблюдать 
всплеск интереса к криптовалютам после многократного удорожания основной 
из них – биткойна – в течение 2020 – начала 2021 года. 
При этом постоянно модернизируются и совершенствуются как сама платформа 
Биткойн и лежащая в ее основе блокчейн-система, так и данные технологии 
в принципе. Их развитие способствует и развитию множества смежных 
технологий и направлений: от криптографических алгоритмов до вычислительных 
ресурсов, применяемых пользователями подобных систем.
Помимо финансового сектора, блокчейн-технологии востребованы в различных 
системах государственных организаций, в частности:
 
 ведение различных реестров, например государственной регистрации 
прав на недвижимое имущество, землю и т. п.;
 
 выпуск цифровых удостоверений личности на основе блокчейн-технологий;
 
 
удаленное голосование, опробованное, в частности, в России в 2019 
и 2020 годах.
Можно предполагать, что в дальнейшем приведенный выше, далеко не полный 
перечень применений блокчейнов будет только расширяться.
Отметим, что распределенные реестры были известны и ранее, но именно 
блокчейн-технологии, обеспечивающие, с одной стороны, возможность модификации 
общих данных различными пользователями распределенных систем и, 
с другой стороны, контроль целостности и непротиворечивости данных на основе 
определенных правил, предопределили масштабное развитие подобных технологий 
и появление таких принципиально новых направлений, как криптовалюты.
Про блокчейн-технологии, особенно в части их применений в криптовалю-
тах, издано достаточно много книг. Специфика этой книги в том, что при ее 
создании мы изначально ставили своей целью рассмотреть и проанализировать 
именно криптографические механизмы, лежащие в основе блокчейн-технологий 
и предопределяющие их основные качества, способствующие столь 
бурному развитию и предполагаемому в будущем широчайшему применению 
данных технологий.
Понимая и разделяя интерес многих потенциальных читателей к крипто-
валютам, мы не обошли их стороной, но рассмотрели именно с точки зрения 
реализованных в них криптоалгоритмов и прочих методов, обеспечивающих 
технические составляющие безопасного использования криптовалют.

В первой главе книги описаны алгоритмы хеширования, обеспечивающие 
контроль целостности данных в блокчейне. Рассмотрены основные принципы 
данных алгоритмов, возможные проблемы при их реализации и использовании, 
включая известные атаки на алгоритмы хеширования. Приведено подробное 
описание наиболее известных алгоритмов хеширования, включая используемые 
в распространенных блокчейн-платформах.
Вторая глава также посвящена криптографическим алгоритмам – на этот 
раз алгоритмам электронной подписи, являющимся одним из важнейших элементов, 
обеспечивающих связь в цепочках данных блокчейна, и не только. Рассмотрены 
эллиптические кривые, лежащие в основе современных алгоритмов 
электронной подписи и наиболее часто применяемые из данных алгоритмов.
Третья глава описывает базовые механизмы построения цепочек данных – 
основы блокчейн-технологий. Значительная часть главы посвящена описанию 
различных механизмов достижения консенсуса, легитимизирующих действия 
пользователей с данными блокчейна.
Наконец, в последней главе рассмотрены примеры построения блокчейн-
платформ на основе алгоритмов и методов, описанных в предыдущих главах. 
В частности, дано подробное описание системы Биткойн, обеспечивающей 
оборот одноименной криптовалюты, наиболее широко используемой в мире.
Надеемся, что изложенная в нашей книге информация оправдает ваши ожидания 
от книги, окажется интересной и принесет пользу в вашей деятельности.
Авторы выражают глубокую признательность известному специалисту по 
прикладной криптографии Олегу Геннадьевичу Тараскину (компания Waves) 
за предоставленную для публикации в данной книге главу 2, без материала 
которой книга была бы неполной, а также за множество полезных замечаний, 
позволивших значительно улучшить книгу.
Авторы также благодарны эксперту технического комитета по стандартизации «
Криптографическая защита информации» (ТК-26) Сергею Васильевичу 
Матвееву за предисловие к книге и ценные замечания по ее материалу.
Будем рады вашим письмам по изложенным в книге вопросам, а также замечаниям 
к содержимому книги и предложениям по ее возможному усовершенствованию. 
Адреса электронной почты для связи с авторами: 
serg@panasenko.ru (Сергей Панасенко) и 
jekky82@mail.ru (Евгения Ищукова).

8  
Введение

Глава 1

Алгоритмы хеширования

Алгоритмы хеширования (или функции хеширования, хеш-функции) позволяют 
по определенным правилам выполнить свертку входных данных произвольной 
длины в битовую строку фиксированного размера, называемую хеш-
кодом [15] (распространены также термины «хеш» или «хеш-значение»).
Фактически хеш-функции выполняют контрольное суммирование данных, которое 
может происходить как с участием некоего секретного ключа, так и без него. 
Обычно алгоритмы ключевого хеширования представляют собой надстройки над алгоритмами 
хеширования, не использующими ключ. Однако существуют и такие хеш-
функции, которые изначально разрабатывались с учетом использования секретного 
ключа в качестве дополнительного параметра преобразований.
Такое контрольное суммирование достаточно широко применяется в области 
защиты компьютерной информации, в том числе:
 
 для подтверждения целостности данных;
 
 для свертки данных перед вычислением или проверкой их электронной 
подписи;
 
 в различных протоколах аутентификации пользователей;
 
 в процедурах генерации псевдослучайных последовательностей и производных 
ключей.
Алгоритмы хеширования применяются и с другими целями, не относящимися 
к задачам защиты информации. В частности, они применяются для вычисления 
уникальных идентификаторов данных и построения на их основе 
хеш-таблиц, существенно ускоряющих поиск требуемых данных в больших 
массивах. Однако в подобных случаях к алгоритмам хеширования предъявляются 
иные требования, чем при их криптографических применениях.
Алгоритмы хеширования активно используются в блокчейн-технологиях, 
наиболее часто – для свертки данных перед их подписанием электронной 
подписью. В ряде случаев хеш-функции используются и с другими целями – 
например, в биткойне для подтверждения проделанной работы используются 
найденные (получаемые путем перебора) хеш-коды специального формата – 
с количеством лидирующих битовых нулей не менее заданного.
Конкретные применения алгоритмов хеширования в технологиях блокчей-
на будут описаны в главах 3 и 4, а в данной главе рассмотрим подробно структуру 
алгоритмов хеширования, предъявляемые к ним требования, а также основные 
методы и результаты их криптоанализа.

1.1 основные понятия и определения

Функции хеширования позволяют выполнить однонаправленное преобразование 
входного массива произвольного размера в выходную битовую строку 
(хеш-код) фиксированного размера.
Криптографические хеш-функции должны обладать, как минимум, следующими 
свойствами [44, 202].
1.  Хеш-код сообщения должен однозначно соответствовать сообщению 
и должен изменяться при любой модификации сообщения.
2.  Должно быть вычислительно сложно найти прообраз, т. е. такое сообщение 
M, хеш-код которого был бы равен заданному значению h:

h = f(M),

где f() – функция хеширования.

3.  Должно быть вычислительно сложно найти второй прообраз, т. е. такое 
сообщение M2, хеш-код которого был бы равен хеш-коду заданного сообщения 
M1:

f(M1) = f(M2).

4.  Должно быть вычислительно сложно найти коллизию, т. е. такие два сообщения 
M1 и M2, хеш-коды которых были бы эквивалентны.

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

Схема Меркля–Дамгорда
Многие из широко используемых алгоритмов хеширования имеют схожую 
между собой структуру, которая была предложена в 1988–1989 гг. независимо 
двумя известными криптологами: Ральфом Мерклем (Ralph Merkle) [177] и Ай-
веном Дамгордом (Ivan Damgård) [102]. Она получила название «схема Мер-
кля–Дамгорда» (Merkle-Damgård construction) – см. рис. 1.1.
В соответствии со схемой Меркля–Дамгорда работают, в частности, алгоритмы 
MD4 [210], MD5 [212] и SHA [125], а также отечественный стандарт хеширования 
ГОСТ Р 34.11–2012 [15], которые будут подробно рассмотрены в этой главе далее.

IV
fb()
HN

M0

fb()

M1

. . .
fb()

MN

Рисунок 1.1. Схема Меркля–Дамгорда

Хешируемое сообщение M разбивается на блоки определенной длины (например, 
по 512 байт в алгоритме SHA-1) M0…MN. Выполняется (по-разному 

10  Глава 1

в различных алгоритмах) дополнение сообщения M до размера, кратного данной 
длине блока (при этом количество блоков может увеличиться – см., например, 
описание алгоритма SHA далее).
Каждый i-й блок сообщения обрабатывается функцией сжатия fb() (функция 
сжатия является криптографическим ядром алгоритма хеширования), причем 
данная функция накладывает результат этой обработки на текущий (промежуточный) 
хеш-код Hi-1 (т. е. результат обработки предыдущих блоков сообщения):

Hi = fb(Hi-1, Mi).

Результатом работы алгоритма хеширования hash() (т. е. хеш-кодом сообщения 
M) является значение HN:

hash(M) = HN.

Начальное значение H-1 обычно является константным и различным в разных 
алгоритмах хеширования; оно часто обозначается как IV (от Initialization 
Vector – вектор инициализации).

Алгоритмы хеширования на основе криптографической губки
Схема алгоритмов хеширования на основе «криптографической губки» 
(cryptographic sponge) была предложена рядом криптологов в работе [69]. 
Авторами данной схемы являются Гвидо Бертони (Guido Bertoni), Джоан 
Деймен (Joan Daemen), Михаэль Петерс (Michaël Peeters) и Жиль Ван Аске 
(Gilles Van Assche).
Алгоритмы хеширования, использующие конструкцию криптографической 
губки, содержат две фазы преобразований (рис. 1.2):
 
 «впитывание» (absorbing) – поблочная обработка входного сообщения, 
в процессе которой внутреннее состояние алгоритма хеширования «впитывает» 
свертку данных очередного блока;
 
 «выжимание» (squeezing) – сжатие внутреннего состояния для извлечения 
из него результирующего хеш-кода.

M

Дополнение

0

Состояние

0

+

f

+

f

+

f
f
f
f

Усечение

...

...

...

Впитывание
Выжимание

...

...

...

Хеш-код

Рисунок 1.2. Фазы преобразований криптографической губки

Конструкция криптографической губки, по мнению ее авторов, имеет как 
минимум следующие преимущества [69, 71]:

Алгоритмы хеширования  11

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

Надстройки над алгоритмами блочного шифрования
Существуют также варианты создания стойких однонаправленных хеш-
функций на основе алгоритмов блочного шифрования. В частности, в работе [
202] подробно описаны 12 алгоритмов, представляющих собой хеширую-
щие надстройки над блочными шифрами.
Рассмотрим две из таких надстроек более подробно. Первая из них – это алгоритм 
Матиаса–Мейера–Осиса (Matyas-Meyer-Oseas – MMO), функция сжатия 
которого представлена на рис. 1.3. В данном алгоритме нижележащий блочный 
шифр используется следующим образом [174]:
 
 блок хешируемых данных Mi подается на вход алгоритма шифрования 
в качестве открытого текста (P);
 
 ключом блочного шифра (K) служит текущее состояние алгоритма хеширования 
Hi-1, обработанное некоторой функцией g() (см. далее);
 
 на результат шифрования (C) блока Mi на ключе g(Hi-1) накладывается 
операцией XOR сам блок Mi, в результате чего получается новое состояние 
алгоритма хеширования Hi.

K

P

C

Блочный шифр
g()
Hi-1

Mi

+

Hi

Рисунок 1.3. Схема алгоритма MMO

Поскольку размеры блока шифруемых данных и ключа алгоритма шифрования 
могут быть различными (и чаще всего они действительно различаются), 

12  Глава 1

а размер состояния алгоритма хеширования является фиксированным, в алгоритме 
MMO существует необходимость в функции g(), задача которой состоит 
лишь в адаптации значения Hi-1 под требуемый размер ключа шифрования. Так 
как функция g() не влияет на безопасность алгоритма, она может быть максимально 
простой и, например, выполнять только дополнение Hi-1 до требуемого 
размера [246].
Формально алгоритм MMO представляется так:

Hi = E(Mi, g(Hi-1)) ⊕ Mi,

где E(P, K) – блочный шифр, шифрующий открытый текст P на ключе K.
Существует также вариант алгоритма MMO, который вместо операции XOR 
использует сложение 32-битовых субблоков Mi и C по модулю 232. В работе [217] 
такой вариант называется предпочтительным, в частности для алгоритмов 
MD4 и MD5.
В качестве блочного шифра может использоваться также функция сжатия 
какого-либо алгоритма хеширования, поскольку, как и блочный шифр, функции 
сжатия алгоритмов хеширования обычно принимают на вход два параметра (
состояние и хешируемый блок данных вместо ключа шифрования и шифруемого 
блока), выдавая в качестве результата модифицированное состояние. 
В этом случае описанные в данном разделе схемы можно рассматривать как 
надстройки, усиливающие криптографические свойства нижележащего алгоритма 
хеширования.
Еще один вариант формирования алгоритма хеширования на основе блочного 
шифра – алгоритм Миягучи–Пренеля (Miyaguchi-Preneel), который отличается 
от предыдущего только тем, что предыдущее состояние алгоритма 
хеширования также участвует в операции XOR с блоком сообщения и результатом 
его зашифрования (рис. 1.4) [174]:

Hi = E(Mi, g(Hi-1)) ⊕ Mi ⊕ Hi-1.

K

P

C

Блочный шифр
g()
Hi-1

Mi

+

Hi

Рисунок 1.4. Схема алгоритма Миягучи–Пренеля

Алгоритмы хеширования  13