Криптографические хэш-функции

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

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

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

Хеш-функция:

• на вход получает любую строку

• на выходе выдает строку фиксированного размера (в этом курсе длина строки 256 бит)

• эффективно вычисляема

Криптографические свойства хэш-функции:

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

• необратимость

• открытость к вычислению

Рис. 1.1. Стойкость к коллизиям

1-е свойство хэш-функций: стойкость к коллизиям ( рис. 1.1).

Никто не может найти такие x и y, чтобы

х!= y и H(x)=H(y).

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

Хеш-функцию также называют функцией свертки, а значение функции для конкретного x – сверткой.

На рис. 1.1 красные стрелки показывают значение x и его свертку — H(x), и y с сверткой H(y). Обратите внимание, что на рисунке сказано:"Никто не может найти". Но этот не значит, что коллизии не существуют. Коллизии существуют, и чтобы понять почему, необходимо обратиться к рис. 1.2.

Рис. 1.2. Коллизии существуют

Слева на рис. 1.2 изображены все возможные значения на входе хэш-функции. Значение может быть строкой любого размера. А справа — все возможные результаты, которые должны быть размером 256 бит. Итак, справа - результаты, и их всего 2²⁵⁶ возможных значений. Слева же значений больше. Вопрос в том, сможет ли кто-либо обнаружить коллизию ( рис. 1.3).

Рис. 1.3. Можно ли найти коллизию?

Определенная точка слева всегда соответствует определенной точке справа. Значения справа сжимаются (сворачиваются). В действительности должны быть значения слева, которые будут указывать на одно и то же значение справа. Такие значения называют коллизиями.

То есть коллизии существуют, и ключевой вопрос в том, можно ли их найти?

При этом есть гарантированно работающий метод поиска коллизии:

Нужно взять 2¹³⁰ случайных значений на вход (левое облако на рис. 1.3). Проверив все эти 2¹³⁰ значения, можно сказать, что есть вероятность, равная 99,8%, что, по крайней мере, два из них будут образовывать коллизию.

Таков простой метод поиска коллизий. Он работает независимо от того, какова хэш-функция. Но проблема состоит в том, что процесс занимает очень много времени. Необходимо вычислить хэш-функцию 2¹³⁰ раз. И это, несомненно, огромное число.

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

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

Для некоторых хэш-функций, конечно, есть. Например, если хэш-функция принимает на вход любое число, а на выходе выдает число по модулю 2²⁵⁶, то есть оставляет последние 256 бит значения. Тогда можно легко найти коллизию. Одной из коллизий будет значение 3 и 3 плюс 2²⁵⁶. Таким образом, для некоторых возможных хэш-функций очень легко найти коллизию, для других - нет.

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

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

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

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

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

Допустим, кто-то подбрасывает монетку. И если выпадает "орел", то на выходе возвращается хэш строки "орел". А если — "решка", то — хэш строки "решка".

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

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

Свойство необратимости, которое рассматривается в этой лекции, немного сложнее. И вот способ, с помощью которого можно исправить проблемы с простым значением х, таким как в примере с подбрасыванием монетки ("орел" и "решка"). Необходимо взять значение х и объединить его со значением r, которое выбрано случайным образом.

Если r выбрано из распределения вероятностей с высокой min-энтропией, то для данного H(r|x), невозможно найти x.

Высокая min-энтропия (см. энтропия Реньи) означает, что распределение настолько широкое, что ни одно значение не может быть выбрано с какой-либо более-менее определенной вероятностью.

H (r|x) означает, что берутся все биты значения r и за ними помещаются все биты значения x. То есть, если берется хэш значения r с хэшем значения х, из этого объединения невозможно вернуть х. И это будет истинно для формально определенного свойства, что если r — случайное значение, выбранное из распределения вероятностей с высокой min-энтропией, то для данного H (r|x), невозможно найти x. Что значит высокая min-энтропия? Это можно описать так, что r выбирается случайно из огромного количества различных значений. Так, например, если r выбирается равномерно из всех строк длиной 256 бит, то любая конкретная строка выбиралась с вероятностью 1 из 2²⁵⁶, то есть 2^-256, а это действительно очень малое число. Итак, до тех пор, пока r выбирается таким образом, хэш r, объединенный с x, будет скрывать x.

