CryptoNight


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

Основы

Алгоритм CryptoNight был разработан примерно в 2013 году в рамках протокола CryptoNote.

Изначально цель состояла в том, чтобы алгоритм могли использовать обычные серийные CPU. Это достигалось путём:

  • использования «родного» AES шифрования;
  • использования быстрых 64-битных мультипликаторов;
  • использования блокнотной памяти, точно подходящей под размер кэша третьего уровня (L3) для каждого ядра на CPU Intel (примерно 2 Мб).

Более амбициозная цель разработки заключалась в том, чтобы сделать вычисления посредством схем ASIC неэффективным. Цель достигнута не была, как и в случае со всеми другими алгоритмами, направленными на противодействие использованию ASIC. Эффективная схема ASIC, работающая с CryptoNight, была разработана в 2017 году компанией Bitmain.

Проект Monero начал использовать CryptoNight в качестве алгоритма доказательства работы в 2014. С тех пор алгоритм постепенно развивался, при этом намеренно сводилась к нулю какая-либо совместимость данного алгоритма с выпускаемыми ASIC. В настоящее время Monero использует версию CryptoNight v2. Это третья итерация оригинального алгоритма CryptoNight (v0, v1, v2).

Цель: найти хеш с достаточно малым значением

В случае с алгоритмами доказательства работы, в основе которых лежит хеширование, цель состоит в нахождении хеша с достаточно малым значением.

Хеш представляет собой целое число (как правило, это довольно большое число). Большинство хеш-функций выдаёт 256-битные хеши (целые числа от 0 до 2^256). Так обстоит и в случае с двойным хешем SHA-256, используемым Bitcoin, и CryptoNight у Monero.

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

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

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

В основе CryptoNight лежат:

  • AES шифрование;
  • 5 хеш-функций, каждая из которых стала «финалистом» конкурса SHA-3, проводимого Национальным институтом науки и техники США (NIST):
    • Keccak (основная функция)
    • BLAKE
    • Groestl
    • JH
    • Skein

Входные данные

В случае с Monero входные данные представляют собой совокупность, состоящую из:

  • упорядоченного заголовка блока (примерно 46 байтов; могут быть в формате varint-представления);
  • корня дерева Меркла (32 байта);
  • ряда транзакций, включённых в блок (примерно 1-2 байта; могут быть в формате varint-представления).

Для получения дополнительной информации см. функцию get_block_hashing_blob() function to dig further.

Алгоритм

Внимание!
Настоящая статья призвана дать читателю глубокое понимание алгоритма CryptoNight. Чтобы ещё глубже понять аспекты реализации, следует ознакомиться со Стандартом CryptoNote и исходным кодом Monero. В конце статьи приводятся соответствующие ссылки.

Обзор

CryptoNight пытается сделать доступ к памяти «узким местом», ограничивающим производительность («ограничение по памяти»). Цель достигается в три этапа:

  1. Инициализация большой области памяти при помощи псевдослучайных данных. Этот вид памяти известен как блокнотная память.
  2. Выполнения множества операций чтения/записи по псевдослучайным (но детерминированным) адресам блокнотной памяти.
  3. Хеширование всей блокнотной памяти для получения итогового значения.

Этап 1. Инициализация блокнотной памяти

Сначала входные данные хешируются при помощи Keccak-1600. В результате получаются 200 байт псевдослучайных данных (1600 бит = 200 байт).

Эти 200 байт становятся начальным числом, на основе которого при помощи 256-AES шифрования генерируется больший буфер псевдослучайных данных размером 2 Мб.

Первые 0..31 байт хеша Keccak-1600 используются в качестве ключа AES.

128 байт полезной информации шифруются до тех пор, пока не будет достигнут размер, составляющий 2 Мб. Первой полезной информацией являются байты 66..191 хеша Keccak-1600. Следующей полезной информацией являются результаты шифрования предшествующей полезной информации.

Каждые 128 байт полезной информации шифруются 10 раз.

Более подробно со всеми нюансами проблема описана в разделе «Инициализация блокнотной памяти» Стандарта CryptoNote.

Этап 2. Цикл с жёстким использованием памяти

Второй этап предполагает 524 288 итераций простого stateful-алгоритма.

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

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

Среди прочих есть такие специфические операции, как AES, XOR, 8byte_mul, 8byte_add, которые отлично подходят для CPU (то есть они предельно оптимизированы для использования с современными CPU).

В данном случае цель состоит в том, чтобы сделать время ожидания памяти «узким местом», позволяющим свести на нет разницу между потенциальным использованием схем ASIC и CPU общего назначения.

Этап 3. Хеширование

На последнем этапе (этапе упрощения) происходит следующее:

  • результат применения оригинального хеша Keccak-1600 объединяется со всей блокнотной памятью;
  • берётся алгоритм хеширования, основанный на 2 битах низкого порядка:
    • 0=BLAKE-256
    • 1=Groestl-256
    • 2=JH-256
    • 3=Skein-256
  • результат хешируется при помощи выбранной функции.

Полученный 256-битный хеш является окончательным результатом использования алгоритма CryptoNight.

Специфичные для Monero модификации

CryptoNight v0

Так сообщество Monero называет оригинальную версию алгоритма CryptoNight.

CryptoNight v1

См. отличие от исходного кода.

CryptoNight v2

См. обоснование и отличие от исходного кода.

CryptoNight v3 aka CryptoNightR

См. обоснование и отличие от исходного кода.

Критика

  • Хеш CryptoNight относительно сложен для верификации. Это создаёт риск с точки зрения возможности проведения DoS атаки на узлы с использованием недействительных доказательств процесса. См. требование к строгой асимметрии.
  • Хеш-функция была разработана с нуля и прошла ограниченный независимый анализ. Несмотря на то, что CryptoNight состоит из доказавших свою надёжность и прошедших независимый анализ примитивов, но объединение безопасных примитивов вовсе не означает создания безопасной криптосистемы.
  • В конечном счёте CryptoNight не обеспечил должного уровня противодействия ASIC.
  • Сложность CryptoNight сводит на нет его конкурентоспособность относительно производства ASIC.

Доказательство работы CryptoNight остаётся одним из самых противоречивых аспектов Monero.

Ссылки