The Path of a Parachain Block

Polkadot guarantees valid state transitions for its member parachains. Beneath the surface, an orchestra of nodes, from validators and collators to fishermen and full nodes, play their parts to deliver parachain blocks to the final Relay Chain.

Parachains are sovereign blockchains connected to the Polkadot network. Like other blockchains, parachains are deterministic state machines, meaning that each parachain has a state, executes a batch of state transitions called a block, and achieves a new state. A state is like a system’s configuration. Think of a light switch. It can be either “on” or “off”. A computer’s state is like several billion light switches. At the most fundamental level, a batch of state transitions contains a list of light switches to toggle. A state transition function is the logic to decide if the switches should be toggled.

Each parachain[1] within Polkadot has its own state. The Relay Chain links all of these into one state — a “state of states” — in a tactic called “sharding”. Each parachain is a shard of Polkadot, with unique state transition rules. Parachains have separate economies, governance mechanisms, and users. Because of the interface that Polkadot provides, the Relay Chain validators can guarantee that each parachain follows its unique rules and can pass messages between shards in a trust-free environment.

This article will cover the series of availability and validity checks that parachain blocks undergo to make their way into the Relay Chain where, once finalized, they benefit from the security of the entire Polkadot network.

I. Match Making

The block creation process starts with parachain collators. Collators are similar to validators on any other blockchain, but they do not need to provide security guarantees because Polkadot provides those. Collators only need to create blocks that extend their finalized chain.

Uniform security guarantees ensure that chains connected to Polkadot can interact in trust-free manner. Parachains can interact without trust bounds much like smart contracts on Ethereum can interact without trust bounds — they share state and validation logic with the greater network.

Because Polkadot provides the security and validity guarantees, parachains are not subject to normal blockchain attack scenarios, like a 51% attack. Polkadot validators will reject invalid blocks, so a parachain only needs a single honest collator to submit blocks. This model opens up a new area of crypto-economics that could include token-less parachains, proof-of-stake parachains that use either a native parachain token or dot tokens, or other collator selection mechanisms. Block author information is normally part of the block header’s digest and is easy to verify.

Each parachain in Polkadot will have a set of Relay Chain validators to accept and validate its parachain blocks and move them toward finality. But these validators don’t stay long like in other sharded systems that assign validators to a single shard indefinitely. As often as every block, Polkadot validators find a new parachain in a cotillion that turns to the beat of Polkadot’s metronome: the BABE randomness beacon.

Validators use the random outputs that BABE generates — the same ones that assign block production slots — to determine which parachain to validate next. Once a validator knows its new parachain, it finds collators from that parachain to establish connections with. Each validator assigned to a parachain will import the correct state transition function to validate that parachain. Now that collators and validators share a connection and common logic, a collator can send a block to one of the validators.

To recapitulate this first phase from the perspective of a single parachain:

• The parachain selects a collator to submit a block to the relay chain,
• Polkadot assigns a set of validators to this parachain, and
• The collators and validators open connections to submit a block.

II. Block Preparation

When a validator receives a block, it will first check that the block follows the state transition rules of the parachain.

A parachain’s state is stored in a Merkle tree. Every data point in the state consists of a key and a value. For example, a key could be an account ID and a value could be the number of tokens it controls. Each of these key-value pairs is represented with a hash and becomes a leaf of the tree. To make the branches, adjacent leaves are concatenated and hashed again, turning two points into one. The process continues, reducing the total number of elements by half each time, until the tree has a single hash value to represent the entire database, the state root.

A small Merkle tree. Each storage item is hashed to find the leaf. Then, each pair of leaves forms the next level until one value remains: the state root.

Merkle trees have a convenient property: If some value changes, one can verify the change by only looking at the new values and the paths in the tree that it affects.

Based on this property, a validator can verify a state transition without having access to the entire state. It only needs:

• The block (list of state transitions),
• The values in the parachain’s database that the block modifies, and
• The hashes of the unaffected points in the Merkle tree.

This set of information constitutes a proof of validity. Hashes have a fixed length. It doesn’t matter how large the unmodified values are; the hash is sufficient to represent them.

In this example, Louise sent 50 tokens to Ben and someone created a new referendum. Polkadot can validate a state transition with the block plus the reduced Merkle tree.

Now is an apt time to make a key distinction: Polkadot does not guarantee a valid state; it guarantees a valid state transition. Polkadot validators do not inspect every value in a parachain’s state, only those that are modified, where it ensures that the modification is valid. If a chain joins the Polkadot network with a valid state and executes all of its transitions under the umbrella of Polkadot security, then it will have a valid state.[2]

Once a validator has the proof of validity, it gossips this information amongst the other validators who are assigned to that parachain. Once more than half of them agree that the block represents a valid state transition, they can start preparing to announce its validity. Validators will construct a “candidate receipt” — this is what actually goes into the Relay Chain block — and an erasure coding that they will send to all validators in the network.

