Return-Path: Received: from hemlock.osuosl.org (smtp2.osuosl.org [140.211.166.133]) by lists.linuxfoundation.org (Postfix) with ESMTP id 1375BC0733 for ; Thu, 2 Jul 2020 16:06:30 +0000 (UTC) Received: from localhost (localhost [127.0.0.1]) by hemlock.osuosl.org (Postfix) with ESMTP id 8CDD387E57 for ; Thu, 2 Jul 2020 16:06:29 +0000 (UTC) X-Virus-Scanned: amavisd-new at osuosl.org Received: from hemlock.osuosl.org ([127.0.0.1]) by localhost (.osuosl.org [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id hJlSvr+tZXY5 for ; Thu, 2 Jul 2020 16:06:27 +0000 (UTC) X-Greylist: domain auto-whitelisted by SQLgrey-1.7.6 Received: from mail-40141.protonmail.ch (mail-40141.protonmail.ch [185.70.40.141]) by hemlock.osuosl.org (Postfix) with ESMTPS id C12A68A4E3 for ; Thu, 2 Jul 2020 16:06:18 +0000 (UTC) Date: Thu, 02 Jul 2020 16:06:04 +0000 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=protonmail.com; s=protonmail; t=1593705975; bh=F4bOgecea8D2/xrViIRwvY4eflKH6AtD9+XYxlUdO48=; h=Date:To:From:Cc:Reply-To:Subject:In-Reply-To:References:From; b=RPt9b3zaCZrmLf9VA1Ln3QR+eHJukha+UvPtPFjUIOOmWbht4/dkgx0c6psdCyfUC jyoZACrW0fQO6MG/fqxS2TapdbgOZ8wJyHbp89GFX062mFhMogEg5cN+ImEM0q8c2s JEyiQpDBWa2tisYIEvr6fwcBJMUFJCxcxVW66j0Y= To: Tejaswi Nadahalli From: ZmnSCPxj Reply-To: ZmnSCPxj Message-ID: In-Reply-To: References: <20200628121517.f3l2mjcy7x4566v3@ganymede> MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: quoted-printable Cc: Matan Yehieli , Bitcoin Protocol Discussion , Itay Tsabary 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 List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Thu, 02 Jul 2020 16:06:30 -0000 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