Computation of real message bandwidth available in asynchronous backing

[rphmeier]

The parachain-system pallet should keep track of the 'unincluded segment' of the parachain. This is all recent blocks which have not been included in a referenced relay-parent.

For each block in the unincluded segment, parachain-system should track:

• Outgoing UMP message count, size
• Outgoing HRMP message count, size per recipient
• Stated HRMP watermark
• DMP messages processed

We also keep a struct aggregating the data from the whole unincluded segment:

• Total outgoing UMP message count, size in the unincluded segment
• Total outgoing HRMP message count, size per recipient in the unincluded segment
• Highest HRMP watermark in the unincluded segment
• Total DMP messages processed

Note that if the unincluded segment of the parachain is empty, this is equivalent to the protocol before asynchronous backing, where we only build parablocks once the parent parablock has been included and therefore the unincluded segment is always empty.

On initialization of parachain-system, we:

1. Read a storage proof of the latest head of the para included under the relay-parent
2. Discard everything in the unincluded segment up to and including that head
3. Update the aggregate struct

The aggregate struct will be used to further limit message bandwidth and processing beyond just what is stated by the relay-parent storage proofs

[rphmeier]

The remaining size of UMP and HRMP outgoing queues available to a parachain depends not only on the relay-chain state but also on the intermediate parablocks which have not yet been applied in the relay-chain state. The status quo, without async backing, is that there aren't intermediate blocks. The message queues are essentially double-ended and as the relay-parent progresses the on-chain queue drains from one side, and new parablocks push onto the other. The way Cumulus should account for the actual remaining message queue size is by reading remaining limits from the relay-parent state and then subtracting all message bandwidth used in parablocks between the last relay-parent recognized parablock and the current block. This is always either an exact estimate or underestimate w.r.t. where the parablock actually gets included in the relay chain due to the double-ended nature of the queue

Based on this comment I posted elsewhere ^

[rphmeier]

Since this requires an extra relay-chain state proof (for the currently included head of the parachain at the given relay-parent), we have a 4 distinct cases we will encounter:

1. (no pallet changes, cumulus-node cannot produce state proof) => status quo
2. (pallet changes, cumulus-node cannot produce state proof) => the pallet changes should probably be "dormant" i.e. silently ignore a missing state proof unless the unincluded segment is allowed to be >0 length.
3. (no pallet changes, cumulus-node can produce state proof) => will require a bit of logic, either in the inherent creation phase or within the InherentData creation phase, to either avoid putting the state proof into the inherent or not producing it at all
4. (pallet changes, cumulus-node can produce state proof) => upgrade complete

The upgrade path will probably be something like:

1. pallet is upgraded but unincluded segment is kept at 0, cumulus nodes upgrade in meantime
2. once the pallet is upgraded and all collators have updated to the new node, the parachain governance sets unincluded segment to the desired length

[slumber]

Why do we need to track watermarks for each unincluded candidate when we have Highest HRMP watermark?

We do need to track per-candidate messages counts and sizes in order to update aggregated struct, but the watermark only depends on the latest candidate

[rphmeier]

Yes, it seems like we could get away with not storing the watermark for each block in the segment and still obey the watermark rules.

[slumber]

Since this requires an extra relay-chain state proof (for the currently included head of the parachain at the given relay-parent), we have a 4 distinct cases we will encounter:

ParachainInherentData provided for each block contains PersistedValidationData with a latest para head, doesn't it? I don't think there's any reason to get it directly from the storage proof. Now I doubt paritytech/polkadot#6915 was necessary

[rphmeier]

The PersistedValidationData would have the parent's head-data, not the head-data of the most recently included parachain block as-of that relay parent. After asynchronous backing, they are not the same.

[slumber]

The PersistedValidationData would have the parent's head-data, not the head-data of the most recently included parachain block as-of that relay parent. After asynchronous backing, they are not the same.

It would have a required parent data for new candidates, yes. This is exactly how prospective parachains fetch modifications constraints from the runtime
https://github.com/paritytech/polkadot/blob/1e06eb8ac76fcaf523a08ac7f6a10c310571fe0f/runtime/parachains/src/runtime_api_impl/vstaging.rs#L46

And the very same line used for constructing PVD:
https://github.com/paritytech/polkadot/blob/1e06eb8ac76fcaf523a08ac7f6a10c310571fe0f/runtime/parachains/src/util.rs#L37

What's the difference?

Thinking of it, parachains system should represent a path in a fragment tree, thus we also need to read pending availability similar to paritytech/polkadot#6791

[rphmeier]

The difference is the point in time when we read the last included head. Cumulus makes its PVD way before runtime::parachains::make_persisted_validation_data is invoked. The Polkadot runtime only processes parablocks in sequential order, so at that point in time the most recently included block is the parent block. That doesn't mean that it's the case at the point in time when those parablocks were created.

Thinking of it, parachains system should represent a path in a fragment tree, thus we also need to read pending availability

This is missing the point of the whole unincluded segment mechanism. After asynchronous backing, we'll have prospective parachain blocks which don't yet exist in any relay chain state and are only stored offchain on nodes, until they can be posted. The unincluded segment mechanism tells us about all parachain blocks since the most recently included one.

Example:

Consider 4 parachain blocks

A <- B <- C <- D

In relay-parent X, A is the most recently included block. B has been posted on-chain but is pending availability. C is backable but hasn't been posted on-chain. D is backable but hasn't been posted on-chain. C and D both have relay-parent X.

The PersistedValidationData for C should have B as its parent head-data, but we'd read A out of the state of X as the most recently included block. Notice that these are different parachain blocks. So then in C we can tell that the unincluded segment is [B].

The PersistedValidationData for D should have C as its parent head-data, but we'd read A out of the state of X as the most recently included block. Notice that these are different parachain blocks. So then in D we can tell that the unincluded segment is [B C].

I hope this makes sense now.

[slumber]

#2438