Криптография и распределенные реестры

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ  
БЮДЖЕТНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ОБРАЗОВАНИЯ  
«ФИНАНСОВЫЙ УНИВЕРСИТЕТ ПРИ ПРАВИТЕЛЬСТВЕ  
РОССИЙСКОЙ ФЕДЕРАЦИИ»  
(ФИНАНСОВЫЙ УНИВЕРСИТЕТ)

В.Б. Гисин

КРИПТОГРАФИЯ  
И РАСПРЕДЕЛЕННЫЕ 
РЕЕСТРЫ
 
Учебное пособие для вузов

МОСКВА
2022

ISBN 978-5-00172-257-1

УДК 004.652.3
ББК 32.972.13
 
Г 51

Рецензенты:
Судаков В.А., доктор технических наук, ведущий научный 
сотрудник Института прикладной математики им. М.В. Келдыша РАН;
Чечкин А.В., доктор физико-математических наук, профессор, профессор Департамента математики Финансового 
университета при Правительстве Российской Федерации.

 

Г 51
Гисин В.Б. 
Криптография и распределенные реестры: Учебное пособие / В.Б. Гисин. — М.: Прометей, 2022. — 
186 с.

ISBN 978-5-00172-257-1
Пособие содержит изложение основ технологии распределенных реестров, представителем которой является 
технология блокчейн. Пособие включает в себя разделы, 
посвященные основам современной криптографии, в первую 
очередь криптографии открытого ключа, и теории функций 
хэширования, теории распределенных систем и технологии 
блокчейн. Помимо этого, в приложениях приведен математический материал, дающий более полное и цельное представление об изучаемых разделах.
Соответствует ФГОС ВО последнего поколения
Для студентов бакалавриата и магистратуры, обучающихся по направлениям подготовки «Прикладная математика и информатика», «Прикладная информатика» 
и «Информационная безопасность».

©  Гисин В.Б., 2022
© Издательство «Прометей», 2022

Оглавление

Предисловие ..................................................................................5
Введение .........................................................................................9

Глава I. Криптографические основы .........................................15
1. Криптографические примитивы ................................15
1.1. Принципы современной криптографии ..............15
1.2. Односторонние функции ..................................17
1.3. Трудные предикаты ........................................21
2. Криптографическое хэширование ..............................22
2.1. Функции хэширования и их свойства .................22
2.2. Построение функций хэширования ...................26
2.3. Алгоритмы поиска коллизий, основанные 
на парадоксе дней рождения ...................................30
2.4. Доказательство выполненной работы .................32
3. Криптография открытого ключа ................................37
3.1. Концепция асимметричного шифрования ...........37
3.2. Формализованная схема симметричного 
и асимметричного шифрования ..............................38
3.3. Примеры криптографических схем  
с открытым ключом ..............................................43
3.4. Цифровая подпись ..........................................47
3.5. Адреса в сетях распределенных реестров ............50

Глава II. Распределенные системы ............................................52
1. Модель распределенной системы ...............................52
1.1. Понятие распределенной системы .....................52
1.2. Упорядочение событий ....................................56
1.3. Синхронность и асинхронность .........................58
2. Время в распределенных системах .............................59
2.1. Временные отметки Лампорта ..........................61
2.2. Векторные часы ..............................................63
3. Консенсус в распределенных системах ........................65
3.1. Общее понятие консенсуса. Модели отказов ........65
3.2. Консенсус в синхронных системах .....................70
3.4. Консенсус в сетях блокчейн ..............................75

Глава III. Технология блокчейн .................................................79
1. От реестров к распределенным реестрам .....................79
2. Функционирование сетей блокчейн ............................82
3. Дерево Меркла ........................................................87
4. Типы сетей блокчейн ................................................89
5. Консенсус в сетях распределенных реестров ................92
6. Модель Накамото .................................................. 100
6.1. Основные понятия ........................................ 100
6.2. PoW и майнинг ............................................. 104
6.3. Устойчивость системы относительно атак 
и эгоистичный майнинг ....................................... 109
7. Смарт-контракты ................................................... 114
8. Технология блокчейн в финансовой сфере ................. 117
Заключение................................................................................120
Приложения ...............................................................................121

