Make compact proofs backwards compatible for relaying with non-compact proof

[bkontur]

Base for runtimes: https://github.com/paritytech/polkadot-sdk/pull/4729 Base for relayer: https://github.com/paritytech/parity-bridges-common/pull/3012

When running Rococo/Westend both upgraded to compact proofs with relayer version with compact proofs, everything works ok, but:

Problem

The compact proofs are not backward-compatible. E.g. Polkadot/Kusama bridge, let's say we upgrade just one chain BridgeHubKusama with the runtime version that contains compact proof, but BridgeHubPolkadot will be upgraded later (in few days, weeks, ...). Our actual relayer code does not work, because an upgraded relayer code produces for the storage proofs:

pub struct UnverifiedStorageProof {
    proof: RawStorageProof,
    db: Vec<(RawStorageKey, Option<DBValue>)>,
}

instead of previous:

pub type RawStorageProof = Vec<Vec<u8>>;

I was able to fix codegen stuff and relay-clients stuff in bridges repo, so where we expect RawStorageProof, I just take it from UnverifiedStorageProof::proof, so at least now we submit valid and encodable extrinsics from relayer version with compact proofs to the runtime with non-compact proofs, but obviously it is not enough, because there is a problem with proofs validation, I can see the error:

Module: {
  index: 52
  error: 0x02010200
}

iiuc, it is this:

 /// The `Vec` entries weren't sorted as expected.
UnsortedEntries,

Solution?

We need to find a way how to fix this, at least for compact proofs. Anytime, we add this kind of breaking change, it has to work with old runtime and new runtime, because all the time the BridgeHub runtimes upgrade is totally asynchronous.

So, maybe possible solution could be:

1. make some conversion from UnverifiedStorageProof to valid/sorted RawStorageProof?
2. fix UnverifiedStorageProof::try_new to create valid/sorted trie_proof ?
3. parametrize fn prove_storage_with_root to return kind of enum:

   enum Proofs {
   Compact(UnverifiedStorageProof),
   NonCompact(RawStorageProof)
   }

4. revert compact proofs?
5. other solution?

How to test locally

Run polkadot-fellows bridges zombienet tests with setup:

• relayer built from https://github.com/paritytech/parity-bridges-common/pull/3012
• chain-spec-generator built from tag 1.2.5
• polkadot/polkadot-parachain built from master or whatever (should not make difference)

[bkontur]

@serban300 Serban, can you please take a look here?