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?