An article to understand how Schnorr signatures improve Bitcoin

When reading the MuSig paper written by Blockstream, I have been imagining what this means for me as a Bitcoin user. I find some features of Schnorr signatures are really great and convenient, but some features are very annoying. In this article, I hope to share my thoughts with you. But let’s review it quickly.

Elliptic Curve Signature Algorithm

The current Bitcoin ownership system uses ECDSA (Elliptic Curve Signature Algorithm). When signing a message m, we first hash the message to obtain a hash value, namely z = hash(m). We also need a random number (or at least a seemingly random number) k. Here, we don’t want to trust random number generators (there are too many errors and vulnerabilities related to unqualified random number generators), so we usually use RFC6979, based on a secret value we know and what we want to sign Message, calculate a deterministic k.

Using the private key pk, we can generate a signature for the message m. The signature consists of two numbers: r (the x coordinate of a random point R = k * G) and s = (z + r*pk)/k.

Then, using our public key P = pk * G, anyone can verify our signature, that is, check that the x coordinate of (z/s)×G+(r/s)×P is indeed r.

An article to understand how Schnorr signatures improve Bitcoin

ECDSA algorithm diagram. For ease of illustration, the elliptic curve is drawn on the real number field 

This algorithm is very common and very easy to use. But there is room for improvement. First of all, the verification of the signature includes division (1/s) and two point multiplications, and these operations are very computationally intensive. In the Bitcoin network, every node must verify every transaction, so when you send a transaction in the network, thousands of nodes in the entire network must verify your signature. Therefore, even if the cost of the signature process becomes larger, it is still very beneficial to make it easier to verify the signature.

Secondly, when the node verifies the signature, each signature must be verified separately. In a multi-signature transaction of mn, the node must verify the same signature multiple times. For example, a 7-11 multi-signature transaction contains 7 signatures, and each node in the network must verify 7 signatures separately. In addition, the volume of this type of transaction is also very large, and users must pay much more for this.

Schnorr signature

The way the Schnorr signature is generated is slightly different. It is not two scalars (r, s), but a point R and a scalar s. Similar to the ECDSA signature, R is a random point on an elliptic curve R = k * G. The calculation process of the second part of the signature s is also different: 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. The verification process is to check s * G = R + hash(P,R,m) * P.

An article to understand how Schnorr signatures improve Bitcoin

Graphical Schnorr signature and verification 

This equation is linear, so multiple equations can be added and subtracted and the equal sign still holds. This brings us many good features of Schnorr signatures.

1. Batch verification

When verifying a block on the blockchain, we need to verify that the signatures of all transactions in the block are valid. If one of them is invalid, no matter which one-we must reject the entire block.

Each signature of ECDSA must be specifically verified, which means that if a block contains 1000 signatures, then we need to calculate 1000 divisions and 2000 point multiplications, a total of about 3000 heavy operations.

But with Schnorr signatures, we can add up all the signature verification equations and save some calculations. In a block containing 1000 transactions, we can verify:

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

Here is a series of point additions (from the point of view of computer operations, it is simply free) and 1001 point multiplications. Already a performance improvement of almost 3 times-only one recalculation is required for each signature during verification.

An article to understand how Schnorr signatures improve Bitcoin

Batch verification of two signatures. Because the verification equation is linearly additable, so long as all signatures are valid, the sum of these equations must also be established. We save some calculations because scalar and point addition are much easier to calculate than point multiplication.

2. Key generation

We want to keep our bitcoins securely, so we may want to use at least two different private keys to control bitcoins. One is used on a laptop or mobile phone (online wallet, hot wallet), and the other is placed in a hardware wallet/cold wallet. Even if one of them is leaked, we are still in control of our Bitcoin.

Currently, the way to implement this kind of wallet is through the 2-2 multi-signature script. That is, a transaction needs to contain two independent signatures.

