Equihash

Equihash ist ein speicherintensiver Proof-of-Work- Algorithmus, der vom Interdisziplinären Zentrum für Sicherheit, Zuverlässigkeit und Vertrauen (SnT) der Universität Luxemburg auf dem Network and Distributed System Security Symposium 2016 vorgestellt wurde. Der Algorithmus basiert auf einer Verallgemeinerung des Geburtstagsproblems , das kollidierende Hashwerte findet. Er weist erhebliche Kompromisse zwischen Zeitaufwand und Speicherplatz auf, ist aber anfällig für unvorhergesehene parallele Optimierungen. ^{[ 1 ]} Er wurde so konzipiert, dass parallele Implementierungen durch die Speicherbandbreite begrenzt werden, um das Kosten-Nutzen-Verhältnis bei der Entwicklung kundenspezifischer ASIC- Implementierungen zu verschlechtern. Die ASIC-Resistenz von Equihash beruht auf der Annahme, dass handelsübliche Hardware bereits über eine recht hohe Speicherbandbreite verfügt, sodass Verbesserungen durch kundenspezifische Hardware den Entwicklungskostenaufwand möglicherweise nicht rechtfertigen.

Equihash wurde von Alex Biryukov und Dmitry Khovratovich im Rahmen der Forschungsgruppe CryptoLUX der Universität Luxemburg entwickelt. Es wurde auf dem Network and Distributed System Security Symposium 2016 in San Diego vorgestellt . Namhafte Blockchain -Projekte wie ZCash , BitcoinZ, Horizen, Aion, Hush und Pirate Chain haben Equihash aus Gründen der Sicherheit, des Datenschutzes und der ASIC-Miner -Resistenz integriert. ^{[ 2 ]}

Dem Hersteller Bitmain ist es gelungen, die Verarbeitung von Zcash's Equihash-200,9 mit einem ASIC zu optimieren. ^{[ 3 ]}

Equihash besitzt drei Parameter – , , und –, die den Zeit- und Speicherbedarf des Algorithmus bestimmen. Die Zeitkomplexität ist proportional zu , während die Speicherkomplexität proportional zu ist . Der Algorithmus wird häufig mit implementiert (wobei eine alternative Methode zur Steuerung der effektiven Schwierigkeit verwendet wird). ^{[ 1 ]}${\displaystyle n}$${\displaystyle k}$${\displaystyle d}$${\displaystyle 2^{{\frac {n}{k+1}}+d}}$${\displaystyle 2^{k+{\frac {n}{k+1}}}}$${\displaystyle d=0}$

Das Problem bei Equihash besteht darin, verschiedene n-Bit-Werte zu finden , die führende Nullen haben , wobei eine gewählte Hash-Funktion ist . ^{[ 1 ]} Zusätzlich gibt es „Algorithmusbindungsbedingungen“, die das Risiko minimieren sollen, dass andere Algorithmen, die zur Lösung des zugrundeliegenden Geburtstagproblems entwickelt wurden, anwendbar sind. Eine speicherlose Verifikation erfordert Hashes und XORs. ^{[ 1 ]}${\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}}$

Es wird vorgeschlagen, das Problem in Equihash durch eine Variante von Wagners Algorithmus für das verallgemeinerte Geburtstagsproblem zu lösen. (Das zugrundeliegende Problem entspricht nicht exakt dem von Wagner definierten verallgemeinerten Geburtstagsproblem, da es eine einzelne Liste anstelle mehrerer Listen verwendet.) Der vorgeschlagene Algorithmus iteriert über eine große Liste. ^{[ 1 ] [ 4 ]} Für jeden Faktor, um den die Anzahl der Einträge pro Liste abnimmt, skaliert die Rechenkomplexität des Algorithmus proportional zu , sofern die Implementierung speichereffizient ist. Alcock und Ren ^{[ 5 ]} widerlegen die Sicherheitsbehauptungen von Equihash und kommen zu dem Schluss, dass für Equihash tatsächlich keine Schranke für die Tradeoff-Resistenz bekannt ist. ${\displaystyle k}$${\displaystyle {\frac {1}{q}}}$${\displaystyle q^{\frac {k}{2}}}$

Die Kryptowährung Zcash implementiert Equihash mit und . ^{[ 6 ]}${\displaystyle n=200}$${\displaystyle k=9}$

Die Kryptowährung BitcoinGold implementiert Equihash mit und . ^{[ 7 ]}${\displaystyle n=144}$${\displaystyle k=5}$

• Proof of Stake