[Перевод] Краткая история эволюции proof-of-work в криптовалютах. Часть 2
Предлагаю вашему вниманию перевод статьи «The Proof-of-Work in Cryptocurrencies: Brief History. Part 2» Рэя Паттерсона (Ray Patterson) с сайта Bytecoin.org.
«Краткая история эволюции proof-of-work в криптовалютах. Часть 1» находится тут.
Скрещивание
К середине лета 2013 года в строю уже находилось больше сотни альткоинов, причем почти половина появилась именно за последние пару месяцев. Стоит ли говорить, что почти все «новички» были форками Litecoin и использовали scrypt? Другим трендом сезона стал новомодный Proof-of-Stake от PPcoin, так что комбинацию scrypt+PoS можно было назвать «стандартным набором начинающего алькоинера».
Такая (количественная) популярность scrypt и начало экспоненциального роста сложности Bitcoin привели к простой мысли: scrypt-ASIC«и появятся в ту же секунду, как только это станет выгодно. И хотя гигантский ноябрьский пузырь — когда Bitcoin дошел до $1200 — еще не начал даже надуваться, поиски новой PoW функции начались снова.
Как можно разнообразить стандартную хэш-функцию? Например… другой стандартной хэш-функцией! Sifcoin первым предложил идею последовательно хэширования несколькими популярными функциями, на роль которых были взяты финалисты конкурса SHA3: Blake, BMW, Groestl, JH, Keccak, Skein. Идея довольно простая: шесть принципиально разных алгоритмов — это шесть разных чипов ASIC, то есть (на первый взгляд) много и дорого. Кроме того, если для какого-то алгоритма найдут черный ход (не обязательно сломают целиком, а научатся быстрее решать задачу «много нулей в начале»), то вся схема еще будет более-менее держаться.
Не всегда первопроходцам достаются все лавры: в итоге этот six-hash алгоритм получил популярность (и имя) в первом форке Sifcoin — валюте Quark. Вывод: не давайте своим продуктам префикс «сиф». От Кварка со временем отпочковалось еще десятка два альткоинов, один из сильно превзошел «папу» по популярности: это Darkcoin (сейчас называется DASH). Новый PoW в нем носил название X11 и отличался, как можно догадаться, числом применяемых хэш-функций. Принципиально ничего нового он не давал (кроме порядка раундов), и потому распространенность X11 (примерно на втором месте после scrypt) стоит связать скорее с успехом самого DarkCoin, в котором было много всяких других изменений (в чем-то толковых, в чем-то не очень).
X11 появился в начале 2014 года и первое время работал исключительно на CPU, чем всех очень радовал. Но в апреле сложность DarkCoin подскочила в два раза, что вызвало обоснованные подзрения в появлении GPU-майнера. Поскольку никто не признавался, то был объявлен конкурс на открытую реализацию такого ПО, собраны деньги — и через месяц хэшрейт уже вырос на порядок на новом GPU-майнере. Он оказался эффективнее CPU примерно в 5 раз (scrypt — в 10).
На текущий день есть много вариаций на тему X11 и Quark; некоторые даже имеют свои уникальные и неповторимые названия: X14, X15… При этом всем, в целом, понятно, что алгоритм совсем не является ASIC-resistant в полном смысле слова. Посчитать 11 разных хэшей вместо одного — это, грубо говоря, сделать конвеер в 11 раз длиннее. Иными словами, ценовой порог окупаемости разработки железки все лишь отодвинулся в несколько раз.
Еще благодаря различным маркетинговым приемам отдельные SHA-3 финалисты стали популярны в соло-варианте. Например, сам Keccak, он же SHA-3 собственной персоной. Ну, здесь все понятно: «как SHA-2, только лучше!». То есть особой идеи противостояния ASIC«ам не было, кроме той, что для разработки и начала производства нужен как минимум год. Зато, с другой стороны: имеем самый настоящий свежий современный стандарт! Также, появилась даже специальная монетка Skeincon, которая использовала, как видно, алгоритм Skein (наверное, фанаты Брюса Шнайера).
Многообразие видов
Эволюция сделала виток, и мысли криптовалютчиков снова вернулись к memory-bound алгоритмам. Взять, например, scrypt: хороший же алгоритм, просто параметры плохие подобрали!
Скорее всего, какая-то работа мысли все же была проведена, поскольку криптовалют с просто другими, статическими параметрами scrypt не появилось. Зато идея с динамическим объемом памяти была реализована аж сразу в двух вариантах:
- Scrypt-N. Напомним три параметра scrypt, которые были выбраны в Tenebrix и прочих Litecoin: N=1024, r=1, p=1. Последний отвечает за возможность распараллеливания, это нам не нужно. N и r увеличивают требуемый объем памяти, причем r так же увеличивает и количество вызовов функции перемешивания Salsa20, т.е. имеет бОльший коэффициент «CPU/memory cost», чем N. В связи с этим было решено периодически увеличивать N в два раза, заставляя алгоритм использовать просто больше памяти. Так, при запуске, Vertcoin [9] требует 512Кб (N=4096), через год аппетиты возрастут до 1024Кб и т.д. Переписать GPU-майнер, по словам создателей, это пустяки, а вот делать новый ASIC каждый год уже никто не будет.
- Scrypt-jane. Идея с увеличением N вс е та же, однако процесс идет не по конкретному расписанию, а регулируется псевдослучайной формулой, нелинейно зависящей от текущего времени. И хотя N монотонно возрастает (ладно-ладно, «не убывает»), периоды между пересчетами представляют собой скорее расходящийся ряд (6,3,,3,9,3,24,12,36…). Помимо этого, scrypt-jane использует внутри несколько перемешивающих (Salsa20/8, ChaCha20/8 и Salsa6420/8) и хэш- функций (SHA2, BLAKE, Skein, Keccak).
Еще одной, принципиально другой memory-bound PoW функцией стал Momentum, реализованный в BitShares. Он очень простой:
- Допустим, мы хотим подписать данные D. Сначала получим H = Hash (D), где Hash () — это некоторая криптографическая хэш-функция
- Найдем такие различные значения A и B, что BirthdayHash (A + H) = BirthdayHash (B + H), где BirthdayHash () — это memory-bound функция, как scrypt.
- Теперь, если Hash (H + A + B) < TargetDifficulty (читай – начинается с n нулей), то все, победа. Иначе –возращаемся на шаг 2.
Как видно, основная работа приходится на поиск коллизий двух хэшей на шаге 2. Размеется, там нужно найти не 256 совпадающих бит, а меньше, однако и это является сложной задачей. Скажем, если нужно найти совпадение 64 первых бит, это потребует 2^64 операций хэширования… Или нет?
На помощь к нам приходит супергерой: парадокс дней рождения. Суть его в том, что вероятность найти коллизию среди некоторого множества квадратично растет с числом элементов (потому что так растет и число уникальных пар среди множества). На практике же это дает нам такую оценку: чтобы найти ЛЮБУЮ 64-битную коллизию с вероятностью 50%, нужно сгенерировать порядка 2^32 хэшей (4 миллиона вместо 18 квинтиллионов — вот такая экономия).
Почему так не работает с «обычным» PoW, ведь там тоже по сути идет поиск коллизий? Ключевое слово здесь — «любая» коллизия. В Bitcoin нужно найти совпадение с конкретным образцом: N нулей в начале, а в Momentum должны совпасть N любых первых бит.
Налицо очевидный компромисс «время» — «память». По замыслу создателя, алгоритм должен использовать около 2Гб памяти на один поток, т.е. обычный компьютер сможет выполнять даже несколько параллельных поисков. При этом уделом ASIC«ов, сила которых отнюдь не в памяти, остается только смотреть и завидовать (ну или быть в квадрат быстрее).
Есть у такого подхода и один недостаток. Все предыдущие proof-of-work алгоритмы работали «мгновенно»; в том смысле, что по сути реализовывали перебор, и каждая попытка занимала фиксированное время и все они имели одинаковые шнасы на успех. Каждый проверенный хэш — это как бросок кубика с 2ˆ256 гранями, причем в любой момент можно было «взять другой кубик» (начать работу над другим блоком) и шансы бы не изменились. Что это значит для майнера? Это значит, что если ему приходит новая транзакция, которую он хочет включить в блок, то ему придется обновить хэшируемую структуру («взять другой кубик»). Это занимает доли секунды, так что можно сказать, что потери пренебрежимо малы. В случае же Momentum все не так просто. Очередная итерация хэширования и добавления нового хэша в глобальную 2 гб таблицу имеет бОльшие шансы на успех, чем предыдущая! Ясно, что тогда обновлять заголовок блока и начинать построение таблицы с нуля сильно невыгодно. Если с каждым броском кубика шансы найти решение все увеличиваются, то выгоднее НЕ брать новый кубик. То есть в конечном итоге майнеру Momentum невыгодно принимать новые транзакции и «сбрасывать» свой прогресс: и в итоге в блок будут попадать те транзакции, что были присланы ДО начала работы с этим блоком. Для Битокина это бы означало, что среднее время подтверждения транзакции увеличилось бы с 10 минут до 20.
Полезные ископаемые
Особняком стоит одна-единственная PoW функция, которая появилась летом 2013 года. Прежде чем перейти к ней, давайте осознаем одну проблему вообще с proof-of-work. Сразу оговорюсь, что кому-то это вполне может и не показаться проблемой (а даже наоборот), т.е. речь пойдет о том, что многие люди считают проблемой.
Вся эта работа — бесполезна! Нигде, кроме как внутри криптовалюты, никому эти хэши не нужны. Можно, конечно, распечатать и повесить на стену самые маленькие из найденных хэшей, но практической пользы в них нет. Мы не будем сейчас вдаваться в философские рассуждения о том, должна ли эта работа вообще быть полезной или нет, но просто отметим тот факт, что придумать PoW функцию, которая приносила бы пользу — задача нетривиальная.
Однако таковая нашлась. Разработчик SunnyKing (он же придумал [или, по крайней мере, первым реализовал] схему Proof-of-stake) представил публике следующую схему: доказательством проделанной работы является найденная цепочка простых чисел, удовлетворящих некоторым свойствам. Точнее, это должна быть последовательность Каннингема первого или второго рода или их комбинация (т.н. bi-twin primes).
Спервая о том, почему это полезно. Данные простые числа, разумеется, не маленькие (иначе бы их искать было довольно легко): порядка сотен цифр в десятичной записи. Однако для шифрования RSA этого все же маловато, да использовать там нужно случайные числа. Цепочки Каннингема представляют собой скорее любытную математическую структуру, которая (в теории) может приоткрыть очередную завесу в теории чисел. В конце концов, до появления криптографии с открытым ключом вся эта область считалась лишь «красивой, бесполезной наукой», поэтому любые усилия, пусть даже и такого «олимпиадного» характера, считаются небесполезными.
Теперь о том, как именно можно связать простые числа с криптовалютными блоками. Допустим, наша цепочка начинается с некоторого числа P. Хэш заголовка блока (в котором перебирается поле nonce) интерпретируется как целое число. И это число должно быть делителем P-1 или P+1. Сложность сети — это длина требуемой цепочки простых чисел (она колеблется от 7 до 11). Вот, в общем-то и вся идея. Таким образом, нельзя (т.е. очень сложно) использовать случайно найденную цепочку (или вообще чужую, от другого блока) для доказательства работы над своим заголовком.
Недостатков можно отметить два: во-первых, нам неизвестно, есть ли более простой способ решения задачи Primecoin (так и называется эта криптовалюта). С хешами все более-менее понятно: атака нахождения прообраза криптографической хэш-функции — дело практически безнадежное (по крайней мере, на этом предположении стоят все криптографические столпы — и не дай бог оно рухнет!), поэтому для имеющегося хэша вероятность подобрать блок нулевая. Но сказать то же самое про блок Primecoin (где нам подходят все множители P-1 или P+1) уже сложно.
Во-вторых, сложность майнинга. Как уже было сказано, она пропорциональна длине цепочки. Однако длина — число целое и не учитывает изменение дробной части. Таким образом, изменение сложности с 9.0 до 9.99 бует совершенно незаметно, а вот с 9.99 до 10 уже резко повлияет на общий хэшрейт и скорость появления новых блоков.
Кроме того, данная функция, очевидно, использует только CPU-мощности компьютера, никакой памяти. Довольно долго у нее не было GPU-майнера, но когда он появился, стало понятно, что никаким anti-ASIC граалем Primecoin не является. Воможно, именно поэтому он остался в своей нише с парой форков, и его PoW функция не стала популярной.
PoWer Sapience
И наконец, рассмотрим совсем другую одну ветвь филогенетического дерева PoW для криптовалют: CryptoNight и CuckooCycle, которая начала развивалась параллельно остальным сразу после провала scrypt, как CPU-only алгоритма.
CryptoNight — это название хэш-функции в коде CryptoNote (не запутайтесь!), который включает в себя много других отличий с Bitcoin (начиная с того, что это вообще не форк — хотя сейчас этим уже никого не удивишь). Криптовалюты CryptoNote как таковой нет, зато есть несколько, построенных на этой технологии: Bytecoin, Monero, DigitalNote и т.д… У каждой если свои отличия, но PoW функция у всех общая.
CryptoNight использует общую идею scrypt о «большой таблице данных, в которой делаются случайные запросы». Однако создателями был отмечен недостаток, связанный с линейным компромиссом «время»-«память». В scrypt основной (второй) слой создает каждый новый блок данных на основе предыдущего. Таким образом, если мы будем хранить, например, только каждый второй блок из N, то в 50% случаев нам придется пересчитывать его заново. Всего таких случайных обращений к массиву тоже N, поэтому получается, что сэкономив половину памяти, мы вычислим N + 1/2N = 150% блоков, то есть лишь в полтора раза больше. Аналогично, сохраняя лишь каждый третий блок, мы в 33% случаев этого не заметим, в 33% — перевычислим один лишний блок, в 33% — два лишних. То есть всего работы: N + 1/3N + ⅓ *2N = 2N = 200%. Итого, как было посчитано, сохранение лишь 1/s от всех данных увеличивает общий объем работы лишь в (s-1)/2 раз (возможно, кстати, что именно так и работают scrypt-ASIC«и).
В связи с этим у CryptoNight принципиальных отличий три:
- Очередной блок является высчитывается на основе ВСЕХ предыдущих. Таким образом, выкидывание, скажем, каждого второго блока приведет к тому, что для восстановления пропуска пересчитывать придется не один блок, а сразу все предыдущие.
- Обращения к массиву данных являются не только чтением, но и записью. Так, получается, у каждого элемента появляется «второе измерение» — время; и пересчитывание становится еще более трудоемким.
- Наконец, общее число обращений к массиву гораздо больше числа элементов самого массива (2^20 против 2^15), то есть итоговый массив преображается до неузнаваемости к концу цикла.
Кроме того, внутри используются 64-битные операции (умножение, сложение) и шифрование AES в качестве функции перемешивания. Это — реверанс в сторону современных процессоров со встроенными соответствующими инструкциями (и камень в огород GPU). Общий объем памяти, требуемый CryptoNight, — 2 Мб, т.е. примерно размер L3-кэша на ядро. Не сказать, что это недостижимая высота для ASIC, но все же планка себестоимости довольно высока.
В целом, можно охарактеризовать CryptoNight как очень эффективный практический алгоритм: GPU майнер для него, конечно, есть, но серьезное преимущество он имеет только по сравнению со старыми процессорами (32 бита или малый кэш). Насколько можно судить, все его детали нацелены именно на практическую эффективность обычных компьютером (которых миллиарды).
CuckooCycle — это, можно, сказать, полная противоположность. Во-первых, он имеет теоретико-информационную базу. Не в том смысле, что он разработан только в теории (на данный момент нет таких криптовалют), а в том, что его надежность основана на сложности решения теоретико-информационной задачи: поиск циклов в двудольном графе. В принципе, вся современная криптография с открытым ключом устроена так же.
Основная идея (если не вдаваться в саму теорию графов) такая же, как и в Momentum — за счет использования некоторого объема памяти мы получаем оптимальный алгоритм решения этой задачи. Вычислительные операции сведены к минимуму, поэтому основное время занимает именно обращения к этой памяти. Причем проверка решения, разумеется, выполняется гораздо быстрее.
Главный вопрос, который можно задать:, а является ли описанный алгоритм действительно оптимальным? Не появится ли завтра какая-нибудь хитрая CS-статья с другим, более эффективным решением, которое не использует много памяти? В принципе, это главное, что отличает CuckooCycle и CryptoNight.
