Walletwasabi: [Mega Thread] Implement SegWit v1 Taproot

[MaxHillebrand]

Implement SegWit v1 Taproot

Introduction

This is a mega thread to summarize the efforts of upgrading Wasabi Wallet to segregated witness version 1, and implement the taproot functionality. Based on this we will open many small issues with specific feature requests and bug reports, that will be implemented in small independent pull requests. This thread is for high level discussion, to emphasize the advantages and cautions of taproot, as well as to organize a ToDo list and to keep track of the research and implementation progress.

Wasabi has from day 1 been SegWit v0 compatible, pioneering this new concept and the Bech32 address type, even to an extend of not supporting legacy and wrapped SegWit. Now it is time to upgrade to v1, and continue pushing cutting edge industry best practices.

Background

Taproot proposes a new SegWit version 1 output type that combines Schnorr signatures, Merkle branches (BIP 114 & BIP 117) and Tapscript OP_CODES. Currently, these BIPs are in rigorous peer review, and eventually if consensus is reached, they will be proposed for a soft fork upgrade. For more information on the technology, read the above mentioned BIPs, and partake in the Bitcoin OpTech taproot workshop. The three BIPs now have an open pull request with a formal proposal. The code reference implementation is also opened.

There has been a very thorough previous discussion on how to add MuSig to Wasabi CoinJoins.

Motivation

Taproot provides privacy, scalability, and usability benefits compared to incumbent solutions.

Privacy Benefits

Wasabi Wallet is a privacy first wallet, in every design and implementation decision, we must prioritize privacy above all else, and taproot offers multiple privacy benefits:

MuSig public key and signature aggregation

MuSig is a provable secure multisignature scheme based on Schnorr signatures. It specifies the non-interactive aggregation of n public keys, into one single public key; as well as an interactive aggregation of n signatures, into one single aggregated signature, which is valid for the aggregated public key. To an outside observer, the aggregated public key and signature look indistinguishable from the non-aggregated. Thus it is no longer obvious that a given UTXO is locked and redeemed with the shared ownership of n peers, compared to the incumbent multisignature scheme that specified n public keys, and m signatures in the transaction on the time chain itself, thus leaking this information to outside observers. With MuSig, any multisignature has the anonymity set of all taproot outputs, which means they no longer suffer from privacy loss.

Private script commitments

Taproot enables several different ways to produce a valid witness to a UTXO, the first is a Schnorr public key and signature [MuSig or single sig], and the second is a OP_CODE based Bitcoin script. All the possible script spending conditions are ordered into the tapleaves of a Merkle tree, and the hash of the Merkle root, concatenated with the hash of the internal public key, is tweaked to the internal public key, generating the taproot public key. When spending from a script path, then only the used script, and a Merkle proof, and the internal public key are revealed in the witness program - not the un-used scripts. This means that UTXOs with several layered spending conditions do not need to leak the un-used spending condition to the verifier, and an outside observer cannot find out if and which other spending conditions were used. In the cooperative case, any output that has a script commitment, has the anonymity set of all taproot outputs.

Private adaptor secret commitments

Scriptless scripts are a trick to gain the functionality of scripts [like incumbent hashed time locked contracts], without the use of incumbent OP_CODES. This allows for example schemes that have a secret [previously the pre-image - now the adaptor], to commit to the secrets [previously the the hash - now the tweaked public key], to use this commitment [previously the hash in UTXO script - now the tweaked public key in UTXO script], then to reveal the secret [previously the pre-image in witness - now the tweaked signature in witness], and then to use the secret in another transaction [previously the usage of pre-image - now the usage of the adaptor]. The very important difference, contrary to incumbent HTLCs, is that an outside observer does not see any difference between a tweaked public key, or an adaptor signature, compared to the non-tweaked. Thus an outside observer cannot know that a scriptless script is used, which has outstanding privacy benefits to countless script contracts. In the cooperative case, any output that has a scriptless script, has the anonymity set of all taproot outputs.

Scalability Benefits

Senders of Bitcoin transaction want to minimize their on-chain footprint so to save on transaction fees. Verifiers of Bitcoin transactions want to safe on computation power without degrading the verification quality. Wasabi users are both senders and verifiers.

