# Equihash

Last updated

Equihash is a memory-hard Proof-of-Work algorithm introduced by the University of Luxembourg's Interdisciplinary Centre for Security, Reliability and Trust (SnT) at the 2016 Network and Distributed System Security Symposium. The algorithm is based on a generalization of the Birthday problem which finds colliding hash values. It has severe time-space trade-offs but concedes vulnerability to unforeseen parallel optimizations. [1] It was designed such that parallel implementations are bottle-necked by memory bandwidth in an attempt to worsen the cost-performance trade-offs of designing custom ASIC implementations. ASIC resistance in Equihash is based on the assumption that commercially-sold hardware already has quite high memory bandwidth, so improvements made by custom hardware may not be worth the development cost.

## General

Equihash was proposed by Alex Biryukov and Dmitry Khovratovich as part of the University of Luxembourg research group CryptoLUX. It was introduced at the Network and Distributed System Security Symposium 2016 in San Diego. Notable blockchain-based projects such as ZCash, Aion, Hush, and Pirate Chain have integrated Equihash for reasons such as security, privacy, and ASIC miner resistance.

The manufacturer Bitmain has succeeded in optimizing the processing of Zcash's Equihash-200,9 with an ASIC. [2]

## Specification

Equihash has three parameters – ${\displaystyle n}$, ${\displaystyle k}$, and ${\displaystyle d}$ – which determine the algorithm's time and memory requirements. The time complexity is proportional to ${\displaystyle 2^{{\frac {n}{k+1}}+d}}$while the memory complexity is proportional to ${\displaystyle 2^{k+{\frac {n}{k+1}}}}$. The algorithm is often implemented with ${\displaystyle d=0}$ (using an alternative method of controlling the effective difficulty).

The problem in Equihash is to find distinct, ${\displaystyle n}$-bit values ${\displaystyle i_{1},i_{2},...,i_{2^{k}}}$ to satisfy ${\displaystyle H(i_{1})\oplus H(i_{2})\,\oplus \,...\,\oplus \,H(i_{2^{k}})=0}$ such that ${\displaystyle H(i_{1}\parallel i_{2}\parallel \,...\,\parallel i_{2^{k}})}$ has ${\displaystyle d}$ leading zeros, where ${\displaystyle H}$ is a chosen hash function. [1] In addition there are "algorithm binding conditions" which are intended to reduce the risk of other algorithms developed to solve the underlying birthday problem being applicable. A memory-less verification requires ${\displaystyle 2^{k}}$hashes and XORs.

It is proposed that the puzzle in Equihash be solved by a variation of Wagner's algorithm for the generalized birthday problem. (Note that the underlying problem is not exactly the Generalized Birthday Problem as defined by Wagner, since it uses a single list rather than multiple lists.) The proposed algorithm makes ${\displaystyle k}$ iterations over a large list. [1] [3] For every factor of ${\displaystyle {\frac {1}{q}}}$ fewer entries per list, computational complexity of the algorithm scales proportional to ${\displaystyle q^{\frac {k}{2}}}$ for memory-efficient implementations. Alcock and Ren [4] refute Equihash’s security claims, concluding that no tradeoff-resistance bound is in fact known for Equihash.

## Usage

The cryptocurrency Zcash implements Equihash with ${\displaystyle n=200}$ and ${\displaystyle k=9}$.

The cryptocurrency BitcoinZ implements Equihash with ${\displaystyle n=144}$ and ${\displaystyle k=5}$.

The cryptocurrency BitcoinGold implements Equihash with ${\displaystyle n=144}$ and ${\displaystyle k=5}$.

The cryptocurrency Genesis implements Equihash with ${\displaystyle n=192}$ and ${\displaystyle k=7}$.

## Related Research Articles

In cryptography, an HMAC is a specific type of message authentication code (MAC) involving a cryptographic hash function and a secret cryptographic key. As with any MAC, it may be used to simultaneously verify both the data integrity and the authenticity of a message.

