What are the implications of Schnorr signatures?

Question

Adam Back (adam3us) explained in March, 2014, but it is all math. There's another short post with advantages, though.

This answer on crypto.SE claims that Bitcoin considered using Ed25519 which is based on Schnorr signatures, but decided against it. Even if it is not going to get used, I'd still like to know the implications.

There's a pull request adding them to libsecp256k1. [edit 2019: that pull request used a flawed approach]

Gavin mentioned them on his wish-list for Bitcoin.

Answer 1

Warning: I've never actually worked with the Schnorr signature scheme. The following is my analysis based on reading the Wikipedia article, the ed25519 page, and some discussions between devs in #bitcoin-dev.

Likely Changes

1. Changed op code behavior: we will need an op code to check Schnorr signatures. With a hard fork, we can redefine op_checksig and op_checksigverify to also check Schnorr signatures. With a soft fork, we can redefine one of the reserved no-op op codes to check Schnorr signatures.

2. Increased P2SH usage (maybe): I think it's highly unlikely that a new address format will be introduced to do the same thing for pubkey scripts paying Schnorr public keys that P2PKH does for ECDSA public keys. That means people who want an address to use Schnorr even with just one key (non-multisig) will have to use P2SH. Of course, for applications that don't need addresses (like for mining or when using the BIP70 payment protocol), they can just use op_checksigverify_schnorr (or whatever) directly in their pubkey scripts.

