path: root/80/1678e502603b7b24c40a3dadcf73be4dd91eda

Return-Path: <nadahalli@gmail.com>
Received: from whitealder.osuosl.org (smtp1.osuosl.org [140.211.166.138])
 by lists.linuxfoundation.org (Postfix) with ESMTP id 8F9BCC0733
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Fri,  3 Jul 2020 09:43:52 +0000 (UTC)
Received: from localhost (localhost [127.0.0.1])
 by whitealder.osuosl.org (Postfix) with ESMTP id 6CB8E88DB6
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Fri,  3 Jul 2020 09:43:52 +0000 (UTC)
X-Virus-Scanned: amavisd-new at osuosl.org
Received: from whitealder.osuosl.org ([127.0.0.1])
 by localhost (.osuosl.org [127.0.0.1]) (amavisd-new, port 10024)
 with ESMTP id HJRNAR-ZKXxt
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Fri,  3 Jul 2020 09:43:49 +0000 (UTC)
X-Greylist: domain auto-whitelisted by SQLgrey-1.7.6
Received: from mail-pf1-f171.google.com (mail-pf1-f171.google.com
 [209.85.210.171])
 by whitealder.osuosl.org (Postfix) with ESMTPS id 2F33C88DB3
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Fri,  3 Jul 2020 09:43:49 +0000 (UTC)
Received: by mail-pf1-f171.google.com with SMTP id 67so9710787pfg.5
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Fri, 03 Jul 2020 02:43:49 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025;
 h=mime-version:references:in-reply-to:from:date:message-id:subject:to
 :cc; bh=3mgWcVie8cLmrgj8oHL0IOg35YyvQBFg1PHBis0581M=;
 b=QFBnqEbU6zchy3WI0ASBCCoRta6zQkCBazV4MZBRVrK4qxy3PUWiCf5U/dJFqUNdGy
 S4lOFQXreWXHrB4fEw9Kt5Grc3FEZoFDuVvSlexjlD17NjE24rpJEmAeQ6MEhy3B0Zs/
 21ogCN+Vp94LdM813N6TlSPfn2b25D5fpZLLqEEuhnCmwInmBaqTTXz55gF9qGsesYge
 OSJXaPkFHvGywei2INiAxQm+YXKJWqllgMg4XDgin5xgY5t9gryM51XggxYCAcVoIEtV
 vEgj1laXAzJPIC4W18RPXjEl5QyKH89gpLQ+2XxXoV66CrJIbTwrt5mDJSdRdyu1KRKx
 GpzA==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
 d=1e100.net; s=20161025;
 h=x-gm-message-state:mime-version:references:in-reply-to:from:date
 :message-id:subject:to:cc;
 bh=3mgWcVie8cLmrgj8oHL0IOg35YyvQBFg1PHBis0581M=;
 b=a1H7LVTt+UL+RIVMjpTrkUxHD0qQvPPjK0siuA6nopVHbnYgNHUp7mZRKS1wc5XWHf
 5bnG3aKRx/sW9ptaW6IfJeadwaRfMwGNNf6IQa2aunbrgxWCoKuV/7ou5PCG1ffwP6j7
 8YI2PHBJj3eFA/9TCntQHitcA35fQaUbE+TdWn/GWmgskq0EyVIAPKBMu4Tdpq+ztx6M
 4EhpaLDScs8MyHLKnAW0obVBhP+HXdyNnbdPaABJD9PaMdU8D9S+Y3lcAczpUjJbJyNo
 hwkzE14I/RLNH+IOQGjiNHIMzicGqhXcZuzY3JyryB0hW0vLxhzr/izkdBAvXQJVKOOl
 bqLg==
X-Gm-Message-State: AOAM533M9xea2WgOe9LSIcs1I+xPPGF+eOZ40Dzr1FIURWPVFbVCp/9k
 /nm/Dvdc5G0u9U4IZAtK5ABdP8Q5FN1FUZPpzUw=
