Bitcoin & Computational Complexity

Well, I’m lying. This blog post isn’t really about bitcoin. It’s just inspired by a lot of discussions about bitcoin I’ve had recently, which is inspired by the recent spade of attention the project received. So let me start with a disclaimer: I’ve not managed to read the bitcoin paper yet, so am not passing judgement on anything to do with bitcoin.

However, as I understand it, bitcoin is based — in some way or another — around using computational complexity for proof of work, and the proof of work for … something or other.

My (vegan) beef isn’t with the idea of using computational complexity for proof of work1. It’s cute. It’s elegant, even. And I think that elegance blinds people.

My beef is with the fact that you can’t use proof of work based on computational complexity as proof of authenticity. That’s a retarded idea, and I’m genuinely surprised and shocked to find so many people don’t question it.

Quite a while ago I ranted a bit in the comments of a proposal to use the same basic idea to build a decentralized DNS replacement. Nice idea, in many ways, yet deeply flawed in others. So I’m not going to go into specifics of any particular implementation at all here. All I want to state is this:

The geeks of this world have got to realize that the cheapest thing in the world today is CPU power. Anything based on computational complexity must therefore be suspect first, elegant second, and sensible only after careful examination.

You want proof? The news is (currently) full of proof. Basically, in order to attack the PlayStation Network, the attackers rented Amazon VMs. Probably using stolen credit card information.

People need to distance themselves from the fact that with the hardware they’ve got at home, a problem with high computational complexity may take a long time to solve. Given enough criminal energy, that is a non-problem.

I understand why this news hasn’t quite sunk in yet. In recent years, we’ve seen — more than anything — an explosion of cheap storage space, and it’s somewhat overshadowed the fact that computing power has got cheaper, too. Yet smartphone owners carry CPUs in their pocket powerful enough to solve all sorts of problems.

On a more programming-related note, the problem programmers face today is rarely that there is not enough CPU to go around for whatever they want to do. The problem they face is how to schedule work on the CPU to use it fully; old-fashioned simple approaches utilize only a fraction of the available power. Read anything on game engine programming or in ACM’s high performance computing publications, and you’ll see this factoid repeated over and over.

Face it: Storage is abundant, but CPU power is ubiquitous, for most intents and purposes.

Edit: It occurs to me that this rant sounds as if I’m dismissing public key cryptography as insecure. There is one crucial difference between the two: public key cryptography is based on the assumption that cracking a key has such high computational complexity that it’s infeasible to do at all. Schemes like the DNS one above are based on the assumption that the computational complexity for abusing the system is just low enough that everyone’s computer can do it legitimately, but too high for anyone to abuse on a massive scale.

Given enough CPU power, it’s entirely possible to crack keys used in public key cryptography, and it’s becoming more and more easy. It’s still hard enough that the assumption of infeasibility holds for most intents and purposes. I don’t expect this to stay that way forever. Few people do, that’s what’s led to the inflation of key sizes: about 10 years ago, 512 bit keys were considered to be OK for many uses, these days it’s recommended not to use any keys smaller than 2048 bit.

This inflation will happen faster, the cheaper CPU power becomes, and I fully expect that to reach a breaking point. I expect/hope that smart people will come up with some other scheme for keeping our data safe. For the moment, it is.

But the difference in assumptions behind public key cryptography and the DNS scheme exposes the flaw: in the latter, it is fully expected that commodity hardware can solve the problem. It is just also expected that nobody can get hold of enough commodity hardware to solve the problem at scales that cause problems. People who think that must have missed the invention of this series of tubes we call the intarwebs.

  1. Though I feel compelled to say it’s nothing new. A guy from c4 that I was working with in or around 2000 raved about how it can be used to protect against SPAM. I didn’t understand it then, but I do now. []