Discouraging dust without hurting exotic uses of small valued coins

[d'aniel]

The idea is kind of simple, so apologies if it's already been proposed.

The UTXO set size can be controlled by weighting fees with the following function:

W(tx) = sum(w(txinval)) / sum(w(txoutval))

w(v) = 1 if v > v0
     w0 if v < v0

where v0 defines what is considered a "small" valued txout, and w0 is the extra weight given to small valued txins and txouts.

With v0 = 0 the sums reduce to number of txins and txouts.  But a finite v0 means outputs that cost more to spend than they are worth can be discouraged from being created.  For exotic uses of small valued outputs like colored coins, this essentially sets an extra fee for creating them, but not much extra for simply transfering them.  Recombining small txouts gives a fee "bonus".

For example, consider the tx where one small valued txout is created, and the rest of a single normal valued txin is sent as a fee to miners.  Then W(tx) = 1/w0, meaning a fee of w0 times more is required to be accepted on par with this tx, had the txout been of normal value.  This adds an extra cost to expand the UTXO set into practically unbounded territory.

Another example: one txin of normal value spent to fees, and a small valued txin spent to a single small valued output.  Then W(tx) = 1 + 1/w0 (~= 1 for large w0), i.e. not much extra fee is required because the UTXO set is not being expanded.

Finally consider the example of adding a small valued txin to a normal one, and spending this to a single normal valued txout.  Then W = 1 + w0, meaning the usual fee to spend a single normal valued txin to a single normal valued txout is attenuated by a factor of 1/(1 + w0) (~= 1/w0 for large w0) as a bonus for contracting the UTXO set size.

v0 should be set somewhere on the order of the minimum tx fee, and w0 will need to be adjusted by miners to whatever (minimum) value is required to prevent abuse of the UTXO set.

[misterbigg]

I don't see a way to distinguish between dust spam that originates from SatoshiDICE versus dust spam that appears that way because it is really the result of colored coin operations.

In fact one could argue that colored coins meet the definition of economically unviable transaction spam. If a colored coin represents an asset its easy to imagine that someone will receive the token representing the asset, where it will just sit for a long time. How do we distinguish this from the notification that SatoshiDICE sends for a gambling loss?

I liked the idea of colored coins originally but now that we see the problems that dust causes, perhaps the idea of using the block chain in novel but economically disadvantaged ways is harmful? Maybe colored coins belongs in an alt chain.

[d'aniel]

I don't see a way to distinguish between dust spam that originates from SatoshiDICE versus dust spam that appears that way because it is really the result of colored coin operations.

There isn't.  The idea is to set w0 high enough to discourage dust spam, but not so high that the creation of legitimate small valued coins is discouraged.  Notice that it's only their creation that incurs the higher fee; transferring them costs roughly the same as transferring normal valued coins.

In fact one could argue that colored coins meet the definition of economically unviable transaction spam.

One could argue this, but some miners may disagree.  Ultimately they're the "deciders".

Edit: A miner that doesn't like colored coins can simply set w0 prohibitively high.

[markm]

Why would it be unviable to, for example, have to spend a 0.0005 fee to transfer ownership of a pleasure cruiser or a Rolls Royce or even a family utility vehicle? Or even just a share in a company? (Unless the company fails, the cruiser sinks, the car is totalled...)

-MarkM-

[gmaxwell]

My crazy list of things mostly only suitable for altcoins has what I believe to be a thoroughly considered solution to half of the concern behind dust.   I think the issues with dust are two-fold: Txout can be created which a rational actor would never redeem even if they can,  and mining non-currency-related txouts has negative externality because nothing compensates the validators on the network for perpetually storing in fast storage an output (an infinite negative externality if it will never be redeemed, depending on how you model storage costs).

Here is a way some blockchain cryptocurrency could at least avoid the complete failure of creating txouts that are outright irrational to redeem:

* Transaction cost prepayment: One problem is that it's possible to create UTXO that are unprofitable to redeem.
** Instead make every output specify a max_size, which is the maximum marginal increase in size from redeeming this txout in a new transaction. (would need to be coded into addresses)
** max_size would be serialized as an unsigned variable length int minus whatever the smallest credible max_size is, (e.g. something like 40 for bitcoin)
*** This makes sure people aren't incentivized to write unspendable txn, perhaps a larger minimum max_size should be used, e.g. the size of the smallest secure TX_IN.
** Then for the 'effective_size' of a transaction is effective_size = MAX(real_size-sum_inputs(max_size),minimum_viable_txn_size) +  sum_outputs(max_size)
** In order to economical align cost the blocksize limit should be based on the effective_size rather than real_size.
** Unused effective_size is paid to the miner (E.g. in the coinbase txn)

This meets a bunch of not super obvious criteria, here is the list of all the things this particular construction was intended to not screw up on:

If miner's limits aren't based on this same metric miners would have no local economic incentive to apply this criteria instead of fees/kb (Better to take high fees and let some other sucker do good by encouraging output consolidation). If the cost of a transaction could be too close to zero then there are network fork attacks that arise from a miner making a block so big only half the network accepts it.  If adding more outputs would allow you to 'conserve' cost that would instead be lost to the MAX() then people would perversely incentivzed to add more outputs to their transaction.  If the number of bytes added per input or output is a constant it may not reflect the typical network activity. If it is too small there is not enough incentive to consume outputs (because the offset doesn't pay the consumption cost), if it is too large there is not enough incentive to consume outputs (size-sum_inputs*x goes negative). In a world with P2SH transactions the size of the scriptsig is unknowable by someone who only has a script hash. If the minimum max_size proposed here is too small people could create unspendable outputs cheaper than spendable ones by setting max_size small.

This doesn't work if ECDSA or network bandwidth are more important in miner's txn selection than the maximum block size, as they'd start to prefer txn with more fees per checksig or more fees per byte instead. Potentially making mininum_viable_size reflect these costs would help, but it also risk undoing the incentive here. Besides, if ECDSA or bandwidth dominates for _miners_ who are getting paid for their work then the network would have serious problems keeping anyone else validating.

While this scheme generally ensures every txout is valuable enough (in the form of offsetting the txn's size with its prepaid worth) to be redeemed it doesn't discourage non-currency usages that exploit the miner's negative externality in adding non-currency data to the chain.

That might be solvable via a mixture of strictly limiting outputs to be P2SH type (bounding their size), making zero value outputs unspendable (and thus instantly prunable)— both softforking changes that could be conceivably by done in Bitcoin— with UTXO expiration (which I think could not be introduced into Bitcoin except perhaps as an optional txn type). But I generally feel less confident around economic incentives.

The OP seems to assume that the 'exotic uses' are good. This isn't clear to me. There is a severe negative externality— All bitcoin users get value from having a strong inflation proof currency, the cost of which they pay in supporting validating nodes storing the utxo set, not all will derive value from any particular exotic use. To the extent that exotic uses are infrequent and paying for security they're doing people good... but the security payment from fees is one time and the utxo storage is potentially forever.  I had some wonky ideas about half the fees distributed among many miners, e.g. returning half the remaining fees to miners every α blocks 'forever' as a way to pay for burying as well as paying the storage cost under some model of decreasing storage cost over time... but it's defeated by the possibility of paying miners fees in other ways (e.g. zero fee txn, but one of the outputs pays a pool directly) and by the fact that its not only miners that have storage costs. ... in any case, the idea I presented here achieves the OPs goals. I don't see how it could be done in Bitcoin, but perhaps there is some similar alternative I'm missing.