3. Smaller multisig transactions: one of the most widely touted advantages of the Schnorr scheme is that it can allow multiple signers to combine their signatures into a single signature which can be authenticated against a single public key created by all the authorized parties. This accomplishes the same thing current Bitcoin multisig does but uses fewer bytes. This may be especially useful if dozens or hundreds of signatures are required, such as in a crowdfunding situation. Note: if I understand correctly, this is also possible also with ECDSA, but in a less flexible way. (2018 note: there's now a paper out that details how to do script-less scripts on ECDSA, including 2-of-2 multisig)

4. Slightly smaller for all transactions: assuming Bitcoin uses the ed25519 curve, which has a similar key strength to the secp256k1 ECDSA curve Bitcoin currently uses, compressed Schnorr public keys and signatures will be (respectively) 32 bytes and up to 64 bytes compared to current compressed Bitcoin secp256k1 public keys and (non-compressed) signatures that are 33 bytes and up to 75 bytes.

5. Plausible deniability for multisig: using Schnorr threshold signatures it may be easier to prevent multiple signers or third-parties from knowing who else signed or didn't sign. That's because the individual signatures are merged into a unified signature that doesn't directly reveal who signed it. This can be used in situations where the signers are afraid of reprisals for spending funds in a particular way.

6. Plausible deniability of authorized parties using a third-party organizer (which doesn't need to be trusted with private keys), it's possible to prevent signers from knowing whether their private key is part of the set of signing keys. Although not directly relevant to Bitcoin transactions, I seem to recall[1] Greg Maxwell saying he'd like to see this property used for distributed forum moderation: choose a bunch of senior forum members, get a public key from each of them, create a threshold public key from some of the individual public keys, and then let individuals submit a signature when they think a post should be removed. The third-party organizer (probably an automated program) will combine the signatures without leaking whose signature actually contributed towards meeting the threshold. If nobody knows whose signature actually matters and the pool of possible moderators is large, effective reprisals against moderators become very expensive. [1]: #bitcoin IRC about 4 months ago; unfortunately that chatroom is not publicly logged.

7. Theoretical better security properties: the experts agree general Schnorr signatures have better theoretical security properties than equivalent ECDSA signatures. The most notable of these improvements is that the hash function used in Schnorr doesn't need to be as collision resistant as the hash function used in ECDSA. (Bitcoin would likely use the same hash function for Schnorr that it uses for ECDSA: SHA256.) Also, the ed25519 page linked above describes several ways it is resistant to side-channel attacks, which can allow hardware wallets to operate safely in less secure environments.

8. Faster signature verification: it likely takes fewer CPU cycles to verify an ed25519 Schnorr signature than a secp256k1 ECDSA signature. This is probably only a tiny improvement for Bitcoin: Bitcoin Core verifies signatures before adding a transaction to its mempool. When a block is received containing transactions already in the local mempol, Bitcoin Core does not re-verify those transactions, so as long as the local node and the mining node have identical mempools, no signature verifications need to be performed. (Recall the coinbase transaction doesn't have a signature.) However, signature verification is currently a bounding factor for nodes during initial blockchain download (assuming a high-speed connection and Bitcoin Core 0.10.0), so "faster would be better."

9. Multi-crypto multisig: with two (slightly) different cryptosystems to choose from, high-security users can create 2-of-2 multisig pubkey scripts that require both ECDSA and Schnorr signatures, so their bitcoins can't be stolen if only one cryptosystem is broken. Unless we hardfork in Schnorr (see point #1), they won't be able to use standard op_checkmultisig---but they can do something like <ecdsa pubkey> OP_CHECKSIGVERIFY <schnorr pubkey> OP_CHECKSIGVERIFY_SCHNORR

Uncertainties (To Me)

10. Maybe changed TXIDs: I'm not familiar enough with Schnorr signatures to know how they might be malleable (changeable by third-parties without invalidating them), but crypto expert Adam Back seems to think they'd be pretty malleable. His solution would be to change how TXIDs are calculated from hash(<whole transaction>) to hash(<almost everything except the signature>). This would fix some current malleability-based problems, such as slow micropayment channel creation, but it also be a major hard fork that affects effectively all Bitcoin software. The last fork of that scale---the soft-fork P2SH implementation---still doesn't have support for it from all Bitcoin programs after three years of discussion, two years of implementation, and fairly widespread use.

• Public key recovery from signatures: I don't know whether a Schnorr public key can be recovered from a Schnorr signature the way an ECDSA pubkey can be recovered from an ECDSA signature. This could be important: the Bitcoin Core verifymessage RPC uses key recovery to verify messages signed with the signmessage RPC or by another client's sign message implementation. (Note: this point left unnumbered because it was added after the original posting.)

Non-Changes

Just to be clear, here are some things that don't change.

11. Deterministic signatures: there has been a drive towards deterministic ECDSA signatures in Bitcoin software. For example, Bitcoin Core will begin using them in the upcoming 0.10.0 release. Schnorr signatures can also be generated deterministically. With deterministic signatures, you don't need a high-quality source of entropy (randomness) to create secure signatures. However, you do still need high-quality entropy to generate private keys or root seeds (see point below).

12. HD wallets: it looks to me like the hierarchical deterministic (HD) key generation protocol will work for Schnorr key pairs with a few small modifications. You can even use the same root seed for both ECDSA and Schnorr hierarchies.

13. Key (address) reuse: as with properly-implemented ECDSA, it's possible to securely create multiple Schnorr signatures for different transactions, meaning it's secure to receive multiple outputs to the same address or public key. This is in contrast to some signature schemes which only allow you to securely use a one signature per public key. However, key reuse can still be less secure than using unique keys for each transaction, and key reuse will always be much less private for you and your trading partners.

Priority

Just as a matter of my opinion: Schnorr seems to provide some nice advantages over ECDSA for power users, but nobody seems to be begging for those features---so adding Schnorr signatures is probably low priority. I'd guess that Schnorr signature support might be one of the first improvements that will be fully tested in a sidechain (PDF link) before being ported back to Bitcoin.

P.S. Sorry for the long post, but thanks for asking such a fun question!

Answer 2

Yes you can do public key recovery with EC Schnorr. Consider

R = kG, [r = R.x, s = k + H(r, m)d], Q = dG

verify:

sG = ?R + H(r, m)Q

recovery:

sG = kG + H(r, m) dG = R + H(r, m)Q

so

Q = 1 / H(r, m) * (sG - R).

(And to compute R from r if R is point-compressed, R = (r,f(r)) R' = (r,-f(r)) and try both R and R' by checking if the signature is valid with the resultant public key).

Answer 3

The primary design goal for DSA was to avoid infringing the Schnorr patent. Now that the patent has expired, there aren't really any good mathematical reasons to go with DSA. With Schnorr, the algorithm and analysis are simpler and often more efficient. It's also easier to split Schnorr private keys, create threshold variants, etc. However, DSA and ECDSA are standards, and have been for a while. As a result, library implementations are everywhere. You can find hardware security module support, etc. Someday the same will hold of either Ed25519 or some other Schnorr variant. People are unlikely to standardize new DSA variants. But for the moment ECDSA is still the algorithm to use if you want something standard and widely supported.