Explicit No-Shows in Approval Checking

[Overkillus]

TLDR; Allow for explicit no-show messages to be sent in approval checking when a node is certain it will no-show (ultra overworked or some weird error preventing it from completing the work)

---

This issue is an early exploration of a slight alteration to the Approval Checking Process. This is a minor departure from the ELVES paper, but remains in the same spirit. RFC will most likely follow after the design is a bit more clear.

No-Shows Reminder

No-Shows are when a relay chain validator publishes his assignment for approval checking but then cannot fulfill the assignment in a timely fashion. This results in a no-show which prompts the system to request even more approval checkers (2-3 more per no-show). This is a soft escalation method.

No-Shows are there as a countermeasure for DoS attacks and so they should be triggered when there is a DoS attack. There is also one other intended cause for no-shows but it is a heavy defense in depth scenario when a validator gets slashed, disabled but still participates in approval checking, he no longer can cause disputes (hard escalations) but he can still cause intentional no-shows (small escalations).

Ideally except the two cases above no-shows should occur as rarely as possible.

Issue

Unfortunately as it stands no-shows are still quite frequently triggered on Kusama and Polkadot and we suspect it has nothing to do with a DoS attack. Sometimes nodes can be overworked (more frequent for under or just on spec nodes) and they will simply not complete the assignment in time, resulting in a no-show.

No-shows without a good reason start a vicious cycle. Some nodes were overworked and they no-showed which soft escalates adding a new tranche of checkers adding even more work to the system causing more nodes to potentially be overworked.

As of today a node that is so overworked it knows for sure it will not complete an assignment will still publish their assignment and the system cannot move on from that candidate untill that assignment timeouts or completes. The timeout window is rather large so every time we get a slow validator everything stalls at least for the timeout, assuming the next tranche was perfectly competent.

This leads to some inconsistent finality times and random short finality lag spikes.

Solution

1. When a validator knows it cannot fulfill an assignment it could skip on publishing the assignment but that is quite risky. We need the approval checkers and completely skipping the checks can give a noticeable edge to the attackers.

2. Alternatively the validator instead of waiting for a full timeout window the validator can issue a new statement type, an explicit no-show message. This instead of waiting for the timeout window until counting a no-show will immediately trigger the next tranche. The next tranche if alsos not overworked will complete the check and everything can proceed as normal, probably before we even reached the original no-show timeout.

3. Pushing this idea even further, the overworked validator creating the explicit no-show message is not as severe of a situation as someone being straight up DoS'ed. So it might warrant a smaller escalation (less than a tranche of 2-3). We might opt in for a 1:1 replacement policy. The overworked validator would issue the explicit no-show statement which most likely will use a VRF to randomly select another validator to take their place.

There is an open question as to how to select the replacement. Maybe the replacement can be freely chosen. Maybe some heuristic is used that takes into account past approval checking performance so better validators are chosen more often. Maybe we use a completely random selection with a VRF for the replacement choosing.

Further Details

No matter what strategy we are choosing this also further improves the new disabling strategy which added a new no-show reason. Disabled validators issuing explicit no-shows (small escalations) makes sense because they can NEVER raise a dispute anyway. This is a straight up upgrade as we get to skip the timeout window in those cases. This benefit is a bit of a defense in depth and it will only materialize when some honest nodes are disabled on chain, while there is an invalid candidate being checked. Unlikely to happen but possible.

This is loosely connected to the issue of being more explicit when raising disputes (hard escalations) discussed here: #872

As of today we don't have approval checking rewards but once those are implemented it would be intended for the replacement approval checker to get them to further incentivise hard working validators (on or above spec).

Additionally, if security or 1:1 replacements are a concern we could potentially opt for replacements only in tranche 0 or early tranches. The policy does not have to be uniform over tranches.

Concerns

This is not a straight up upgrade (except for the disabled node scenario). Especially the 1:1 replacement policy can pose some risks and it needs to be looked into more.

[burdges]

Importantly there is no back pressue here, just workload rearrangement, which makes us nervious.

We've not analyized this properly, but the analysis feels messy.

In principle, workload rearrangement might lower security, and thus demand more checkers. As an extreme example, no-shows already lower security vs some idealized scheme which simply makes needed_approvals assignments, and then rejects the parablock if even one approval checker never responds. We do no-shows as some liveness compromise, and this pushes that further, but if no-shows really rearranged workload much then maybe security drops more?

Adversaries could definitely improve their odds by having better hardware, certianly in the current system, but maybe worse here. Alistair expressed worries over the no-shows being faster, but this requires more thought imho. Also, one could discuss really how the work gets dropped, like maybe the adversary cannot benefit so much for other reasons?

Ideally except the two cases above no-shows should occur as rarely as possible.

A priori, this proposal goes the opposite direction of this statement. We've high risks this proposal cause more work overall, and even more no-shows, making this some a load vs latency tradeoff.

Although certianly not impossible, I'd argue this needs more justification, and alternatives need a closer look.

No matter what strategy we are choosing this also further improves the new disabling strategy which added a new no-show reason.

