How do Digital Signatures work on Blockchains? (Part 1)

In the original Bitcoin paper, Satoshi Nakamoto defines Bitcoin as a “chain of digital signatures”.

While blockchain technology is an important component for creating decentralised finance, without digital signatures, blockchains can’t become decentralised. As far as we’re concerned, blockchain is only a data structure — a container for storing data.

Without digital signatures, anyone can write absolutely anything on the blockchain, even lies. In this scenario, someone can claim that you’ve sent BTC to them, even if you didn’t. Fortunately, in all blockchain networks, a transaction must be signed by the owner of a wallet before the blockchain can even accept it.

Get to know Bitcoin. Learn the basics of Bitcoin (BTC).

Digital Signature explained in three levels

I’ll explain to you how digital signatures work in three ways. A top-level view will give you the general concept of how digital signatures work, without involving any mathematics.

An intermediate-level explanation will involve some mathematics and a deeper exploration of cryptography, which form the basis of digital signatures.

The expert level will be a technical deep dive on Bitcoin’s digital signature algorithm and how it’s been changed since the Taproot update in November 2021. Since this is a lengthy concept, it warrants an article in itself in an upcoming Part Two of this series. 

You don’t have to go through all levels to understand how digital signatures work. You can choose how far down the mathematical rabbit hole you’d like to go.

Digital Signature explained without math

As mentioned in the introduction, without digital signatures, anyone can write anything on a blockchain. Without digital signatures, nobody would know if a transaction was truly written by you or someone else posing as you.

The only way to identify every account holder (wallet owners) is to use a private key. But here’s the problem — private keys are meant to be a secret. So, how can we prove that we own a private key without revealing it to anyone?

Well, all private keys come with their own public key. Think of a public key like the child of the private key. 

If you ask a baby who her mother is, she probably won’t tell you her mother’s name (she’s just a baby). But if you give her a photo of her mother, and she smiles in recognition, then you’ll know that the person in the photo is indeed her mother, even without knowing her real name. 

In our analogy, the photo is like a digital signature. It contains no detail about the person’s true identity, but only the shape and colour of the person. 

The signature that changes every time

Unlike your paper signature, digital signatures very rarely look the same every time you make one. This is because to make a digital signature, you need to combine your private key with the message through a one-way encryption.

Private key + “Transfer 0.5 BTC to Charlie on 2021-12-01 (09:10:01:120)” → Signature

Although the encryption uses mathematics, it isn’t the same as adding A and B. If that’s the case, if you know the result (the signature), and the message (B), you could figure out the private key (A). 

Instead, some ingenious mathematics is used so that you can’t figure out the private key from the signature.

Signature → “Transfer 0.5 BTC to Charlie on 2021-12-01 (09:10:01:120)” + (???)

While your private key remains the same forever, your message will always change. Even if you send the same amount of crypto to the same person, your signature will change at every fraction of a second.

Private key + “Transfer 0.5 BTC to Charlie on 2021-12-01 (09:10:01:20)” → Signature

Private key + “Transfer 0.5 BTC to Charlie on 2021-12-01 (09:10:01:50)” → SiGnaTurE

Private key + “Transfer 0.5 BTC to Charlie on 2021-12-01 (09:10:01:99)” → SIGnAtuRE

Private key + “Transfer 0.5 BTC to Charlie on 2021-12-01 (09:10:02:12)” → SIGNATUre

A millisecond of difference between two transactions can result in wildly different signatures.

Verifying signatures without needing to know the private key

The public key is able to take the signature and perform some mathematical operations to decode the signature, but it’s still impossible to derive the private key this way.

Signature + Public key → “Transfer 0.5 BTC to Charlie on 2021-12-01 (09:10:01:20)”

If the decoded message matches the actual message being broadcasted, then the message is legitimate and comes from the holder of the private key associated with the public key.

However, if you try to do it with a different public key, the decoded message will look like gibberish.

