Ergo и механизм консенсуса Autolykos: Часть II

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

В качестве напоминания, вот псевдокоды для майнинга блоков и хеш-функции.

Псевдокод майнинга блоков Autolykos

Хеш-функция на основе Blake2b256

Строки 3, 4 – начало цикла while и угадывание

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

Строки 5, 6 – семя для генерации индексов

Строка 5, i = takeRight(8, H(m||nonce)) mod N, производит целое число в [0,N). Используется Алгоритм 3, но с m и nonce в качестве входных данных. Как только хеш H(m||nonce) возвращается, 8 наименее значащих байтов сохраняются и затем передаются через mod N. К слову, максимальное возможное целое значение с 8 байтами равно 2⁶⁴ – 1, и предполагая, что N = 2²⁶, 8-байтовый хеш mod N приведет к тому, что первые несколько цифр будут нулями. Количество нулей в i уменьшается по мере роста N.

Строка 6 производит e, семя для генерации индексов. Алгоритм 3 вызывается с входными данными i (сгенерированным в строке 5), h и M. Затем наибольший значащий байт числового хеша отбрасывается, а оставшиеся 31 байт сохраняются как значение e. Также следует отметить, что значение e можно получить из списка R вместо вычисления, так как e является значением r.

Строка 7 – генератор индексов

Индекс элемента J создается с использованием Алгоритма 6 с входными данными e, m, и nonce. Функция genIndexes является псевдослучайной и возвращает список k (=32) чисел в [0,N).

Функция genIndexes

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

GenIndexes(e||m||nonce)...

hash = Blake2b256(e||m||nonce) = [0xF963BAA1C0E8BF86, 0x317C0AFBA91C1F23, 0x56EC115FD3E46D89, 0x9817644ECA58EBFB]

hash64to32 = [0xC0E8BF86, 0xF963BAA1, 0xA91C1F23, 0x317C0AFB, 0xD3E46D89 0x56EC115F, 0xCA58EBFB, 0x9817644E]

extendedhash (т.е. байтсвоп и конкатенация 4 байтов, повторяя первые 4 байта) = [0x86BFE8C0, 0xA1BA63F9, 0x231F1CA9, 0xFB0A7C31, 0x896DE4D3, 0x5F11EC56, 0xFBEB58CA, 0x4E641798, 0x86BFE8C0]

Следующий код на python показывает процесс нарезки расширенного хеша, возвращая k индексов. В этом примере мы предполагаем, что h < 614,400, таким образом, N = 2²⁶ (67,108,864).

Нарезка и mod N[1]
for i in range(8):
idxs[i << 2] = r[i] % np.uint32(ItemCount)
idxs[(i << 2) + 1] = ((r[i] << np.uint32(8)) | (r[i + 1] >> np.uint32(24))) % np.uint32(ItemCount)
idxs[(i << 2) + 2] = ((r[i] << np.uint32(16)) | (r[i + 1] >> np.uint32(16))) % np.uint32(ItemCount)
idxs[(i << 2) + 3] = ((r[i] << np.uint32(24)) | (r[i + 1] >> np.uint32(8))) % np.uint32(ItemCount)

Основной вывод заключается в том, что нарезка возвращает k индексов, которые являются псевдослучайными значениями, полученными из семени, т.е. e, m, и nonce.

return [0x2BFE8C0, 0x3E8C0A1, 0xC0A1BA, 0xA1BA63, 0x1BA63F9, 0x263F923, 0x3F9231F, 0x1231F1C, 0x31F1CA9, 0x31CA9FB, 0xA9FB0A, 0x1FB0A7C, 0x30A7C31, 0x27C3189, 0x31896D, 0x1896DE4, 0x16DE4D3, 0x1E4D35F, 0xD35F11, 0x35F11EC, 0x311EC56, 0x1EC56FB, 0x56FBEB, 0x2FBEB58, 0x3EB58CA, 0x358CA4E, 0xCA4E64, 0x24E6417, 0x2641798, 0x179886, 0x39886BF, 0x86BFE8]

Этот индекс можно перевести в значения в десятичной системе, так как он относится к числам в [0, N). Например, 0x2BFE8C0 = 46131392, 0x3E8C0A1 = 65585313, 0xC0A1BA = 12624314 и так далее. Майнер использует эти индексы для получения k r значений.

Функция genIndexes предотвращает оптимизации, так как крайне сложно, по сути невозможно, найти семя, такое что genIndexes(seed) возвращает желаемые индексы.

Строка 8 – сумма r элементов, заданных k