Candidate Receipts

In the parachain validation process, validators and collators have exchanged a lot of information. A proof of validity contains an entire parachain block as well as large sections of its state. For Polkadot to scale to hundreds of parachains, validity proofs need something smaller to represent them on the Relay Chain: candidate receipts.

A validator constructs a candidate receipt for a parachain block by signing:

• The parachain ID
• The collator’s ID and signature
• A hash of the parent block’s candidate receipt
• A Merkle root of the block’s erasure coding
• A Merkle root of any outgoing messages
• A hash of the block
• The state root of the parachain before executing the block
• The state root of the parachain after executing the block

While this looks like a long list of information, it is actually much smaller than a proof of validity because every item is of fixed length. The parachain and collator IDs are just numbers; everything else is a hash (a Merkle root is a hash of a hash of a hash of a …). In computer science, any method to represent an arbitrary amount of information in a constant size provides a scalability advantage. This system can scale by pushing more and more information to the edges while only pushing constant-size information through the Relay Chain.

The hash of the parent block’s receipt ensures that the current receipt builds off the correct chain. Likewise, the state roots of the parachain and the hash of the block allow anyone to verify this state transition by obtaining the proof of validity — the block itself plus the updates in the state tree.

Erasure Coding

Now for the erasure coding. Prior to sending this candidate receipt to the Relay Chain transaction queue, the validator who constructs the candidate receipt must also construct an erasure coding of the parachain block.

An erasure coding takes a message — in this case, the message is the parachain block and proof of validity — and creates a set of smaller messages such that you can reconstruct the original message by obtaining a fraction of the smaller messages. In the case of Polkadot, the number of smaller messages is equal to the total number of validators and the fraction is one-third. As an example, if Polkadot has 1,000 validators and they each get a chunk (the small pieces are called “chunks”) then they could reconstruct a block with any 334 of them.

So, the validator creates all these erasure coding chunks, puts those chunks into their own Merkle tree, and sends out each chunk to a corresponding validator. Along with these chunks, the validator also includes the candidate receipt, which is what actually goes into a block on the Relay Chain.

The validators who receive a candidate receipt along with an erasure coding chunk will include the candidate receipt in the Relay Chain transaction queue, where an author can include it in a block.

Cool Story Bro

Although erasure coding may be a bit dry, why we perform the erasure coding is far more interesting than how it works.

Imagine that a malicious collator submits a valid block to the validators and then immediately goes offline. The attack here is not to create an invalid transaction, it is to completely shut down the parachain, which would — broadly speaking — make everyone’s lives miserable.

If the validators only checked this block for validity and then finalized it in the Relay Chain, the collators would be left with their previous state and their current state root, without knowing what changes to make to create the current state root. Since they would no longer have their state, they could no longer create new blocks.

Therefore, collators must be able to retrieve and reconstruct a block for their parachain before it becomes final.

III. Relay Chain Block Construction

Collators and validators have done a lot of work to get to this point. Each parachain got a small set of validators randomly assigned for a block. These validators had to connect to parachain collators, compute state roots, look up parent blocks, and create and distribute erasure coding chunks to every other validator in the network. They arranged all that work into a candidate receipt that represents it all.

The candidate receipt goes into the Relay Chain transaction queue and validators gossip it around the network just like other transactions. When a validator wins BABE slot leadership, it will select candidate receipts to build a Relay Chain block.

The transaction queue could have hundreds of parachain candidate receipts. How does the block author decide which ones to include in a block?

First, the block author will only include candidate receipts that have a parent candidate receipt in an earlier Relay Chain block. This check ensures that the parachain follows a valid chain.

Second, the block author will only include candidate receipts for which the author has an erasure coding chunk. A parachain validator sends its chunks to all the other validators in the network, so each validator should have chunks from each parachain. By only including candidate receipts for which the author has a chunk, the author ensures that the system can perform the next round of availability and validity checks.

Hermit Relay Chain

I’ve mentioned before that one strategy for scalability is to push information to the edges of the system. One of our ideas with Polkadot is to make Polkadot itself a parachain. As in, all the transactions for token transfers, staking, governance, etc. would take place in a Polkadot parachain with its candidate receipts finalized by the Relay Chain. In this case, the Relay Chain blocks would comprise solely candidate receipts.

IV. Finale

Most sharded blockchain protocols require a large number of validators on each shard. Polkadot’s erasure coding feature, and the extra checks that happen next, is the edge that allows it to provide the same validity guarantees on each shard with as low as ten validators per shard.

