Equihash

Equihash — алгоритм консенсуса Proof-of-work в блокчейн-системах, особенностью которого являются повышенные требованиями к памяти устройства, на котором он выволняется. Это существенно затрудняет майнинг с использованием ASIC.

Алгоритм предложили в 2016 году специалисты Междисциплинарного центра безопасности, надёжности и доверия Университета Люксембурга. В его основе лежит атака «дней рождения» — обобщение парадокса дней рождения для нахождения совпадающих значений хеш-функций.

Алгоритм стал базовым в ряде блокчейн-систем, например, Zcash, Bitcoin Gold^[англ.], Horizen, Aion, Hush и Pirate Chain.

Алгоритм Equihash был предложен специалистами исследовательской группы CryptoLUX Люксембургского университета Алексом Бирюковым и Дмитрием Ховратовичем. Он был представлен на Симпозиуме по безопасности сетей и распределённых систем в 2016 году в Сан-Диего.

Алгоритм разработан таким образом, что пропускная способность памяти устройства является «узким местом» при распараллеливании вычислений, что не даёт возможности существенно увеличить скорость майнинга при использовании устройств ASIC.^[1]

Позднее производителю ASIC Bitmain удалось в свои чипы интегрировать версию алгоритма Equihash-200,9 используемую в Zcash^[2].

Алгоритм имеет три параметра, ${\displaystyle n}$, ${\displaystyle k}$ и ${\displaystyle d}$, которые определяют требования по времени и занимаемой памяти:

• Требуемое время пропорционально ${\displaystyle 2^{{\frac {n}{k+1}}+d}}$.
• Объём необходимой памяти пропорционален ${\displaystyle 2^{k+{\frac {n}{k+1}}}}$.

Алгоритм часто применяется с ${\displaystyle d=0}$, используя альтернативный метод управления сложностью.^[1]

Задача, решаемая алгоритмом Equihash, состоит в нахождении ${\displaystyle 2^{k}}$ различных ${\displaystyle n}$-битных значений ${\displaystyle i_{1},i_{2},...,i_{2^{k}}}$, таких, что ${\displaystyle H(i_{1})\oplus H(i_{2})\,\oplus \,...\,\oplus \,H(i_{2^{k}})=0}$ и ${\displaystyle H(i_{1}\parallel i_{2}\parallel \,...\,\parallel i_{2^{k}})}$ имеет ${\displaystyle d}$ ведущих нулей, где ${\displaystyle H}$ — некоторая хеш-функция.^[1]

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

Верификация работы алгоритма требует ${\displaystyle 2^{k}}$ вычислений хеш-функции и для проверки не предъявляет специальных требований к памяти.^[1]

Сформулированная выше задача решается в Equihash с помощью вариации алгоритма Вагнера для обобщённой задачи о дне рождения. Предлагаемый алгоритм выполняет ${\displaystyle k}$ итераций по большому списку.^[1][3] При изменении количества записей в списке на ${\displaystyle {\frac {1}{q}}}$ вычислительная сложность алгоритма изменяется пропорционально ${\displaystyle q^{\frac {k}{2}}}$ для эффективных по памяти реализаций.

В работе Оклок и Рен ставят под сомнения заявления об устойчивости Equihash, сделав вывод, что для него на самом деле не существует границы устойчивости к компромиссам.^[4]

Алгоритм используется в криптовалюте Zcash с параметрами ${\displaystyle n=200}$ и ${\displaystyle k=9}$.

В криптовалюте Bitcoin Gold^[англ.] используется Equihash с параметрами ${\displaystyle n=144}$ и ${\displaystyle k=5}$.