Eek! I just realized something, which is that the scheme does require O(C^2) bandwidth after all. The scheme does require validators creating collations or blocks to verify the work of the entire chain, even if only for a short “burst” period of time once in a while. Particularly, this means that it can’t work if the only acceptable values for WINDBACK are less than SLOT_COUNT (which is likely; remember that if SLOT_COUNT = 20 with 100 shards, that means that each collation contains 5 blocks’ worth of data, so with WINDBACK = SLOT_COUNT, a validator is asked to process the equivalent of a block for each shard within the timespan of one block). Also, note that increasing LOOKAHEAD doesn’t help, as the data doesn’t become available to verify until one block length before the validator needs to make their own block/collation.
The goal should be for block creators to be able to use an existing random-sampled vote among collation validators to determine that some collation is available and finalize its membership in the main chain. One simple option is forkful sharding with a revert limit. In fact, I’m not sure if it’s possible to improve on that without completely leaning on a scalable data availability proof solution.
We can have a scheme where once a shard is suggested it needs to be voted on by a committee, but that has more complicated incentives as you have to figure out the right rewards for the committee members, whereas it’s much more clear for the forkful model where each collation creator is implicitly voting on the availability of every collation before them.