Date: Thu, 02 Jul 2020 16:06:04 +0000
To: Tejaswi Nadahalli <nadahalli@gmail.com>
From: ZmnSCPxj <ZmnSCPxj@protonmail.com>
Reply-To: ZmnSCPxj <ZmnSCPxj@protonmail.com>
Message-ID: <YhzMZ419vB1BY4Opd3lwfSSJ6_4AIQUDDtZPPhyB2HgskDZv0DKCQlEOAFklskLp1mj5AZrI43VPXOslX25MO-3Fijl9pBWrWYlYiaERr70=@protonmail.com>
In-Reply-To: <CAAifmARxvG+_Wo3zba6MCd=jxwesb2JhWAwRErq6QPVTe1AQEA@mail.gmail.com>
References: <CABT1wW=X35HRVGuP-BHUhDrkBEw27+-iDkNnHWjRU-1mRkn0JQ@mail.gmail.com>
 <CABT1wW=KWtoo6zHs8=yUQ7vAYcFSdAzdpDJ9yfw6sJrLd6dN5A@mail.gmail.com>
 <20200628121517.f3l2mjcy7x4566v3@ganymede>
 <WYQRrIi65yvBWc9qsqCxHWadrMFtYPh2wI-IzVS15FBTFmpIXqHwj5yrj3Igpr-9sKygWsH4DkI_maWcULKKQb51Xp_xZBvKuPF_HmCvqb4=@protonmail.com>
 <CAAifmATmQSUUsEbouVYTNNMu-BT8vQiGvh3jwLNK4CUB11s7mg@mail.gmail.com>
 <Fh70O0CqbkbLaOUEqRzIG3MOOZi_tYz69xRDPlIlF5tgTIPdYF9LyeoJjypo-agN9-WkuoXJD896R6CQygTozeHA_CFULp3k7007PioaDrs=@protonmail.com>
 <CAAifmARxvG+_Wo3zba6MCd=jxwesb2JhWAwRErq6QPVTe1AQEA@mail.gmail.com>
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: quoted-printable
Cc: Matan Yehieli <matany@campus.technion.ac.il>,
 Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>,
 Itay Tsabary <sitay@campus.technion.ac.il>
Subject: Re: [bitcoin-dev] MAD-HTLC
Precedence: list

Good morning Tejaswi,

> > So it looks to me that scorched-earth is a possible mitigation against =
this attack.
>
> I don't follow this. We show that a reasonable value of fees and timelock=
 are enough to avoid the attack. Why scorch the earth?

Because your model only considers that a block might have only 0 or 1 trans=
actions, and there is no such thing as a mempool containing alternative, fe=
e-paying transactions that the miner could include *instead*.

In reality, what a miner can earn from adding Alice transaction is the *dif=
ference* between the Alice transaction fee and the transaction that *just* =
misses getting included in the block because of feerate.

Thus, the f will not, in fact, *quite* be the Alice fee, but instead less t=
han that.

Indeed if the Alice transaction fee is lower than the top 4 Mweight transac=
tions in the mempool, the miner would be *losing* funds by including the Al=
ice transaction.

My understanding is that we expect mempools to eventually never empty, as t=
he block subsidy reduces over time, thus the payoff f for including the Ali=
ce transaction *instead of* some other transaction will be less than the Al=
ice fee.


This effect also holds for Bob, but we can probably expect, all things bein=
g equal, that approximately the same value will be deducted from both the B=
ob bribe and Alice fee by the mempool effect.
Thus the ratio should really be (f - x) / (b - x), where x is the fee-of-tr=
ansaction-that-just-misses-the-block.
At fee spikes, this x will go higher, and thus (f - x) / (b - x) will be fa=
r smaller than f / b and might even become negative, in which case the Alic=
e transaction will not be confirmed even by myopic miners, because the Alic=
e transaction will be below the top 4Mweight transactions in the mempool.


So it seems to me reasonable to use a *gradual* scorched earth policy, as i=
t is not only resilient against this attack, but also to fee spikes.
Alice starts at the 1% reserve, then for every block that goes by, bumps up=
 the fee.
