Signature Verification

Signature verification can happen off-chain and on-chain. Any oracle-validator can do off-chain validation to be sure the submission makes sense. On-chain signature is done by a smart contract equipped with the logic required to validate Secp256k1 or Ed25519 signatures.

Off-chain Verification

The FROST group leader can verify the validity of the signature before submitting it to the on-chain contract to avoid burning gas in vain. If the signature verification resolves to true, the leader submits it. Otherwise, the leader launches another round of signing to get enough valid partial signatures from the participants for the threshold signature to be valid.

Rust implementation.

let threshold_signature = aggregator.aggregate();

let verified = threshold_signature.verify(&p_5_group_key, &message_hash);

On-Chain Verification

Bridge smart contracts have the logic to verify threshold signatures signed with FROST. If the signature appears to be valid, the transaction is processed by the contract. Otherwise, the transaction is reverted. Let's see how the FROST signature can be verified on EVM-compatible chains.

EVM chains use the same $secp256k1$ elliptic curve as Bitcoin. The formula of the curve is $y^2=x^3+7$. Schnorr's public and private keys are compatible with secp256k1 used with ECDSA (Elliptic Curve Digital Signature Algorithm).

ECDSA is characterized by the following properties:

Private key: any random number. In Bitcoin & EVM chains it is represented by an unsigned integer $1-2^{256}$ uint256 or bytes32;

Public Key: is a number calculated from the private key with an irreversible algorithm making it impossible to restore the private key from the public one. In EVM chains, public keys are 20 bytes long and can be represented by a uint160.

Signature: is the hash of the $M$ message plus the signer's private key.

k is a random number between $1$ and $n-1$, where $n$ is the group order of the curve. For $Secp256k1$ n = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141. $k$ must be generated for each signature and never reused. If reused, attackers may compare the initial messages and their signatures and restore the original private key. This is why $k$ is a nonce or a "number used once."

Numbers r and s uniquely represent the signature. They are calculated at the signature generation stage. If either $r$ or $s$ equals zero, the nonce $k$ must be regenerated, and both $r$ and $s$ recomputed.

z is used to hold the hash of the signed message.

Solidity constants

// Group order of the Secp256k1 curve `n`
uint256 constant public Q =
    // solium-disable-next-line indentation
    0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141;

On-chain Signature verification

1. Check the public key greater than Q/2

Solidity

uint256 constant public HALF_Q = (Q >> 1) + 1;
...
require(signingPubKeyX < HALF_Q, "Public-key x >= HALF_Q");

2. Verify that the signature is less than Q

Solidity

uint256 signature = _signature;
require(signature < Q, "signature must be reduced modulo Q");

3. Check that no trivial inputs were provided:

Solidity

// solium-disable-next-line indentation
address nonceTimesGeneratorAddress = _nonceTimesGeneratorAddress;
uint256 signingPubKeyX = _signingPubKeyX;
uint256 signature = _signature;
uint256 msgHash = _msgHash;
require(nonceTimesGeneratorAddress != address(0) && signingPubKeyX > 0 &&
      signature > 0 && msgHash > 0, "no zero inputs allowed");

4. Calculate the message challenge e

Solidity

// solium-disable-next-line indentation
uint256 msgChallenge =
   // solium-disable-next-line indentation
   uint256(keccak256(abi.encodePacked(
     signingPubKeyX, // uint256
     pubKeyYParity,  // uint8
     msgHash,        // uint256
     nonceTimesGeneratorAddress // address
     ))
   );

5. Calculate the recover address:

Solidity

address recoveredAddress = ecrecover(
   // solium-disable-next-line zeppelin/no-arithmetic-operations
   bytes32(Q - mulmod(signingPubKeyX, signature, Q)),
   // https://ethereum.github.io/yellowpaper/paper.pdf p. 24, "The
   // value 27 represents an even y value and 28 represents an odd
   // y value."
   (pubKeyYParity == 0) ? 27 : 28,
   bytes32(signingPubKeyX),
   bytes32(mulmod(msgChallenge, signingPubKeyX, Q))
);

6. Compare the expected & the recovered address:

If the two addresses match, the signature is valid.

Solidity

return nonceTimesGeneratorAddress == recoveredAddress;