Nice proposal. It is exciting to hear some carefully thought, incentivize based design


I think the current design already incentivize smaller blocks: Smaller blocks get broadcasted much faster and become less possible to be orphaned. If you consider that there are 25 coins to compete for, you would like to broadcast your block as fast as possible once you find it

With bigger blocks cap, it becomes more favorable to mine smaller blocks. 10MB blocks have a very high risk of being orphaned by 1MB blocks, since the time needed to broadcasting them will be much longer than 1MB blocks, maybe several minutes longer

However, if everyone is aiming for the smallest block possible, then most of the transactions will not be included. So far we have not run into this problem because the broadcasting speed is still relatively fast at current block size. But if one day it happens, a natural result is the bigger blocks will ask for more fee due to higher risk of being orphaned, how mathematically it is formulated is difficult to say without some real world cases. I guess it will be very similar to what OP described, above certain threshold, the fee will increase exponentially due to the risk of being orphaned also increase exponentially

While searching for block propagation data, I found out an article from Gavin. His Invertible Bloom Look-up Tables proposal will incentivize all the miners to include similar set of transactions to speed up the block propagation time (miners do not need to broadcast transactions that other peers already have in their memory pool, only block header and some extra transactions), but that seems to be a major change further down the road

https://gist.github.com/gavinandresen/e20c3b5a1d4b97f79ac2