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.
To create a digital signature you need two components:
- A message, in most cases a transaction
- 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 -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 - and -axis. Alternatively, you can use the , , and - 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:
- Vectors are written with capital letters, like the public key:
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 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 is a large random number
- If you multiply the base point used for the elliptic curve, secp256k1, with a private key, you get a public key PK
- You want to prove knowledge of to the network without revealing it
How to Create a Digital Signature?
- Generating a digital signature in an elliptic curve cryptography (ECC) scheme is based on the distributive property for point addition.
- We get the equation below by multiplying with on both sides and factoring out the base point on the right side of the equation. This equation holds for any , and .
- We learned that your private key multiplied with the base point yields your public key.
- We replace the universal variable with our private key , and use to simplify the expression .
Let's do this in two steps, first replacing n:
and next simplifying to PK:
- Now, we will replace with . This follows the convention that the scalar multiplied with the base point gives us a point on the curve, the vector .
- We define s as..
..and replace it accordingly. It should be clear that only a person in possession of the private key can compute .
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 that satisfy the equation
This proves you know the private key sk that corresponds to the public key .
Two conditions must be met in order for this to be the case:
- If you know , then you must be able to provide working values for , , and
- If you don't know , then you must not be able to provide working values for , , and .
Being Able to Provide a Valid Signature With the Private Key
Let's assume you know sk.
- First, you choose random value for and a message to sign.
- Next, you compute .
- Lastly, you compute .
If you plug these values into the equation..
...from above, you get...
...which we said earlier holds for any , , and , formerly .
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 , then you must not be able to provide working values for , , and .
In order to provide these working values you would have to solve the equation below:
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 and , 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 from publishing . The message and the point are entirely independent of .
Only could potentially reveal anything useful about ...
...but in order to derive from one would have to solve for:
An adversary doesn't know and cannot derive it from - discrete log problem - as it would be the same as deriving from .
Without knowledge of you cannot compute from .
Quick Recap - Creating a Digital Signature
- First, we used the distributive property to build an equality.
- We multiplied both sides with with .
- We replaced the variable with our private key and the expression which represents the product of our private key with the base point with the public key .
- We defined to be the product .
- We defined as the term .
- We showed that if you can provide an , , and that satisfy the resulting equation, it proves knowledge of the private key corresponding to the public key .
- We also proved that without knowledge of , you cannot provide working values for , , and .
- Lastly, we showed that you can reveal , , and without revealing any information about the private key .
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 , based on the originating public key and the signature, which is composed of and .
As we showed above, only by knowing one can produce a valid signature. Verification of the signature includes plugging those three variables into the equation below and checking if it holds.
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 is to be signed, with and comprising the signature of that message.
Because depends on the message , the verification process is only successful if two conditions are met:
- The sender of the message knows the private key used to generate the UTXO's address
- And the signature (, ) was created for that specific transaction .
With cryptocurrencies, the message m is the unsigned part of a transaction.
The digital signature of that transaction consists of the -coordinate of and the sign of its -value.
This -coordinate is concatenated with , 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 with a base point to get the public key and then hashing 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 can produce a valid signature (R,s) for a given message m.
We also showed that you cannot compute the private key from the information contained in .