What are the implications of Schnorr signatures? 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.
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


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.
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.
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)
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.
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.
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.
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.
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."
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 &lt;ecdsa pubkey&gt; OP_CHECKSIGVERIFY &lt;schnorr pubkey&gt; OP_CHECKSIGVERIFY_SCHNORR


Uncertainties (To Me)


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(&lt;whole transaction&gt;) to hash(&lt;almost everything except the signature&gt;).  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.


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).
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.
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!