Return-Path: Received: from hemlock.osuosl.org (smtp2.osuosl.org [140.211.166.133]) by lists.linuxfoundation.org (Postfix) with ESMTP id 4E91AC016F for ; Thu, 25 Jun 2020 03:26:57 +0000 (UTC) Received: from localhost (localhost [127.0.0.1]) by hemlock.osuosl.org (Postfix) with ESMTP id 42F4787BC8 for ; Thu, 25 Jun 2020 03:26:57 +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 yuqZkT2P+0Q2 for ; Thu, 25 Jun 2020 03:26:55 +0000 (UTC) X-Greylist: from auto-whitelisted by SQLgrey-1.7.6 Received: from mail-lj1-f194.google.com (mail-lj1-f194.google.com [209.85.208.194]) by hemlock.osuosl.org (Postfix) with ESMTPS id 3F2BE87BB1 for ; Thu, 25 Jun 2020 03:26:55 +0000 (UTC) Received: by mail-lj1-f194.google.com with SMTP id q19so4876454lji.2 for ; Wed, 24 Jun 2020 20:26:55 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=shesek.info; s=shesek; h=mime-version:references:in-reply-to:from:date:message-id:subject:to :cc; bh=BVO9HJZYKCWkTGaC/OteAA/e3WMK8hDhRDakODg0Mw0=; b=Bo8PDLA3goitzbc06WZT+6RN6jaV3jeSK0t2lLvW2wK82e3pHT4IDXVu87xio/L+SL dGK3PEohLBtupgQw3EdwoH5uAs3FWRWRlXU/c/Eomqd4+9omQMdmjWVaNDD3IppKhyoR g+giFktx5zxmz7jMrW71bT6GSEkvKnO9prLWQ= 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=BVO9HJZYKCWkTGaC/OteAA/e3WMK8hDhRDakODg0Mw0=; b=JGdOwVoEXqVYCrua8jqAZoUvR4a0Lgk4nq7NTjxZEisSR/n4iAg1bzG8mErUe8lJXE a5pDuzUKO4S307Gg/OfiDiiY5uSF5bpJydMjdily0K3tDJUyhG0InPvgOS1jZM//xuwB iKkYySdcB2H2pH2D+Vi6YmpxP8xPH0kSebAA3zjZIdvB4fuiNe7qaintRUFcDBMlsMUK TB/uTRXz/Xe9bs330CIC6Pgl0Emo0KWlSW9jZbbxx5Tj+9WrRRpduMFvZHzpUBe8146f 59daCICHcHCxfGS49jnZcTNLSg6daCsisfN2Qp/7tKLsWTmQp1a3OVEnix1yFWQRMu0d CZ7A== X-Gm-Message-State: AOAM530V2dsDzXqyOqWhPaPcmDq2/FlqiMbFelOyXhpEIaF5Sw9+v7rj Y6tYrPJVFEmQiWoFapdldkmQMWrApXRJctDTFDTFTw== X-Google-Smtp-Source: ABdhPJwKqQWpsgIVPv8EYpHkt6GajGyXvjAYvbArMlsi7mkgnSffhezc2AeaCpgZw6ciLVcTXjUwmRWoedOR1y3lDfI= X-Received: by 2002:a05:651c:106f:: with SMTP id y15mr4377576ljm.32.1593055612992; Wed, 24 Jun 2020 20:26:52 -0700 (PDT) MIME-Version: 1.0 References: In-Reply-To: From: Nadav Ivgi Date: Thu, 25 Jun 2020 06:26:41 +0300 Message-ID: To: ZmnSCPxj , Bitcoin Protocol Discussion Content-Type: multipart/alternative; boundary="000000000000ebb0fd05a8e02920" X-Mailman-Approved-At: Thu, 25 Jun 2020 12:45:36 +0000 Cc: Matan Yehieli , 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, 25 Jun 2020 03:26:57 -0000 --000000000000ebb0fd05a8e02920 Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable > I and some number of Lightning devs consider this to be sufficient disincentive to Bob not attacking in the first place. An additional disincentive could be introduced in the form of bribery proofs for failed attempts. If we assume that "honest" users of the LN protocol won't reveal their timelocked transactions before reaching the timelock expiry (they shouldn't anyway because standard full node implementations won't relay them), we can prove that Bob attempted bribery and failed to an outside observer by showing Bob's signed timelocked transaction, spending an output that was in reality spent by a different transaction prior to the locktime expiry, which should not be possible if Bob had waited. These proofs would be gossiped, and lightning network participants could choose not to peer with Bob when they see them. This might require some sort of a scoring/reputation scheme that makes it harder for Bob to attack with new throw-away identities to be effective. (i.e. limiting your exposure to peers to some BTC amount based on their historical public channels records, using fidelity bonds, etc.) Bob could still send these bribery transactions privately to selected miners, but not making them public would greatly reduce the participating miners' confidence that there is enough participating hashpower for the attack to be profitable. Nadav On Thu, Jun 25, 2020 at 4:38 AM ZmnSCPxj via bitcoin-dev < bitcoin-dev@lists.linuxfoundation.org> wrote: > Good morning Stanga et al, > > > > > Hi ZmnSCPxj, > > > > > > Thank you for taking the time to respond, these are very good points. > Responses inline. > > > > > > On Tue, Jun 23, 2020 at 12:48 PM ZmnSCPxj > wrote: > > > > > > > Good morning Itay, Ittay, and Matan, > > > > > > > > I believe an unstated assumption in Bitcoin is that miners are > short-sighted. > > > > > > > > The reasoning for this assumption is: > > > > > > > > * Deployment of new mining hardware controlled by others may occur > at any time you do not control. > > > > * Thus, any transactions you leave on the table are potentially > taken by somebody else and not by you. > > > > * Sudden changes in hashpower distribution may reduce your > expected future earnings, so any future theoretical earnings should be > discounted (*in addition to* expected return-on-investment on getting mon= ey > you can invest *now*). > > > > > > Our analysis assumes constant difficulty, i.e., no significant change= s > of the miners set. Indeed, hash-rate changes typically occur at a much > larger granularity than your average HTLC timeout. For instance, we notic= ed > plenty of lightning nodes use timeouts of a day. So, we do not consider > optimization at infinity, just a day ahead, and within this time frame al= l > the factors you mentioned are not expected to dramatically change. > > > > > > That being said, it would be interesting to analyze the effect of > miners joining during the HTLC duration. Intuitively, this shouldn=E2=80= =99t affect > the results, as those new miners have the same incentive to wait for the > higher-paying tx. > > We already know that hashrate tends to trend upwards, and that we do not > expect hashrate to fall except for occasional transients. > > The expectation is not that new miners have different incentives. > Instead, the expectation is that current miners discount future possible > gains because in the future, they expect to have less hashrate share than > right now. > > The only trustless way for Bob to bribe miners into deferring Alice tx is > to attach the bribe to the future confirmation of the Bob tx, thus Bob is > offering future-coins, not present-coins like Alice can offer, and the fa= ct > that miners expect an overall uptrend in total hashrate (leading to an > overall downtrend in their hashrate share) means that miners discount the > Bob offered future-coins. > The discounting is proportional to the time delay involved, as a larger > delay implies greater reduction in hashrate share. > > This discounting is, again, *in addition to* natural discounting a.k.a. "= I > will gladly pay you Thursday for a hamburger today", the hamburger seller > will want some pretty stiff assurances plus a bigger payment on Thursday > for giving you a hamburger today, due to expected returns on investment. > > > > > > > > > > > > It also strikes me that, in a world with RBF and CPFP, the same > endpoint (i.e. miners earn the entire fund of the HTLC) is achieved by > existing HTLCs, without the additional branch and script opcodes needed b= y > MAD-HTLC. > > > > For example, if an HTLC is confirmed but the hashlock-claiming > transaction is not being confirmed (because miners are holding it up > because Bob is offering a much higher fee in the future for the > timelock-claiming transaction), then Alice can, regardless of the reason > why it is not being confirmed, bump up the fee with RBF or CPFP. > > > > > > > > If the fee bump offered by Alice is sufficiently large, then miners > will start re-preferring the Alice hashlock transaction. > > > > To counter this, Bob has to bid up its version higher. > > > > > > > > As the timeout approaches, Alice can bump up its fee until it is > just 1 satoshi short of the total fund. > > > > It is rational for Alice to do so since at timeout, it can expect t= o > lose the entire fund. > > > > In order for Bob to win, it has to beat that fee, at which point it > equals or exceeds the total fund, and miners get the total fund (or more)= . > > > > > > > > Knowing this end-point, rational Bob will not even begin this game. > > > > > > > > I think this research considers these two endpoints to be distinct: > > > > > > > > * Bob misbehaves and the entire fund is punished by miners, leaving > miners with the fund and Alice and Bob without money (MAD-HTLC). > > > > * Bob misbehaves, Alice counters, and the ensuing fee war leads to > fees approaching the fund value, leaving miners with the fund and Alice a= nd > Bob without money (standard HTLC). > > > > > > > > But in practice I think both endpoints are essentially equivalent. > > > > > > These are not the same scenario, since in HTLC there is a race betwee= n > Alice and Bob. Alice might not wish to pay the full HTLC amount once she > sees Bob is trying to cheat. She could wait until close to the timeout so > as to reduce the time Bob can respond. Of course Bob would do the same. S= o > this is an actual race, and Bob takes no risk since his payment is all fr= om > the HTLC amount. Mutual destruction is only assured under certain > assumptions in HTLC. MAD-HTLC achieves security without relying on such > assumptions. > > Alice already knows that a rational Bob (who it might never interact with > again in the future) will take the funds at the locktime L. > Thus, Alice can offer, at time L - 1, the entire fund, minus 1 satoshi, t= o > miners. > Alice getting 1 satoshi versus 0 satoshi is a no-brainer for Alice. > Bob can only beat this offer by offering the entire fund, at which point > Bob earns nothing and it performed an attack for no benefit. > > I and some number of Lightning devs consider this to be sufficient > disincentive to Bob not attacking in the first place. > > > > > > > > > > > > -- > > > > > > > > What MAD-HTLC can do would be to make different claims: > > > > > > > > * Inputs: > > > > * Bob 1 BTC - HTLC amount > > > > * Bob 1 BTC - Bob fidelity bond > > > > > > > > * Cases: > > > > * Alice reveals hashlock at any time: > > > > * 1 BTC goes to Alice > > > > * 1 BTC goes to Bob (fidelity bond refund) > > > > * Bob reveals bob-hashlock after time L: > > > > * 2 BTC goes to Bob (HTLC refund + fidelity bond refund) > > > > * Bob cheated, anybody reveals both hashlock and bob-hashlock: > > > > * 2 BTC goes to miner > > > > > > > > This is an actual improvement over HTLC: Bob misbehavior leads to > loss of the fidelity bond. > > > > The above cases can be assured by requiring both Alice and Bob to > sign in the alice-hashlock branch, so that the splitting of the fund is > enforced, and SegWit signing so that the dependent transaction is signed > before the HTLC-funding transaction is. > > > > It can also be implemented with `OP_CHECKTEMPLATEVERIFY`. > > > > > > The cases you present are exactly how MAD-HTLC works. It comprises tw= o > contracts (UTXOs): > > > * Deposit (holding the intended HTLC tokens), with three redeem paths= : > > > - Alice (signature), with preimage "A", no timeout > > > - Bob (signature), with preimage "B", timeout T > > > - Any entity (miner), with both preimages "A" and "B", no timeout > > > * Collateral (the fidelity bond, doesn't have to be of the same amoun= t) > > > - Bob (signature), no preimage, timeout T > > > - Any entity (miner), with both preimages "A" and "B", timeout T > > > > > > Only Bob initially knows preimage "B", and is required to reveal it i= f > he wishes to get the Deposit tokens. > > > > > > Consider first the case where Alice publishes preimage "A": Bob can > safely publish preimage "B" and get both the Deposit and Collateral token= s > after the timeout. > > > Now, consider the case where Alice does not publish preimage "A": If > Bob publishes preimage "B" he gets nothing (and so does Alice - this is t= he > mutual assured destruction), and if he doesn't, he gets the Collateral > tokens. > > Thank you for the clarification. > > Regards, > ZmnSCPxj > > _______________________________________________ > bitcoin-dev mailing list > bitcoin-dev@lists.linuxfoundation.org > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev > --000000000000ebb0fd05a8e02920 Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable
>=20 I and some number of Lightning devs consider this to be sufficient disincen= tive to Bob not attacking in the first place.

