📅 Original date posted:2021-10-07
📝 Original message: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
ZmnSCPxj [ARCHIVE] /
npub1g5…3ms3l
2023-06-07 22:59:48
in reply to nevent1q…uha9
Author Public Key
npub1g5zswf6y48f7fy90jf3tlcuwdmjn8znhzaa4vkmtxaeskca8hpss23ms3lPublished at
2023-06-07 22:59:48Event JSON
{
"id": "7603d48f45917867c712ece21b8b963753a7129dc7faf78f0acd8b5613b38f67",
"pubkey": "4505072744a9d3e490af9262bfe38e6ee5338a77177b565b6b37730b63a7b861",
"created_at": 1686178788,
"kind": 1,
"tags": [
[
"e",
"253f5d7bc6975c77193fd9562401b6feaa0355ffaa6137785c44a341508d5545",
"",
"root"
],
[
"e",
"7f328cd074972376489bf89bc701ec3d0816b593cd76b083fabeb0f7b18b8793",
"",
"reply"
],
[
"p",
"ffbede6cc00fc0cadcbf4d9c17063fe865134ffd55e693dcfbd95bd883ecd42e"
]
],
"content": "📅 Original date posted:2021-10-07\n📝 Original message:Good morning shymaa\n\n\u003e If u allow me to discuss,,,\n\u003e I previously suggested storing dust UTXOS in a separate Merkle tree or strucutre in general if we are talking about the original set.\n\u003e 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. \n\u003e So, if dust UTXOS making a burden keep them in secondary storage, where in such cases u can verify then delete them.\n\nWhile 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).\n\nIt is helpful to remember that attacks will always target worst-case behavior.\nThis is why quicksort is strongly disrecommended for processing data coming from external sources, its worst-case time is O(n^2).\nAnd 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.\n\nMoving 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.\n\nRegards,\nZmnSCPxj",
"sig": "29e5abf59a1fc6f61d53bae8172a9faec0e21d0c13d59e8994cd93d87dad73ae823779a5e9dae92e4f8595aa3e871ee16b28e002636597480ba8d97ff6b8ee88"
}