A quick review of different consensus changes on the mailing list, with advantages, drawbacks, among others Schnorr, Taproot, MAST, Graftroot, new sighashes.
To get started, a high-level list of Schnorr advantages like :
- reduce onchain footprint
- n-of-n key aggregation
- k-of-n key aggregation
- batch validation
- better security proof than ECDSA
A gentle introduction to Schnorr by Pieter Wuille at Scaling Bitcoin 2016 or this one by Christopher Allen with more cryptographic litterarure references. Another good explanation by CryptoAdvance with more ECC context.
You can find a discussion of Schnorr security proofs on Adam Gibson blog.
Hurdles and challenges of getting Schnorr right have been laid out in this sipa conference.
Schnorr has been further reviewed on bip-schnorr announcement ml thread
Beyond simple signatures, multiple applications are explored like efficient pubkey aggregation for multi-sig, scriptless scripts protocols, atomic signatures exchange, anonymous credentials exchange via blind signatures and maybe secure threshold sigs schemes.
Other new signature schemes have been discussed inside the community, most notably the Boneh-Lynn-Shacham one. You can find a summary of pros and cons in this core-dev meetup here and here, BLS signatures are more space-efficient but more computation-intensive and security assumption is looser. If you want to go deeper an implementation of BLS signature algorithms has been made by the Chia team.
2-party aggregated pubkeys are also workable on ECDSA but far harder to implement. Further discussion on the LN mailing list about 2p ECDSA
Schnorr is under implementation in bitcoin-core ECC library, libsecp256k1. You can find a bip-schnorr rust implementation of some applications like aggregated sigs, accountable sigs and threshold sigs.
If Schnorr is deployed, we may build on top of further applications like cross-input signature aggregation, non-interactive signature aggregation per-block, generalised taproot (more efficient taproot in non-cooperative case).
Lightning will reap a huge bonus from Schnorr adoption on the base layer. To go through a simple introduction.
More in-depth:
- how to eliminate payment hash correlation ? Switch to payment-points/scalar locks and theoretical discussion
- how to enable Atomic Multi-Payment path while keeping the Proof-of-Payment ?
- what interactions between LN-invoices and scriptless scripts ?
- how to enable stuckless payments without resorting to script-update on the whole network or use sha256 midstate ?
- what about more expressive e2e contracts like escrow or even combination of payment-points type of contract
A quick skim about how LN transactions could look like and even further ideas to redesign LN transactions in a post-schnorr world
Although the MAST idea has been merged into Taproot, it's important to understand MAST context to well understand Taproot design.
MAST is a combination of a compiler construction (an AST) and a cryptographic one (a Merkle Tree) to gain both privacy and expressivity for Script. While it has been historically known as Merklized Abstract Syntax Tree, the backcronym Merklized Alternative Script Trees has been proposed to reflect idea refinements.
A gentle introduction by David Harding or a more-in-depth introduction at a core-dev meetup.
Merkle Trees in themselves have been hard to get right as some vulnerabilities affecting the one used in Bitcoin consensus have shown.
The MAST debate has been focused on the template-vs-generic approach for script upgrades.
Mark Friedenbach proposed a script-based approach relying on the combination of modular mechanism to enable powerful MAST:
- BIP 98 : Fast Merkle Tree (maybe relevant in the discussion about Taproot merkle tree) and ml thread
- BIP 116 : MERKLEBRANCHVERIFY
- BIP 117 Tail Call Execution Semantics and ml thread
Johnson Lau on a templated-design a la P2SH via a Segwit bump version.
- BIP 114 Merkelized Abstract Syntax Tree and ml announcement (with examples of further upgrades like re-enabling OP_CAT or OPMUL)
Further debtate on both alternatives and taproot interaction during this core-dev meetup.
MAST-specific advantages for Lightning:
- in cooperative closing, make output and spending indistinguishable from other users
- feature-gating of advanced feature (like SIGHASH_NOINPUT) inside MAST scripts
Announcement on the ml and following design discussion.
A security proof of taproot has been written by Andrew Poelstra, spec has been drafted and announced on the ml around May 2019.
Some engineering sheenigans of taproot/schnoor have been raised in this talk by Jonas Nick.
Already covered in MAST and Schnorr sections.
- March 2018, with issues in coordinating both OP_RETURNVALID (aka OP_SUCCESS)and signatures aggregation
- December 2018, more on OP_SUCCESS design
Optech workshop material is a great source, it plays with Miniscript, a language to write subset of Bitcoin Script in a structured way, enabling analysis, composition, generic signing... Some work has been done by James Chiang to extend Miniscript for Taproot.
Finally, some slides on how to review cryptosystems, among other advices, aiming for 5 properties: accountability, usability, privacy, efficiency and composability.