15

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?

8 Answers 8

7

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.

1
  • 2
    Litecoin is a bitcoin variant that uses scrypt.
    – Eyal
    Apr 13, 2013 at 16:14
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 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.

1
  • 1
    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". Sep 14, 2011 at 2:27
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

5

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.

1
  • 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. Sep 14, 2011 at 7:59
1

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.

5
  • 1
    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.) Sep 14, 2011 at 19:34
  • 1
    @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. Sep 15, 2011 at 0:18
  • 2
    @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. Sep 16, 2011 at 19:59
  • @Kevin: As stated in the question, the goal is an algorithm that could not be made orders of magnitude more efficient on an ASIC. Sep 16, 2011 at 20:06
  • 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). Sep 16, 2011 at 20:16
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.

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

3
  • funny you mention national security since the NSA published the SHA-256 algorithm in 2001
    – CQM
    Apr 13, 2013 at 16:14
  • 1
    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 Apr 18, 2013 at 18:02
  • "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
    Aug 5, 2017 at 8:10
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.

4
  • Why was this downvoted? Everything I said is correct Apr 18, 2013 at 17:59
  • 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. Apr 18, 2013 at 18:01
  • Especially considering that the ASICS and GPUS are more than 51% of the computational power Apr 18, 2013 at 18:05
  • 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? Apr 19, 2013 at 0:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.