With Schnorr signature, we can use a pair of keys (pk1, pk2), and use a shared public key P = P1 + P2 = pk1 * G + pk2 * G to generate a common signature. When generating a signature, we need to generate a random number (k1, k2) on the two devices, and generate two random points Ri = ki * G, and add hash(P, R1 + R2, m ), you can get s1 and s2 (because si = ki + hash(P, R, m)* pki ). Finally, add them up to get the signature (R, s) = (R1+R2, s1+s2), this is our shared signature, which can be verified with the shared public key. Others can’t tell if this is an aggregated signature. It looks no different from an ordinary Schnorr signature.

However, this approach has three problems.

The first problem is on the UI. To initiate a transaction, we need to initiate multiple rounds of interaction on two devices-in order to calculate a common R, in order to sign. In the case of two private keys, you only need to visit the cold wallet once: we can prepare the transaction to be signed in the hot wallet, select k1 and generate R1 = k1 * G, and then combine the transaction to be signed with these data Pass in the cold wallet and sign. Because R1 is already available, the signature transaction can be completed in only one round in the cold wallet. We get R2 and s2 from the cold wallet and pass them back to the hot wallet. The hot wallet uses the aforementioned (k1, R1) signature transaction, and the two signatures are added together to broadcast the transaction.

This experience is no different from what we can do now, and whenever you add an extra private key, the problem becomes more complicated. Suppose you have a wealth that is jointly controlled by 10 private keys, and 10 private keys are stored all over the world. At this time, you want to send transactions. How troublesome! In the current ECDSA algorithm, you only need to access each device once, but if you use Schnorr’s key aggregation, you need two times to obtain all Ri and sign. In this case, aggregation may not be used, and it would be better to use each private key to sign separately-so only one round of interaction is required.

After finishing the article, I got feedback from Manu Drijvers: In a multi-signature scheme with provable security, you need 3 rounds of interaction:

  • Choose a random number ki and the corresponding random point Ri = ki \ G, and then tell each device the hash value of Ri ti=hash(Ri), and then each device can ensure that you do not know the random number of other people change idea*
  • Collect all the numbers Ri and calculate the common R
  • sign

The second problem is the known Rogue key attack. This paper explains very well, so I won’t repeat it. It probably means that if one of your devices is hacked (for example, your hot wallet is hijacked) and you pretend that your public key is (P1-P2), then you can control the sharing of the two private keys with only the private key pk1 funds. A simple solution is to require the private key to sign the corresponding public key when setting up the device.

There is a third major issue. You cannot use the deterministic k to sign. If you use a deterministic k, then a hacker can obtain your private key with a simple attack. The attack is as follows: a hacker hacked into your laptop and completely controlled one of the private keys (such as pk1). We feel that the funds are still safe, because the use of our Bitcoin requires an aggregate signature of pk1 and pk2. So we initiate the transaction as usual, prepare a transaction to be signed and R1, send it to our hardware wallet, and send (R2, s2) back to the hot wallet after the hardware wallet signs… Then, the hot wallet went wrong, Unable to complete signing and broadcasting. So we tried again, but this time the hacked computer used another random number-R1′. We signed the same transaction in the hardware wallet and sent (R2, s2′) back to the hacked computer. This time, there is no more text-all our bitcoins are gone.

In this attack, the hacker obtained two valid signatures for the same transaction: (R1, s1, R2, s2) and (R1′, s1′, R2, s2′). This R2 is the same, but R = R1 + R2 and R’= R1′ + R2 are different. This means that the hacker can calculate our second private key: s2-s2’=(hash(P,R1+R2,m)-hash(P,R1’+R2,m))⋅pk2 or pk2 =(s2-s2′)/(hash(P,R1+R2,m)-hash(P,R1’+R2,m)). I find that this is the most inconvenient aspect of key aggregation-we have to use a good random number generator every time so that we can safely aggregate.

3. Musig

MuSig solves one of the problems-rogue key attacks will no longer work. The goal here is to aggregate the signatures and public keys of multiple parties/multiple settings without requiring you to prove that you have the private keys corresponding to these public keys.