Signature + Wrong public key → 0xE2C11A6F67953680EAE2F51E27487E13AD9

If the decoded message doesn’t match the message being broadcasted, the network simply ignores the transaction and moves on.

Digital Signature explained with some math 

At this level, I’ll be showing you the mathematics behind digital signatures. Note that there are many algorithms that can produce digital signatures. Bitcoin specifically uses an algorithm called the Elliptic Curve Digital Signature Algorithm (ECDSA). 

However at this level, we won’t be going over ECDSA just yet. You’ll have to understand the fundamental mathematics behind asymmetric encryption. The best way to explain this concept is to go back to the beginnings of mathematical cryptography.

Introduction to modular exponentiation

Let’s say we have a number and a divisor, say 40 and 6 respectively. You’ll know that 6 doesn’t go completely into 40, and that 4 is the remainder. We say that 40 (mod 6) is congruent to 4. 

Now, the result of the modular expression is one-way, meaning that other expressions can produce the result of 4.

10 (mod 6) ≡ 4

16 (mod 6) ≡ 4

742 (mod 6) ≡ 4

The ≡ in math means the expression “is congruent to” the result. This is very useful, because if we know the result and the modulus, we can’t simply work backwards to know the number you’re dividing. 

Three great mathematicians Whitfield Diffie, Martin Hellman, and Ralph Merkle worked out a way for two people to exchange the same secret number even if they have to exchange some information out in public. The Diffie-Hellman-Merkle key exchange protocol works like this:

Adrian picks a random secret number [10] and inserts it into the following expression

7 ^ [10] (mod 13) ≡ 4

Beatrice does the same with another random secret number [2]

7 ^ [2] (mod 13) ≡ 10

Both 7 and 13 are agreed-upon numbers in public, and anyone can use them. Adrian and Beatrice then exchanged each other’s results (4) and (10), and uses them on the same expression.

Adrian uses Beatrice’s (10) and raises it by his secret number [10]

(10) ^ [10] (mod 13) ≡ 3

Beatrice uses Adrian’s (4) and raises it by her secret number [2]

(4) ^ [2] (mod 13) ≡ 3

As a result, both Adrian and Beatrice will have the same secret number 3, and have only exposed the numbers 4 and 10 out into the public.

This works because Adrian and Beatrice are exponentiating the same expressions, just at a different order. Since both sides contain a (mod 13), we can kind of ignore them.

7 ^ [10] ^ [2] ≡ 7 ^ [2] ^ [10]

A ^ B ^ C  = A ^ C ^ B

Modular exponentiation opens up many new doors to cryptography. Next is the development of public key cryptography. This is how the sender can encrypt a message using the recipient’s public key, and only the receiver can decrypt the coded message with their secret key.

Introduction to public key cryptography

Modular exponentiation has one more surprise. If you have two numbers E and D such that

E x D (mod R) ≡ 1

then E and D can act like a lock and key, in other words, a public and secret/private key. The variable E is for encryption and D is for decryption. Don’t worry about (mod R) just yet.

If you have a message M, and you raise it to the power of E, you will have a code C like in the following expression:

M ^ E (mod N) ≡ C

For now, don’t worry about mod N, either. Just know that to decrypt code C to get message M back, we cannot use E (the public key). We have to raise C to the power of D (the private key), like so:

C ^ D (mod N) ≡ M

With the public key encryption algorithm, anyone can encrypt a message to you, but only you can decrypt the message using your own private key.

This brings us to the primitive digital signature algorithm devised by Ronald Rivest, Adi Shamir, and Leonard Adleman (Rivest-Shamir-Adleman, or RSA).

The primitive digital signature algorithm RSA

Building upon the Diffie-Hellman-Merkle key exchange protocol, RSA uses the unique properties of public/private key pairs through modular exponentiation of prime numbers. 

