Fairness issue on NXT and its solutions

Hi team,
We are blockchain researchers from the National University of Singapore.
Our current research analyzed the fairness of NXT incentive algorithm. Several issues are found, so we try to report here and wish to hear some feedback from the team.

We found that the current NXT forging algorithm does not ensure that the block winning probability is proportional to the stake deposited by players.
Specifically, the players with more stakes will receive a higher ROI comparing with poor ones.
In a long-term staking competition, this mechanism will encourage players to join the mining pools and making incentives centralized.

Let me show you some intuitions that the issue caused.
Currently, to propose a new block, NXT forgers must calculate a 'hit' number and a 'target' number, where,

Target = BaseTarget * EffectiveBalance * TimeSinceLastBlock

and,

hit = gethit(publicKey, lastBlock) .

The gethit function can be regarded as a hash function or verifiable random function. The hit number is fixed for every block and the target number increases every second (because of the variable TimeSinceLastBlock). Once a new block is found, every forger will update his hit in the current block and continuously check if hit < Target for the current timestamp. The player who is assigned the shortest waiting time becomes the proposer of the next block.

We can simplify the waiting time formulation in this form
Waiting_Time = constant * Hash(pk,...)/balance .

Suppose there are two forgers A and B, who control S_A and S_B stakes, respectively ( assuming S_A < S_B). By some probability calculation, we can show that the probability forger A generates a smaller Waiting_Time with probability S_A/2S_B, which is less than S_A/(S_A+S_B). Consequently, the rich forger will have a higher probability to propose the next block, making himself becomes even richer.

To address this problem, we also proposed a practical solution that can be deployed easily on current NXT client. The solution is just modifying the current target and 'hit' formulas so that the proposer selection algorithm can be fair. Since we can not put any latex formula here, please check our paper for more details. We are very happy to help the team solving this bug. :slight_smile:
Here is the paper link.

3 Likes

Congratulations on your publication. We are aware that the probability to generate block is not exactly proportional to the stake. This was noticed back in 2014 - see "The math of Nxt forging" by mthcl.

Indeed the rich are getting richer in NXT but not that much since all coins are pre-mined and the only reward for generating block are the fees. The following result should apply only to networks with block reward:

In other words, the mining game ends with the fact that one monopoly miner acquires almost 100% staking power.

Nevertheless, thank you for proposing a solution!

1 Like

I agree with you that if the system providing no block reward or very few rewards (like transaction fee). The monopolizing process can move very very slow, even for years.

Nevertheless, the stakers taking care of staking reward may dissatisfy with this unfair mechanism since the smaller they are, the lower ROI they will obtain. As an example, the current individual miner (with ~0.5% staking power) can only obtain ~0.3% incentives if mining independently ...

I think that may partially explain why forging power is over-centralized. Besides the convenience reason, stakers have much higher ROI depositing into pools rather than deploying clients by themselves.

I agree with you that if the system providing no block reward or very few rewards (like transaction fee). The monopolizing process can move very very slow, even for years.

Actually it depends on how much fees the minority stakeholder pays. If he doesn't make transactions, he will remain with same percent of the stake.

Nevertheless, the stakers taking care of staking reward may dissatisfy with this unfair mechanism since the smaller they are, the lower ROI they will obtain. As an example, the current individual miner (with ~0.5% staking power) can only obtain ~0.3% incentives if mining independently ...

Well, if the rest 99.5% are owned by a single account, yes. But that's unlikely in practice. If, for example, the rest 99.5% stake is distributed to even smaller accounts, the guy with the 0.5% stake should be getting more than 0.5% of the blocks.