All that complexity and a possible DOS risk could be moved to layer 2 if it was possible to
(1) separate the sender from the gas payer, ie. one account pays for gas (‘Payer’), another one has everything else (balance, origin, sender, …) (‘Sender’). Two signatures and two separate repeat protections (eg. nonces) are needed. The Payer must be a codeless account with a direct signature, the Sender can be a contract with arbitrary signature verification code.
(2) execute code in transactions directly.
The major advantage is that as the contract itself doesn’t have to care about gas payments for this to work, so this upgrade would include all existing contracts.
In (1) ‘everything else’ includes gas limit, gas price and replacement behavior in the mempool.
First the Payer’s signature is checked exactly like now. If correct, Sender’s signature verification starts - the gas cost is paid by the Payer. Invalid signature reverts.
The Payer’s nonce is increased, as in a normal transaction.
For a non-contract Sender its nonce has to be increased too. For contracts it’s a detail that should be determined by the signature verification function; it’s enough to have a bit that specifies whether to increment the nonce or not.
A nonce-incrementing transaction in the mempool is in two accounts at once: Payer’s and Sender’s. Replacement of one of them removes the other - this preserves the current replacement mechanic for both.
By (2) executing code directly in transaction I mean deprecating the ‘to’ field: instead the transaction only has an eth amount and code, all calls have to be explicit. Unused eth returns.
This would make it possible to pay for gas (indirectly) in tokens: include code to transfer them to the Payer (an opcode that provides its address is needed) as a fee.
If Sender is a contract all signature schemes are possible, assuming there’s a way to specify the verification function.
For dapps with a clearly defined site (eg. etherdelta) utilization of this would be trivial - they can generate transactions (as a Payer) on their server. For a general use case third-party providers, or a network of them, would be needed - I can imagine wallets (especially metamask) providing an option to pay a fee in tokens, or something else, directly. All DOS risk is shifted to the willing participants, which can utilize methods not possible on the protocol level (like using a website with a captcha to prevent spamming).
Everything in between these two extremes (total abstraction, and forcing one specific signature scheme on everyone) is a tradeoff
Only the gas-paying accounts would have to use the builtin signature scheme.