Why is Schnorr Signature known as the biggest technology update after bitcoin segwit

Want to make APP Same thing as WeChat , Can run small programs smoothly ？ | Experience will send you to Xinjiang 、 Huawei 、 Cherry keyboard ！>>>

This report is produced by Huo coin blockchain Research Institute    
When the report was released 2020 year 10 month 30 Japan   
author ： Yuan Yuming 、 Ma Tianyuan 、 Zhao Wenqi 、 Chen le

10 month 15 Japan , Core developers of bitcoin Pieter Wuille Dominant 3 A proposal （BIP340-342） The code is formal Into the main branch of bitcoin code . The three proposals contain Schnorr、Taproot and Tapscript The content of . Community comments that this change is the biggest technology update on bitcoin since the isolation witness .

Schnorr The main goal of signature is to replace the current bitcoin ECDSA Signature . Compared with the bitcoin blockchain currently used ECDSA,Schnorr It has some advantages ：

1. Signature security is high , Its security can be proved mathematically , And it's not malleable ;
2. Signature can provide privacy protection for the participants of multi signature ;
3. The linear characteristic of signature , Can be used as Taproot And the foundation of Technology , Further enhance the privacy of transactions ;
4. The signature length is shorter , And it can aggregate multiple signatures , Can save storage space , To realize the expansion of special currency ;
5. The signature can be verified in batch , So as to improve the verification efficiency ;

however , It also has some shortcomings , lie in ：

1. Users need multiple rounds of interaction before using it ;
2. The signature consumes some extra bandwidth and computing resources ;
3. Signature requires high randomness of random number .

As a possible alternative to the elliptic encryption algorithm ECDSA Technical update of signature mechanism ,Schnorr Signature is one of the important milestones in the development of bitcoin's underlying technology . After adding this code , It means that the technology has basically taken shape , Next, we need to wait for the community to determine the official activation time of the soft fork , However, there is no final conclusion at this time point .

1 Background introduction

Schnorr The signature mechanism was originally developed by German cryptographers 、 Mathematician Claus-Peter Schnorr The invention （ See the picture 1）,Schnorr The digital signature is also named after his name .Schnorr The security of is based on a particular discrete logarithm problem , Long known for its safety and simplicity . however Schnorr Registered a patent for his signature , therefore , This technology is good , But for a long time , Some apps can't use it directly .

until 2008 in ,Schnorr The signed patent will expire . meanwhile , There is no widely accepted specific implementation scheme in the industry , So Nakamoto, who published the white paper on bitcoin the same year , There was no choice at the time Schnorr Signature scheme , I chose the more mature one at that time ECDSA Signature scheme . With Schnorr The expiration of technical patents , This technology is gradually coming to the ground , In the bitcoin community Pieter Wuille Driven by the core developers , The community began to seriously consider the application of Schnorr The signature replaces the current ECDSA Signature , And upgrade in the way of soft bifurcation .

stay 2018 year 7 month , Core developers of bitcoin Pieter Wuille I proposed upgrading Schnorr Of BIP, And then Blockstream And the open source community also participated in the related development work . Before bitcoin was officially adopted , The bifurcations of bitcoin BCH Has been deployed in advance through hard forks Schnorr. That is to say 2019 year 5 month ,BCH The signature scheme has been upgraded to Schnorr Signature . The reason it was activated earlier , Mainly because it's an upgrade through hard forks , Bitcoin can't use hard bifurcations , Need a more elaborate design of soft bifurcation scheme .

later ,Pieter Wuille It is further proposed that Taproot/Schnorr Soft fork upgrade proposal , And this year 1 Month was officially released , That is to say BIP 340-342. And this time ,Schnorr The upgrade proposal has been formally incorporated into the code base . Together are merged into Bitcoin The three main proposals are BIP 340:Schnorr Signatures for secp256k1、BIP 341:Taproot:SegWitversion 1 spending rules、BIP 342: Validation of Taproot Scripts.

among , The first proposal is Schnorr Signed main proposal .Taproot It's Merkel's tree like abstract syntax tree upgrade , It is associated with Schnorr Sign together , It will allow bitcoin to execute more smart contract scripts in a private way ; And the last proposal is a complement to the first two proposals on bitcoin , It mainly upgrades the original bitcoin script , To support the Schnorr Signature 、 Batch verification and signature hashing . But here's the thing ,Schnorr The algorithm is still not standardized by the industry , this BIP 340 The proposal adopted by Schnorr It's still custom-made based on bitcoin .

2 Schnorr Signature And BIP The proposal

2.1 Schnorr What exactly is a signature ？

Schnorr It is essentially a cryptographic signature technology , We can simply understand it as , In bitcoin system ,Schnorr It will be ECDSA An alternative upgrade to .