An a= dditional disincentive could be introduced in the form of bribery proofs fo= r failed attempts.

If we assume that "honest" users of the LN protocol won'= ;t reveal their timelocked transactions before reaching the timelock expiry= (they shouldn't anyway because standard full node implementations won&= #39;t relay them), we can prove that Bob attempted bribery and failed to an= outside observer by showing Bob's= signed timelocked transaction, spending an output that was in reality spen= t by a different transaction prior to the locktime expiry, which should not= be possible if Bob had waited.

<= span class=3D"gmail-css-901oao gmail-css-16my406 gmail-r-1qd0xha gmail-r-ad= 9z0x gmail-r-bcqeeo gmail-r-qvutc0">These proofs would be gossiped, and ligh= tning network participants could choose not to peer with Bob when they see = them. This might require some sort of a scoring/reputation scheme that make= s it harder for Bob to attack with new throw-away identities to be effectiv= e. (i.e. limiting your exposure to peers to some BTC amount based on their = historical public channels records, using fidelity bonds, etc.)

Bob could still send = these bribery transactions privately to selected miners, but not making the= m public would greatly reduce the participating miners' confidence that= there is enough participating hashpower for the attack to be profitable.

Nadav

On Thu, Jun 25, 2020 at 4:38 AM ZmnSCPxj via bitcoin-dev <bitcoin-dev@lists.linuxf= oundation.org> wrote:
Good morning Stanga et al,


