Bitcoin Stack Exchange is a question and answer site for Bitcoin users, developers, and enthusiasts. It only takes a minute to sign up.
Sign up to join this community
How do BLS signatures (or other pairing-based schemes) compare to Schnorr signatures in terms of cryptographic assumptions?
Is it faster to verify, say 100 (non-interactively) aggregated BLS signatures than 100 aggregated Schnorr signatures?
Apart from relying on different assumptions, why wouldn't BLS signatures be interesting for Bitcoin?
How do BLS signatures (or other pairing-based schemes) compare to Schnorr signatures in terms of cryptographic assumptions?
BLS needs a pairing-compatible elliptic curve, which imposes additional structure on the curve. The elliptic curve used for cryptography in Bitcoin today (both for ECDSA and Schnorr), secp256k1, is not pairing-compatible.
This additional structure may be concerning. See it this way: normally when picking an elliptic curve for cryptographic purposes, there are a number of "gotchas" to avoid - properties that, if present, are either known or suspected to aid attackers to break its security. One of those properties is having a "low embedding degree":
secp256k1 has embedding degree 19298681539552699237261830834781317975472927379845817397100860523586360249056 (exactly 1/6 of the number of points on the curve).
Pairing-compatible curves however need a relatively small embedding degree; small enough to be tractable for computation (because signature verification actually involves computing this embedding), but also large enough to not result in making private keys easy to find. Currently popular pairing curves use embedding degree 12.
So, BLS requires curves that are from a traditional perspective "risky". It's not that this risk is unmanageable: obviously actual curves are constructed in such a way that there is no way to exploit this structure, but it is walking a fine line. The concern is that perhaps in the future other ways are discovered to exploit it. And us having selected parameters such that all known attacks fail isn't sufficient when new attacks get discovered.
Of course, that's not fundamentally different from other elliptic curve security, or cryptographic security in general. We always select parameters/curves/... in such a way that all known ways of attacking fail, and when new attacks get discovered, those parameters may not be sufficient anymore. But in the case of generic ECC, that's just one set of attacks to avoid. In the case of pairing-based cryptography, there is an entirely separate added newer set of attacks to worry about as well.
As for what this means for Bitcoin: I don't know. The question is just whether the Bitcoin community, as a whole, is ok with this added set of security assumptions that BLS would bring. And it isn't sufficient that it's optional; if (hypothetically) I personally would be uncomfortable with BLS's security outlook, I wouldn't want a large fraction of the BTC supply to become subject to it, as a break of pairing-based cryptography may threaten the currency's value overall, including my non-BLS-encumbered coins. So I believe this means the bar for adding new security assumptions is fairly high.
Is it faster to verify, say 100 (non-interactively) aggregated BLS signatures than 100 aggregated Schnorr signatures?
They're a few times slower per non-batched signature verification (aggregated or not). Batching (the act of verifying multiple pubkey/signature/message triplet simultaneously, only learning whether all or not all of them are valid) with sufficiently large batches however counteracts most of that slowdown.
Apart from relying on different assumptions, why wouldn't BLS signatures be interesting for Bitcoin?
They'd certainly be interesting. Lots of complications around multisignatures (see all the MuSig schemes) and multi-party spending in general are largely non-existent for BLS signatures. They're smaller too. The question is mostly one around acceptability of the added security assumptions, in my opinion.
There is one other (rather weak) argument against them I'm aware of. Schnorr (and ECDSA) signatures support adaptor signatures. These are a construction that makes it possible to use the publication of a signature to trigger revealing a pre-agreed secret, and are the basis for unlinkable atomic swap protocols that are indistinguishable from normal payments, and for PTLCs (a more private replacement for Lightning's HTLCs). BLS signatures however inherently don't support adaptor signatures—there is just no space in them to reveal anything. This means that in a world where everyone has migrated to BLS for nearly everything, these adaptor signature constructions would need to stick to Schnorr/ECDSA, and thus stand out and no longer be indistinguishable from normal payments.
