This article explains the core of cross-chain bridge technology: random number “k” and “R” value


 412 total views

Cross-chain bridges are frequently attacked. From the random number k and R value in the core of the technology, understand the cause of the attack and the countermeasures.

Written by: Li Ni, Demmon

As most DeFi projects have gradually begun to move from Ethereum to multi-chain deployment, it has become a rigid demand for users to transfer assets between chains. From the technical dimension of asset ownership, cross-chain asset transfer can be divided into two categories: Custodial Service and Decentralization (or non-custodial). As a result, many “bridges” have emerged for users to transfer assets between chains. An interesting phenomenon is that after the DeFi protocol was frequently targeted by hackers in the past few months, because these cross-chain “bridges” also store a large amount of assets, they have gradually become a hot spot for hacker attacks. Recently, we have noticed several attacks on cross-chain bridges in the industry. For example, in a piece of news reported by Chain Wen, the cross-chain bridge was caused to lose millions of dollars worth of agreements and users. Generally speaking, hackers will choose a decentralized cross-chain bridge as the target, because the custody bridge is a centralized way to control assets, and it is more difficult to be compromised; while the decentralized cross-chain bridge is more sophisticated due to The design of cryptography and the engineering realization of computer code are often easy to produce loopholes in a certain place so that hackers can seize and exploit them to attack.

This article will introduce the core of cross-chain bridges that analysis users generally understand less: the core of multi-party security computing-the process of random number “k” and the R value derived from k. Popularize science about how these attacks happen and how How should a reliable decentralized cross-chain bridge be realized? For readers.

According to the chain news, ” Account private key was cracked? Dismantling the Anyswap cross-chain bridge was revealed byDetails “. The security incident was caused by two transactions with the same R value digital signature on the chain. The hacker calculated the account controlled by the Anyswap cross-chain bridge MPC through the two signature values. Private key, and then stolen the assets in it. So how is the private key calculated through the signature? Is there any way to prevent this security loophole from occurring? First of all, we need to understand what this R value is.

“R” value-the Achilles heel of account security

This article explains the core of cross-chain bridge technology: random number "k" and "R" value

As we all know, the authority of the blockchain account is realized by digital signature, that is, the user signs the transaction data with the private key to complete the transfer of account assets. At present, the widely used digital signature algorithm in the blockchain is ECDSA, which belongs to the “non-deterministic” type of digital signature algorithm, that is, the same data will have multiple legal signatures. This is because ECDSA will Introduce a random number k, and the R value is calculated by k. This is equivalent to saying: in order to crack the private key, the same R value must be obtained; to obtain the same R value, it is equivalent to the random number k value being exposed or colliding (that is, the two signatures have the same R). Therefore, the importance of the random number k is equivalent to the private key.

Assuming that the signature process of two transactions uses the same random number k, then the R of the two signature values ​​are the same. Suppose the two signatures are (R, s1) and (R, s2), then according to the ECDSA algorithm process, there are the following two equations representing these two transactions:

This article explains the core of cross-chain bridge technology: random number "k" and "R" value

Where m1 and m2 are transaction data, and sk is the account private key.

Observe the above two equations, where s1, s2, R are signature data, m1 and m2 are transaction data, which are all public and transparent, and everyone knows, but there are only two unknowns, namely A) random number k and B) account The private key sk. According to simple calculations, two unknowns and two equations, then the value of the unknown can be solved. This is the “solving equation” in middle school mathematics! Therefore, the private key formula can be solved naturally as follows:

This article explains the core of cross-chain bridge technology: random number "k" and "R" value

Because in the Anyswap attack, the hacker found that the signatures in the two transactions used the same random number k! Therefore, the hacker can easily calculate the private key sk that controls the cross-chain asset bridge! Then take the restored private key to transfer all the assets in the cross-chain lock contract!

So the question is: Why does this important random number k value appear repeatedly? Next, we will introduce the reasons why we need to use a multi-party secure calculation scheme to generate random numbers.

If MPC account signature is used, the value of k cannot be leaked!

This article explains the core of cross-chain bridge technology: random number "k" and "R" value

Compared with ordinary account signatures, multi-party secure calculation of MPC, Multi-party Computation (special note here, multi-party secure calculation is not multi-signature!) The account signature process is undoubtedly very complicated. Because the signature participant is no longer a single controller, but N multiple controllers cooperate to complete the signature process. A simple analogy is the process of multi-person collaboration. In the ordinary account signature process, only a true random number generator is used in the R value generation process, which can basically guarantee security; while in the MPC account signature process, since the participants are not unique, and theoretically agree that there may be malicious nodes, The generation of R value can no longer rely on the generation of a single user, because once the user is malicious, he will be able to control the random number k by himself, thereby controlling R, and then calculating the private key of the MPC account to steal assets. Therefore, during the MPC account signature process, the generation of R must meet the following three principles:

  • Non-single user generation
  • No one can get the value of k corresponding to R
  • The generation of random number k should be random enough to satisfy unbiased and unpredictable

To describe this process in a layman’s terms is: It requires a group of people to work together, but you can’t let you know what you are doing!

This article explains the core of cross-chain bridge technology: random number "k" and "R" value

Typical MPC design example: Verifiable secret sharing-the core guarantee for the security of the R value of Wanchain MPC account