X-Google-Smtp-Source: ABdhPJzDTnJeuCNlfPcjMb+wT0+TWWaxAZmxPiJRsK7Tltjv9xz+S4I8O2mGUKtNio+HlyYtEmcP2P9t/geZH5yrzLA=
X-Received: by 2002:a63:5a54:: with SMTP id k20mr27851469pgm.226.1593769428539; 
 Fri, 03 Jul 2020 02:43:48 -0700 (PDT)
MIME-Version: 1.0
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>
 <YhzMZ419vB1BY4Opd3lwfSSJ6_4AIQUDDtZPPhyB2HgskDZv0DKCQlEOAFklskLp1mj5AZrI43VPXOslX25MO-3Fijl9pBWrWYlYiaERr70=@protonmail.com>
In-Reply-To: <YhzMZ419vB1BY4Opd3lwfSSJ6_4AIQUDDtZPPhyB2HgskDZv0DKCQlEOAFklskLp1mj5AZrI43VPXOslX25MO-3Fijl9pBWrWYlYiaERr70=@protonmail.com>
From: Tejaswi Nadahalli <nadahalli@gmail.com>
Date: Fri, 3 Jul 2020 11:43:37 +0200
Message-ID: <CAAifmATpg21K=yvi8OaPgr2esdtciu_uNLmNbA8983iht7Ru_Q@mail.gmail.com>
To: ZmnSCPxj <ZmnSCPxj@protonmail.com>
Content-Type: multipart/alternative; boundary="000000000000a4611e05a9865c39"
X-Mailman-Approved-At: Fri, 03 Jul 2020 10:09:11 +0000
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
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: Fri, 03 Jul 2020 09:43:52 -0000

--000000000000a4611e05a9865c39
Content-Type: text/plain; charset="UTF-8"

On Thu, Jul 2, 2020 at 6:06 PM ZmnSCPxj <ZmnSCPxj@protonmail.com> wrote:

> At fee spikes, this x will go higher, and thus (f - x) / (b - x) will be
> far smaller than f / b and might even become negative, in which case the
> Alice transaction will not be confirmed even by myopic miners, because the
> Alice transaction will be below the top 4Mweight transactions in the
> mempool.
>

I agree. The MAD-HTLC authors actually keep the base fee in their
calculations, and we deliberately decided to ignore this. We believe that
this base fee to be much lower than the typical 1% channel balance, and it
actually doesn't change any of our results. This was brushed under the
"without loss of generality" rug. I admit that we should have made this
clear in our Assumptions section though. Point taken.


> 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
> gradually and automatically move to higher fee regions until our
> transaction confirms, and we have a good excuse for it to present to users:
> "a fee spike was happening at the time, so you had to pay some extra miner
> fees".
>

