Date: Mon, 29 Nov 2021 14:27:23 +0000
To: Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
From: darosior <darosior@protonmail.com>
Reply-To: darosior <darosior@protonmail.com>
Message-ID: <hBx6OYA5Mv9C_anoMQ-s-9l_XNwNFPfDVmOND9pXBJEBi7qsULF3bgPGpagtqjOsKDTXu8iOTVzvOjflz-M6EfnfwVH81Cu-nnai0kakouo=@protonmail.com>
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: quoted-printable
Subject: [bitcoin-dev] A fee-bumping model
Precedence: list

Hi everyone,

Fee-bumping is paramount to the security of many protocols building on Bitc=
oin, as they require the
confirmation of a transaction (which might be presigned) before the expirat=
ion of a timelock at any
point after the establishment of the contract.

The part of Revault using presigned transactions (the delegation from a lar=
ge to a smaller multisig)
is no exception. We have been working on how to approach this for a while n=
ow and i'd like to share
what we have in order to open a discussion on this problem so central to wh=
at seem to be The Right
Way [0] to build on Bitcoin but which has yet to be discussed in details (a=
t least publicly).

I'll discuss what we came up with for Revault (at least for what will be it=
s first iteration) but my
intent with posting to the mailing list is more to frame the questions to t=
his problem we are all
going to face rather than present the results of our study tailored to the =
Revault usecase.
The discussion is still pretty Revault-centric (as it's the case study) but=
 hopefully this can help
future protocol designers and/or start a discussion around what everyone's =
doing for existing ones.


## 1. Reminder about Revault

The part of Revault we are interested in for this study is the delegation p=
rocess, and more
specifically the application of spending policies by network monitors (watc=
htowers).
Coins are received on a large multisig. Participants of this large multisig=
 create 2 [1]
transactions. The Unvault, spending a deposit UTxO, creates an output payin=
g either to the small
multisig after a timelock or to the large multisig immediately. The Cancel,=
 spending the Unvault
output through the non-timelocked path, creates a new deposit UTxO.
Participants regularly exchange the Cancel transaction signatures for each =
deposit, sharing the
signatures with the watchtowers they operate. They then optionally [2] sign=
 the Unvault transaction
and share the signatures with the small multisig participants who can in tu=
rn use them to proceed
with a spending. Watchtowers can enforce spending policies (say, can't Unva=
ult outside of business
hours) by having the Cancel transaction be confirmed before the expiration =
of the timelock.


## 2. Problem statement

For any delegated vault, ensure the confirmation of a Cancel transaction in=
 a configured number of
blocks at any point. In so doing, minimize the overpayments and the UTxO se=
t footprint. Overpayments
increase the burden on the watchtower operator by increasing the required f=
requency of refills of the
fee-bumping wallet, which is already the worst user experience. You are lik=
ely to manage a number of
UTxOs with your number of vaults, which comes at a cost for you as well as =
everyone running a full
node.

Note that this assumes miners are economically rationale, are incentivized =
by *public* fees and that
you have a way to propagate your fee-bumped transaction to them. We also do=
n't consider the block
space bounds.

In the previous paragraph and the following text, "vault" can generally be =
replaced with "offchain
contract".


## 3. With presigned transactions

As you all know, the first difficulty is to get to be able to unilaterally =
enforce your contract
onchain. That is, any participant must be able to unilaterally bump the fee=
s of a transaction even
if it was co-signed by other participants.

For Revault we can afford to introduce malleability in the Cancel transacti=
on since there is no
second-stage transaction depending on its txid. Therefore it is pre-signed =
with ANYONECANPAY. We
can't use ANYONECANPAY|SINGLE since it would open a pinning vector [3]. Not=
e how we can't leverage
the carve out rule, and neither can any other more-than-two-parties contrac=
t.
This has a significant implication for the rest, as we are entirely burning=
 fee-bumping UTxOs.

This opens up a pinning vector, or at least a significant nuisance: any oth=
er party can largely
increase the absolute fee without increasing the feerate, leveraging the RB=
F rules to prevent you
from replacing it without paying an insane fee. And you might not see it in=
 your own mempool and
could only suppose it's happening by receiving non-full blocks or with tran=
sactions paying a lower
feerate.
Unfortunately i know of no other primitive that can be used by multi-party =
(i mean, >2) presigned
transactions protocols for fee-bumping that aren't (more) vulnerable to pin=
ning.


## 4. We are still betting on future feerate

The problem is still missing one more constraint. "Ensuring confirmation at=
 any time" involves ensuring
confirmation at *any* feerate, which you *cannot* do. So what's the limit? =
In theory you should be ready
to burn as much in fees as the value of the funds you want to get out of th=
e contract. So... For us
it'd mean keeping for each vault an equivalent amount of funds sitting ther=
e on the watchtower's hot
wallet. For Lightning, it'd mean keeping an equivalent amount of funds as t=
he sum of all your
channels balances sitting there unallocated "just in case". This is not rea=
sonable.

So you need to keep a maximum feerate, above which you won't be able to ens=
ure the enforcement of
all your contracts onchain at the same time. We call that the "reserve feer=
ate" and you can have
different strategies for choosing it, for instance:
- The 85th percentile over the last year of transactions feerates
- The maximum historical feerate
- The maximum historical feerate adjusted in dollars (makes more sense but =
introduces a (set of?)
  trusted oracle(s) in a security-critical component)
- Picking a random high feerate (why not? It's an arbitrary assumption anyw=
ays)

Therefore, even if we don't have to bet on the broadcast-time feerate marke=
t at signing time anymore
(since we can unilaterally bump), we still need some kind of prediction in =
preparation of making
funds available to bump the fees at broadcast time.
Apart from judging that 500sat/vb is probably more reasonable than 10sat/vb=
yte, this unfortunately
sounds pretty much crystal-ball-driven.

We currently use the maximum of the 95th percentiles over 90-days windows o=
ver historical block chain
feerates. [4]


## 5. How much funds does my watchtower need?

That's what we call the "reserve". Depending on your reserve feerate strate=
gy it might vary over
time. This is easier to reason about with a per-contract reserve. For Revau=
lt it's pretty
straightforward since the Cancel transaction size is static: `reserve_feera=
te * cancel_size`. For
other protocols with dynamic transaction sizes (or even packages of transac=
tions) it's less so. For
your Lightning channel you would probably take the maximum size of your com=
mitment transaction
according to your HTLC exposure settings + the size of as many `htlc_succes=
s` transaction?

Then you either have your software or your user guesstimate how many offcha=
in contracts the
watchtower will have to watch, time that by the per-contract reserve and re=
fill this amount (plus
some slack in practice). Once again, a UX tradeoff (not even mentioning the=
 guesstimation UX):
overestimating leads to too many unallocated funds sitting on a hot wallet,=
 underestimating means
(at best) inability to participate in new contracts or being "at risk" (not=
 being able to enforce
all your contracts onchain at your reserve feerate) before a new refill.

For vaults you likely have large-value UTxOs and small transactions (the Ca=
ncel is one-in one-out in
Revault). For some other applications with large transactions and lower-val=
ue UTxOs on average it's
likely that only part of the offchain contracts might be enforceable at a r=
easonable feerate. Is it
reasonable?


## 6. UTxO pool layout

Now that you somehow managed to settle on a refill amount, how are you goin=
g to use these funds?
Also, you'll need to manage your pool across time (consolidating small coin=
s, and probably fanning
out large ones).

