Equihash

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

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

Алгоритм стал базовым в ряде блокчейн-систем, например, Zcash, Шаблон:Iw, Horizen, Aion, Hush и Pirate Chain.

Общие сведения

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

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

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

Спецификация

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

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

Алгоритм часто применяется с $d=0$, используя альтернативный метод управления сложностью.

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

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

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

Компромисс сложности по времени и памяти

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

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

Применение

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

В криптовалюте Шаблон:Iw используется Equihash с параметрами $n=144$ и $k=5$.