Memory-hard proof-of-work: are they ASIC-resistant?
Theoretically, the answer is a clear “no”.
Given enough resources (read: invested time and money) and the appropriate knowledge (ASICs don’t grow on trees, they have to be designed) all currently known and/or published “memory-hard PoW” solutions could be rendered into futile efforts. But theory ends where the real world starts…
More specifically, is it true that memory-hardness is enough to ensure that ASICs won't have much of an advantage over general-purpose CPUs?
Your “feel” seem to be correct, as no memory-hard design has managed “to be enough” to ensure that ASICs won't have much of an advantage over general-purpose CPUs… at least, so far.
What prevents an attacker from building a custom ASIC and buying off-the-shelf DRAM chips, and building systems that pair each ASIC with a DRAM chip?
Allow me to step up my soapbox while I dive into that…
Practically, the real show-stopper for ASICs in the realms of cryptocurrency is and will always be “production cost”. Remember that an ASIC is a dedicated piece of hardware. It only solves a single, specific task and isn't (re)programmable like a personal computer or some handheld device.
Production costs for ASICS can quickly run into a few million Euros/US-Dollars due to things like the design of such ASIC chips, their (clean room) manufacturing, and – last but not least – the low yields that come with ASICs (current industry feedback shows 50% of the manufactured chips don't work and are destroyed instead of being used or sold).
Long story short: to create an ASIC for whatever cryptocurrency, you have to have financial backing and a clear break-even-point within reach. If you don’t have those two corner-stones, memory hardness is the least of your problems and you better go back to your drawing board to rethink your plan.
Getting back to your questions: if we assume that your attacker has access to resources as described above, such an attacker would be able to work his/her way well beyond the limits of a specific “memory-hard” PoW implementation.
The logic question arising out of this (and somewhat implied by your question) is: is memory-hardness “the” solution towards ASIC-resistance? Not really, for reasons of which I only described a few (to prevent this answer from becoming a small book).
Potential solution to the problem…
Besides that, I’ld like to point at the fact that — based on the above – there seems to be a solution to the problem. Yet, it clearly leaves the path of “memory-hard PoW algos”. Nevertheless, I think it should be mentioned in this context: instead of chasing some dragon, one could simply exploit the usual problems faced by attackers by exploiting the amount of resources needed, and pushing things beyond feasability… in this case: economic feasability, by leveraging the break-even-point out of the financial reachability of the opponent.
Keeping in mind that ASICs – once designed and manufactured – can not be recoded, transformed, or otherwise reused, a simple but effective attack vector against such attackers themselves emerges: frequently change the PoW implementations, swapping one algo design for another. To keep up with such changes, an attacker who relies on (let’s just call it) ”the magic of ASICs” would need to restart his/her efforts… over and over again upon each swap of algo designs. This – even theoretically – will quickly become more and more infeasable in several areas (economic, time-factor, etc). In the end, an attacker will have to decide of it makes sense to invest more than the expected return, or giving up the efforts of fighting ever-changing cryptocurrency hashing algos and instead focussing on economically more interesting targets.
Memory-hard PoW may have its place, but currently that’s not the front seat…
I can’t deny this potential solution to the problem could benefit from different memory-hard algo designs as well, as those would change ASIC design requirements even more than usual. Yet, this is a “could” and not a “would”. All in all, memory-hard PoW algos currently don’t provide the amount of protection against ASICs that “marketing speak” tries to sell to cryptocurrency users (incl. miners). Surely, we can’t ignore that algos like Litecoin’s Scrypt and things like cryptonight were able to show it is possible to slow down the birth-rate of leaner and meaner ASICs at least for a few short moments (because they changed the hardware and/or resource requirements via algo-design and -combination).
Yet, up until now, every fixed algo implementation – memory-hard or not – is slowly being rendered void just like some former cryptographically secure things we all used to love: MD5, RC4, and SHA1. Therefore, I’ld say it’s not worth focussing on memory-hardness in relation to PoW.
Instead, memory-hardness should be kept in mind as a potential factor when designing the next hashing implementations… only to be implemented in such a way if it really makes sense. (After all, cryptocurrencies – just like everything else cryptography-related – are also influenced by “implementation speed expectations” as well as considering “resources available to the average, benign users in contrast to potential attackers”.)
Missing proofs, practical disproofs, and the future of it all…
If there were a working memory-hard PoW (in relation to ASIC resistance, providing equal chances when mining et al), you would be looking at a near-to-perfect cryptocurrency. As soon as you see it, feel free to ping me… as far as I can see when looking around, we’re still a few years away from something like that. Chances are, it does’t exist… but we can’t know for sure yet since – up until now – no one was able to prove that; just like no one was able to prove up until today that memory-hard implementations are actually able to successfully prevent ASIC (or FPGA) implementations, or at least pull their effectiveness down to a near-CPU level. Instead of providing the needed/wanted/expected proof, a small truckload of theories and papers have already practically been proven wrong.
Nevertheless, assuming cryptocurrency is here to stay (which the most recent EU tax decisions in relation to cryptocurrencies definitely underlined) we might get to a useable and fair PoW one day… even if there’s a good chance that “memory-hardness” will not be a prime factor of the solution. After all, attackers only get smarter and attacks only get better. The search for better and more flexible solutions to known problems have been ongoing for a pretty long time now (as a random example, see the following paper from 1995: An SRAM-programmable field-configurable memory as well as bordering patents), and might push “memory-hardness” into an abandoned corner unless CPU technology, as well as desktop systems as a while, are able to make some similar jumps forward soon.
Looking at military crypto, it’s a wonder we still tend to rely on CPUs instead of using dedicated ASICs and speedy FPGAs. This especially hits one in the face when thinking about cryptocurrency mining: while PoW resembles a high-speed race with a few sprinkles of luck to go with it, some still seem to hope they’ll win that race against fellow-miners (and potential attackers) while riding a “memory-hard” bicycle. Personally, I sincerely doubt memory-hardness by itself will ever be able to provide the fair chance those people are hoping for.