Suppose Alice has some Bitcoin and Bob has some other coin(e.g., Litecoin). Alice wants to trade her bitcoins for Bobs litecoin.
However, they both want to preserve their privacy, so an outside adversary or even an observer (e.g., Eve) could not
distinguish Alice and Bobs transactions from ordinary bitcoin transactions like a simple transaction between
Alice and Carol in which Alice sends some bitcoin to Carol. Note that having such a feature on bitcoin's blockchain
not only improves bitcoin's fungibility but improves all network participants privacy due to the fact that
anybody analyzing the blockchain must now deal with the possibility that Carol's transaction was actually a simple payment
or an atomic swap or a smart contract(script) etc.
To understand how the aforesaid swap can be done some prior knowledge is needed:
- What is a swap? what is an atomic swap and why we need it?
- How a tradition atomic is done using hash time-lock contracts?
- What is taproot?
- What are Schnor signatures?
- What are Signature Adaptors?
- What Are Scriptless Scripts?
- What Are PTLCs (point timelocked contract)?
- How to implement a realworld ptlc on bitcoin?
The Taproot update encompasses three Bitcoin Improvement Proposals (BIPs), including BIP340 (BIP – Schnorr), BIP341 (BIP – Taproot), BIP342 (BIP – Tapscript).
BIP-Schnorr introduces “Schnorr Signatures,” a faster, more secure and less data-intensive way to authorize transactions. BIP – Schnorr also enables BIP – Taproot, which uses a technique called “MAST” to commit less smart contract transaction data to the blockchain while also obscuring some private transaction information. Finally, BIP – Tapscript outfits Bitcoin with an upgraded transaction programming language which utilizes Schnorr and Taproot technology. Tapscript also allows developers to implement future Bitcoin upgrades more efficiently.
Taproot got activated at block 709,632 on November 14, 2021.
For the rest of this text, we focus on each component of Taproot to get a firm understanding on its different parts and how the come to gether to imrprove Bitcoins performance, scalability, privacy and fungibility.
Schnorr signature is a digital signature produced by the Schnorr signature algorithm that was described by Claus Schnorr. It is a digital signature scheme known for its simplicity. Although this schema came around 1980s, it was guarded by the patent law until 2008. At that time
there were no standardized way to implement the algorithm and not many people used in their systems, so satoshi decided to use ECDSA instead of Schnorr in Bitcoin. Fast forwarding a couple of years, an implementation of Schnoor Signatures was proposed in BIP340.
Here we try to dig a little deep into the actual workings of these algorithms. We assume the reader is already familiar with Public-Key Cryptography on an introductory level and has some understanding of Digital Signatures. We won't go into detailed proofs and won't use very formal mathematical notations, instead try to show a simplified outlook of Schnorr signatures in bitcoin.
We define
Now we take
To sign a message
Sig(m) = s = z + H(r || P || m ) * k
We present the tuple of
Note that instead of r || m
, r || P || m
is used to prevent Related-key attack.
To verify a signature we can simply check given
Note that
Schnorr Signature has many advantages over ECDSA with little to no disadvantage, apart from not being standardized. Some main pros are listed below:
- Provable security: Schnorr signatures are provably secure while it is still not proven that ECDSA is secure under reasonable assumptions. An explanation of the main ideas behind th security proof of Schnorr signatures can be found here
-
Non-malleability: The ECDSA signature scheme itself is vulnerable to a form of malleability, due to the fact that for every ECDSA signature
$(r,s)$ , the signature$(r,-s \mod N)$ is a valid signature of the same message. This problem is mitigated in bitcoin (BIP146) But when using a Schnorr signature, no such problem happens in the first place. -
Linearity: This arguably the most important improvement. Schnorr signatures are linear in nature, meaning we can add multiple signatures together to construct new signatures. The simple property can have many important consequences(some parts may be ambiguous for now but will be discussed and clarified later):
- Better privacy: By making different multisig spending policies indistinguishable on chain from regular P2PK. Actually with Taproot, the concept of Scriptless Scripts can be implemented in bitcoin transaction which not only improves security and privacy, but also improves bitcoins fungibility as a medium of exchange.
- Faster Verification Speed: Using Schnorr signatures, network participants can do batch/bulk verification on a blocks' transaction signatures. Furthermore, since Schnorr signatures are inherently less computationally expensive, signing and verifying any single transaction would need less time.
- Less Usage of Block Space: Because the ability of batch/bulk verification, less block space can be given to signatures. Also since in some cases instead of using P2SH (smart contracts), simpler forms of transactions can be used(Scriptless Scripts) which use less space and hence consume less of a blocks space.
Linearity of Schnorr signatures can be utilized to construct a new way to have n-of-n Multi-Signature contracts in Bitcoin without actually using P2SH or writing any Bitcoin Scripts. The specific implementation of such an algorithm in Bitcoin's Taproot Upgrade is called MuSig. Here we only explore a general description of it.
Suppose Alice (with private key
Alice and Bob create a new public key
So Alice and Bob can deposit to address
Before the Taproot upgrade, to verify all the transactions of a block, a miner had to
individually verify each transaction. With Taproot, multiple transaction can be verified at once (provided that all of them use Schnorr). For set of
Note that summation is a cheap operation in terms of computational resources need but verification is quite resource intensive compared to summation, hence by reducing the number of verifications drastic preformance boost can expected - especially when all of transaction inside a block use Schnorr-.
Contracts in Bitcoin often require a locking mechanism to ensure the atomicity of a set of payments—either all the payments succeed or all of them fail. This locking has traditionally been done by having all payments in the set commit to the same hash digest preimage; when the party who knows the preimage reveals it on-chain, everyone else learns it and can unlock their own payments. This is called a hashlock.
In 2019, Andrew Poelstra published a scientific paper describing Adaptor Signatures as a means to insure the atomicity of disjoint transactions with the signatures themselves rather on relying on Bitcoin contracts. The resulting transactions will appear to verifiers to be no different from ordinary single-signer transactions(P2PKH), except perhaps for the inclusion of lock-time refund logic. It's worth noting that the concept of Adaptor Signatures can be implemented using both Schnorr signatures and ECDSA, however we focus on Schnorr based implementations for now.
Suppose Alice and Bob want to conduct a some kind of payment between themselves. More details on how they can do different kind of payments (e.g. atomic swap) will be provided later but regardless of the application here how they would use Adaptor signatures to their benefit:
At first Bob generates a random number
Now Bobs creates a partial signature
References:
- BIP340
- What The heck is Schnorr?-Rajarshi Maitra
- What are the advantages of Schnorr vs ECDSA?
- https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2018-January/015614.html
- https://github.com/bitcoin/bips/blob/master/bip-0114.mediawiki
- https://github.com/bitcoin/bips/blob/master/bip-0341.mediawiki
- https://en.bitcoin.it/wiki/Multi-signature
- http://coders-errand.com/malleability-ecdsa-signatures/
- https://github.com/ElementsProject/scriptless-scripts
- https://medium.com/crypto-garage/adaptor-signature-schnorr-signature-and-ecdsa-da0663c2adc4
- https://medium.com/crypto-garage/adaptor-signature-on-schnorr-cross-chain-atomic-swaps-3f41c8fb221b
- https://bitcoinmagazine.com/culture/the-who-what-why-and-how-of-the-ongoing-transaction-malleability-attack-1444253640
- https://www.youtube.com/playlist?list=PLPrDsP88ifOVTEJf_jQGunDUS05M9GdIC
- https://bitcoinops.org/en/topics/adaptor-signatures/#:~:text=Adaptor%20signatures%20(also%20called%20signature,the%20adaptor%20reveals%20the%20signature.
- https://murchandamus.medium.com/2-of-3-multisig-inputs-using-pay-to-taproot-d5faf2312ba3
- https://eprint.iacr.org/2018/472
- https://bitcoin.stackexchange.com/questions/111169/what-is-an-adaptor-signature
- https://medium.com/@BR_Robin/basic-taproot-wallet-with-script-path-spend-c41f3f648a5a
- https://github.com/bitcoinops/taproot-workshop
- https://github.com/bitcoin/bips/blob/master/bip-0086.mediawiki
- https://bitcoinops.org/en/newsletters/2019/05/14/#overview-of-the-taproot--tapscript-proposed-bips