From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from smtp3.osuosl.org (smtp3.osuosl.org [IPv6:2605:bc80:3010::136]) by lists.linuxfoundation.org (Postfix) with ESMTP id 0EE6BC000D for ; Thu, 7 Oct 2021 10:02:03 +0000 (UTC) Received: from localhost (localhost [127.0.0.1]) by smtp3.osuosl.org (Postfix) with ESMTP id D164F60754 for ; Thu, 7 Oct 2021 10:02:02 +0000 (UTC) X-Virus-Scanned: amavisd-new at osuosl.org X-Spam-Flag: NO X-Spam-Score: -0.199 X-Spam-Level: X-Spam-Status: No, score=-0.199 tagged_above=-999 required=5 tests=[BAYES_05=-0.5, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1, FREEMAIL_FROM=0.001, FROM_LOCAL_NOVOWEL=0.5, RCVD_IN_MSPIKE_H4=0.001, RCVD_IN_MSPIKE_WL=0.001, SPF_HELO_PASS=-0.001, SPF_PASS=-0.001] autolearn=ham autolearn_force=no Authentication-Results: smtp3.osuosl.org (amavisd-new); dkim=pass (1024-bit key) header.d=protonmail.com Received: from smtp3.osuosl.org ([127.0.0.1]) by localhost (smtp3.osuosl.org [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id iwmeLtl3Ygd1 for ; Thu, 7 Oct 2021 10:02:01 +0000 (UTC) X-Greylist: domain auto-whitelisted by SQLgrey-1.8.0 Received: from mail-40140.protonmail.ch (mail-40140.protonmail.ch [185.70.40.140]) by smtp3.osuosl.org (Postfix) with ESMTPS id 89C276071A for ; Thu, 7 Oct 2021 10:02:01 +0000 (UTC) Date: Thu, 07 Oct 2021 10:01:53 +0000 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=protonmail.com; s=protonmail; t=1633600919; bh=6pZf+PlNzcSQUB8OXYFTfQ+fo1y1d6EFUczDo9bkHcU=; h=Date:To:From:Cc:Reply-To:Subject:In-Reply-To:References:From; b=Ib8Xe+x+IB7irI9DnRezIALhyTlBA9RToEn5p1prT2FavY6W5n0uG4OLKvzW3PNn7 +XVkAi16vdsdnuEokN83SVYnPp1z/WxaSj+uCSBL5yF2DVvuxpjpKiNiRkyjecirxx 3z6dpEgp8q+3wAAFx+HFaHJ9kfnAHNf67qhWRdA4= To: shymaa arafat From: ZmnSCPxj Reply-To: ZmnSCPxj Message-ID: In-Reply-To: References: <20210808215101.wuaidu5ww63ajx6h@ganymede> MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: quoted-printable Cc: Bitcoin Protocol Discussion Subject: Re: [bitcoin-dev] [Lightning-dev] Removing the Dust Limit X-BeenThere: bitcoin-dev@lists.linuxfoundation.org X-Mailman-Version: 2.1.15 Precedence: list List-Id: Bitcoin Protocol Discussion List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Thu, 07 Oct 2021 10:02:03 -0000 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