Suppose the transaction fee is split into two fees: one for the miner, and one for a node that relays it to a miner.
The person who creates a transaction would need a method to sign an input that anybody could claim, but in a way that it's only valid if their transaction makes it into a block.
So here's a proposal: let's say you implement one of the recent suggestions, and make an altcoin which uses SNARKs as its transaction validation method. Instead of a block containing inputs, signatures, and outputs, it contains inputs, outputs, and a SNARK that proves that all inputs have been properly signed to
some output in the block.
Now, you've got gossips which pass the transaction from the person who originally signed it. With this kind of proof system, it's easy enough to aggregate transactions into a larger transaction, and include as its proof - once again - that all the outputs required by the inputs are being paid. Then, it'd be easy enough for such relays to add their own outputs to the merged transaction (so long as those new outputs don't make output>input). The mining case, then, becomes merely a specific case of this general one - the miner joins the transactions with the coinbase into a final "mining transaction", and pockets all unaccounted-for fees. Miners can't steal relay money because they can't necessarily
see the original transaction; all they have is the SNARK-blinded transactions sent by their peers. Unless, of course, they're getting the transactions directly from the users, in which case they're the ones paying for the bandwidth so them getting the reward fee is fine.
