Is the evolution of the Bitcoin algorithm to the Schnorr signature algorithm a progress? |

特邀专栏作者

2021-01-18 01:30

This article is about 6490 words, reading the full article takes about 10 minutes

From the point of view of cryptography: using Schnorr signature is a"Bold and imprudent" approach deviates from the first essence of "long-term security".

AI Summary

Expand

From the point of view of cryptography: using Schnorr signature is a"Bold and imprudent" approach deviates from the first essence of "long-term security".

The wheel of history is rolling forward, and the progress of technology has never stopped. A milestone Bitcoin protocol has begun its technological upgrade. The technical upgrades in its protocol, Schnorr Signature (Schnorr Signature) and Taproot (Taproot of the tree) have been integrated into Bitcoin Core 0.21.0 version.

The future of Bitcoin seems brighter than ever, and now it has the opportunity to surpass all other blockchains not only by its capacity but also by its functionality.

When the Bitcoin ECDSA elliptic curve signature algorithm was used, the multi-signature transaction verification process was very cumbersome. Now it is possible to combine all the signatures and public keys in a transaction into a single signature and public key. What will happen if it is untraceable and simple and fast?

In fact, before this, when Satoshi Nakamoto designed the Bitcoin protocol, he needed to consider various conditions such as the signature length of the signature algorithm, whether it is open source, whether it has patents, whether it has passed security verification for a long enough time, and performance. At that time, there were not only ECDSA digital signature algorithms that could meet the above conditions, but also Schnorr Signature, a digital signature algorithm that was no less than ECDSA in all aspects. However, since it was in the state of patent protection before 2008, this may be the reason why Satoshi Nakamoto did not use this signature algorithm when designing the Bitcoin protocol, and finally chose the Elliptic Curve Digital Signature Algorithm (ECDSA). A special elliptic curve secp256k1 was chosen at the suggestion of .

After 10 years, in July 2018, Bitcoin developer Pieter Wuille wrote bip-schnorr and proposed to change bitcoin's signature algorithm to schnorr. Although Schnorr and ECDSA are both elliptic curve encryption algorithms using the secp236k1 curve, due to the advantages of Schnorr Signature in cryptographic characteristics, it is more convenient to construct multi-signature transactions on the basis of almost the same security.

Schnorr used on Bitcoin has some additional significant advantages over ECDSA:

Safer: It is easy to prove the security of Schnorr signatures in the random oracle model, but there is no such proof for ECDSA.
No malleability problem: ECDSA signature is malleable, a third party can directly modify the existing signature without knowing the private key, and still keep the signature valid for this transaction. There has always been a malleability attack on Bitcoin, which was not fixed until SegWit was activated, provided that segwit transactions were used instead of traditional transactions. BIP62 and BIP66 describe this in detail.
Linear: The Schnorr signature algorithm is linear! Based on this feature, a more efficient and private blockchain system can be built. Parties using Schnorr signatures can generate signed aggregates of their respective keys. For example, if N public keys are used to sign, if ECDSA is used, there will be N signatures, and verification also needs to be done N times. If Schnorr is used, due to the linear property, signature superposition can be performed, and only the final superposition signature is kept. For example, regardless of the number of inputs in the same transaction, it can be superimposed into one signature, and one verification is enough.

The Schnorr signature algorithm is superior to Bitcoin's existing signature algorithm ECDSA in almost every aspect: performance, security, volume, scalability, etc., and Schnorr Sig can use the same elliptic curve as ECDSA: secp256k1 curve, an upgraded change very small.

Of course, in addition to the signature algorithm in the Bitcoin protocol, the Taproot scripting language is also designed to define how to use Bitcoin. Bitcoin multi-signature addresses do not need to reveal their "multi-signature" identity, and can also support a large number of multi-signature scenarios (on-chain transactions only require an aggregated public key and a signature), reducing the number of transaction bytes , especially for addresses that require high-frequency operations, reducing transaction fees on the chain can save a lot of costs.

Here are some of the more common questions and answers:

Q&A

Q: Can Schnorr signatures be used for m of n multi-signatures?

