## Digital Signatures

### History

1. **1976**: Whitfield Diffie and Martin Hellman first described the idea of a digital signature scheme, but they only theorized that such schemes existed.

2. **1977**: Ronald Rivest, Adi Shamir, and Len Adleman invented the RSA algorithm, which could be used to produce a kind of primitive digital signature.

3. **1988**: Lotus Notes 1.0, which used the RSA algorithm, became the first widely marketed software package to offer digital signatures.

4. **1999**: The ability to embed digital signatures into documents is added to the PDF format.

5. **2000**: The ESIGN Act makes digital signatures legally binding.

6. **Until today**: Some institutions and websites have emerged to legalize digital signatures and verify identity.

Digital signatures have evolved over time, becoming an integral part of secure communication and document integrity.

### What is a digital signature?
A **digital signature** is a mathematical scheme for verifying the authenticity of digital messages or documents.

A **valid** digital signature, where the prerequisites are satisfied, gives a **recipient** very high confidence that:
- The message was created by a known **sender** (**authenticity**),
- The message was not altered in transit (**integrity**).

As the main focus of this article is the Schnorr signature, we will not delve into the details of what a digital signature is, assuming that you are already familiar with the concept. However, to provide you with a general intuition, the following illustration may be helpful:


### Digital signatures are new concepts!

