Date: Thu, 28 Oct 2021 01:04:10 +0000
To: Gloria Zhao <gloriajzhao@gmail.com>,
 Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
From: ZmnSCPxj <ZmnSCPxj@protonmail.com>
Reply-To: ZmnSCPxj <ZmnSCPxj@protonmail.com>
Message-ID: <DS-9LyYKokVu_2m2j7ZxpVY3CmOLF_efYCGftH4pqHF1Wk2mFBQNl_ILazvKXJvTiVSQ3b_v5vg29DRFQs301wwNwfEgKUCPo3MOq_VIPm0=@protonmail.com>
In-Reply-To: <CAFXO6=Jk0MAqQ6u5JCrpC3eMv=bF3DT6wH6Y60zb_b-beU4mcg@mail.gmail.com>
References: <CAM1a7P04apCwwmqNp4VLRam5_uk59tVRWv74UVD_g0-DUGNghw@mail.gmail.com>
 <CAFXO6=Jk0MAqQ6u5JCrpC3eMv=bF3DT6wH6Y60zb_b-beU4mcg@mail.gmail.com>
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: quoted-printable
Cc: lisa neigut <niftynei@gmail.com>
Subject: Re: [bitcoin-dev] death to the mempool, long live the mempool
Precedence: list

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