A: Of course you can. Multisig is just a pattern of m of n number of signatures. Regardless of the signature algorithm.

Q: Can Schnorr's group signature feature make or simulate m of n signatures?

A: It cannot be done. If there are N public keys in the group, there must be corresponding N signatures, all of which are indispensable. When everyone generates a signature, they all substitute the group public key P in the hash function.

Q: How to measure the security of the signature mechanism?

A: It mainly depends on two: 1. The signature algorithm itself 2. The elliptic curve. Currently, both Schnorr and ECDSA use the curve secp256k1, which is the same level. As for the security of the signature algorithm itself, Schnorr currently has a security certificate, which is better than ECDSA.

BCH's Trial Implementation of Schnorr Signature Algorithm

As early as May 16, 2019, BCH had already started a hard fork upgrade. The main content of the upgrade is Schnorr signature algorithm and Segregated Witness recovery, the most anticipated function in the Schnorr signature upgrade, and Segregated Witness recovery principle is a repair technology to retrieve the BCH that was wrongly sent to the Segregated Witness address.

Developer Mark Lundeberg Users don't have to generate new addresses to start using Schnorr signatures. The advantages brought to BCH by this upgrade are as follows:

1. Improve the validity of the signature data: Since the signature is 64 bytes of data, compared with the usual 70 bytes, the transaction can reduce 4% of the bytes. The validity of the signature data (Schnorr signature will reduce the blockchain storage and bandwidth by at least 25%, making the BCH network faster and more efficient). And after the upgrade, the Schnorr signature brings BCH the ability to hide ordinary payment channels.
2. Improvement of privacy: Before the upgrade, many users deliberately use multiple signatures to send transactions to improve privacy, and Schnorr signatures will make all user signatures look the same as any other signatures. This structure leads to transaction privacy significant increase in sex. The properties provided by Schnorr and some extensions added by BCH developers and infrastructure providers such as wallets will further enhance privacy and scalability.
3. Fight against spam transaction attacks: There has been a spam transaction attack in the past. Attackers hope to congest Bitcoin through as much transaction space as possible. One of their methods is to make this transaction happen by frequently sending transactions from multiple sources. Transactions include dozens of signatures, which take up a lot of space. This is the hidden danger left by ECDSA signature. Schnorr can avoid such spam attacks. If each transaction has only one signature, then the block can accommodate more transactions, and spammers must send more transactions if they want to create an attack, and compete with more people, so the cost of the attack will be relatively higher. The space occupied by the signature is usually the largest part of a transaction, so the attacker has no advantage.

Of course, we can't just see the good side, everything will be lacking, and extremes will be reversed. In particular, the development of quantum computers has prompted some visionary people to find solutions as soon as possible. In order to deal with the attacks of quantum computers on some algorithms, in 2017, NIST started the post-quantum cryptography standardization process. The anti-quantum signature scheme promoted, one of the anti-quantum algorithms supported by the post-quantum encryption foundation, and the signature anti-quantum signature scheme with the shortest signature length-Rainbow signature is the most promising.

In August 2017, Jin Liu and mathematician Prof. Jintai Ding prepared to establish ABCMint and registered in Encryption Valley near Zurich, Switzerland. The underlying signature of its digital currency ABC is the rainbow signature Rainbow. Their vision is to support the research and application of anti-quantum computer cracking algorithms globally. The research includes supporting mathematicians in the discovery, cracking, and improvement of algorithms around the world. The algorithm is applied to mainstream digital cryptocurrencies.

They believe that Bitcoin's proposal BIP340, which uses Schnorr signatures from ECDSA to Schnorr signatures, is a major regression of Bitcoin. We are not optimistic about the algorithm selection and improvement proposed by computer security experts. We prefer the algorithm selection and improvement proposed by mathematicians. The Schnorr signature has a big problem, and it should be used in Litecoin and the like for a long time test run.

BTC should wait for BCH, or other chains to use Schnorr signatures for a few years before looking at it. The main advantage of the Schnorr signature is that "the signature length is the shortest when there are multiple signatures", but the disadvantage is that "the last person is easy to deceive when there are multiple signatures".

