Skip to main content

What is a Digital Signature?

Public-Key Cryptography is used to verify ownership on a blockchain.

Digital signatures allow you to prove your knowledge of a private key corresponding to a particular address without revealing any information about it.

digital signatures

To create a digital signature you need two components:

  1. A message, in most cases a transaction
  2. And the private key

A verifier will use the message, the public key, and the digital signature as an input to the verification algorithm. This algorithm will then produce a binary output: Either the signature is valid, or it is not.

Every full node and miner on the network will verify every single transaction using this concept.

This mechanism is usually treated as a blackbox, but we will dissect the inner workings of this cryptographic method in this article.

Scalars and Vectors

A scalar is something that only has a magnitude. Simply speaking, any number is a scalar.

A vector, however, has a magnitude and a direction and is represented by a tuple of values.

If we are looking at a two-dimensional plane, a vector can be interpreted as an arrow with a certain length, magnitude, and the angle alpha relative to the positive xx-axis, direction.

This means it is a tuple comprising two values, a double. In order to represent a vector in three-dimensional space, one would use a triple of values.

One value for the magnitude and two for the direction, the angle relative to xx- and zz-axis. Alternatively, you can use the xx, yy, and zz- coordinates to represent a given point in three-dimensional space.

Either way, you need three values.

  • Scalars are written with small letters, like the private key: sksk
  • Vectors are written with capital letters, like the public key: PKPK

scalars vs vectors

It's important to note that the hash of a vector is a scalar. The hash function consumes the tuple of values as an input, and produces a scalar as an output.

We use the bulletbullet operator when we are referring to multiplication on the elliptic curve. We use the $cdot$ operator when we are referring to regular multiplication of scalars.

We added this little discourse because it should help you to keep track of what values are points on the curve, vectors, and what values are scalars.

To recap our previous articles:

  • Your secret or private key sksk is a large random number
  • If you multiply the base point PP used for the elliptic curve, secp256k1, with a private key, you get a public key PK
  • You want to prove knowledge of sksk to the network without revealing it

proving private key

How to Create a Digital Signature?

  1. Generating a digital signature in an elliptic curve cryptography (ECC) scheme is based on the distributive property for point addition.
nP+rP=(n+r)Pn \bullet P + r \bullet P = (n + r) \bullet P
  1. We get the equation below by multiplying with hash(m,rP)\text{hash} (m, r \bullet P) on both sides and factoring out the base point PP on the right side of the equation. This equation holds for any mm, rr and nn.
hash(m,rP)nP+rP=(hash(m,rP)n+r)P\text{hash} (m, r \bullet P) \bullet n \bullet P + r \bullet P = (\text{hash}(m, r \bullet P) \cdot n+r) \bullet P
  1. We learned that your private key multiplied with the base point yields your public key.
skP=PKsk \bullet P = PK
  1. We replace the universal variable nn with our private key sksk, and use PKPK to simplify the expression skPsk \bullet P.

Let's do this in two steps, first replacing n:

hash(m,rP)skP+rP=(hash(m,rP)sk+r)P\text{hash} (m, r \bullet P) \bullet {\color{red} sk} \bullet P + r \bullet P = (\text{hash}(m, r \bullet P) \cdot {\color{red} sk}+r) \bullet P

and next simplifying skPsk \bullet P to PK:

hash(m,rP)PK+rP=(hash(m,rP)sk+r)P\text{hash} (m, r \bullet P) \bullet {\color{red} PK} + r \bullet P = (\text{hash}(m, r \bullet P) \cdot sk+r) \bullet P
  1. Now, we will replace rPr \bullet P with RR. This follows the convention that the scalar rr multiplied with the base point PP gives us a point on the curve, the vector RR.
hash(m,R)(PK+R)=hash(m,R)(sk+r)P\text{hash} (m, {\color{red} R}) \bullet (PK + {\color{red} R}) = \text{hash}(m, {\color{red} R}) \cdot (sk+r) \bullet P
  1. We define s as..
s=hash(m,R)(sk+r)s = \text{hash}(m,R) \cdot (sk + r)

..and replace it accordingly. It should be clear that only a person in possession of the private key sksk can compute ss.

hash(m,R)(PK+R)=sP\text{hash}(m, R) \bullet (PK + R) = {\color{red} s} \bullet P

This is the equation we will be working with from here to prove the following claim:

If you can provide an R and s together with a message mm that satisfy the equation

hash(m,R)(PK+R)=sP\text{hash}(m, R) \bullet (PK + R) = s \bullet P

This proves you know the private key sk that corresponds to the public key PKPK.

Two conditions must be met in order for this to be the case:

  • If you know sksk, then you must be able to provide working values for mm, RR, and ss
  • If you don't know sksk, then you must not be able to provide working values for mm, RR, and ss.

Being Able to Provide a Valid Signature With the Private Key

Let's assume you know sk.

  1. First, you choose random value for rr and a message mm to sign.
  2. Next, you compute R=rPR = r \bullet P.
  3. Lastly, you compute s=hash(m,R)(sk+r)s = \text{hash}(m,R) \cdot (sk + r).

