Speaking of Equihash

The generalized birthday problem

If there are two people alone in a room, they have a chance of 1 in 366 to have the same birthday, one for every day of the year, plus February 29. If there are 367 people in a room, you can be 100% sure that two of them will have the same birthday, since there are more people than possible birth dates. However, how many people you need to have a probability of 50%? The answer might be surprising since we only need 23 people for that. For an average classroom of 30 students, the probability goes up to 70%, and with only 70 people we have a 99.9% chance of a double birthday, assuming that each day of the year is equally probable for a birthday.

This problem can be generalized with years of variable length. Given a year with d days, what is the n amount of randomly chosen people to have a birthday coincidence of at least 50%?

The problem can also be extended to 2 dimensions (or types), given two types of people, say m men and n women, what is the probability of a shared birthday between at least one man and one woman (shared birthdays between two men or two women do not count). David Wagner further generalized to k-dimensions[1], which adds multiple dimensions of types: “given k lists of n-bit values, find some way to choose one element from each list so that the resulting k values XOR to zero.” He proved its complexity and devised an algorithm for it. It was found to be hard on time and space.

Although the original birthday problem presents a combinatorics paradox, the generalized problem is important for cryptography and the study of hash collisions.

This problem has properties which make it suitable for a proof of work scheme, and one which has time and space tradeoffs which limit ASICs profitability, as explained below.

Hard problems for proof of work

Biryukov and Khovratovich

Biryukov and Khovratovich, who developed Equihash, showed that a wide range of hard problems can be adapted as an asymmetric proof-of-work with tunable parameters. Hard problems are formalized to be so under Computational Complexity Theory. Such problems are intractable when they can be solved in theory, but any solution would take too many resources to be useful. Feasibility is defined as a polynomial-time solution, which means that the bigger the problem, the computation would get bigger as a polynomial equation such as n^k for some positive constant k. An intractable problem, however, would get bigger in an exponential time. A big enough problem would require the entire age of the universe to compute.

Source: BIGOCHEATSHEET.COM

One of these hard problems is the traveling salesman problem: “Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city and returns to the origin city?” Another is the exam scheduling problem: “Given that students are enrolled in many classes, find the shortest exams schedule so as no student has multiple exams at overlapping times.” We have no elegant equation for solving such commonplace problems, yet for small inputs, a brute-force approach is still viable.

A subset of these problems, the NP-complete problems are the best candidates for proof of work, since the best algorithms for them run in exponential time, while their verification runs in polynomial time, and are thus easy to verify. SAT solving, cliques, and Hamiltonian paths, are all good candidates.

Super Mario Coin — Nintendo

A Sudoku Coin could be made with N by N Sudoku grids, or a Super Mario Coin with special Super Mario levels, or even Pac Man, which have all been proven to be NP-Hard[2] by a process or reduction (turning one problem into another). There is a long list of hard and NP problems, the generalized birthday problem is one of them, and has been used by Equihash with the enhanced Wagner’s algorithm for computing it.

Biryukov and Khovratovich formalized in Equihash’s paper[3] that the following conditions are needed for a good proof of work mechanism:

• Asymmetry, which means that it’s hard to prove for a miner, but easy to verify. If it was hard to verify it would be a vector for denial of service attacks on the network. This is similar to problems like Sudoku, solving the grid is hard, and barring a few optimization we have no better strategy than brute-force with backtracking. However, a solved grid can be immediately verified with no effort. The same thing is true for prime factorization, used in cryptographic schemes such as RSA. Given a number, what are the two prime numbers that, when multiplied we get that number? With 15 it’s 3 and 5, with 77 it’s 7 and 11. What about 54063013? RSA uses numbers hundreds of digits long. Again, it is hard to compute, easy to verify.
• No possible optimizations. Clever mining companies might devise a clever algorithm to mine much more efficiently, which they would conceal from everyone else. An efficient algorithm would be orders of magnitude better than any technological advance in microchips from Moore’s law. The Generalized Birthday Problem has been widely studied by computer scientists and cryptographers, and future optimizations are difficult to come by, although not impossible.
• No possible amortizations. Amortizations are due to economies of scale, which would make mining much more efficient if clustered and centralized. With amortization, 2+2 does not equal 4, since the whole is much greater than the sum of its parts. Any computer is better than a billion calculators. Currently, mining pools form to share profit equally, which makes it much more granular. A sole miner would have to wait for the mining reward with worst chances than winning the lottery, a mining pool has far greater chances and will share the reward among its worker ants. Amortization would exacerbate things, since mining pools themselves wouldn’t be able to compete among each other, since the biggest would be at a considerable advantage, thus creating irreparable centralization into the biggest pool.
• Independently tunable parameters. To allow further algorithm improvements and architecture changes, time, memory, and steepness of the proof of work must be tunable independently. Equihash introduces Bitcoin’s difficulty filter (Hashcash[4]) to Wagner’s problem, where the cryptographic hash function must have d leading zero bits. Proof of work needs to adapt its difficulty setting to account for better miners due to technological improvements, so as to sustain a constant mining rate over time. Once we learned how to play tic-tac-toe we won every time and stopped playing altogether, since the game wasn’t tunable for difficulty settings (or we weren’t ready for N by N grids).
• Constrained parallelism. If the cores have to communicate with each other, then parallelism is limited by the network bandwidth. Having a bottleneck in the network or the memory would make the problem bandwidth-hard. It is yet to be proven if parallelism can be completely avoided. We still need to find a hard problem that is inherently sequential. Equihash attempts to use a problem in which any parallel solution would enlarge the chip prohibitively, or require enormous bandwidth. Parts of Equihash can be parallelized, while some steps remain sequential. Parallelism also reduces the time that memory needs to be held per proof. Equihash is memory bandwidth bound, which means that it both depends on RAM GB, and GB/s.

Equihash goes a step further and tries to find a solution which is memory-hard, originally to remedy the disparity between commodity hardware and custom hardware. They do so with a hard problem which requires a great deal of memory to generate a proof (memory-hardness) but is still easy to verify. As known, algorithms are measured by their time complexity and their space complexity. Time complexity measures the increase in the computational steps required as the size of the input increases.

Space complexity measures how much extra memory is needed as the input increases. With infeasible time, even moderate inputs result in a computation of cosmic lengths, while with infeasible space, no hardware on earth can store the data required to compute. Algorithms usually devise tradeoffs between the two. In the Generalized Birthday Problem, the space/time complexity tradeoffs can be set by changing k.

Many memory-hard schemes have been proposed, where a random array of moderate sizes is accessed in a pseudo-random manner to get high bandwidth. Later they suggested filling this memory with a memory-hard function. It was originally assumed that since memory is a very expensive resource in terms of area and the amortized chip cost, ASICs would be only slightly more efficient than regular x86-based machines in terms of memory, yet this is not true in terms of bandwidth, where ASICs can be optimized further than GPUs, which already have more efficient memory bandwidth than CPUs.

The first proposed schemes were symmetric with respect to memory use (A verifier must use the same amount of energy as the prover). Also, the schemes weren’t analyzed for possible optimizations and amortizations: The schemes should neither allow any optimization algorithms, nor should the computational cost be amortizable over multiple calls.

Other Attempts

Aside from Equihash, there has been several notable memory-hard asymmetric PoW solutions to these problems[5]:

