Well, everybody, I'm Shinobi Technical Editor at Bitcoin
Magazine, joined by Peter Woola of Chain Code Labs.
So we are here to discuss your latest obsession over the last
few years. Cluster Manpool.
Yep, I this is definitely not not the first time we've talked
about this. I I hope it's among the last
times I need to talk about it now that the changes have
actually been merged in Bitcoin Core with plan to be in the 31
dot O release later this year. I can imagine that's a familiar
feeling with you at this point. It's been a long project.
I mean, I've, I've had many big projects over over the past few
years, but I mean, it's still a big one that it's good to have
off my plate. So you you and Suha staff tour
kind of like conceptualized this I think 3 years ago now roughly.
Yeah, I think it was a discussion we had in the office
here in February 2023 where, you know, we're thinking about all
the problems that the current MAMPOL has.
And in fact I think this was inspired by a talk Suez gave to
us here internally just talking about the problems the MAMPOL
has. And among them, it's not the
only one, but I think it it sort of a nice demonstration of of
how things are broken. And that's really the difference
between how in the current mining algorithm we use one
ordering and when deciding what transactions to remove from the
mempu when it fills up and you don't have enough memory
anymore. We we use a different ordering.
And this was necessitated by the design of the code at the time,
but it, it was still surprising. So in a bit more detail when,
when jumping ahead, the the real problem is that you, you would
hope that the mining algorithm picks the transaction in some
order going from, you know, higher fee rate to lower fee
rate order, but respecting topology.
Because of course we can in Mampol have dependent
transactions where you have, you know, I pay you in an
unconfirmed transaction and then you use those coins and then
spend them further to, to pay for something.
So now we have a child transaction and there's logic in
there so that if if your transaction pays a higher fee
rate, these two will be considered together and we'll
have that that's the child pays for parents concept.
But so all of that block mining algorithm in Bitcoin Core today
and as it has been since 2015 has taken all of this into
account. So it roughly comes up with a
good ordering, not perfect, we'll get into that later, but
fairly good going from higher fee rate to lower fee rate with
parents always before their children.
And you would hope that when memory runs out, you start
evicting transactions that would be considered last by this
order. The very last, the first thing
you want to evict is the last thing you would want to mine
that this makes sense. And that's, that's true in most
cases, but you can construct pathological examples of
constellations of transactions within a member where this is
not the case. And in, in very extreme cases,
in fact, it, it appeared to be possible.
She also discovered this, that the very first thing you evict
is the last thing is the first thing you would, you would mine,
which is obviously bonkers. That's not what we want to throw
away. And I, I I I don't say that this
is the only problem, or even the most important one.
It just is a nice way of showing that what we really want inside
is a a well defined single ordering on all transactions if.
You want predictability. You want to know this is going
to always happen in these conditions.
Right. And and the the the the the the
real problem. Why?
Why are these orderings difference?
Well, the the reason is, is roughly that in order to decide
what you'd want to mine last, you basically need to run the
mining algorithm for like a mem pool minus epsilon sized block
and then see what you didn't mine.
And well, if it that that that would work.
But sadly this is computationally infeasible with
all the transactions in there. So and and So what?
What happens if you're faced with a problem?
Well, we need a fixed ordering, but it is too computationally
expensive to do. Well, what if we could pre
compute things? What if instead of just running
the mining algorithm at the time a book template is built?
And that's only what a miner would do.
We we in fact do it ahead of time whenever a change is made
to to the memple, we we in fact keep a total ordering on all
transactions in the memple at all times.
And if we have this pre computed well then block building is
easy. You pick from the front eviction
is evict from the from the end. But there there are many more
examples of parts of the Bitcoin Core codebase that in one way or
another try to assess with a heuristic that's often in
incorrect and often inconsistent.
Is this transaction better than this one?
Say there is a flood of transaction that come into your
node as we've seen a year or two ago, or there have been such
floods. There's a rate limiting process
that will prevent that that flood from being propagated to
all your peers and having them over be overwhelmed too.
So you need to make a decision which transactions are you going
to send first? Well, obviously the better one
you want to send first, but it doesn't know that because we
can't certainly at that time don't have computational need of
time to go determine what things are.
But there are even more examples like for fee rate estimation.
It would be nice if fee rate estimation could take CPFP into
account. It can't do that because it
would need this information of adjusted goodness or effective
fee rate as we call it, of transactions.
And so all these problems we realized in fact that there's a
whole bunch of ways that we're trying to compare quality of
transactions with each other inside the code base in many
different ways, all heuristically and all done
independently. Another one is, is when fee
bumping transactions in the wallets that there's, there's
similar logic there and we really need to come up with a, a
way to pre compute this total ordering.
And if we have that and all these problems become so much
simpler. The oh, the biggest one of all,
replaced by fee. If you have a transaction that
comes in that replaces another one, you need to know whether
taking this new transaction and evicting all the things that
conflicts with is actually an improvement.
There's a bit 125 rules which are so sort of followed still,
but they are heuristics and they are imperfect in many ways.
There, there are ways today that you you can replace a
transaction with one that is just unambiguously worse and
gets accepted, and similarly many ways that you can have an
unambiguously better transaction come in and will reject it for
arbitrary reasons. Yeah.
Just difference between like absolute fee and fee rates
looking at size and how that's computed.
So that is one that that's orthogonal so that the
replacement rules, if we're going into that sort of boiled
down into two categories, 1 is incentive compatibility in the
sense of does taking this transaction make things better
for the manpool, the minor in terms of fee income.
And there's another set of rules which are about denial of
service protection. So we, we want when a
transaction replaces another one, we sort of charge the new
transaction a fee for the cost of having relayed the old
transaction, which will now not as we expected won't end up in a
block anymore. And so that there is an absolute
fee increase requirements that comes from there.
Yeah, kind of just looking at bandwidth.
Cost. Yes, this is just to prevent,
you know, enabling avenues for an attacker to use the Bitcoin
peer-to-peer network as a free relay mechanism.
You're effectively at least imposing as much cost on them as
relaying nodes is going to pay. So it's it's not like the nodes
aren't being compensated, but they're still bearing the cost.
Right. Ideally, we, you know, we we'd,
we'd have the the transaction relayers receive the income that
for relaying transactions, but that that really does.
Figure that out, Let me know we can finally replace Bitcoin.
I do believe there, there there was a very early research paper
called the red balloons paper that tried to do this.
But it's, it's not, I don't, I don't recall how it worked.
And in any case, it's it's just not a practical problem because
or, or rather, even if you have a solution for it, it's not a
desirable outcome because it just means you will try to
bypass the relay network that charges you a fee to relay and
send it to minors directly, which is the very opposite of
what we want to achieve. Yep.
So replaced by fee rules, you have the incentive compatibility
ones and you have the denial of service ones.
We're not touching the denial of service protection rules, but
the incentive compatibility ones today are wrong in both ways.
Like they will accept things that are worse and they will
reject many things that are better.
And with sort of a framework of reasoning properly about how
good transactions are with respect to each other.
This involves a bit more than just ordering them.
Like sort of come boils down to drawing a diagram of how the fee
increases with the size and comparing those diagrams.
But but still the cluster member framework in the end is is a
solution to all all these problems at the same time.
And so all right, we we want to impose a total ordering that we
can pre compute, but sadly already plain like the we, we
can't just run an imple sized version of the block building
algorithm to determine the full ordering of everything at all
times. And sadly, as things stand
today, it it's in theory possible to relay a single
transaction and completely change the optimal ordering of
every transaction in the MPL, like completely reverse it.
For example, we, we have an example like you have this chain
of transactions sideways like parent, child, parent child,
parents, child. And the ordering is like you
first mind this, then this, then this.
And now you add one very high fee rate transaction to the end.
And suddenly it's this, this, this, this, this.
So that's a problem because that means we need to deal with the
case of the single transaction is being relayed to you, and you
need to recompute the ordering of everything in your MAMPOL,
however big it is, maybe hundreds of megabytes.
And the solution to this is, well, what if we can just
restrict how many transactions can be affected by any given new
transaction coming in? And that's where the term
cluster comes from. So we partition, the idea is to
partition the manpool into groups of related transactions.
And this includes parents, children, ancestors,
descendants, but also descendants of your ancestors
and their ancestors and their descendants and and and so
forth. So anything that can be reached
or any 2 transactions that that are related by an arbitrary
combination of parent of child, of steps, they are considered to
be in the same. It's just like.
A A family tree? Yeah.
Like visually? Yeah, like there's even the
slightest relation between them that you, you, you think of them
as the same. So it's it's your parents, your
grandparents, your children, your grandchildren, but also
your uncles, your nieces, your cousins, you're everything.
And the idea is simple instead. So the the previous MAMPOL had
some resource limitation rules. The default was that we would
impose, and other things at most 25 ancestors including the
transactions itself, and at most 25 descendants, including the
transaction itself. And this is related directly to
the computational cost of the mining algorithm and the
eviction algorithm which needed to operate on these sets of
ancestors and set of descendants.
I won't go into the details here, but anyway.
So with this new approach, we're replacing them those, those
rules go away completely and they are replaced instead with a
rule that clusters can be at most 64 transactions.
The number is a bit bigger. So it, it does mean that you can
build longer chains of transactions than 25.
But of course it's it, it now works both ways.
And so it's it's not, not. It's.
It's not directionally bound, it's just total size.
And your family can be at most 64 transactions rather than just
your ancestors or just your descendants.
Based we've we've done analysis on historical weight of the
member, it doesn't appear that many transactions would be
affected by this new rule. And of course, it will possibly
enable new use cases that weren't possible before.
And so with that, our solution is really partition them and
pull into these clusters of at most 64.
We impose a policy rule. You can't go above that.
If you try to go above, we'll just reject the transaction.
And whenever such a cluster is changed, a new transaction is
added to it. Some part of it is mined,
there's a reorg that conflict, some part out, there's a
replacement that that that conflicts with some parts.
Any change that's made to a cluster, we, we run effectively
the block mining algorithm again, but just on that little
cluster of at most 64 transactions.
And because it's so small, this is fast.
And it turns out that really all you need is this ordering within
sets of related transaction, the the the overall ordering of them
and pull this sort of a very simple merge sort of all your
clusters and and this we can do at runtime whenever needed.
But the the hard part, the computationally hard part is now
restricted to just these groups of 64 transactions.
Whenever a change is made, we just rerun A mining algorithm on
it. And it's not a mining algorithm
anymore. It's really just an algorithm
for deciding the order of the transactions within it.
Yeah. And of course what once we had
that and we now actually do have that there.
There is an obvious follow up question because, as I mentioned
earlier, the existing logic for deciding transactions at block
building time is suboptimal in many ways.
This isn't necessarily a problem, but it's nice if we can
do better and given that we're only going to be running this
algorithm anymore on groups of 64 transactions, we may have the
ability to do something far better than than what is done
today. As an example, so today you have
child pays for parent, which works.
So you can have a single child that that pays for a parent and
they will be aggregated and seen as a group, which is what you
want. But what doesn't work is
children pays for parent or children pay for parent grammar.
So if you have two children that both have a higher fee rate than
a parent, it only the the the one with the most effects will
be considered alone rather than the combination of the two both
bumping the parents together. I wouldn't say it's a problem
because. It's a big blind spot.
Yeah, it it's just I, I don't think it matters much in
practice today because of course people aren't relying on use
cases that need children pay for parent because it just doesn't
work. But so this has has been my
focus for I guess most of the past two years on and off some
other things too, but is is try to come up with, you know, good
algorithms for deciding. I have a group of at most 64
transactions. What's the best ordering to to
to mind them in? Hey everyone, it's Shinobi and
I'm here in front of the Chicago Fed to talk to you about the
core issue of Bitcoin Magazine. The last few years have been a
bit of a communication breakdown between developers and people
using Bitcoin. Bitcoin exists to be an
alternative. To this institution.
But to do that, it needs people to actively maintain it.
If you actually want to hear from developers themselves, how
they approach their work and what they choose to work on, go
to bitcoinmagazine.com and get yourself a copy of The Core
Issue. So it's pretty much like.
You have this. Whole abstract architecture and
new way of ordering things and managing the man pool, and now
it's just, well, now what's the math of how we're going to
manage? Yeah, it's just a drop in
replacement, right. When we start this idea of
cluster man pool, the idea was just to run the existing block
mining algorithm on these now groups of 64 transactions ahead
of time as opposed to do it on the whole manpool at blog
building time. But given that we'll only be
running in on groups of 64, maybe we can just do something
better or specialize it. And in in.
In practice we can basically find the optimal ordering
always, which is neat. I mean, that's a little more
than neat. I think that's the very good
thing long term for the network to have like an optimal like
most profitable algorithm like that to be open like anyone has
access. To it anymore exactly because it
before optimal. Our goal would be to be
sufficient to cover all the things that people do on the
network. Practically, if all that people
do is single transaction CPFP bumping, then all you need is an
algorithm that can deal well with that.
But what if some use whose case, who, who, who knows what crazy,
interesting or dumb things people come up with in the
future that, you know, creates a strong economic incentive to pay
for weird things in transactions?
Well, if it's optimal, it's optimal.
Like there, there, there's nothing people can come up with
as long as it's restricted to 64 transactions and it's, it's
still subject to the denial of service protection rules and so
on. But you know, in in terms of
topologies of related transaction, it doesn't matter
what people come up with, we'll always order it the right way.
Yeah. So it it's it's essentially
future proof so that you can continue optimizing it based on
like new second layers built new network behaviors or meta
protocols or whatever people. You can come up with whatever
use case and the OR the behavior of nodes just becomes well if
it's better, I'll take it, if it's not better, I won't take
it. And it it can discern better in
US in any topology of of up to 64 transactions.
I mean that. That sounds like a huge deal,
especially for layer twos and just kind of giving more
predictability or certainty as far as what people are building
on top of. Especially for like reactive
layer twos like Lightning or Arc where you might have to respond
to another party's transactions and you need that guarantee.
You need to know like if I submit this transaction like is
this going to out compete something or replace something.
It, it, it's true, but it, I wouldn't say it, it becomes more
predictable in because it's predictable in the sense that
it, it's at a very high level, super easy to give you what you
need to do. You, you need to make it worth
whatever you're doing needs to result in increasing fee income.
And if you can do that, it will take it.
But it it how that's decided. That's sort of a a very high
level black box kind of thing where where before we had the
big 125 rules which were not perfect and deviated from in in
several ways, but they gave you a list of conditions like if you
satisfy this rule, this rule, this rule, this rule, the
replacement will go through. That's no longer the case.
The rule is it needs to be better figure it out.
I don't think this is an issue in practice because people
really, if you're talking about groups of transactions where you
or your protocol lightning or whatever layer to have, you
know, control over all related transactions, that there is no
issue Because you can of course, just run the algorithm on it and
then see if it will be accepted. As soon as you interact with,
you know, potentially grieving parties that might try to attach
to your group of transaction. Like I, I make an unconfirmed
output to a third party. Now they can attach arbitrary
other things to that. And what I might need to do to
bump a fee here becomes now dependent on what they're doing.
So it it it does become, I think, harder to reason about,
but it's but it's a far cleaner and it actually aligns with, you
know, the incentive compatibility in the network
where where before we had arbitrary rules that weren't
actually always the best ones. And we shouldn't expect that
going forward, those rules would be ones that miners keep
following while this they hopefully will.
I mean, I feel like, you know, this, at least from my
perspective, it feels kind of like the latest point and like a
progression of kind of cleaning up or removing incompatible
things in the man pool. Like the original first scene
safe rule. And then when we first
implemented RBF, it was opt in. We had to flag it and then but
miners were still mining on flag transactions anyway.
And it's kind of been the, at least the entire time I've been
in this space, people have been slowly cleaning up those things
that people just did. Do you remember priority?
I don't know how long. Ago where?
You had the. The percentage of the block set
aside for zero fee transactions if they were old enough.
If they were, yeah, if they had sufficiently high bitcoins, they
destroyed per byte, which I just made sense in in very early days
because that was a useful prioritization mechanism.
But of course I mean that that's just not maintainable in in.
Yeah. Well, once the once there was
real value and people competing for block space, no rational
minor would would run that, Yeah.
Exactly. So yeah, there, there.
There's been a long sequence of steps in that direction, I
think. I mean, it's a necessary thing
in the long term, like if if we're going to use a system that
depends on the incentives of these profit motivated players,
like we should be aligned with their incentives or how do you
think this is going to work? Exactly.
You know, I think you gave a super stellar breakdown and I
think most people watching might actually walk away understanding
it. So I want to thank you a lot for
that, Peter. Yes, Peter.
And I hope you guys all learned something.
By uh.