If you plug these values into the equation..

hash(m,R)(PK+R)=sP\text{hash}(m, R) \bullet (PK + R) = s \bullet P

...from above, you get...

hash(m,rP)skP+rP=(hash(m,rP)sk+r)P\text{hash} (m, r \bullet P) \bullet sk \bullet P + r \bullet P = (\text{hash}(m, r \bullet P) \cdot sk+r) \bullet P

...which we said earlier holds for any mm, rr, and sksk, formerly nn.

This satisfies the first condition we need to prove our claim.

Not Being Able to Provide a Signature Without the Private Key

Now we need to prove the second condition is met as well: If you don't know sksk, then you must not be able to provide working values for mm, RR, and ss.

In order to provide these working values you would have to solve the equation below:

hash(m,R)(PK+R)=sP\text{hash}(m, R) \bullet (PK + R) = s \bullet P

To do so, you would need to break the preimage resistance property, one-wayness, of the hash function. This means that you would have to find inputs to the hash function, specifically an mm and RR, that produce a certain output.

Because blockchains use strong preimage-resistant cryptographic hash functions, this proves our second claim.

You cannot provide working values for m, R, and s if you don't know sk.

Not Revealing Information About the Private Key

Now we only need to make sure a potential adversary doesn't learn anything about sksk from publishing ss. The message mm and the point RR are entirely independent of sksk.

Only ss could potentially reveal anything useful about sksk...

s=hash(m,R)(sk+r)s = \text{hash}(m,R) \cdot (sk + r)

...but in order to derive sksk from ss one would have to solve for:

sk=shash(m,R)rsk = \frac{s}{\text{hash}(m,R)} - r

An adversary doesn't know rr and cannot derive it from RR - discrete log problem - as it would be the same as deriving sksk from PKPK.

Without knowledge of rr you cannot compute sksk from ss.

Quick Recap - Creating a Digital Signature

  • First, we used the distributive property to build an equality.
  • We multiplied both sides with with hash(m,rP)\text{hash} (m, r \bullet P).
  • We replaced the variable nn with our private key sksk and the expression skPsk \bullet P which represents the product of our private key sksk with the base point PP with the public key PKPK.
  • We defined RR to be the product rPr \bullet P.
  • We defined ss as the term hash(m,R)(sk+r)\text{hash}(m,R) \cdot (sk + r).
  • We showed that if you can provide an mm, RR, and ss that satisfy the resulting equation, it proves knowledge of the private key sksk corresponding to the public key PKPK.
  • We also proved that without knowledge of sksk, you cannot provide working values for mm, RR, and ss.
  • Lastly, we showed that you can reveal mm, RR, and ss without revealing any information about the private key sksk.

Verifying a Digital Signature

All full nodes and mining nodes verify every transaction before forwarding it or including it in a block.

They verify a transaction, or message mm, based on the originating public key PKPK and the signature, which is composed of ss and RR.

As we showed above, only by knowing sksk one can produce a valid signature. Verification of the signature includes plugging those three variables into the equation below and checking if it holds.

hash(m,R)(PK+R)=sP\text{hash} (m,R) \bullet (PK + R) = s \bullet P

In the context of cryptocurrencies, signatures are used to prove that you own a UTXO-set and that you are entitled to spend it. One spends a UTXO by creating a transaction and using it as an input to create one or more new outputs.

Each input spent needs to be signed.

What Does a Digital Signature Look Like?

A transaction typically informs the network about a transfer of money or data. The message mm is to be signed, with ss and RR comprising the signature of that message.

Because ss depends on the message mm, the verification process is only successful if two conditions are met:

  1. The sender of the message knows the private key sksk used to generate the UTXO's address
  2. And the signature (RR, ss) was created for that specific transaction mm.

With cryptocurrencies, the message m is the unsigned part of a transaction.

The digital signature of that transaction consists of the xx-coordinate of RR and the sign of its yy-value.

This xx-coordinate is concatenated with ss, a 256-bit integer, after they have been converted to hexadecimal format.

Each transaction output has a locking script. It is called scriptPubKey and requires certain conditions to be met in order for the recipient to spend it.

Summary - Digital Signatures

To summarize, public key cryptography (PKC) is used to verify ownership. It's basic building blocks are private keys, public keys, and digital signatures.

This methodology is also used in encryption schemes such as TLS, PGP or SSH.

While there are many different PKC schemes, blockchains use elliptic curve cryptography (ECC).

Cryptography mostly relies on one-way functions. The first one-way function we introduced was the hash function. ECC and its underlying discrete log problem pose a second one-way function.

We showed that multiplication on the curve, even with large numbers, is easy and computationally inexpensive. We also showed that division is computationally infeasible.

Next, we showed how an address is derived from a private key with the two most important steps being multiplication of the private key sksk with a base point PP to get the public key PKPK and then hashing PKPK to get an address.

Because both multiplication and hashing are one-way functions, it is not possible to reverse this process.

We constructed the equation used to create and verify digital signatures and proved that only someone with knowledge of sksk can produce a valid signature (R,s) for a given message m.

We also showed that you cannot compute the private key sksk from the information contained in ss.