I still think a once-per-day change in BASEFEE would be optimal for the user experience. Today, say it’s 10 Gwei. Let the MAX gas float up to 4x the target of 8 million for the entire day. If we use 175 Billion gas instead of the daily 50 Billion target, AND that raises the 30-day moving average above 50 Billion, then the BASEFEE inches up to 12 Gwei tomorrow, and 20% more the day after that, etc…until the average gas usage returns to target. Sure, the state size can grow at 4x for very a few days, but it really doesn’t matter as long as the gas slowly reprices to limit state growth to something sustainable.
Tips would only really be needed (1) to incentivize miners to take the transaction and (2) if the network is under a severe load (whether the surge due to an ICO or Cryptokitties or DOS), in which case it can revert to more of a competitive auction. But set the default tip at 25% of BASEFEE. Everyone knows the gas price, and that it might go up (or down) 20% tomorrow. If a client pays yesterday’s basefee by accident (e.g. they submit the tx a few seconds before the BASEFEE changes, then their 25% tip will be reduced to 5% and probably still be accepted by a miner.
Clients can still opt to pay double the BASEFEE (or more) as a tip for high priority transactions during congestion.
I fail to see why the gas price needs to change so rapidly as every few blocks. It makes for a frustrating user experience. We have the luxury of a low uncle rate now, so there is no barrier to allowing high capacity days to occur.