Analysis of validator collusion

Bifrost is dedicated to providing a liquidity solution for PoS mechanisms on public chains. On Bifrost’s platform, users can buy the votes needed to run PoS nodes at a low price. We need to consider the impact of vote-buying behavior on PoS public chains’ security. Let us take Polkadot as an example for scientific analysis.

The origin of shared security

First, we review the development history of the blockchain consensus mechanism. As the earliest consensus mechanism, PoW emerged with the emergence of Bitcoin. There are only a few successful projects, such as BTC and ETH1.0. The reason is that globally computing power resources are limited. When most computing power focuses on Bitcoin, other PoW public chains face challenges to start safely. Because the network cannot attract enough computing power, its security is vulnerable. The big miners’ computing power is enough to launch 51% attacks on some smaller PoW networks.

Later, people invented the PoS mechanism, relying on their valuable tokens as collateral to maintain network security so that the consensus process no longer needs to compete with other projects for computing power. However, PoS does not eliminate the dilemma faced by PoW because maintaining a PoS network requires necessary security expenditures. When the currency price is too low, and the value capture ability is insufficient, high inflation will lead the network to a death spiral. However, PoS networks will not directly compete for computing power resources as between PoW networks, at a certain point in time, the purchasing power to support the currency price in the market is absolute. To magnify, the total economic value in the world is also absolute. The currency prices between different currencies are still competitive. For start-up projects with relatively low currency prices, the network security is too unreliable. This security issue still hinders innovation in the blockchain field.

Faced with such problems, Polkadot put forward the concept of “shared security”. Polkadot uses the relay chain + parachain architecture so that parachains do not need to provide security by themselves but can reuse the security of Polkadot. Therefore, as a Polkadot parachain project, the projects can focus on developing their business logic. Also, Polkadot provides secure cross-chain interoperability. Cross-chain message transfer between parachains can be carried out safely through the relay chain, and no additional trust mechanism is needed.

Implementation and problems of shared security

Before discussing the security of the Polkadot parachain, we can briefly review the architecture design of Polkadot. Polkadot adopts the system architecture of the relay chain, parachain, and the relay chain’s validators. Provide block validity and availability verification for parachains, and adopt erasure coding to provide storage backup for parachain blocks and Proof of Validity data (PoV). Parachain nodes (collators) are responsible for building the blocks and ledgers of the parachain and providing more professional services to external users.

During Parachain Collators’ operation, the relay chain will randomly allocate multiple validators according to specific rules to verify the blocks and PoV submitted by Collators. The safety and availability of the parachain depend on the relay chain, overall security, and security of validators. If more than half of the validators assigned to a parachain collude to commit malicious acts, the parachain will be unavailable for some time, although these malicious nodes are punished by the relay chain itself (slash). We can make a mathematical analysis of the probability of this situation.

Problem

Assuming that the Polkadot system has 1000 validators and 100 parachain slots, each parachain can get an average of 10 randomly assigned validators. If there are more than five malicious nodes, the attack on the parachain can launch successfully. If there are a total of 20 malicious nodes in these 1000 validators, how to calculate the probability that more than five malicious nodes assign to the same parachain in one allocation (we will call this ‘event E’)?

This probability is a very interesting permutation and probability calculation problem. First of all, continue to simplify this problem and equate it to this scenario: N = 20 (bad validators), K = 100 (parachains). What is the probability that six or more bad validators enter the same parachain? This problem is essentially a conditional addition of a positive integer.

Problem-solving ideas

A recursive degradation method is to solve the problem into a small one, and the large parameters transform into small parameters, and the result returns. First, calculate the number of permutations (P1) without event E, calculate the total number of arbitrary permutations (P2), and finally calculate the value of 1 — (P1 / P2), that is, the value of the probability of the result.

Solving process

The number of bad validators (N), the number of normal validators (M), the number of parachains (K), the limit of the number of bad validators for a single parachain (R), the number of validators filled by a single parachain (T), the above parameters are all positive integers.

The problem can be simplified as:

P(N, M, K, T, R)
=> P(20, 980, 100, 10, 5)
=> [20 = i1+i2…+i100]
=> [980 = j1+j2…+j100]
=> [1000 = (i1+j1)+(i2+j2)…+(i100+j100)], in+jn = 10

The value range of jn is [0, 10], and the value range of in is [0,5] because if it exceeds 5, an E event will occur, which does not meet the preconditions. According to the multiplication principle of permutation and combination, the task of addition and division is completed in 100 steps. The number of combinations in step 1 is C(20, i1) C(980, j1), and the remaining number of combinations to be solved P(20-i1, 980-j1, 99, 10, 5), namely:

P(20, 980, 100, 10, 5) = 
C(20, i1)C(980, j1)P(20-i1, 980-j1, 99, 10, 5)

Following the same idea, we can solve P(20-i1, 980-j1, 99, 10, 5), namely:

P(20-i1, 980-j1, 99, 10, 5) =
C(20-i1-i2, i2)C(980-j1-j2, j2)P(20-i1-i2, 980-j1-j2, 99, 10, 5)

