election-provider: allow duplicate submissions

[kianenigma]

Overall context

The current EMP signed submission phase rules out the possibility for two miners to submit the same score. In such a case, the solution is instantly rejected. The fundamental reason for this is using a btree-map of scores under the hood.

Instead, what we want is to allow duplicate submissions to exist, but incorporate the block number at which they have been submitted in them so that they can still be sorted. If two solutions with the same score have been submitted, the one that is submitted earlier is considered "better".

This will help @niklasad1 and the deployment strategy of the staking miner. Currently, a duplicate score is an invalid submission that results in full loss of funds. With this PR, we will allow duplicate submissions to exist.

---

Technical details.

Conceptually, I have a good guess of what we can do here.

I think this whole process has been over-engineered. We will have at most a very small number of submissions. Therefore, keeping it in a btree-map is an overkill. We can just store the indicies in a vector, and sort it any time that we insert into it.

-pub type SubmissionIndicesOf<T> =
-       BoundedBTreeMap<ElectionScore, u32, <T as Config>::SignedMaxSubmissions>;
+pub type SubmissionIndicesOf<T> = BoundedVec<
+       (ElectionScore, <T as frame_system::Config>::BlockNumber, u32),
+       <T as Config>::SignedMaxSubmissions,
+>;

This will simplify the code a lot, and helps us allow duplicate submissions as well.

I did a prototype of this here and seemingly it all works now? https://github.com/paritytech/substrate/pull/new/kiz-duplicate-signed-submission

[Ank4n]

This makes sense but thinking out loud, assuming we intend to open up staking miner for the community in future, wouldn't a vector solution be inefficient and stop us from doing that?

[rossbulat]

This makes sense but thinking out loud, assuming we intend to open up staking miner for the community in future, wouldn't a vector solution be inefficient and stop us from doing that?

How so, from a performance perspective?

[Ank4n]

This makes sense but thinking out loud, assuming we intend to open up staking miner for the community in future, wouldn't a vector solution be inefficient and stop us from doing that?

How so, from a performance perspective?

Yes, the sorting would get expensive with higher number of submissions. But may be we never want to have too many submissions.

I am also wondering if this opens up a new attack vector to slow down the chain? Basically push huge number of valid submissions to slow down election process? What happens in that scenario?

[niklasad1]

How so, from a performance perspective?

@Ank4n

is implying that sorting a Vec is O(n log n) vs O(log n) for a Binary Tree (BTreeMap) however this not really a concern right now because we haven't had more than 2 or 3 solutions per round and it's likely that solutions with the same score occurs which this fixes.

When we get solutions > 1000 I would be more concerned about that but this is still a temporary fix until we got a two-phase commit for submitting solutions (Kian could elaborate on that).

I am also wondering if this opens up an attack vector? Basically push huge number of valid submissions to slow down election process? What happens in that scenario?

You would loose the transaction fee and the bond which would be expensive

[Ank4n]

How so, from a performance perspective?

@Ank4n

is implying that sorting a Vec is O(n log n) vs O(log n) for a Binary Tree (BTreeMap) however this not really a concern right now because we haven't had more than 2 or 3 solutions per round and it's likely that solutions with the same score occurs which this fixes.

When we get solutions > 1000 I would be more concerned about that but this is still a temporary fix until we got a two-phase commit for submitting solutions (Kian could elaborate on that).

I am also wondering if this opens up an attack vector? Basically push huge number of valid submissions to slow down election process? What happens in that scenario?

You would loose the transaction fee and the bond which would be expensive

Can you lose bond even if its a valid solution?

[niklasad1]

Can you lose bond even if its a valid solution?

Right, it was like that with a BTreeMap with a BoundedVec that is not true anyway I guess.
Not sure, @kianenigma can probably explain that :P

[Ank4n]

This test early_ejected_solution_gets_bond_back shows if the queue is full and a new solution is added which is better than the weakest, the weakest solution is ejected and they get their bond back.

[kianenigma]

This pallet is configured in production to have a maximum of 16 or 64 submissions. In this scale, arguing over sorting complexity is moot IMO.

In the future, we might want to scale this to a larger value, but by then we would have to re-design a big part of this and this Vec won't remain. paritytech/polkadot-sdk#457

And yes, you can lose bond even if you submit a valid solution.