I disagree, you've no connection between disabling and no-shows here, and afaik and explicit no-show messages provide nothing useful there. We could introduce some linkage of course, but only if we instrumet no-shows and compute the no-show median across validators, like for approvals in polkadot-fellows/RFCs#119 In particular, no-show medians/percentiles cannot benefit from these messages.

Anyways..

I'd propose three alternatives near-term:

We look more clearly about behavior under extreme loads: We should tolerate 10s of minutes of finality lag, so maybe we paniced and relaxed the spammining too early? We've maybe code bugs that trigger under long finality delays too, so maybe kusama needs more heavy spammining to identify and fix those bugs?

We implement polkadot-fellows/RFCs#119 with no-show medians/percentiles. Adjusting rewards based upon good vs bad no-show percentile actually helps, even if it impacts the validator set only slowly. We could discuss disabling options too, like maybe a week of high no-shows removes your intention to validate.

We focus upon real back pressue: We've some back pressue in backing already, based upon our own CPU load, but additionally

• RC block producers should drop backing statements,
• RC block producers could drop availability votes to delay inclusion, and
• all three of those should be triggerd by our observed no-shows, not just our own CPU load.

We could leave this issue open, it being one part of the design space, but focus upon these other topics.

[alexggh]

We do no-shows as some liveness compromise, and this pushes that further.
We look more clearly about behavior under extreme loads: We should tolerate 10s of minutes of finality lag,

The problem with that is that we had parachains complain about having high finality(~10 blocks, when normally is 3-4), that were triggered just by a few bad apples(validators), while I'm not sure this is the right solution, the core problem still exists just a few bad(slow or misbehaving) validators can significantly impact the finality lag and that's a metric some of our customers care about.

[Overkillus]

Importantly there is no back pressure here, just workload rearrangement,

I completely agree. This is not back-pressure nor is it aimed to be one. It simply aims to remedy the consequences of having some slow nodes which deteriorate the finality. It is a rearrangement of the workload.

In principle, workload rearrangement might lower security, and thus demand more checkers.

I don't have a clear cut answer here, but I can discuss my understanding.

Are nodes under the spec treated as byzantine in the analysis? They are not obviously malicious but not adhering to the spec is harmful so I assume they are. So what happens in a scenario where we have 2/3 honest and on spec with and without this change?

First of all with or without explicit no-shows attackers can still kill execution sharding if they really want to by a combination of DoS and no-showing themselves. This preserves security and keeps liveness but slows everything down. It leads to no obvious cost other than opp cost (minimal rn with no approval rewards). And slashing them through opengov will be difficult due to them blending in with the nodes they themselves DoS'ed.

Assuming the 1/3 is not as aggressive...

2/3 on spec nodes will still very rarely no-show when they get overworked with too many assignments. This hopefully should be very rare for on spec nodes.

The remaining 1/3 might no-show at an increased rate even during "normal" load.

Without explicit no-shows this will always lead to at least no-show timeout finality lag followed by another tranche worth of workload. So we always pay the latency price AND the extra workload price. This will occur very rarely for 2/3rds and more frequently for slow ones in the 1/3rd.

With explicit no shows the node seeing an unluckily high number of assignments and workload will skip on some and issue an explicit no-show (full tranche), this will skip the latency price but still add extra workload. Assuming we have a perfect oracle and can always predict we will eventually no-show for this assignment, issuing it explicitly is always an improvement (saving on latency and work will be done anyway). Do you agree with that? @burdges To rephrase, assuming we have no false positives explicitly no-showing does NOT deteriorate security.

The true cost of the explicit no-shows comes from the heuristic used to determine when to explicitly no-show. The heuristic is imperfect so sometimes false positives (cases where the validator would in fact make it in time but the heuristic used made him explicitly no-show) will occur. This creates a slight edge for good hardware attackers where they can expect a slightly higher proportion of approval checks than usually, based on how accurate our heuristic is. This introduced more load and some security costs.

False negatives (heuristic fails and we timeout instead of issuing an explicit no-show) on the other hand, are not affecting security but they affect latency.

A priori, this proposal goes the opposite direction of this statement. We've high risks this proposal causes more work overall, and even more no-shows, making this some a load vs latency tradeoff.

That's completely true. This will overall increase the load slightly. Remember that the no-shows would generally happen anyway, we simply aim to report them before they happen to reduce latency. If the heuristic is good the minor load overhead might be worth the latency stabilisation, or at least it is nice to have as an option in our toolbelt (since parachains complained about the unstable finality times).

On the other hand if we have a naive heuristic for a number of assignments being super high, this will probably lead to few false positives (not much extra load) but many false negatives on under the spec nodes. This will fail to achieve the main objective of reducing the latency issues caused by under the spec nodes timing out. Choosing a good heuristic here seems quite difficult. Ideally it would be aggressive under low spec and conservative for on or over spec.

I disagree, you've no connection between disabling and no-shows here, and afaik and explicit no-show messages provide nothing useful there.

