Author: ZmnSCPxj 2021-10-07 10:01:53
Published on: 2021-10-07T10:01:53+00:00
In a discussion about reducing CPU cost, ZmnSCPxj suggests storing dust UTXOS in a separate Merkle tree or structure to avoid burdening the original set. While this technique decreases average CPU cost, it does not reduce worst-case CPU cost and can worsen the worst-case time if the secondary storage sacrifices speed for increased capacity per satoshi. It is important to keep in mind that attacks always target worst-case behavior. ZmnSCPxj draws a parallel to sorting algorithms, stating that quicksort's worst-case time complexity of O(n^2) makes it disrecommended for processing data from external sources. Instead, mergesort or similar algorithms are preferred, as they have an O(n log n) worst-case but generally worse average times than quicksort. Moving unlikely-to-be-referenced data to slower secondary storage that provides more storage per economic unit brings us closer to quicksort-like solutions to be avoided, as it is always the worst-case behavior that is targeted in attacks.
Updated on: 2023-06-15T00:47:16.191447+00:00