NPoS Impacts, Critiques and Future Potentials in Polkadot [Decoded Talk]

Author: hackmd.io

Length: • 9 mins

Annotated by Kian

This [talk/article] is divided in three main sections: 1) what is Nominated Proof-of-Stake (NPoS) and why does Polkadot use it; 2) how has NPoS been performing in Polakdot and how does it compare to non-NPoS solutions and 3) future work and improvements.

todo: glossary with most important concepts used throughout the talk/posts, so that we’re on the same page.

idea 1. economic security in PoS is tightly coupled to the amount of stake backing the active validators. However, there are other parameters to consider (usability, freedom of choice, fair representation, economic efficiency).

One of the most important design decisions of any PoS blockchain is how the protocol selects the subset of validators from a list of candidates should propose the next blocks to the network. The most intuitive solution is to select the subset of validators that have higher stake, in order to maximize the amount of stake and – hopefully – the maximize the economic security (ES) of the network.

However, simply trying to maximize the amount of stake backing the selected validators is not necessaily the best strategy to optimize the overall security of the network. Other factors such as decentralization also impact economic security. In addition, there are other important aspects to consider that affect the network incentives, capital efficiency, fairness and UX of token holders. The Polkadot PoS scheme tries to optimize more parameters than only the amount of stake backing the active validators in the network. In this talk/post, we will discuss which other factors we consider important and why, and have these design decisions impact the security of the network.

Polkadot uses a variant of PoS called Nominated Proof-of-Stake (NPoS). In NPoS, token holders may chose to become a validator candidate or a nominator. Nominators delegate their stake to validators they trust, which allows any token holder to contribute to the economic security of the network and earning a share of the validators’ rewards.

Nominators are incentivized to contribute to the economic security of the network by earning a share of the rewards of the validators they nominated. In addition, slashes are also applied on nominators, which incentivizes nominators to carefully select which validators to back.

Key takeaways:

  • Polkadot staking scheme is called Nominated Proof-of-Stake, where validators and nominators stake their tokens to provide economic security to the network;
  • Insted of simply trying to maximize the amount of stake backing the active validators, NPoS also aims at optimizing other factors that improve the overall economic security, fairness and usability of the network.

What is NPoS optimizing for?

idea 2. Polkadot’s NPoS optimizes for economic security, with focus on fair representation, nominator freedom of choice and capital efficiency.

Eventually, the staking protocol needs to decide on (i.e. to “elect”) the subset of validators that will take part on the block production for the next upcoming blocks. As mentioned, different election mechanisms can optimize for different outcomes.

Similarly to other PoS networks, NPoS aims at to maximize the amount of stake behind the elected winners. By doing so, we increase the incentives of the selected validators to behave as expecteed by the network. From a game theoretical perspective, the higher the stakes backing the winners, the lower the incentives to misbehaved since the costs for misbaheving are higher (due to slashing) and the potential future losses also higher.

There is a detail in Polkadot’s consensus protocol that guides what NPoS election algorithm should optimize for. In Polkadot, the elected validators have equal voting power in the consensus protocol. In practice, this means that the validators that are selected to author the next set of blocks have the same voting power, regardless of their backing stake.

Thus, one of the NPoS election scheme goal’s is to ensure that the result of the election consists of a set of winners which stake is as evenly distributed as possible. In addition, the NPoS scheme was designed to prevents any minority to be overrepresented in the winner set, in order to prevent an attacker – which in PoS is assumed to be a minority – from acquiring asymmetric power over the elected validator set. We call this property fair representation.

todo: outline advantages of pro-rata weight of validators.

Finally, the NPoS scheme also optimizes for nominator freedom and capital efficiency. In doing so, the NPoS algorightm tries to allocate as much of the capital locked from nominators as possible, while giving a relatively high degree of freedom for nominators to select the validators they trust the most.

Key takeaways:

  • Polkadot’s NPoS election algorithm is designed to maximize the following properties: economic security; fair representation; capital efficiency and nominator freedom and satisfaction.
  • Polkadot’s NPoS election algorithm tries to answer the following question: “Given the current set of validator candidates, their nominations and their overall backing, which subset of validators optimizes the economic security, fair representation and capital efficiency of the network?”,

How to measure NPoS election solutions?

idea 3. optimization algorithm requires heuristics to assess/compare solutions.
given that NPoS is maximizing not only backing stake but also other factors, we need to define the concept of “election score” that helps us comparing different solutions. the election score (sum_stake, min_stake,variance) works for NPoS.

  • goals: maximize sum_stake, maximize min_stake, minimize variance
  • election score verification and comparison must be relatively cheap to run on-chain.

Computing the election result that optimizes the parameters described above is a NP-complete optimization problem. As expected, the optimization complexity grows with the number of validators, nominators and number of votes per nominators (edges). For a reasonable number of validators, nominators and edges, it becomes infeasible to compute the election on-chain.

W3F researchers have put forward a set of heuristics and approximations that, coupled with protocol-level design optimizations (e.g. off-chain computation, on-chain verification) have made it possible to use NPoS in Polkadot. These optimizations are out of scope of this talk/post, but you can learn more about how the election scheme works here and how the staking-related pallets are designed here.

There are, however, a few important insights from W3F’s research outcomes that is worth mentioning here:

  • First, is that a “good” election solution (i.e. approximate to the optimal solution) can be computed relatively fast using a set of heuristics;
  • competing solutions can be accurately compared based on their sum_stake, minimum_stake and stake_variance.
  • there is an algorithm that allows any party to verify if a solution computed by an untrusted third party satisfies the required properties; and finally,
  • the verification algorithm can be computed in linear time with the number of edges.