> > Hi ZmnSCPxj,=C2=A0
> >
> > Thank you for taking the time to respond, these are very good poi= nts. Responses inline.
> >
> > On Tue, Jun 23, 2020 at 12:48 PM ZmnSCPxj <ZmnSCPxj@protonmail.com> w= rote:
> >
> > > Good morning Itay, Ittay, and Matan,
> > >
> > > I believe an unstated assumption in Bitcoin is that miners a= re short-sighted.
> > >
> > > The reasoning for this assumption is:
> > >
> > > * Deployment of new mining hardware controlled by others may= occur at any time you do not control.
> > > =C2=A0 * Thus, any transactions you leave on the table are p= otentially taken by somebody else and not by you.
> > > =C2=A0 * Sudden changes in hashpower distribution may reduce= your expected future earnings, so any future theoretical earnings should b= e discounted (*in addition to* expected return-on-investment on getting mon= ey you can invest *now*).
> >
> > Our analysis assumes constant difficulty, i.e., no significant ch= anges of the miners set. Indeed, hash-rate changes typically occur at a muc= h larger granularity than your average HTLC timeout. For instance, we notic= ed plenty of lightning nodes use timeouts of a day. So, we do not consider = optimization at infinity, just a day ahead, and within this time frame all = the factors you mentioned are not expected to dramatically change.=C2=A0 > >
> > That being said, it would be interesting to analyze the effect of= miners joining during the HTLC duration. Intuitively, this shouldn=E2=80= =99t affect the results, as those new miners have the same incentive to wai= t for the higher-paying tx.

