A Note on the Security of Equihash


#1

I overlooked the appearance of this paper late last year by Leo Alcock and Ling Ren:

https://dl.acm.org/citation.cfm?id=3140652

https://www.researchgate.net/publication/320745041_A_Note_on_the_Security_of_Equihash

Quoting the abstract:

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.


#2

I requested the full text. I hope they grant it.


#3

https://www.researchgate.net/publication/316568874_Equihash_Asymmetric_Proof-of-Work_Based_on_the_Generalized_Birthday_Problem

Here the full text, all you need is to login with facbook or google or signup.


#4

That is not at all what I’m talking about. Read please.


#5

Uhmm, i just readed 30 pages, what do i miss? Another even longer paper?


#6

I can send you a copy too, if you give me your email address…


#7

I got confused. Is the 30 pages paper i linked the only one or are there other papers/researches as well that i missed?


#8

Specifically
"https://www.researchgate.net/publication/320745041_A_Note_on_the_Security_of_Equihash

The actual body of their article supporting their claims is what I have requested.


#9

Thanks @tromp 20char


#10

@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

Direct link to paper: https://www.cryptolux.org/images/c/cd/Egalitarian.pdf


#11

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.


#12

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.


#13

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…


#14

Heh. I thought you were an engineer, but now you’re a spin doctor :stuck_out_tongue:


#15

Thx a lot, will follow this on the AE forum as it’s another one of my favourite projects :slight_smile:


#16

http://sci-hub.tw/10.1145/3140649.3140652


#17

Do we need to worry? (srs question)


#18

I remember reading that quite some time ago there didn’t seem to be much alarm then