About phragmen election's complexity

[vjoke]

From the source code, I find that election process may consume more time than a slot duration, if it is true, then would it be an attack vector if malicious users have registered many many validators ?

[kianenigma]

In theory, it is true that there could be an infinitely large number of validators which makes the election algorithm exploitable. The complexity of such operations that are user-controlled needs to be checked.

Do you have solid analysis in hand showing that under how much load (candidates and votes per se), how much slower your chain got? or is this a gut feeling that you are sharing here based on observing the complexity of the code?

[vjoke]

It's just a gut feeling now, It's obvious since no limit on the loop with candidates. I have no solid analysis now, because I am just beginning to setup a new chain with substrate.

[vjoke]

In addition, if one validator has many nominators, it will consume more time to reward/slash all the nominators.

[gavofyork]

cc @AlistairStewart

[burdges]

We need each validator to have many nominators because we want roughly equal amounts to be at stake for each validator. If we lacked this then we'd create many worse problems, like not assigning equal numbers of validators to each parachain.

[AlistairStewart]

The guarantee that we get is that the running time is at most linear in the total size of the vote transactions. We loop over the candidates and over the votes themselves, but there are no nested loops.

If we have a lot of votes, then our running time can indeed be large, but it's expensive to pay the transaction fees to push that time up. Now we hope here that it should not matter that our computing time is longer than the slot time, because anyone who produces an alternative block at this height also needs to do the computation.

In my Python implementation, I was still getting under 1 second for 1000s of votes. The rust should be faster.

[kianenigma]

I should try the same in the runtime externalities. afaik test_externalities will not actually write to a database an everything is kept in memory so it will be a fair comparison. Can you share the details of your benchmark exactly, @AlistairStewart? How many nominators / validators / votes in total + how votes are spread.

[AlfonsoCev]

The running time of Phragmén is linear in E*m, where m is the number of validators to elect, and E is the number of nominator-candidate pairs, i.e. E is the sum over the nominators of the number of candidates supported by that nominator. So E would be the user-controlled parameter. As Al said, when a nominator submits a list of candidates, we can charge a fee proportional to the list size, so that increasing E considerably would be pretty expensive. FYI, the math analysis of Phragmén is here.

[kianenigma]

I will for now use this issue as a tracker than sometime-soon (probably before BETA) a set of benchmarks should be added to the rust impl of phragmen to verify.

[AlfonsoCev]

Another thing to consider is the size of a solution to the NPoS election problem, where a solution consists of a set of m validator candidates, and a distribution of the nominators' stakes over these candidates. A solution should be small enough to fit as a transaction on-chain, i.e. just a couple hundred of megabytes long, and we would like to receive several tentative solutions from the candidates themselves, so we can choose and keep the best one.

Luckily we have a compact encoding where the bit-length of a solution is linear in the number of nominators, and it is independent from the number of validator candidates. So, if we see that we're getting way too many nominators, we can add a minimum required amount of stake to be a nominator.

[AlistairStewart]

One of the python reference implentations has large random instance examples that can be used as benchmarks. Try running riparty() with various values from here . It can't handle electing 1000 candidates with 10000 voters very well but will likely work fine with 100 validators.

[kianenigma]

stale; this operations also now happen offchain.