First, the good news: Bitcoin does not actually rely on very much cryptography. There are literally decades of cryptological research, including “digital cash” research, that Bitcoin simply ignores because it can. The bad news: I do not see how to understand Bitcoin without some understanding of cryptography. So this is where this whole series might fall down. Let’s get started.
All of Bitcoin’s cryptography — and arguably all of cryptography, period — is based on two concepts: The one-way function and the trapdoor one-way function.
A function is a mapping from inputs to outputs. If you ask a computer person “what is a function?”, they will probably say a function is a program (or a machine) that takes any input x and generates a corresponding output f(x). If you ask a math person the same question, they will probably say a function is an enormous (or infinite) set of pairs (x,f(x)) containing the mapping from each input to the corresponding output. Both perspectives are correct. Well, until you get into non-computable functions, uncountable infinities, etc., at which point the math people win as usual. Both types of people usually think of functions in terms of other functions, like “f(x) is defined as x2” or “x2 is defined as x*x“.
To compute (or evaluate) a function f is to take a particular input x and find the corresponding output f(x). To invert a function f is to take a value y and find any input x such that f(x) = y.
For example, if f(x)=x2, to compute f(5) is to find the value 25. To invert f(x)=36 is to find the value 6 or the value -6; in either case, you have successfully inverted the function.
A one-way function is a function that is easy to compute but hard to invert. The formal definition of “hard” is a little tricky, but the basic idea is that you either have to get very lucky or you have to take a very long time. These are often related: Good one-way functions usually have the property that your best strategy for inverting them is to keep guessing values of x until you stumble across one with f(x) = y. Indeed, Bitcoin “miners” are currently doing precisely this fifty trillion times per second. And rising. We will come back to this.
A trapdoor one-way function is a function that is easy to compute but hard to invert… for everybody except you. The idea is that you create your own personal function g(x) that has a secret (called a private key), such that inverting g is easy if and only if you know the secret. You share the function — but not the secret — with the whole world. So now the whole world can compute the function, but only you can invert it. (Unless, of course, somebody gets very lucky or takes a very long time. You choose g to make “very long” be large compared to, say, the age of the universe.) Every Bitcoin “address” represents a unique trapdoor one-way function. We will come back to this, too.
Given one-way functions and trapdoor one-way functions, some truly amazing things are possible, and they are worth a little discussion. But this is long enough, so I will leave them for another installment.
I will mention one catch: Nobody has actually proven that one-way functions exist, much less trapdoor one-way functions. (As it turns out, proving that something is hard can be hard.) This is one reason to be a little concerned about using Bitcoin. Although probably not as concerned as it might sound at first.
And yes, I will get to all of that. Eventually.
We could add the words “Extension” and “Intension”. Where the extension is the pairs you mentioned and the intension is “what that really means”. What does
square(x)really mean, though?I think there’s yet another answer lurking in NCatLab land, and googling:
(smile and nod)
As for the formal definition of “hard to invert”—discontinuity is a good start. In the sense that neighbours in the domain do not map onto neighbours in the codomain.
So I don’t know much about quantum computers, except that a small one has been constructed, and it breaks RSA. Now imagine that people put $10T or so into bitcoins. Does it become worth your time as a thief to build a quantum coprocessor, based on the published science of how to do so? And mine bitcoins that way?
Great question about quantum computers. I don’t know much about them, either, but I think I know enough to say a word or two later. Somewhere toward the end of this series I will explore “what could go wrong”. Probably. I am sort of making this up as I go…