Are there algorithms that could have been chosen for mining that balance CPU/GPU?

Question

The mining algorithm for Bitcoins (and most alternative but similar currencies as well) is purely computation hard, but not decision hard or memory hard. This caused the unexpected effect that GPUs are insanely good at mining and CPUs are so bad at mining that there's almost no point in using them to mine.

This has had many effects, including the concentration of mining into specialized hardware. Suppose that I think that's bad and would prefer that commodity CPUs be optimal for mining and that mining on them be practical. Given the requirements of mining, particularly that it work like a lottery and that valid results be quickly verifiable, are there algorithms that could have been chosen that would have resulted in commodity CPUs being the optimal miners?

Are there algorithms that require lots of decisions and/or lots of memory that could serve as the mining algorithm on future crypto-currencies that would make CPU mining practical again and give everyone with a high-end CPU a reasonable chance at mining?

Answer 1

The scrypt key derivation function was explicitly designed to be resistant to hardware optimization, with an explicit trade-off allowed between memory and cpu usage:

The scrypt key derivation function ... is designed to be far more secure against hardware brute-force attacks than alternative functions such as PBKDF2 or bcrypt.

This makes it better than SHA-256 or bcrypt if the intent is to give more of an advantage to CPUs.

Another option would be to include the same sort of variety of primitives that are provided for general purpose CPUs, e.g. a combination of floating point operations, access to large memories (perhaps including something that would use a large random access memory like a disk), etc.

But as Thilo point out, including some sort of anti-botnet feature might also be needed. A CAPTCHA might also make it rather unpopular, but some sort of work load that would indeed be noticed by a regular computer user might make it hard to hide botnet activity.

Answer 2

I suggest bcrypt. It is not a cryptographic hash function per se, but it could replace SHA-256 and add some memory constraints that would make its implementation harder on GPUs.

Bcrypt uses blowfish to encrypt a string with a key derived from a password chosen by the user. So given a string and a target, finding a password that encrypts the string below the target works exactly like the Bitcoin lottery.
As for the memory constraints, it is possible to implement bcrypt on a GPU, but it is much harder (probably impossible) to get the same kind of performance improvements we see with SHA. Here is an excerpt from a post on crypto stackexchange about implementing bcrypt with cuda:

Now bcrypt is a variant of the Blowfish key scheduling, which is defined over a table (a few kilobytes) which is constantly accessed and modified throughout the algorithm. Due to the size of the table, each core will have to store it in the GPU main RAM, and they will compete for usage of the memory bus. So bcrypt will run -- but not with full parallelism. At any time, most cores will be stalled, waiting for the memory bus to become free.

Answer 3

The choice of the SHA-256 algorithm for Bitcoin's proof of work has created what could be described as the most ideal application for botnets that one could possibly conceive of. Bot masters are looking for ways, essentially, to turn computation into cash. Bitcoin does that natively.

The huge risk is if the botnets take over the network. Given that botnets can comprise up to millions of machines (at their largest - most are much smaller than this), even with CPU mining a single botnet could potentially take over the network. For instance, assume a 2M strong botnet comprising Core2 Duo machines (5 MHash/s). This network would do 10 THash/s.

The only countermeasure to this is to have special mining gear that is more efficient than CPUs and GPUs, and not available on the average botted PC. This is why the community needs an ASIC-based mining solution.