The aggregate signature corresponds to the aggregate public key. But in MuSig, instead of adding the public keys of all joint signers directly, we multiply them by some parameters so that the aggregate public key P = hash(L,P1)×P1 +… + hash(L,Pn) ×Pn. Here, L = hash(P1,…,Pn)-this public number is based on all public keys. The nonlinear characteristic of L prevents the attacker from constructing a special public key to launch an attack. Even if the attacker knows what his hash(L,Patk)×Patk should be, he cannot derive Patk from it-this is the same as you want to derive the private key from the public key.

The rest of the signature construction process is very similar to that described above. When generating a signature, each co-signer chooses a random number ki and shares Ri = ki * G with others. Then they add up all the random points to get R=R1+…+Rn, and then generate the signature si = ki + hash(P,R,m) ⋅ hash(L,Pi) ⋅ pki. Therefore, the aggregate signature is (R, s)=(R1+…+Rn, s1+…+sn), and the method of verifying the signature is the same as before: s×G = R + hash(P,R,m)×P.

4. Merkel tree multi-signature

You may have also noticed that MuSig and key aggregation require *all signers to sign a transaction*. But what if you want to do a 2-3 multi-signature script? Can we use signature aggregation at this time, or do we have to use the usual OP_CHECKMULTISIG and separate signatures? (Translator’s Note: OP_CHECKMULTISIG is the operation code of Bitcoin verification elliptic curve multi-signature script)

Let me talk about the answer first, yes, but the agreement will be slightly different. We can develop an opcode similar to OP_CHECKMULTISIG, but check whether the aggregate signature corresponds to an element on the public key Merkel tree.

For example, if we want to use public keys P1, P2, and P3 to form a 2-3 multi-signature script, we need to use all pairwise combinations of these public keys (P1, P2), (P2, P3), (P1, P3) to build a Merkel tree and publish the root of the Merkel tree in the lock script.

When spending Bitcoin, we need to submit a signature and a proof that the public key corresponding to this signature is located on the Merkel tree marked by the root of the tree. For a 2-3 multi-signature contract, there are only 3 elements in the tree, and only 2 hash values ​​are needed for the evidence-the hash value of the public key combination we want to use, and a neighbor’s. For the 7-11 multi-signature script, there are 11!/7!/4!=330 kinds of public key combinations, and 8 hash values ​​are required for evidence. Generally speaking, the number of elements contained in the evidence is roughly proportional to the number of multi-signature keys, which is log2(n!/m!/(nm)).

But with the Merkel public key tree, we don’t have to be limited to mn multi-signature scripts. We can make a tree using any combination of public keys. For example, if we have a laptop, a mobile phone, a hardware wallet and a mnemonic, we can build a Merkel tree that allows us to use a laptop + hardware wallet, mobile phone + hardware wallet or a separate helper. Remember words to use Bitcoin. This is something that the current OP_CHECKMULTISIG cannot do-unless you use “IF-Else”-style flow control to construct more complex scripts.

An article to understand how Schnorr signatures improve Bitcoin

Merkel tree that aggregates public keys. More than just multi-signature 

in conclusion

Schnorr signature is great. It solves some computational overhead problems in block verification and also gives us the ability to aggregate keys. The latter is somewhat inconvenient to use, but we are not forcing everyone to use it-in any case, we can still use the ordinary multi-signature scheme, using separate, non-aggregated signatures.

I can’t wait to use Schnorr signatures and hope that the Bitcoin protocol can be incorporated into this signature scheme as soon as possible.

In addition, I really like MuSig. It is an elegant solution and the paper is easy to understand. I strongly recommend that you read the full text in your spare time.

 

Posted by:CoinYuppie,Reprinted with attribution to:https://coinyuppie.com/an-article-to-understand-how-schnorr-signatures-improve-bitcoin/
Coinyuppie is an open information publishing platform, all information provided is not related to the views and positions of coinyuppie, and does not constitute any investment and financial advice. Users are expected to carefully screen and prevent risks.

Like (0)
Donate Buy me a coffee Buy me a coffee
Previous 2021-09-09 08:40
Next 2021-09-09 08:43

Related articles