Shulou(Shulou.com)06/01 Report--

This article introduces you to Bitcoin ECDSA and Schnorr signature algorithm and Taproot upgrade is how, the content is very detailed, interested friends can refer to, I hope to help you.

In January 2020, the Taproot/Schnorr soft fork upgrade proposal proposed by Bitcoin core developer Pieter Wuille in May last year was officially released as Bitcoin Improvement Proposals (BIPs), with the relevant proposal numbers BIP 340-342. Taproot/Schnorr upgrade, if supported by the community, will be Bitcoin's largest technical expansion since the Lightning Network went live. This article looked up the documentation for BIP 340-342 to give a brief introduction to the Taproot/Schnorr upgrade. This article is divided into three parts, the first part briefly introduces the current ECDSA signature algorithm of Bitcoin, the second part introduces Schnorr signature algorithm in detail, and the third part introduces Taproot.

1. Bitcoin ECDSA signature algorithm

The ECDSA signature algorithm currently used by Bitcoin and the proposed Schnorr signature algorithm belong to elliptic curve digital signature algorithms, and the elliptic curves they use are secp 256k1. This part introduces secp 256k1 firstly, then ECDSA signature algorithm.

Elliptic curve secp256k1

Note: G coordinates are

（79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798, 483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8），

Order equals

FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141，

All are expressed in hexadecimal notation.

Second, Schnorr signature algorithm

In this part, we introduce the main characteristics of Schnorr signature algorithm first, then introduce Schnorr signature algorithm and batch verification step by step, finally introduce multisignature algorithm based on Schnorr signature.

(i) Main features

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

First, Schnorr signature algorithm has provable security. Under the Random Oracle model assuming the difficulty of elliptic curve discrete logarithm problem and the general group model assuming preimage resistance and Second preimage resistance, Schnorr signature algorithm has strong unforgeability under Chosen Message Attack (SUF-CMA). In other words, if the private key of Schnorr signature is not known, even if there is a valid Schnorr signature for any message, no other valid Schnorr signature can be derived. The provable security of ECDSA signature algorithm depends on stronger assumptions.

Second, Schnorr signature algorithm has non-malleability. Signature malleability means that a third party can transform a valid signature for a public key and message into another valid signature for that public key and message without knowing the private key. ECDSA signature algorithms have inherent scalability, 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 important for applications such as multisignature and batch verification, both to improve efficiency and to help protect privacy. But under ECDSA signature algorithm, if there is no additional witness data, batch verification has no efficiency improvement compared with individual verification.

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

(2) Schnorr signature algorithm

batch verification

Figure 2: Time to verify signatures individually/time required for batch verification

(3) Schnorr Signature Algorithm and Multisignature

signature generation

III. Taproot upgrade

Taproot upgrade can be seen as an application of Merkelized Abstract Syntax Tree (MAST), which in turn is related to Pay-to-Script-Hash (P2SH). Therefore, this section covers P2SH, MAST, and Taproot in turn.

(i) P2SH

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

(ii) MAST

MAST uses Merck trees to encrypt complex locking scripts (Figure 3), whose leaves are a series of scripts that do not overlap each other (e.g., multisignatures or time locks). To spend, simply disclose the relevant script and the path from that script to the Merck tree root. For example, in Figure 3, to use script 1, you only need to disclose script 1, script 2, and hash 3.

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

(iii) Taproot

However, P2SH differs from the common Pay-to-Public-Key-Hash (P2PKH) in performance and still has privacy protection issues. Is it possible to make P2SH and P2PKH look the same on the chain? That's the problem Taproot is trying to solve.

A script involving a limited number of signers can be broken down into two parts: the first part is a multi-signature, where all signers agree on a spending outcome, called collaborative spending; the second part is called non-collaborative spending, and can have a very complex script structure. These two parts are "or" relations. For example, in Figure 3, Script 3 is a type 2-of-2 multisignature that requires both Alice and Bob to be valid and is a "collaborative expense";Script 1 and Script 2 are "non-collaborative expenses."

About Bitcoin ECDSA and Schnorr signature algorithm and Taproot upgrade is how to share here, I hope the above content can be of some help to everyone, you can learn more knowledge. If you think the article is good, you can share it so that more people can see it.

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.