Просмотр кода страницы Equihash

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

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

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

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

Алгоритм разработан таким образом, что пропускная способность памяти устройства является «узким местом» при распараллеливании вычислений, что не даёт возможности существенно увеличить скорость майнинга при использовании устройств ASIC.<ref name="Biryukov 2017">{{cite journal|last1=Biryukov|first1=Alex|last2=Khovratovich|first2=Dmitry|date=2017|title=Equihash: Asymmetric Proof-of-Work Based on the Generalized Birthday Problem: Open Review|journal=Ledger|url=https://ledger.pitt.edu/ojs/index.php/ledger/article/view/48|volume=2|access-date=7 October 2018|doi=10.5195/ledger.2017.48|doi-access=free|archive-date=13 October 2018|archive-url=https://web.archive.org/web/20181013175805/http://ledger.pitt.edu/ojs/index.php/ledger/article/view/48|url-status=live}}</ref>

Позднее производителю ASIC [[Bitmain]] удалось в свои чипы интегрировать версию алгоритма Equihash-200,9 используемую в Zcash<ref>{{cite web|url=https://www.heise.de/newsticker/meldung/Ende-der-Grafikkarten-Aera-8000-ASIC-Miner-fuer-Zcash-Bitcoin-Gold-Co-4091821.html|title=End of the graphics card era: 8000 ASIC Miners for Zcash, Bitcoin Gold & Co.|date=2018-06-26|access-date=2018-10-06|last=Dölle|first=Mirko|website=Heise|language=de|archive-date=2018-09-06|archive-url=https://web.archive.org/web/20180906131216/https://www.heise.de/newsticker/meldung/Ende-der-Grafikkarten-Aera-8000-ASIC-Miner-fuer-Zcash-Bitcoin-Gold-Co-4091821.html|url-status=live}}</ref>.

== Спецификация ==
Алгоритм имеет три параметра, <math>n</math>, <math>k</math> и <math>d</math>, которые определяют требования по времени и занимаемой памяти:
* Требуемое время пропорционально <math>2^{\frac{n}{k+1}+d}</math>.
* Объём необходимой памяти пропорционален <math>2^{k+\frac{n}{k+1}}</math>.
Алгоритм часто применяется с <math>d = 0</math>, используя альтернативный метод управления сложностью.<ref name="Biryukov 2017" />

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

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

Верификация работы алгоритма требует <math>2^k</math> вычислений хеш-функции и для проверки не предъявляет специальных требований к памяти.<ref name="Biryukov 2017" />

== Компромисс сложности по времени и памяти ==
{{см. также|Атака «дней рождения»}}
Сформулированная выше задача решается в Equihash с помощью вариации [[Расстояние Левенштейна#Алгоритм Вагнера — Фишера|алгоритма Вагнера]] для обобщённой [[Парадокс дней рождения|задачи о дне рождения]]. Предлагаемый алгоритм выполняет <math>k</math> итераций по большому списку.<ref name="Biryukov 2017" /><ref>{{Citation|last=Wagner|first=David|date=2002|pages=288–304|publisher=Springer Berlin Heidelberg|language=en|doi=10.1007/3-540-45708-9_19|isbn=9783540440505|title=Advances in Cryptology — CRYPTO 2002|volume=2442|series=Lecture Notes in Computer Science|chapter=A Generalized Birthday Problem|citeseerx=10.1.1.5.5851}}</ref>
При изменении количества записей в списке на <math>\frac{1}{q}</math> вычислительная сложность алгоритма изменяется пропорционально <math>q^{\frac{k}{2}}</math> для эффективных по памяти реализаций.

В работе Оклок и Рен ставят под сомнения заявления об устойчивости Equihash, сделав вывод, что для него на самом деле не существует границы устойчивости к компромиссам.<ref name="Alcock 2017">{{cite conference|last1=Alcock|first1=Leo|last2=Ren|first2=Ling|title=A Note on the Security of Equihash|publisher=ACM|book-title=CCSW '17. Proceedings of the 2017 Cloud Computing Security Workshop|conference=2017 ACM SIGSAC Conference on Computer and Communications Security|location=Dallas, TX, USA|date=November 3, 2017|url=https://dl.acm.org/doi/10.1145/3140649.3140652|doi=10.1145/3140649.3140652|access-date=July 21, 2020|archive-date=July 22, 2020|archive-url=https://web.archive.org/web/20200722010402/https://dl.acm.org/doi/10.1145/3140649.3140652|url-status=live}}</ref>

== Применение ==
Алгоритм используется в криптовалюте [[Zcash]] с параметрами <math>n=200</math> и <math>k=9</math>.

В криптовалюте {{iw|Bitcoin Gold}} используется Equihash с параметрами <math>n=144</math> и <math>k=5</math>.

== Примечания ==
{{примечания}}

{{Криптовалюты}}

[[Категория:Криптовалюты]]
[[Категория:Криптография]]