Используя индекс, сгенерированный в строке 7, майнер извлекает соответствующие k (=32) r значения из списка R и суммирует эти значения. Это может показаться запутанным, но давайте разберем это.

Продолжая приведенный выше пример, майнер хранит следующие индексы:

{0 | 46,131,392},
{1 | 65,585,313},
{2 | 12,624,314},
{3 | 10,599,011},
…
{31 | 8,830,952}

Учитывая приведенные выше индексы, майнер извлекает следующие r значения из списка R, хранящегося в памяти.

{0 | 46,131,392} → dropMsb(H(46,131,392||h||M))
{1 | 65,585,313} → dropMsb(H(65,585,313||h||M))
{2 | 12,624,314} → dropMsb(H(12,624,314||h||M))
{3 | 10,599,011} → dropMsb(H(10,599,011||h||M))
…
{31 | 8,830,952} → dropMsb(H(8,830,952||h||M))

Обратите внимание, что Takeright(31) примененный к 32-байтовому хешу также можно записать как dropMsb – отбросить наибольший значащий байт.

Поскольку майнер уже хранит список R в ОЗУ, ему не нужно вычислять k (= 32) функций Blake2b256 и вместо этого он ищет значения. Это ключевая особенность устойчивости к ASIC. ASIC с ограниченной памятью должен вычислять 32 итерации Blake2b256, чтобы получить значения, которые могли бы быть извлечены из памяти, а извлечение из памяти занимает гораздо меньше времени. Не говоря уже о том, что ASIC с ограниченной памятью потребует 32 экземпляра Blake2b256 физически на кристалле, чтобы достичь одного хеша за цикл, что потребует больше площади и более высоких затрат. Легко доказать, что хранение списка R в памяти стоит того. Предположим следующее: GPU имеет хеш-скорость G = 100MH/s, _N = 2²⁶, k = 32, интервал блока t = 120 секунд, и элементы извлекаются каждые 4 хеша. Я предпочитаю предполагать, что элементы извлекаются каждые 4 хеша, потому что для каждой попытки nonce требуется несколько элементов, таких как i, J, и H(f), которые требуют экземпляров Алгоритма 3, т.е. хешей blake2b. Мы можем оценить, что каждое r значение будет использоваться в среднем, (G * k * t)/(N*4) = 1430.51 раз.

Как только 32 r значения извлечены, они суммируются.

Строки 9, 10, 11, 12 – проверьте, если хеш суммы ниже целевого

Сумма 32 r значений хешируется с использованием Алгоритма 3, и если выход ниже целевого b, PoW успешен, m и nonce возвращаются к узлам сети, и майнер получает вознаграждение в ERG. Если хеш суммы выше целевого, Строки 4 – 11 повторяются с новым nonce.

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

Устойчивость к ASIC

Мы знаем из Ethereum, что «память жесткие» алгоритмы могут быть преодолены путем интеграции памяти на ASIC. Ergo отличается, но давайте сначала рассмотрим, почему ASIC с ограниченной памятью неконкурентоспособен и почему майнеру необходимо хранить список R. Строка 8 майнинга блоков Autolykos отпугивает машины с ограниченной памятью. Если ASIC-майнер не хранит список R, ему требуется много ядер для генерации 31-байтовых числовых хешей на лету. 32 r значения не могут быть эффективно рассчитаны с использованием одного цикла ядра, потому что выход будет генерироваться только каждые 32-й цикл хеша. Учитывая J, для вычисления одного nonce за цикл хеша, необходимо как минимум 32 экземпляра Blake2b256, работающих dropMsb(H(j||h||M)). Как мы упоминали выше, это значительно увеличивает размер кристалла и стоимость. Ясно, что хранение списка R стоит того, потому что иметь 32, или даже 16, ядер очень дорого. Более того, чтение памяти быстрее, чем вычисление экземпляров Blake каждый раз, когда тестируется nonce.

Давайте посмотрим, конкурентоспособен ли ASIC с достаточной памятью, потому что это более актуально для обсуждения. Сравнивая Ethash и Autolykos, разница в том, что Ethash включает N элементов при хешировании nonce и заголовок перемешивается 64 раза, в то время как Autolykos включает N элементов при извлечении 32 r значений на основе сгенерированных индексов. Для каждого протестированного nonce Autolykos запускает около 4 экземпляров Blake2b256 и 32 извлечения из памяти, в то время как Ethash запускает около 65 экземпляров SHA-3 и 64 извлечения из памяти. Не говоря уже о том, что k в настоящее время установлен на 32, но это значение может быть увеличено для получения большего количества r значений, если это необходимо. ASIC, работающие с Ethash, имеют много возможностей для увеличения скорости хеширования SHA3, поскольку 65 хешей завершаются на каждый протестированный nonce по сравнению с примерно 4 на Autolykos. Соотношение извлечений из памяти к экземплярам хеширования значительно больше на Autolykos. По этой причине Autolykos более жесткий к памяти, чем Ethash, поскольку пропускная способность памяти играет гораздо более важную роль по сравнению со скоростью хеширования.