Then Alice will settle at an (f - x) / (b - x) level that achieves the leas=
t weak miner that is known to run the myopic strategy.


I believe this is also better for UX --- people already accept that during =
high fee spikes, they end up paying more for onchain activities.
But boosting up `to_self_delay` is bad because it makes honest unilateral c=
loses take longer, and we already get frownie faces from users about this p=
arameter.
By using a gradual scorched-earth strategy we can start at the reserve leve=
l, and if we are not under attack and there is no fee spike, do not lose an=
ything other than the reserve funds of the thief (which is not ours, but is=
 instead that of the thief).
But if an attack happens during a fee spike, then even though we retain our=
 current default `to_self_delay` of 144, we still have the ability to gradu=
ally and automatically move to higher fee regions until our transaction con=
firms, and we have a good excuse for it to present to users: "a fee spike w=
as happening at the time, so you had to pay some extra miner fees".


----

And since you and your paper openly discusses it anyway, I would like to re=
veal that the MAD-HTLC argument does not apply to *just* HTLCs.
You make recommendations about `to_self_delay` and `channel_reserve_satoshi=
s`, which are not parameters of Lightning HTLCs (those are stuff like `cltv=
_delta` and `final_cltv`), but are channel parameters.

The MAD-HTLC argument applies just as well to channel mechanisms themselves=
, ***independently of*** any HTLCs they transport.

The MAD-HTLC paper has the following core argument:

* We currently assume that currently-valid transactions will inevitably sup=
ersede alternate transactions that are valid at a later block height, simpl=
y because of the time advantage.
  * However, the owner of a later-block-height transaction can bribe miners=
 to defer confirmation of currently-valid transactions, until its later-blo=
ck-height transaction is valid and confirms.

The above core argument is presented as applying to HTLCs.

However, the same argument actually **also** applies to all current offchai=
n multiparticipant cryptocurrency systems (i.e. "channel mechanisms").

* Spilman
* Poon-Dryja (what we currently use in Lightning)
* Decker-Wattenhofer decrementing-`nSequence`
* Decker-Russell-Osuntokun

The [Khabbazian-Nadahalli-Wattenhofer "Timelocked Bribing" paper](https://e=
print.iacr.org/2020/774.pdf) mentions the use of revoked transactions in a =
Poon-Dryja mechanism, but seems to imply that the issue is with the HTLC in=
stantiated inside the revoked transaction.
But note that the paper describes recommendations for the `to_self_delay` p=
arameter and also analyzes the `channel_reserve_satoshis` parameter, which =
are parameters of the ***Poon-Dryja*** mechanism, and **not** of the HTLCs =
instantiated inside it.

So, to be very clear, the MAD-HTLC argument applies to all the above mechan=
isms *even if HTLCs are not used at all*.
Or put another way, if you use a modern offchain updateable cryptocurrency =
system at all, you are still vulnerable to the MAD-HTLC argument even if yo=
u never instantiate HTLCs inside the offchain system.

Thus, other proposed systems that (could) use any of the channel mechanisms=
, but do ***not*** necessarily use HTLCs, such as CoinPools, channel factor=
ies, and statechains, are also vulnerable to the MAD-HTLC argument.

In particular, if the MAD-HTLC argument holds, we should take note that e.g=
. Lightning channels have to be at least as large as any HTLC they contain,=
 and since the MAD-HTLC argument applies to the channel itself (in addition=
 to any HTLCs they contain), the application of that argument implies great=
er loss, as it is the entire channel that is at risk, not just any HTLCs it=
 might contain.

Spilman
=3D=3D=3D=3D=3D=3D=3D

A Spilman channel is a unidirectional single-funded channel.

The overall idea was presented pre-SegWit, and needed `OP_CHECKLOCKTIMEVERI=
FY` to be malleation-safe.
I will describe here a modernized version that uses SegWit (and thus is mal=
leation safe) instead.

Suppose Bob wishes to make a Spilman channel to Alice.
The setup is as follows:

* Bob creates but does *NOT* sign a funding transaction, paying out to a 2-=
of-2 between Alice and Bob, and hands over this txid and the output number =
to Alice.
* Alice creates a timeout transaction, `nLockTime`d to a pre-agreed locktim=
e, spending the above txout, and returning the funds to Bob, and signs this=
 transaction and hands over the signature and tx to Bob.
* Bob signs the funding transaction and broadcasts it.
* Alice and Bob wait for deep confirmation of the funding tx.

At each payment from Bob to Alice, Bob signs a non-`nLockTime`d (or one wit=
h current blockheight) transaction that spends the funding txout and assign=
s more of the fund to Alice, then sends the signature and tx to Alice.

At any time, Alice can unilaterally close the channel using any of the sign=
atures given by Bob.
Rationally, it will publish the one that gives it the most money, which is =
the latest such transaction, thus leading to the unidirectional nature of S=
pilman channels.
Alice needs to perform this unilateral close far before the pre-agreed lock=
time.

Under the MAD-HTLC argument, Bob can bribe miners to ignore the Alice unila=
teral close transaction, and the initial timeout transaction by Bob gets co=
nfirmed even if within the channel mechanism Alice is supposed to own most =
or all of the funds.

Poon-Dryja
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D

A Poon-Dryja channel is a modern two-participant bidirectional channel.

The core of security of Poon-Dryja involves "revocable outputs".
A revocable output is an output that, when published onchain, is owned by o=
ne entity (the owner), but that entity may reveal a secret, the revocation =
secret, to another entity (the revoker).
Once that other entity knows the revocation secret, if the output is ever p=
ublished onchain, it can revoke the output and claim its value.

Poon-Dryja uses this building block to implement an updateable state.
All states are represented by commitment transactions that have revocable o=
utputs.
In order to advance to a new state, the revocable outputs of previous state=
s are revoked by exchanging revocation secrets.
Thus, the security of Poon-Dryja is dependent on the correct operation of r=
evocation.

Revocable outputs are implemented by imposing a relative locktime on the ow=
ner of the output, and requiring knowledge of two secrets from the revoker.

Thus, a revocable output has two branches:

* Revocation branch: with the revoker privkey and knowledge of a revocaatio=
n secret, the revoker can claim the fund immediately.
* Claim branch: with the owner privkey and a relative locktime, the owner c=
an claim the fund after a pre-agreed number of blocks (`to_self_delay` in L=
ightning) since the output is confirmed onchain.

Under the MAD-HTLC argument, the owner of the revoked output can bribe mine=
rs to ignore attempts by the revoker to claim the funds until the claim bra=
nch is valid and confirmable.
Thus, a thief can publish old state, then apply the MAD-HTLC argument to ge=
t miners to ignore the revoker of the old state.

Decker-Wattenhofer decrementing-`nSequence`
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D

Decker-Wattenhofer ("Duplex Micropayment Channels") is a modern multi-parti=
cipant (N >=3D 2) offchain updateable cryptocurrency mechanism.

Decker-Wattenhofer chains together two different mechanisms, embedding them=
 one inside the other, in order to balance the tradeoffs of one with the tr=
adeoffs of the other.

* One or more decrementing-`nSequence` mechanisms, chained one inside the o=
ther.
* Two ("duplex") unidirectional Spilman variants, using a relative locktime=
 instead of an absolute locktime, one in both directions of the channel, in=
side the innermost decrementing-`nSequence` mechanism.

The decrementing-`nSequence` mechanisms by themselves are multiparticipant =
(N >=3D 2), and if we focus only on having one or more of these mechanisms =
chained together, we can consider Decker-Wattenhofer as multiparticipant.

In the decrementing-`nSequence` mechanism, there is a kickoff transaction w=
hich spends from the n-of-n funding outpoint, and sends it to yet another n=
-of-n output between the participants.
Then, the second n-of-n is spent by a transaction with a relative-locktime =
`nSequence` transaction, which then distributes the money among various par=
ticipants.

When a new state is created, the participants create and sign a new relativ=
e-locktime `nSequence` transaction spending the kickoff n-of-n outpoint.
The new state transaction has a lower `nSequence` than the most previous st=
ate transaction, hence decrementing-`nSequence`.
Once the latest state transaction has a 0-block relative locktime, a newer =
state can no longer be added to the mechanism.