Since the value range of jn is [0,10], the value range of in is [0,5], and in+jn=10, according to the principle of permutation and combination.

C(20, i1)C(980, j1)P (20-i1, 980-j1, 99, 10, 5) corresponds to the sum of the following categories:

i1 = 0 => j1 = 10 => C(20, 0)C(980, 10)P(20, 970, 99, 10, 5)
i1 = 1 => j1 = 9 => C(20, 1)C(980, 9)P(19, 971, 99, 10, 5)
…
i1 = 5 => j1 = 5 => C(20, 5)C(980, 5)P(15, 975, 99, 10, 5)

Continue iterating (recursive degradation) until the value of P(N, M, K, T, R) can obtain on a smaller scale. Note that the values ​​of T and R always remain unchanged. When KR >= N, KR >= M, K*T = N+M, P(N, M, K, T, R) is meaningful. Moreover, when N <= R, R no longer has a restrictive meaning. At this time, we can get:

P(N, M, K, T, R) = C(KT, T)C((K-1)T, T)…C(2T, T)C(T, T)

At this point, the process of a ‘recursive call’ can end. Record the value of P(N, M, K, T, R) as P1, and record the value of any combination as P2, P2 = C(1000, 10)C((990, 10)…C(20, 10)C( 10, 10), 1-(P1/P2) is the probability value of event E.

Based on the above problem analysis and problem-solving ideas, we can quickly write the corresponding algorithm program and calculate that when there are 20 malicious nodes in 1000 nodes, the probability that they can collude to launch an effective attack on the parachain is: 0.0000005666859763811864585098205641632487151064266458860864606967870544507157082900619766159677426216.

When the number of malicious nodes is 100, the probability value is:
0.0129923223383844666654513109068870692897226919075963159959911315405387765954746781823649549513027886.

When the number of malicious nodes is 200, the probability value is:
0.4692855359876098354641144084770167516167561963346186017546237875587669675673670636786298382465593851.

According to the running data, let us draw a picture. The number of validators in the relay chain is 1000, the number of slots is K=100, and the number of validators assigned to each slot is T=10, where the number of malicious validators is N, then event E: more than R (R=5) malicious validators are the relationship between the probability P and N assigned to the same parachain is as follows:

It can be seen from the figure that malicious nodes are between 0–100, and the possibility of collusion is low. As malicious nodes exceed 100, the possibility of collusion increases rapidly. When malicious nodes reach 300, the possibility of collusion almost reaches 100%.

In the Polkadot consensus process, there is a Byzantine 3f+1 mechanism. For the Polkadot relay chain, the number of malicious nodes is less than 1/3, the relay chain is safe. For the parachain, the number of malicious nodes in the chain needs to be less than 1/10.

Of course, what we have calculated above is the probability of malicious collusion in the Polkadot parachain. Any one of the 100 parachains counts into event E. If only one specific parachain joins, the probability will be too minimal.

The impact of shared security on Bifrost
Bifrost currently uses staking derivatives (vToken) to provide liquidity for pledged assets, which will inevitably lead to the original PoS network’s native assets and their corresponding voting rights being mapped in the Bifrost protocol. Bifrost’s consensus on the part of the original assets that participate in staking security has also been transferred to the Bifrost network accordingly.

If the Bifrost consensus security attack cost is lower than the original PoS consensus security cost, hackers will deliberately attack the Bifrost network to complete the original PoS network attack. This attack will make the Bifrost network no longer trusted and even be countered by other PoS networks. Only when the Bifrost consensus security is higher than or equal to the original PoS network can the Bifrost protocol provide large-scale staking liquidity for other PoS networks under objective conditions.

People can buy voting rights from the Bifrost platform at a low price, and they are elected as validators. If these nodes do evil, many DOT assets used for staking will be punished, seriously threatening the security of the Bifrost system. To ensure that these validators do not collude and do evil, and to ensure the safety of Polkadot parachain and Bifrost itself, the Bifrost technical team conducted a careful investigation of Polkadot’s Slash mechanism and NPOS rules and designed an effective risk prevention and control mechanism. Regarding the design of Bifrost’s Slash risk prevention and control mechanism, follow-up articles will continue to give specific descriptions and detailed analysis.

What is Bifrost?

Bifrost is a Polkadot Ecosystem DeFi infrastructure protocol that aims to provide staking liquidity and currently offers a derivative vToken for Staking and Polkadot Lease Offering (PLO). It is also a member of the Substrate Builders Program and Web3 Bootcamp. vToken can optimize transactions in multiple scenarios such as DeFi, DApp, DEX, and CEX.

vToken can optimize transactions in multiple scenarios such as DeFi, DApp, DEX, and CEX. vToken can be used to realize the transfer channel of governance right such as Staking and PLO to hedge the risk of Staking assets. In extended scenarios such as when vToken is used as collateral for lending, the staking proceeds can offset part of the interest and realize low-interest lending.

Website https://bifrost.finance/
Github https://github.com/bifrost-finance
Telegram https://t.me/bifrost_finance
Medium https://medium.com/@bifrost_finance
Twitter https://twitter.com/bifrost_finance
Discord https://discord.gg/8DRBw2h5X4