1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
|
Return-Path: <ZmnSCPxj@protonmail.com>
Received: from smtp3.osuosl.org (smtp3.osuosl.org [140.211.166.136])
by lists.linuxfoundation.org (Postfix) with ESMTP id 1582EC000E
for <bitcoin-dev@lists.linuxfoundation.org>;
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 <bitcoin-dev@lists.linuxfoundation.org>;
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 <bitcoin-dev@lists.linuxfoundation.org>;
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 <bitcoin-dev@lists.linuxfoundation.org>;
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 <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
X-BeenThere: bitcoin-dev@lists.linuxfoundation.org
X-Mailman-Version: 2.1.15
Precedence: list
List-Id: Bitcoin Protocol Discussion <bitcoin-dev.lists.linuxfoundation.org>
List-Unsubscribe: <https://lists.linuxfoundation.org/mailman/options/bitcoin-dev>,
<mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=unsubscribe>
List-Archive: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/>
List-Post: <mailto:bitcoin-dev@lists.linuxfoundation.org>
List-Help: <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=help>
List-Subscribe: <https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev>,
<mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=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
|
