Potential Gas costs improvement for message deliveries

[acatangiu]

Right now, on Polkadot Bridge Hub, message M is only stored on-chain during one block: block q when it was enqueued to outbound queue. It is only included in messages_root_digest of block q.

BEEFY proofs are not sent to Ethereum very often because they are very expensive, so a BEEFY proof will cover a large range of [prev_BEEFY_proof, current_BEEFY_proof] blocks.

Proposal:
On Polkadot Bridge Hub keep messages in storage across multiple blocks: on-chain storage lifetime of message M: [M_enqueued, M_delivery_confirmed_and_M_pruned] == [block_q, block_p].

This means message M can be proven using any of the merkle tree root digests in [block_q, block_p] interval.

On Ethereum side, this means that M can be proved directly using the BH block included in any BEEFY proof that falls within [block_q, block_p].

This saves a step on Ethereum side to also prove that block_q is parent of block_in_current_BEEFY_proof, at the cost of extra storage use on Polkadot Bridge Hub.

It with worth noting however, that we already cover the storage "deposit" for message M in the form of the relayer reward which is locked on BH until the message delivery proof is provided (at which point we would also pruned from storage), so there is no DoS concern as long as there is a minimum relayer reward enforced.

[yrong]

This saves a step on Ethereum side to also prove that block_q is parent of block_in_current_BEEFY_proof

Actually, there is no such step on Ethereum side. In the parachain/message relayer, we simply scan messages before the BEEFY block that is finalized on light client, and generate MMR proof against that block.

we already cover the storage "deposit" for message M in the form of the relayer reward

Actually, this is not covered by the relay reward. The deposit/commit message cost is benchmarked seperately and is covered either by the bridge fee configured on AH, or through extra weight on the bridge extrinsic - e.g., register_token

@acatangiu I've explored your idea in PR#9036. In that PR, instead of using on_initialize or on_finalize to commit messages in every block, I switch to on_idle to merge messages from multiple blocks - at the cost of some extra storage used on BH and potentially some latency in relaying the message.

I'm not sure it's worthwhile, so I'd like to get some early feedback before moving forward.