Good start, I have some questions, though:
Thank you, your help is invaluable, the discussion really helps to sharp my idea.
Well, I hope you'll remember this when you've become a millionaire
How does this coupon system work exactly? Is there a lottery, is there a reward-per-coupon-system? Redeeming the PoW as a classic PoW, with the miners being essentially pool operators and the senders contributing to the pool won't work.
It will be directly a reward per coupon system.
Let me define the Proof-of-work that is needed for interacting with the smart contracts. I'm talking about something that would take an average computer or an smart-phone 15 - 30seconds to calculate. It's not as nearly as intense as the miner's proof-of-work. It would probably be a CPU-friendly (GPU-unfriendly) algorithm, something like what $VRM has implemented.
The data they need to do the Proof-of-work onto will have reference to the last known head of the main chain, and the last known head of the smart-contract chain. There will be a threshold (~10 blocks?). By doing so, we make sure that the proof-of-work have an expiration date. So even if someone have "unlimited" CPU power, they would be able to calculate online a limited proof-of-work.
I still don't really see how this might play out in practice, maybe an example would help?
Scenario: A miner mines a block and includes 10 TXs with one PoW-coupon each. What is happening now?
Is there a simple "number of coupons per block" system, which forces miners to include a minimum number of TXs in a block to get the full block reward?
Is there a fixed payout per coupon and he would have earned more by including 11 TXs? So, would that mean that more or less coins will be created according to the number of TXs made?
Is there a payout pool and every X blocks, it gets divided between the miners of the last X blocks, according to the number of coupons they earned in that time?
In the two latter cases, you'll have a problem, which is, that not every PoW-coupon will be worth the same. TXs will be of different sizes and miners will have an incentive to include the smallest possible TXs, because they can get more coupons per block this way. Possible solutions are:
A maximum number of coupons per block.
Make it a "coupon per XX bytes TX size" system. Bigger TXs have to provide multiple coupons. This is still exploitable, because of thresholds. If you have a 0.5 kb TX and a 0.9 kb TX and both are one coupon, miners will try to generate as many 0.5 kb TXs as possible and will not include bigger TXs.
Yes, I think an expiration date is needed to prevent attacks. We will see what number makes the most sense, but I am somewhat afraid that there won't be a perfect magic number. Even if the algo is CPU-friendly, the system could still be attacked by renting a big amount of hashing power. You'd probably need some type of difficulty adjustment system for the PoW coupons, but when under atack, this might keep weaker devices (older smartphones) from being able to do PoW.
In either case, this will lead to the effect that every block will be full. If nothing else, miners will fill them themselves, just to not miss out on the rewards. This isn't necessarily a bad thing, just something to keep in mind.
I think those steps are good enough to encourage PoW from "real" users and discourage miners from filling the blocks.
I think miners will include as many "real" TXs as possible, because they don't have to do the work. But at the same time, if they are unable to fill up a block with as many TXs as possible, they will miss out on coupons. So they will fill the empty space with TXs they generated themselves. I don't think this is a bad thing per se, it might even be easier to make this the only type of block reward.