Proof-of-work (PoW) has recently become the backbone of cryptocurrencies. However, users with Application Specific Integrated Circuits (ASICs) can produce PoW solutions at orders of magnitude lower cost than typical CPU/GPU users. Memory-hard PoWs, i.e., PoW schemes that require a lot of memory to generate proofs, have been proposed as a way to reduce the advantage of ASIC-equipped users. Equihash is a recent memory-hard PoW proposal adopted by the cryptocurrency Zcash. Its simplicity, compact proof size, and tunable parameters make it a good candidate for practical protocols. However, we find its security analysis and claims are flawed. Most importantly, we refute Equihash’s claim that its security is based on Wagner’s algorithm for the generalized birthday problem. Furthermore, no tradeoff-resistance bound is known for Equihash, and its analysis on the expected number of solution is incorrect. Our findings do not expose any immediate threat to Equihash. The main purpose of this short note is to raise awareness that Equihash should be considered a heuristic scheme with no formally proven security guarantees.
@tromp Do you have an opinion on the Memory Hard Computing white paper that shows using Argon2 as a method of proof-of-work that theoretically equalizes the computing work between GPU, CPU, and ASIC? It appears to be from the same organization that published the Equihash white paper. https://www.cryptolux.org/index.php/Argon2#Egalitarian_Computing
Authors: Alex Biryukov and Dmitry Khovratovich
University of Luxembourg
Argon2, or any other memory hard key derivation function, makes a poor proof-of-work since verification should be very cheap. I don’t think the authors suggest using it directly for that purpose. They do offer a new Merkle tree based PoW that happens to use Argon2 underneath, but in such a way that verification remains memoryless.
Maybe a bit off-topic, but how are these different to the Cuckoo Cycle you work on for Aeternity?
I would appreciate an answer for the average joe as i’am not an academic in cyrptography, lol.
Cuckoo Cycle is about the simplest possible PoW, with a 42 line specification, and a solver core of about 67 lines. It needs a lot of SRAM to solve efficiently. So you could consider it proof of SRAM. That means the gap between GPUs and ASICs is bigger than with Equihash, as GPUs don’t have much SRAM.
A year ago it looked like Cuckoo Cycle might be ASIC resistant, and was advertized as such, but seeing miners like the Z9 I realize that you can put huge amounts of SRAM on chips at relatively low cost. So now I just call it ASIC friendly and champion its simplicity…