1. Primecoin, the first mining algorithm with scientific computing as its work, disrupted the conception that mining equals Hashcash (with variations on the hashing algorithm). Miners search for special prime number chains known as Cunningham chains[6] and bi-twin chains[7], where primes almost double at every step or follow a specific sequence.
2. Momentum[8] by Daniel Larimer (BitShares, Steemit, EOS), also based on the generalized birthday problem, looks for a collision in 50-bit outputs of the hash function with 26-bit input. In simple terms, a miner has to find two items which hash together to zero. However, it failed as a proof of work because the time-space tradeoffs are very unfavorable. Tradeoffs should have a linear relationship for a good PoW. The puzzle is similar to Equihash, but with only 1 dimension (k=1).
3. Ethash[9], Ethereum’s proof of work. A seed can be computed for each block, from it, one can compute a pseudorandom cache of several megabytes. A dataset of several Gigabytes is generated from that cache (updated once every “epoch” of 30000 blocks, or around 125 hours). Mining involves hashing together random slices of that dataset. Here the asymmetry is inverted, since verification takes longer than each individual proof. This is because verifiers (which are often light clients) trade time for space for a recomputation from the cache, instead of the large dataset used by miners with full clients.
4. Proof of Space[10] (also called proof of capacity) by Dziembowski et al., implemented by Burstcoin, SpaceMint, and Chia, the prover computes a memory-hard function and then a verifier requests a subset of memory locations to check whether they have been filled by a proper function.
5. Cuckoo Cycle[11] by Tromp et al, the first graph-theoretic proof of work, with a very concise 42-line complete specification. The prover must find a cycle of 42 edges in a bipartite Cuckoo Hashtable graph, which is very easy to verify. The January 2015 Cuckoo Cycle publication includes the edge trimming space optimization identified by Dave Andersen.

Equihash proposed a fast, memory-asymmetric and optimization / amortization-free proof of work, based on the generalized birthday problem. To make it amortization-free, they introduced another constraint called algorithm binding which makes each solution almost unique. It also combines elements of Bitcoin’s Hashcash algorithm (by Adam Back), where miners hash until they find a digest that has d leading zeros. As outlined above, Wagner’s Generalized Birthday Problem allow for n and k parameters, which result in space and time difficulties which are not trivial to modify. The computation time per solution can be decreased by increasing n, which increases the number of solutions at the expense of memory. With Hashcash, difficulty adjustment with d is easy, and in Zcash’s implementation, this difficulty parameter is adjusted by the network to target a 2.5-minute block time.

Zcash’s implementation

Zcash Foundation implemented Equihash proof of work[12], specified with parameters of n=200, k=9, which dictate how much memory space/bandwidth will be needed to find a solution. They tested it with an Open Source Miner Challenge[13] with $30,000 in prizes. The algorithm has been used by Bitcoin Gold and Bitcoin Private.

Solar Designer (Alexander Peslyak)[14] analyzed Zcash’s choice of Equihash and its parameters in 2016 and concluded that Zcash’s parameters (n=200, k=9) are suboptimal and may need to be changed. The submissions to Zcash’s Open Source Miner Challenge required at least 144 MiB of RAM to efficiently find almost all solutions at Zcash’s parameters (current largest commodity CPUs include over 64 MiB of SRAM), and with a specific goal to maximize the amount of SRAM per die, ASICs can catch up very fast, with 10 to 100 improvement in energy efficiency and hardware cost over the most suitable commodity hardware. Other solutions would be many-core CPUs such as Epiphany V (which has 1024 CPU cores), or eDRAM. Solar concluded in 2016 that this might eventually put Zcash on par with Litecoin (but not Bitcoin) in terms of ASIC mining.

Furthermore, Solar noted that current optimized Equihash solvers do contain some optimizations that don’t appear to have been publicly known for Equihash when Zcash launched. They store intermediate results in a much more compact manner (binary tree of index pairs) than what the Equihash paper implied (growing lists of index pairs), which reduces the big-O space complexity by a factor of (2^k)/k. Besides, they identify collisions with incomplete bucket sort that does not ever output the fully sorted lists, whereas Wagner’s algorithm is normally expressed in terms of a complete list sort operation.

Tromp[15], and independently xenoncat[16], identified a space optimization on the published version of Equihash. Alcock and Ren[17] refuted Equihash’s claim that its security is based on Wagner’s algorithm for the generalized birthday problem, and that no tradeoff-resistance bound is known for it, and that its analysis on the expected number of solution is incorrect. They concluded that Equihash should be considered a heuristic scheme with no formally proven security guarantees.

The ASIC era

In June 2018, Bitmain released the ASIC Antminer Z9 mini (followed by the company ASICminer in May), which managed to mine Equihash much more efficiently than commodity CPUs and GPUs by interfacing with SRAM chips at relatively low cost. This was a month after Bitmain released their Ethereum miner, whose Ethash algorithm was also devised to be ASIC-resistant. Researchers at the University of Luxembourg discovered that as of May 2018, 20%-30% of Equihash is mined by ASICs[18].

