From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from smtp3.osuosl.org (smtp3.osuosl.org [140.211.166.136]) by lists.linuxfoundation.org (Postfix) with ESMTP id 1582EC000E for ; Thu, 28 Oct 2021 01:04:20 +0000 (UTC) Received: from localhost (localhost [127.0.0.1]) by smtp3.osuosl.org (Postfix) with ESMTP id 04E2C60651 for ; Thu, 28 Oct 2021 01:04:20 +0000 (UTC) X-Virus-Scanned: amavisd-new at osuosl.org X-Spam-Flag: NO X-Spam-Score: -1.602 X-Spam-Level: X-Spam-Status: No, score=-1.602 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, 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_H2=-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 hlTodL1QfTqY for ; Thu, 28 Oct 2021 01:04:16 +0000 (UTC) X-Greylist: domain auto-whitelisted by SQLgrey-1.8.0 Received: from mail-40138.protonmail.ch (mail-40138.protonmail.ch [185.70.40.138]) by smtp3.osuosl.org (Postfix) with ESMTPS id 2E9BD60093 for ; Thu, 28 Oct 2021 01:04:16 +0000 (UTC) Date: Thu, 28 Oct 2021 01:04:10 +0000 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=protonmail.com; s=protonmail; t=1635383053; bh=ZsT6yYOfF8reHv3p9lM+gBscfhtP8dtE2HXeCWCWtYg=; h=Date:To:From:Cc:Reply-To:Subject:In-Reply-To:References:From; b=pOFn6A31+nY/VFqhsSR6lAtGSc80uUPotbi8fxUJMnwIk2ual+flnrBNzQgMillDs bLY1m12n+pUtPJPKbL429BJbTIbeorj8PVkvc/Sd4ffmKuERiQdU2h8snTwgAS8qna 5oD289BKapK9dSxrzy/GlGRlilhrGUMlwjZWcb3k= To: Gloria Zhao , Bitcoin Protocol Discussion From: ZmnSCPxj Reply-To: ZmnSCPxj Message-ID: In-Reply-To: References: MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: quoted-printable Cc: lisa neigut Subject: Re: [bitcoin-dev] death to the mempool, long live the mempool 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, 28 Oct 2021 01:04:20 -0000 Good morning Gloria, et al, > > Removing the mempool would... naturally resolve all current issues inhe= rent in package relay and rbf rules. > > Removing the mempool does not help with this. How does a miner decide whe= ther a conflicting transaction is an economically-advantageous replacement = or a DoS attack? How do you submit your CPFP if the parent is below the mem= pool minimum feerate? Do they already have a different relay/mempool implem= entation handling all of these problems but don't aren't sharing it with th= e rest of the community? This seems an important key point: *even if* miners maintain some kind of "= accept any transaction!!!" endpoint, the miner still wants to have *some* p= olicy on how to evict transactions from its pool of transactions, for the s= imple reason that *everyone* has limited resources, even miners. Perhaps the issue is that eviction is done *immediately*, i.e. if a node re= ceives a transaction below some feerate treshhold, it immediately drops the= transaction. What if instead we did the eviction lazily? Suppose we used something like a garbage collector. Unconfirmed transactions are objects that point to other objects (i.e. the = input of a transaction "points to" another object). "Primitive" objects are UTXOs of *confirmed* transactions, i.e. the UTXO se= t at the block tip. Then, a GC algorithm would start at some roots and then terminate when it r= eaches primitive objects. I describe here an algorithm based on semispace GC, but the GC algorithm sp= ace is well-studied and other algorithms may also be devised (in particular= , spam is likely to match quite well with "infant mortality" concept in GC,= i.e. "most objects die young", so some kind of nursery / generational GC m= ay work better against spam in practice). A semispace GC has two "spaces" for memory. One is the "from-space" and the other is the "to-space". During normal operation, the "from-space" is used and the "to-space" is emp= ty. (Note that we can implement a "space" as a table (`std::map`) from txid to = transaction, and avoid having to *actually* copy the transaction data; the = important thing is having two spaces) There is a maximum size that from-space and to-space can be. As we receive transactions, we allocate them on the from-space. Once the from-space is filled, we stop operations and perform a GC cycle. We select "roots" by ordering all transactions in the from-space, from high= est-feerate to lowest-feerate (figure out some way to handle ties later, ma= ybe put a timestamp or monotonic counter?). Starting with the highest-feerate tx, we trace all the transactions they re= fer to, recursively, copying them from from-space to to-space. We stop once the to-space is filled more than half. At this point, we drop all transactions in the from-space that are not alre= ady in to-space, and then delete the from-space. Then we promote the to-space as the from-space, and continue our merry way,= allocating more transactions. (Nothing prevents doing this on disk rather than in memory; xref Eric Vosku= il) Note that the algorithm operates on individual transactions, not packages o= f transactions. The algorithm is vulnerable to spam where the spammer creates several large= low-feerate transactions, then anchors them all using a tiny high-feerate = transaction (a "tall" attack). It is also vulnerable to spam where the spammer creates several high-feerat= e transactions spending the same UTXO (a "wide" attack), thus preventing an= yone else from getting any transactions into the mempool. Against these exploit, we can mitigate by *first* moving objects to a small= er "packagespace" instead of directly on the to-space. When tracing a new root, we first move the transactions that are not alread= y in to-space to the packagespace, then measure the aggregate fee divided b= y the aggregate memory usage. If this is below, say, half the feerate of the root transaction, then we dr= op the packagespace (put it back into from-space) and move on to the next r= oot. This protects against "tall" attacks. To protect against "wide" attacks, if the packagespace consumes a TXO that = is already consumed in the to-space, we also drop the packagespace (i.e. on= ly retain the highest-feerate version in a "wide" attack). Once the above checks pass, we merge the packagespace into the to-space. This algorithm means that we do not need package relay; instead, we just se= nd transactions in the correct order (parents first, then children), and if= the receiver does not need to do a GC in-between, then everything ends up = in the mempool. If the child transaction is high-fee enough to be a root transaction, and p= ays enough that its feerate dominates in the packagespace result, then the = entire sequence will remain in the mempool. The algorithm allows for conflicting transactions to be retained in the mem= pool temporarily, until the next GC triggers (at which point conflicting tr= ansactions are resolved by whoever is higher-feerate). This is helpful since a conflicting transaction may be what ends up getting= confirmed in a block from a miner whose mempool did not contain the "best"= feerate transaction. WDYT? Regards, ZmnSCPxj