Larger m-of-n MuSig

In incumbent OP_CHECKMULTISIG, where the number of n public keys and m signatures is revealed in the transaction, which means that with higher n and m, the block usage increases, thus also increasing the cost for both sending and verifying. Contrarily, any size of n in MuSig is aggregated to exactly one public key, and any m to exactly one signature. Thus the block usage is exactly the same size as single signature spends, thus having the same cost for senders and verifiers.

Only used script revealed

Because any number of tapleaves can be committed to in a single Merkle root, there are no extra costs for creating multi-layered complex contracts. When spending out of these scripts, only the actually used script is revealed, as well as the depth of the taptree in the Merkle proof. Again, less block space is used, meaning less costs for senders and verifiers.

Signature batch verification

A verifier can batch all the public keys and signatures of all the transactions in a given block, and with one computation, calculate if they are valid, or not. This decreases the cost of verifying the property right transfer of UTXOs, thus enabling more peers to run full nodes and not relying on a trusted third party. Although this does not effect the sending users of Wasabi, it does benefit the verifying users.

Usability Benefits

The above mentioned privacy and scalability improvements enable countless new opportunities to use Bitcoin in a more private and efficient way, and this affects Wasabi directly.

Private shared ownership

One of the reasons that Wasabi does currently not support multisignatures, is that they have a vastly lower usage, and thus anonymity set compared to single signature. With MuSig, a user no longer leaks this information. Further, higher m-of-n are possible, and thus providing even more use cases for this powerful tool.

Private script usage

Wasabi does currently not use advanced op codes, with one reason being again that this decreases anonymity set, because of lower overall usage on the network. With taproot in the cooperative case, the fact that there exists a script is not revealed at all. And when a script spending path is used, only one script is revealed, and not all other possible ones. This allows to have very private fall back conditions in the spending rules, that in most cases will not be ended up used, but can save users from loosing access to funds. [For example long timeout recovery keys etc].

Atomic utxo swaps

Atomic utxo swaps are in summary when Alice spends her coin to Bob, under the condition that Bob spends his coin to Alice - they swap their coins. With scriptless scripts, the adaptor signature trick can be used to construct swaps that do not leak the script on-chain [like HTLC swaps do]. This breaks the link from inputs to outputs not just within one transaction [as zero link coin joins does] but across several blocks! And even better, because of the indistinguishably of tweaked public keys and adaptor signatures, EVERY taproot user has plausible deniability of potentially doing an atomic swap.

Lightning Network

Lightning network routes payment across several multi-party payment channels, utilizing both multisignatures and HTLCs. With taproot, both of these underlying technologies are drastically improved, both in privacy and scalability. This will help Wasabi on the long term goal to implementing a privacy cautious lightning node.

To Do

Must Do

• [ ] learn and research about the nuances of Schnorr signatures, taproot, and tapscript.
• [ ] review the BIPs and ensure a proper specification of the protocol
• [ ] implement the Schnorr cryptography into NBitcoin
• [ ] implement the ability to send to taproot outputs. Because of Bech32 addresses, this is already possible.
• [ ] implement generating Schnorr private & public keys & single signatures
• [ ] implement key tweaking [needed even for single signature taproot outputs]
• [ ] include SegWit v1 in BIP158 filters
• [ ] implement coin detection of SegWit v1, so that user can receive to taproot public keys
• [x] have lots of fun doing it

Can Do

• [ ] implement MuSig key generation and signing
• [ ] implement tapscript
• [ ] implement adaptor signature logic
• [ ] implement atomic UTXO coin swap
• [ ] implement partially blind atomic UTXO swap

[davterra]

Thanks Max.
It would seem to me that this should be a major priority.
Question: I saw tidbits of your conversation w/ Luke-jr about Knots. Have you asked him
about the merging of this BIP into Knots? That would seem like a prerequisite to offering Knots as a Core alternative in Wasabi.
For those interested in delving deeper into the weeds on Taproot, in "real time", there is a dedicated IRC channel on Freenode: ##taproot-bip-review
Logs of recent meetings on the channel: http://www.erisian.com.au/meetbot/taproot-bip-review/2019/