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

CC BY-SA 3.0
2011-09-14T22:45:28.313Z
2011-09-14T22:45:28.313Z
Patashu
<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>

CC BY-SA 3.0
2011-09-14T02:27:14.940Z
So the question is how to design the algorithm so that the answer is "no", if that's possible. I do agree that the answer for Bitcoin is most definitely "yes".
David Schwartz
CC BY-SA 3.0
2011-09-14T01:30:16.960Z
2011-09-14T01:30:16.960Z
Andrew Jones
<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>

CC BY-SA 3.0
2011-09-14T07:59:14.477Z
While adaptively changing the die area required would make ASIC mining tricky, it would also make the difficulty algorithm fragile. Exceeding things like cache sizes would cause a "wall" effect where a small difficulty change results in a large change in solution rate. I think you pretty much have to change only the number of iterations required on average to solve a block.
David Schwartz
CC BY-SA 3.0
2011-09-14T07:48:22.967Z
2011-09-14T07:48:22.967Z
sad_mac
<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>

CC BY-SA 3.0
2011-09-14T19:34:38.480Z
I believe this is simply incorrect. For example, consider algorithms that require large amounts of memory. It's hard to make an ASIC any better at that than a commodity DDR3 DRAM chip. (If we could, we already would be, and using that as our RAM chips.)
David Schwartz
CC BY-SA 3.0
2011-09-15T00:18:35.213Z
@David I agree - this was the thrust of Dan Kaminsky's talk at Defcon. He advocated that a memory-heavy algorithm would have been a better choice because it would have made computation on botnet PCs greatly disadvantaged versus computation on specially designed farms.
Ken Simpson
CC BY-SA 3.0
2011-09-16T19:59:42.193Z
@David. Even with a memory heavy algorithm, an ASIC would outperform a CPU. In the worst case, the ASIC might be a CPU with all the unessisary opcodes removed, and the remaining ones optimized, using standard DD3 Chips for ram. But there is more room to opimize. The RAM's access patterns could be optimized for the algorithm (which would be undesirable in general purpose RAM), and it is even possible to put the logic on the same chip as the RAM. The speedup would tiny relative to the speedup possible with bitcoin and hundreds of execution units on chip, but a would speedup still exist.
Kevin Cathcart
CC BY-SA 3.0
2011-09-16T20:06:16.193Z
@Kevin: As stated in the question, the goal is an algorithm that could not be made orders of magnitude more efficient on an ASIC.
David Schwartz
CC BY-SA 3.0
2011-09-16T20:16:17.377Z
Right, somehow that slipped by mind. It depend on the algorithm in question, since not all "memory heavy" algorithms require tons of memory in the big picture. Some (although not all) could still get major speedups on an ASIC, especially those designed to be just heavy enough to be slow on current GPUs. Even the memory heaviest algorithms could benefit from reduced cost and power consumption possible with an ASIC, permitting speedup simply by buying more of them, (but still not the orders of magnitude of the question).
Kevin Cathcart
CC BY-SA 3.0
2011-09-14T17:04:26.183Z
2011-09-14T17:04:26.183Z
Brian Carlton
<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>

CC BY-SA 3.0
2013-04-13T12:50:22.633Z
2013-04-13T12:50:22.633Z
Darren
<p><em>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.</em></p>

<p>Common misconception.  Most fabs now have <a href="http://www-03.ibm.com/press/us/en/pressrelease/32970.wss" rel="nofollow">logic-in-dram processes</a> 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.</p>

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

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

CC BY-SA 3.0
2013-04-13T16:14:59.133Z
funny you mention national security since the NSA published the SHA-256 algorithm in 2001
CQM
CC BY-SA 3.0
2013-04-18T18:02:18.603Z
It's also in their Suite B protocols and Russia uses them as well. SHA-256 is pretty secure unless you're some dude with a proof for P=NP in your backpocket
Charles Hoskinson
CC BY-SA 3.0
2017-08-05T08:10:12.243Z
"boot up a virtual machine running Windows 95 and run this MS-DOS program on it" I'm getting 1.3 M Win95/s
Seph Reed
CC BY-SA 3.0
2011-09-17T06:40:45.117Z
2011-09-17T06:40:45.117Z
eldentyrell
<p>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. </p>

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

CC BY-SA 3.0
2013-04-18T17:59:49.577Z
Why was this downvoted? Everything I said is correct
Charles Hoskinson
CC BY-SA 3.0
2013-04-18T18:01:15.037Z
Changing the block generation method is something the majority of bitcoin clients have to agree to. The community will not agree to make their ASICs and GPUs worthless.
Charles Hoskinson
CC BY-SA 3.0
2013-04-18T18:05:27.490Z
Especially considering that the ASICS and GPUS are more than 51% of the computational power
Charles Hoskinson
CC BY-SA 3.0
2013-04-19T00:06:24.603Z
So no one is going to tell me why they downvoted me? I can write a java program to reflect what I described above if necessary. 

You can change the proof of work computation with every block in a way that requires a different set of algorithms to resolve. An ASIC would then only be useful for certain blocks, but not all. Yet somehow this is worthy of downvoting?
Charles Hoskinson
CC BY-SA 3.0
2013-04-18T17:11:30.940Z
2013-04-18T17:11:30.940Z
Charles Hoskinson
<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>

CC BY-SA 3.0
2013-04-13T16:14:06.767Z
Litecoin is a bitcoin variant that uses scrypt.
Eyal
CC BY-SA 3.0
2011-09-14T00:36:11.203Z
2011-09-14T02:28:20.290Z
2017-04-13T12:47:33.610Z
nmat
<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>

