W3F Research Workshop Outcomes

This blog post is the first in an ongoing series of blogs W3F Research will write on their ongoing efforts to crack the most difficult research problems standing between us and Web 3.0. W3F Research delves into a wide variety of outstanding research questions including scalability solutions, interchain message passing, and decentralised messaging. Read more W3F Research here.

The following notes were taken at a two-day W3F Research workshop focusing on the Polkadot protocol last month in Berlin. Attendees included: Jeff Burdges, Peter Czaban, Robert Habermeier, Arkadiy Paronyan, Fatemeh Shirazi, Alistair Stewart, and Gavin Wood.

The researchers managed to nail down a majority of the outstanding protocol components required for the initial version of Polkadot as well as the order in which these components would be implemented.

The workshop focused on the Polkadot protocol, including:

• Interchain message passing
• Block production mechanism
• Nominated proof of stake
• Randomness beacon

Workshop Terminology

• PoV: Proof of Validity (a block candidate plus all witness data in order to let a stateless (light) client execute it)
• AG: Availability Guarantor (validators holding an erasure coded piece)
• GRANDPA: Block finality gadget in Polkadot

Workshop Notes

The workshop began addressing initial questions about buffering (whether it should be done and how) and defining the order of events that lead to a block being created in Polkadot. The researchers settled on having a limit on the size and number of messages that can be sent by each parachain and enabling the blocking function whereby a parachain can block another parachain from sending messages it messages.

PoV Block is execution proof witness data. This might include:

• Output messages (as message bundle hash preimages); and
• External data (“transactions”, “extrinsics” or any other data extrinsic to Polkadot)
• Witness (cryptographic proof statements of data validity)
• New header (probably only the case for verification-only STFs like zkSTARKs or whatever)

Parachain Block Creation and Messaging Process

1. Collator has transaction pool
2. Collator runs relay chain light client to determine the latest relay chain head
3. Collator tracks parachain head and that parachain’s input queue as a set of hashes of message-bundles (which requires tracking all parachain’s output queues since the last time the parachain accepted input)
4. Collator retrieves the outgoing messages from other parachains or collator queries AGs (based on relay chain data) in order to get actual message data from bundles
5. Collator creates block candidate from transaction pool, previous head, messages and any other data (e.g. inherents)
6. Collator builds a PoV block candidate for this parachain
7. Collator distributes it to all PVs (for its parachain)
8. Parachain Validatorproduces attestations on some subset of valid PoV candidates that it receives and redistributes to other PVs of their parachain and BAs
9. Block Author selects a set of PoV candidates, at most one for each parachain, which are fully attested by their group
10. Block Author distributes the relay chain block candidate to other validators

Another set of topics discussed included the assumptions we’re making in designing Polkadot and how Nominated Proof of Stake (NPoS) would work.

Assumptions:

• Block Producer (BP) set could be huge; doesn’t matter too much if offline, could be low-staked.
• GRANDPA Validators (Grandpas) <= 1000
• Parachain Validators (PV) are a subset of Grandpas
• Availability Guarantors (AG) same set as Grandpas

Nominated Proof of Stake

1. Validators declare their desired stake they want to deposit and desired interest rate (fee)
2. Nominators declare their desired stake (the total amount of stake they want to invest), preferred validators, and desired interest rate (fee)
3. A solution is an assignment of nominators to validators and the amount of stake each nominator needs to invest in those selected validators
4. There exists an algorithm to measure how good a solution is
5. N blocks prior to a session start, the problem is fixed from the current nominator/validator declarations
6. Solutions may submitted by block producers as an inherent
7. Solutions must be better by a substantial margin (e.g. 5% on the least slashable validator) than previous
8. Finally included solution gets paid some reward; reward inversely proportional to solution size.

Changes to current staking

• Reward should directly reflect risk (i.e. slash ratio)
• Historical session delegations (or the changes thereof) should be recorded in state for later slashing (to avoid big proofs). Will need to be recorded per session under the new NPoS scheme, but should generally fit into around 1MB on-chain per session; 90 sessions worth would need to be recorded (for one era).
• BP set should be divorced from GRANDPA/AG set

The workshop also delved into the Polkadot randomness beacon and the scheme for ensuring availability of parachain data.

Follow the W3F Research forum to read more.