### Schnorr Signature

This article continues my previous piece on [ECDSA Digital Signatures](https://hackmd.io/@kEyqkad6QderjWKtcBF5Hg/HkKjQ7StC). If you’ve followed along, you may have noticed that negating the $s$ part of ECDSA signature, i.e verifying $-s$ $\bmod$ $q$ (cyclic prime order) paired with the correct $r$, still verifies as valid for a given message.
I included this test intentionally, as it highlights one of the inherent vulnerabilities of ECDSA signatures: they can be modified by a third party and still pass verification.

This means a third party could take an existing valid signature, modify it, and produce a valid signature for the same message. Even though the altered signature wasn’t generated by the original signer, the signature will be verified as correct. The process is termed as malleability. Highlighting the specifics of why is beyond the scope of this article.

ECDSA Signature malleability poses a vulnerability for legacy Bitcoin Transactions. A third party could tamper with a transaction's signature, but it would still be valid. When any part of a transaction's data changes, its hash, and identifier will change, which means the transaction Identifier can be modified.

Fortunately, this problem has been addressed by moving signatures from transaction data into a separate field known as the "witness" and changing the signature generation and verification algorithm to Schnorr Signatures. Unlike ECDSA, Schnorr Signatures are not malleable. They are also easier to compute and verify, thanks to their linear properties.

In this article, we’ll explore how to generate and verify Schnorr Signatures.

I will skip a key generation, and we will just continue inside the `KeyPair` class defined in [ECDSA Digital Signatures](/vMddCfV6SJC5CgvicPTcNQ).

### Signature generation

#### 1. Generate an Ephemeral Key

Select a random number $k$ which serves as the ephemeral (temporary) key.
This number should be between 0 and the cyclic prime order of the elliptic curve group.

#### 2. Compute $R$ by Multiplying $k$ by the Generator Point $G$

#### 3. Extract $r$ as the x-Coordinate of $R$

From the point $R$ computed in step 2, extract the x-coordinate as $r$.

#### 4. Compute the Message Hash

The message in bytes should be hashed using the SHA-256 hashing algorithm.

This step ensures the message is converted into a fixed-size digest as a 256-bit hash value. This digest represents the message in a form that can be easily processed by the signature algorithm.
Hashing is reproducible as such it is guaranteed that the message will always produce the same hash value.

#### 5. Compute the Challenge $e$

The challenge value $e$ is computed by hashing the concatenation of $r$, The public key $A$'s $x$ coordinate, and the message hash in step 4 using SHA-256.

$$e = SHA256 (r \parallel A.x \parallel message hash)$$

_Where $\parallel$ denotes concatenation._

#### 6. Calculate the Signature $s$ Component

$$s = (k + e * d) \bmod n$$

_Where $n$ is the cyclic prime order of the elliptic curve, and $d$ is the private key._

#### 7. Return $R$ and $s$ pair as the Final Signature

### Implementation in python

class KeyPair:
    .....
    def generate_signature_schnorr(self, message):
        # Generate an ephemeral key (k)
        ephemeral_key = generate_random_number(1, CYCLIC_PRIME_ORDER)

        # Compute R = k * G
        R = ephemeral_key * GENERATOR_POINT

        # Extract the x-coordinate of R
        r = convert_to_bytes(int(R.x) % CYCLIC_PRIME_ORDER)

        # Compute the SHA-256 hash of the message
        message_hash = compute_sha256_hash(message)

        # Compute the challenge e = H(r || pubkey || message_hash)
        e = compute_sha256_hash(r + convert_to_bytes(int(self.pubkey.x)) + message_hash)
        e_int = convert_bytes_to_int(e)

        # Calculate the signature component s = k + e * privkey mod CYCLIC_PRIME_ORDER
        s = (ephemeral_key + e_int * self.privkey) % CYCLIC_PRIME_ORDER

        # Return the signature components (R, s)
        return R, s

### Signature Verification

#### 1. Compute the SHA-256 Hash of the Message

$$ \text{message_hash} = SHA256(\text{message}) $$

#### 2. Destructure the given signature to point $R$ and the $s$ component.
#### 3. Extract the $x$-coordinate of $R$

We extract the $x$-coordinate of the point $R$ and reduce it modulo the order $n$ of the elliptic curve group.

$$R = (r_x, r_y)$$

$$r = r_x \bmod n$$

#### 4. Compute the Challenge $e$

The challenge value $e$ is computed by hashing the concatenation of $r$, The public key $A$'s $x$ coordinate, and the message hash in step 1 using SHA-256.

$$ e = SHA256(r \parallel \text{A.x} \parallel \text{message_hash}) $$

### 5. Verify the Signature

To verify the signature, we check if the following equation holds:

$$ s \cdot G = R + e \cdot \text{pubkey} $$

_Where $G$ is the curve's generator point, $s$ is the signature $s$ component, $R$ is the derived point, $e$ is the computed challenge, and $A$ is the public key._

If the equation holds, the signature is valid; otherwise, it is not.

### Implementation of Schnorr Signature verification

def verify_schnorr(signature, pubkey, message):
    R, s = signature
    # Compute the SHA-256 hash of the message
    message_hash = compute_sha256_hash(message)
    
    # Extract the x-coordinate of R and reduce it modulo the order of the group
    r = convert_to_bytes(int(R.x) % CYCLIC_PRIME_ORDER)
    
    # Compute the challenge e = H(r || pubkey || message_hash)
    e = compute_sha256_hash(r + convert_to_bytes(int(pubkey.x)) + message_hash)
    e_int = convert_bytes_to_int(e)
    
    # Verify the signature: check if s * G == R + e * pubkey
    P = s * GENERATOR_POINT
    Q = R + (e_int * pubkey)

    return P.x == Q.x and P.y == Q.y

### Code Implementation that tests the Schnorr signature signing and verification

def verification_test_schnorr(signature, pubkey, message_bytes):
    print("Schnorr Signature Verification test")
    R, s = signature
    # Test 1: verifies the malleated signature s+1
    is_valid_modified_s = verify_schnorr((R, (s+1) % CYCLIC_PRIME_ORDER), pubkey, message_bytes)
    print(f"Modified s+1 Signature valid: {is_valid_modified_s}")

    # Test 2: verifies the malleated signature -s
    is_valid_modified_neg_s = verify_schnorr((R, (-s % CYCLIC_PRIME_ORDER)), pubkey, message_bytes)
    print(f"Modified -s Signature valid: {is_valid_modified_neg_s}")

    # Test 3: use Wrong R
    R_wrong =  generate_random_number(1, CYCLIC_PRIME_ORDER) * GENERATOR_POINT
    is_valid_wrong_R = verify_schnorr((R_wrong, s), pubkey, message_bytes)
    print(f"Wrong R part of Signature valid: {is_valid_wrong_R}")

    # Test 4: verify correct signature
    is_valid = verify_schnorr(signature, pubkey, message_bytes)
    print(f"Actual Signature is valid: {is_valid}")

if __name__ == "__main__":
    ....
    # Schnorr Signature Test
    schnorr_signature = key1.generate_signature_schnorr(message_bytes)
    verification_test_schnorr(schnorr_signature, key1.get_pubkey(), message_bytes)

Schnorr signaturesis easy and linear to generate and verify.
The signature scheme has been standardized and specified in a Bitcoin improvement proposal [BIP-340](https://github.com/bitcoin/bips/blob/master/bip-0340.mediawiki).
It has been also adopted as part of an upgrade to the Bitcoin protocol.

Thanks for reading.