<algorithms><altcoin-development><mining-theory><asic-resistance>
Are there algorithms that could be used for mining that resist acceleration with ASICs?
David Schwartz
# Are there algorithms that could be used for mining that resist acceleration with ASICs?

(Asked by: username_0 on 2011-09-14)

In my related question about [mining algorithms that balance CPU and GPU](https://bitcoin.stackexchange.com/questions/931/are-there-algorithms-that-could-have-been-chosen-for-mining-that-balance-cpu-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](https://bitcoin.stackexchange.com/questions/658/what-can-an-attacker-with-51-of-hash-power-do) 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?

**Tags:** algorithms, altcoin-development, mining-theory, asic-resistance


---

## 8 answers

### Answer by username_12 on 2011-09-14. Score: 7 | Accepted answer

You are missing [botnets of GPUs](http://www.symantec.com/connect/blogs/bitcoin-mining-trojanbadminer).

Honestly, I do not think botnets are such a big problem. Botnets succeed because they are invisible to the victims ([some trojans](http://www.securelist.com/en/analysis/204792180/TDL4_Top_Bot) 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](http://www.tarsnap.com/scrypt.html), from [nealmcb's answer](https://bitcoin.stackexchange.com/questions/931/are-there-algorithms-that-could-have-been-chosen-for-mining-that-balance-cpu-gpu/935#935) at your other question, is be a pretty good choice.

> **Comments:**
> **username_13**: Litecoin is a bitcoin variant that uses scrypt.  

---

### Answer by username_1 on 2011-09-14. Score: 7

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 by username_2 on 2011-09-14. Score: 7

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](http://www.largecoin.com) 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.

> **Comments:**
> **username_0**: So the question is how to design the algorithm so that the answer is "no", if that's possible. I do agree that the answer for Bitcoin is most definitely "yes".  

---

### Answer by username_3 on 2011-09-14. Score: 5

Colin Percival, the author of [`scrypt`](http://www.tarsnap.com/scrypt.html), estimates and compares the costs of implementing various password hashing algorithms in hardware. From his [paper](http://www.tarsnap.com/scrypt/scrypt.pdf):

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

> **Comments:**
> **username_0**: While adaptively changing the die area required would make ASIC mining tricky, it would also make the difficulty algorithm fragile. Exceeding things like cache sizes would cause a "wall" effect where a small difficulty change results in a large change in solution rate. I think you pretty much have to change only the number of iterations required on average to solve a block.  

---

### Answer by username_4 on 2011-09-14. Score: 1

Explaining further what @username_2 said:

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

So the answer is no.

> **Comments:**
> **username_0**: I believe this is simply incorrect. For example, consider algorithms that require large amounts of memory. It's hard to make an ASIC any better at that than a commodity DDR3 DRAM chip. (If we could, we already would be, and using that as our RAM chips.)  
> **username_5**: @username_0 I agree - this was the thrust of Dan Kaminsky's talk at Defcon. He advocated that a memory-heavy algorithm would have been a better choice because it would have made computation on botnet PCs greatly disadvantaged versus computation on specially designed farms.  
> **username_6**: @username_0. Even with a memory heavy algorithm, an ASIC would outperform a CPU. In the worst case, the ASIC might be a CPU with all the unessisary opcodes removed, and the remaining ones optimized, using standard DD3 Chips for ram. But there is more room to opimize. The RAM's access patterns could be optimized for the algorithm (which would be undesirable in general purpose RAM), and it is even possible to put the logic on the same chip as the RAM. The speedup would tiny relative to the speedup possible with bitcoin and hundreds of execution units on chip, but a would speedup still exist.  
> **username_0**: @username_6: As stated in the question, the goal is an algorithm that could not be made orders of magnitude more efficient on an ASIC.  
> **username_6**: Right, somehow that slipped by mind. It depend on the algorithm in question, since not all "memory heavy" algorithms require tons of memory in the big picture. Some (although not all) could still get major speedups on an ASIC, especially those designed to be just heavy enough to be slow on current GPUs. Even the memory heaviest algorithms could benefit from reduced cost and power consumption possible with an ASIC, permitting speedup simply by buying more of them, (but still not the orders of magnitude of the question).  

---

### Answer by username_7 on 2013-04-13. Score: 1

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 by username_8 on 2011-09-17. Score: 0

*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](http://www-03.ibm.com/press/us/en/pressrelease/32970.wss) 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").

> **Comments:**
> **username_9**: funny you mention national security since the NSA published the SHA-256 algorithm in 2001  
> **username_10**: It's also in their Suite B protocols and Russia uses them as well. SHA-256 is pretty secure unless you're some dude with a proof for P=NP in your backpocket  
> **username_11**: "boot up a virtual machine running Windows 95 and run this MS-DOS program on it" I'm getting 1.3 M Win95/s  

---

### Answer by username_10 on 2013-04-18. Score: 0

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.

> **Comments:**
> **username_10**: Why was this downvoted? Everything I said is correct  
> **username_10**: Changing the block generation method is something the majority of bitcoin clients have to agree to. The community will not agree to make their ASICs and GPUs worthless.  
> **username_10**: Especially considering that the ASICS and GPUS are more than 51% of the computational power  
> **username_10**: So no one is going to tell me why they downvoted me? I can write a java program to reflect what I described above if necessary.   You can change the proof of work computation with every block in a way that requires a different set of algorithms to resolve. An ASIC would then only be useful for certain blocks, but not all. Yet somehow this is worthy of downvoting?  

---

