One of the speakers at this year’s Blockchain Protocol Analysis and Security Engineering 2018 conference (BPASE ‘18) was Blockstream’s Pieter Wuille, who spoke about Schnorr signatures and their usage in Bitcoin.
Schnorr signatures have long been of interest for Bitcoin because of their numerous advantages, which Wuille discusses in his BPASE talk. They produce a smaller on-chain size, they support faster validation, and they have better privacy. Schnorr signatures natively allow for combining multiple signatures into one through aggregation. Furthermore they permit more complex spending policies, including k-of-n and more, to be represented as a single signature for a single key.
However, signature aggregation also has its challenges. One of the biggest that Wuille faced was the rogue-key attack, where a participant steals funds using a specifically constructed key. Although this is trivially solvable for simple multi-signatures, using an enrollment procedure where the keys sign themselves, supporting it across multiple inputs of a transaction requires plain public-key security, meaning there is no setup.
An additional attack, dubbed “Russell’s attack” after its discoverer Russell O’Connor, was discovered for multi-party schemes where a party could claim ownership of someone else’s key and so spend their other outputs; as Wuille says, “Attack models in multi-party schemes can be very subtle.”
In his BPASE talk, Wuille extensively discusses these issues and their solution, which refines the Bellare-Neven scheme. Wuille’s seminar also covers the performance improvements that were implemented for the scalar multiplication of the Bellare-Neven scheme and how they enable batch validation on the blockchain. A pair of BIPs are in process to make these advances a reality for Bitcoin.
Wuille’s BPASE ‘18 Schnorr Signatures seminar is now available online.
Further expansions of Schnorr multi-signatures and their applicability for key aggregation can be found in the MuSig blog post and the paper “Simple Schnorr Multi-Signatures with Applications to Bitcoin” by Gregory Maxwell, Andrew Poelstra, Yannick Seurin, and Pieter Wuille.