Equihash - Equihash

Equihash трудно запомнить Доказательство работы алгоритм введен Люксембургский университет Междисциплинарный центр безопасности, надежности и доверия (SnT) на симпозиуме по безопасности сетей и распределенных систем в 2016 году. Алгоритм основан на обобщении Проблема дня рождения который находит конфликтующие хеш-значения. Он имеет серьезные компромиссы во времени и пространстве, но допускает уязвимость для непредвиденных параллельных оптимизаций.^[1] Он был разработан таким образом, что параллельные реализации ограничены пропускной способностью памяти в попытке ухудшить компромисс между стоимостью и производительностью при разработке пользовательских ASIC реализации. Устойчивость к ASIC в Equihash основана на предположении, что коммерчески продаваемое оборудование уже имеет довольно высокую пропускную способность памяти, поэтому улучшения, сделанные с помощью специального оборудования, могут не окупить затрат на разработку.

Общий

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

Производитель Bitmain удалось оптимизировать обработку Zcash Equihash-200,9 с помощью ASIC.^[2]

Технические характеристики

Equihash имеет три параметра - ${\displaystyle n}$, ${\displaystyle k}$, и ${\displaystyle d}$ - которые определяют время работы алгоритма и требования к памяти. Временная сложность пропорциональна ${\displaystyle 2^{{\frac {n}{k+1}}+d}}$а сложность памяти пропорциональна ${\displaystyle 2^{k+{\frac {n}{k+1}}}}$. Алгоритм часто реализуется с помощью ${\displaystyle d=0}$ (с использованием альтернативного метода управления эффективной сложностью).

Проблема в Equihash - найти отчетливые, ${\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}}$хеши и XOR.

Компромиссы жесткости памяти и пространства-времени

Предлагается решить головоломку в Equihash с помощью вариации алгоритма Вагнера для обобщенной проблемы дня рождения. (Обратите внимание, что основная проблема - это не совсем обобщенная проблема дня рождения, как определено Вагнером, поскольку она использует один список, а не несколько списков.) Предлагаемый алгоритм делает ${\displaystyle k}$ итерации по большому списку.^[1][3] Для каждого фактора ${\displaystyle {\frac {1}{q}}}$ меньше записей в списке, вычислительная сложность алгоритма масштабируется пропорционально ${\displaystyle q^{\frac {k}{2}}}$ для реализаций с эффективным использованием памяти. Алкок и Рен^[4]опровергнуть утверждения Equihash о безопасности, заключив, что на самом деле Equihash не знает никаких ограничений, связанных с сопротивлением компромиссу.

использование

Криптовалюта Zcash реализует Equihash с ${\displaystyle n=200}$ и ${\displaystyle k=9}$.

Смотрите также

• Доказательство ставки
• Система подтверждения работы

Рекомендации

1. Бирюков Алексей; Ховратович, Дмитрий (2017). «Equihash: асимметричное доказательство работы, основанное на обобщенной проблеме дня рождения: открытый обзор». Бухгалтерская книга. 2. Дои:10.5195 / бухгалтерская книга.2017.48. Получено 7 октября 2018.
2. Дёлле, Мирко (26 июня 2018 г.). «Конец эры видеокарт: 8000 майнеров ASIC для Zcash, Bitcoin Gold & Co». Heise (на немецком). Получено 6 октября 2018.
3. Вагнер, Дэвид (2002), «Обобщенная проблема дня рождения», Достижения в криптологии - CRYPTO 2002, Конспект лекций по информатике, 2442, Springer Berlin Heidelberg, стр. 288–304, CiteSeerX  10.1.1.5.5851, Дои:10.1007/3-540-45708-9_19, ISBN  9783540440505
4. Олкок, Лео; Рен, Линг (3 ноября 2017 г.). «Записка о безопасности Equihash». CCSW '17. Материалы семинара по безопасности облачных вычислений 2017 г.. 2017 Конференция ACM SIGSAC по компьютерной и коммуникационной безопасности. Даллас, Техас, США: ACM. Дои:10.1145/3140649.3140652.