In the last section, we didn’t talk about (mod R) and (mod N). Both R and N are essentially derived from two large prime numbers that mathematicians like to name P and Q, the initiating prime pairs.

If we want to generate a new private/public key pair, we can’t use random numbers. We have to use the initiating prime pairs P and Q. Think of them like the parents of the private key, and the grandparents of the public key. 

In RSA cryptography, we must keep P and Q secret as well as the D decryption variable. However, we can publish the multiplication product of P and Q which makes N in:

M ^ E (mod N) ≡ C          for encryption,

C ^ D (mod N) ≡ M          for decryption.

So, to generate a new private key, we have to choose P and Q such that both are large, unique, prime numbers. Another property must also be satisfied.

E x D ≡ 1 ( mod [(P-1)(Q-1)] )

Let (P-1)(Q-1) be R so we don’t get confused here.

E x D ≡ 1 (mod R)

or in other words,

D (mod R) ≡ E^-1

Notice that both the decryption (private) key D and encryption (public) key E are modular inverses of one another. This is why it’s possible to encrypt one way and decrypt another way. Both numbers have a special mathematical relationship that makes the entire crypto world possible.

Let’s make our own digital signature!

I’m going to break rule (1) where I must choose large enough prime numbers. I choose P = 1487 and Q = 1489 to produce N = 2214143. Typically P and Q are at least 20 digits long, specifically 2 to the power of 64 (or 64 bits in computer science). I also calculate for R = (P-1)(Q-1) = 2211168.

I then have to pick the value of D for the private key such that D is any prime between 1 to (R-1). Let D = 2017, a good year for crypto and a memorable prime number. Once we have the private key, we can derive the public key using the Euclidean algorithm. Don’t worry, I’ll spare you the details.

D (mod R) ≡ E^-1

2017 (mod 2211168) ≡ 1 / 1027201

Therefore, the public key is E = 1027201.

Let’s now write a message. For this purpose, we won’t play around with ASCII codes that transform keyboard letters into numbers. Let’s just have M = 1234 and that M < D to make it work.

Signing the message M with private key D will produce a signature S,

M ^ D (mod N) ≡ S

(1234)²⁰¹⁷ (mod 2214143) ≡ S = 1779720

Does the signature “1779720” really come from someone who possesses the private key 2017? Let’s validate it using our public key E.

S ^ E (mod N) ≡ M

(1779720)^1027201 (mod 2214143) ≡ M = 1234

Don’t take my word for it. Validate it yourself using this online modular exponentiation calculator! 

Why Satoshi Nakamoto doesn’t use the RSA digital signature algorithm

RSA has benefited a lot of businesses, from banking to communications. However, there are a couple of reasons why the RSA algorithm isn’t being used in Bitcoin.

The first reason is that to ensure high security, RSA private keys have to be made longer and longer because computers are increasingly powerful. Because N is a multiplicative product of prime numbers P and Q, it narrows down the target numbers for brute force (guessing and checking). 

Right now, it may be computationally expensive to guess 20 digit numbers. In the future, that may not be the case. Larger and larger numbers will take up so much memory space, which is a resource as precious as electricity.

Being a forward-thinking inventor, Satoshi Nakamoto had to rely on the Elliptic Curve Digital Signature Algorithm (ECDSA) to make private keys shorter but equally powerful.  

The second reason is that ECDSA saves even more memory space because generating a private/public key pair doesn’t require us to store the prime numbers P and Q. Anyhow, these are two additional private values that we must keep. Keeping one private key is challenging enough!

With ECDSA, we need one common public number G as a basis for generating our private key. ECDSA is so powerful because it’s extremely difficult to derive the private key even if we know what G is and what the public key is.

If you want to know more about ECDSA digital signatures, stay in the loop for updates for when the article is published!

Want to see a video summary?

If you want to solidify your understanding of public key cryptography (and refresh your eyes), check out this video below from Android Authority.

And as always, to learn more on all things crypto explore the Easy Crypto Hub!