ECDSA The full name of elliptic curve digital signature algorithm （EllipticCurve Digital Signature Algorithm）. Its role in bitcoin is no stranger to us , Every time we sign on the bitcoin network, we use ECDSA technology . for instance ,Alice Want to send a transaction , The miners have to make sure that only Alice Own private key , Have the right to dispose of this asset . therefore Alice Need to use ECDSA To generate a unique signature that cannot be modified , To prove Alice Own private key , At the same time, confirm the specific amount of the transaction part . And wait for Schnorr After the official activation , This work will be carried out by Schnorr replace . This process is shown in the figure 2.

2.2 Why we need to change the signature scheme ？

In the past 10 Within a year ,ECDSA Working well , Seems to be able to do the key job of generating signatures . But there's a problem that's been around ECDSA, At present, the industry has not been able to give a rigorous mathematical and cryptographic proof , To prove ECDSA It's math safe . In contrast ,Schnorr Sure . Under certain conditions ,Schnorr Signature technology has been proved mathematically secure . For a cryptocurrency like bitcoin, which relies heavily on security , The technology that can prove security is more reassuring than the technology that has no problem in practice .

• DavidPointcheval,Security Arguments for Digital Signatures and Blind Signature
• YannickSeurin,On the Exact Security of Schnorr-Type Signatures in the Random OracleModel

meanwhile , For bitcoin , what's more Schnorr The signature has “ linear ” Characteristics of , This feature allows multiple users' public keys to be aggregated into one public key through linear computation , And can generate corresponding aggregate signature .

Why do you say “ linear ” The features of bitcoin are very important for the current bitcoin ？ECDSA It does not support multi signature itself , Now it's through bitcoin P2SH Script to handle , however P2SH Class will expose the existence of multiple signature transactions to the network and reveal all signers . Use Schnorr A signature can aggregate multiple signatures into one signature , Enhance the privacy of transactions , It also saves the space occupied by multiple signatures in the unlock script , Save valuable space on the chain , Realize the capacity expansion in disguise . As a whole , If it is widely used , It's possible to bring bitcoin performance 5%~20% Left and right lifting .

Besides , Because the signature is aggregated into a , Only one verification is needed during signature verification , This will reduce the cost of Computing . The technical details of this part will be discussed in detail in the next chapter .

Schnorr Signature means a lot to bitcoin , Because it can be Taproot The cornerstone of this kind of Technology .Taproot It's also the second proposal this time BIP 341 The content of ,Taproot From MAST（Merkelized Abstract Syntax Tree）, It can express complex scripts in a Merkel tree based form . We know , One of the important characteristics of Merkel tree , It's just that it can't reveal the true data of unrelated branches , Quickly verify the existence of a node value , Therefore, it is widely used to store transactions in blockchain 、 Status data, etc . Based on this characteristic Taproot, It can be done without revealing unused branching conditions in the script , Finish running the script . By contrast ,P2SH You need to reveal all the script content .

combination Schnorr Signature technology ,Taproot You can even implement a transaction with a complex script （ Including transactions on Lightning networks 、 More deals 、 Judge more about branch transactions, etc ） It looks like a normal P2PKH Transactions . Support complex scripts , Protect script privacy , Don't expose the signer , Make a transaction with complex judgment conditions look as simple as a normal transaction , And there's no formal distinction , This is it. Taproot And Schnorr The effect of the combination .

2.3 Schnorr In what form will it take ？

And many of the previous ones BIP similar , this Schnorr In a soft bifurcation way .

BIP The full name of bitcoin is bitcoin improvement proposal （Bitcoin Improvement Proposals）, Generally speaking , It includes the technical update of the underlying blockchain technology of bitcoin 、 New feature introduction and information supplement . since 2009 In the middle of the year, bencong released the first version of bitcoin blockchain client , Most of the technology updates are in the form of BIP Forms are added to bitcoin Technology . at present , The bitcoin community has adopted more than 100 BIP The proposal , such as ： Isolation witness （BIP 144）、P2SH Multi signature structure （BIP 49） And mnemonics （BIP 39） etc. .

We may not be unfamiliar with the difference between hard bifurcation and soft bifurcation , In the hard fork , When communities have strong disagreements about certain features and technologies , Will cause the main chain to split into two chains , And the old and new clients are not compatible with each other , for example BTC and BCH,BCH and BSV etc. . And in a soft fork upgrade , Such as Segwit Upgrade, etc. , Although there may be differences in the community , But it still keeps a chain , The new and old clients are compatible to a certain extent .

Hard forking can sometimes bring strong unrest to the community , Therefore, the bitcoin community has long held a reservation on active hard fork upgrading , Avoid upgrading through hard forks as much as possible . This time bitcoin's Schnorr upgrade , It's going to be done through soft forks , This is an important reason why it is likely to be successfully activated by the community .

