Technical Guide | How does Poka's NPoS mechanism work?

Source of this article: PolkaWorld

Author: Alfonso Cevallos

The Polkadot blockchain will implement a Proof of Stake Nomination ( NPoS) mechanism, which is a relatively new scheme for selecting verification nodes participating in the consensus protocol. In this article, we will give an introduction to NPoS and a review of Web3 Foundation research. We also explained the special way to verify that the node is selected. So how does NPoS work in Poka?

Verifiers and nominees

Several times a day, the system selects a group of entities that become validators , and they will play key roles in highly sensitive protocols, such as block production and final verification, in the next few hours. Their job requirements are high because they require expensive operations, ensure high communication responsiveness, and build a long-term reputation for reliability. They must also pledge their DOTs (Polkadot's tokens) as a guarantee of good behavior. When they deviate from the agreement, this pledge will be punished. On the contrary, when they act according to the rules, they will be rewarded. Any node that completes the task can openly become a candidate verification node. However, due to operational reasons, only a limited number of validators can be selected in the end, and we expect it to be hundreds or thousands.

• Opinion | Monetization of Bitcoin and Ethereum: Who can be the next world currency?
• Babbitt Column | Cai Weide: Blockchain is used for credit information to build a "Taoyuan World"
• Introduction to Blockchain | Why do miners overclock and downclock?

The system also encourages any DOT holder to participate as a nominee . The nominee published a list of candidates he trusted and pledged a certain number of DOTs to support them. If some of these candidates are selected as validators, he will get a corresponding return of interest based on the proportion of the pledged amount. Unlike validators, there is no limit to the number of nominees. As long as the nominee chooses and only supports candidate validators with good security practices, his risk is low and there is a continuous source of income. There are other special roles in the Polkadot network, but we only focus on the relationship between these two roles.

NPoS mechanism

This nominee-verifier design has a very strong security guarantee. It allows the system to select verification nodes with a large total pledge (much higher than the DOT holdings of any group of people), and eliminate candidates with a lower total pledge. In fact, at any given moment, we hope that a relatively large portion of DOT will be pledged in NPoS. This makes it difficult for some hostile groups to become verification nodes (because they need to build a strong reputation to get the support they need), and the cost of attacking the system is also high (because any attack will cause a large number of DOTs to be cut).

Our NPoS scheme is much more efficient than the proof-of-work mechanism (PoW) and much faster than the proof-of-stake mechanism (PoS): it allows almost all participants with DOT to continue to participate, thereby maintaining a high level of security , While limiting the number of verification nodes, so all basic network operations are efficient.

Election process

With the vote of the nominee, how to choose a validator? Unlike other PoS-based projects that measure the proportion of votes based on the number of validators' pledges, Polkadot gives the elected validators equal voting rights in the consensus protocol. To reflect this fact, the nominee ’s shares should be distributed as evenly as possible to the selected verifier, while still respecting the nominee ’s preferences. In the research team of the Web3 Foundation, we have used tools from election theory to game theory to discrete optimization to develop an efficient election process with fair representation and security, and can be applied in the future using NPoS Any blockchain. Below we will combine some examples to explore these views.

Fair representation. At the end of the 19th century, Swedish mathematician Lars Edvard Phragmén proposed a method of electing members of the Swedish Parliament. He noted that the election method at the time tended to give all seats to the most popular parties; instead, his new method ensured that the number of seats allocated to each party was proportional to the votes given to them, so it gave minority More representation. The attributes obtained through his method are formally called proportional justified representations, and are very suitable for NPoS elections because it ensures that any node pool is neither over-represented by the validators selected nor selected. The outgoing validators are too low representatives, but proportional to their pledges. Our inspiration is based on Phragmén's ideas and ensures that every election has this nature.

This example represents a typical election process. The nominees on the left have a different number of stakes and are connected to the candidate validators on the right that they trust (for simplicity, the validators do not have themselves in this example Stake, although in real scene they will take). Suppose we need to select n = 4 validators. The attribute of fair representativeness can be roughly transformed into a rule that any nominee who holds at least 1 / n of the total shares guarantees that at least one validator they trust is elected. Since the total stake is 40 DOTs, a quarter of which are 10 DOTs, the first two nominees are guaranteed to be represented by one validator. In the picture below, we see three possible election results: one violates fair representation and two achieve fair representation.

safety. If the nominee is selected by two or more validators that he trusts, we need to allocate the nominee ’s shares among them so that the support of the validator is as balanced as possible. Recall that we want to make it as difficult as possible for the opponent pool to obtain a validator, and they can only do this if they have sufficient support. Therefore, we equate the security level of the election results with the minimum number of validators selected. For the last two fair and representative election results, we provide stake allocation, and the results show that they have reached the security levels of 6 and 9, respectively.

The election results on the right have reached a higher level of security, and obviously have done a better job of averaging the nominees ’shares among the validators. Therefore, the goal of the NPoS election process is to provide a result that achieves fair representation and the highest possible level of security. This creates a rather challenging optimization problem (ie NP-complete), for which we have developed a fast approximation heuristic algorithm with strong guarantees in safety and scalability.

We are excited about the technical developments proposed by Polkadot and the possibilities brought about by NPoS and other efficient solutions developed in the blockchain field. You can learn more on the Web3 Foundation research page and Polkadot wiki. To learn about Polkadot's development, follow Polkadot on Twitter and join the newsletter.

Web3 Foundation Research : http://research.web3.foundation/

Polkadot wiki : http://wiki.polkadot.network/

Polkadot Twitter : https://twitter.com/polkadotnetwork

Newsletter : http://eepurl.com/gbyVCD

Original: https://medium.com/web3foundation/how-nominated-proof-of-stake-will-work-in-polkadot-377d70c6bd43

We will continue to update Blocking; if you have any questions or suggestions, please contact us!