March 28, 2020

Recreating Bitcoin 4:Digital Signature

Prologue #

The previous chapter mentioned symmetrical encryption, and we discovered that we didn’t need to encrypt the whole message in the transaction. Since transaction data can be read by the public, we only need to encrypt a small part of the transaction. What should be encrypt?

Signature #

Since our fundamental purpose is not to prevent others from seeing the message in the transaction data, but to use the encrypted message to prove “I am I,” then my requirement is to encrypt as little text as possible. That is, the name of the sender of the encrypted message.

Why?

The inspiration originates from the real life. John wanted to buy a tractor, but he didn’t have enough money. So he needed to borrow $10,000 from Paul. Paul wanted an IOU from John, but John didn’t want to do that. In fact, John didn’t know how to write. Instead, Paul just wrote one for him: John owes Paul $10,000. But the note didn’t have any legal binding, because John could claim that Paul just made it up himself. To make the IOU a legal-binding note, John needed to sign his name on it at least to make the note unique. He signed it with his name and acknowledged the legal effects of the note. If he signed it with something other than his name, the note wouldn’t have been effective as, for all we know, only John’s name signed by himself had the uniqueness to produce the legal-binding effect (see graph below).

Signature

The unique pattern of John’s signature was the private key. The name John was the public key. John’s signature was only effective in encrypting his own public key (“John”). If he encrypted other people’s names, it wouldn’t be effective. Conversely, when a judge sees John’s signature (that scribble), he can use the public key to decrypt it. Since the public key is “John”, he can use past signature records of John to match this one or to call for John to confirm(decrypt) the signature himself.

In real life the name on the IOU is signature, the least amount of text that proves “I am I.”

Based on the above inspiration, in the Bitcoin system, Alice could use his private key to encrypt his name as unique proof. The name after encryption is “digital signature.” (see graph below)

Use digital signature to prove Alice is Alice

Flaw in the Digital Signature #

Satoshi simulated running the system from the start and discovered a flaw.

This flaw came from the fact that the server didn’t store the corresponding relation between the username and the public key - it wouldn’t be able to know what the public key of Alice was. If someone used their public key to sign someone else’s name, legally speaking it would mean that John signed Sam’s name on the IOU. But currently the system lacked the ability verify.

If Carol wants to steal Alice’s Bitcoin:

1.Carol creates a fake transaction: Alice to Carol 40.

2.Carol uses his private key to encrypt Alice’s username to get a fake signature: 806535be3e.

3.Carols puts public key + fake signature + fake transaction data into the message and sends it to Bitcoin’s server.

4.Server receives the message and gets three parts: public key, signature, and transaction data.

5.Server uses Carol’s public key to decrypt Carol’s fake signature and gets username “Alice.”

6.Server will verify if this “Alice” signature was actually encrypted by the real Alice.

nbsp:nbsp:nbsp:nbsp:That’s the problem. The current server, without having a record of Alice’s public key, cannot verify if the public key in the transaction actually belongs to Alice. In this example, the public key is Carol’s, but because there’s no record of corresponding relation between the username and the public key, the system cannot verify.

7.After the verification is complete, the transaction gets written in the ledger and becomes effective. Carol successfully completed the fake transaction and receives 40 Bitcoin.

Flaw in using username as signature

Public Key as Username #

What’s the source of this flaw?

The source lies in that although server could decrypt the signature into the username, it didn’t know if the public key in the transaction belonged to the actual username. That is, the server didn’t know what Alice’s public key was. And of course, it didn’t know what Carol’s public key was either. So Carol could use her own private key to sign Alice’s name, and naturally decrypting the signature with Carol’s public key wouldn’t be an issue.

How to circumvent this problem?

Satoshi and Gilfoyle started thinking.

If we let the server store the relation between usernames and public keys, we’re going back to the old account model.

What’s the solution?

Satoshi suddenly got an inspiration: the fundamental solution is to get rid of the username and to replace it with the public key!

Same example: if Carol wants to fake a transaction from Alice to herself.

Now we have the transaction data from “Alice to Carol 40” to “Public Key A to Public Key C 40,” with Public Key A being Alice’s public key and Public Key C being Carol’s.

The process goes like following:

1.Carol creates a fake transaction: Public Key A to Public Key C 40.

2.Carol uses her private key to encrypted Alice’s public key and gets a fake signature: f9293ued3.

3.Carols puts Public Key C + fake signature + fake transaction data into the message and sends it to Bitcoin server.

4.Server receives the message and gets three parts: public key, signature and transaction data.

5.Server uses Carol’s public key to decrypt Carol’s fake signature and gets the decrypted text “Public Key A” (Alice’s public key).

6.Server starts to verify if the Public Key C in the message and the decrypted Public Key A match. If there’s no match, the transaction is denied.

Server denies request. Transaction is invalid.

This method solved the flaw by replacing the username with public key (see graph below).

Public key to replace username

Adding Signature to the Transaction Model #

Satoshi ran through the system a couple of times and had another inspiration: currently the message consists of three parts: public key, signature and transaction data. This can be further improved by first eliminating the public key parameter since it already exists in the transaction data. Additionally, the signature parameter can be eliminated as well and added to the transaction data by modifying the transaction model and adding a signature part. This signature can be a part of the transaction data and be added into the ledger for future search.

“This is perfectly reasonable! It’s very necessary to add the signature part into the transaction data since every transaction’s signature and the data should be stored together just like the text and the signature in an IOU. If separated, they don’t constitute legal binding,” said Gilfoyle (see graph below).

Modifying the message

After the change it looks like this (see graph below):

Transaction in the new transaction model

“Now username has absolutely no use. And since the public key can replace username, user.txt doesn’t need to be there either. Now we can completely be done with the account model,” Satoshi finally solved the problem of user registration.

Gilfoyle added, “the public key can be seen as the recipient address, not just a username, although essentially they are the same thing.”

“That’s a good way to understand it. Just like when I order a newspaper, I don’t have to tell the messenger my real name, just my address. The idea of public key as address fits better with everyday experience.”

“I’m ready to code. Updating it to the new model without the account part,” Satoshi took out his computer and started to code.

“May I help?” Gilfoyle said slowly.

“Absolutely! You go ahead with the data part and I will take care of the program part. I’ll give you the password of the server,” Satoshi said.
Gilfoyle got into the server and started change the data model.

First user.txt was removed.

Then usernames were changed into public keys in transaction.txt.
Lastly signature was added to the transaction model (see graph below).

Changes to the data model

Epilogue #

The Bitcoin system in the story has introduced digital signature and given up the account model.

However, the new design has a flaw. Since the signature remains the same, it runs the risk of being used repeatedly. For example, Alice sent Carol 50 Bitcoin. Then Carol could have the motivation to intercept and repeat this request to the server and mislead the server to pay her more than once until Alice’s balance gets below 50.

This flaw will be addressed later.

Next chapter ：Recreating Bitcoin 5:Public Key and Private Key