In probability theory, the birthday problem or birthday paradox concerns the probability that, in a set of n randomly chosen people, some pair of them will have the same birthday. In a group of 23 people, the probability of a shared birthday is 50%, while a group of 70 has a 99.9% chance of a shared birthday.

The Deutsch–Jozsa algorithm is a deterministic quantum algorithm proposed by David Deutsch and Richard Jozsa in 1992 with improvements by Richard Cleve, Artur Ekert, Chiara Macchiavello, and Michele Mosca in 1998. Although of little practical current use, it is one of the first examples of a quantum algorithm that is exponentially faster than any possible deterministic classical algorithm.

Proof of work (PoW) is a form of cryptographic zero-knowledge proof in which one party proves to others that a certain amount of computational effort has been expended for some purpose. Verifiers can subsequently confirm this expenditure with minimal effort on their part. The concept was invented by Cynthia Dwork and Moni Naor in 1993 as a way to deter denial-of-service attacks and other service abuses such as spam on a network by requiring some work from a service requester, usually meaning processing time by a computer. The term "proof of work" was first coined and formalized in a 1999 paper by Markus Jakobsson and Ari Juels. Proof of work was later popularized by Bitcoin as a foundation for consensus in permissionless blockchains and cryptocurrencies, in which miners compete to append blocks and mint new currency, each miner experiencing a success probability proportional to their computational effort expended. PoW and PoS are the two best known consensus mechanisms. In the context of cryptocurrencies they are the most common mechanisms.

The GOST hash function, defined in the standards GOST R 34.11-94 and GOST 34.311-95 is a 256-bit cryptographic hash function. It was initially defined in the Russian national standard GOST R 34.11-94 Information Technology – Cryptographic Information Security – Hash Function. The equivalent standard used by other member-states of the CIS is GOST 34.311-95.

In cryptography, a one-way compression function is a function that transforms two fixed-length inputs into a fixed-length output. The transformation is "one-way", meaning that it is difficult given a particular output to compute inputs which compress to that output. One-way compression functions are not related to conventional data compression algorithms, which instead can be inverted exactly or approximately to the original data.

A rolling hash is a hash function where the input is hashed in a window that moves through the input.

A fundamental problem in distributed computing and multi-agent systems is to achieve overall system reliability in the presence of a number of faulty processes. This often requires coordinating processes to reach consensus, or agree on some data value that is needed during computation. Example applications of consensus include agreeing on what transactions to commit to a database in which order, state machine replication, and atomic broadcasts. Real-world applications often requiring consensus include cloud computing, clock synchronization, PageRank, opinion formation, smart power grids, state estimation, control of UAVs, load balancing, blockchain, and others.

In computer science, the prefix sum, cumulative sum, inclusive scan, or simply scan of a sequence of numbers x0, x1, x2, ... is a second sequence of numbers y0, y1, y2, ..., the sums of prefixes of the input sequence:

Threefish is a symmetric-key tweakable block cipher designed as part of the Skein hash function, an entry in the NIST hash function competition. Threefish uses no S-boxes or other table lookups in order to avoid cache timing attacks; its nonlinearity comes from alternating additions with exclusive ORs. In that respect, it is similar to Salsa20, TEA, and the SHA-3 candidates CubeHash and BLAKE.

The elliptic curve only hash (ECOH) algorithm was submitted as a candidate for SHA-3 in the NIST hash function competition. However, it was rejected in the beginning of the competition since a second pre-image attack was found.

Double-spending is a potential flaw in a digital cash scheme in which the same single digital token can be spent more than once. Unlike physical cash, a digital token consists of a digital file that can be duplicated or falsified. As with counterfeit money, such double-spending leads to inflation by creating a new amount of copied currency that did not previously exist. This devalues the currency relative to other monetary units or goods and diminishes user trust as well as the circulation and retention of the currency. Fundamental cryptographic techniques to prevent double-spending, while preserving anonymity in a transaction, are blind signatures and, particularly in offline systems, secret splitting.

