ACK -- the economics seem to make sense, but I am interested in comments from others

Here's a sample attack:
http://abe.liteco.in/tx/48878749fa2bbad375cc5aa8332aabb262c0a98259e85bbdb20f42ab4fa38966

Only cost him 1 LTC to bloat the blockchain by 50kb

This doesn't sound bad— although generally I'd like to start talking about how to get the net-change-to-the-open-txn-set included in the free/priority structure.

This is a dual attack in that it both adds static blockchain data but it also adds a ton of data which is probably never going to get redeemed, thus also burdening pruned nodes. This could be discouraged using as the size metric of something like max(size/2,2*size-size_of_txouts_reedemed). This would also discourage this sort of attack, where the out data size is much larger than the redeemed inputs.

Yes, once you get a lot of dust spam, select coins can take forever. For Litecoin, I had to implement a workaround for people to ignore the dustspam and make them not count towards coins that they own. It was a huge pain.

Sort of tangent— but wrt the select coins problem you might want to look at adding a post processing step: once you've prepared a txn with change and either a free txn with excess priority, or a with fee which isn't right at the boundary, then add in additional of your smallest inputs in order to get them out of your wallet (and out of pruned chains).

On further consideration: This will break the faucet, it will also remove an incentive to use sendmany.

As Bitcoin's value increases, you will probably need to reduce the value in which a output is considered spam. For Litecoin, less than 0.01 LTC is pretty much worthless. Maybe for Bitcoin, we should change it so that we add a fee for any output less than 0.0001 BTC.

This doesn't feel like the right fix to me.

Fixing the coin selection algorithm so it works quickly with wallets containing gazillions of tiny transactions is part of the solution. Something simple like "If there are more than X unspent outputs, don't use the fancy knapsack-problem-solver, just use the biggest-value unspent input(s) until you have enough to pay for the transaction+fee."

See https://gist.github.com/2961409 for the direction I think will work. With the right priority algorithm (and a minimum-to-be-relayed-included threshold) I don't think a dust spam fee is needed at all.

The coin selection fix does not fix the problem that someone can bloat the blockchain with only a small fee like this:
http://abe.liteco.in/tx/48878749fa2bbad375cc5aa8332aabb262c0a98259e85bbdb20f42ab4fa38966

Right, see the gist for the other part of what I think would be a better fix.

For a very-low-transaction-volume chain like LiteCoin, I think the right fix would involve miners specifying a small maximum block size (say 10K, enough space for 40 or so regular-sized transactions) and a high "forgo this amount of transaction fees" (so block space is dominated by transaction priority, not fee).

Automatic sanity-testing: PASSED, see http://jenkins.bluematt.me/pull-tester/9b11e48d5a03662333c11c046017f9394b127cd5 for binaries and test log.

Remember there is a previously reported attack involving one connection sending txs with tiny amounts to increase the GLOBAL limit, thus preventing the other connections from sending free transactions. It's necessary to review how this change may affect that attack, and if it can make it worse. I suggested using per-connection limits, and not a global limit.

It sounds like consensus is against merging this specific fix at this time.

It sounds good merging this specific fix at this time, after some attacks.

One only learns from mistakes

@felipelalli +1

Whatever my opinion is worth... +1.

Consensus has changed. It's back on the table. This could potentially resolve the backlog we have in transactions

Txout should be compared not to CENT, which is very hardcoded value, but to nBaseFee imho. Like this

if (txout.nValue < nBaseFee) nMinFee += nBaseFee;

This is certainly not back on the table at all, imho. There were very good reasons this pull request was closed out in 2012. I would encourage people to re-read the remarks (including those of @gavinandresen as shown here) and @gmaxwell's.

It's a bad idea to take a nuclear option with respect to fees and reject the opportunity that can be presented from analyzing microgiving potential. Odd also that people keep referring to this as "dust spam" when they could be reframing the language and the issue... the current "dust problem" (which I would argue should actually be called a "giving opportunity") is an opportunity to re-examine transactions, transforming them into bursts of microgiving. Do not foreclose on the an opportunity to re-examine and re-envision transactions and thus change the system you are using.

In closing, I would also recommend you see issue #6402 as an example (of how this could be handled better, perhaps) and also some of the more recent comments on #6201 (including one that I've entered).