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}$.

Примечания

1. Biryukov, Alex; Khovratovich, Dmitry (2017). "Equihash: Asymmetric Proof-of-Work Based on the Generalized Birthday Problem: Open Review". Ledger. 2. doi:10.5195/ledger.2017.48. Архивировано 2018-10-13. Дата обращения: 2018-10-07. {{cite journal}}: |archive-date= / |archive-url= несоответствие временной метки; предлагается 13 октября 2018 (справка)
2. Dölle, Mirko. End of the graphics card era: 8000 ASIC Miners for Zcash, Bitcoin Gold & Co. (нем.). Heise (26 июня 2018). Дата обращения: 6 октября 2018. Архивировано 6 сентября 2018 года.
3. Wagner, David (2002), "A Generalized Birthday Problem", Advances in Cryptology — CRYPTO 2002, Lecture Notes in Computer Science (англ.), vol. 2442, Springer Berlin Heidelberg, pp. 288–304, CiteSeerX 10.1.1.5.5851, doi:10.1007/3-540-45708-9_19, ISBN 9783540440505
4. Alcock, Leo; Ren, Ling (2017-11-03). "A Note on the Security of Equihash". CCSW '17. Proceedings of the 2017 Cloud Computing Security Workshop. 2017 ACM SIGSAC Conference on Computer and Communications Security. Dallas, TX, USA: ACM. doi:10.1145/3140649.3140652. Архивировано 2020-07-22. Дата обращения: 2020-07-21. {{cite conference}}: |archive-date= / |archive-url= несоответствие временной метки; предлагается 22 июля 2020 (справка)