#4 - Bitcoin: Nuts & Bolts, Part Two

signatures only you can make, but everyone can verify

In issue #3, we invented an incomplete, bare-bones version of a cryptocurrency and pointed out a key missing element: the ability to make sure only you can give away your money.

Today, we’ll be tackling that flaw. This issue will explain digital signatures and public/private keys.

Next issue will be all about proof-of-work.

I hope you find it useful. I welcome any comments or questions!

--

We left off last time with Alice expressing concern about forgeries. Alice and her friends were sending a list of transactions (i.e. a ledger) back and forth via email. This was fine when everyone knew everyone, but not as the number of people involved grew. Trust eroded.

What if someone gave away someone else's money without them noticing? What if the person who wrote "Alice gave Frank 5 Imacoins" wasn't Alice?

Here's where cryptography comes in. It'll get technical, but don't worry, we'll pace ourselves.

We want this system to have two properties:

1. anyone can verify the signature of who produced that line

2. anyone can add a transaction to the ledger with a signature producible by only them

That means we want a process that goes something like this:

1. Alice decides to give Frank 5 imacoins

2. Alice writes the entry "Alice gave Frank 5 imacoins." on the ledger

3. Alice encodes the entry with a “key”. Let’s say she uses her name as the key. This creates a code that corresponds ONLY to that entry. Let's say the code is 23o5u42g.

4. Alice "signs" the entry, meaning that she writes the code next to the entry. This is a digital signature that only works for that entry and that code.

5. Finally, Frank verifies that he received the money by confirming that the code matches the entry. It is here that we run into a problem.

In order to verify that the code matches the entry, he needs Alice’s key. He would take the key (“Alice”) plus the transaction entry (“Alice gives Frank 5 imacoins”), use the same encoding process, and then confirm that the code he gets matches the signature on the ledger (“23o5u42g”).

Unfortunately, if Alice gives her key to Frank, that compromises the system. Frank can now sign transactions with Alice’s key. With this system, it seems we have to choose between "anyone can verify" and "only one can sign".

How can we have both?

The solution turns out to be having two versions of the key: a public key (“k43lkj…”) and a private key (e.g. “924jfr…”). You sign transactions with your private key:

Which gives you a signature unique to your private key and the specific entry on the ledger.

Then, other people verify your transactions with your public key:

Bam. Now, anyone can verify any transaction, but only the person with the private key can create them. Alice can sleep well at night.

At this point, you may be wondering three things:

Why can't you create someone’s signature with their public key?

Let’s go back to our Alice-Frank forgery example. You’re Frank and you want to fake Alice’s signature with the message “Alice gave Frank 5 imacoins”.

The verification algorithm is public. Why can't you take the message plus Alice's public key and "solve" for her signature?

The short answer is because these algorithms use cryptographic hash functions. They were created to protect against "solving" for the message. How they work is complicated, but here’s a small amount of intuition.

Imagine you made spaghetti for someone. You’re proud of it, so you took a picture of it.

Now, you’re carrying it in a bowl to them. You trip and spill it everywhere. You can try putting it back in the bowl, but it’ll never be exactly how it was.

It doesn’t matter if you knew exactly how you tripped or how far it fell. There are too many ways it can be different. (Yay entropy!)

But, you do have a picture of it. Let's say you did somehow manage to reconstruct the spaghetti exactly how it was in the bowl.

In this case, verifying that it is the same spaghetti is easy. You can compare it to the picture, and any slight difference will be obvious. At least, for a computer.

Creating a code (or hash) is like spilling spaghetti. The only person who can prove they have that exact spaghetti is the person who didn't spill it in the first place.

How are the public and private keys “connected”?

The real answer is that it’s complicated and depends on the exact encryption algorithms (RSA, elliptic curve, etc). The short and sweet answer is that the public key is a “spilled spaghetti” version of the private key. Given the private key, you can generate the public key. But you can’t go the other way around.

What happens if I take a ledger entry + signature and copy/paste it?

Let's say Alice gives Frank 5 imacoins. This means that Frank has a copy of the ledger with "Alice gives Frank 5 imacoins" and a valid signature by Alice.

What's to stop Frank from copy and pasting that line over and over?

Ah. We've encountered the double-spend problem. There are several solutions to this problem, but the most famous one is Proof-Of-Work.

We'll cover that next time!