jonatack has quit [Read error: Connection reset by peer]
jonatack has joined #bitcoin-core-dev
brunoerg has joined #bitcoin-core-dev
brunoerg has quit [Ping timeout: 264 seconds]
TheRec has joined #bitcoin-core-dev
TheRec has quit [Changing host]
TheRec has joined #bitcoin-core-dev
brunoerg has joined #bitcoin-core-dev
brunoerg has quit [Ping timeout: 256 seconds]
brunoerg has joined #bitcoin-core-dev
brunoerg has quit [Ping timeout: 268 seconds]
ghost43 has quit [Remote host closed the connection]
ghost43 has joined #bitcoin-core-dev
brunoerg has joined #bitcoin-core-dev
brunoerg has quit [Ping timeout: 256 seconds]
brunoerg has joined #bitcoin-core-dev
jonatack has quit [Ping timeout: 256 seconds]
jonatack has joined #bitcoin-core-dev
<bitcoin-git>
[bitcoin] hebasto opened pull request #28919: build: Fix regression in "ARMv8 CRC32 intrinsics" test (master...231120-crc-arm64) https://github.com/bitcoin/bitcoin/pull/28919
salvatoshi__ has quit [Remote host closed the connection]
salvatoshi has joined #bitcoin-core-dev
benwestgate has joined #bitcoin-core-dev
kevkevin has joined #bitcoin-core-dev
brunoerg has quit [Remote host closed the connection]
brunoerg has joined #bitcoin-core-dev
brunoerg has quit [Ping timeout: 255 seconds]
brunoerg has joined #bitcoin-core-dev
brunoerg has quit [Ping timeout: 256 seconds]
puchka has joined #bitcoin-core-dev
bitdex has quit [Quit: = ""]
brunoerg has joined #bitcoin-core-dev
<bitcoin-git>
[bitcoin] furszy opened pull request #28920: wallet: birth time update during tx scanning (master...2023_wallet_birhtime_update) https://github.com/bitcoin/bitcoin/pull/28920
brunoerg has quit [Ping timeout: 255 seconds]
<sdaftuar>
sjors: thanks for your comments on cluster mempool. regarding RBF and carveout i think it might be easier to discuss here
Sjors[m] has joined #bitcoin-core-dev
<Sjors[m]>
sdaftuar: or even park them in a tracking issue
<sdaftuar>
since i opened the draft pr, sipa and i have been doing a lot more thinking about rbf, and the rules i have proposed in the PR are going to change
<Sjors[m]>
Do you have a tl&dr of those changes?
<sdaftuar>
it turns out that even with the rules that I initially proposed, it's possible that the mempool might not get "strictly better" as a result of an RBF that satisfied those tests.
<sdaftuar>
so the tldr is that I'm going to write up what it means for the mempool to be "strictly better", and then test for that condition directly when evaluating a potential replacement.
preimage has joined #bitcoin-core-dev
<sdaftuar>
the quick summary of what "strictly better" means is: if you look at the mempool chunks sorted in descending feerate order, you want the new mempool (after a replacement happens) to contain the old one.
<sdaftuar>
the implementation of this is still a work in progress, but i'll update the PR once I finish it. it shouldn't change the algorithmic complexity of what we're doing.
<Sjors[m]>
How do you mean "contain the old one"?
martinus has joined #bitcoin-core-dev
<sdaftuar>
imagine drawing a graph where you have accumulated fee on the y-axis, and cumulative size on the x-axis.
<sipa>
Sjors[m]: you draw a diagram with the cumulative size and cumulative fee after every chunk in (the combination of) all the clusters
<sipa>
connect those with straight lines
<sipa>
the diagram of the new mempool has to be nowhere below that of the old mempool, and at least in some places above it
<Sjors[m]>
So it has be a steeper hill and at every point at least as high as before?
martinus has quit [Client Quit]
<sdaftuar>
yeah that's basically it
<sipa>
not necessarily; just at every point at least as high
martinus_ has joined #bitcoin-core-dev
<sdaftuar>
the idea is that for every size block that could be mined, you collect more fee in the new mempool than the old one.
<sdaftuar>
(ignoring tail effects at the end of a block)
<sipa>
the steepness of segments of the diagram is the feerate of the individual chunks; it's not necessary that all the feerates are higher - it's possible that the first chunk just takes you high enough so that further chunks don't need to be very steep anymore to always stay above
<Sjors[m]>
Ok, I'll wait for that update.
<Sjors[m]>
Regarding CPFP carveout, I think that's orthogonal to the above?
<sdaftuar>
yes, separate topic
<Sjors[m]>
My thinking is that we either need really large clusters, or allow eviction inside a cluster
<Sjors[m]>
Otherwise afaik you're always at risk of pinning by maxing out a cluster.
<sdaftuar>
the problem with allowing eviction within a cluster is that there's not a good way to do so that will avoid pinning problems in all adversarial scenarios
<sipa>
some forms of pinning are inevitable regardless, because of a conflict between incentive-compatibility and dos protection
<sdaftuar>
and so if your concern is that there's an adversarial scenario where your counterparty fills up a cluster to mess with you, that they can do that differently even if we allow eviction
<sdaftuar>
basically because any form of eviction that i can conceive of would (to be DoS-resistant) still require that the total fee in the mempool must increase
<sdaftuar>
and so therefore if you fill up a cluster with large transactions, evicting them will be expensive
<instagibbs>
ephemeral anchors is the current constrained answer, that's how you get non-DoSy sibling eviction(via explicit RBF)
<sdaftuar>
if we don't care about that, and just want to argue that allowing any form of same-cluster-eviction is valuable so that you always have some way to broadcast a transaction (by putting a sufficiently high fee on it), then i could agree with that.
<Sjors[m]>
So this is a universal RBF rule 3?
<instagibbs>
sdaftuar it makes everything basically fullrbf ;)
<instagibbs>
well, in lots of scenarios
<sdaftuar>
no, not transactions that are not in full clusters?
<sdaftuar>
well you could argue it i guess
<Sjors[m]>
instagibbs: that could also make sense, but does that imply we have to wait with (wide) cluster mempool deployment until ephemaral anchors work?
<instagibbs>
attacker makes it full to replace it
<instagibbs>
"attacker"
<Sjors[m]>
Or does nobody use the CPFP carveout anyway?
<sdaftuar>
you could also argue that everythign is full rbf anyway due to mempool eviction
<sdaftuar>
\shrug
<instagibbs>
psh :)
<instagibbs>
Sjors[m] no, ephemeral anchors works today, it simplifies the problem to clusters of size 2
<sdaftuar>
Sjors[m]: the problem with carveout is that it exists to deal with descendant limits, and descendant counts are a property that is local to a particular transaction. cluster size is a concept that is not specific to one transaction, so there's no way to allow a carveout to bypass that limit in any meaningful way
<Sjors[m]>
instagibbs: "ephemeral anchors works today" ?? I thought it required package relay. Or is that deployed already?
<sdaftuar>
our thought is to first deploy some form of v3 transaction policy, so that people relying on carveout could migrate to that first, and then we can get rid of carveout and deploy cluster mempool afterward
<instagibbs>
Sjors[m] v3 shrinks the packages to size 2, ephemeral anchors allows dust outputs and provides a type of sibling eviction
<Sjors[m]>
Oh
<instagibbs>
Sjors[m] I meant it doesn't require clsuter mempool sorry
<Sjors[m]>
Right, so if we drop the CPFP carveout before v3 is ready, that might be a problem
<Sjors[m]>
But the other around, v3 doesn't have to wait for cluster mempool.
<sdaftuar>
Sjors[m]: yeah right now i'm assuming that cluster mempool is going to be delayed for v3
<instagibbs>
practically speaking, the only users of cpfp carevout are LN implementations, so getting uptake there is key. Good news is it's a huge simplification of their state machines, security, and fee savings, so it's about getting going
<Sjors[m]>
instagibbs: but it does suggest having one or two major releases in between the moment v3 is ready before clusters can be (at large scale) deployed, since LN folks need time.
<instagibbs>
(not trying to go off topic) depends on uptake speed, most important imo is getting implementations using it done and deployed, as soon as parent-child package relay is considered deployed
<Sjors[m]>
The other question I raised in the PR is we can drop RBF rule 5. But maybe we should wait for the new "better than before" mempool commits to be pushed.
<instagibbs>
that's not this project's burden clearly, just noting
<sdaftuar>
ah rule 5. i have a few thoughts on that
<instagibbs>
you need to constrain how many re-linearizations you do
<Sjors[m]>
I haven't seen a clear illustration of the worst case abuse that rule prevents.
<sdaftuar>
do you mean in the new cluster mempool model, or legacy model?
<sdaftuar>
i wrote up an explanation on the mailing list of why that rule exists currently
<sdaftuar>
in the new model, the concern is around avoiding too many re-linearizations, as instagibbs mentioned. every cluster that is changed by a replacement needs to be re-linearized, which is a costly operation
<sdaftuar>
the basic tradeoff here is that the more clusters you have that might be linearized at once, then the smaller clusters can be
<Sjors[m]>
sdaftuar: in the new cluster model
<sdaftuar>
so in theory, you could imagine that replacing a bunch of transactions that are in clusters which would disappear entirely may be ok, because those don't contribute linearization costs
<sdaftuar>
Sjors[m]: right
brunoerg has joined #bitcoin-core-dev
<sdaftuar>
however i haven't exactly figured out what limits make sense when we switch from the RBF heuristic i originally proposed to the new one i described before, where we actually measure if the new mempool is "strictly better" in order to process a replacement.
<sdaftuar>
roughly speaking, it's the same issue, but i think the constants get bigger when we analyze the computational work being performed
<sdaftuar>
Sjors[m]: yep that one
<sdaftuar>
so, tldr: more to come on exactly how we can engineer that, and what the new limit or rule would be
<Sjors[m]>
Whether it's useful to drop RBF rule 5 also depends on how big a cluster size is realistic. If the limit is ~100 anyway, then there's not much benefit other than just fewer rules.
<sdaftuar>
no that's not true, because a single transaction can conflict with multiple clusters.
<sdaftuar>
so regardless of what the cluster size limit is, it's useful to think about how many in-mempool transactions are being conflicted
martinus_ is now known as martinus
<sdaftuar>
for instance a transaction might have 500 inputs -- that could conflict with 500 different unrelated transactions
martinus has quit [Quit: Konversation terminated!]
martinus has joined #bitcoin-core-dev
<Sjors[m]>
What I mean is: the RBF rule 5 limit makes it possible to pin something using just 100 transactions. If we dropped that limit, but if the cluster limit is 100, then you can still pin someone with just 100 transactions. Even though it would be a different kind of pinning attack.
brunoerg has quit [Ping timeout: 276 seconds]
<instagibbs>
I told sdaftuar that counting directly conflicts would be better, then a txn creator can "just not do that"
<instagibbs>
it's in the PR I'm sure you saw
<sdaftuar>
Sjors[m]: not sure i follow -- the cluster size limit is applied after the conflicting transactinos are removed.
<sdaftuar>
oh and yes, we should be able to just count direct conflicts i think.
<sdaftuar>
or do better, and just count number-of-relinearized-clusters or something
<instagibbs>
either works 👍
<Sjors[m]>
sdaftuar: put another way, if the goal is to get rid of all pinning attacks that can be done with 100 transactions, you would need to drop/increase the RBF rule 5 limit AND increase the maximum cluster size. If we can't do the latter for performance reasons, then it's not very useful worry about the former.
<sdaftuar>
ok i think i see your broader point. the biggest RBF pinning vector that will remain is the one that we have today, which is that you have to pay a greater total fee than what is being evicted.
bugs_ has joined #bitcoin-core-dev
<sdaftuar>
i think maximum-cluster-size is not exactly an anti-RBF pinning vector? it seems like more of a vector to prevent spending some related unconfirmed output...
<sdaftuar>
but yes, pinning vectors remain.
<Sjors[m]>
It's a thorny problem.
<Sjors[m]>
Last question, sipa are you planning any major changes to the linearize code?
<sdaftuar>
sipa has discovered some stuff that i think will likely result in some additional changes (my best guess)
<Sjors[m]>
It would be good to have some prose at the top of cluster_linearize.h to explain what's going on and where to start reading.
<sipa>
Sjors[m]: i think my approach will be to create a python reimplementation of the same algorithm(s)
<sipa>
so that it can abstract away the complexity that's due to data structures, and just explain it all as operations on feerates and sets
<Sjors[m]>
Sounds good.
<sipa>
Sjors[m]: i don't expect big changes to the algorithms compared to what's implemented there, and perhaps some optimizations that don't contribute much may be dropped to reduce review complexity
<sipa>
i do have a nice O(n^2) linearization post-processing algorithm that just improves it, which can be run after normal linearization
<sipa>
that's not implemented there
<Sjors[m]>
One thing that's useful to clarify is which linearization is perfect and which is "merely" pretty good.
<Sjors[m]>
At least my understanding was that for small clusters you can find the best result?
<sipa>
yeah up to 10-15 transactions
<Sjors[m]>
And is there some metric of goodness?
<sdaftuar>
yes, the mempool fee-size diagram we discussed before
<sdaftuar>
you can imagine applying that a single cluster, and comparing two cluster linearizations by their fee-size diagrams.
<Sjors[m]>
I mean, is there a metric to determine if you found the optimum or (stastitically) how far away you are
<sipa>
but it's only a partial ordering - it's possible to have two linearizations for which in some places one's diagram is on top, and in other places the other one is; such linearizations are incomparable
<sipa>
Sjors[m]: nope, i don't even have a way to quickly tell if a linearization is optimal or not
<sipa>
apart from recomputing it
<sdaftuar>
Sjors[m]: so, we don't have a proof that there exists an optimal ordering always.
<sdaftuar>
Sjors[m]: however, we believe the optimal ordering is the one you get by doing the naive thing: at every step, select the topologically valid subset of remaining transactions with highest feerate
<sipa>
also, i also just came up with an algorithm that can given two incomparable linearizations, finds a third linearization that's strictly better than both
<Sjors[m]>
Are there any papers that explain the general problem?
<sipa>
i have no clue what keywords to even look for
<sdaftuar>
Sjors[m]: research links would be welcome!
brunoerg has joined #bitcoin-core-dev
brunoerg has quit [Ping timeout: 264 seconds]
brunoerg has joined #bitcoin-core-dev
brunoerg has quit [Ping timeout: 255 seconds]
micha_ has joined #bitcoin-core-dev
brunoerg has joined #bitcoin-core-dev
salvatoshi has quit [Ping timeout: 256 seconds]
kabaum has quit [Ping timeout: 264 seconds]
brunoerg has quit [Ping timeout: 255 seconds]
benwestgate has quit [Quit: Leaving.]
kabaum has joined #bitcoin-core-dev
brunoerg has joined #bitcoin-core-dev
brunoerg has quit [Ping timeout: 256 seconds]
Talkless has joined #bitcoin-core-dev
szkl has joined #bitcoin-core-dev
brunoerg has joined #bitcoin-core-dev
abubakarsadiq has quit [Quit: Connection closed for inactivity]
dviola has joined #bitcoin-core-dev
Guest77 has joined #bitcoin-core-dev
Guest77 has quit [Client Quit]
pablomartin has joined #bitcoin-core-dev
Talkless has quit [Remote host closed the connection]
Guest14 has quit [Quit: Client closed]
cryptapus_ has joined #bitcoin-core-dev
cryptapus has quit [Ping timeout: 256 seconds]
mudsip has joined #bitcoin-core-dev
micha_ has quit [Quit: Connection closed for inactivity]
micha_ has joined #bitcoin-core-dev
cryptapus_ has quit [Ping timeout: 255 seconds]
mudsip has quit []
jon_atack has joined #bitcoin-core-dev
jonatack has quit [Ping timeout: 256 seconds]
mudsip has joined #bitcoin-core-dev
mudsip has quit [Client Quit]
cryptapus_ has joined #bitcoin-core-dev
cryptapus has joined #bitcoin-core-dev
cryptapus_ has quit [Ping timeout: 255 seconds]
brunoerg has quit [Remote host closed the connection]
brunoerg has joined #bitcoin-core-dev
brunoerg has quit [Remote host closed the connection]
brunoerg has joined #bitcoin-core-dev
brunoerg has quit [Ping timeout: 255 seconds]
brunoerg has joined #bitcoin-core-dev
abubakarsadiq has joined #bitcoin-core-dev
brunoerg has quit [Ping timeout: 255 seconds]
pablomartin has quit [Ping timeout: 256 seconds]
cryptapus has quit [Read error: Connection reset by peer]