Antminer Z9 mini announcement

Zcash founder Zooko Wilcox clarified in a forum post that he never committed to ASIC-resistance since it would be impossible in the long-term. Furthermore, there’s a fundamental trade-off between a widespread distribution of the coins on one hand, and miners having a large sunk-cost investment into the coin on the other hand, and that the latter might eventually prove to be valuable for attack-resistance and network stability. He clarified that the motivation for Equihash was for an initial widespread distribution of the coins and mining, yet it allowed people to assume that this was a long-term principle rather than a temporary strategy. The Zcash Foundation stated that they are still committed to an ASIC-resistant path.

Conclusion

At BEAM we believe that Mimblewimble and Equihash are the most promising, state-of-the-art technologies. Equihash is a stable, GPU-friendly algorithm which will allow a fair coin distribution at launch. BEAM will set the parameters giving CPU and GPU miners significant head start over ASICs. However, BEAM does not hold a long-term ASIC resistance policy, and we expect ASICs to eventually catch up in the long term. That will establish a stronger hashrate and cryptographic wall for BEAM’s network, as well as an incentive alignment from the professional mining community.

Thus we will achieve a balance between the tradeoffs of a widespread, democratic coin distribution and the inevitable but synergic attack-resistance from ASIC miners.

Article by Ronen Lahat. @ronenl

References:

[1] Wagner D. 2002. A Generalized Birthday Problem. In: Yung M. (eds) Advances in Cryptology — CRYPTO 2002. Lecture Notes in Computer Science, vol 2442. Springer, Berlin, Heidelberg. https://link.springer.com/chapter/10.1007%2F3-540-45708-9_19

[2] Viglietta G. 2012 Gaming is a hard job, but someone has to do it! https://arxiv.org/abs/1201.4995

[3] Biryukov, A., & Khovratovich, D. 2017. Equihash: Asymmetric Proof-of-Work Based on the Generalized Birthday Problem. Ledger, 2, 1–30. https://doi.org/10.5195/ledger.2017.48

[4] Black, Adam. 2002. Hashcash — A Denial of Service Counter-Measure. http://www.hashcash.org/papers/hashcash.pdf

[5] @tromp: Cuck(at)oo Cycle POW https://youtu.be/CLiKX0nOsHE

[6] Cunningham chain https://en.wikipedia.org/wiki/Cunningham_chain

[7] Bi-twin chain https://en.wikipedia.org/wiki/Bi-twin_chain

[8] Larimer, Daniel. 2014. Momentum — A Memory-Hard Proof-of-Work via Finding Birthday Collisions. http://www.hashcash.org/papers/momentum.pdf

[9] ethereum/wiki https://github.com/ethereum/wiki/wiki/Ethash

[10] Dziembowski, Faust, Kolmogorov, Pietrzak. 2013. Proofs of Space. https://eprint.iacr.org/2013/796.pdf

[11] tromp/cuckoo https://github.com/tromp/cuckoo/

[12] Why Equihash? — Zcash https://z.cash/blog/why-equihash/

[13] Zcash Open Source Miners https://zcashminers.org/

[14] Solar Designer. 2016. Zcash’s use of Equihash as a memory-hard proof-of-work scheme. http://www.openwall.com/articles/Zcash-Equihash-Analysis

[15] Breaking equihash in Solutions per GB second https://forum.zcashcommunity.com/t/breaking-equihash-in-solutions-per-gb-second/1995

[16] xenoncat/equihash-xenon https://github.com/xenoncat/equihash-xenon

[17] Alcock, Leo & Ren, Ling. 2017. A Note on the Security of Equihash. 51–55. 10.1145/3140649.3140652. https://dl.acm.org/citation.cfm?id=3140652

[18] Biryukov, Alex & Feher, Daniel. 2018. Detecting ASIC Miners in Zcash (draft v1.1) https://cryptolux.org/images/e/ef/Zcash_Mining.pdf

Speaking of Equihash was originally published in BEAM Privacy on Medium, where people are continuing the conversation by highlighting and responding to this story.

This article was also translated to Japanese.