Date: Thu, 07 Oct 2021 10:01:53 +0000
To: shymaa arafat <shymaa.arafat@gmail.com>
From: ZmnSCPxj <ZmnSCPxj@protonmail.com>
Reply-To: ZmnSCPxj <ZmnSCPxj@protonmail.com>
Message-ID: <ZKZ4RR6uAv0mG8yFQyRkWDTFQ7JnsGVfLQcMTmsc5ui7MTJXuzMkVk5YQTniPuc4F_KRhn7BEZZHEK60IZYZYU9A1r-tbmfPTnIs0pOd7oU=@protonmail.com>
In-Reply-To: <CAM98U8nSOQ9HpdRLBdkcFAdToW=z7_EhnYisMb7F46ExmJkT-w@mail.gmail.com>
References: <CAD5xwhjFBjvkMKev_6HFRuRGcZUi7WjO5d963GNXWN4n-06Pqg@mail.gmail.com>
 <20210808215101.wuaidu5ww63ajx6h@ganymede>
 <MkPutJpff5rqUxXFQrEyHZl6Iz0DfrJU_-BQD-y0El65GQFnj7igVfmWU79fPCtiFztUYl4ofzrqeaN0HFMB45YPErY9rYY7_h1XkuTMfvc=@wuille.net>
 <CAJowKgKt=yYdNOYYNsWh7FJ2EH7rz0bd2EjUjmyA=cA6k5cvUQ@mail.gmail.com>
 <BtaljKLqpe75GB6pHEPQMF6_L-hBaE0ZCBGaXrUfnHRYeEbCqFWZ12DaMRm5jEADceL3uPfCiL-WU9MOZJ_m54Zi3Pzu0vSFN3nQvuSKvBM=@protonmail.com>
 <CAM98U8nSOQ9HpdRLBdkcFAdToW=z7_EhnYisMb7F46ExmJkT-w@mail.gmail.com>
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: quoted-printable
Cc: Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Subject: Re: [bitcoin-dev] [Lightning-dev] Removing the Dust Limit
Precedence: list

Good morning shymaa

> If u allow me to discuss,,,
> I previously suggested storing dust UTXOS in a separate Merkle tree or st=
rucutre 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 nee=
ded now keep it in the basement for example.=C2=A0
> So, if dust UTXOS making a burden keep them in secondary storage, where i=
n such cases u can verify then delete them.

While this technique helps reduce *average* CPU cost, it does not reduce *w=
orst-case* CPU cost (and if the secondary storage trades off to gain increa=
sed 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 behavi=
or.
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 ke=
eping an O(n log n) worst-case.

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

Regards,
ZmnSCPxj