Dry Goods | Read the Taproot / Schnorr Upgrade for Bitcoin

The author of this article is Zou Chuanwei, chief economist of Wanxiang Blockchain and PlatON.

In January 2020, the Taproot / Schnorr soft fork upgrade proposal proposed by Bitcoin core developer Pieter Wuille in May last year has been officially released as a Bitcoin Improvement Proposal (BIPs), and the relevant proposal number is BIP 340-342. The Taproot / Schnorr upgrade, if supported by the community, will be the largest technical expansion of Bitcoin since the launch of the Lightning Network. This article inquired about BIP 340-342 related documents and gave a brief introduction to the Taproot / Schnorr upgrade. This article is divided into three parts. The first part briefly introduces Bitcoin's current ECDSA signature algorithm, the second part introduces the Schnorr signature algorithm in detail, and the third part introduces Taproot.

I. Bitcoin ECDSA signature algorithm

The current ECDSA signature algorithm and the proposed Schnorr signature algorithm used by Bitcoin are both elliptic curve digital signature algorithms. The elliptic curves they use are both secp256k1. This section first introduces the elliptic curve secp256k1, and then introduces the ECDSA signature algorithm.

(1) Elliptic curve secp256k1

• DeFi guardian: DeFi insurance agreement
• DeFi weekly selection 丨 Lightning attack or new normal, should I buy insurance for DeFi?
• Web3 Foundation announces funding for Second State blockchain company, introduces Ethereum virtual machine to Boca ecosystem

Figure 1: Illustration of an elliptic curve

(2) ECDSA signature algorithm

Note: G coordinates (79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798, 483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8), is equal to the order FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141, are expressed in hexadecimal.

Schnorr signature algorithm

This section first introduces the main characteristics of the Schnorr signature algorithm, then introduces the Schnorr signature algorithm and batch verification step by step, and finally introduces the multi-signature algorithm based on Schnorr signature.

(I) Main Features

Schnorr signature algorithm and ECDSA signature algorithm use the same elliptic curve secp256k1 and hash function SHA256, so they have the same security at this level. The Schnorr signature algorithm has the following advantages.

First, the Schnorr signature algorithm has provable security. The Schnorr signature algorithm has options under the random Oracle model that assumes the difficulty of the discrete logarithm problem of the elliptic curve, and the general group model that assumes Preimage Resistance and Second Preimage Resistance Strong Unforgeability under Chosen Message Attack (SUF-CMA). In other words, if the private key of the Schnorr signature is not known, even if there is a valid Schnorr signature for any message, there is no way to derive other valid Schnorr signatures. The provable security of the ECDSA signature algorithm relies on stronger assumptions.

Second, the Schnorr signature algorithm is non-malleability. The meaning of signature scalability is that a third party can transform a valid signature for a public key and message into another valid signature for the public key and information without knowing the private key. The ECDSA signature algorithm is inherently extensible, which is a problem addressed by BIP 62 and BIP 146.

Third, the Schnorr signature algorithm is linear, enabling multiple partners to generate signatures that are also valid for the sum of their public keys. This feature is very important for applications such as multi-signature and batch verification, which can improve efficiency and help protect privacy. Under the ECDSA signature algorithm, if there is no additional witness data, the batch verification is relatively inefficient compared to the individual verification.

Finally, the Schnorr signature algorithm is compatible with the current Bitcoin public and private key generation mechanism because it uses the same elliptic curve secp256k1 and the hash function SHA256.

(B) Schnorr signature algorithm

Public and private key generation

Signature generation

Signature verification

Batch verification

Figure 2: Time to verify signatures one by one / Time required for batch verification

(3) Schnorr signature algorithm and multi-signature

Key generation

Signature generation

Signature verification

Third, Taproot upgrade

The Taproot upgrade can be viewed as an application of the Merkelized Abstract Syntax Tree (MAST), which is related to Pay-to-Script-Hash (P2SH). Therefore, this section introduces P2SH, MAST, and Taproot in this order.

(1) P2SH

P2SH is a new type of transaction introduced in 2012 that makes using complex scripts as easy as paying directly to a Bitcoin address. In P2SH, complex lock scripts are replaced by their hash values, called Redeem Scripts. When a subsequent transaction attempts to spend this UTXO, it must include a script that matches the hash value and unlock the script. The main advantages of P2SH include: First, in transaction output, complex scripts are replaced by hash values, which makes transaction codes shorter. The second is to shift the burden of building the script to the receiver, not the sender. The third is better privacy protection. Theoretically, no party other than the recipient can be aware of the spending conditions contained in the redemption script. For example, in a multi-transaction, the sender may not know the public key associated with the multi-signature address; the public key is only disclosed when the receiver spends the funds. But P2SH also has shortcomings. First, all possible spending conditions must eventually be disclosed, including those that have not actually been triggered. The second is that when there are multiple possible spending conditions, P2SH will become complicated, which will increase the calculation and verification workload.

(Two) MAST

MAST uses the Merck tree to encrypt complex locking scripts (Figure 3), whose leaves are a series of non-overlapping scripts (for example, multi-signature or time-locking). To pay, just disclose the script and the path from that script to the root of the Merck tree. For example, in Figure 3, to use script 1, you only need to disclose script 1, script 2, and hash 3.

Figure 3: MAST, source: https://medium.com/@listedreserve/schnorr-and-taproot-cc4fa1edc828

The main advantages of MAST include: First, it supports complex spending conditions. The second is not to disclose unexecuted scripts or untriggered spending conditions, to provide better privacy protection. The third is to reduce transaction size. As the number of scripts increases, the size of non-MAST transactions grows linearly, while the size of MAST transactions grows logarithmically (Figure 4).

Figure 4: Number of scripts and transaction size, source: https://bitcointechtalk.com/what-is-a-bitcoin-merklized-abstract-syntax-tree-mast-33fdf2da5e2f

(Three) Taproot

However, P2SH is different from the common Pay-to-Public-Key-Hash (P2PKH) in terms of performance, and still has privacy protection issues. Is it possible to make P2SH and P2PKH look the same on the chain? This is the problem that Taproot solves.

A script involving a limited number of signers can be broken down into two parts: the first part is multi-signature, and all signers agree on a certain expenditure result, called "collaborative expenditure"; the second part is called "non-collaborative expenditure", There can be very complex script structures. The two parts are "OR" relationships. For example, in Figure 3, Script 3 is a 2-of-2 multi-signature, which requires both Alice and Bob to sign to be valid. It is "collaborative expenditure"; Script 1 and 2 are "non-collaborative expenditure".

Figure 5: Taproot, source: https://medium.com/@listedreserve/schnorr-and-taproot-cc4fa1edc828

references

1 Maxwell, Gregory, Andrew Poelstra, Yannick Seurin, and Pieter Wuille, 2018, "Simple Schnorr Multi-Signatures with Applications to Bitcoin".

We will continue to update Blocking; if you have any questions or suggestions, please contact us!