Tracking

• Backwards compatible runtime changes: accept older relay-parents (Runtime changes for Asynchronous Backing #4786)
  • Deploy to Kusama
  • Deploy to Polkadot
• Implementation of 'Context' logic on the node-side (inclusion emulator logic for asynchronous backing #4790)
• Implementation of a 'Prospective Parachains' subsystem that tracks backed blocks (Prospective Parachains Subsystem #4913 )
  • Deploy to Kusama parameterized without 'look-forward'
  • Deploy to Polkadot parameterized without 'look-forward'
• Update backing & collation subsystems to take impulses from prospective parachains instead of active-leaves directly
  • collation-generation (Update collation generation for asynchronous backing #7405)
  • collator-protocol (collator-protocol: asynchronous backing changes #5740)
  • candidate-backing (Integrate prospective parachains subsystem into backing: Part 1 #5557)
  • statement-distribution (Asynchronous backing statement distribution: Take III #5999)
  • provisioner: choose backed candidates from Prospective Parachains instead of Backing. Find ones that the new block will accept (provisioner: async backing changes #5711)
• Final deployment
  • Test on Versi, Rococo with 'look-forward' parameter
  • Collect & publish throughput improvements, fiddle with parameters
  • Deploy with farther look-forward to Kusama
  • Deploy with farther look-forward to Polkadot

Board: https://github.com/orgs/paritytech/projects/37

This is a long-standing idea which has been pending a writeup for some time.

I previously referred to this as "Contextual Execution", but I'd prefer to rename it to "Asynchronous Backing", which is the goal, rather than "contextual execution" which doesn't describe the purpose very well and is fact an implementation detail.

Terminology

• The relay parent is the relay-chain block that a parachain block anchors to.
• A parachain block is backed when it is first appears in the relay chain but is not necessarily available.
• A parachain block is included when it has appeared in the relay chain and has been signified as available by a majority of validators. Note that this happens at the earliest one relay-chain block after backing.
• The base parent of a parachain block is the parachain block of the same parachain which is included as-of the relay-parent. This could be described as a function base_parent(relay_parent) -> Parachain Block Hash
• The context of a parachain block P is a set of constraints on execution for a parachain block derived from the relay-parent R of P and all the parachain blocks in-between P and base_parent(R). This could be described as a function context(R, [intermediate_blocks]) -> Constraints.

Motivation

Currently, the relay-chain runtime accepts only parachain blocks anchored to the most recent relay-chain block as a relay_parent. This means that the runtime only accepts parachain blocks which have context(most_recent_rp, []). This implicitly creates a requirement for a parachain block to be authored, submitted to relay-chain validators, executed, and backed all within a 6-second window. Practically, this leaves only around 0.5 seconds for the collator to author a block, which is not enough time to include a meaningful amount of transactions. Backing, at the moment, is heavily synchronized with the progress of the relay chain, and we'd like to make it more asynchronous, and therefore, less dependent.

We'd like to expand the set of permitted relay_parents accepted by the relay-chain to include the most recent K blocks of the relay chain so collators can begin building their blocks earlier with the intent to include them into the relay chain later on. Even doubling the 6-second window to a 12-second window might quadruple the time given to execution and therefore quadruple throughput on parachains.

Some diagrams to show the difference follow. "R*" denotes a relay chain block, "P*(b)" denotes a parachain block that is backed in a particular relay-chain block. "P*(i)" denotes a parachain block that is included in a particular relay-chain block. We only need to consider 1 parachain for the purposes of these diagrams, because the same algorithm can be run in parallel for all parachains at once.

Without contextual execution:
R<--- R1<-------- R2<----- R3
 \--- P1(b)<----- P1(i)
       \--------- P2(b)<-- P2(i)

With contextual execution
R<--- R1<-------- R2<-------- R3<-------- R4<------- R5
 \--x--|--------- P1(b)<----- P1(i)
        \--x------|---------- P2(b)<----- P2(i)
                   \---x----------------- P3(b)<---- P3(i)

In the 'without contextual execution' example, we have only a 1-block window to begin building a parachain block to getting it backed in a relay-chain block. Also note that this example assumes that we begin working on a backed parent before it is included, something which we currently don't do. Still, we only have 6 seconds (1 relay-chain blocktime) to author, distribute, and back the parachain block.

In the contextual execution example, we start building parachain blocks earlier. P1 is in context(R, []). P2 is in context(R1, [P1]). P3 is in context(R2, [P2]). The 'x's mark the points where the respective parachain block is actually built & signed, which is the earliest point that the parachain block can be built upon. Typically, we expect that the next relay-chain block and the parablock being accepted by the first validators will happen at around the same time. In the contextual execution example, we always have around 12 seconds to author, distribute, and back the parachain block. Doubling this period actually more than doubles the amount of execution and data that can be done in a single parachain block, because there are constant overheads associated with the parachain backing process.

Contexts

The context of a parachain candidate dictates the constraints on the inputs and outputs of the candidate. The context dictates:

• The parent-head of the parachain candidate. That is, the parachain block that this block builds on top of.
• The Downward Message Passing (DMP) messages available to the parachain candidate. DMP messages are sent from the relay chain to the parachain directly.
• The Upward Message Passing (UMP) queue space available to the parachain candidate. UMP messages are sent from the parachain to the relay chain directly.
• The Parachain Validation Function (PVF) used to validate the candidate.
• The incoming Cross-chain Message Passing (XCMP) messages available to the parachain candidate on each of its incoming channels. XCMP messages are sent from parachains to parachains, with parachains establishing unidirectional channels.
• The outgoing XCMP queue space available to the parachain candidate on each of its outgoing channels.
• The status of any previously announced code upgrades - code upgrades can be pending, ready to activate, or aborted.
• The limitations on announcing a new code upgrade.

Note that a context is created from a relay chain state and a series of amendments The context of a relay-chain block is the context, drawn from the post-state of that relay-chain block. Each amendment updates the context by altering message queues, updating the parent head, and so on.

Contexts are independent from availability. They only dictate constraints on the inputs and outputs of a PVF execution, not whether it is prudent to vouch for a particular parachain execution or even whether that PVF execution is valid.

Expressed in pseudocode

context(relay_state, amendments) = /* draw values from relay_state and apply amendments in turn */
base_context(relay_parent) = context(relay_parent_state, [])

Another way to think about contexts is as a stack. We have a base context, plus a stack of prospective changes to that context. From the perspective of the runtime, in a state S we only need to accept candidates that are valid under the context drawn from state S. So the runtime only deals with 'flat' contexts. The job of the node-side code is to anticipate the future state of the relay chain so it can build stacks of prospective contexts that it believes may equal the relay chain's own state at some point in the near future.

We say that a context underestimates another, that is A < B when every parablock b valid under A would also be valid under B. Stated differently, we denote the 'validity set' of a context C as the set of parablocks valid under a context. A < B iff validity_set(A) is a subset of validity_set(B)

Underestimates are useful because they let us maximize the number of possible future relay-chain blocks a candidate can be included in.

Considerations

1. Prospective Backing

Asynchronous backing means that we seek to de-couple the extension of parachains from the extension of the relay-chain. This can mean a lot of different things, but one property that is beneficial to the network that we'd like to pursue is "whenever a relay-chain block is authored, there should be a parachain block ready to be backed on-chain". This means that relay-chain validators need to build prospective parachains, likely in-memory.

While this is aimed at efficiency gains, it can also be the source of wasted effort. If there is a parachain A<-B<-C<-D where only A is referenced by the relay-chain, if it turns out that B is unavailable then the work backing C and D was wasted. Likewise if an alternate block B' ends up actually being on-chain, as C and D are no longer possible to be accepted.

When a backing group is majority-malicious, there is little we can do to prevent wasted effort. As is already done, we can avoid accepting more candidates than would reasonably be produced by such a backing group. The best way for a parachain to avoid validators accidentally wasting effort (and thereby spending less time on legitimate validation) is for the parachain to avoid forks with a plausibly-unique authoring mechanism like BABE, Aura, SASSAFRAS, or PoW.

2. Message Queues

Parachains have both incoming and outgoing message queues. Our solution should allow prospective parachains to both add and remove upwards, downwards, and horizontal messages without surpassing queue size or weight limits.

Upwards, downwards, and horizontal messages are intentionally designed to be hash-chain ranging from a head to a tail. The head is the last unprocessed message and the tail is the first unprocessed message. We'd denote such a list as [head, tail].

Each parachain is the only producer of messages for its outgoing message queues. Therefore, as long as the context under-estimates the amount of space remaining in the message queue, it will never write too many messages into the queue to be accepted by the relay-chain at a later point.

Likewise, each parachain is the only consumer of messages for its incoming message queues. Therefore, as long as the context under-estimates the amount of messages available to be processed, it will never read more messages than exist in the queue.

Here's an example. Imagine the base context of parachain P at relay-parent R2 has space for 5 messages in its upward message queue. At R2, the latest parachain block included is P1. Off-chain, there's P2 building on R0 with 4 upward mesasges and P3 building on R2 with 1 upward message. By the time P3 is backed in R4, there might be more message space is available. But that's fine, because our underestimate ensured that we didn't use more space than there was available.

The downside of this approach is that it introduces additional latency between parachains. If 2 parachains are communicating but the chains are built asynchronously with an N block delay between being backed and actually included on the relay-chain, that means that there's a 2N*6s latency for messages to pass between them.

To alleviate the downside of higher latency for message-passing, we could relax the 'underestimate' condition for nodes to choose which chains to build on, and instead allow them to assume that by the time a particular candidate is included, the message queues of 1 or more other parachains will have a particular prefix. This increases the risk of wasted effort: if all parachains expect that all others' prospective chains will, in fact, be included, one parachain block being different than expected would be able to set off a cascade of un-backable prospective chains. This bears further research.

3. Limitations from Approval Checking

Although modifications to allow prospective chains to be built may in theory allow us to extend execution time and PoV size almost indefinitely in a tradeoff for cross-chain message latency, the approval checking protocol has to run more or less synchronously with the growth of the relay chain. Approval-checking will become the ultimate guide for maximum PoV size and execution time limits.

4. Cross-session blocks

At the moment, parablocks never cross session boundaries. That is, if a parablock is backed in session S but is not included before the end of S, it is immediately dropped. This has deeper implications for prospective chains - we don't propose to change this restriction at the moment, but it does mean that there will be more wasted effort at session boundaries or potentially a period of 2 or 3 relay chain blocks at the beginning of each session where there is no parachain block.

5. Prospective Availability

The initial goal of contextual execution is to make backing networking & execution no longer a bottleneck for parachain progression. However, when there is a candidate pending availability, that also impedes progress of the parachain. We might look to extend availability distribution to have validators fetch chunks for candidates that are only backed off-chain (prospectively), so all that remains after inclusion is to sign bitfields, which is cheap. Availability currently suffers from the same issues as backing, with respect to the short relay-chain block time - there are 6 seconds between every relay-chain block, which gives only a few seconds to recover chunks before signing a bitfield. If the window of opportunity for enough backers to recover their chunk of a candidate is missed even by a tiny margin, the parachain is delayed by 6 whole seconds. Making availability asynchronous would be ideal.