Imagine an honest node that somehow got slashed and disabled maybe due to non-determinism. As of today this node will still participate in approval checking but it cannot raise disputes. This node still can no-show and if it finds an invalid candidate the idea was that instead of a hard escalation (dispute) it will soft escalate (no-show for 1 more tranche). Disabled nodes retain some escalation privileges. Issue is that an honest disabled node still needs to wait for the no-show timeout for others to acknowledge their soft escalation. This extra latency here is unnecessary and it would be better if they could issue it explicitly. I think there is a connection. Security wise it's the same but we save on latency.

We look more clearly about behavior under extreme loads: We should tolerate 10s of minutes of finality lag

500 blocks trigger the "training wheels" so that is how much we can "tolerate".

so maybe we panicked and relaxed the spammining too early? We've maybe code bugs that trigger under long finality delays too, so maybe kusama needs more heavy spammining to identify and fix those bugs?

A few days before the official spammening there was a prior Kusama test that pushed it to its limits. We know what broke then, see here for post-mortem: https://forum.polkadot.network/t/2025-11-25-kusama-parachains-spammening-aftermath/11108

We implement polkadot-fellows/RFCs#119 with no-show medians/percentiles. Adjusting rewards based upon good vs bad no-show percentile actually helps, even if it impacts the validator set only slowly. We could discuss disabling options too, like maybe a week of high no-shows removes your intention to validate.

This is overall a good direction and I support it fully. Disabling seems harsh and unnecessary since being disabled still allows you to do approval checking and possibly (?) gain rewards from it. But I understand the intention of further punishments for very inactive validators and think they are needed.

We focus upon real back pressure

I also agree we need better back pressure mechanisms. We will be adding finality proofs on chain to have some definitive reasons to do hard back pressuring but I am aware that this is quite delayed and not ideal. But it might be connected to some more drastic layer of back pressuring as it is very concrete and there is consensus on it. We should look for some other more immediate heuristics as well.

Nevertheless none of the above help fix the few under spec validators causing no-show timeouts. We cannot noticeably backpressure because 3 validators out of a 1000 are running terrible hardware. Approval checking rewards also might not be enough since those validators when contacted simply "accept" having lower reward and they are fine with it because financially they feel like upgrading is not worth it for them. The extra rewards are not worth the cost of new hardware. This might indicate we are too lenient on the rewards drop-off.

[burdges]

The problem with that is that we had parachains complain about having high finality(~10 blocks, when normally is 3-4), that were triggered just by a few bad apples(validators), while I'm not sure this is the right solution, the core problem still exists just a few bad(slow or misbehaving) validators can significantly impact the finality lag and that's a metric some of our customers care about.

At least for parachains, we should argue that "inclusion" should suffice for their own block production purposes, because including blocks not being finalized results in slashing, or at least loss of block production rewards.

In particular, inclusion behind some aura block means the chunks were distributed, so inclusion behind some babe block should occur, even if the current aura block gets forked out. Also sassafras fixes this, but maybe that waits for JAM.

[burdges]

Are nodes under the spec treated as byzantine in the analysis?

We've no idea if the spec makes sense or continues to make sense. An adversary could run seriously overspeced nodes, campaign for more cores, buy all those cores, and then then swamp everyone. This should transition workload onto the adversary, possible breaking our the 2/3rd honest assumption if the adversary were powerful enough.

Also, remember multiple relay chains pushes the honest assumptions harder, so an 80% adversay might approach being a 2/3rd adversary ocasionally, so while 2/3rd cannot really be sharp, maybe it'll become sharper than we'd like. That's distant future, but still..

Again I'm not completely opposed. I'd left space for this from early on, like that's why we never used RSA VRF, instead accepting slow EC VRF verifiers. Yet, I always worry changes like this "cover up" real needs using incorrect fixes. Alistair seems more worried than me, but we only discussed this briefly.

The true cost of the explicit no-shows comes from the heuristic used to determine when to explicitly no-show. The heuristic is imperfect so sometimes false positives .. will occur.

Yup the heuristic seems tricky. We've not even finished the back pressue heuristics yet,

This creates a slight edge for good hardware attackers where they can expect a slightly higher proportion of approval checks than usually, based on how accurate our heuristic is.

This is significant, not slight. Attackers could always trigger a heuristic more easily than really overworking the node, like the opposite of fudging a bencmark. ;)

Also, explicit no-shows are fast by design, so individually they miss some real back pressure. This is what most bothers me.

Issue is that an honest disabled node still needs to wait for the no-show timeout for others to acknowledge their soft escalation.

I see, you meant disabling impacting no-shows, while I thought you meant not no-shows impacting intention-to-validate. I suppose disabling comes from wrong votes, so we've no reason to disable a node because of no-shows, but intention-to-validate makes good sense. We've previously discussed intention-to-validate, but only after long running poor performance.

500 blocks trigger the "training wheels" so that is how much we can "tolerate".

I've forgotten what exactly happens then, but I think non-system parachains slow way down, right? At some point we'll have "true system parachains" so AssetHub could be slowed way down too. 10s of minutes was my example, but minutes makes sense too.

Anyways if we do this then we should push forward on the other alternative directions too.

[burdges]

We set non-zero tranches way too high ala #6853 which resulted in excessively fast blow ups.

I suppose this casued 5x the no-shows on no-shows, which cause quite a big delay.