Bitcoin part 5: More Cryptography

Let’s see if we can get this train of thought back on the rails.

A previous installment introduced one-way functions and trapdoor one-way functions. Make sure you have internalized that because this will build on it.

One-way functions have many uses, and I want to discuss a few, starting with a simple example. Suppose you and I want to bet on a coin toss. You will guess “heads” or “tails”; I will flip the coin; if you guess right, you win $1; if you guess wrong, you lose $1.

Oh, one more thing: We will play this game over the phone.

Ready? Go.

“Heads.”

“Sorry, it was tails. You lose. Try again.”

“Tails.”

“Oh, sorry, that time it was heads. You lose. Try again.”

After you lose like this a few hundred times in a row, you start to get suspicious.

Is it possible for two untrustworthy people, like you and me, to play this game fairly? By the power of the one-way function, it is! Here is how. First, we agree on a one-way function f. Then I flip a coin. If the coin lands “tails”, I pick a big even number. If it lands “heads”, I pick a big odd number. Call that number x. Then I compute y=f(x) and tell you y. Then you guess “heads” or “tails”. Then, finally, I reveal x.

Since you cannot invert f(x), you have no idea whether x is even or odd at the time you make your guess. And since I cannot invert f either, you can check the x I revealed simply by confirming that f(x)=y. Thus we have flipped a coin over the phone fairly, even if both of us would rather cheat.

A sequence of steps like these — composing cryptographic primitives (like one-way functions) to achieve a more complex result — is called a cryptographic protocol.

This example demonstrates something very important: Even if you are smart — actually, especially if you are smart — you almost certainly should not attempt to design your own cryptographic protocols. The one I just gave fails in at least two ways. Can you spot them?

First, the definition of “one-way function” says it is hard to go from f(x) back to x. It does not say that it is hard to tell whether x is even or odd. So this is a potential avenue for you to cheat.

Second, even if it is hard to find x given f(x), maybe I can somehow find two numbers x and x' such that x is even, x' is odd, and f(x) = f(x'). If you guess “heads”, I can claim my number was x. If you guess “tails”, I can claim my number was x'. So this is a potential avenue for me to cheat.

The point is that designing cryptographic protocols is subtle. To do it right, you have to understand completely the guarantees made by your cryptographic primitives, and then you have to compose those primitives in provably correct ways. Bitcoin’s designer (designers?) did a pretty good job on this score.

Anyway, to flip a coin by phone — or to design Bitcoin — you want something a little stronger than a one-way function. That something is called a cryptographic hash function.

Definition: A hash function is a function that accepts any number as input and maps it to a limited range of outputs. For example, taking the remainder of a number when divided by 12 is a simple hash function; it maps any number to a value in the range 0 to 11. The output of a hash function is called the hash of the input.

Definition: A collision for a hash function f is a pair of values having the same hash; that is, two distinct x and x' such that f(x) = f(x').

Definition: A cryptographic hash function f is a hash function with two additional properties. First, it is a one-way function. Second, finding any collision for f is hard, in the sense that you have to get very lucky or take a very long time. Note that, among other things, this implies the range of f is much, much bigger than 0 to 11. We will see examples later.

The coin-flipping protocol above works if f is a cryptographic hash function, and if it is hard to determine, from f(x), whether x is even. (Eliminating that last criterion is tricky, I think, and takes us into the realm of “hard-core predicates”, “semantic security”, and “random oracles”. To be perfectly frank, this pushes the envelope of my own knowledge. Like I said, do not attempt to invent your own cryptographic protocols; use somebody else’s instead.)

Hm. I guess I did not quite get back on track. But I came close, since the above is related to how Bitcoin addresses work.

Also, the main point here was to introduce the concept “cryptographic hash function”. (If you have any cryptographer friends, go up to them and say “today I learned that a cryptographic hash is just a collision-resistant one-way function”.) It is impossible to overstate how fundamental this gadget is to Bitcoin’s operation. If I failed to motivate and/or explain it clearly, let me know.

Next up: Digital signatures, a.k.a. even more cryptography. I apologize in advance.

Leave a Reply