Equihash

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

Общие [ править ]

Equihash был предложен Алексом Бирюковым и Дмитрием Ховратовичем в составе исследовательской группы CryptoLUX Люксембургского университета. Он был представлен на симпозиуме по безопасности сетей и распределенных систем 2016 г. в Сан-Диего . Известные проекты на основе блокчейнов, такие как ZCash , Aion, Hush и Pirate Chain , интегрировали 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 ^ {к + {\ гидроразрыва {п} {к + 1}}}}$${\ displaystyle d = 0}$

Проблема в Equihash состоит в том, чтобы найти различные -битные значения, которым нужно удовлетворять такие, которые имеют ведущие нули, где - выбранная хеш-функция . ^[1] Кроме того, существуют «условия привязки алгоритмов», которые предназначены для снижения риска применимости других алгоритмов, разработанных для решения основной проблемы дня рождения. Для проверки без памяти требуются хеши и XOR.${\ 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}$${\ displaystyle 2 ^ {k}}$

Компромисс между жесткостью памяти и пространственно-временным [ править ]

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

Использование [ править ]

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

См. Также [ править ]

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

Ссылки [ править ]