# Substrate's NPoS overview

### Introduction to NPoS

NPoS is a very difficult problem to solve in a blockchain context. The reason for that is that we want a sovereign algorithm, be it our currently used `phragmen` or not, to solve the problem of NPoS for us offchain, and resubmit the solution back to the chain.

The problem of NPoS can be summarized as: given an input graph of nominations, find a distribution of stake for each nominator so that some objectives are optimized. As an example, say Alice nominates Bob, Charlie and Dave. Bob and Charlie are in the active validator set. How should Alice's stake be divided between them? What about Dave?

To contrast the simplicity of DPoS, such a problem does not exist there, since each nominator backs only one account. Even if you can back multiple accounts, your stake is split between them equally, or based on some pre-defined order. This is basically the same as splitting your funds into multiple accounts.

Current objectives of NPoS in substrate (and consequently polkadot and any other use of `sp-npos-elections` crate) is set to be:

- the backing stake of the least-backed elected validator, which should be maximized.
- the sum of backing stake of all elected validators, which should be maximized.
- the sum squared of backing stake of all elected validators, which should be minimized.

For a more extensive detail about all of this, see [this talk](https://www.youtube.com/watch?v=MjOvVhc1oXw).

For any additional question, feel free to ask @kianenigma in github or [Polkadot's watercooler](https://app.element.io/#/room/!FdCojkeGzZLSEoiecf:web3.foundation?via=matrix.parity.io&via=matrix.org&via=web3.foundation) chat.

---------

### Current Solutions

We have a set of algorithms that solve the NPoS problem, optimize it further, and reduce its size, all of which are packed nicely in `sp-npos-election`.

In the runtime, we have a dedicated pallet that does our multi-phase, offchain-oriented, election process, named `pallet-election-provider(-multi-phase)`, as described in [#6242](https://github.com/paritytech/substrate/issues/6242). pallet-staking will only use the election pallet and does not deal with details of the election itself.

An important part of the current system is that the pallet-staking and pallet-election-provider don't keep up with each other's changes, and this is intentional. At some point, pallet-staking will need to provide a snapshot of its nominators and validators (or a subset thereof) to pallet-election-provider. Form this point onwards, the two pallets can work independently.

This design decision has multiple benefits for us. Most importantly, we can use the snapshot as a **source of index-lookup** for all nominators and validators. In all solutions computed and submitted offchain, we never use account ids, but rather the much more efficient index in snapshot (compare a 4 byte u32 with 32 byte account id.).

### Bottlenecks

With this overview of the system in mind, let's look at the main bottlenecks:

1. **Snapshot creation**: This happens `on_initialize`, and can easily cause a heavy block. More importantly, there is a strict limit on how much memory each block can use, so we surely can never iterate a massive number of nominators in a single block.

2. **Solution Submission**: A solution that is being submitted must also not reach neither the block size limit, not the block memory limit. The latter is the real bottleneck with low congestion.

3. **Solution Verification**: The solution needs to be verified at some point. This needs to happen **against the snapshot**, and is thus again a memory intense operation.

The solution to all of this, and our direction of movement is towards doing all of this over multple blocks. The snapshot will be taken over multiple blocks, and the outcome snapshot will be a map of `page-index -> snapshot-page`, instead of one big flat snapshot.

The solution will need to take this into account. It needs to provide nominator indices in a way that is understandable, to the chain. Instead of identifying a nominator by a single index, each nominator is now identifiable by a `(page, index)` tuple.

Similarly, the solution verification also needs to take this into account, and verify each page of the solution against its corresponding page in the snapshot. Finally, the partial solutions need to be amalgamated into a single one.