You could keep a single large UTxO and peel it as you need to sponsor trans=
actions. But this means
that you need to create a coin of a specific value according to your need a=
t the current feerate
estimation, hope to have it confirmed in a few blocks (at least for now! [5=
]), and hope that the
value won't be obsolete by the time it confirmed. Also, you'd have to do th=
at for any number of
Cancel, chaining feebump coin creation transactions off the change of the p=
revious ones or replacing
them with more outputs. Both seem to become really un-manageable (and expen=
sive) in many edge-cases,
shortening the time you have to confirm the actual Cancel transaction and c=
reating uncertainty about
the reserve (how much is my just-in-time fanout going to cost me in fees th=
at i need to refill in
advance on my watchtower wallet?).
This is less of a concern for protocols using CPFP to sponsor transactions,=
 but they rely on a
policy rule specific to 2-parties contracts.

Therefore for Revault we fan-out the coins per-vault in advance. We do so a=
t refill time so the
refiller can give an excess to pay for the fees of the fanout transaction (=
which is reasonable since
it will occur just after the refilling transaction confirms). When the watc=
htower is asked to watch
for a new delegated vault it will allocate coins from the pool of fanned-ou=
t UTxOs to it (failing
that, it would refuse the delegation).
What is a good distribution of UTxOs amounts per vault? We want to minimize=
 the number of coins,
still have coins small enough to not overpay (remember, we can't have chang=
e) and be able to bump a
Cancel up to the reserve feerate using these coins. The two latter constrai=
nts are directly in
contradiction as the minimal value of a coin usable at the reserve feerate =
(paying for its own input
fee + bumping the feerate by, say, 5sat/vb) is already pretty high. Therefo=
re we decided to go with
two distributions per vault. The "reserve distribution" alone ensures that =
we can bump up to the
reserve feerate and is usable for high feerates. The "bonus distribution" i=
s not, but contains
smaller coins useful to prevent overpayments during low and medium fee peri=
ods (which is most of the
time).
Both distributions are based on a basic geometric suite [6]. Each value is =
half the previous one.
This exponentially decreases the value, limiting the number of coins. But t=
his also allows for
pretty small coins to exist and each coin's value is equal to the sum of th=
e smaller coins,
or smaller by at most the value of the smallest coin. Therefore bounding th=
e maximum overpayment to
the smallest coin's value [7].

For the management of the UTxO pool across time we merged the consolidation=
 with the fanout. When
