Convenient transaction fees for Ethereum

Right now, transaction fee is the most disturbing issue for Dapps’ new users. No one wants to pay for basic Dapp functions by converting fiat to crypto and wasting crypto on any action. Free transactions are impossible for the Ethereum network because it will be immediately flooded by millions of free transactions.

I’d like to propose an optional new way of paying fees. Just imagine that users can “mine” transactions right before submitting. For example, generating on the client side about a several million of transactions to find one with a few leading zero bytes. Such transactions while being included in the block will produce amount of gas proportional to the number of leading zero bytes. Thus users will need to wait a few seconds to generate and submit transaction instead of paying. And the network will be safe from flood because actually users do pay for transactions indirectly with their CPU calculations though it looks like free.

Please let Vitalik Buterin know about this proposition, wanna know his opinion on this idea.