Re: Zcash Equihash PoW Released
If you look on page 115 of Bernstein's Post Quantum Cryptography, it confirms a sqrt(N) speedup for Wagner's solution to the Generalized Birthday Problem for the hypothetical quantum computer.
You seem to have have misinterpreted the book. Page 115 says
If both lists have the same same size sqrt(N) , this means that the merging can be done in sqrt(N) operations instead of N , which is the same speed-up that can be achieved by Grovers
algorithm. Thus, even with a quantum computer we can not expect to get attacks for FSB or CFS
That says there is *no* known quantum speedup for the Generalized Birthday Problem.
Additionally I was thinking that this Equihash can be trivially sped up on an ASIC because the Equihash algorithm is not memory latency bound and thus is bound on the sorting and computation speed and/or the memory bandwidth, which can be optimized with specialized hardware.
There is no publicly available optimized code for Equihash, so we don't really know to what extent it
is bandwidth or latency bound. There may be subtle trade offs between the two. We really need to see the memory behaviour of actual running optimized code.
Even once zcash gets around to publishing more optimized cpu and gpu code,
it won't be clear for a while whether further optimizations are possible, considering that the mining
algorithm is rather nontrivial.
I'm somewhat worried by this statement on their optimization page at
https://github.com/zcash/zcash/issues/857We don't have to do every possible optimization, but enough that it's feasible to run a miner with the right parameters.
Leaving optimizations on the table means that some miners will be able to run more efficiently than others.