Today, there are numerous cryptographic methods available. However, upon closer examination, we realize that cryptography is not a new concept but has a [rich history](https://www.redhat.com/en/blog/brief-history-cryptography#:~:text=The%20first%20known%20evidence%20of,place%20of%20more%20ordinary%20ones). Throughout time, cryptography has been widely used, employing elements such as plain text, keys, and cipher text. Modern cryptography follows a similar pattern, enhancing security, verifiability, and other aspects.

While signatures may have existed before the advent of cryptography, such as the signatures used by kings in their letters, there exists a crucial distinction. In the past (and even in physical signatures used today in banks), signing something to establish ownership required revealing the signature itself. This left the signature vulnerable to forgery since anyone could view it. However, digital signatures introduce a groundbreaking concept: **private key remains hidden**, and there is no need to expose it in order to prove the authenticity of a signature. The ability to sign without revealing one's signature represents a new and innovative development in the realm of digital signatures.


Having gained this intuition from digital signatures, we will now delve into ECDSA and Schnorr to provide a deeper understanding of these advanced digital signature schemes. However, before we proceed, let's take a closer look at the mathematics upon which these signatures are built.

## Elliptic Curve

### What is Elliptic Curve?
We define Weierstrass equation as follows: $y^2 = x^3 + ax + b$

It also has a non-singularity condition: $4a^3 + 27b^2 \neq 0$

This points that satisfies the above equation, form a curve which we call it Elliptic curve. See the picture below for $a = -2, b = 2$.


### Addition of two points

On the points of this curve (i.e., every $(x, y)$ that satisfies the equation), we define new addition method. Let us explain this method by an example. Imagine the curve in the picture above ($a = -1, b = 2$).

$P_1 = (-1.5, \sqrt{1.625})$

$P_2 = (0, \sqrt{2})$

$P_3 = P_1 + P_2 = ?$

We connect point $P_1$ to $P_2$ and extend the line until it intersects the curve at point $-P3$. After that, we reflect it with respect to the x-axis to achieve $P_3$. The math for this procedure is as follows:

$s = \frac{Y_{P_1} - Y_{P_2}}{X_{P_1} - X_{P_2}}$

$X_{P_3} = s^2 - (X_{P_1} + X_{P_2})$

$Y_{P_3} = s(X_{P_1} - X_{P_3}) - Y_{P_1}$

For a better understanding, see the picture below:


### Point doubling

Now we define doubling a point in Elliptic curves. The problem is as follows:

$P = (-0.5, \sqrt{2.875})$

$P + P = 2P = ?$

The procedure is like adding two points. However since there is no two points to draw a line between them, we draw a tangent line on the point $P$ and extend the line until it intersects the curve at point $-P_2$. After that, we reflect it with respect to the x-axis to achieve $P_2$. The math for this procedure is as follows:

$s = \frac{3 {X_P}^2 + a}{2Y_P}$

$X_{2P} = s^2 - 2X_P$

$Y_{2P} = s(X_P - X_{2P}) - Y_P$

For a better understanding, see the picture below:


### Elliptic curve over finite fields

Due to the computational limitations of computers, we **can not** use the aforementioned curve in the $\mathbb{R}^2$ field. So we need to confine ourselves to discrete spaces.

Bitcoin uses **secp256k1** that is defined as follows:

$y^2 = x^3 + 7 \; \; (mod p)$

over $\mathbb{F}_p$, where:

$p = 2^{256} - 2^{32} - 2^9 - 2^6 - 2^4 - 2^0$

By assuming the curve above, we now are in a discrete space.

### An example of finite field
$y^2 \equiv x^3 + 7 \pmod{37}$ in $\mathbb{F}_{37}$

By the definition of the curve, we see that $(5, 21)$ is a point of this curve since: $21 \equiv 5^3 + 7 \pmod{37}$

The picture below shows the above curve:


### A visual look at addition

By starting from a point $G$ (can be seen in the picture below), you can see the addition procedure and how points are scattered.

**Note** that in the realm of finite spaces, the geometric intuitions we had for addition are no longer applicable, and we must rely on mathematical formulas.


### Modular multiplicative inverse
To travel from continuous space to finite space, there are something we have to take care of.

We know that addition, multiplication, and subtraction can be easily defined in finite spaces. See the following examples:

$3 + 4 = 2 \; mod \; 5$

$3 - 4 = 4 \; mod \; 5$

$3 \times 4 = 2 \; mod \; 5$

**But, what is $\frac{1}{s} \; mod \; p$?**

We have to answer this question since it is used in formulas of addition and doubling.

**Definition:**

In $\mathbb{F}_p$, we define $z = \mathbf{\frac{1}{x}}$ iff $xz \equiv 1 \pmod{p}$

So now we can easily apply **all formulas** (addition, doubling) in the **finite fields** too.

## Elliptic Curve Digital Signature Algorithm (ECDSA)

### ECDSA elements
Generator: A publicly known curve point:

$G =(0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798,
\\
0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8)$

Private Key: A big random number. We shall call it $k$ from now on. This number has the following properties:
- Almost unique
- Hard to guess
- In Bitcoin, it’s 256 bit

Public key: Corresponding to each private key, a public key is computed by multiplying $k$ with a public Elliptic curve point $(G)$. We shall call it $P$ from now on.

$P = k \times G$

Every digital signature, has two main algorithms:
- Signing
- Verifying

We will define them for ECDSA in details.

**Note:** From now on, when we use $\times$ symbol, it means a point of curve, multiplied by an integer. For example, $P = k \times G$ (where $k$ is an integer and $G$ is a point of curve). When we eliminate $\times$ symbol, it means multiplication of two integers, For example: $rk$ (where both $r$ and $k$ are integers).

### Sign with ECDSA

Prerequisites:
- Private key: $k$ (integer)
- Public key: $P = k \times G$ (curve point)
- Message: $m$ (integer)

Algorithm:

1. Choose a random number: $z$ (integer)
2. Calculate: $R = z \times G$ (curve point)
3. X-coordinate of $R$: $r$ (integer)
4. Calculate: $s = \frac{m + rk}{s}$ (integer)
5. Signature: $(r, s)$ (integer, integer)

In general:

$SIG_{ECDSA} = (private \; key, \; message) = (r, \; s)$

### Verify with ECDSA

Prerequisites:
- Obtain the public key: $P$ (curve point)
- Obtain signature: $(r, s)$ (integer, integer)
- Obtain massage: $m$ (integer)

Algorithm:

1. Calculate: $u = \frac{m}{s}$ (integer)
2. Calculate: $v = \frac{r}{s}$ (integer)
3. Calculate: $N = u \times G + v \times P$ (curve point)
4. Assert: X-coordinate of $N$ is equal to $r$

In general:

$VER_{ECDSA}(r, \; s) = accept \; or \; reject$

### Proof of correctness

By considering:
- m = message
- G = publicly known initial point on curve
- k = private key
- P = public key
- $u = \frac{m}{s}$
- $v = \frac{r}{s}$
- $s = \frac{m + rk}{z}$

We have:

$u \times G + v \times P$
$= \frac{m}{s} \times G + \frac{r}{s} \times P$
$= \frac{m}{s} \times G + \frac{r}{s} \times (k \times G)$
$= \frac{m + rk}{s} \times G$
$= z \times G$
$= R$

So we have shown that verifying algorithm is correct. In other words, $u \times G + v \times P = R$, so if we get its X-coordinate, we reach $r$.

### Time complexity
After all the above descriptions, we have to answer two questions to prove that the ECDSA is an **effcient** algorithm:

1. How to calculate $k \times G$ in effcient time? (with knowledge of $k$ is a big number)
2. How to calculate $\frac{1}{s}$ in effcient time? (with knowledge of being in a finite field and the prime number of the field is too large)

We first answer the **second question**. From number theory, we know the following:
$s ^ {p - 1} \equiv 1 \pmod{p}$
$gcd(s, p) = 1 \rightarrow s ^ {p - 2} \equiv \frac{1}{s} \pmod{p}$

so we just need to calculate $s^{p - 2}$ for $\frac{1}{s}$, but $p$ is a large number. However this is not a problem since we know a [method](https://www.geeksforgeeks.org/write-an-iterative-olog-y-function-for-powx-y/) for calculating $a^b$ in logarithmic time complexity ($log(b)$ and for our purpose, $log(p - 2)$ which is not large anymore).

For the **first question**, the same technique applies to calculating $k \times G$. Think of the binary representation of 𝑘. For example if we want to calculate $9G$, we can do the following:

$9G = 8G + G = 2^3G + 2^0G$

Since we know how to doubling a point in the curve, starting from point $G$, we double it to get $2G$, double it two more times to get $8G$. Finaly we add a $G$ to it to get to $9G$. So it took only 4 operations instead of blindly adding up $G$ 8 times!

So there is no need to worry about the time complexity of ECDSA.

### Why ECDSA?
| Symmetric | ECC | DH/DSA/RSA |
|----------:|----:|-----------:|
| 80 | 163 | 1024 |
| 112 | 233 | 2048 |
| 128 | 283 | 3072 |
| 192 | 409 | 7680 |
| 256 | 571 | 15360 |

The table above shows how many bits is needed to provide the **same level of security** in each cryptographic method. This raise a question. Thus we can see why we prefer **ECC** over **DH/DSA/RSA** methods. However, **symmetric encryption** methods need much less bits even than **ECDSA**, so why doesn't bitcoin network utilize it?

The answer is simple, symmetric encryption methods need a **shared key** between each pairs of nodes. So in Bitcoin network, for each two nodes we have to have a shared key between them, and this is almost impossible (at least for now)! Because some nodes may never talk to each other directly, however both belong to the network and work properly. So they can't share a key between themselve.

**Note:** **ECC** refers to the broader class of cryptographic algorithms, while **ECDSA** is a specific algorithm within **ECC** used for digital signatures.

## Schnorr Signature

Like ECDSA, **Schnorr** also uses the same private-public key pairs. The only difference is in the signing and verification algorithm, which happens to be a lot **simpler** than ECDSA.

### Sing with Schnorr

Prerequisites:
- Private key: $k$ (integer)
- Public key: $P = k \times G$ (curve point)
- Message: $m$ (integer)

Algorithm:

1. Choose a random number: $z$ (integer)
2. Calculate: $R = z \times G$ (curve point)
3. X-coordinate of $R$: $r$ (integer)
4. Calculate: $s = z + Hash(r||m)k$ (integer)
5. Signature: $(r, s)$ (integer, integer)

In general:

$SIG_{Schnorr} = (private \; key, \; message) = (r, \; s)$

**Note:** In some versions, you might see a different notation instead of $r||m$. However, this does not affect the main idea behind it. We use $r||m$ for simplicity purposes. Making this part more complicated may increase security against certain types of attacks in specific versions.

### Verify with Schnorr

Prerequisites:
- Obtain the public key: $P$ (curve point)
- Obtain signature: $(r, s)$ (integer, integer)
- Obtain massage: $m$ (integer)

Algorithm:

1. Calculate the random point $R$ from $r$ (We will explain how)
2. Assert: $s \times G = R + Hash(r||m) \times P$

In general:

$VER_{Schnorr}(r, \; s) = accept \; or \; reject$

*Question:* How to calculate the random point $R$ from $r$?!

- As $r$ is only the x-coordinate of the curve point $R$, a special consideration is taken into the Schnorr signature proposal to unambiguously obtain any curve point, given only the x-coordinate.

- For any elliptic curve point, for a given x-coordinate, there exist two valid points on the elliptic curve. The difference between these two points is:
- y-coordinates differ in parity (one is even, another is odd)
- y-coordinates differ in the quadratic residue (one has a square root, the other does not)

So between the two points we have, we assume one of them is **valid** and another one would be **invalid** (based on the implementation). Thus, by having the x-coordinate of a point on the curve, we can get the point itself uniquely.

For more details, you can see [bip340](https://github.com/bitcoin/bips/blob/master/bip-0340.mediawiki) implementation. The function `lift_x(x)` is exactly what we discussed in this section. It gets the x-coordinate of a point and returns a point on curve whose x-coordinate is equal to `x`.

### Proof of correctness

Much simpler proof than ECDSA.

By considering:
- m = message
- G = publicly known initial point on the curve
- k = private key
- P = public key
- $s = z + Hash(r||m)k$

We have:
$s \times G = z \times G + Hash(r||m)k \times G$
$s \times G = R + Hash(r||m) \times P$

### Security
- Both Schnorr and ECDSA are widely used digital signature schemes that provide security through the hardness of the **elliptic curve discrete logarithm** problem.

- Specifically, the security of these signature schemes relies on the fact that it is **computationally infeasible** to calculate the private key from the public key in an elliptic curve group.

### Schnorr VS ECDSA
There are some advantages of Schnorr over ECDSA; as mentioned in [BIP340](https://github.com/bitcoin/bips/blob/master/bip-0340.mediawiki):

- **Provable security:** Schnorr signatures are provably secure. In more detail, they are strongly unforgeable under **chosen message attack** (SUF-CMA) in the random oracle model assuming the hardness of the elliptic curve discrete logarithm problem (ECDLP) and in the generic group model assuming variants of preimage and second preimage resistance of the used hash function. In contrast, the best-known results for the provable security of ECDSA rely on stronger assumptions.

- **Smaller signature size** (to provide the same level of security)

- **Non-malleability:** The SUF-CMA security of Schnorr signatures implies that they are non-malleable. On the other hand, ECDSA signatures are inherently malleable; a third party without access to the secret key can alter an existing valid signature for a given public key and message into another valid signature for the same key and message. This issue is discussed in BIP62 and BIP146.

**Note:** This might raise a question: if ECDSA is not secure enough and malleable, isn't it dangerous that the Bitcoin network still uses it? The answer is that ECDSA is susceptible to **chosen plaintext attacks**. This means that if an attacker can choose any message and obtain its signature, they can potentially discover the private key by choosing multiple messages. However, in the case of having a personal wallet with a pair of private and public keys, no one (including an attacker) can force you to sign anything with your private key. This is unlike Google's private key, where an attacker can search for anything and Google would be required to encrypt it using its private key.

- **Faster verification** (Note that faster verification is more important than faster signing. Because signing occurs once, while verification can occur multiple times by different nodes)

- **Linearity:** Schnorr signatures provide a simple and efficient method that enables multiple collaborating parties to produce a valid signature for the sum of their public keys. This is the building block for various higher-level constructions that improve efficiency and privacy, such as multisignatures and others

- For all these advantages, there are virtually no disadvantages, apart from **not being standardized**.

### So why prefer ECDSA over Schnorr?

*Question*: Given all of its benefits, why does Bitcoin utilize ECDSA?

*Answer*: Schnorr was invented by Claus-Peter Schnorr back in the 1980s. He patented it before he published the paper. Because of his patent, the Schnorr signature algorithm did not see any widespread use for decades. In fact, ECDSA’s predecessor, DSA, was created specifically to bypass the Schnorr patent.

### Multisignatures using Schnorr


- By means of an interactive scheme such as MuSig, participants can aggregate their public keys into a single public key which they can jointly sign for. This allows n-of-n multisignatures, which, from a verifier’s perspective, are no different from ordinary signatures, giving improved privacy and efficiency versus CHECKMULTISIG or other means.

- Moreover, Schnorr signatures are compatible with distributed key generation, which enables interactive threshold signatures schemes. These protocols make it possible to realize k-of-n threshold signatures, which ensure that any subset of size $k$ of the set of $n$ signers can sign, but no subset of size less than $k$ can produce a valid Schnorr signature. However, the practicality of the existing schemes is limited: most schemes in the literature have been proven secure only for the case $k - 1 < \frac{n}{2}$

### Multisignature scheme

Schnorr multi-sig creation:

If $P = P_1 + P_2$ is the addition of two public keys (remember curve points can be added together), $z = z_1 + z_2$ is the addition of two random numbers chosen by users, $m$ is the message being signed, then $s = s_1 + s_2$ is a valid signature for aggregate pubic key $P$ and the common message $m$.

$s_1 = z_1 + Hash(r||m)k_1$
$s_2 = z_2 + Hash(r||m)k_2$
$s = s_1 + s_2 = (z_1 + z_2) + Hash(r||m)(k_1 + k_2)$

Schnorr multi-sig verification:
$s \times G = (z_1 + z_2) \times G + Hash(r||m)(k_1 + k_2) \times G$
$= z \times G + Hash(r||m) \times (P_1 + P_2)$
$= z \times G + Hash(r||m) \times P$

Note: If two nodes want to create multi-sig and each one chooses a random $r$ individually, their randoms would not be the same (with high probabilities). To solve this problem, they should agree on a random $r$.

### More details
For more details and to see an implementation of Schnorr signature, you can visit [bip340](https://github.com/bitcoin/bips/blob/master/bip-0340.mediawiki).

## References

https://medium.com/bitbees/what-the-heck-is-schnorr-52ef5dba289f

https://www.redhat.com/en/blog/brief-history-cryptography#:~:text=The%20first%20known%20evidence%20of,place%20of%20more%20ordinary%20ones

https://en.wikipedia.org/wiki/Schnorr_signature

https://en.wikipedia.org/wiki/Elliptic_Curve_Digital_Signature_Algorithm

https://en.wikipedia.org/wiki/Modular_multiplicative_inverse

https://en.wikipedia.org/wiki/Electronic_Signatures_in_Global_and_National_Commerce_Act

https://en.wikipedia.org/wiki/Digital_signature

https://www.geeksforgeeks.org/write-an-iterative-olog-y-function-for-powx-y/

https://github.com/bitcoin/bips/blob/master/bip-0340.mediawiki