Replace ECDSA The signature looks like a very big change , Why? Schnorr It can be done through soft bifurcation ？ This is from Schnorr Speaking of .

Schnorr The security of is based on the assumption that ： It is very difficult to solve a particular discrete logarithm problem , And this security can be proved mathematically . let me put it another way , As long as this hypothesis holds , be Schnorr The intractability of signatures , Will be equal to the intractability of the discrete logarithm problem .

meanwhile , In an elliptic curve , There is also a problem very similar to the discrete logarithm . In the past, the elliptic curve digital signature algorithm in the underlying blockchain technology of bitcoin （ECDSA） The security of , It is also based on the elliptic curve discrete logarithm problem （ECDLP） It's hard to understand .

Schnorr The signature still uses the elliptic curve of the original bitcoin , But it uses a new calculation method , This allows maximum compatibility with versions that you don't want to upgrade , Realize soft fork upgrade .

On the other hand ,Schnorr Yes Segwit The client changes are very small , Now, Segwit The penetration rate of clients exceeds 90%. according to luke.dashjr Statistics , By 2020 year 10 month , More than 90% Has updated the client to 0.16 Above version , namely Segwit Upgraded version .Segwit Separate signature information from transaction information , And attached to the end as a separate structure . Because signature information only serves as verification , Key parameters that do not affect the transaction ： Such as transfer address 、 Quantity, etc .Schnorr Signature mainly affects signature information , For the upgrade Segwit Features of the client side ,Schnorr Signature only involves signature verification information attached to the end with a separate structure , So the impact is small .

in summary ,Schnorr The signature can be added to the bottom layer of bitcoin blockchain in the form of soft fork upgrade , There's no need for hard forks , It won't divide the community . Refuse Schnorr The signed client can still join the network normally , Finish packing and other operations . Soft fork as a blockchain ledger upgrade means , Although the implementation is more difficult , It often requires elaborate design to circumvent certain rules , But it's more compatible , It won't lead to a split consensus , It's a step-by-step process 、 A gentle way to update .

Due to the gentle upgrade characteristics of soft bifurcation , Plus Schnorr The disadvantages are minor , By the core developers （Bitcoin Core） Push , So it has a high possibility of activation .

3 Schnorr Signature technology details analysis

Next in , Let's be right Schnorr The technical details of the signature are analyzed ：

3.1 High safety

Schnorr The security of the signature is proved mathematically , and ECDSA It hasn't been proven yet . Although over the past many years ,ECDSA There has been no security problem , It's like a volcano that never erupted , Long silence , But you don't know if it's going to explode one day . And a mathematical proof of the algorithm must be more than possible “ hidden danger ” The algorithm is more trustworthy .

stay David Pointcheval、Yannick Seurin Under the mathematical proof of scholars , We know , In the random prediction model , Suppose the elliptic curve discrete logarithm problem is very difficult , Want to break through Schnorr The only way to sign is to solve the discrete logarithm problem .

So in a way ,Schnorr Signatures are more secure , More credible （trustless）.

Besides ,Schnorr Signature is not extensible , This feature is associated with ECDSA Can be fully demonstrated in the contrast of ,ECDSA It's a scalable signature algorithm . say concretely , be based on ECDSA Generated signature , For a given message , The attacker doesn't know the key , Can generate new signatures that are equally valid . Bitcoin also specifically proposes BIP 146 In response to the problem . but Schnorr Signature is naturally non extensible , This security problem can be avoided directly .

3.2 Support signature aggregation , Save storage space

The aggregation of signatures , It mainly refers to the aggregation of multi signatures . Multisignature （ The abbreviation is multi signature ） yes Bitcoin A technique that controls the use of funds . For example, we often see “2 of 3” Multiple signatures , Asking for authorization 3 There must be at least 2 Fang signed the deal , This money can only be used .

For example, the figure above 4 Just a stroke. “2 of 3” Multi signed input script , You can see in the red box 2 individual ECDSA The signature of the , With this 2 A signature , The money can be used legally . however ECDSA There is no aggregation of signatures , Just simply put each signature in the input script , also 2 The public keys of the signers also need to be placed in the input script . If there is one “9 of 10” Multiple signatures , It needs to be stored in blocks 9 Signatures and 9 Public key , It takes up a lot of space .

But if Schnorr Signature , Can improve this problem .Schnorr Signatures are signed through a method called key aggregation （Key Aggregation） Technology , You can put any stroke “m of n” More than one m Signatures aggregate to 1 A signature , meanwhile m The public keys of signers can also be aggregated into 1 Public key . No matter what m How big? , In the input script, you just need to fill in 1 Signatures and 1 Public key , This can greatly reduce the space occupied by multiple signings in the block .

 

