Why Schnorr signatures are hailed as the biggest technical update after Bitcoin Segwit?

2021-01-14 17:03

Read this article in 12 Minutes

AI summary

View the summary

Original title: "A Multi-signature Scheme and Wallet Architecture Based on Schnoor Algorithm"

Original Source: Han Sheng, NPC Source Project

Bitcoin core client recently released a new version, This release mainly brings the Schnorr signature Taproot technology. Schnorr is an elegant and concise signature algorithm that can improve transaction privacy, save space, and also implement aggregated multi-signatures. At the same time, it is different from the traditional ESDSA signature technology. It has obvious characteristics in terms of technology and implementation. It has been widely used in different links of different public chains. In this issue, we are honored to invite cryptography expert Han Sheng (pseudonym) to write a paper to introduce a multi-signature scheme and wallet architecture based on the Schnoor algorithm. At the same time, I recommend two related popular science articles at the end of the article, hoping to learn this new technology together and understand the significance of Schnorr signatures for the development of Bitcoin and blockchain technology.

EDIT: xy works Chamber, NPC

ECDSA Signature Review

A digital signature is a digital simulation of a signature. The earliest digital signature algorithm was the RSA signature algorithm proposed by Rivest, Shamir, and Adleman in 1978. Its security is based on the incomprehensibility of large integer decomposition, and it is widely used in digital certification and CA and other fields. However, due to the large key size of the RSA algorithm, the storage efficiency is not as good as the later signature algorithm based on elliptic curves. Therefore, the signatures widely used in cryptocurrency are almost all ECDSA algorithms, but the underlying elliptic curves are different. The security of ECDSA is based on the intractability of elliptic curve discrete logarithms.

Bitcoin signature algorithm - ECDSA based on SECP256k1 curve

The signature algorithm currently used by Bitcoin is the ECDSA algorithm based on the SECP256k1 curve. Use the detailed information of the transaction as a message summary, that is, z=SHA256(m), and use the summary z as the core signature algorithm.

cryptographically secure digital signature The randomness of the signature needs to be achieved by adding nonces. However, according to the RFC6979 standard, the random number in the signature algorithm is extracted from the message digest z, which is not a random number in the cryptographic sense. This scheme is in many cryptography codebases and is used in most blockchain projects.

Trivial scheme with Schnorr signature

Schnorr signature can solve the problem of multi-signature resource consumption mentioned above.

Schnorr was developed by Claus-Peter Schnorr in The digital signature algorithm proposed at the Secret Conference in 1989, and applied for patent protection. As far as the signature algorithm itself is concerned, it has the characteristics of provable security and scalability compared to the ECDSA algorithm.

The main algorithm is realized as follows:

It can be seen that Schnorr Signatures are also based on elliptic curve arithmetic. Currently, the underlying arithmetic modules widely deployed in major code bases and chip instructions can still be used effectively, but it is necessary to re-encapsulate instructions from the underlying interface to implement the Schnorr algorithm. This is more convenient for software wallet upgrades. But for hardware wallets, the upgrade cost may be higher.

Linearity of the Schnorr signature scheme

Assume that Alice and Bob sign the message m respectively. Specifically, suppose Alice's public-private key pair is (x1,X1=x1G), Bob's public-private key pair is (x2,X2=x2G),

< br>

The above scheme is just to show the linearity of Schnorr signature , and cannot be directly used in practical applications, because this solution may lead to Rouge key Attack.

Multi-signature scheme based on Schnorr signature

1. Multi-signature scheme

Take n-of-m multi-signature scheme as an example.

2. Wallet service architecture

The wallet is divided into server-side (S-side) and client (C-side), the C-side will have multiple logical points, corresponding to multiple users.

The S-terminal and C-terminal here are only logical. There can be both S-terminal and C-terminal on one physical device, or on multiple physical devices.

Conclusion ;

For the linear nature of Schnorr and the cumulative nature of the signature, it makes the In the execution of Bitcoin multi-signature transactions, too much user signature data is not required, only "signature sum" and "public key sum" are needed to verify the legality of the transaction. This will greatly reduce the size of Bitcoin's multi-signature transactions, thereby greatly increasing the number of multi-signature transactions that can be accommodated in a block. Taking 2-3 multi-signature as an example, the current bitcoin multi-signature locking script requires 3 public key addresses, and this part will be compressed into a script, so the size will not change after the upgrade, but the unlocking script requires 2 public keys With 2 signatures, after upgrading to Schnorr, only a "public key sum" and "signature sum" are required. For the more general n-m multi-signature, the current Bitcoin multi-signature unlocking script requires n public keys and n signatures, while the Schnorr signature still only needs a "public key sum" and a "signature sum". That is to say, the more signers, the higher the space utilization rate of Schnorr signature.