Equihash (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].
Спецификация
[править | править код]Алгоритм имеет три параметра, , и , которые определяют требования по времени и занимаемой памяти:
- Требуемое время пропорционально .
- Объём необходимой памяти пропорционален .
Алгоритм часто применяется с , используя альтернативный метод управления сложностью.[1]
Задача, решаемая алгоритмом Equihash, состоит в нахождении различных -битных значений , таких, что и имеет ведущих нулей, где — некоторая хеш-функция.[1]
Алгоритмом также накладываются дополнительные ограничения, которые призваны предотвратить применение других алгоритмов для решения основной задачи.
Верификация работы алгоритма требует вычислений хеш-функции и для проверки не предъявляет специальных требований к памяти.[1]
Компромисс сложности по времени и памяти
[править | править код]Сформулированная выше задача решается в Equihash с помощью вариации алгоритма Вагнера для обобщённой задачи о дне рождения. Предлагаемый алгоритм выполняет итераций по большому списку.[1][3] При изменении количества записей в списке на вычислительная сложность алгоритма изменяется пропорционально для эффективных по памяти реализаций.
В работе Оклок и Рен ставят под сомнения заявления об устойчивости Equihash, сделав вывод, что для него на самом деле не существует границы устойчивости к компромиссам.[4]
Применение
[править | править код]Алгоритм используется в криптовалюте Zcash с параметрами и .
В криптовалюте Bitcoin Gold[англ.] используется Equihash с параметрами и .
Примечания
[править | править код]- ↑ Перейти обратно: 1 2 3 4 5 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. Архивировано 13 октября 2018. Дата обращения: 7 октября 2018.
- ↑ Dölle, Mirko End of the graphics card era: 8000 ASIC Miners for Zcash, Bitcoin Gold & Co. (нем.). Heise (26 июня 2018). Дата обращения: 6 октября 2018. Архивировано 6 сентября 2018 года.
- ↑ 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
- ↑ Alcock, Leo; Ren, Ling (November 3, 2017). "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. Архивировано 22 июля 2020. Дата обращения: 21 июля 2020.