DPOI algorithm exploration
We are starting now a series of posts dedicated to the exploration of the DPOI algorithm.
Aims of modeling
The main aim of modeling is to find the weak points of the importance index calculation algorithm, accepted in the system, and to propose suitable improvements to the algorithm. DPOI algorithm is used in the U◦OS project. Detailed description can be found in the yellow paper.
According to the DPOI algorithm, the activity index is calculated for every account. It is intended as a measure of useful activity. It contributes to the total importance index, so that the active accounts are rewarded for the useful activity.
Thus, there is a danger of manipulating the DPOI algorithm to get a large activity index, without the real useful activity. There are some possible vectors of attack.
- Creating a set of isolated accounts and imitating activity between them (''splitting account'' attack).
- Expanding activity index of an existing active account, using additional an account set (''Expand rating'' attack)
- Getting the activity index from alien accounts that have a large activity index.
We'll consider these types of the attack now.
Using the Bitcoin network as a base of modeling
Modeling attacks requires a base account network imitating the typical behavior of a real blockchain network. Let us use the Bitcoin network as the base network.
To build the base network, we are going to use a selection of Bitcoin transactions from block 545373 to block 546373. We are only including the transactions with volumes 1.5 BTC and above. This selection of transactions has 57682 accounts.
The following figure shows the distribution of the activity index that we get by applying the NCDAwareRank algorithm to the selection of transactions from the Bitcoin network.
"Splitting account" attack
Let us take a look at a ''splitting account'' attack on a network consisting of two subnetworks: a base network and an attacking network.
Let us consider the attacking network as a number N of accounts. The accounts cyclically transfer an amount of assets to each other. The objective of the attack is to obtain the maximum fraction of the activity index of the entire network.
The activity index is calculated with the NCDAwareRank algorithm and by changing the value of the parameter μ.
Based on the algorithm parameters and the size of the attacking network, the attack modeling produces the following results:
You can see that the total activity index grows with the number of accounts. So, additional actions are necessary to protect the network from this kind of the attack (such as nonzero stack threshold for accounts participating in rating calculation, or nonzero cost of creating a new account).
Further we'll discuss this problem in more details.
"Expand rating" attack
Let us take the most active account in the base network. The account is 1NDyJtNTjmwk5xPNhjgAMu4HDHigtobu1s. The account's activity index is equal to 2.36e-03, i.e. 0.236% of total network activity. The aim of the attack is to get the maximum possible summary activity index.
We'll consider the attacking network which consists of 100 accounts. All of the 100 accounts cyclically transfer the assets through all 100 accounts, starting and finishing at the largest account of the network. The result is on the following figure.
You can see that with the growth of the exchange volume with the largest account, the total activity index of the attacking network grows as well. This growth, however, slows down when reaching a threshold, which makes it ineffective to keep increasing the exchange volume. You can see also that the NCDAwareRank algorithm (μ=0.2) is more resistible to this kind of attack than the PageRank algorithm (μ=0).
Generally, it can be shown that there is a limit for the total activity index that one can get with this kind of the attack. This limit is equal to (μ + η)/(1 - μ - η)R. R is activity index of the large account. Meaning of coefficients μ and η is described in the yellow paper.
This kind of attack can be used to obtain the rating using one's own large account as well as an alien account.
Obtaining a significant activity index requires a high exchange volume which must be comparable to the total outgoing volume of the large account. Providing the exchange volume that high enough is not an easy objective in case of using an alien large account.
Modeling the social activity index
The algorithm of calculating the activity index is applied not only to asset transfer, but to social connections between accounts as well, as described in the yellow paper. This means that we have the network nodes of two types — accounts and content (posts, comments, reposts). Let us have a look at the possible attack vectors. As the base network, we will take a selection from the testnet. The selection consists of 78 accounts and 570 content objects.
First, let us look at the effect of creating a large amount of posts. The results are on the figure.
You can see that creating posts first produces an increased growth of the account rating, but then the growth slows down. After creating 1000 posts (which exceeds the number of posts of the base network, 570), the rating reaches a mere 0.23, which is lower than a quarter of the total activity index.
Analysis of these results will be made in next posts.