The availability check by the block author ensures that Polkadot will only include blocks for which the validators distributed their chunks, but it does not guarantee their validity. Because the number of validators on each parachain is so low, collusion is a reasonable concern. By separating block production (BABE) from finality (GRANDPA), Polkadot can perform extra validity checks after a block is produced but before it is finalized.[3] Polkadot has special actors, fishermen, who patrol Relay Chain blocks for invalid candidate receipts.

A fisherman is essentially a parachain full node with some dot tokens at stake. While parachain collators don’t need any stake of dot tokens [4] — they only need incentives from their own parachain to create blocks — fishermen do need to stake dot tokens as an anti-spam mechanism. Without any value at stake, fishermen could submit fabricated invalidity claims.

Once a block is added to the Relay Chain, it begins a verification phase where randomly selected validators must perform secondary checks to test the availability and validity of the candidate receipts inside. A secondary check involves requesting enough erasure coding chunks to reconstruct the encoded block and proof of validity to validate the state transition.

When a validator creates a new block, it sends the block to its connections in the network, who forward the new block on to their connections. When a validator imports a block, it will check to see if it has an erasure coding chunk for each candidate receipt in the block. If any chunks are missing, then the validator will alert the others. If more than one-third of the validators send missing-chunk alerts within a set time period, then the block is discarded.

Once the block makes it through the grace period, the secondary checks begin. The number of secondary checks that Polkadot requires depends on collators and fishermen, who test the availability and validity of candidate receipts, respectively. If a fisherman detects a block that it considers invalid, then it submits an invalidity statement along with a stake of dot tokens. Likewise, collators submit unavailability statements. Blocks with more invalidity or unavailability statements require more secondary checks by validators, all the way up to requiring more than one-third of validators to attest to a block’s validity or invalidity. Like the unavailability grace period, if more than one-third of the validators report a block as invalid, the block is discarded.[5]

The role of collators and fishermen performing additional availability and validity checks further pushes scalability to the edges and away from the Relay Chain validators. As the number of parachains increases, so too does the number of collators and fishermen associated with them who can perform these checks, without any further burden on the validators. The additional checks keep the workload of validators low, primarily using them to resolve any dissonance.

After enough secondary checks have been performed on all the candidate receipts within a block, validators can finally vote for that block (and by extension, all previous blocks) in GRANDPA. Once it has more than two-thirds of pre-commits, the block is in the finalized chain.

Validators cannot vote on blocks until validators have performed enough secondary checks. This feature gives the Relay Chain three zones: the finalized chain, the GRANDPA voting zone with valid candidates for finalization, and the fishing zone where blocks need availability and validity checks.

All parachains in Polkadot follow the finality of the Relay Chain. Future parachain blocks must always build off the candidate receipts that are in the finalized Relay Chain. All of the availability and validity checks should take place in less than one minute from the time a block is authored to the time it is finalized.

Once final, the block benefits from the shared security environment that allows chains to interact with each other in a trustless manner, where reverting the block would require reverting all of Polkadot. Reverting the entire network is an arduous task, and one to avoid, which is why validators, collators, and fishermen must ensure valid state transitions with Mozartesque precision. The framework of erasure coding and our BABE/GRANDPA consensus allows Polkadot to provide these guarantees in a faster and more scalable fashion than any other blockchain network.

Coda

This article only discussed the validation of parachain blocks, but alluded to an environment for trust-free messaging between parachains. Because the same validators secure all parachains, cross-chain messages have the same integrity as cross-account messages within a single chain, for example inter-contract communication on Ethereum.

In Polkadot’s cross-chain message passing protocol (XCMP), parachains establish direct channels between each other. Parachains that share full nodes can gossip messages directly, while parachains that do not share full nodes request their messages from validators. Only channel operations, e.g. opening and closing, and proofs of delivery go into the Relay Chain. XCMP is just one more way that Polkadot scales by pushing information to the edges while still providing the necessary guarantees for trust-free interaction.

For more information on cross-chain communication, see Polkadot’s Messaging Scheme.

To learn more about BABE and GRANDPA, see the Polkadot Consensus Series.

Notes

1. This article will always use “parachains”, but everything here also applies to parathreads unless specifically noted.
2. Of course, the users must decide what “valid” means w/r/t state.
3. This separation doubles as a spam-prevention mechanism; validators only check candidate receipts that are in a block, not every receipt that a parachain submits.
4. While true for parachain collators, parathread collators will need to hold DOT tokens to participate in block auctions to schedule their block execution. But since parachain collators are in a good position to act as fishermen, they can easily take on both roles.
5. This may seem odd, that crossing the one-third threshold is sufficient both to accept or reject a block, when both subsets could exist in a set without intersection. Byzantine fault tolerant systems, however, require that less than one-third of the validators be faulty. If more than one-third say a block is valid, and more than one-third also say a block is invalid, then the assumptions of the system have broken.