The picture above shows Pieter Wuille Yes Bitcoin A simulation of historical data , take Bitcoin All multiple signatures in the historical data are replaced with Schnorr After the aggregate signature of , Can significantly reduce Bitcoin Block storage space .

It's just mentioned above Schnorr One of the aggregate signatures , namely “ Yes UTXO Multiple signatures in a single input are aggregated ”. in fact ,Schnorr Signature has more powerful functions , Sure “ Yes UTXO Multiple signatures from multiple inputs are aggregated ”, So that the whole UTXO only one Schnorr Signature . However, the preconditions for this polymerization are more stringent , It's complicated to implement .

3.3 The signature length is shorter , Save storage space

according to Pieter Wuille The proposal ,Bitcoin Used in Schnorr Signature algorithm , The length of the public key is 32 byte , The signature length is 64 byte . and Bitcoin Currently used ECDSA Signature algorithm , The length of the public key is 33 byte , The longest signature will be 72 byte .Bitcoin Every piece of land is worth an inch of gold , It's important to save a little space .

For example, figure 3 In this 2 Inputs 2 Output UTXO, The part selected in the red box is filled in the input ECDSA Signature , The length is 72 byte ; It's followed by 33 Byte public key . So using Schnorr After signing , The space occupied by signature and public key can be reduced to 64 Byte and 32 byte .

in fact Schnorr There is also a variant of signature , You can shorten the signature to 48 byte , But because batch verification is not supported ,Pieter Wuille Not recommended .

3.4 Stronger privacy protection

Schnorr It can be used to aggregate multiple keys into one , It can make bitcoin “ Multisignature ” The transaction sent out by the wallet only shows the aggregated one , This makes multiple wallets simpler and more private . In the past , User based ECDSA Signature use “ Multisignature ” In the wallet , Because we have to show more than one public key , Therefore, it is easy to expose the multi signature of this wallet . But if based on Schnorr Signature , Aggregate multiple keys under the chain , Can make a multi signature transaction look like a normal transaction （ A single signature transaction ） It's no different .

The top one “2 of 3” Examples of multiple signatures , You can see the signature provided by 2 Fang's public key has been exposed , in other words , which 2 Fang's participation is open . But if you use Schnorr Aggregate signature of , Public keys are also aggregated into 1 individual , So it doesn't reveal what it is 2 Fang participated in the signing of more . Multiple signatures after aggregation even with a normal “ Single sign ” It doesn't seem to make any difference , This means that the outside world doesn't even know it's a multi signature . This greatly protects the privacy of multiple signers .

3.5 The signature can be verified in batch , Improve verification efficiency

Schnorr Signature , Because of its linear nature , Naturally, it can support batch verification . The principle is not complicated ,Schnorr Signature verification process , It's to judge whether an equation holds or not . And batch validation , Is when there is n This equation needs to be verified , We can add up all of them on the left , On the right, it's all added up , In this way, we only need to verify whether the equation is true once , You can judge n Are all signatures legal .

And the original verification n When it comes to equations , The calculation needs to be done n Times multiplication , Now it can be merged into , Just do n-1 Second addition and 1 Times multiplication , Greatly improve the efficiency of verification .

Schnorr This linear property of signature is natural , So even from different users 、 Different Tx, Even different block signatures , Can be combined for batch validation . A new full node , When data is synchronized in blocks , A lot of validation is needed , If Bitcoin use Schnorr Signature , Through batch verification, the synchronization speed of the whole node can be significantly improved .

3.6 Some shortcomings

All that was said before was Schnorr The advantages of signing . in fact , There are also costs to bring these benefits . because Schnorr The characteristics of aggregate private key signature , It requires multiple rounds of interaction between participants , This is compared to the past ECDSA It's going to be more troublesome . And it requires a lot of random numbers , Make sure that random numbers are not easily guessed by attackers , Some traditional pseudo-random number generation methods are not necessarily suitable for . meanwhile ,PC The process of calculating these signatures and generating random numbers is cumbersome , As a result, there will be a little delay in sending the transaction , And ask the PC Consume more computing bandwidth resources . however , In terms of current technology , These problems can be solved and overcome to a certain extent .

4 summary

Schnorr Signature compared to ECDSA More secure and credible , And it also brings the expansion of space on the bitcoin chain , The performance of bitcoin has been improved slightly , meanwhile ,Schnorr Signatures can also protect multiple signatures 、 The privacy of participants in technologies such as lightning networks , combination Taproot It also enables more smart contract scripts to increase privacy .

For now , Proposed by Core Group members push , Gentle upgrade in soft fork mode , There is a high probability of successful activation in the future , Also look forward to Schnorr Signature can be for bitcoin and blockchain world , Bring more fresh technological vitality .