[bitcoin-dev] [Lightning-dev] Removing the Dust Limit

[ZmnSCPxj]

Good morning shymaa

> If u allow me to discuss,,,
> I previously suggested storing dust UTXOS in a separate Merkle tree or strucutre in general if we are talking about the original set.
> I'm a kind of person who doesn't like to throw any thing; if it's not needed now keep it in the basement for example. 
> So, if dust UTXOS making a burden keep them in secondary storage, where in such cases u can verify then delete them.

While this technique helps reduce *average* CPU cost, it does not reduce *worst-case* CPU cost (and if the secondary storage trades off to gain increased capacity per satoshi by sacrificing speed, it can worse the worst-case time).

It is helpful to remember that attacks will always target worst-case behavior.
This is why quicksort is strongly disrecommended for processing data coming from external sources, its worst-case time is O(n^2).
And we should switch to algorithms like mergesort or similar whose average times are generally worse than quicksort but have the major advantage of keeping an O(n log n) worst-case.

Moving data we think is unlikely to be referenced to secondary storage (presumably in a construction that is slower but gets more storage per economic unit) moves us closer to quicksort than mergesort, and we should avoid quicksort-like solutions as it is always the worst-case behavior that is targeted in attacks.

Regards,
ZmnSCPxj