Приложение А. Алгебра и теория чисел ....................... 121
Приложение B. Эллиптические кривые ........................ 136
Приложение C. Теоретико-числовые алгоритмы ............ 154
Приложение D. Сложность вычислений ....................... 167
D.1. Классы P и NP ..................................................
D.2. Вероятностные алгоритмы (машины Тьюринга) .....
Глоссарий ...................................................................................176
Литература.................................................................................183

ПРЕДИСЛОВИЕ

Идеи, на которых основывается технология блокчейн, 
обсуждались в кругу специалистов несколько последних 
десятилетий. Удивительное по своей простоте и изяществу соединение некоторых из них привело к возникновению такого уникального явления, как Биткоин. Широкие 
дискуссии вокруг Биткоина начались практически сразу 
с момента его появления и продолжаются, не затихая, 
до настоящего времени. Несмотря на полярность мнений, 
стало ясно, что использованная в Биткоине технология 
имеет перспективы применения в самых разных областях, и, в частности (возможно, и прежде всего), в сфере 
финансов. 
За прошедшие десять с небольшим лет после 2008 г. 
Биткоин послужил катализатором технологической революции в сфере финансов. Информационное поле, сопровождающее рождение и внедрение новой технологии, 
находится сейчас в таком состоянии, когда нереалистичные и необоснованные ожидания могут смениться разочарованием и последующим торможением распространения 
новой перспективной технологии. Скепсис в отношении 
технологии блокчейн, лежащей в основе Биткоина, периодически сменяется завышенными ожиданиями. В последние годы амплитуда этих колебаний стала затухать, 
и траектория развития технологии блокчейн стала просматриваться более четко. Несмотря на то, что предпринимаются многочисленные попытки применить блокчейн 
в самых разных, подчас довольно экзотических видах деятельности, блокчейн остается тем, чем он и должен быть 
по задумке его разработчиков, — распределенной базой 
данных со всеми ее возможностями и ограничениями. 
Эта база данных может содержать общий реестр транзакций или других цифровых событий, которые происходят 
в сети, объединяющей участников (узлы сети).
За последние несколько лет было написано много 
книг и статей о Биткоине и блокчейне. Статьи посвящены, 

как правило, специальным вопросам. Для каждой книги 
характерны свои пропорции, в которых внимание уделяется технологическим аспектам и применениям. В основе 
технологии лежит математический аппарат, доступный 
для понимания общих принципов специалисту, имеющему стандартную общую университетскую математическую подготовку. В то же время используемые математические факты довольно специфичны, и, как правило, 
изучаются только при профессиональной математической 
подготовке.
В настоящей книге делается попытка описать технологию распределенных реестров с точки зрения математика, и сделать описание доступным читателю, изучавшему (или изучающему) математику при обучении 
на экономическом или инженерном направлении. Понимание математических фактов, используемых при изучении и внедрении технологии блокчейн, позволяет лучше 
понять природу проблем, связанных с безопасностью 
и эффективностью тех или иных решений, и точнее определить те области, в которых применение распределенных реестров целесообразно. Без понимания основополагающих концепций будет невозможно оценить ценность 
или потенциальное влияние технологии распределенных 
реестров на сферу финансов в целом и ценность конкретных приложений.
Три основных раздела книги посвящены трем краеугольным камням, составляющим фундамент технологии: 
криптографии, распределенным системам и блокчейнам 
(цепочкам блоков). 
Книга содержит четыре приложения. В приложении 
A собраны необходимые сведения из элементарной теории чисел. В приложении B приведено краткое описание 
эллиптических кривых, общее представление о которых 
потребуется читателю, желающему разобраться в том, как 
связаны узлы в распределенной сети блокчейна. В этой же 
главе даны компактные описания основных криптографических протоколов используемых в блокчейнах. Анализ 

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

