I feel like this is much more complicated than it needs to be. Here’s what I had in mind.
Base-level fee market
There exist a class of users that we’ll call “operators”. An operator might have a piece of data D with root R = root(D), which they want to become the block published at some slot in some shard. They sign (R, slot, shard, operatorID, fee).
There is an execution environment that maintains a state storing a balance for each (operator, shard) pair and that contains a function submitDataProof. This function takes as input (i) a signed message as above, (ii) a Merkle proof proving that a shard block with data root R actually as included at the given slot in the given shard. If this data is correct, and if the operator has enough balance assigned to that shard, the fee is transferred into the account of the proposer of that block.
For replay protection, we could just do the dumb thing: save hash((R, slot, shard, operatorID, fee)) as a state object, which will eventually expire on its own, and to prevent replay post-expiry just require such objects to be included on-chain between slot and slot + 1\ week.
Execution-environment-specific fee market
Any of the schemes in here: Tradeoffs in Account Abstraction Proposals
I currently favor PAYGAS + BREAKPOINT.
To facilitate operators “capturing” fees, we could add to the execution environment a transaction type that says “set the PAYGAS receipient to address X”.