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 _______________________________________________ bitcoin-dev mailing list bitcoin-dev@lists.linuxfoundation.org https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
