Are there algorithms that could be used for mining that resist acceleration with ASICs?

Question

In my related question about mining algorithms that balance CPU and GPU it came up that such an algorithm would tremendously increase the incentive for people to create mining botnets. The prospect of a 51% attack by a botnet is not a good one.

However, the algorithms typically used by Bitcoin and related currencies still have the problem that ASIC mining may be so efficient that someone who develops an ASIC and keeps it strictly to themselves could outmine everyone else. This could easily mean a 51% attack by a well-funded adversary.

One possible solution would be a mining algorithm that was inefficient on CPUs but could not be made significantly (orders of magnitude) more efficient with an ASIC. Perhaps an algorithm that requires a moderate amount of memory that would be practical for a GPU to have but not very practical to locate on an ASIC. Perhaps an algorithm that would consume a very large number of gates on an ASIC.

Does anyone know any algorithms that meet the requirements for mining (easily verified on CPU hardware) that don't encourage botnets by working very efficiently on CPUs and don't encourage well-funded adversaries to launch 51% attacks by working very efficiently on ASICs. An algorithm that worked well on common GPUs but couldn't easily be accelerated massively by ASICs would do, I think. Am I missing something?

Answer 1

You are missing botnets of GPUs.

Honestly, I do not think botnets are such a big problem. Botnets succeed because they are invisible to the victims (some trojans even include an anti-virus to clean the system). If an infected computer has 100% CPU usage, it will not stay infected for long. Stealing credit card data is still a lot more profitable than running a crippled mining botnet.

So I would say that the scrypt key derivation function, from nealmcb's answer at your other question, is be a pretty good choice.

Answer 2

There is practically no fixed algorithm that is bounded in computational complexity and storage requirements which does not benefit significantly from an optimized, fixed gate or transistor implementation in the form of an ASIC. The only question is: do the power and computational density benefits versus a CPU/GPU outweigh the significant NRE costs associated with the production of such an ASIC? In the case of Bitcoin, we believe strongly that the answer is 'yes', and that return periods on such an investment are in fact shorter than those associated with GPU mining, particularly at high scale.

Answer 3

MBound would work well, since the fastest way to solve it uses lots and lots of memory - making it fastest on a CPU, not a GPU or ASIC.

On Memory-Bound Functions for Fighting Spam: http://research.microsoft.com/pubs/65154/crypto03.pdf

Answer 4

Colin Percival, the author of scrypt, estimates and compares the costs of implementing various password hashing algorithms in hardware. From his paper:

When used for interactive logins, [scrypt] is 35 times more expensive than bcrypt and 260 times more expensive than PBKDF2; and when used for file encryption — where, unlike bcrypt and PBKDF2, scrypt uses not only more CPU time but also increases the die area required — scrypt increases its lead to a factor of 4000 over bcrypt and 20000 over PBKDF2.

I wonder if the algorithm could be modified to adaptively require more "die area" for hashes as well. At the very least, it could raise the price of entry into custom circuits to allow only the most well-financed attackers.

Answer 5

Explaining further what @Andrew Jones said:

• Algorithms are pushing around 1's and 0's
• Digital chips are good at that.

So the answer is no.

Answer 6

Long-term solution: what about including a low-cost ASIC in commodity hardware that everyone has, like their network router or cable modem, making gaining 51% of the hashing power by a single entity prohibitively expensive.

Answer 7

Perhaps an algorithm that requires a moderate amount of memory that would be practical for a GPU to have but not very practical to locate on an ASIC.

Common misconception. Most fabs now have logic-in-dram processes available; a memory-bandwidth-intensive algorithm would be obscenely faster on these chips than on a GPU or CPU which need to use big slow copper pins and PCB traces to get to the memory chips.

I doubt you're ever going to find the kind of problem you're looking for. CPUs and even GPUs pay a heavy price to be jack-of-all-trades; unless your cryptographic function is something like "boot up a virtual machine running Windows 95 and run this MS-DOS program on it", somebody will find a way to make it more efficient by tossing out the part of the CPU/GPU it doesn't need.

That said, I don't think ASICs will ever be a cost-effective way to mine. They only matter if you're worried about entities with deep pockets who are motivated by something other than making them deeper ("national security").

Answer 8

If one was to have a library of proof of work functions that perform fundamentally different calculations requiring different algorithms that are both genetic and also randomly selected, then yes, ASICs would become irrelevant. But this would require restarting the bitcoin entirely. It won't be done. ASICs are here to stay.

The community's focus should be on developing open sourced ASICs and ensuring they are evenly distributed. Everything usually ends up getting its own hardware. Gamers created the GPU market for example.