Теперь давайте рассмотрим применение этого свойства – обязательство (commitment). Это своего рода цифровая аналогия, когда берется значение и запечатывается в конверте. Конверт кладется на стол, где всякий может его увидеть. То есть фиксируется то, что находится в конверте.

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

API обязательства

(com, key) := commit(msg)

match := verify(com, key, msg)

Чтобы запечатать msg в конверте:

(com, key) := commit(msg) – затем опубликовать com

Чтобы открыть конверт:

опубликовать key, msg

любой может использовать verify(), чтобы проверить валидность.

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

Чтобы создать обязательство, используются секретный ключ(key) и сообщение (msg). Данный процесс вернет два значения - обязательство (com) и ключ (key).

(com, key) := commit(msg)

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

match := verify(com, key, msg)

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

Свойства безопасности обязательства:

1 свойство - необратимость: для данного com, невозможно найти msg.

2 свойство - невозможно найти msg1!= msg2 такое, чтобы verify(commit(msg1), msg2) == true

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

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

Откуда известно, что эти два свойства неизменны? Для начала нужно рассмотреть, как можно их использовать.

commit(msg) := (H(key | msg), key)

где key – случайное значение 256 бит

verify(com, key, msg) := (H(key | msg) == com)

Свойства безопасности:

Необратимость: для данного (H(key|msg), невозможно найти msg.

Фиксация: невозможно найти msg1!= msg2 такое, чтобы

(H(key|msg1) == (H(key|msg2)

Чтобы создать обязательство сообщения, генерируется случайное 256-битное значение - ключ. В качестве обязательства возвращается хэш конкатенации ключа и сообщения (H(key|msg)). В качестве значения ключа используется хэш этого ключа. Чтобы сделать проверку, нужно вычислить хэш ключа, объединенного с сообщением.

Перейдем к свойствам безопасности.

для данного H(key|msg), невозможно найти msg.

То есть для данного обязательства (com= H(key|msg)) невозможно найти сообщение (msg).

Это свойство необратимости, которое было рассмотрено ранее. Ключ — это случайное 256-битное значение. Свойство необратимости гласит, что если будет взято сообщение, и перед ним поставлено значение, которое было выбрано случайным образом и размером 256 бит, тогда невозможно найти значение сообщения.

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

Обязательство: невозможно найти msg1 != msg2 такое, чтобы

(H(key | msg1) == (H(key | msg2)

Схема обязательств будет работать только благодаря двум рассмотренным свойствам безопасности.

3-е свойство хэш-функций - открытость для сложного вычисления.

Для любого возможного значения на выходе y, если k берется из распределения с высокой min энтропией, невозможно найти такой x, чтобы H(k | x) = y.

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

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

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

Применение: сложная поисковая задача

При заданном идентификаторе задачи (puzzle ID) id (из распределенной последовательности с высокой min-этропией) и целевым значением Y:

Пытаться найти решение x, такое чтобы

H(id | x) ∈ Y

Свойство открытости для сложного вычисления подразумевает, что нет лучшей стратегии решения, чем попытка случайного поиска значения x.

Идея состоит в том, имеется идентификатор задачи (id), который выбирается из некоторой высокой распределенной случайной последовательности с высокой min-энтропией. И задана цель — Y, которая должна быть равна хэш-функции. Необходимо попытаться найти решение - x. Таким образом, если хэшировать идентификатор задачи (ID) вместе с решением X, будет получен результат, который находится в заданном Y. Y — это целевой диапазон или набор желаемых результатов хэширования. ID определяет конкретную задачу, а x — ее решение.

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

Рис. 1.4. Стойкость к коллизиям

Она называется SHA-256 и работает следующим образом. Берется сообщение, которое необходимо хэшировать, и разбивается на блоки размером 512 бит (синие блоки на рис. 1.4). Сообщение не должно быть кратно размеру блока, поэтому в конце будет добавляться дополнение (padding ). В конце дополнения будет поле длиной 64 бит, которое обозначает длину сообщения в битах. А перед дополнением будет стоять один бит, за которым следует некоторое количество нулевых бит, чтобы заполнить блок до конца. Когда длина сообщения станет кратной блоку размером 512 бит, оно разбивается на эти блоки. Потом выполняется вычисление. Оно начинается с 256-битного значения, называемого IV. Это номер, который можно просмотреть в стандартном документе. Берется IV и первый блок сообщения, получается 768 бит, и пропускается через функцию сжатия. На выходе получается 256 бит. То же самое делается со следующими 512 битами сообщения – этот цикл продолжается до конца. Каждая итерация сжимает последующий 512-битный блок сообщения и включает его в логический результат. Результатом вычисления станет хэш, размером 256 бит. При этом нет проблемы доказать, что если функция обладает свойством стойкости к коллизиям, то вся хэш-функция также будет обладать стойкостью к коллизиям. В этой части лекции были рассмотрены хэш-функции, их свойства и использование этих свойств. Описана хэш-функция, которая используется в биткоине. В следующем разделе лекции будут рассмотрены способы использования хэш-функций для создания более сложных структур данных, которые используются в распределенных системах, таких как биткоин.

Терминологический словарь

Бит – единица измерения информации в двоичной системе счисления.

Хеширование (англ. hashing) — преобразование массива входных данных произвольной длины в (выходную) битовую строку фиксированной длины, выполняемое определённым алгоритмом.

Хешем (хэш-суммой, хэш-кодом) называется результат обработки неких данных хэш-функцией.

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

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

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

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

Хеш-указатели и структуры данных

Хеш-указатель ( рис. 1.5) – это указатель на место хранения информации и (криптографический ) хэш этой информации

Имея хэш-указатель, можно

• запросить информацию, на которую он указывает обратно

• верифицировать то, что хэш не изменился, как следствие, не изменилась информация.

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

Рис. 1.5. Изображение хэш-указателя

На рис. 1.5 показано, как в лекциях будет изображаться хэш-указатель. H( ) – хэш информации и стрелка, указывающая на эту информацию.

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

Рис. 1.6. Определение искажений

Для примера рассмотрим связный список, построенный с хэш-указателями( рис. 1.6). Эта структура данных называется цепочкой блоков (блокчейн).

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

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

Рис. 1.7. Определение искажений

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

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

Рис. 1.8. Определение искажений

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

Рис. 1.9. Определение искажений

Если, конечно, злоумышленник также не подделает блок справа как показано на рис. 1.9. Но если он это делает, хэш этого блока не будет соответствовать хэшу, показанному как крайнее правое значение H(). А это значение злоумышленник не может изменить, потому что сохраненное значение является заголовком всего списка. И если злоумышленник хочет подделать данные в какой-либо точке данной цепочки, то, чтобы сохранить согласованность, ему придется изменять хэш-указатели вплоть до начала. В итоге он столкнется с серьезной проблемой, потому что не сможет подделать заголовок списка. Все это означает, что сохранение данного хэш-указателя является средством контроля изменений всего списка от начала до конца. Поэтому можно построить цепочку блоков похожую на эту, содержащую столько угодно блоков, но в начале имеющую особый блок, который можно назвать генезис-блоком. Все это представляет собой журнал контроля изменений, построенный из последовательности блоков.

Рис. 1.10. Определение искажений

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

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

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

Рис. 1.11. Доказательство вхождения в дерево Меркла

Поэтому, если сохранен только корень, и кто-то хочет доказать, что блок находится в дереве Меркла, он должен показать блок с рисунка рис. 1.11. Можно пройти по всему до блока данных, проверяя на соответствие сохраненные хэши. И только проверив хэши до корня, можно убедиться, что этот блок данных находится в дереве Меркла. Таким образом, если будет O(log n) элементов, которые нужно отобразить, то требуется O(log n) времени, чтобы их проверить. И поэтому даже при очень большом числе блоков данных в дереве Меркла, можно проверить достоверность их принадлежности за относительно короткое время.

Преимущества дерева Меркла:

В дереве содержится множество элементов, но помнить необходимо только хэш корня.

Можно проверить вхождение за О(log n) время/пространство

Разновидность: сортированное дерево Меркла

Можно проверить на вхождение за O(log n) (показать элементы перед, после пропавшего)

Таким образом, деревья Меркла имеют различные преимущества. Одно из них состоит в том, что дерево содержит много элементов, но нужно помнить только корневой хэш, который составляет всего лишь 256 бит. Можно проверить принадлежность к дереву Меркла в логарифмическом времени и логарифмическом пространстве. Есть разновидность дерева Меркла — сортированное дерево Меркла. Это то же самое дерево, но здесь блоки, расположенные внизу, сортируются в определённом порядке. Скажем, алфавитном, лексикографическом или числовом, или каком-либо другом. Как только дерево отсортировано, можно проверить достоверность данных в нем. То есть можно доказать, что конкретный блок не находится в дереве Меркла. Для этого нужно указать путь к элементу, который находится непосредственно перед тем, где будет этот элемент, и сразу после того места, где он должен быть. И тогда можно сказать, что оба эти элемента находятся в дереве Меркла, они последовательны. И поэтому между ними нет места. Между ними нет ничего, поэтому не может быть доказательства, что они не являются членами дерева. Итак, дерево Меркла — это дерево двоичного поиска, построенное с помощью хэш-указателей, в котором можно осуществить проверку членства логарифмическим временем, либо сортировкой, и это очень эффективно.

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

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

Терминологический словарь

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

Связные списки — базовая динамическая структура данных в информатике, состоящая из узлов, каждый из которых содержит как собственно данные, так и одну или две ссылки ("связки") на следующий и/или предыдущий узел списка.

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

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

Цифровые подписи

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

Требования к подписям:

• Подписать может только один человек, но все могут проверить. Точно так же, как с подписью на бумаге.

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

Вопрос в том, как это можно реализовать в цифровой форме с использованием криптографии?

Рис. 1.12. API цифровых подписей

API для цифровых подписей показан на рис. 1.12.

Есть три операции, которые необходимо сделать. Первая – генерация ключей с помощью операции generateKeys. Входным параметром служит значение размера ключа (keysize) в битах. Эта процедура генерирует два ключа — sk и pk. sk — закрытый, секретный ключ подписи. Это информация, которую необходимо держать в секрете и использовать для создания своей подписи. А pk - это открытый, общедоступный ключ проверки, который можно дать любому, чтобы он мог проверить достоверность подписи.

Вторая операция — это операция подписи. Здесь используется закрытый ключ подписи и сообщение, на котором необходимо поставить подпись. Это действие возвращает sig (комбинацию битов), которая является подписью. И затем, третья операция — это проверка, которая берет то, что считается истинной подписью и проверяет ее достоверность. Для ее выполнения берется открытый ключ подписывающего лица, подписанное сообщение и подпись. Эта операция отвечает на вопрос, настоящая ли это подпись, возвращая значение "да" или "нет".

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

Требования к подписям:

1. "достоверные подписи подтверждаются": verify(pk, message, sign(sk,message)) == true

2. "подпись нельзя подделать": злоумышленник, знающий pk и имеющий возможность видеть подписи на любых сообщениях, не может создать проверяемую подпись на другом сообщении.

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

Это свойство обычно объясняют с помощью импровизированной игры со злоумышленником ( рис. 1.13).

Рис. 1.13. Игра со злоумышленником

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

Рис. 1.14. Генерация ключей

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

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

Рис. 1.15. Злоумышленник отправляет судье сообщение

Взломщик собирается отправить сообщение (m0) судье ( рис. 1.15). Судья подписывает это сообщение и отправляет подписанное обратно. Взломщик может посмотреть на это, почесать голову, и отправить другое сообщение (m1).

Рис. 1.16. Получение злоумышленником подписанных сообщений от судьи

Судья подпишет и его ( рис. 1.16). Взломщик может отправить любое количество сообщений и получить на них подписи.

Как только взломщик удостоверится, что увидел достаточно подписей, он выберет сообщение m, на котором хочет подделать подпись, и попытается это сделать ( рис. 1.17).

Рис. 1.17. Подделка подписи под сообщением

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

После получения бросающий вызов запустит алгоритм проверки, с помощью открытого ключа ( рис. 1.18).

Рис. 1.18. Проверка подписи, которую подделал злоумышленник

И если алгоритм возвращает значение true, то взломщик победил, так как он смог подделать подпись.

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

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

Биткоин использует определенную схему цифровой подписи, которая называется ECDSA. Это алгоритм цифровой подписи с эллиптической кривой, стандарт правительства США. В рамках данного курса не будут рассматриваться детали его работы, которые основываются на достаточно сложной математике. Заострим внимание только на том, что для ECDSA важна высокая степень случайности. При этом особенностью ECDSA является то, что даже если недостаточная степень случайности используется только в процессе подписи, а сам ключ совершенен, это всё равно приведет к его потере.

Терминологический словарь

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

Открытые ключи как идентификаторы личности

Рассмотрим один из способов применения цифровых подписей.

открытый ключ = = идентификатор личности

если sig такой, что verify(pk, msg, sig) == true, считается, что pk произносит: "[msg]" и чтобы "говорить от имени" pk, нужно знать соответствующий закрытый ключ sk.

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

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

Как создать новый идентификатор

создаем новую случайную пару ключей (sk, pk):

• pk – публичное "имя", которое можно использовать (обычно лучше использовать хэш от pk)

• sk позволяет "говорить от имени" идентификатора

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

Децентрализованное управление идентификацией:

• любой может создать новый идентификатор в любое время в любом количестве!

• нет центрального места координации

Идентификаторы в системе биткоин называют "адресами".

Рассмотрим подробнее, что такое децентрализованная идентификация. Это значит, что отсутствует необходимость иметь одно место для регистрации пользователей в системе, получения имени пользователя (user name). Не нужно сообщать кому-то о намерении использовать определенное имя. Если нужен новый идентификатор, его нужно просто создать. Любой может создать новый идентификатор в любое время и в любом количестве. Если есть необходимость иметь 5 разных имен, нужно создать пять идентификаторов.

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

Конфиденциальность:

• Адреса не имеют прямой привязки к реальной личности.

• Но наблюдатель может связать действия адреса в определенное время и сделать нужные выводы.

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

Простая криптовалюта

Рассмотрим, как связаны хэш-функции и цифровые подписи с криптовалютой на примере простой криптовалюты – Гуфикойна ( рис. 1.19).

Рис. 1.19. Принцип работы гуфикойна

Гуфи может создавать новые монеты в любое время. Новая монета после создания принадлежит Гуфи. Монету можно представить следующей структурой данных. Есть операция CreateCoin (создать монету) и есть уникальный CoinID (ID монеты), который сгенерировал Гуфи. Также есть цифровая подпись Гуфи, которую любой может проверить. Поэтому всякий, получающий монету, может проверить, что подпись действительна и что это подпись этого заявления.

Рис. 1.20. Трата гуфикойнов

Второе правило Гуфикойн состоит в том, что владелец монеты может ее передать кому-то другому. Он может ее потратить ( рис. 1.20). Так, например, у Гуфи есть монета, которую он создал. Гуфи делает заявление, в котором говорится: заплатить монету Элис. Элис представлена здесь своим отрытым ключом. Заплатить открытому ключу Элис монету, представленную хэш-указателем, и это все также подписано Гуфи. Так как Гуфи – владелец монеты, то ему следует подписывать всякую транзакцию, которая связана с передачей монеты.

После этого монета станет принадлежать Элис. И она может это доказать, предоставив структуру данных, действительно подписанную Гуфи и указывающую на монету, которая принадлежит Гуфи.

Рис. 1.21. Трата гуфикойнов

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

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

И тогда тот, кто владеет монетой, может передать ее кому-то другому, подписав заявление о передаче этой монеты человеку X. Достоверность монеты можно проверить, просто пройдя по цепочке и проверяя в ней все подписи. Это Гуфикойн.

Но у Гуфикойн есть большая проблема с безопасностью.

Рис. 1.22. Двойная трата монеты

Еще раз вернемся к монете Гуфи. Гуфи создал монету, затем передал ее Элис. Элис какое-то время владела монетой.Затем Элис передала эту монету Бобу. А потом она создает такую же структуру данных, но в ней она передает эту же самую монету Чаку и подписывает данную операцию. Чак может не знать о том, что находится в левом верхнем углу этой структуры данных. Например, если Элис просто отдала монету Бобу и не рассказала Чаку. Теперь Чак, смотря на представленную структуру, совершенно справедливо считает, что он — владелец монеты. У Чака есть все основания быть владельцем этой монеты, как и у Боба есть такие же основания быть владельцем этой монеты ( рис. 1.22). В этом заключается проблема — монеты нельзя так передавать.

Проведение операции с одной и той же монетой дважды называется атакой двойного расходования. Атаки двойного расходования — одна из ключевых проблем, которую следует решить в криптовалюте. Гуфикойн не защищен от этой атаки. Хотя криптовалюта Гуфикойн проста для понимания, она не подойдет для построения криптовалюты, потому что в ее структуре может присутствовать двойное расходование. Чтобы криптовалюта была работоспособной, необходимо решить эту проблему. Для этого рассмотрим еще одну криптовалюту – Скруджкойн.

Скруджкойн похож на Гуфикойн, но он защищен от атаки двойного расходования.

Рис. 1.23. Скруджкойн

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

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

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

На практике (в биткоине) для оптимизации в один блок помещается сразу несколько транзакций.

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

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

В Скруджкойн есть два вида транзакций. Первая транзакция — создание новых монет CreateCoins. Это похоже на операцию, которую Гуфи делал в Гуфикойн. Но здесь в одной транзакции можно создавать нескольких монет.

Рис. 1.24. Создание монет Скруджкойн

ID номер транзакции — 73. Тип транзакции — это создание монет. Ниже расположен список созданных монет. Каждая монета будет иметь серийный номер в этой транзакции: ноль, один, два и т. д. Каждая монета имеет ценность, определенную в Скруджкойн. И каждая монета имеет получателя, который указан в виде открытого ключа. Таким образом, этот тип транзакции создает множество новых монет и присваивает их людям как первоначальным владельцам.

Рис. 1.25. Добавление идентификаторов монет

Далее в Скруджкойн добавляется идентификатор для каждой монеты (coinID), на который в дальнейшем можно сослаться.

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

Рис. 1.26. Транзакция PayCoins потребляет (и уничтожает) некоторые монеты, создавая новые с той же общей ценностью

Второй вид транзакции— транзакция передачи монет PayCoins( рис. 1.26). Транзакция, которая некоторые монеты потребляет, уничтожая, а из них создает новые монеты той же общей ценности, но которые могут принадлежать разным людям. На рис.1.26 показана транзакция 73, ее тип — PayCoins. Перечислен список потребляемых монет. Все эти монеты потребляются и уничтожаются транзакцией PayCoins. Стоимость всех этих монет объединяется и создается ряд новых монет. Как и раньше, в транзакции CreationCoins каждая из них имеет свою ценность и принадлежит определенному получателю.

И новые монеты имеют ровно такую же общую стоимость, как и те, которые были уничтожены.

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

Во-первых, если потребленные монеты действительны, то есть они действительно были созданы в предыдущих транзакциях.

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

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

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

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

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

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

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

Также нужно решить проблему присвоения идентификаторов ID децентрализованным образом. Решение перечисленных задач позволит создать криптовалюту, похожую на биткоин. Она будет похожа на Скруджкойн, но без централизованной части.

Терминологический словарь

Двойное расходование (double spending) – повторная передача одних и тех же активов.

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