Эквихэш

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

Общий

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

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

Спецификация

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

Проблема в Equihash состоит в том, чтобы найти отдельные, $n$-битовые значения $i_{1},i_{2},...,i_{2^{k}}$ удовлетворить $H(i_{1})\oplus H(i_{2})\,\oplus \,...\,\oplus \,H(i_{2^{k}})=0$ такой, что $H(i_{1}\parallel i_{2}\parallel \,...\,\parallel i_{2^{k}})$ имеет $d$ ведущие нули, где $H$ — выбранная хэш-функция . Кроме того, существуют «условия привязки алгоритма», которые призваны снизить риск применения других алгоритмов, разработанных для решения основной проблемы дня рождения. Проверка без памяти требует $2^{k}$хеши и XOR.

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

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

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

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

Криптовалюта BitcoinGold реализует Equihash с $n=144$ и $k=5$.

См. также

• Доказательство доли