We already know that hashrate tends to trend upwards, and that we do not ex= pect hashrate to fall except for occasional transients.

The expectation is not that new miners have different incentives.
Instead, the expectation is that current miners discount future possible ga= ins because in the future, they expect to have less hashrate share than rig= ht now.

The only trustless way for Bob to bribe miners into deferring Alice tx is t= o attach the bribe to the future confirmation of the Bob tx, thus Bob is of= fering future-coins, not present-coins like Alice can offer, and the fact t= hat miners expect an overall uptrend in total hashrate (leading to an overa= ll downtrend in their hashrate share) means that miners discount the Bob of= fered future-coins.
The discounting is proportional to the time delay involved, as a larger del= ay implies greater reduction in hashrate share.

This discounting is, again, *in addition to* natural discounting a.k.a. &qu= ot;I will gladly pay you Thursday for a hamburger today", the hamburge= r seller will want some pretty stiff assurances plus a bigger payment on Th= ursday for giving you a hamburger today, due to expected returns on investm= ent.


> > =C2=A0
> >
> > > It also strikes me that, in a world with RBF and CPFP, the s= ame endpoint (i.e. miners earn the entire fund of the HTLC) is achieved by = existing HTLCs, without the additional branch and script opcodes needed by = MAD-HTLC.
> > > For example, if an HTLC is confirmed but the hashlock-claimi= ng transaction is not being confirmed (because miners are holding it up bec= ause Bob is offering a much higher fee in the future for the timelock-claim= ing transaction), then Alice can, regardless of the reason why it is not be= ing confirmed, bump up the fee with RBF or CPFP.
> > >
> > > If the fee bump offered by Alice is sufficiently large, then= miners will start re-preferring the Alice hashlock transaction.
> > > To counter this, Bob has to bid up its version higher.
> > >
> > > As the timeout approaches, Alice can bump up its fee until i= t is just 1 satoshi short of the total fund.
> > > It is rational for Alice to do so since at timeout, it can e= xpect to lose the entire fund.
> > > In order for Bob to win, it has to beat that fee, at which p= oint it equals or exceeds the total fund, and miners get the total fund (or= more).
> > >
> > > Knowing this end-point, rational Bob will not even begin thi= s game.
> > >
> > > I think this research considers these two endpoints to be di= stinct:
> > >
> > > * Bob misbehaves and the entire fund is punished by miners, = leaving miners with the fund and Alice and Bob without money (MAD-HTLC). > > > * Bob misbehaves, Alice counters, and the ensuing fee war le= ads to fees approaching the fund value, leaving miners with the fund and Al= ice and Bob without money (standard HTLC).
> > >
> > > But in practice I think both endpoints are essentially equiv= alent.
> >
> > These are not the same scenario, since in HTLC there is a race be= tween Alice and Bob. Alice might not wish to pay the full HTLC amount once = she sees Bob is trying to cheat. She could wait until close to the timeout = so as to reduce the time Bob can respond. Of course Bob would do the same. = So this is an actual race, and Bob takes no risk since his payment is all f= rom the HTLC amount. Mutual destruction is only assured under certain assum= ptions in HTLC. MAD-HTLC achieves security without relying on such assumpti= ons.=C2=A0

