Polkadot Research Update

Several articles have recently been added to the Web3 Foundation research portal covering individual subprotocols of the Polkadot decentralized blockchain platform: nominated proof of stake (NPoS), time consensus and GRANDPA (the finality gadget implemented for the relay chain). Here, we give a brief introduction to each, along with links to the papers.

Validator election in nominated proof of stake

Polkadot implements nominated proof of stake (NPoS), an adaptation of proof of stake (PoS) in which an unlimited number of token holders can participate as nominators, backing a large but limited set of validators (expected to be in the order of hundreds at genesis). This scheme allows for a massive amount of stake to back validators, much higher than any single user’s holding, thus rendering the network more secure.

Nominators, who share the economic rewards as well as possible slashings with the validators they back, are economically vested in the security of the system and are thus economically incentivized to watch over the validators’ performance.

As such, NPoS is not only much more efficient than proof of work, but also considerably more secure and decentralized than PoS schemes without stake delegation, where only a few whales (owners of a large amount of tokens) can ever become validators.

Based on the nominators’ preferences, the system selects a new set of validators every era (roughly equivalent to one day), according to an election rule that selects the set whose stake backings are as high and as evenly distributed as possible.

This paradigm simultaneously achieves high levels of security and scalability, as well as an unprecedented level of decentralization, by giving a formal mathematical guarantee that the committee of validators achieves proportional representation.

Informally speaking, this means that every minority in the nominator set gets to elect a number of validators in proportion to their stake, with no minority being under-represented.

We highlight that diverse preferences and factions will naturally arise among the network users, be it for security, political, geographical or economic-related reasons. Such diversity of points of view is expected and welcome in a decentralized community, and we aim to ensure that all minorities are represented and engaged in decision-making processes.

Abstract: Polkadot is a decentralized blockchain platform to be launched in 2020. It will implement nominated proof-of-stake (NPoS), a proof-of-stake based mechanism where k nodes are selected by the network as validators to participate in the consensus protocol, according to the preferences expressed by token holders who take the role of nominators. This setup leads to an approval-based multi-winner election problem, where each nominator submits a list of trusted candidates, and has a vote strength proportional to their stake. A solution consists of a committee of k validators, together with a fractional distribution of each nominator's vote among them. We consider two objectives, both recently studied in the literature of social choice. The first one is ensuring the property of proportional justified representation (PJR). The second objective, called maximin support, is to maximize the minimum amount of vote support assigned to any elected validator. We argue that the former objective aligns with the notion of decentralization, while the latter aligns with the security level of the consensus protocol.

We prove that the maximin support problem is constant-factor approximable, as we present several approximation algorithms for it, and prove a matching hardness result. Furthermore, we present an efficient post-computation which, when paired with an approximation algorithm for maximin support, returns a new solution that a) preserves the approximation guarantee, b) satisfies the PJR property, and c) can be efficiently verified to satisfy PJR by an untrusting third party. Besides being of independent theoretical interest, our results enable the network to run an efficient validator election protocol that simultaneously achieves the PJR property and a constant-factor approximation for maximin support, thus offering strong theoretical guarantees on decentralization and security.

To read more about NPoS and the validator election rule that we use, read the full paper or the Medium post How Nominated Proof-of-Stake will work in Polkadot.

Network Time with a Consensus on Clock

In everyday life we don’t often think about the mechanisms for measuring time. Nowadays, it is usually measured by the number of vibrations happening on crystal oscillators in a clock. As the frequency of these vibrations changes due to factors such as temperature, pressure, and humidity, variations of up to a few seconds drift in one day can occur.

Rather than relying on crystal oscillators, computer clocks that are connected to the internet often use extra mechanisms such as the Network Time Protocol (NTP) or the Global Positioning System (GPS) for precision. However, in the past, incidents have occurred where NTP servers were corrupted or GPS signals fooled. If this kind of attack happens in a proof-of-stake blockchain, honest full nodes stop producing blocks because they don’t know it’s time for their round while malicious full nodes continue to produce blocks and dominate the blockchain.

To prevent this possibility, Polkadot uses the relative time protocol, a generic synchronization protocol that works on top of a blockchain protocol. This is particularly important in the relay chain, where each validator has its own clock (which is not corrected by any protocol such as NTP or GPS). The validators interpret the arrival time of finalized blocks with relative time protocol to decide the current right clock to be aligned in a decentralized network. Thus, synchronization of time across the validators can be defined more precisely.

Abstract: Decentralized protocols which require synchronous communication usually achieve it with the help of the time that computer clocks show. These clocks are mostly adjusted by centralized systems such as Network Time Protocol (NTP) because these adjustments are indispensable to reduce the effects of random drifts on clocks. On the other hand, an attack on these systems (which has happened in the past) can cause corruption of the protocols which rely on the time data that they provide to preserve synchronicity. So, we are facing the dilemma of relying on a centralized solution to adjust our timers or risking the security of our decentralized protocols. In this paper, we propose a Global Universal Composable (GUC) model for the physical clock synchronization problem in the decentralized systems by modelling the notion of consensus on clocks. Consensus on clocks is agreed upon considering the local clocks of all parties in a protocol which are possibly drifted. In this way, we model the functionality that e.g. NTP provides in a decentralized manner. In the end, we give a simple but useful protocol relying on a blockchain network that realizes our model. Our protocol can be used by the full nodes of a blockchain that need synchronous clocks in the real world to preserve the correctness and the security of the blockchain protocol. One advantage of our protocol is that it does not cause any extra communication overhead on the underlying blockchain protocol.

To read more, see the full paper here.

Byzantine Finality Gadgets

Polkadot has a hybrid consensus protocol that splits the finality gadget (GRANDPA) from the block production mechanism (BABE).

This is a way of achieving probabilistic finality (after a certain time the block will be finalized with a probability close to one) and provable, deterministic finality (implying a finalized block stays final forever.)

Combining the mechanisms avoids the chance of unknowingly following the wrong fork (a hazard of probabilistic finality) and allows the rapid production of blocks, as the slower finality mechanism finalizes blocks separately without risking slower transaction processing or stalling.

This paper presents the GRANDPA (GHOST-based Recursive ANcestor Deriving Prefix Agreement) protocol.

GRANDPA reaches agreements on chains rather than blocks: It attempts to finalize the prefix of the chain that 2/3 of voters agree on, whether that is one or thousands of blocks. The full paper is available here. GRANDPA is also presented in the Medium post Polkadot Consensus Part 2: GRANDPA

Stay up to date

To keep up with the continuing changes in the Polkadot universe, keep an eye on our blogs and research pages.

We have provided lots of ways for members of the wider Polkadot community to keep up to date with what’s going on. Join us on your favorite medium as we head into exciting times.

Join the discussion on Telegram and Riot, or subscribe to Polkadot’s newsletter. Learn more about Polkadot in the Polkadot Lightpaper and the Polkadot Wiki. Looking to validate on Polkadot? Join Polkadot’s validator lounge on Riot.