This is one reason I think we'll move to a direct-submission model with pay by the gigahash. There's really no way to know how much fees to pay today. Even if you try and guess based on prior experience, you might get unlucky and end up with a transaction stuck in limbo that nobody is working on.
The mining model I proposed a week or so ago in which you pay for work done rather than inclusion in a block solves this. If you are trying to pay too little to ever make it into a block the miner just rejects your tx with an error message (eg if you submit via HTTP POST you'd get "402 Payment Required"). If you pay 100 BTC then maybe the miner in question works on blocks for hours or days after your tx is successfully incorporated into the chain, just to ensure it's buried as deep as you paid for.
Firstly, there is already a way described by Satoshi to re-send a transaction with a higher fee. Secondly, I found a few problems with such a solution:
1. You said you pay per gigahash. Let's say you paid to MineCorp1 100 BTC which is defined by their rules to cater for 100 Thash. They start up their rig and mine for 100 Thash and find nothing. All the user's money went to waste.
2. MineCorp1 can mine for 100 Thash and find a block, but actually have some incentive not to put the user's transaction in there. Because no-one can prove who actually found a block, they can pretend they didn't find anything and include other, more valuable transactions into the block.
For end users who just want to buy something, they'd send free transactions .... they sit in the memory pool never confirming until the recipient wants to get some confidence they won't be reversed and pays the fee. To decide how much to pay in fees, you look at how many blocks you'd like it buried under, and how many gigahashes you'd need to pay for to achieve that in your chosen timeframe, then directly submit a fee-paying tx to the miner. They don't broadcast it. They work on it until they find a block and claim the fees.
3. The miner can just take the fee-paying tx and drop the user's transaction.
Broadcasting policies makes me nervous-- it is too easy to lie, and there might be some advantage to lying.
Couldn't clients infer all the information they need to know about what transactions/fees are being accepted by miners by keeping track of transactions in the memory pool and looking at the last 10,000-or-so generated blocks?
I agree, nice idea. Perhaps even a mixture between broadcasting pre-set policies and learning from the past could be used.
Hopefully there's not much incentive in lying.
Also, mind you, trying to "guess" a policy based on looking at the past might be more difficult. With a broadcast fee policy, you have an input (state of network, number of transactions waiting, etc.) and an algorithm (the fee policy), so you can predict the fee by applying this algorithm to this input. With looking at old blocks, you have an input and an output, but you have to guess the algorithm. Perhaps neural networks are good at this, but it's kinda hard to implement.
It's not so easy, but we'll face that problem sooner or later, so there'd better be a discussion for it :->