Материал пособия рассчитан на семестровый курс 
и содержит необходимый теоретический материал. Что 
касается практических занятий, то, как показал опыт 
преподавания этой дисциплины в Финансовом университете, наиболее эффективными оказываются практические 
занятия, связанные с изучением кейсов по применению 
технологии блокчейн и анализом тех или иных платформ блокчейн. Технология развивается настолько стремительно, что ежегодно тематика семинарских занятий 
практически полностью обновлялась.
Основная часть пособия достаточно компактна. Это 
позволяет преподавателю, используя приложения, планировать изучение курса в зависимости от уровня математической подготовленности аудитории.
Объем публикаций, посвященных технологии блокчейн, растет настолько быстро, а ландшафт блокчейн 
меняется столь стремительно, что задача составления 
сколь-нибудь полного списка литературы выглядит нерешаемой. Вместе с тем (а, возможно, и вследствие этого), 
наблюдается явный дефицит учебной литературы по технологии блокчейн. Имеются хорошие учебники по криптографии и теории распределенных систем. Ссылки 
на них приведены в списке литературы. Есть несколько 
удачно написанных монографий, посвященных технологии блокчейн и сети Биткоин, которые могут играть роль 
учебных пособий. Ссылки на них также приведены. Автор 
воздержался от составления списка научной литературы, 
ограничившись ссылками на актуальные обзоры.

ВВЕДЕНИЕ

Распределенные реестры — это защищенные 
от несанкционированного доступа цифровые реестры, 
реализованные распределенным способом (без центрального хранилища) и, как правило, без центрального органа 
(банка, компании или правительства). Распределенные 
реестры позволяют сообществу пользователей регистрировать транзакции в общем реестре внутри этого сообщества, так что при нормальном функционировании распределенного реестра никакая транзакция не может быть 
изменена после публикации. В 2008 году идея распределенного реестра в формате цепочки блоков (блокчейна) 
была объединена с несколькими другими технологиями 
и вычислительными концепциями для создания современных криптовалют: электронных денежных средств, 
защищенных с помощью криптографических механизмов, а не центрального хранилища или органа власти.
Термины «распределенные реестры» и «блокчейн» 
используются зачастую как синонимы, хотя, видимо, 
и имеется небольшое различие. Блокчейн является частным случаем реестра, когда реестр представляет собой 
линейно упорядоченную цепочку блоков, содержащих 
записи. Если копии реестра хранятся в узлах сети, реестр 
(в том числе и блокчейн) можно считать распределенным. 
Эта формулировка нуждается в небольшом уточнении. 
Копии реестра, хранящиеся в узлах сети (реплики), могут, 
вообще говоря, различаться. Таким образом, система 
в целом хранит информацию о транзакциях в виде древовидной структуры: имеется основная цепочка, от которой могут отходить ветки. В процессе функционирования 
старые ветки отпадают, образуются новые, но основная 
цепь блоков (общая для всех веток) растет. Биткоин дает 
в некотором смысле канонический пример распределенного реестра со структурой блокчейн.
Альтернативный подход состоит в том, чтобы организовать хранение блоков транзакций в форме направленного 

ацикличного графа (DAG). В качестве распределенного 
реестра, отличного от блокчейн, можно привести Хэшграф.
Распределенность является ключевым свойством, обеспечивающим устойчивость системы относительно отказа 
в работе одного или нескольких узлов. Данные, хранящиеся в реестре, не будут потеряны, если некоторые узлы 
перестанут работать должным образом. С другой стороны, 
распределенность реестров порождает проблемы, характерные для любых распределенных систем. Хранение 
копии реестра в каждом узле и отсутствие центрального 
органа, который уполномочен обновлять реестр, делает 
необходимым обеспечивать консенсус узлов относительно 
состояния реестра.
К консенсусу относительно состояния реестра участники сети приходят голосованием с выбором лидера, проводимым в той или иной форме. Предоставление права 
голоса и способ учета поданных голосов лежат в основе 
механизмов достижения консенсуса. Методы достижения 
консенсуса существенно зависят от свойств сети. 
В публичных (открытых) сетях, где не требуется разрешения для подключения к сети, узлы в определенном 
смысле анонимны. Право голоса предоставляется тем 
узлам, которые предъявят доказательство выполненной 
работы и/или доказательство владения активами в соответствии с установленными требованиями (используются 
также доказательство активности, знания и некоторые 
другие). Алгоритмы достижения консенсуса, основанные 
на этих принципах, достаточно просты, устойчивы к расширению сети, но, как правило, затратны в отношении 
вычислительных ресурсов. К консенсусу должны прийти 
«честные» узлы, соблюдающие правила.
В приватных (закрытых) сетях узлы должны быть 
идентифицируемы. Узлы включаются в сеть и получают 
доступ к ее сервисам при выполнении требований, которые, вообще говоря, находятся вне пространства сети.
И открытые, и закрытые сети учитывают возможность некорректного (нелояльного) поведения некоторых