From the point of view of cryptography: using Schnorr signature is a"Bold and imprudent" approach deviates from the first essence of "long-term security".

From the perspective of cryptography, Schnorr signatures are mainly for multi-signatures, and the suitable scenarios for multi-signatures should be: centralized and extremely important scenarios, and its extremely important scenarios are similar to the dozens of Verifiable procedures launched by nuclear bombs. Or gates like the Cheyenne Mountain Nuclear Weapons Base. It should not be a decentralized scenario, or a scenario such as the sending of Bitcoin.

To put it simply: Decentralization itself deviates from multi-signature.

Here are a few simple algorithms:

1 Elliptic Curve Digital Signature Algorithm (ECDSA)

Elliptic Curve Digital Signature Algorithm (ECDSA, Elliptic Curve Digital Signature Algorithm) is a simulation of Digital Signature Algorithm (DSA) using Elliptic Curve Cryptography (ECC). (Elliptic Curve Cryptography (ECC) was invented by Neal Koblitz and Victor Miller in 1985), ECDSA was first proposed by Scott and Vanstone in 1992 in response to NIST's request for the Digital Signature Standard (DSS).

Bitcoin currently uses the ECDSA elliptic curve digital signature algorithm. To sign a message m, we need to hash it and treat this hash as a number: z = hash(m). We also need a random or random lookup number k. We don't like to trust random number generators (there are too many bugs, many bugs related to bad RGNs), so we usually use RFC6979 and compute a deterministic K value based on our secret and the message we want to sign.

Using the private key pk, we can generate a signature for a message m consisting of two numbers: r (x-coordinate of random point R = k×G) and s = (z+r⋅pk)/k. Then, using our public key P = pk×G, anyone can verify our signature by checking that the x-coordinate of the point (z/s)×G+(r/s)×P is equal to r.

Signature verification includes inversion (1/s) and two-point multiplication, and these operations are computationally expensive. In Bitcoin, every node must verify all transactions. This means that when you broadcast a transaction, thousands of computers will have to verify your signature. And simplifying the verification process would be very beneficial, even if the signing process would be more difficult.

Schnorr signature

The Schnorr signature algorithm was proposed by German mathematician and cryptographer Claus Schnorr. And applied for a patent in 1990, US Patent 4,995,082, which expired in February 2008. The algorithm is currently freely available.

Schnorr signatures are generated slightly differently, we use a point R and a scalar s instead of two scalars (r, s). Similar to ECDSA, R is a random point on the elliptic curve (R=K×G). The second part of the signature is calculated slightly differently:

s = k + hash(P,R,m) ⋅ pk. Here pk is your private key, and P = pk×G is your public key, and m is the message. This signature can then be verified by checking s×G = R + hash(P,R,m)×P.

This equation is linear, so the equations can add and subtract from each other and still be valid, which gives us several great benefits about Schnorr signatures.

3 Batch Verification of Schnorr Signatures

To verify a block in the Bitcoin blockchain, we need to ensure that all signatures in the block are valid.

For the ECDSA signature algorithm, each signature must be verified individually. That is, if there are 1000 signatures in the block, we need to calculate 1000 inversions and 2000 dot multiplications, for a total of about 3000 heavy calculation tasks.

And by using Schnorr signatures, we can add up all the signature verification equations, saving some computing power. For a block with 1000 signatures, we need to verify:

(s1+s2+…+s1000)×G=(R1+…+R1000)+(hash(P1,R1,m1)×P1+hash(P2,R2,m2)×P2+…+hash(P1000,R1000,m1000)×P1000)

Here we have a bunch of additions (almost free in computing power) and 1001 point multiplications. We need to calculate about one heavy computation for each signature.

4 Key Aggregation for Schnorr Signatures

We want to keep our bitcoins safe, so we probably want to use at least 2 different private keys to control our bitcoins. For example, one on a laptop or mobile phone, and the other on a hardware wallet/cold wallet. So when one of them is compromised, we can still control our bitcoins.

