This post presents an implementation to efficiently verify aggregated Schnorr signatures.
Note that to make aggregated Schnorr signatures useful, and prevent having to store the combinatoric explosive number of possible aggregated public keys onchain, the key aggregation of the signers’ public keys must be performed onchain as well.
The implementation can be found in Chronicle Labs’ new Scribe oracle contract. Via using Schnorr signatures we were able to reduce gas costs by ~60% compared to our current Median oracle. A further optimistic Scribe flavor with onchain fault resolution has nearconstant gas usage for a variable amount of signers.
Motivation
There are currently two ways to implement multisignatures in smart contracts, with each having its drawbacks regarding gas usage:
 Using sets of ECDSA signatures
 Using BLS signatures on the alt_bn128 curve
Using sets of ECDSA signatures has linear runtime and calldataload as each signature needs to be pushed and verified onchain.
BLS signatures are expensive in terms of gas usage. Furthermore, using alt_bn128 is discouraged due to its decreasing security.
Schnorr Signature Scheme
Note that the following paragraphs are mostly copied from Scribe’s Schnorr Specification.
Terminology

H()
 Keccak256 hash function 
‖
 Concatenation operator, defined asabi.encodePacked()

G
 Generator of secp256k1 
Q
 Order of secp256k1 
x
 The signer’s private key as typeuint256

P
 The signer’s public key, i.e.[x]G
, as type(uint256, uint256)

Pₓ
 P’s x coordinate as typeuint256

Pₚ
 Parity ofP
’sy
coordinate, i.e.0
if even,1
if odd, as typeuint8

m
 Message as typebytes32
. Note that the message SHOULD be a keccak256 digest 
k
 Nonce as typeuint256
Signing

Select a cryptographically secure
k ∊ [1, Q)

Compute
R = [k]G

Derive
Rₑ
being the Ethereum address ofR
Let
Rₑ
be the commitment 
Construct
e = H(Pₓ ‖ Pₚ ‖ m ‖ Rₑ) mod Q
Let
e
be the challenge 
Compute
s = k + (e * x) mod Q
Let
s
be the signature
=> The public key P
signs via the signature s
and the commitment Rₑ
the
message m
A Solidity implementation can be found here.
Verification
 Input :
(P, m, s, Rₑ)
 Output:
True
if signature verification succeeds,false
otherwise

Compute challenge
e = H(Pₓ ‖ Pₚ ‖ m ‖ Rₑ) mod Q

Compute commitment:
[s]G  [e]P  s = k + (e * x)
= [k + (e * x)]G  [e]P  P = [x]G
= [k + (e * x)]G  [e * x]G  Distributive Law
= [k + (e * x)  (e * x)]G  (e * x)  (e * x) = 0
= [k]G  R = [k]G
= R  Let ()ₑ be the Ethereum address of a Point
→ Rₑ
 Verification succeeds iff
([s]G  [e]P)ₑ = Rₑ
A Solidity implementation can be found here.
Key Aggregation for Multisignatures
To efficiently aggregate public keys onchain, the key aggregation
mechanism for aggregated signatures is specified as the sum of the public
keys:
Let the signers' public keys be:
signers = [pubKey₁, pubKey₂, ..., pubKeyₙ]
Let the aggregated public key be:
aggPubKey = sum(signers)
= pubKey₁ + pubKey₂ + ... + pubKeyₙ
= [privKey₁]G + [privKey₂]G + ... + [privKeyₙ]G
= [privKey₁ + privKey₂ + ... + privKeyₙ]G
Note that this aggregation scheme is vulnerable to roguekey attacks!
To prevent such attacks, it MUST be verified that participating
public keys own the corresponding private key.
Note further that this aggregation scheme is vulnerable to public keys with
linear relationships. A set of public keys A
leaking the sum of their private
keys would allow the creation of a second set of public keys B
with
aggPubKey(A) = aggPubKey(B)
. This would make signatures created by set A
indistinguishable from signatures created by set B
.
To prevent such issues, it MUST be verified that no two distinct
sets of public keys derive to the same aggregated public key. Note that
cryptographically sound created random private keys have a negligible
probability of having a linear relationship.
Other Security Considerations
Note that the signing scheme deviates slightly from the classical Schnorr
signature scheme.
Instead of using the secp256k1 point R = [k]G
directly, this scheme uses the
Ethereum address of the point R
. This decreases the difficulty of
bruteforcing the signature from 256 bits
(trying random secp256k1 points)
to 160 bits
(trying random Ethereum addresses).
However, the difficulty of cracking a secp256k1 public key using the
babystep giantstep algorithm is O(√Q)
, with Q
being the order of the group.
Note that √Q ~ 3.4e38 < 128 bit
.
Therefore, this signing scheme does not weaken the overall security.
Important Optimizations
Elliptic Curve Addition
The key aggregation computes the sum of a set of secp256k1 points. In order to save computationheavy conversions from Jacobian coordinates  which are used for point addition  back to Affine coordinates  which are used to store public keys , one can use the madd2007bl addition formula expecting one point’s z
coordinate to be 1. Effectively allowing to add a point in Affine coordinates to a point in Jacobian coordinates.
This optimization enables computing the sum of secp256k1 points in an efficient manner by only having to convert the end result from Jacobian coordinates to Affine coordinates. Note that to convert from Jacobian coordinates to Affine coordinates the modular inverse of the z
coordinate needs to be computed.
A Solidity implementation can be found here.
Elliptic Curve Multiplication
The Schnorr verification procedure needs to verify an elliptic curve multiplication. This computation can be done performantly by misusing the ecrecover
precompile. For more info, see Vitalik’s ethresear.ch post and Scribe’s documentation.