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

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

Часть I

Autolykos, механизм консенсуса Ergo, является одним из немногих асимметричных, трудоемких, доказательств работы, которые все еще устойчивы к ASIC - тем самым обеспечивая, что блокчейн остается максимально децентрализованным. Autolykos основан на статье Equihash[1] и задаче о дне рождения. Вкратце, майнеру ставится задача найти k (=32) из N элементов, так что хэш суммы элементов меньше целевого значения. Следующий псевдокод объясняет процесс майнинга, и этот анализ будет подробно разбирать каждую строку, поскольку в Интернете очень мало ресурсов, которые объясняют Autolykos в полном объеме.

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

Перед обсуждением процедуры майнинга блоков алгоритм сначала требует очень большой циклической группы G простого порядка q с фиксированным генератором g и единичным элементом e. Эта простая группа используется для возврата целых чисел в Z/qZ во время хеширующей функции на основе Blake2b256.

Пример циклической группы с генератором z, единичным элементом 1, порядком 6[2]

Мы не будем подробно останавливаться на циклической группе, так как она охватывает лишь небольшой сегмент схемы PoW. Теперь давайте разберем майнинг блоков Autolykos строка за строкой.

Строка 1 – Входные данные h и m

PoW начинается с двух входных данных: высоты блока h и хэша заголовка предстоящего блока m. Хэш заголовка блока - это хэш компонентов заголовка блока, таких как хэш заголовка предыдущего блока, корень Меркла, nonce и т.д.

Строка 2 – Рассчитать список R

Во-первых, важно заметить обозначение H() в строке 2. Это обозначение вызывает хеширующую функцию Алгоритм 3. Алгоритм 3 - это хеш-функция на основе Blake2b256, и она используется на протяжении всего Autolykos. Алгоритм 3 утверждает, что если хэш Blake входных данных ниже 2²⁵⁶ (= 16⁶⁴ = 0xFFFFFFFFFFFF86633A9E8F1256D61ED5325EBF2A4B4366BA0000000000000000), то возвращается hash.mod(q). Если нет, Алгоритм 3 повторяется, пока не достигнет числового хэша в допустимом диапазоне. Для справки, обратите внимание, что q - это простой порядок группы G, выходы хэша Blake2b256 составляют 256 бит, 64 цифры в длину, и Алгоритм 3 всегда будет возвращать числовой хэш в Z/qZ.

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

В строке 2 акцент делается на создании списка R. Список R содержит r значения, которые являются 31-байтовыми числовыми хэшами, созданными из целых чисел в [0, N). r значения генерируются с помощью takeright(31,H(j||h||M)). Переменные следующие:

• j, целое число в [0, N)
• h, высота блока
• M, 8 КБ постоянных данных - дополнение для замедления вычисления хэша

Раздел takeRight(31,H(…)) означает, что данное H(…), 32-байтовый выход Blake2b256, возвращает 31 байт справа (т.е. в малом порядке (в то время как другие алгоритмы хеширования являются битовым порядком)). Другими словами, самый значимый байт, байт, находящийся дальше всего слева, отбрасывается. В результате каждое r значение является 31 наименее значимым байтом, полученным из 32-байтового H(j||h||M)) выхода. Например, если j = 1, r1 = takeRight(31,H(1||h||M)). Список R состоит из N элементов и может быть сгенерирован для каждого блока, увеличивая j на 1 N-1 раз. Поскольку H(…) возвращает hash.mod(q), мы можем утверждать, что список R состоит из r0, 1, 2, 3 … N-1 и список R ⊂ Z/qZ. Как указано в белой книге Autolykos v2[3], “N элементы получены из высоты блока и констант, в отличие от Autolykos v1, так что майнеры могут легко пересчитывать кандидатов на блоки (только индексы зависят от них).” Другими словами, j всегда находится в [0,N), N определяется h, M всегда постоянен, и h меняется с каждым блоком, единственная переменная, которую майнеру нужно вычислить для списка R, это h.

Список R хранится в ОЗУ. В Autolykos N = 2²⁶ (67,108,864 целых числа) используется в реализации для каждого блока до 614400. Таким образом, требование к памяти для блоков до блока 614400 составляет (226 * 31 байт =) 2.08 ГБ. N впервые увеличился на блоке 614400. После блока 614400, каждые 51200 блоков N увеличивается на 5%. Другими словами, требование к памяти майнера Ergo увеличивается на 5% каждые ~71 день. На блоке 4198400 значение N становится постоянным и равно 2,143,944,600[4]. Обратите внимание, что последние 2 значения, указанные в таблице, должны быть 2,143,944,600, а не 2,147,387,550. После блока 4198400, требование к хранилищу списка R будет (31 байт * 2,143,944,600) = 66.46 ГБ.

N элементы на основе высоты блока

N элементы, Ethash против Autolykos

Autolykos похож на Ethash в том смысле, что высота блока определяет N элементы, которые должны храниться в ОЗУ. С Autolykos высота блока определяет N 31-байтовых числовых хэшей, которые должны храниться. С Ethash высота блока определяет N 128B DAG страниц, которые должны храниться. Вы можете задаться вопросом, если блок Ergo происходит каждые 2 минуты, как майнеры Ergo могут так быстро генерировать набор данных более 2 ГБ? Майнеры Ethereum только регенерируют DAG каждые 100 часов, потому что это занимает так много времени... Для майнера Ergo бремя вычисления списка R составляет N экземпляров Алгоритма 3; помните, каждое r значение вычисляется как takeRight(31,H(j||h||M)). Однако GPU может делать это очень быстро, GPU обычно имеют 32-широкие или 64-широкие многопроцессоры, что означает, что 32 или 64 экземпляра Алгоритма 3 могут выполняться одновременно в зависимости от GPU. Например, 32-широкий GPU, такой как RTX570, может заполнить список R всего за несколько секунд.

Для Части II, мы продолжим отсюда и продолжим объяснение Autolykos v2. Следите за обновлениями на социальных медиа-каналах Ergo о Части II этой серии.

[1] https://www.researchgate.net/publication/316904748_Equihash_Asymmetric_Proof-of-Work_Based_on_the_Generalized_Birthday_Problem
[2] https://en.wikipedia.org/wiki/Cyclic_group#/media/File:Cyclic_group.svg
[3] https://www.docdroid.net/mcoitvK/ergopow-pdf
[4] https://www.ergoforum.org/t/autolykos-v-2-details/480
[5] Кредит Wolf9466#9466 на Discord