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

Недавно (20 июня 2019 года) на Cryptology ePrint Archive была опубликована статья "SoK of Used Cryptography in Blockchain". Данный пост - пятый в запланированной серии, содержащей любительский перевод этой статьи.

Систематизация знаний по используемой криптографии в блокчейне

(перевод с английского

статьи

Mayank Raikwar, Danilo Gligoroski and Katina Kralevska

SoK of Used Cryptography in Blockchain

Cryptology ePrint Archive, Report 2019/735

https://eprint.iacr.org/2019/735)

Аннотация

(перевод аннотации здесь)

1 Введение (перевод введения здесь)

1.1 Наш вклад (перевод здесь)

2 Методология исследования (перевод здесь)

3 Основные понятия блокчейна

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

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

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

Хэш-функция H - это функция, которая принимает вход произвольного размера и сопоставляет его с выходом фиксированного размера. Криптографические хэш-функции имеют дополнительные свойства, такие как: а) стойкость к коллизиям - трудно найти два входа a и b таких, что H(а) = H(b); b) cтойкость к поиску первого прообраза - для данного вывода y трудно найти вход a такой, что H(а) = y; и c) cтойкость к поиску второго прообраза - для заданных входа  a и выхода y = H(а) трудно найти второй вход b, такой, что H(b) = y. Читатели, заинтересованные широким охватом области криптографических хэш-функций, отссылаются к [18].

Рисунок 2: Блокчейн-структура данных с блочным форматом.
Криптографические хэш-функции в блокчейне используются для различных целей, таких как:
1. решение криптографических головоломок (доказательство работы (PoW) в Биткойне [1]);
2. генерация адресов (для открытых и закрытых ключей);
3. сокращение размера публичных адресов;
4. подписи сообщений.
Наиболее популярными криптографическими хэш-функциями, используемыми в блокчейнах, являются SHA-2 [19] (особенно вариант SHA-256 - вариант, который выдает на выходе 256 бит), а также некоторые из хорошо проанализированных хэш-функций из конкурса NIST SHA-3, которые перешли на более поздние этапы этого процесса (5 финалистов или некоторые из 14 участников из второго этапа [20]).
Некоторые из существующих блокчейн-проектов, таких как IOTA, создали свою собственную ”доморощенную” криптографическую хэш-функцию Curl-P, которая была воспринята криптосообществом очень критически и негативно [21], [22].
Типичный способ использования криптографических хэш-функций в блокчейн-проектах заключается в форме режима работы, т. е. комбинации нескольких вызовов одной и той же или разных хэш-функций. Например, в Биткойне [1] SHA256 используется дважды, и эта конструкция называется SHA256d, т. е.,
  (1)
Майнинг - это процесс создания нового блока транзакций путем решения криптографической головоломки, и участник, который решает головоломку первым, называется майнером блока. Если мы посмотрим на головоломку Bitcoin PoW, мы увидим, что майнер должен найти Nonce раз (подобно протоколу Hashcash [7], который мы обсуждаем в следующем подразделе), чтобы создать следующий блок в блокчейне.
Головоломка выглядит так:
  (2)

где T - 256-битное целевое значение.

Таблица 1. Доля выходов SHA256d в соответствии с целевым значением.
Глядя на долю выходов SHA256d, которые меньше целевого значения T для различных значений T в Таблице 1, можно понять, почему майнинг является трудным в PoW. А именно, вероятность нахождения nonce, которая приведет к тому, что весь блок будет иметь хэш, который меньше целевого значения, равна

(3)

Далее мы обсудим исследовательскую и инновационную деятельность в области криптографических хэш-функций, которые были либо отдаленно, либо напрямую связаны и вдохновлены тенденциями в блокчейне.
Спустя несколько лет после запуска биткойна и его исходного кода, опубликованного в качестве открытого исходного кода на Github, блокчейн-разработчики начали копировать и менять его базовый код, а также начали внедрять различные варианты и инновации. Одним из самых ранних форков с 2011 года, который до сих пор популярен в наши дни, является Litecoin [23]. Основная идея дизайна Litecoin заключалась в использовании другой хэш-функции для доказательства работы. Мотивация исходила из того, что еще в 2011 году появились тенденции к созданию специализированных прикладных интегральных схем (ASIC) аппаратных реализаций SHA256d, которые будут добывать блоки на несколько порядков быстрее, чем обычные процессоры и графические процессоры. Вместо SHA256d Litecoin использует Scrypt [24] – интенсивно использующую память сборку с использованием конструкции HMAC [25], созданной с помощью SHA256, и использованием потокового шифра Salsa20/8 [26]. Идея заключалась в том, что использование Scrypt будет непрактичным для его реализации на ASIC, что, таким образом, дает возможность индивидуальным владельуам обычных компьютеров и GPU стать заметным майнинг-сообществом. Хотя без сомнения мы можем сказать, что Litecoin является очень успешной альтернативной криптовалютой, мы можем с уверенностью утверждать, что его первоначальная цель быть ASIC-устойчивым блокчейн проектом не была успешной. В настоящее время вы можете найти коммерческие продукты для аппаратного майнинга Litecoin.
Собственно, можно сказать, что 10-летняя история блокчейна, в целом, и криптовалют, в частности, - это история неудачных попыток построить устойчивый блокчейн, который предотвратит появление прибыльных ASIC майнеров, способных добывать блоки со скоростями вычисления хэша, которые на несколько порядков выше, чем у обычных пользователей процессоров и ГПУ. В этой короткой истории мы можем упомянуть Ethash, используемый в Ethereum [11], для которого сейчас в продаже имеются ASIC майнеры как минимум двух компаний. В 2013 году QuarkCoin [27] представил идею использования цепочки из шести хэш-функций (пять финалистов SHA-3 BLAKE, Grøstl, JH, Keccak и Skein [28]) и хэш-функции из второго этапа Blue Midnight Wish [29]. Одна из мотиваций функции QuarkCoin PoW быть более устойчивой к ASIC, чем SHA256d. Идея каскада в QuarkCoin позже была расширена до каскада из одиннадцати хэш-функций в Darkcoin (позже переименована в DASH [30]). Излишне говорить, что в настоящее время есть коммерчески доступные ASIC-майнеры также и для X11. Разногласия между ASIC-майнерами и криптовалютным сообществом, похоже, остаются до сих пор, и в некоторой степени развивают и вдохновляют новые проекты в протоколах блокчейн. Последним является инициатива Programmatic Proof-of-Work (ProgPoW) для блокчейн-экосистемы Ethereum, которая направлена на то, чтобы сделать майнинг на ASIC менее эффективной и дать некоторые преимущества для майнинга на графических процессорах (GPU) [31].