user85: 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?

user228: 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.

user4338: 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.

user381: 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.

user5: 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.

user222: 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.

user390: 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

85: <p>In my related question about <a href="https://bitcoin.stackexchange.com/questions/931/are-there-algorithms-that-could-have-been-chosen-for-mining-that-balance-cpu-gpu">mining algorithms that balance CPU and GPU</a> it came up that such an algorithm would tremendously increase the incentive for people to create mining botnets. The prospect of a <a href="https://bitcoin.stackexchange.com/questions/658/what-can-an-attacker-with-51-of-hash-power-do">51% attack</a> by a botnet is not a good one.</p>

<p>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.</p>

<p>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.</p>

<p>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?</p>
 228: <p>Explaining further what @Andrew Jones said:</p>

<ul>
<li>Algorithms are pushing around 1's and 0's</li>
<li>Digital chips are good at that.</li>
</ul>

<p>So the answer is no.</p>
 4338: <p>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.</p>
 381: <p>Colin Percival, the author of <a href="http://www.tarsnap.com/scrypt.html"><code>scrypt</code></a>, estimates and compares the costs of implementing various password hashing algorithms in hardware. From his <a href="http://www.tarsnap.com/scrypt/scrypt.pdf">paper</a>:</p>

<blockquote>
  <p>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.</p>
</blockquote>

<p>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.</p>
 5: <p>You are missing <a href="http://www.symantec.com/connect/blogs/bitcoin-mining-trojanbadminer" rel="nofollow noreferrer">botnets of GPUs</a>. </p>

<p>Honestly, I do not think botnets are such a big problem. Botnets succeed because they are invisible to the victims (<a href="http://www.securelist.com/en/analysis/204792180/TDL4_Top_Bot" rel="nofollow noreferrer">some trojans</a> 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.</p>

<p>So I would say that the <a href="http://www.tarsnap.com/scrypt.html" rel="nofollow noreferrer">scrypt key derivation function</a>, from <a href="https://bitcoin.stackexchange.com/questions/931/are-there-algorithms-that-could-have-been-chosen-for-mining-that-balance-cpu-gpu/935#935">nealmcb's answer</a> at your other question, is be a pretty good choice.</p>
 222: <p>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, <a href="http://www.largecoin.com">we believe strongly</a> 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.</p>
 390: <p>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.</p>

<p>On Memory-Bound Functions for Fighting Spam: <a href="http://research.microsoft.com/pubs/65154/crypto03.pdf">http://research.microsoft.com/pubs/65154/crypto03.pdf</a></p>
