Idea: Block based collator

[eskimor]

The currently getting implemented slot based collator is fully time based, but still depends on relay chain blocks to validate the time, to be able to prove legitimate aura block authorship.

The result is, that while we build based on time/parachain slots we still need to wait for the relay block for the current slot to arrive, before building a block.

Slots:

|i-----------|--------i---|-------i----|

In the above graphic, arrival of relay chain blocks is marked with an i. The collator still needs to wait for that relay chain block in its slot, because the timestamp of the relay chain block is used to validate the "correctness" of the slot: The aura authorship is compared with the timestamp in the relay chain block: It has to be in the right slot for it to be valid.

Now, why is this a problem? This is actually only problematic if you are having a parachain with really high load, think of elastic scaling. Here the waiting for the relay chain block can significantly harm performance, we will simply be lacking the time to build blocks fast enough to occupy all our cores: One second waiting is one second not building.

Towards a Solution

First idea to fix this was to use the relay chain block of the previous slot to validate the time. This approach has two problems though:

1. If we were using the previous block as relay parent, this would imply an additional 6s delay for processing messages, adding latency for users.
2. It gives collators too much freedom.

The problem with (2) is we can not check that a collator actually used the previous relay chain block instead of the most recent one, hence it can cheat and claim block authorship when it was not actually its turn. This works because slots may get occupied by a block, but don't need to, so jumping one slot number is totally fine.

Given that the cheating collator would be the one having the next turn anyways, it would not be able to produce more blocks this way, but can steal a block production opportunity from the previous collator, harming its rewards (potentially benefiting itself) and might also profit from stealing a block with a high amount of transaction fees. A collator might find incentives to harm others and the network itself.

Proposed Solution

We could use relay chain block numbers as a means for measuring time and thus parachain slots. We would index into the Aura collator set via the relay chain block number the collation is based on (or its parent).

With this we can have the following scheme:

First, we store the relay chain block number that was used for the last produced block in the state of the parachain, we call this block number s.

Second when you build a new block we determine the index into the Aura set like this:

We take the block number of the used relay parent n determine the index k of the legitimate block producer like so:

1. n >= s + 1 && n < s + 3 -> k := s + 1
2. n <= s -> illegal
3. n >= s + 3 -> k := n - 1

The idea is, we are logically basing the authorship selection on the parent of the most recent relay chain block: We offset. How the protocol would work for collators:

1. First block produced: Collator takes the most recent relay parent available and uses its parent number n - 1 to determine whether it is its turn. This number is then stored in the state and will become the current s := n - 1.
2. Collators wait 6s (slot time), then they check, either still only the relay parent used by the previous collator is available, then they can use that and k will simply be s+1 or a new relay block already arrived, then they can also use that one (for lower latency), but the k will still be determined by s+1.

With this we don't need to wait for the next relay chain block to be available, but if it is available we can use it and thus have the lowest possible latency. Because we use s+1 regardless of whether a newly available relay chain block was used or the previous one, "block stealing" is not possible.

Rule (3) exists to deal with censoring or malfunctioning collators. Without rule (3) we would forever be stuck with the same collator and if it would not produce blocks the chain would stall. With rule (3), it becomes legal to advance k by more than 1, if block production opportunities have been missed.

Limitations/Consequences

If we take relay chain block numbers to index the collator set, slot times lower than 6s are not possible. I believe that is fine though and might actually lead to simplifications. A slot time of 6s does not mean that we can not produce blocks faster than that, it is just that we can only rotate the block producer every 6s, which does not seem problematic. For elastic scaling, it would simply be the duty of the current collator to produce blocks for all cores of its slot, this is also a very simple solution for how to coordinate what collator should produce blocks for what core ... there is only one -> No coordination required.

Theoretical Generalization

If we ever found that being able to use the previous relay chain block is not sufficient, the above scheme can be arbitrarily extended at the cost of larger downtime in case of a malfunctioning collator. E.g. if we wanted to allow not only the parent of the most recent block, but even the grand parent, we would achieve that by adjusting above to:

1. n >= s + 1 && n < s+ 4 -> k := s + 1
2. n <= s -> illegal
3. n >= s + 4 -> k := n - 1

