Parachain Authoring: Enforce Relay Parent Gap By Descendant Headers

[skunert]

Problem to solve

Parachain forks are tightly coupled to relay chain forks. With asynchronous-backing chains, we were able to build a parachain block on all observed relay parents. This allowed parachains to progress even in the presence of relay chain forks.
With elastic-scaling, we build blocks on a much stricter time-budget, where we don't have time to build on every relay parent we see. Therefore, we just build on the best one. This leads to situations where a parachain builds on the wrong relay chain fork and has to rebuild some blocks.

We can alleviate this by building on older relay parents instead of the tip of the chain. This leads to a higher message latency, but we can assume that any forks have settled.

Providing Relay Parent Descendants

The problem with these approaches has been that we were not sure how to enforce that authors really author blocks behind the tip.

I propose that parachain block authors who want to author on relay parent RP also need to provide N additional headers of RP's descendants to the parachain runtime. N is the size of the offset the authoring should lag behind the chain-tip. By enforcing that these headers are present, parachain authors cannot author directly at the tip, because not enough descendants of their relay parent would exist.

For verification, we could do rough verification by checking that the headers were signed by relay chain authorities. A proof of the authority can be provided in the relay chain storage proof that is passed into the parachain runtime anyway. This way, no modification of the PVF is necessary and this remains a parachain-only modification. Relay chain authorities should not be able to easily forge additional headers, because that would be an equivocation on the relay chain.

The downside is that we need to include more data in the Proof of Validity. The PoV would grow by the space for N relay chain headers and the additional nodes in the storage proof.

[alexggh]

The problem with these approaches has been that we were not sure how to enforce that authors really author blocks behind the tip.

Why does it need enforcing ? Is there any downside if the honest ones follow this rules and the malicious ones don't ?

[skunert]

The problem with these approaches has been that we were not sure how to enforce that authors really author blocks behind the tip.

Why does it need enforcing ? Is there any downside if the honest ones follow this rules and the malicious ones don't ?

Mostly annoyances. Since we are currently authoring at the tip, its not possible to just jump some slots in the future. But when everyone authors 3 blocks behind the tip, one author could just eagerly use its slot by using a RP from the "future". This will skip authors basically.

With the block-based collator this is addressed partly, but you can still jump multiple blocks ahead by exploiting the leniency.

My proposal here is an extension that should work with both models and should prevent this kind of "slot jumping".