POLKADOT: VISION FOR A HETEROGENEOUS MULTI-CHAIN FRAMEWORK DRAFT 1 14 parachaintohaveexplicitlysanctionedthispost. Theonly ensure that each next-block destination subgroup’s mem- constraints we place upon our model is that parachains bers are informed of the egress from the present block. must provide, packaged as a part of their overall block Validators are incentivised only to form a consensus on a processing output, the posts which are the result of the (parachain) block, as such they care little about which col- block’s execution. lator’s block ultimately becomes canonical. In principle, a These posts are structured as several FIFO queues; the validator could form an allegiance with a collator and con- number of lists is known as the routing base and may be spire to reduce the chances of other collators’ blocks be- around 16. Notably, this number represents the quantity coming canonical, however this is both difficult to arrange of parachains we can support without having to resort to due to the random selection of validators for parachains multi-phase routing. Initially, Polkadot will support this and could be defended against with a reduction in fees kind of direct routing, however we will outline one possible payable for parachain blocks which hold up the consensus multi-phase routing process (“hyper-routing”) as a means process. of scaling out well past the initial set of parachains. We assume that all participants know the sub- 6.6.1. External Data Availability. Ensuring a parachain’s groupings for next two blocks n, n + 1. In summary, the external data is actually available is a perennial issue with routing system follows these stages: decentralised systems aiming to distribute workload across the network. At the heart of the issue is the availability • CollatorS: Contact members of Validators[n][S] problem which states that since it is neither possible to • CollatorS: FOR EACH subgroup s: ensure at make a non-interactive proof of availability nor any sort least 1 member of Validators[n][s] in contact of proof of non-availability, for a BFT system to properly • CollatorS: FOR EACH subgroup s: assume validate any transition whose correctness relies upon the egress[n−1][s][S] is available (all incoming post availability of some external data, the maximum number data to ‘S‘ from last block) of acceptably Byzantine nodes, plus one, of the system • CollatorS: Compose block candidate b for S: must attest to the data being available. (b.header,b.ext,b.proof,b.receipt,b.egress) For a system to scale out properly, like Polkadot, this • CollatorS: Send proof information invites a problem: if a constant proportion of validators proof[S] = (b.header,b.ext,b.proof,b.receipt) to must attest to the availability of the data, and assuming Validators[n][S] that validators will want to actually store the data be- • CollatorS: Ensure external transaction data b.ext fore asserting it is available, then how do we avoid the is made available to other collators and validators problem of the bandwidth/storage requirements increas- • CollatorS: FOR EACH subgroup s: ing with the system size (and therefore number of valida- Send egress information egress[n][S][s] = tors)? Onepossible answer would be to have a separate set (b.header,b.receipt,b.egress[s]) to the re- of validators (availability guarantors), whose order grows ceiving sub-group’s members of next block sublinearly with the size of Polkadot as a whole. This is Validators[n+1][s] described in 6.5.3. • ValidatorV: Pre-connect all same-set members We also have a secondary trick. As a group, colla- for next block: let N = Chain[n+1][V]; connect tors have an intrinsic incentive to ensure that all data is all validators v such that Chain[n +1][v] = N available for their chosen parachain since without it they • ValidatorV: Collate all data ingress for this are unable to author further blocks from which they can block: FOR EACH subgroup s: Retrieve collect transaction fees. Collators also form a group, mem- egress[n−1][s][Chain[n][V]], get from other val- bership of which is varied (due to the random nature of idators v such that Chain[n][v] = Chain[n][V]. parachain validator groups) non-trivial to enter and easy Possibly going via randomly selected other val- to prove. Recent collators (perhaps of the last few thou- idators for proof of attempt. sand blocks) are therefore allowed to issue challenges to • ValidatorV: Accept candidate proofs for this the availability of external data for a particular parachain block proof[Chain[n][V]]. Vote block validity block to validators for a small bond. • ValidatorV: Accept candidate egress data for Validators must contact those from the apparently of- next block: FOR EACH subgroup s, accept fending sub-group who testified and either acquire and re- egress[n][s][N]. Vote block egress availability; re- turn the data to the collator or escalate the matter by tes- publish among interested validators v such that tifying to the lack of availability (direct refusal to provide Chain[n+1][v] = Chain[n+1][V]. the data counts as a bond-confiscating offence, therefore • ValidatorV: UNTIL CONSENSUS the misbehaving validator will likely just drop the connec- tion) and contacting additional validators to run the same Where: egress[n][from][to] is the current egress queue test. In the latter case, the collator’s bond is returned. information for posts going from parachain ‘from‘, to Once a quorum of validators who can make such non- parachain ‘to‘ in block number ‘n‘. Collator is a col- S availability testimonials is reached, they are released, the lator for parachain S. Validators[n][s] is the set of val- misbehaving sub-group is punished, and the block re- idators for parachain s at block number n. Conversely, verted. Chain[n][v] is the parachain to which validator v is as- signed on block number n. block.egress[to] is the egress 6.6.2. Posts Routing. Each parachain header includes an queue of posts from some parachain block block whose egress-trie-root; this is the root of a trie containing the destination parachain is to. routing-base bins, each bin being a concatenated list Since collators collect (transaction) fees based upon of egress posts. Merkle proofs may be provided across their blocks becoming canonical they are incentivised to parachain validators to prove that a particular parachain’s