Some points I'd like to add to the discussion:

**Fees are always paid by the recipient** (even though it might seem the other way around)

The only party directly interested in the success of the transfer is the recipient. The sender is only willing to pay a fee on behalf of the recipient. The sender gains nothing from coins disappearing from his wallet, however the recipient needs the transfer to be successful in order to take definitive custody of the coins transferred.

Even in cases where it seems like the sender pays the fee voluntarily he's still only acting on behalf of the recipient. So if I send money to my grandma and she says "don't include a fee," but I do, it's because I'm acting altruistically in the interest of my grandma.

Therefore it provides a clearer picture to look at transaction costs from the perspective of the recipient.

**Cost function**Gavin's formula captures the normal situation perfectly. But [mike] correctly points out that there is another cost, currently hidden (because it is very, very near zero at the moment).

So extending Gavin's formula with the risks, we get:

cost = f(txn, B, P) + txamount * (1-P) + txamount * P

_{A}P

_{A} ... Probability of a successful attempt by s.b. to overtake the block chain for the purpose of rejecting/delaying at least this transaction.

Or, in other words, the total cost of a transaction is

- the fee paid, plus

- the risk of it not being included because the fee is too low, plus

- the risk of it not being included because the block chain has been overtaken.

That means that if f() is continuous we can actually find an optimal P for any given txn and B. (In the formulas I use myself, I actually use t for time, however B is Bitcoin's

*representation* of time, so it's just a different unit essentially.)

At the moment P

_{A} is very, very small. This is because seigniorage provides an added incentive to mine, leading to much, much higher hash rates.

As minting is phased out, the hashing rate will come down, and P

_{A} will rise. At some point it will start to be noticeable either as a risk by observant users or because an attack has actually taken place.

In terms of the P2P client... For now it seems reasonable to assume that P

_{A} is for all intents and purposes zero. And if we can indeed figure out a good approximation function for f(), we should be able to calculate the recommended fee based solely on txn and B. Note that an optimal P will likely be fairly close to 1, because we're counting the tx not getting confirmed at the requested time as a total loss (which is an exaggeration). But it allows us to ask the user "How fast do you want this to get confirmed?" and it will almost always get confirmed at least by that time.

In terms of future solutions... I expect insurance providers to crop up very soon. Even with P

_{A} = 0, they can still provide a useful service by offering t < 10min, something the P2P client can't offer. As soon as P

_{A} starts rising that will simply become another selling point for them.

*Disclaimer: I actually suck at math, so feel free to point out any errors in my formulas/reasoning.*