Меню Главная Случайная статья Настройки Equihash Материал из https://ru.wikipedia.org Equihash — алгоритм консенсуса Proof-of-work в блокчейн-системах, особенностью которого являются повышенные требованиями к памяти устройства, на котором он выволняется. Это существенно затрудняет майнинг с использованием ASIC. Алгоритм предложили в 2016 году специалисты Междисциплинарного центра безопасности, надёжности и доверия Университета Люксембурга. В его основе лежит атака «дней рождения» — обобщение парадокса дней рождения для нахождения совпадающих значений хеш-функций. Алгоритм стал базовым в ряде блокчейн-систем, например, Zcash, Bitcoin Gold[англ.], Horizen, Aion, Hush и Pirate Chain. Содержание 1 Общие сведения 2 Спецификация 3 Компромисс сложности по времени и памяти 4 Применение 5 Примечания Общие сведения Алгоритм 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 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. Dlle, Mirko. End of the graphics card era: 8000 ASIC Miners for Zcash, Bitcoin Gold & Co. (нем.). Heise (26 июня 2018). Дата обращения: 6 октября 2018. Архивировано 6 сентября 2018 года.