Cuckoo Cycle¶

Cuckoo Cycle — это алгоритм доказательства выполнения работы (Proof-of-Work, PoW), предназначенный для использования в криптовалютах. Алгоритм был разработан Джоном Тромпом (John Tromp) в 2014 году и опубликован в 2015 году. Основная цель Cuckoo Cycle — создать PoW-алгоритм, который был бы устойчив к специализированному оборудованию (ASIC) и «дружелюбен» к обычным персональным компьютерам, однако на практике он также нашёл применение в ряде криптовалют, включая те, что ориентированы на графические процессоры (GPU).

¶Принцип работы

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

Особенность Cuckoo Cycle заключается в том, что задача поиска цикла в разреженном графе требует значительного объёма оперативной памяти. Это делает алгоритм «memory-hard» (требовательным к памяти), что теоретически должно препятствовать созданию эффективных ASIC-майнеров, так как стоимость памяти сложнее оптимизировать, чем вычислительные блоки. В отличие от алгоритмов, ориентированных на вычисления (например, SHA-256), Cuckoo Cycle опирается на скорость доступа к памяти и её объём.

¶История и развитие

Первая реализация алгоритма была представлена Тромпом в 2015 году. Изначально он предложил две версии: Cuckoo Cycle (с использованием битового графа) и Cuckoo Hash. Впоследствии появились модификации, такие как Cuckoo-RFC, Cuckaroo (вариант с уменьшенным размером графа для ускорения проверки) и Cuckatoo (увеличенный размер графа для повышения ASIC-устойчивости).

Cuckoo Cycle стал основой для нескольких криптовалютных проектов. Наиболее известным является Grin — криптовалюта, запущенная в январе 2019 года, которая использует модификацию Cuckoo Cycle под названием Cuckatoo. Также алгоритм применялся в проектах Monero (в ранних версиях) и Aeternity.

¶Варианты алгоритма

• Cuckoo Cycle (базовый): длина цикла 42, граф размером 2^N (обычно 2^30 или 2^32). Требует от 1 до 8 ГБ памяти.
• Cuckaroo: вариант с меньшим графом (например, 2^28), что позволяет быстрее проверять решения и снижает требования к памяти. Используется в Grin для «лёгких» майнеров.
• Cuckatoo: увеличенный граф (2^31 и более), требующий больше памяти (от 8 ГБ). Используется в Grin для «тяжёлых» майнеров.

¶Применение в криптовалютах

¶Grin

Grin — это конфиденциальная криптовалюта, использующая протокол MimbleWimble. Она применяет Cuckatoo для основного майнинга и Cuckaroo для поддержки GPU-майнеров. Запуск сети состоялся 15 января 2019 года. Алгоритм позволил Grin стартовать без крупных инвесторов и предварительной продажи монет, так как майнинг был доступен на обычном оборудовании.

¶Aeternity

Платформа смарт-контрактов Aeternity использовала Cuckoo Cycle в своей основной сети, запущенной в 2018 году. Однако позже проект частично перешёл на другие механизмы консенсуса.

¶Другие проекты

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

¶Критика и ограничения

Несмотря на заявленную ASIC-устойчивость, Cuckoo Cycle не смог полностью избежать появления специализированного оборудования. Для варианта Cuckatoo были разработаны ASIC-майнеры (например, от компании GMO), что вызвало критику со стороны сообщества, ориентированного на децентрализацию. В ответ разработчики Grin ввели периодические обновления алгоритма (так называемые «форки»), чтобы усложнить работу ASIC.

Кроме того, алгоритм критикуется за высокий порог входа для обычных пользователей: для эффективного майнинга Cuckatoo требуется от 8 ГБ видеопамяти, что доступно не всем. Это привело к централизации майнинга в пулах и снижению децентрализации сети.

¶Интересные особенности

• Название алгоритма происходит от английского слова «cuckoo» (кукушка), что отсылает к методу хеширования с вытеснением (cuckoo hashing), который используется для построения графа.
• Проверка решения в Cuckoo Cycle выполняется очень быстро — она занимает миллисекунды, что делает алгоритм удобным для верификации транзакций.
• Алгоритм является одним из немногих PoW, где основная нагрузка ложится не на вычисления, а на операции с памятью.

¶Источники

• John Tromp. «Cuckoo Cycle: a memory bound proof-of-work system» (2015).
• Официальная документация проекта Grin (github.com/mimblewimble/grin).
• Статья «Cuckoo Cycle» в Bitcoin Wiki.