Core Sharing Parachains

We actually do have an issue with parachains sharing a core with this scheme, but that issue exists for the existing time based scheme as well: If paras are sharing a core, e.g. 2 paras, we have assignments like [A,B,A,B], which implies that parachain A will only ever see uneven block numbers and B will only ever see even block numbers. Thus both paras would operate on half their collator set. For three paras only a third.

This can easily be adjusted statically both in the existing model as in the proposed one. In the time based model you would have a slot time of 12s instead of 6. In the proposed model it is similarly easy to adjust statically for every nth relay chain block.

Ideally though, this would work dynamically, so that chains can switch between core sharings as they please easily. Luckily, we do have a partial solution already in place: The reshuffling of collators every session might be good enough in practice, to not worry about this for now.

SASSAFRAS

I have not checked, but I would assume that using relay chain block numbers as a measure of time should equally well work here.

Alternatives

Instead of going with block numbers, we could also keep slots, but make it so, that skipping one slot is illegal, you have to skip two or none. (Same as above proposal with block numbers.)

Then we would store the last slot number or time in the state and do above scheme with slot numbers. (Always advance by 1, regardless of the timestamp of the relay parent as long as it is within bounds.)

In other words, we don't need to move to block numbers to deploy above scheme. It does feel a bit cleaner though, as in the end we are using relay chain blocks as the metric of time anyways.

[sandreim]

The currently getting implemented slot based collator is fully time based, but still depends on relay chain blocks to validate the time, to be able to prove legitimate aura block authorship.

The result is, that while we build based on time/parachain slots we still need to wait for the relay block for the current slot to arrive, before building a block.

Currently we have implemented an offset of +1s (hardcoded) for the aura slots vs relay chain slot. Meaning, first slots starts 1s after the relay chain one, so it is not that much of a problem , one second should be enough to get the relay chain block.

Slots:

|i-----------|--------i---|-------i----|

In the above graphic, arrival of relay chain blocks is marked with an i. The collator still needs to wait for that relay chain block in its slot, because the timestamp of the relay chain block is used to validate the "correctness" of the slot: The aura authorship is compared with the timestamp in the relay chain block: It has to be in the right slot for it to be valid.

Now, why is this a problem? This is actually only problematic if you are having a parachain with really high load, think of elastic scaling. Here the waiting for the relay chain block can significantly harm performance, we will simply be lacking the time to build blocks fast enough to occupy all our cores: One second waiting is one second not building.

The proposal looks sensible. Is it worth to invest time to implement it at this point ? It looks to me like an optimization that could be done later if we still needed. Beefy single core performant collator CPUs and eventuall transaction streaming can mitigate the problem described here.

Otherwise, definetly a good property for elastic scaling: same author builds all collations which leads to much less need to coordinate with next author by tx streaming.

[eskimor]

Is it worth to invest time to implement it at this point ?

Very likely not at this point. This just serves as an idea for further improvements, to be picked up when/if needed.

[burdges]

Sassafras should slightly improve this: If you've two relay chain blocks coming then they might come at different times. We could delay the relay chain aura blocks just slightly, even like 20 miliseconds, so that the praos relay hain blocks tended to arrive first, which then reduces the sassafras advantage.

In test nets, it's possible to reduce the number of praos relay chain blocks, so then you get a measure of how much worse the unpredictable praos blocks make things. This is much easier to do, even vs delaying down the praos blocks.

[burdges]

We could transport relay chain blocks faster using bittorrent style fetching, and possible erasure coding, instead of just gossiping the whole block.

As an aside, there are academic papers on deducing real time from block time, like https://eprint.iacr.org/2019/838 and https://eprint.iacr.org/2019/1348, but they're after specific threat models, not optimization, so they might be miss-leading here.

[burdges]

Is it worth to invest time to implement it at this point ?

At a high level, we should remember that web2 requires sharded data models everywhere, so elastic scaling tops out quickly once real usage occurs. We'll risk deluding ourselves into thinking that elastic scaling could go futher than really possible.

It's likely better to push stuff like off-chain messaging rather than squeeking out every last 5% from elastic scaling.