Agree on the UX. There is a tradeoff between the timelocked value of the
channel balance to Alice during benign vs malicious abandonment by Bob. In
your opinion, increasing the fees beyond 1% (and thereby cutting into
Alice's share itself) is a slightly better tradeoff than increasing
to_self_delay.


> And since you and your paper openly discusses it anyway, I would like to
> reveal that the MAD-HTLC argument does not apply to *just* HTLCs.
>

We know. Maybe we should have made it clear in the paper that when we use
the Poon-Dryja channel construction, we use the idea that the knowledge of
the preimage of a hash is equivalent to knowing the private key of the
revocation public key. In fact, this is how the Poon-Dryja construction is
explained in McCorry's Ph.D thesis
<https://nms.kcl.ac.uk/patrick.mccorry/thesis.pdf>, and IMHO is easier to
understand than the original description in the Poon-Dryja paper (or Bolt
#3, for that matter).

You could further argue that the hashlock is an incidental artefact, and
our paper mostly refers to timelocked transactions. And the rest of your
email describes applications of timelocked (and obviously presigned)
transactions, which are all vulnerable to the same bribing attack.
Additionally, the Wattehnofer in our paper is the same Wattenhofer from the
Duplex Channel paper.

My current analysis suggests that in practice, the MAD-HTLC argument does
> not 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
> strategy seems to be pretty much inevitably dominant at stable states.
>

We agree.


> But it would still be best to investigate further until we are fully
> convinced that the MAD-HTLC argument ("'earlier supersedes later' might be
> falsified by bribery") does not apply.
>

I think this is the analysis our paper does, and perhaps it's our mistake
that we do not set the context better. We only mention (and propose fixes
for) Poon-Dryja channel construction, and Tier Nolan's Atomic Swap
construction.

We could have addressed Spilman's one-way channels or Decker-Wattenhofer
duplex channels, but that would have been pointless as they were never
going to make it into production after Poon-Dryja and subsequently, Eltoo
were proposed. But not addressing Eltoo in the paper is an omission that I
am a bit upset about. We additionally do not address more sophisticated
atomic swaps from Somsen or Fournier. Nor do we address Kanzure's vault
proposal. In fact, one rule of thumb might be that wherever watchtowers are
required, a timelocked bribe might be possible.

And again, thanks for the detailed analysis.

On Thu, Jul 2, 2020 at 6:06 PM ZmnSCPxj <ZmnSCPxj@protonmail.com> wrote:

> 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
> transactions, and there is no such thing as a mempool containing
> alternative, fee-paying transactions that the miner could include *instead*.
>
> In reality, what a miner can earn from adding Alice transaction is the
> *difference* 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
> than that.
>
> Indeed if the Alice transaction fee is lower than the top 4 Mweight
> transactions in the mempool, the miner would be *losing* funds by including
> the Alice transaction.
>
> My understanding is that we expect mempools to eventually never empty, as
> the block subsidy reduces over time, thus the payoff f for including the
> Alice transaction *instead of* some other transaction will be less than the
> Alice fee.
>
>
> This effect also holds for Bob, but we can probably expect, all things
> being equal, that approximately the same value will be deducted from both
> the Bob bribe and Alice fee by the mempool effect.
> Thus the ratio should really be (f - x) / (b - x), where x is the
> fee-of-transaction-that-just-misses-the-block.
> At fee spikes, this x will go higher, and thus (f - x) / (b - x) will be
> far smaller than f / b and might even become negative, in which case the
> Alice transaction will not be confirmed even by myopic miners, because the
> Alice 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
> it 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
> least 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
> closes take longer, and we already get frownie faces from users about this
> parameter.
> By using a gradual scorched-earth strategy we can start at the reserve
> level, and if we are not under attack and there is no fee spike, do not
> lose anything 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
> gradually and automatically move to higher fee regions until our
> transaction confirms, and we have a good excuse for it to present to users:
> "a fee spike was 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
> reveal that the MAD-HTLC argument does not apply to *just* HTLCs.
> You make recommendations about `to_self_delay` and
> `channel_reserve_satoshis`, 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
> supersede alternate transactions that are valid at a later block height,
> simply 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-block-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
> offchain 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://eprint.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 instantiated inside the revoked transaction.
> But note that the paper describes recommendations for the `to_self_delay`
> parameter 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
> mechanisms *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
> you 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 factories, 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 greater loss, as it is the entire channel that is at risk, not just
> any HTLCs it might contain.
>
> Spilman
> =======
>
> A Spilman channel is a unidirectional single-funded channel.
>
> The overall idea was presented pre-SegWit, and needed
> `OP_CHECKLOCKTIMEVERIFY` to be malleation-safe.
> I will describe here a modernized version that uses SegWit (and thus is
> malleation 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
> locktime, 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
> with current blockheight) transaction that spends the funding txout and
> assigns 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
> signatures 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
> Spilman channels.
> Alice needs to perform this unilateral close far before the pre-agreed
> locktime.
>
> Under the MAD-HTLC argument, Bob can bribe miners to ignore the Alice
> unilateral close transaction, and the initial timeout transaction by Bob
> gets confirmed even if within the channel mechanism Alice is supposed to
> own most or all of the funds.
>
> Poon-Dryja
> ==========
>
> 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
> one 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
> published 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
> outputs.
> In order to advance to a new state, the revocable outputs of previous
> states are revoked by exchanging revocation secrets.
> Thus, the security of Poon-Dryja is dependent on the correct operation of
> revocation.
>
> Revocable outputs are implemented by imposing a relative locktime on the
> owner 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
> revocaation secret, the revoker can claim the fund immediately.
> * Claim branch: with the owner privkey and a relative locktime, the owner
> can claim the fund after a pre-agreed number of blocks (`to_self_delay` in
> Lightning) since the output is confirmed onchain.
>
> Under the MAD-HTLC argument, the owner of the revoked output can bribe
> miners to ignore attempts by the revoker to claim the funds until the claim
> branch is valid and confirmable.
> Thus, a thief can publish old state, then apply the MAD-HTLC argument to
> get miners to ignore the revoker of the old state.
>
> Decker-Wattenhofer decrementing-`nSequence`
> ===========================================
>
> Decker-Wattenhofer ("Duplex Micropayment Channels") is a modern
> multi-participant (N >= 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 tradeoffs of the other.
>
> * One or more decrementing-`nSequence` mechanisms, chained one inside the
> other.
> * Two ("duplex") unidirectional Spilman variants, using a relative
> locktime instead of an absolute locktime, one in both directions of the
> channel, inside the innermost decrementing-`nSequence` mechanism.
>
> The decrementing-`nSequence` mechanisms by themselves are multiparticipant
> (N >= 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
> which 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
> participants.
>
> When a new state is created, the participants create and sign a new
> relative-locktime `nSequence` transaction spending the kickoff n-of-n
> outpoint.
> The new state transaction has a lower `nSequence` than the most previous
> state 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
> created state.
> The most recent state is assumed to supersede previous states, because it
> has 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
> more recent states until its preferred state is confirmable onchain.
>
> Decker-Russell-Osuntokun
> ========================
>
> Decker-Russell-Osuntokun ("eltoo") is a futuristic multiparticipant (N >=
> 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
> that signs using `SIGHASH_NOINPUT` to be used to spend a different
> transaction 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
> outpoint, as long as the spending transaction has a higher `nLockTime` than
> the update transaction.
> * State branch: can be spent by a different n-of-n pubkeys from the same
> participants, after a relative locktime.
>   * Each update transaction has its own unique set of n-of-n pubkeys for
> the 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
> confirmation of a transaction spending that branch.
>
> Update transactions (awesomely mis)use `nLockTime` as a sequence number;
> the 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
> itself, 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
> that 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
> publish the update transaction for the older state, then bribe miners to
> defer confirmation of newer update transactions, until the state
> transaction for that update transaction can be confirmed.
>
> Conclusion
> ==========
>
> 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
> assumption 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
> the 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
> mechanisms (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
> not 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
> strategy seems to be pretty much inevitably dominant at stable states.
> But it would still be best to investigate further until we are fully
> convinced that the MAD-HTLC argument ("'earlier supersedes later' might be
> falsified by bribery") does not apply.
>
>
>
> Regards,
> ZmnSCPxj
>

--000000000000a4611e05a9865c39
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr"><div dir=3D"ltr">On Thu, Jul 2, 2020 at 6:06 PM ZmnSCPxj &=
lt;<a href=3D"mailto:ZmnSCPxj@protonmail.com">ZmnSCPxj@protonmail.com</a>&g=
t; wrote:<br></div><div class=3D"gmail_quote"><blockquote class=3D"gmail_qu=
ote" style=3D"margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,20=
4);padding-left:1ex">At fee spikes, this x will go higher, and thus (f - x)=
 / (b - x) will be far smaller than f / b and might even become negative, i=
n which case the Alice transaction will not be confirmed even by myopic min=
ers, because the Alice transaction will be below the top 4Mweight transacti=
ons in the mempool.<br></blockquote><div><br></div><div>I agree. The MAD-HT=
LC authors actually keep the base fee in their calculations, and we deliber=
ately decided to ignore this. We believe that this base fee to be much lowe=
r than the typical 1% channel balance, and it actually doesn&#39;t change a=
ny of our results. This was brushed under the &quot;without loss of general=
ity&quot; rug. I admit that we should have made this clear in our Assumptio=
ns section though. Point taken.<br></div><div>=C2=A0</div><blockquote class=
=3D"gmail_quote" style=3D"margin:0px 0px 0px 0.8ex;border-left:1px solid rg=
b(204,204,204);padding-left:1ex">But if an attack happens during a fee spik=
e, then even though we retain our current default `to_self_delay` of 144, w=
e still have the ability to gradually and automatically move to higher fee =
regions until our transaction confirms, and we have a good excuse for it to=
 present to users: &quot;a fee spike was happening at the time, so you had =
to pay some extra miner fees&quot;.<br></blockquote><div><br></div><div>Agr=
ee on the UX. There is a tradeoff between the timelocked value of the chann=
el balance to Alice during benign vs malicious abandonment by Bob. In your =
opinion, increasing the fees beyond 1% (and thereby cutting into Alice&#39;=
s share itself) is a slightly better tradeoff than increasing to_self_delay=
.=C2=A0<br></div><div>=C2=A0</div><blockquote class=3D"gmail_quote" style=
=3D"margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding=
-left:1ex">And since you and your paper openly discusses it anyway, I would=
 like to reveal that the MAD-HTLC argument does not apply to *just* HTLCs.<=
br></blockquote><div><br></div><div>We know. Maybe we should have made it c=
lear in the paper that when we use the Poon-Dryja channel construction, we =
use the idea that the knowledge of the preimage of a hash is equivalent to =
knowing the private key of the revocation public key. In fact, this is how =
the Poon-Dryja construction is explained in McCorry&#39;s Ph.D <a href=3D"h=
ttps://nms.kcl.ac.uk/patrick.mccorry/thesis.pdf">thesis</a>, and IMHO is ea=
sier to understand than the original description in the Poon-Dryja paper (o=
r Bolt #3, for that matter).=C2=A0</div><div><br></div><div>You could furth=
er argue that the hashlock=C2=A0is an incidental artefact, and our paper mo=
stly refers to timelocked transactions. And the rest of your email describe=
s applications of timelocked (and obviously presigned) transactions, which =
are all vulnerable to the same bribing attack. Additionally, the Wattehnofe=
r in our paper is the same Wattenhofer from the Duplex Channel paper.</div>=
<div><br></div><blockquote class=3D"gmail_quote" style=3D"margin:0px 0px 0p=
x 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">
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.<br></bl=
ockquote><div><br></div><div>We agree.=C2=A0</div><div>=C2=A0</div><blockqu=
ote class=3D"gmail_quote" style=3D"margin:0px 0px 0px 0.8ex;border-left:1px=
 solid rgb(204,204,204);padding-left:1ex">
But it would still be best to investigate further until we are fully convin=
ced that the MAD-HTLC argument (&quot;&#39;earlier supersedes later&#39; mi=
ght be falsified by bribery&quot;) does not apply.<br></blockquote><div><br=
></div><div>I think this is the analysis our paper does, and perhaps it&#39=
;s our mistake that we do not set the context better. We only mention (and =
propose fixes for) Poon-Dryja channel construction, and Tier Nolan&#39;s At=
omic Swap construction.=C2=A0</div><div><br></div><div>We could have addres=
sed Spilman&#39;s one-way channels or Decker-Wattenhofer duplex channels, b=
ut that would have been pointless as they were never going to make it into =
production after Poon-Dryja and subsequently, Eltoo were proposed. But not =
addressing Eltoo in the paper is an omission that I am a bit upset about. W=
e additionally do not address more sophisticated atomic swaps from Somsen o=
r Fournier. Nor do we address Kanzure&#39;s vault proposal. In fact, one ru=
le of thumb might be that wherever watchtowers are required, a timelocked b=
ribe might be possible.=C2=A0</div><div><br></div><div>And again, thanks fo=
r the detailed analysis.=C2=A0</div></div></div><br><div class=3D"gmail_quo=
te"><div dir=3D"ltr" class=3D"gmail_attr">On Thu, Jul 2, 2020 at 6:06 PM Zm=
nSCPxj &lt;<a href=3D"mailto:ZmnSCPxj@protonmail.com">ZmnSCPxj@protonmail.c=
om</a>&gt; wrote:<br></div><blockquote class=3D"gmail_quote" style=3D"margi=
n:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex=
">Good morning Tejaswi,<br>
<br>
&gt; &gt; So it looks to me that scorched-earth is a possible mitigation ag=
ainst this attack.<br>
&gt;<br>
&gt; I don&#39;t follow this. We show that a reasonable value of fees and t=
imelock are enough to avoid the attack. Why scorch the earth?<br>
<br>
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*.<br>
<br>
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.<br>
<br>
Thus, the f will not, in fact, *quite* be the Alice fee, but instead less t=
han that.<br>
<br>
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.<br>
<br>
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.<br>
<br>
<br>
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.<br>
Thus the ratio should really be (f - x) / (b - x), where x is the fee-of-tr=
ansaction-that-just-misses-the-block.<br>
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.<b=
r>
<br>
<br>
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.<br>
Alice starts at the 1% reserve, then for every block that goes by, bumps up=
 the fee.<br>
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.<br>
<br>
<br>
I believe this is also better for UX --- people already accept that during =
high fee spikes, they end up paying more for onchain activities.<br>
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.<br>
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).<br>
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: &quot;a fee sp=
ike was happening at the time, so you had to pay some extra miner fees&quot=
;.<br>
<br>
<br>
----<br>
<br>
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.<br>
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.<br>
<br>
The MAD-HTLC argument applies just as well to channel mechanisms themselves=
, ***independently of*** any HTLCs they transport.<br>
<br>
The MAD-HTLC paper has the following core argument:<br>
<br>
* 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.<br>
=C2=A0 * However, the owner of a later-block-height transaction can bribe m=
iners to defer confirmation of currently-valid transactions, until its late=
r-block-height transaction is valid and confirms.<br>
<br>
The above core argument is presented as applying to HTLCs.<br>
<br>
However, the same argument actually **also** applies to all current offchai=
n multiparticipant cryptocurrency systems (i.e. &quot;channel mechanisms&qu=
ot;).<br>
<br>
* Spilman<br>
* Poon-Dryja (what we currently use in Lightning)<br>
* Decker-Wattenhofer decrementing-`nSequence`<br>
* Decker-Russell-Osuntokun<br>
<br>
The [Khabbazian-Nadahalli-Wattenhofer &quot;Timelocked Bribing&quot; paper]=
(<a href=3D"https://eprint.iacr.org/2020/774.pdf" rel=3D"noreferrer" target=
=3D"_blank">https://eprint.iacr.org/2020/774.pdf</a>) mentions the use of r=
evoked transactions in a Poon-Dryja mechanism, but seems to imply that the =
issue is with the HTLC instantiated inside the revoked transaction.<br>
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.<br>
<br>
So, to be very clear, the MAD-HTLC argument applies to all the above mechan=
isms *even if HTLCs are not used at all*.<br>
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.<br>
<br>
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.<br>
<br>
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.<br>
<br>
Spilman<br>
=3D=3D=3D=3D=3D=3D=3D<br>
<br>
A Spilman channel is a unidirectional single-funded channel.<br>
<br>
The overall idea was presented pre-SegWit, and needed `OP_CHECKLOCKTIMEVERI=
FY` to be malleation-safe.<br>
I will describe here a modernized version that uses SegWit (and thus is mal=
leation safe) instead.<br>
<br>
Suppose Bob wishes to make a Spilman channel to Alice.<br>
The setup is as follows:<br>
<br>
* 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.<br>
* 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.<br>
* Bob signs the funding transaction and broadcasts it.<br>
* Alice and Bob wait for deep confirmation of the funding tx.<br>
<br>
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.<br>
<br>
At any time, Alice can unilaterally close the channel using any of the sign=
atures given by Bob.<br>
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.<br>
Alice needs to perform this unilateral close far before the pre-agreed lock=
time.<br>
<br>
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.<br>
<br>
Poon-Dryja<br>
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D<br>
<br>
A Poon-Dryja channel is a modern two-participant bidirectional channel.<br>
<br>
The core of security of Poon-Dryja involves &quot;revocable outputs&quot;.<=
br>
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).<br>
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.<br>
<br>
Poon-Dryja uses this building block to implement an updateable state.<br>
All states are represented by commitment transactions that have revocable o=
utputs.<br>
In order to advance to a new state, the revocable outputs of previous state=
s are revoked by exchanging revocation secrets.<br>
Thus, the security of Poon-Dryja is dependent on the correct operation of r=
evocation.<br>
<br>
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.=
<br>
<br>
Thus, a revocable output has two branches:<br>
<br>
* Revocation branch: with the revoker privkey and knowledge of a revocaatio=
n secret, the revoker can claim the fund immediately.<br>
* 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.<br>
<br>
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.<br>
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.<br>
<br>
Decker-Wattenhofer decrementing-`nSequence`<br>
=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<br>
<br>
Decker-Wattenhofer (&quot;Duplex Micropayment Channels&quot;) is a modern m=
ulti-participant (N &gt;=3D 2) offchain updateable cryptocurrency mechanism=
.<br>
<br>
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.<br>
<br>
* One or more decrementing-`nSequence` mechanisms, chained one inside the o=
ther.<br>
* Two (&quot;duplex&quot;) unidirectional Spilman variants, using a relativ=
e locktime instead of an absolute locktime, one in both directions of the c=
hannel, inside the innermost decrementing-`nSequence` mechanism.<br>
<br>
The decrementing-`nSequence` mechanisms by themselves are multiparticipant =
(N &gt;=3D 2), and if we focus only on having one or more of these mechanis=
ms chained together, we can consider Decker-Wattenhofer as multiparticipant=
.<br>
<br>
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.<br>
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.<br>
<br>
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.<br=
>
The new state transaction has a lower `nSequence` than the most previous st=
ate transaction, hence decrementing-`nSequence`.<br>
Once the latest state transaction has a 0-block relative locktime, a newer =
state can no longer be added to the mechanism.<br>
<br>
The kickoff n-of-n outpoint thus has multiple branches, one for each create=
d state.<br>
The most recent state is assumed to supersede previous states, because it h=
as the smallest relative locktime among all states.<br>
<br>
Under the MAD-HTLC argument, a participant which prefers an older state can=
 bribe miners to defer confirmation of all more recent states.<br>
Thus, that participant can publish the kickoff and bribe miners to defer mo=
re recent states until its preferred state is confirmable onchain.<br>
<br>
Decker-Russell-Osuntokun<br>
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D<br=
>
<br>
Decker-Russell-Osuntokun (&quot;eltoo&quot;) is a futuristic multiparticipa=
nt (N &gt;=3D 2) offchain updateable cryptocurrency system.<br>
<br>
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.<br>
<br>
As is typical for channel mechanisms, a funding outpoint is created, which =
is an n-of-n of all participants.<br>
The funding outpoint is spent by an update transaction with a single output=
, which has the following branches:<br>
<br>
* 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.<br>
* State branch: can be spent by a different n-of-n pubkeys from the same pa=
rticipants, after a relative locktime.<br>
=C2=A0 * Each update transaction has its own unique set of n-of-n pubkeys f=
or the state branch, given by the same participant set.<br>
<br>
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.<br>
Only the state branch has an actual timelock that could prevent immediate c=
onfirmation of a transaction spending that branch.<br>
<br>
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.<br>
<br>
Update transactions are signed with `SIGHASH_NOINPUT`.<br>
This allows the update transaction to not only spend the funding outpoint i=
tself, but also to spend any previous update transaction.<br>
<br>
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.<br>
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.<br>
<br>
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.<br>
<br>
Conclusion<br>
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D<br>
<br>
All the above mechanisms use a timelock, and implicitly have the assumption=
 that &quot;a transaction, that can be confirmed now, supersedes any transa=
ction that has a timelock that forces it to be confirmed later&quot;.<br>
<br>
It seems likely to me that even future mechanisms will use the same assumpt=
ion as well.<br>
<br>
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).<br>
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).<br>
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).<br>
<br>
Thus, we really need to carefully investigate the MAD-HTLC argument.<br>
<br>
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.<br>
But it would still be best to investigate further until we are fully convin=
ced that the MAD-HTLC argument (&quot;&#39;earlier supersedes later&#39; mi=
ght be falsified by bribery&quot;) does not apply.<br>
<br>
<br>
<br>
Regards,<br>
ZmnSCPxj<br>
</blockquote></div>

--000000000000a4611e05a9865c39--