Область, где можно оптимизировать Autolykos, это заполнение списка R. Заполнение списка R требует N экземпляров функции Blake2b256. N велико и только увеличивается, так что это много хеширования. ASIC может оптимизировать скорость Blake2b256, что даст больше времени для майнинга блоков, так как список R будет заполнен быстрее. Хотя это можно сделать, заполнение списка R требует циклического прохода по [0, N) и GPU с 32-широкими мультипроцессорами уже может заполнить список R очень быстро (за секунды). Потребуется ASIC с множеством ядер Blake, чтобы быть значительно быстрее – снова, очень дорого, и, вероятно, не стоит того, поскольку узким местом может стать пропускная способность записи памяти (т.е. запись списка R в ОЗУ, а не скорость хеширования).

Последняя область, которую можно оптимизировать для Autolykos, это скорость чтения/записи памяти. ASIC-майнеры Ethash имеют немного более высокую скорость чтения по сравнению с GPU, так как память работает на более высокой частоте без эффекта троттлинга GPU. Однако эта разница довольно незначительна и ожидается, что станет еще менее значительной по мере развития GPU. Это связано с тем, что аппаратное обеспечение памяти само по себе одинаковое: DRAM. Можно задаться вопросом, можно ли использовать более быстрое аппаратное обеспечение памяти, при котором скорость чтения и записи памяти гораздо быстрее… SRAM, например, может быть воображаемым следующим шагом в преодолении алгоритмов, жестких к памяти, однако SRAM не является жизнеспособным решением просто потому, что он менее плотный.

SRAM на FPGA[2]

На фото выше изображен FPGA с 8 чипами памяти спереди, и еще 8 сзади. Общая память SRAM составляет всего 576 МБ. Установить достаточное количество SRAM на кристалле не получится, потому что SRAM нужно будет разместить дальше от ядра, так как он недостаточно плотный, чтобы поместиться в один слой вокруг ядра. Это может привести к задержкам чтения/записи, потому что электричеству нужно будет проходить более длинные расстояния, даже если само оборудование быстрее. Кроме того, для майнинга Ergo требования к памяти увеличиваются по мере роста N, поэтому установка достаточного количества SRAM не является жизнеспособной со временем. Таким образом, ASIC на основе SRAM не стоит изучать, даже если у кого-то есть достаточно денег, чтобы потратить на сам SRAM.

Blake2b256

Одно из основных отличий между алгоритмом, таким как Autolykos, и другими является использование Blake2b256. Это не случайность. Blake сильно полагается на операции сложения для смешивания хешей вместо операций XOR. Операция, такая как XOR, может выполняться бит за битом, в то время как сложение требует переносных битов. Таким образом, Blake требует больше энергии и площади ядра по сравнению с алгоритмами SHA, но он по-прежнему так же безопасен и, на самом деле, быстрее. Как упоминается на сайте Blake2, "BLAKE2 быстр в программном обеспечении, потому что использует возможности современных ЦП, а именно параллелизм на уровне инструкций, расширения набора инструкций SIMD и несколько ядер."[3] Таким образом, хотя ASIC может выводить экземпляры Blake быстрее, врожденная природа функции ограничивает оптимизации, требуя сложения и вовлекая функции, найденные как в ЦП, так и в GPU.

Скорость Blake2b относительно других хеш-функций

Заключение

Autolykos является отличной инновацией, которая является необходимым ответом на борьбу с ростом оптимизированных для PoW ASIC машин. Мы надеемся, что эта двухчастная серия помогла вам понять Autolykos на более техническом уровне и почему он более жесткий к памяти, чем Ethash. Поскольку Ethereum переходит на сеть PoS, будет большая община майнеров, ищущих место для направления своей хешрейтовой мощности, и Ergo должен стать значительным игроком в привлечении этих майнеров.

Если вам понравилась эта статья, автор приглашает вас ознакомиться с дополнительным контентом через их аккаунт в Twitter, @TheMiningApple.

[1] Кредит Wolf9466#9466 на Discord
[2] http://www.ldatech.com/_images/imageGallery/SBM09P-3_front.jpg
[3] https://www.blake2.net/#:~:text=A%3A%20BLAKE2%20is%20fast%20in,of%20the%20designers%20of%20BLAKE2).