# Schnorr signature verification ecrecover hack
This idea is based off Vitalik's post here: https://ethresear.ch/t/you-can-kinda-abuse-ecrecover-to-do-ecmul-in-secp256k1-today/2384

However, instead of using ecrecover to do ECMUL, it can be hacked to cheaply verify a Schnorr signature.

## Background: Schnorr

### Signing

Given message `m`, private key `x` and hash-to-scalar function `h`, pick random value `k` from field. `G` is the curve generator.

Also define function `address()` which returns the 20-byte Ethereum address given a point. (Note: this is needed only for the hack)

R = G*k
e = h(address(R) || m)
s = k + x*e
Signature = (e, s) or (R, s)

### Verification

Given signature `(R, s)`, message `m` and public key `P`

e = h(address(R) || m)
R' = G*s - P*e
check R == R'

or, given signature `(e, s)`

R = G*s - P*e
e' = h(address(R) || m)
check e' == e

## Background: ecrecover

Ethereum `ecrecover` returns an address (hash of public key) given an ECDSA signature.

Given message `m` and ECDSA signature `(v, r, s)` where `v` denotes the parity of the y-coordinate for the point where x-coordinate `r`

ecrecover(m, v, r, s):
R = point derived from r and v
a = -G*m
b = R*s
Qr = a + b
Q = Qr * (1/r)
Q = (1/r) * (R*s - G*m) //recovered pubkey

Ethereum's ecrecover returns the last 20 bytes of the keccak256 hash of the 64-byte public key (see https://github.com/ethereum/go-ethereum/blob/eb948962704397bb861fd4c0591b5056456edd4d/crypto/crypto.go#L275)

## The hack

Given signature `(R, s)`, message `m` and public key `P` we can feed values into ecrecover such that the returned address can be used in a comparison to the challenge.

calculate `e = H(address(R) || m)` and `P_x = x-coordinate of P`

pass:
`m = -s*P_x`
`v = parity of P`
`r = x-coordinate of P`
`s = -e*P_x`

then:

ecrecover(m=-s*P_x, v=0/1, r=P_x, s=-e*P_x):
P = point derived from r and v (public key)
a = -G*(-s*P_x) = G*s*P_x
b = P*(-m*P_x) = -P*e*P_x
Q = (1/P_x) (a+b)
Q = (1/P_x)(G*s*P_x - P*e*P_x)
Q = G*s - P*e  // same as schnorr verify above

the returned value is `address(Q)`.
- calculate `e' = h(address(Q) || m)`
- check `e' == e` to verify the signature.

## solidity

//SPDX-License-Identifier: LGPLv3
pragma solidity ^0.8.0;

contract Schnorr {
  // secp256k1 group order
  uint256 constant public Q =
    0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141;

  // parity := public key y-coord parity (27 or 28)
  // px := public key x-coord
  // message := 32-byte message
  // e := schnorr signature challenge
  // s := schnorr signature
  function verify(
    uint8 parity,
    bytes32 px,
    bytes32 message,
    bytes32 e,
    bytes32 s
  ) public pure returns (bool) {
    // ecrecover inputs are (m, v, r, s);
    bytes32 sp = bytes32(Q - mulmod(uint256(s), uint256(px), Q));
    bytes32 ep = bytes32(Q - mulmod(uint256(e), uint256(px), Q));

    require(sp != 0);
    // the ecrecover precompile implementation checks that the `r` and `s`
    // inputs are non-zero (in this case, `px` and `ep`), thus we don't need to
    // check if they're zero.
    address R = ecrecover(sp, parity, px, ep);
    require(R != address(0), "ecrecover failed");
    return e == keccak256(
      abi.encodePacked(R, uint8(parity), px, message)
    );
  }
}

## References/notes

- Chainlink has already implemented a similar idea here: https://github.com/smartcontractkit/chainlink/blob/bb214c5d7ec172de400a72a1d8851ff639c979d2/evm/v0.5/contracts/dev/SchnorrSECP256K1.sol however their implementation uses more than just `ecrecover` and `keccak256`; it also checks that the signing public key's x-coordinate is less than the half-order, amongst other checks. however, I don't think that the `s < Q` check is required; it appears to have been in the yellow paper but not in the actual ecrecover implementation used by Ethereum.

- If you're using this in production, you probably want to add `block.chainId` to the challenge to prevent replay attacks.

- canonical ecrecover implementation:
- https://github.com/ethereum/go-ethereum/blob/8a134014b4b370b4a3632e32a2fc8e84ee2b6947/crypto/secp256k1/secp256.go#L105
- https://github.com/bitcoin-core/secp256k1/blob/aa5d34a8fe99b1f69306be20819f337dbd3283db/src/modules/recovery/main_impl.h#L87