Chain dust mitigation: Demurrage based Chain Vacuuming

[libcoin]

The amount of "dust" in the block chain is getting large and it is growing all the time. Currently 11% of unspent tx outputs (UTXO) are of 1Satoshi (0.00000001BTC), 32% is less than 0.0001BTC and 60% is less than 0.001BTC. (Thanks to Jan for digging out these numbers!)

This means that a huge part of the block chain is used for essentially nothing - e.g. the sum of the 11% is worth roughly 2 US cents !

The main source for these 1 Satoshi payouts is Sahtoshi Dice. And nothing wrong with that, however, we should work on ensuring that too many too small payments will not kill the size of the blockchain in the end - further, they are essentially too small to be included in other transaction as the added fee will often make it more expensive to remove them. Hence, there is no incentive to get rid of them.

I have an idea for a possible mitigation of this problem - introduction of demurrage - not as in it normal meaning as a percentage over time (see: http://en.wikipedia.org/wiki/Demurrage_(currency) btw, this has also been tried in freicoin), but as a mean to recycle pennies over time. The proposal is simple - UTXOs age out if not re-transacted - the smaller the coin the faster the aging:
1-99 Satoshi: lives for 210 blocks
100-9999 Satoshi: lives for 2100 blocks
10000-999999 Satoshi: lives for 21000 blocks
1000000-99999999 Satoshi: lives for 210000 blocks

Only amounts above 1BTC lives forever - (or we could even impose aging on those too..)

The aged coins are simply included in the block mining reward, creating another incentive for miners. Further, if we include all coins in this recycle scheme coins will never be lost forever.

This scheme will impose some lifetimes also on e.g. colored coins (hence you need to use a certain amount to borrow space on the blockchain for the time needed, or simply transact them).

If you like this I would be happy to write it into a BIP.

Thoughts ?

[justusranvier]

People are adopting Bitcoin precisely because it doesn't include bullshit like arbitrary inflation and demurrage. If you don't like this switch to one of those alternate chains that nobody wants to use instead of trying to change Bitcoin into the opposite of what it is.

[DeathAndTaxes]

I don't think you will get a change like that into Bitcoin at this point.  I would stay away from the "D" word.  It is only going to draw emotional responses.  I don't see a problem with ultra tiny transactions being scrubbed over time but it will be a hard fork and the odds of that happening on anything other than critical fixes is roughly 0%.  It may be useful to use in a new coins.  I would make it a lot less complicated than your mult-tiered system though.  Anything below X becomes can be expired and included in the next block after it is Y blocks old.

Maybe a better system would to have limited the number of digits.  Requiring increasing digits to require a super majority of miners approval.   Start with something like 3 digits and let it expand up to 10 digits based on need*.  Everything internally would be stored as 10 digit "satoshi" integer values.  


*21 million BTC @ 10 digit precision stored as an integer would be max value of  210,000,000,000,000,000 which is less than the max value of 64bit unsigned int  (18,446,744,073,709,600,000). .  If the total number of coins was made to be 18 million instead of 21M one could get 12 bits of precision in the same 64bit unsigned int  18,000,000,000,000,000,000

[Herbert]

I also don't see a chance that demurrage will be part of bitcoin protocol.

But could this not be handled somehow on clientside?

Ideas:
-> When generating transactions try to use more of the small outpoints, if possible exact so no new change is needed
This will still have the problem of increased transaction fees, but maybe some tradeoff can be found.

-> Don't generate new change addresses when the change is small, instead "fill up" existing addresses
Privacy risk, so should only be done when the user understands/requests it.

[DannyHamilton]

-> When generating transactions try to use more of the small outpoints, if possible exact so no new change is needed
This will still have the problem of increased transaction fees, but maybe some tradeoff can be found.

I'm not certain, but I thought that, in order to increase anonymity, the current client intentionally attempts to use up enough outputs to require change.  This way it is difficult to tell when looking at a transaction which is the change and which is the payment.

-> Don't generate new change addresses when the change is small, instead "fill up" existing addresses

This won't help.  You'll still have a small output associated with the existing address instead of at the change address.  The outputs associated with an address aren't all combined into a single output.  They are all separate.  You'd have to create a transaction that sends all the outputs associated with that address to get them combined into a single output.

[casascius]

Although I haven't really filled in all the gaps, I believe this is possible, if we ever get around to implementing a "meta-tree" proposal as has been discussed elsewhere in the forums.

Briefly, a "meta tree" is a sorted tree structure of all unspent outputs, the hash of which becomes a required part of the coinbase transaction.  From block to block, nodes simply keep the tree updated, and discard spent transactions.  My proposal idea assumes the meta tree methodology is understood by the reader.

The idea I have would be to actually have two meta trees: one with the "most" important unspent outputs, and ones with the "least".  Bit dust would fall into the "least".  Actually, any transaction output that reaches an age proportional to its size would be a candidate to fall into the "least important" tree (example: 1 satoshi may belong there after just 1 confirmation, but an idle 1 BTC, such as a Casascius Coin, will belong there only after sitting idle for, say, 4 years).

Nodes joining the network have the option of maintaining only the "most important" tree, or both trees.

The "most important" tree would be greatly size limited (maybe a few hundred MB at the most).  Someone with only the "most important" tree will only see an incoming transaction that spends coins on the tree.

If someone with only the "most important" tree receives coins from the "least important" tree, they will still arrive, just much later.  Nodes without the least important tree will learn about the transaction when it gets mined into a block and then sees several confirmations.  So, people can still spend their bitdust, they'll just need to wait 6 confirmations for the transaction to even be seen let alone confirmed by the mass of people who have simply downloaded the minimum data set needed to be part of the network.

[DeathAndTaxes]

This risk in doing that is that honest nodes lacking the unimportant tree won't be able to unimportant txs.  This can allow an attacker to flood the network with bogus transactions which honest but uninformed nodes will still forward.  One countermeasure could be to require a proof of work on unimportant transactions.  Nodes lacking both trees couldn't validate the tx but could validate the proof of work.  Thus there is now a cost for attackers in attempting to flood the network.

A side note:  even if all nodes kept all tx (as they do now) pruning out the spam along with spent tx into a separate table, db, index may improve performance.  Essentially the ultraprune method but include "low probability" outputs in the spent set.

So a node receives a tx.  It does a high speed lookup in its active but unspent tx set (which may be cachable in memory).  If there is a match it validates, adds to the memory pool, and forwards.   If there is no match it looks in the spent & improbable set.  Most transactions are performed quickly.  The occasion bulk spent of low value outputs may require a second slower lookup but it is offset by the gains in performance on the majority of transactions.

[casascius]

This might be bold and unorthodox and I would welcome being shot down on this, but I would venture to suggest that it would be OK for nodes with only the "most important" tree to not even bother relaying transactions that might belong to the "least important" tree.  Almost as though the "most important" network were some sort of elite sub-network.

The reason for this is that the prospect of having a difficult time quickly spending an extremely low priority coin is not too much to make a user suffer.  It's not going to make the network suffer any, nor is it going to split the network up.  It will simply make blasting such transactions out an uphill battle.  On the other hand, this is the internet: if such a transaction can even be sent to half dozen nodes known to be willing to receive it, and it makes it into a block, it will propagate throughout the whole network without discrimination.

If someone wants to spend their low priority coin, they'll either have to download the low priority transaction set, or use a service set up for that (their coin will almost certainly become "high priority" again once it moves).  Such a client or such a service will already be in a position to make sure the transaction makes it to miners somehow for eventual inclusion in a block.

It would be like, in real world terms, trying to buy groceries using an old clock radio from the 80's as payment.  The old clock radio isn't worthless, but you've got to find a buyer first, and being unwilling to help with that is a reasonable policy position for a grocery store to take.

[DeathAndTaxes]

As long as the protocol supports a method for node to identify their capabilities and allows a node to find a "full set" node to relay to it really isn't a problem.   

Currently they can't which likely would mean a lot of confusion.  i.e. I create a valid tx, submit it, and it is rejected by all my peers.  The tx never goes anywhere.  My nodes keeps trying to send it forever and the recipient never even knows it exists.

[casascius]

As long as the protocol supports a method for node to identify their capabilities and allows a node to find a "full set" node to relay to it really isn't a problem.  

Currently they can't which likely would mean a lot of confusion.  i.e. I create a valid tx, submit it, and it is rejected by all my peers.  The tx never goes anywhere.  My nodes keeps trying to send it forever and the recipient never even knows it exists.

I'm convinced that "the protocol" has a ton of evolving to do, and is a relatively easily replaced part of the bitcoin infrastructure.   Of course, the format of the data structures like blocks and transactions cannot be changed independently, but the part of the protocol that defines how handshaking works, how peer finding works, how to decide what messages to relay, how to communicate node capabilities, what assumptions can be made about what information each peer has... I believe could be 100% replaced with a new protocol on a different port or via a different transport, if someone else came up with a better mousetrap that covered all the critical points.  I assume it will happen one day, just not very soon.

[J-Norm]

This cannot be done because it is in violation of the common contract we are all involved in that we call the bitcoin protocol. We have to live with a design that allows these to accumulate.

I have never understood why we could not just take the top 200k blocks and replace them with a "key frame" of sorts and go from there. A very public checksum of this keyframe can be built into clients to prevent revisionism.

If a single satashi is never used again then it never adds to the size of the blockchain again right? Even if you combine the 11% of outputs that add up to 2 cents you will still have all of those outputs in the chain, they will just be spend.

[casascius]

This cannot be done because it is in violation of the common contract we are all involved in that we call the bitcoin protocol. We have to live with a design that allows these to accumulate.

I have never understood why we could not just take the top 200k blocks and replace them with a "key frame" of sorts and go from there. A very public checksum of this keyframe can be built into clients to prevent revisionism.

Where did I sign?

If I spin up a Bitcoin node and it exchanges information via pigeon dropping USB sticks rather than TCP 8333, am I in breach of contract?

OK, silliness aside.  I actually think you're on the right track.  Using video terminology, the meta tree idea of keeping track of only the unspent state of the network is probably already what you have in mind, with key frames being maintained by the network and propagated just to bring new nodes up to speed, and then the solved blocks themselves being the "I frames" let's say.  And in the coinbase of each block, there would be the hash of the currently rendered "frame" with the block itself applied, so that the nodes can be assured that the whole network is watching the same movie.

The reason it would be arranged into a sorted tree, is that one can prove the existence or non-existence of a particular leaf on the tree, just by providing the hashes that go from the leaf node to the root (in the case we're proving something exists), or else providing all of the surrounding leaf nodes, everything between them up to their common ancestor, and then all the way to the root (in the case we're proving something doesn't exist), sort of like proving there are no "Forzoops" in the phone book by providing the contiguous set of page(s) including both "Forrester" and "Foster".  More on the meta-tree idea can be found with the forum search.

[J-Norm]

Where did I sign?

The contract is the bitcoin protocol, you sign when you send money. Any transaction that involves taking away other people's money no matter how small will be rejected by clients due to not meeting the agreed upon contract the clients enforce.

Since it is unlikely you will ever get 51%+ members of the communal contract to agree to this and start doing it at the same time it is very unlikely the blockchain will ever include removal of funds from an address without a signature from its private key.

[casascius]

Where did I sign?

The contract is the bitcoin protocol, you sign when you send money. Any transaction that involves taking away other people's money no matter how small will be rejected by clients due to not meeting the agreed upon contract the clients enforce.

Since it is unlikely you will ever get 51%+ members of the communal contract to agree to this and start doing it at the same time it is very unlikely the blockchain will ever include removal of funds from an address without a signature from its private key.

I'm not sure that's how it works.  Actually, I'm pretty sure it's not.  The only "signing" that happens when I send money is the calculation of a number that proves to the rest of the network that the putative owner of some coins consents to a transaction to reassign their ownership.

I need 51% consent if I want to alter the definition of a valid block or transaction, but if I want to alter how I pass blocks and transactions between another node (presumably that also speaks the "satoshi" way to "satoshi" nodes, so we're not an island), I don't need anybody's consent.  It's something totally different.

If tomorrow I declare that I have produced a unicorn protocol that does what the Satoshi protocol does plus something else that everyone instantly finds attractive, and I make sure I provide a way to bridge nodes using my protocol with everyone else on the Satoshi-only network, the community of those who choose to use the protocol will need no consent from those who do not adopt it, no matter their relative sizes.  None of us ever consented or withheld consent from Electrum / Stratum, and yet it functions just like it should.

It's possible that we may be conflating two different definitions for what constitutes the "bitcoin protocol".  To the extent you mean the format of data structures like blocks and transactions, you're 100% right.  But to the extent it includes the pattern and style of communication conducted across TCP port 8333, this is exempt from needing 51%'s permission.

[J-Norm]

Yes, I was referrring only to the transaction auditing rules. The transport mechanism can be switched out without issue.

I agree that the way transactions are crafted can change to reduce dust production, clients can even refuse to relay dust.

But the dust that already exists can never be moved without the private keys for them, not without violating the transaction auditing rules we have all agreed to.

[gmaxwell]

I need 51% consent if I want to alter the definition of a valid block or transaction,

No, for that you need almost everyone's 'consent'.  A majority can not make the invalid valid.   [A tangent on your point about freely being able to change node to node communication; thats spot on]

[grau]

Although I haven't really filled in all the gaps, I believe this is possible, if we ever get around to implementing a "meta-tree" proposal as has been discussed elsewhere in the forums.

I do love the idea of POW validated UTXO set, that however would remain "dusty".

The spending clients should prefer to aggregate inputs to address this.

[casascius]

What I suggested in a nutshell is that the dust can be stored only by nodes that want to store it (let's call this a lower storage tier) and allow users the option to download the unspent transaction set not including the dust. This would result in a smaller community of nodes that could validate transactions containing dust - and of course all miners would have to store the dust as well. Nodes that do not store the dust would find out about dust transactions by seeing them mined into blocks that continue to be confirmed. Such a node would take a far longer time to see a dust transaction as they would not be listening for the unconfirmed transaction (they have no way to tell it apart from a totally bogus/invalid transaction).

[grau]

I think that that only miner, merchants and web wallet services will be storing the chain soon.

[cunicula]

What I suggested in a nutshell is that the dust can be stored only by nodes that want to store it (let's call this a lower storage tier) and allow users the option to download the unspent transaction set not including the dust. This would result in a smaller community of nodes that could validate transactions containing dust - and of course all miners would have to store the dust as well. Nodes that do not store the dust would find out about dust transactions by seeing them mined into blocks that continue to be confirmed. Such a node would take a far longer time to see a dust transaction as they would not be listening for the unconfirmed transaction (they have no way to tell it apart from a totally bogus/invalid transaction).

What you suggest is interesting.

Question 1: Why would anyone maintain the dust tree in this case? The only incentive I can see is to earn mining fees from dust. But if it is truly dust (like the 11% of blockchain data containing $0.02 USD of value), then there are no fees to earn.

Question 2: If dust is "dusted off and used", does this require the other nodes to download the dust's entire history again? Or alternatively to trust the nodes that validated the dust?

Question 3: Blocks can be mined which contain no dust. If most miners restrict themselves to this type of block, isn't it best for other miners to do so also? (since a dust block would appear to take a long time to validate and thus risk creating an orphan. Also even if all the miners deal in dust, won't dust blocks take much longer to propagate through the network, leading to the same effect?)



It seems to me that this is a sneaky way of introducing dust demurrage via economic incentives. i.e. if you make it cheap to sort dust records from valuable records, and no party profits from maintaining dust records, then we end up only maintaining valuable records. Just like if we changed the protocol rules.

I like it.

Say we mop up all the new dust created after each block arrival (introducing new stuff will turn some old stuff into dust). Is there a quick algorithm for doing this? Or would it require a resource intensive search and thus maintenance of a dust index?