The kickoff n-of-n outpoint thus has multiple branches, one for each create=
d state.
The most recent state is assumed to supersede previous states, because it h=
as the smallest relative locktime among all states.

Under the MAD-HTLC argument, a participant which prefers an older state can=
 bribe miners to defer confirmation of all more recent states.
Thus, that participant can publish the kickoff and bribe miners to defer mo=
re recent states until its preferred state is confirmable onchain.

Decker-Russell-Osuntokun
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D

Decker-Russell-Osuntokun ("eltoo") is a futuristic multiparticipant (N >=3D=
 2) offchain updateable cryptocurrency system.

Decker-Russell-Osuntokun uses a proposed new `SIGHASH_NOINPUT` flag, which =
does not commit to the specific output being spent, allowing a signature th=
at signs using `SIGHASH_NOINPUT` to be used to spend a different transactio=
n outpoint, as long as the same pubkey is used for that outpoint.

As is typical for channel mechanisms, a funding outpoint is created, which =
is an n-of-n of all participants.
The funding outpoint is spent by an update transaction with a single output=
, which has the following branches:

* Update branch: can be spent by the same n-of-n pubkeys as the funding out=
point, as long as the spending transaction has a higher `nLockTime` than th=
e update transaction.
* State branch: can be spent by a different n-of-n pubkeys from the same pa=
rticipants, after a relative locktime.
  * Each update transaction has its own unique set of n-of-n pubkeys for th=
e state branch, given by the same participant set.

Of note is that the `nLockTime` used in Decker-Russell-Osuntokun are always=
 past `nLockTime`s, so that the update branch is always confirmable at the =
current tip, from now until forever.
Only the state branch has an actual timelock that could prevent immediate c=
onfirmation of a transaction spending that branch.

Update transactions (awesomely mis)use `nLockTime` as a sequence number; th=
e first update transaction has the lowest `nLockTime`, then each succeeding=
 update transaction has a higher `nLockTime`, until they reach the present =
time.

Update transactions are signed with `SIGHASH_NOINPUT`.
This allows the update transaction to not only spend the funding outpoint i=
tself, but also to spend any previous update transaction.

Thus, if an old update transaction is published onchain, its output can be =
re-spent by any newer update transaction before the state transaction for t=
hat update can come into play.
Any other participant who notices this event can simply publish the newest =
update transaction it knows, as that would supersede the state transaction,=
 which can only be confirmed after a time delay.

Under the MAD-HTLC argument, a participant who prefers an older state can p=
ublish the update transaction for the older state, then bribe miners to def=
er confirmation of newer update transactions, until the state transaction f=
or that update transaction can be confirmed.

Conclusion
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D

All the above mechanisms use a timelock, and implicitly have the assumption=
 that "a transaction, that can be confirmed now, supersedes any transaction=
 that has a timelock that forces it to be confirmed later".

It seems likely to me that even future mechanisms will use the same assumpt=
ion as well.

In particular, many proposed mechanisms for non-federated sidechains often =
include some kind of delay between when a sidechain coin is burned and the =
corresponding mainchain coin is released (i.e. side-to-main peg).
Often, this delay exists in order to allow showing of a counterproof that t=
he supposed side-to-main transfer did not actually exist in the sidechain (=
or was later reorged out, or whatever).
It seems to me that the MAD-HTLC argument would also apply to such mechanis=
ms (if anyone still wants to go push sidechains, anyway).

Thus, we really need to carefully investigate the MAD-HTLC argument.

My current analysis suggests that in practice, the MAD-HTLC argument does n=
ot apply at all (else I would not be revealing that all channel mechanisms =
are broken **if** the MAD-HTLC argument *does* apply), since the myopic str=
ategy seems to be pretty much inevitably dominant at stable states.
But it would still be best to investigate further until we are fully convin=
ced that the MAD-HTLC argument ("'earlier supersedes later' might be falsif=
ied by bribery") does not apply.



Regards,
ZmnSCPxj