Currently, it does so via a 2-of-2 multi-signature script, which requires two separate signatures to be included in the transaction. Whereas with schnorr signatures, we can use a pair of private keys (pk1,pk2) and generate a shared signature corresponding to the shared public key P=P1+P2=pk1×G+pk2×G. To generate this signature, we need to choose a random number (k1,k2) on each device, generate a random point Ri=ki×G, add them to calculate a public hash (P,R1+R2,m) , and then get s1 and s2 from each device (si = ki + hash(P,R,m) ⋅ pki). We can then sum these signatures and use the pair (R, s) = (R1+R2, s1+s2) as our signature on the shared public key p. Everyone else can't tell if it's an aggregated signature, it looks exactly like a normal schnorr signature.

There are 3 problems with this construction, first, from a user interface point of view, to make a transaction, we need to do several rounds of communication, calculate the public R, and then - sign. With two private keys, this can be done with a single access to the cold wallet: we prepare an unsigned transaction on the online wallet, choose k1, and write down R1=K1×G along with the unsigned transaction. We then transfer this data to the cold wallet and sign it. Since we already have R1, we can sign transactions on the cold wallet in one go. From the cold wallet, we get R2 and s2 and transfer them back to the online wallet. The online wallet signs the transaction with the previously selected (k1, R1), combines the signatures and broadcasts the signed transaction. This is very similar to where we are now, but once you add a third private key, everything gets more complicated. Let's say you have a fortune, which is controlled by 10 private keys, which are stored in different secure locations around the world, and then, you need to make a transaction. Currently, you only need to go through all these locations once, but if you are using key aggregation, you need to do it twice, to assemble all RIs, and then sign. In this case it is better to keep individual signatures without aggregation, then we need 3 rounds of communication:

Choose a random number ki and the corresponding Ri=ki×G, and tell everyone only its hash ti=hash(Ri), so that everyone can be sure that you won't change your mind after learning other random numbers;
Put all the numbers together and calculate the common R;
sign;

The second issue is known malicious key attacks. It's well described, both in the paper and this article, so I don't want to go into detail. The idea is that if one of your devices is hacked (say, your online wallet) and pretends its public key is (p1-p2), then it can control the shared funds with its private key pk1. A simple solution is that when setting up the device, the public key needs to be signed with the corresponding private key.

There is a third important question. It cannot be signed with deterministic k. There is an easy way to attack, if you use deterministic K, it allows a hacker to get our private key. An attack would look something like this: Someone hacked into our laptop and took full control of one of the two private keys (e.g. pk1). We may feel safe because our bitcoin requires an aggregated signature from pk1 and pk2. So we try to do the transaction as usual, prepare an unsigned transaction and R1 value, transfer them to our hardware wallet and sign it there. Then return (r2, s2) and ... something happened to our online wallet, it can't sign and broadcast. We try again, but our hacked computer uses another random value R1' this time. We sign the same transaction with our hardware wallet again and bring the value (r2, s2) back to our hacked computer. Then, something bad happened and our bitcoins were lost.

In this attack, the hacker obtains a pair of valid signatures for the same transaction: (R1, s1, R2, s2) and (R1', s1', R2, s2'), where R2 is the same, but R = R1 +R2 and R'=R1'+R2 are different, which means a hacker can calculate our second private key: s2-s2'=(hash(P,R1+R2,m)-hash(P,R1 '+R2,m))⋅pk2 and pk2=(s2-s2')/(hash(P,R1+R2,m)-hash(P,R1'+R2,m)). I find this the most inconvenient feature of key aggregation: we need a good random number generator everywhere to use key aggregation.

# Rainbow #

Rainbow is a multivariate signature scheme whose layered structure is based on the Unbalanced Oil-Gooseberry (UOV) signature scheme. The extra structure imposed by the Rainbow layer exposes the scheme to more cryptanalytic techniques, but increases the efficiency of the scheme. Rainbow provides fast signing and verification and very short signatures, but with very large public keys.

Choosing Rainbow increases the diversity of shortlisted signature schemes; however, due to the very large key size, Rainbow is not suitable as a general-purpose signature algorithm to replace the algorithms currently appearing in FIPS 186-4. In particular, large public keys make certificate chains very large. However, some applications do not need to send keys very often. For such applications, Rainbow provides small and fast signatures.