In the Wanchain cross-chain bridge mechanism, cross-chain assets are kept by locked accounts, and locked accounts are managed by 25 anonymous (this value can be expanded or reduced as needed) Storeman nodes through multi-party computing (MPC). In the process of signing the locked account, the R value is jointly determined by the 25 Storeman nodes through the Verifiable Secret Sharing (PVSS), ensuring that no two transaction signatures have the same R value. Specific steps are as follows:

  • Step 1: Each Storeman node generates a random number locally through a true random number generator;
  • Step 2: Each Storeman node will share Shamir secrets and transmit the secret fragments to other nodes through a secure channel;
  • Step 3: After receiving the secret fragments transmitted by other nodes, each Storeman node accumulates locally to obtain a set of secret fragments, then multiplies the set of secret fragments by the elliptic curve base point, and broadcasts the result;
  • Step 4: Each Storeman node performs Lagrangian interpolation calculation on the broadcast data to obtain an elliptic curve point whose abscissa is the R value.

Although the above process is a bit complicated, the core idea is very simple, that is, the R value is jointly determined by 25 Storeman nodes, and each Storeman node contributes a part of the encrypted fragments, and finally the R value is synthesized through cryptographic operations. That is to say, the state described in the above sentence is realized: both of you are required to work together, but you don’t know what you are doing and who the others are.

Verifiable secret sharing can ensure:

It is impossible for any two transactions to have the same R value

First, the R value is determined by 25 Storeman nodes, rather than a single node. In theory, as long as there is one honest node among the 25 Storeman nodes, the R value is random; secondly, each node contributes to the R value The part is generated by a true random number generator, and the distribution is sufficiently uniform. Combining the two points, two transactions with the same R value will only occur when the sum of the random numbers selected by 25 Storeman nodes in the two signatures is equal. The probability is 2-256. To put it more vividly, The probability of being hit by a meteorite on the road is small.

This article explains the core of cross-chain bridge technology: random number "k" and "R" value

The k corresponding to the R value is completely confidential

We said earlier that once k is leaked, the private key can be calculated. In the signing process of Wanchain’s locked account, k is jointly determined by 25 Storeman nodes, but since the secret fragments are transmitted to each node through a secure channel, no node can recover the complete k value. In other words, the value of k is only a theoretical existence that can complete the MPC signature process normally, but it is indeed invisible to anyone.

Through the analysis of points 1 and 2, it is concluded that the security of locked accounts in the Wanchain cross-chain bridge instance is extremely high, and there will be no leakage of private keys.

This article explains the core of cross-chain bridge technology: random number "k" and "R" value

So what kind of situation will cause the same R value in the two transactions of Anyswap?

We have not read all of the MPC part of the Anyswap project. We can only derive such conclusions through the above-mentioned MPC theory and implementation mechanism: 1) If we did not adopt the real MPC implementation process and just hang up the name of MPC, or A random number k is generated by a single individual, resulting in the recurrence of k; or 2) There are major code problems in the implementation of the code, and such major technical errors should not occur in the view of a rigorous development team.

In another article “What is an ideal cross-chain bridge?” “There is a paragraph about the MPC cross-chain bridge: “Anyswap: Explain in one sentence, “The hacker found the Anyswap code loopholes, obtained the public and private key pair, and stole the assets.” Vulnerabilities that appear. The author does not agree with all kinds of arguments about loopholes that will occur when using MPC. Several of the peers in the industry that have implemented MPC do not think that such loopholes or errors are a common phenomenon that will occur. The essence of adopting MPC is to achieve multi-party anonymous and secure computing. Otherwise, if this is not even guaranteed, why use MPC , Wouldn’t it be simpler and more secure to use a multi-signature, single-signature scheme? “If you can use the public chain consensus of enough nodes, you can largely avoid the situation similar to this attack (MPC is not decentralized enough).” The conclusion of this sentence is also disagreeable. Whether the R value of different transaction signatures is repeated does not depend on the number of nodes, but on the way the random number is generated during the signing process. If the random number in the signature process is jointly determined by multiple nodes through multi-party calculation, then only 20 nodes can also generate secure random numbers; on the contrary, if the random number is not generated in a secure and distributed manner during the signing process, Then no matter how many nodes are piled up, it is futile. The project browser shows that there are more than 20 nodes participating in the MPC calculation. If the calculation method is indeed MPC, then the probability of R value collision is negligible. Therefore, the project attributed the reason for the same R value of the two transaction signatures to the insufficient number of participating MPC nodes, which is undoubtedly evasive and misleading.

At the end of the article, I especially want to emphasize the importance of random numbers to the blockchain. It is not only used in the account signature process, but also in the fields of PoS consensus and shard algorithm, which directly determines the security of the entire system. Sex, must not be ignored. The production of a small random number is not that simple. It is a holy grail field that the entire mathematics and cryptography circles have been pursuing continuous optimization. A blockchain team should continue to accumulate in the field of distributed random number generation algorithms, design and continuously optimize the random number generator on the chain, so that it can provide secure random numbers for the cross-chain and consensus process, and for the entire blockchain, The DeFi field provides reliable, usable, and credible cross-chain bridges.

Disclaimer: As a blockchain information platform, the articles published on this site only represent the author’s personal views, and have nothing to do with the position of ChainNews. The information, opinions, etc. in the article are for reference only, and are not intended as or regarded as actual investment advice.

Adblock test (Why?)

Disclaimer: does not endorse any content or product on this page. While we aim at providing you all important information that we could obtain, readers should do their own research before taking any actions related to the company and carry full responsibility for their decisions, nor can this article be considered as investment advice or recommendations. Every investment and trading move involves risk, you should conduct your own research when making a decision.