In cryptography, scrypt is a password-based key derivation function created by Colin Percival, originally for the Tarsnap online backup service. The algorithm was specifically designed to make it costly to perform large-scale custom hardware attacks by requiring large amounts of memory. In 2016, the scrypt algorithm was published by IETF as RFC 7914. A simplified version of scrypt is used as a proof-of-work scheme by a number of cryptocurrencies, first implemented by an anonymous programmer called ArtForz in Tenebrix and followed by Fairbrix and Litecoin soon after.

Litecoin is a peer-to-peer cryptocurrency and open-source software project released under the MIT/X11 license. Litecoin was an early bitcoin spinoff or altcoin, starting in October 2011. In technical details, Litecoin is nearly identical to Bitcoin.

Zerocoin is a privacy protocol proposed in 2013 by Johns Hopkins University professor Matthew D. Green and his graduate students, Ian Miers and Christina Garman. It was designed as an extension to the Bitcoin protocol that would improve Bitcoin transactions' anonymity by having coin-mixing capabilities natively built into the protocol. Zerocoin is not currently compatible with Bitcoin.

The Sakai–Kasahara scheme, also known as the Sakai–Kasahara key encryption algorithm (SAKKE), is an identity-based encryption (IBE) system proposed by Ryuichi Sakai and Masao Kasahara in 2003. Alongside the Boneh–Franklin scheme, this is one of a small number of commercially implemented identity-based encryption schemes. It is an application of pairings over elliptic curves and finite fields. A security proof for the algorithm was produced in 2005 by Chen and Cheng. SAKKE is described in Internet Engineering Task Force (IETF) RFC 6508.

In the context of cryptocurrency mining, a mining pool is the pooling of resources by miners, who share their processing power over a network, to split the reward equally, according to the amount of work they contributed to the probability of finding a block. A "share" is awarded to members of the mining pool who present a valid partial proof-of-work. Mining in pools began when the difficulty for mining increased to the point where it could take centuries for slower miners to generate a block. The solution to this problem was for miners to pool their resources so they could generate blocks more quickly and therefore receive a portion of the block reward on a consistent basis, rather than randomly once every few years.

Monero is a privacy-focused cryptocurrency released in 2014. It is an open-source protocol based on CryptoNote. It uses an obfuscated public ledger, meaning anyone can send or broadcast transactions, but no outside observer can tell the source, amount, or destination. A proof of work mechanism is used to issue new coins and incentivize miners to secure the network and validate transactions.

Bitcoin Gold (BTG) is a cryptocurrency. It is a hard fork of Bitcoin, the open source cryptocurrency. It is an open source, decentralized digital currency without a central bank or intermediary that can be sent from user to user on the peer-to-peer Bitcoin Gold network.

Dmitry Khovratovich is a cryptographer, currently a Principal Cryptographer at Evernym, Inc., Senior Cryptographer for the Dusk Network and member of the International Association for Cryptologic Research. He developed, together with Alex Biryukov, the Equihash Proof-of-work algorithm which is currently being used as consensus mechanism for the ZCash cryptocurrency, and the Argon2 key derivation function, which won the Password Hashing Competition in July 2015.

## References

1. Biryukov, Alex; Khovratovich, Dmitry (2017). "Equihash: Asymmetric Proof-of-Work Based on the Generalized Birthday Problem: Open Review". Ledger. 2. doi:. Retrieved 7 October 2018.
2. Dölle, Mirko (June 26, 2018). "End of the graphics card era: 8000 ASIC Miners for Zcash, Bitcoin Gold & Co". Heise (in German). Retrieved 6 Oct 2018.
3. Wagner, David (2002), "A Generalized Birthday Problem", Advances in Cryptology — CRYPTO 2002, Lecture Notes in Computer Science, 2442, Springer Berlin Heidelberg, pp. 288–304, CiteSeerX  , doi:10.1007/3-540-45708-9_19, ISBN   9783540440505
4. Alcock, Leo; Ren, Ling (November 3, 2017). "A Note on the Security of Equihash". CCSW '17. Proceedings of the 2017 Cloud Computing Security Workshop. 2017 ACM SIGSAC Conference on Computer and Communications Security. Dallas, TX, USA: ACM. doi:10.1145/3140649.3140652.