Alice already knows that a rational Bob (who it might never interact with a= gain in the future) will take the funds at the locktime L.
Thus, Alice can offer, at time L - 1, the entire fund, minus 1 satoshi, to = miners.
Alice getting 1 satoshi versus 0 satoshi is a no-brainer for Alice.
Bob can only=C2=A0 beat this offer by offering the entire fund, at which po= int Bob earns nothing and it performed an attack for no benefit.

I and some number of Lightning devs consider this to be sufficient disincen= tive to Bob not attacking in the first place.


> > =C2=A0
> >
> > > --
> > >
> > > What MAD-HTLC can do would be to make different claims:
> > >
> > > * Inputs:
> > > =C2=A0 * Bob 1 BTC - HTLC amount
> > > =C2=A0 * Bob 1 BTC - Bob fidelity bond
> > >
> > > * Cases:
> > > =C2=A0 * Alice reveals hashlock at any time:
> > > =C2=A0 =C2=A0 * 1 BTC goes to Alice
> > > =C2=A0 =C2=A0 * 1 BTC goes to Bob (fidelity bond refund)
> > > =C2=A0 * Bob reveals bob-hashlock after time L:
> > > =C2=A0 =C2=A0 * 2 BTC goes to Bob (HTLC refund + fidelity bo= nd refund)
> > > =C2=A0 * Bob cheated, anybody reveals both hashlock and bob-= hashlock:
> > > =C2=A0 =C2=A0 * 2 BTC goes to miner
> > >
> > > This is an actual improvement over HTLC: Bob misbehavior lea= ds to loss of the fidelity bond.
> > > The above cases can be assured by requiring both Alice and B= ob to sign in the alice-hashlock branch, so that the splitting of the fund = is enforced, and SegWit signing so that the dependent transaction is signed= before the HTLC-funding transaction is.
> > > It can also be implemented with `OP_CHECKTEMPLATEVERIFY`. > >
> > The cases you present are exactly how MAD-HTLC works. It comprise= s two contracts (UTXOs):
> > * Deposit (holding the intended HTLC tokens), with three redeem p= aths:
> > =C2=A0 =C2=A0 - Alice (signature), with preimage "A", n= o timeout
> > =C2=A0 =C2=A0 - Bob (signature), with preimage "B", tim= eout T
> > =C2=A0 =C2=A0 - Any entity (miner), with both preimages "A&q= uot; and "B", no timeout
> > * Collateral (the fidelity bond, doesn't have to be of the sa= me amount)
> > =C2=A0 =C2=A0 - Bob (signature), no preimage, timeout T
> > =C2=A0 =C2=A0 - Any entity (miner), with both preimages "A&q= uot; and "B", timeout T
> >
> > Only Bob initially knows preimage "B", and is required = to reveal it if he wishes to get the Deposit tokens.
> >
> > Consider first the case where Alice publishes preimage "A&qu= ot;: Bob can safely publish preimage "B" and get both the Deposit= and Collateral tokens after the timeout.
> > Now, consider the case where Alice does not publish preimage &quo= t;A": If Bob publishes preimage "B" he gets nothing (and so = does Alice - this is the mutual assured destruction), and if he doesn't= , he gets the Collateral tokens.

Thank you for the clarification.

Regards,
ZmnSCPxj

_______________________________________________
bitcoin-dev mailing list
= bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mail= man/listinfo/bitcoin-dev
--000000000000ebb0fd05a8e02920--