Predictable leader election with power above 1/e

[taoshengshi]

owe to @steven004 for his deep research.

Bug Description:

One of basic principles of secret leader election in blockchain is randomness, that means no one can predict who will be the leader before the election round.

However, in the current leader election process implemented in lotus (with the latest commit id:c618fe1 as of the issue is submitted), a miner with more than 20% power will always win election in each epoch, which makes the giant miners could be possibly try different measures to break the network or gain extra benefits, and collusion or bribe can happen easily.

Root cause:

In the current leader election process, each miner is to call gen.IsRoundWinner, in which types.IsTicketWinner invoked to run an election. When myPower/totalPower >= 20% (e=5)

h(vrfout) * totalPower < e * myPower * 2^256

will always return true since we have h(vrfout)<2^256, which means the miner wins the election all the time.

Another "issue" of this algorithm

Clearly, with the winning algorithm, any miner with >20% power will not have higher winning ratio than the miner only has 20% power. That means, we actually set a top-power threshold for rational miners.

This could be fine, not a big issue since it encourage decentralization.

One solution:

To avoid this, we could introduce a parameter ticketWeight with a winning ticket. With ticketWeight introduced, the election winning ratio (let's say Wr) for miners can be adjusted, and for each miner, One thing to be sure: Wr * ticketWeight = myPower / totalPower * e.

E.g. (not think through thoroughly, just an example), it could look like:
ticketWeight = e * sqrt(myPower/totalPower*e)
then, we have:
Wr = sqrt(myPower/totalPower/e)
Thus, we can achieve: Wr * ticketWeight = myPower / totalPower * e.

Once we have ticketWeight, we could change:
h(vrfout) * totalPower < e * myPower * 2^256
to:
h(vrfout) * totalPower * ticketWeight < e * myPower * 2^256

This will decrease winning ratio of high-power miners, and increase winning ratio of low-power miners while keeping their block reward fair.

Of course, the block reward for a miner who wins election in a round should be:
AmountBlockReward * ticketWeight

More benefit:

1. It solves the 20% issue;
2. It significantly improved low-power miner's winning ratio, that means, more chance for small miners to get rewards, though not as much. In other words, it improved certainty, which could attract more casual miners join the game;
3. Harder for big miners to take advantage of their power to get more rewards since less chances for them to produce blocks than their power.
4. We may think to adjust e's value. 5 may not be a good number.

[schomatis]

Hi @taoshengshi, this is working as intended. The comparison is a bit opaque, reordering the terms:

(h(vrfout) / 2^256) < (myPower/totalPower) * e 

The left term is a "random" number between 0 and 1, compared against the proportional power on the right with the e boost.

(edit: as pointed out by @whyrusleeping with the e multiplication at 5 the comparison will always be true for >=20%)

[whyrusleeping]

(going to reopen just for a bit of discussion)

This is generally a known issue, and one i'm not too worried about. The downside is if a single miner has greater than 1/e power, they get less rewards than their power ratio (since they can't win more than a single block per round).

The reason i'm not concerned about this is because i really dont want miners to be that large. Its far better to have them split up their power across separate miners (even if controlled by the same person). Setting things up this way provides a good incentive to break up your miner if its gets too big.

[whyrusleeping]

As for concerns about winning every block making collusion or bribing easier, i'd say that no matter what algorithm we select, large miners are going to be assumed to win roughly that proportion of blocks, whether its mathematically guaranteed to happen every round or not.

[sternhenri]

Again, the "less rewards" for power, or general upper-bound before sybils are incentivized are points that do not hold so long as the rewards actor is modified, per @Kubuxu 's suggestion (further explained below in the thread. It was my understanding per conversations with @zixuanzh that this would be addressed in the reward actor before mainnet launch (which I strongly believe it should. No reason to incent sybiling).

[sternhenri]

If you have precise attacks in mind that are not addressed by slashing or other mechanisms currently in the protocol, I would love to think about them @taoshengshi!

[steven004]

As for concerns about winning every block making collusion or bribing easier, i'd say that no matter what algorithm we select, large miners are going to be assumed to win roughly that proportion of blocks, whether its mathematically guaranteed to happen every round or not.

@whyrusleeping, I do not fully agree. Not exactly like this. No other chain systems we could see that a miner always wins election. Winning roughly that proportion of blocks is fine, but we know the proportion is less than 50% normally, thus winning ratio is less than 1/2. In our case, it's not like this.

In addition, what we really want to achieve is not to have winning ratio roughly proportionally to the power ratio (or stake share), but the block reward a miner gain roughly proportionally to the power ratio. They are not equivalent.

As mentioned in the one solution part of this issue, there could be a way (or any alternatives) to lower the winning ratio of large miners while higher ones of small miners. That means, we count both power ratio and individual rights in the election process, while issuing rewards that proportion of the power ratio to avoid the vulnerability.

[steven004]

If you have precise attacks in mind that are not addressed by slashing or other mechanisms currently in the protocol, I would love to think about them @taoshengshi!

May not be that easy for slashing breakage, but I would expect selfish mining will be easier.

[sternhenri]

@steven004

In addition, what we really want to achieve is not to have winning ratio roughly proportionally to the power ratio (or stake share), but the block reward a miner gain roughly proportionally to the power ratio. They are not equivalent.

I agree with this, but see the issue I pointed to, with this current issue, a miner with 2/e stake will still only win one block, thus we need to change the rewards function to ensure there's no clear incentive to break up power as soon as you get > 1/e. But thereafter, once that change is made, winning ratio will not be proportional to power for miners with > 1/e, but reward will be. For that same reason, I would not expect selfish mining to be easier. But I may be misunderstanding your idea there.

[steven004]

The key point of this issue is: the election implementation loses an important attribute - secret in some cases, which is considered as a base of blockchain's election security.

We are not able to achieve SSLE (Secret Single Leader Election), but we may still want to achieve Secret Leader Election.

And the idea here is to lower the winning ratio of large miners (at the same time, increasing the ratio for small miners), so that they could not be predicted to be a winner easily.

[sternhenri]

good point. thereafter there are issues with sublinear wins/reward schemes which incentivize sybils, just as here (if you want to stay secret stay away from 1/e).

[steven004]

Yeah. Good point.

I have a simple approach to let miners stay away from 1/e, very simple with one line code change.

How about to set a upper-bound for miner's winning ratio, let's say:
UPPER_BOUND_ELECTION_RATIO = 25% (you may want to change it to Integer in real code, and the code below changes accordingly)

And then, only need to change this:
h(vrfout) * totalPower < e * myPower * 2^256
to:

h(vrfout) * totalPower < e * myPower * 2^256  
   &&  h(vrfout) < 2^256 * UPPER_BOUND_ELECTION_RATIO 

Will this make things better? It looks solving the predictability issue without incentivize sybils.

Basically, I am still thinking that POS could do better than POW on election since the stake share are known.

[sternhenri]

Yeah I like making these things explicit as you do with UPPER_BOUND_ELECTION_RATIO... Don't know if it's worth pushing in time for mainnet... but @whyrusleeping can speak to that I'm sure...

[Kubuxu]

We have an alternative solution (base on Algorand's Sortition) which we will probably end up implementing for a few additional reasons. It is still in a bit in flux but should be landing soon.

[nicola]

Hello here, wanted to give a little update: there has been work to go around this issue (which as @steven004 is pointing out is problematic for selfish mining).

The code has been merged in lotus next #2084 and a spec update will come soon.

Thank you for the valuable bug reporting!

[magik6k]

This is now fixed