Allow parachains to place extra data in the availability store

[rphmeier]

Each candidate descriptor would get another field:

extra_data: Vec<(Hash, u32)>,

indicating the hashes and lengths of preimages of extra data to be maintained by the validators of Polkadot. The sum of the lengths would not be allowed to exceed more than a certain protocol limit.

Collators would be responsible for providing the actual data here to backers, and each piece of data would be erasure-coded just as the PoV is and fetched by validators from backers during availability distribution.

[rphmeier]

cc @eskimor @drahnr I think it would make sense to start aggregating issues that propose changes to the primitive type formats in a "Primitives v2.0" milestone or project. Your call!

[eskimor]

Some motivation for this would be good. Is this the way we are going to implement XCMP?

[rphmeier]

The motivation is that it would be helpful for implementing multi-level relay chains and other rollups on parachains. @gavofyork has a specific experiment in mind called 'Blitzchain' which will need this, but only in the later phases.

[burdges]

It'll probably be useful for something.. We know two designs for multiple relay chains:

Candy flipping (or elf flipping)

We divide validators into relay chains of n validators per relay chain with n <= 3f+1 < 2^{k+2} and 2^k <= f+1, so likely f=511 and n=1534 or f=255 and n=765. We add new validators to random relay chains and "churn enough" validators among relay chains based upon the leaving and new validators, so that we can prove that if the global validators set is 80% honest then each relay chain has 2f+1 aka 66.667% honest validators. We need some tricky stuff for XCMP etc. but under this design relay chains can simply trust one another's beefy poofs, which makes it extremely efficient.

As a simpler-but-not-really-correct variant, we could simply elect the validator set once and then assign exactly the same controller keys to all t relay chains, so that each controller key can run one validator on each relay chain. This only makes sense if you assume all validator operators would happily run all t of their validators themselves, not just loan out their one of their positions because they're too lazy to run an extra validator.

Hierarchical turnstiles

A polkadot-like chain runs as a polkadot parachain, so the parachain check both the child relay chain blocks, and the child beefy signatures. We might permit slashing and disputes via messages from polkadot too, although details remain unclear.

We obtain polkadot soundness only for the child relay chain however, not for the child relay chain's own parachains. We make the child's own reversion protocols work by checking the child's beefy, and enforcing its disputes, slashing, etc.

Although we lack polkadot soundness for the child relay chain's own parachains, we could enforce balance turnstiles so that unsoundness does not propagate, but arbitrary messages do not work of course.

I believe @gavofyork's blitzchain ideas work like this hierarchical approach but pass availability data too. It's likely availability improves upon pure turnstiles for some transaction or message types, but the details become quite messy:

• We'd require no one machine ever possesses all the extra_data, which complicates our validator-collators networking considerably.
• As polkadot validators never run child parachain code, them doing pre-PVF builds might become a tragedy of the commons.

A priori, I'd suggest blitzchains initially focus upon doing turnstiles correctly, so purely a problem in token standard, warning users, etc. After we've discussed the problem more, then we'd later "lightly" involve the parachain team for messaging slashes, disputes, etc. We avoid validator-collators networking until someone demonstrates some concrete improvements over turnstiles however. @AlistairStewart has thought more about IBC, bridges, etc. so maybe he already knows cases.

All that said, there could exist other reasons for doing this without additional pre-PVF builds and without complicating validator-collators networking.

[burdges]

Anyways what does this really look like?

In polkadot, we first do a data availability proof and then next do an interactive correctness proof under a byzantine threat model. As I said above, we know weaker threat model stories for which availability does not necessarily matter.

We also know protocols that only require the data availability proof, like paying polkadot validators for initial super-seeding of contentious data before bittorrent takes over, meaning we want pure data availability chains eventually.

In this, we're slaving multiple extra unchecked data only availability cores to a single parachain, but without involving them directly in approval checking, so maybe extra_data could simply reference multiple earlier blocks already included by the relay chain?

We could seemingly do this entirely in parachain code without complicating consensus, although likely this requires asynchronous backing on the child relay chain?

Alright, I've now argued both that this sounds too complex, and that it's maybe trivial once we have asynchronous backing and unchecked data only availability cores, so.. ;)