note: not sure if this jump is the correct one. How did we come up with the elections core parameters? In insight, they do make sense, but I wonder if these were part of the results from W3F paper/work on npos phragmen etc or just approximations. Not very clear from the W3F paper either, although those score parameters are mentioned.

An important finding that we should retain for the remaining of the talk/post is how to compare competing solutions for the same election. Note that since the election is an NP-optimization problem and the solutions are computed using heuristics, there can be different solutions proposals that approximate the optimal solution. Thus, in the presence of competing proposals, it is useful to define a way to compare and rank different solutions. We achieve this by defining an election score and a simple algorithm that ranks different election scores.

In NPoS, an election score consists of a tuple of the overall sum of the stake (sum_stake) of the election, the stake associated with the validators with the least stake in the winner set (min_stake) and the variance of stake backing each of the winner validators (variance).

Competing election results with different scores are ranked by their sum_stake, min_stake and variance parameters. More specifically:

  • An election score with higher sum_stake is preferred, as it maximizes the economic security by making it more expensive to attack the network (the slashes are propotionally as high as sum_stake). It also means that the solution was able to “stack” more backing into the winner set, making the solution more capital efficient (the ratio between the locked assets and assets ensuring the security of the network is lower)l
  • An election score with higher min_stake is preferred, as it ensures that all the winners with lowest backing still have a high enough incentive to behave as expected.
  • An election score with lower variance is preferred. Lower variance means that the available stake was “well distributed” among the winners, compared with one solution with higher variance.
  • The election solutions are ranked strictly based on each election score parameter and, as such, sum_stake takes precedence over min_stake and min_stake takes precedence over variance.

hm, confirm claims above on variance.

Practically, we also define a minimum election accepted score in Polkadot to ensure a baseline of economic security.

❓ how accurately does the election score used in Polkadot help steering the NPoS election outcomes? Any good data for this?

Elections walkthrough examples

idea 3. walkthrough simple examples of elections outcomes and how they compare in terms of each relevant parameter, with images.

Now that we have a good overview of the goals of NPoS and how to measure and compare election solutions based on those goals, let’s go through a few elections using NPoS and an approval-voting based scheme and gauge their outcomes.

todo, let’s perhaps re-use examples that have been used in other talks/articles.

idea 4. compare election score of NPoS Polkadot vs approval-based Polkadot based o historical data; Compare other chain’s election score with their election scheme vs if NPoS was used.

In this section, we compare the election score in Polkadot using the current NPoS scheme with a scheme that simply tries to optimize the backing stake of the network. We use historical Polkadot data to compare both schemes and

In addition, we also compare the election scores of

We can compare the staking election scores of Polkadot/Kusama with other blockchains without having to touch the economic security topic. Instead, we can keep the discussion at a lower level and compare min_stake, staked_total and variance metrics with and without the phragmen across multiple projects.

Plot 1.
Historical and current election score trends in Polkadot, given the number of voters, candidates and locked/active stake.

  • election_score {min_stake, staked_total, variance} changed over time.
  • num_nominators, num_validators, total_stake_locked, total_active_stake

Plot 2.
Compare election score of historical NPoS with approval-based election.

  • election_score_npos {min_stake, staked_total, variance}
  • election_score_approval_base {min_stake, staked_total, variance}

Plot 3-X.
Compare election score of historical approval-based election from other nominator-based PoS blockchains vs if NPoS was used.

  • election_score_X_npos {min_stake, staked_total, variance}
  • election_score_X_approval_base {min_stake, staked_total, variance}

Plot Y-Z.
insert ideas/wishes here

  • Elected validators have the same weight regardless of their backing stake;
  • Election optimizes for fair representation, capital efficiency and voter freedom;
  • Finding a NPoS election solution must run off-chain due to space/computation requirements.
  • Data insights: (TODO after data analysis)

Future improvements and directions

idea 4. outline future improvements and directions, link to issues/discussions so that the community can contribute.

  • Group nominators/validators by operator and introduce the notion of “operator” in the NPoS algorithm to improve decentralization/ Nakamoto-Operator Coefficient (note: do we want to talk about this?)

The main service provided by staking system is economic security. The economic security can be measured by the amount of stake backing the active validator set, from self-stake (staked by the validators) or nominated staked. As an heuristic, we expect that a chain is as secure as the amount of stake backing the active validator set.

Intuitively, the best way to maximize the economic security in staking is by selecting the validators with the highest amount of backed stake. In this case, the election mechanism would consist on selecting the top validators from a list of candidates sorted by stake. However, although it is critical to maximize economic security, there are other important properties to consider such as fair representation and capital efficiency. Electing the validators solely based on the amount of stake

todo: graphic with nomination edges representing votes to candidates.

Let’s start with a simple

Stake of the nominators must be distributed as evenly as possible among the validators, while 1) (freedom) respecting the nominator’s preferences; 2) (security) the minimum stake backing a validator should be maximised; 3) (security) the sum of stake backing winners should be maximised and 3) (security) variance of the winner cohort should be minimised.

Advantages:

  • NPoS has a mechanism to prevent overrepresentation of an (adversarial) minority
  • Freedom and flexibility for nominators
    • many options to pick from
    • always exposes with the full stake if at least one of the N nominated validators was chosen

Disadvantages:

  • Optimisation problem is too expensive to run on-chain (at least verification is linear with the number of edges)

idea: election needs to run off-chain since it’s a heavy optimization problem. that’s solved through incentivizing off-chain participants to run the election off-chain and submit election solutions on-chain.

Ideally, we would like to leverage available blockspace to run the election, to piggyback on the trustless and security properties provided by the blockchain. However, the on-chain resources are scarce. The NPoS election scheme used in Polkadot is an optimization algorithm that

  • One concern (Ankan)
    • NPoS incentivizes nome operators to run multiple nodes (low variance, etc)
    • How come other chains have more validator nodes? Why is that?