POLKADOT: VISION FOR A HETEROGENEOUS MULTI-CHAIN FRAMEWORK DRAFT 1 15 block had a particular egress queue for a particular desti- Routing itself is deterministic and simple. We begin by nation parachain. limiting the number of bins in the ingress/egress queues; At the beginning of processing a parachain block, each rather than being the total number of parachains, they other parachain’s egress queue bound for said block is are the routing-base (b) . This will be fixed as the number merged into our block’s ingress queue. We assume strong, of parachains changes, with the routing-exponent (e) in- 9 probably CSPR , sub-block ordering to achieve a deter- stead being raised. Under this model, our message volume e ministic operation that offers no favouritism between any grows with O(b ), with the pathways remaining constant parachainblockpairing. Collatorscalculatethenewqueue andthelatency(ornumberofblocksrequiredfordelivery) and drain the egress queues according to the parachain’s with O(e). logic. Our model of routing is a hypercube of e dimensions, The contents of the ingress queue is written explicitly with each side of the cube having b possible locations. into the parachain block. This has two main purposes: Each block, we route messages along a single axis. We firstly, it means that the parachain can be trustlessly syn- alternate the axis in a round-robin fashion, thus guaran- chronised in isolation from the other parachains. Secondly, teeing worst-case delivery time of e blocks. it simplifies the data logistics should the entire ingress As part of the parachain processing, foreign-bound queue not be able to be processed in a single block; val- messages found in the ingress queue are routed imme- idators and collators are able to process following blocks diately to the appropriate egress queue’s bin, given the without having to source the queue’s data specially. current block number (and thus routing dimension). This If the parachain’s ingress queue is above a threshold process necessitates additional data transfer for each hop amount at the end of block processing, then it is marked on the delivery route, however this is a problem itself saturated on the relay-chain and no further messages may which may be mitigated by using some alternative means be delivered to it until it is cleared. Merkle proofs are of data payload delivery and including only a reference, used to demonstrate fidelity of the collator’s operation in rather than the full payload of the post in the post-trie. the parachain block’s proof. An example of such a hyper-cube routing for a system with 4 parachains, b = 2 and e = 2 might be: Phase 0, on each message M: 6.6.3. Critique. One minor flaw relating to this basic • sub : if M ∈{2,3} then sendTo(2) else keep 0 dest mechanism is the post-bomb attack. This is where all • sub : if M ∈{2,3} then sendTo(3) else keep 1 dest parachains send the maximum amount of posts possible • sub : if M ∈{0,1} then sendTo(0) else keep 2 dest to a particular parachain. While this ties up the target’s • sub : if M ∈{0,1} then sendTo(1) else keep 3 dest ingress queue at once, no damage is done over and above Phase 1, on each message M: a standard transaction DoS attack. • sub : if M ∈{1,3} then sendTo(1) else keep Operatingnormally, withasetofwell-synchronisedand 0 dest • sub : if M ∈{0,2} then sendTo(0) else keep non-malicious collators and validators, for N parachains, 1 dest • sub : if M ∈{1,3} then sendTo(3) else keep N×Mtotalvalidators and L collators per parachain, we 2 dest • sub : if M ∈{0,2} then sendTo(2) else keep can break down the total data pathways per block to: 3 dest Validator: M−1+L+L: M−1fortheothervalidators The two dimensions here are easy to see as the first in the parachain set, L for each collator providing a can- two bits of the destination index; for the first block, the didate parachain block and a second L for each collator higher-order bit alone is used. The second block deals of the next block requiring the egress payloads of the pre- with the low-order bit. Once both happen (in arbitrary vious block. (The latter is actually more like worst-case order) then the post will be routed. operation since it is likely that collators will share such Maximising Serendipity. One alteration of the basic pro- 2 data.) posal would see a fixed total of c −c validators, with c−1 Collator: M+kN: M for a connection to each relevant validators in each sub-group. Each block, rather than parachain block validator, kN for seeding the egress pay- there being an unstructured repartitioning of validators loads to some subset of each parachain validator group for among parachains, instead for each parachain sub-group, the next block (and possibly some favoured collator(s)). each validator would be assigned to a unique and different As such, the data path ways per node grow linearly parachain sub-group on the following block. This would with the overall complexity of the system. While this is lead to the invariant that between any two blocks, for any reasonable, as the system scales into hundreds or thou- two pairings of parachain, there exists two validators who sands of parachains, some communication latency may be have swapped parachain responsibilities. While this can- absorbed in exchange for a lower complexity growth rate. not be used to gain absolute guarantees on availability In this case, a multi-phase routing algorithm may be used (a single validator will occasionally drop offline, even if in order to reduce the number of instantaneous pathways benevolent), it can nonetheless optimise the general case. at a cost of introducing storage buffers and latency. This approach is not without complications. The addi- Hyper-cube Routing. Hyper-cube routing is a mechanism tion of a parachain would also necessitate a reorganisation which can mostly be build as an extension to the basic of the validator set. Furthermore the number of valida- routing mechanism described above. Essentially, rather tors, being tied to the square of the number of parachains, than growing the node connectivity with the number of would start initially very small and eventually grow far parachains and sub-group nodes, we grow only with the too fast, becoming untenable after around 50 parachains. logarithm of parachains. Posts may transit between sev- Noneof these are fundamental problems. In the first case, eral parachains’ queues on their way to final delivery. reorganisation of validator sets is something that must be 9 cryptographically secure pseudo-random