fanning out a refilled UTxO, we scan the pool for coins that need to be con=
solidated according to a
heuristic. An instance of a heuristic is "the coin isn't allocated and woul=
d not have been able to
increase the fee at the median feerate over the past 90 days of blocks".
We had this assumption that feerate would tend to go up with time and there=
fore discarded having to
split some UTxOs from the pool. We however overlooked that a large increase=
 in the exchange price of
BTC as we've seen during the past year could invalidate this assumption and=
 that should arguably be
reconsidered.


## 7. Bumping and re-bumping

First of all, when to fee-bump? At fixed time intervals? At each block conn=
ection? It sounds like,
given a large enough timelock, you could try to greed by "trying your luck"=
 at a lower feerate and
only re-bumping every N blocks. You would then start aggressively bumping a=
t every block after M
blocks have passed. But that's actually a bet (in disguised?) that the next=
 block feerate in M blocks
will be lower than the current one. In the absence of any predictive model =
it is more reasonable to
just start being aggressive immediately.
You probably want to base your estimates on `estimatesmartfee` and as a con=
sequence you would re-bump
(if needed )after each block connection, when your estimates get updated an=
d you notice your
transaction was not included in the block.

In the event that you notice a consequent portion of the block is filled wi=
th transactions paying
less than your own, you might want to start panicking and bump your transac=
tion fees by a certain
percentage with no consideration for your fee estimator. You might skew min=
ers incentives in doing
so: if you increase the fees by a factor of N, any miner with a fraction la=
rger than 1/N of the
network hashrate now has an incentive to censor your transaction at first t=
o get you to panic. Also
note this can happen if you want to pay the absolute fees for the 'pinning'=
 attack mentioned in
section #2, and that might actually incentivize miners to perform it themse=
lves..

The gist is that the most effective way to bump and rebump (RBF the Cancel =
tx) seems to just be to
consider the `estimatesmartfee 2 CONSERVATIVE` feerate at every block your =
tx isn't included in, and
to RBF it if the feerate is higher.
In addition, we fallback to a block chain based estimation when estimates a=
ren't available (eg if
the user stopped their WT for say a hour and we come back up): we use the 8=
5th percentile over the
feerates in the last 6 blocks. Sure, miners can try to have an influence on=
 that by stuffing their
blocks with large fee self-paying transactions, but they would need to:
1. Be sure to catch a significant portion of the 6 blocks (at least 2, actu=
ally)
2. Give up on 25% of the highest fee-paying transactions (assuming they got=
 the 6 blocks, it's
   proportionally larger and incertain as they get less of them)
3. Hope that our estimator will fail and we need to fall back to the chain-=
based estimation


## 8. Our study

We essentially replayed the historical data with different deployment confi=
gurations (number of
participants and timelock) and probability of an event occurring (event bei=
ng say an Unvault, an
invalid Unvault, a new delegation, ..). We then observed different metrics =
such as the time at risk
(when we can't enforce all our contracts at the reserve feerate at the same=
 time), or the
operational cost.
We got the historical fee estimates data from Statoshi [9], Txstats [10] an=
d the historical chain
data from Riccardo Casatta's `blocks_iterator` [11]. Thanks!

The (research-quality..) code can be found at https://github.com/revault/re=
search under the section
"Fee bumping". Again it's very Revault specific, but at least the data can =
probably be reused for
studying other protocols.


## 9. Insurances

Of course, given it's all hacks and workarounds and there is no good answer=
 to "what is a reasonable
feerate up to which we need to make contracts enforceable onchain?", there =
is definitely room for an
insurance market. But this enters the realm of opinions. Although i do have=
 some (having discussed
this topic for the past years with different people), i would like to keep =
this post focused on the
technical aspects of this problem.


[0] As far as i can tell, having offchain contracts be enforceable onchain =
by confirming a
transaction before the expiration of a timelock is a widely agreed-upon app=
roach. And i don't think
we can opt for any other fundamentally different one, as you want to know y=
ou can claim back your
coins from a contract after a deadline before taking part in it.

[1] The Real Revault (tm) involves more transactions, but for the sake of c=
onciseness i only
detailed a minimum instance of the problem.

[2] Only presigning part of the Unvault transactions allows to only delegat=
e part of the coins,
which can be abstracted as "delegate x% of your stash" in the user interfac=
e.

[3] https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2020-May/017835=
.html

[4] https://github.com/revault/research/blob/1df953813708287c32a15e771ba749=
57ec44f354/feebumping/model/statemachine.py#L323-L329

[5] https://github.com/bitcoin/bitcoin/pull/23121

[6] https://github.com/revault/research/blob/1df953813708287c32a15e771ba749=
57ec44f354/feebumping/model/statemachine.py#L494-L507

[7] Of course this assumes a combinatorial coin selection, but i believe it=
's ok given we limit the
number of coins beforehand.

[8] Although there is the argument to outbid a censorship, anyone censoring=
 you isn't necessarily a
miner.

[9] https://www.statoshi.info/

[10] https://www.statoshi.info/

[11] https://github.com/RCasatta/blocks_iterator