From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from silver.osuosl.org (smtp3.osuosl.org [140.211.166.136]) by lists.linuxfoundation.org (Postfix) with ESMTP id 08D38C016F for ; Sun, 5 Jul 2020 09:03:29 +0000 (UTC) Received: from localhost (localhost [127.0.0.1]) by silver.osuosl.org (Postfix) with ESMTP id CD7C9203B0 for ; Sun, 5 Jul 2020 09:03:28 +0000 (UTC) X-Virus-Scanned: amavisd-new at osuosl.org Received: from silver.osuosl.org ([127.0.0.1]) by localhost (.osuosl.org [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id HrrCMkycU+SJ for ; Sun, 5 Jul 2020 09:03:26 +0000 (UTC) X-Greylist: domain auto-whitelisted by SQLgrey-1.7.6 Received: from mail-ot1-f53.google.com (mail-ot1-f53.google.com [209.85.210.53]) by silver.osuosl.org (Postfix) with ESMTPS id AE4BD203A8 for ; Sun, 5 Jul 2020 09:03:26 +0000 (UTC) Received: by mail-ot1-f53.google.com with SMTP id d4so29565187otk.2 for ; Sun, 05 Jul 2020 02:03:26 -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=S/xtJSUBlahXAAk+pCvi7XTtSay8/OVDVN82cPUGdTw=; b=japUCs7FQUfWVIYRKyBRe3zM/hTIo1TQofYVJKIN/bHqdgY087wRTHW+TsC2rCvYsh TJE/eEmQA9lwezdJEV3QdOBXh0pxAMm3MiCfMahusslItegNLIigfVApBNVnMK/17zfb F9tNJM8qjOybqWDKRLZZWLVg15403U0fS3XYq+m/zPg3aGDQl1soE/zyZYf0V0ky9TJJ AmAAnpBEVIUbkJOFuJH9cq0UJxGFtnsMAdwOL8T5Sm3rIW754IwG2+06ucX7L2qpdSDU 802aJMIplmtRljKi8kLbZl9fAVH3xBkcUXri+BB7aCjAwD44+lyU6TWwi9uWIJPcnJFD FImA== 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=S/xtJSUBlahXAAk+pCvi7XTtSay8/OVDVN82cPUGdTw=; b=KytE0pdz9LwazKU/plvpw6d82GxNMDDR8xWIpureBG7svDSIsjImgSJeq7TzH/PPOG 0pkl8D/CmQmsIc4wgygqjxDcE7F+yQV1v0QIo7rKcmqNLUU2mXfflb/JIwBxfG2wrMLx RfCqIYGfMEUOj2g4JrBimphM1za6oOGdpzQJ5OeoMioHcrjajIZCF3qpibD/0mouF9zL 3QNdluVNTXYI87O3z/an311utY2i8n/V1FyejtkfvcmKvIR+laWIs+ePugcGx1DCZZQg KoRHv5TwE5kAw1B/0yGa78K8we9WDQ5zq2DVEZtosTmg+97soVKbc8TOKCAJAeAxvTFk jcZw== X-Gm-Message-State: AOAM533vuMn0xxo2vKnzzZgzTnVbgx7e1Esa/J0wNdAM2H8foXoljsRr LGYbl7ejkhmMycEKFM4ugB89quqYwQTptraKO5k= X-Google-Smtp-Source: ABdhPJye4uHa9t1GYL9J53sFpM1lsPPLVpdp+lo9X3ysLzt9gU5zS4KcMoje523tssFA8jsIHRzbS/V+wR/x2J8P6dc= X-Received: by 2002:a05:6830:151a:: with SMTP id k26mr38934480otp.363.1593939805614; Sun, 05 Jul 2020 02:03:25 -0700 (PDT) MIME-Version: 1.0 References: <-R0O_3IqpmbxNSONd1A2peCnpEIRs73ZELJgsBf06ygq4BGMo3Hg9h4OlXiGuIUyaITWixSY7LlgVyJ2MkAFQb7Y6I1gC8AXiAeS7eMlSso=@protonmail.com> In-Reply-To: From: Stanga Date: Sun, 5 Jul 2020 12:03:14 +0300 Message-ID: To: ZmnSCPxj , Bitcoin Protocol Discussion Content-Type: multipart/alternative; boundary="000000000000e8366005a9ae07e9" X-Mailman-Approved-At: Sun, 05 Jul 2020 09:10:51 +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: Sun, 05 Jul 2020 09:03:29 -0000 --000000000000e8366005a9ae07e9 Content-Type: text/plain; charset="UTF-8" Hi ZmnSCPxj, 1. If all miners are rational and non-myopic, they will support the attack. They don't need to cooperate, it's not the end of Bitcoin, but they all have to know everyone is rational and non-myopic. If you want to be secure in a situation like this then mad-htlc helps. Otherwise you can stick with htlc. To be clear, assuming it away means assuming at least some miners are altruistic or suboptimal. 2. I believe what Itay meant when he said myopic is included in non-myopic is that non-myopic will never choose a worse strategy than myopic. They both have the same utility function, but the non-myopic has more freedom. Specifically, if there are enough miners that are either irrational or myopic, and the bribe is small, then the best non-myopic strategy and the best myopic strategy is to not accept the bribe. (I think we're all in agreement on this one, it's just about terminology) Best, Ittay On Fri, Jul 3, 2020 at 3:38 PM ZmnSCPxj via bitcoin-dev < bitcoin-dev@lists.linuxfoundation.org> wrote: > Good morning Ittay, > > > Hi all, > > > > Itay from MAD-HTLC here. I feel like some details got lost along the way > so please let me get these sorted out. > > > > 1. Myopic and non-myopic miners: > > When we use the term myopic we mean a miner that optimizes transaction > selection for the next block with respect only to the next block. The > term non-myopic refers to a miner that optimizes transaction selection for > the next block with respect to several future blocks. To accommodate for > the stochastic nature of block creation these optimizations are of > the expected revenue. However, neither of these mean that these miners > choose to act in a way that reduces their expected revenue -- specifically, > if from a non-myopic's miner perspective including Alice's immediate > transaction is better off than waiting for Bob's future transaction, then > this is what they do. > > > > Consequently, saying that "being myopic" dominates "being non-myopic" is > incorrect -- myopic is included in being non-myopic, thus cannot be better > than it. > > The term "dominates" here is a technical term in game theory. > > A strategy dominates over another strategy if, in a mixed environment, the > first strategy always wins more points than the second strategy, no matter > what proportion they may initially start in the mixed environment. > > For example, in an environment of prisoner dilemma games, a tit-for-tat > strategy dominates over the always-betray strategy, which dominates over > always-cooperate strategy. > > The above is the use of the term "dominate", and not that somehow one > strategy "contains" the other. > Always-betray does not contain always-cooperate. > > It is immaterial that the non-myopic "contains" myopic strategy as a > sub-strategy. > Sometimes, overriding a sub-strategy can lead to worse outcomes and you > are better off sticking to the sub-strategy rather than an extended > strategy that sometimes overrides the sub-strategy > > (notice how mixed teams of computer+human are no longer dominant in chess, > because computer chess AIs are now so sophisticated that on average, the > human overriding the computer strategy often leads to worse outcomes than > just following the computer; yet about a decade ago such mixed > computer+human teams were dominant over pure-computer and pure-human teams; > yet you could say the same, that the computer+human "includes" the > pure-computer strategy, but nowadays does ***not*** dominate it). > > Or: worse is better. > > > What matters is, if you make them compete in an environment, myopic > strategies will consistently beat non-myopic strategies because the myopic > miners will impose costs on the non-myopic miners. > > > > > > So, the next issue to address is estimation of how much of the hash rate > is actually non-myopic. Currently that answer is simple -- probably 0. > Bitcoin Core (97% of the blocks) doesn't offer these optimizations, and > most likely other clients do not have these as well. But, we showed this is > rather trivial to implement (150 LoC in Bitcoin Core), and theoretically > can be included in Core's next version AFAIK. Moreover, any miner can > simply apply our patch independently, achieving the same effect. > > > > Please note more elaborate optimizations are in miners' best interest, > especially as mining incentives transition from block minting to fees -- > the latter are becoming the main income source, and I believe less > sophisticated miners will miss out substantially. You can check out Phil > Daian's paper about front-running in Ethereum for example: > https://arxiv.org/abs/1904.05234 > > Yes, but again: myopic strategies dominate over non-myopic strategies, > thus implementing non-myopic strategies is pointless, since they will lose > revenue in an environment where even a single miner is myopic. > > It is immaterial that it takes only 150 LoC to implement non-myopia: if it > earns less money in an environment where even a minority of blocks are > created by myopic miners (much less 97%), nobody will use the non-myopic > strategy and they will remain at negligible near-0% hashrate. > > As they say, "you can't get to there from here". > > > > As common in game-theory papers, our analysis does assume Common > Knowledge -- all participants know all other participants, their available > strategies and utilities (Tejaswi et al.'s paper makes the same > assumption). As commented before, true, this is not always the case -- > nodes might have different mempools, and some might not have applied the > optimization patch and act myopically. Such miners are therefore > "resisting" the attack -- as stated, by including Alice's transaction they > ruin other miners' potential profit from Bob's high fee transaction. > > The only additional assumption you are missing is that miners care about > *themselves* and not about *all miners*. > > Non-myopia may earn more money for *all* miners if *all* miners use it, > but if a *single* miner starts using myopic strategies in a non-myopic > environment, they will earn more funds than their non-myopic competitors > and thus dominate, shifting the percentages until almost all miners are > using myopic strategies. > That they require less processing ("keep it simple, sir") is just gravy on > top. > > > The only way for non-myopic miners to win is to form a cartel, and a miner > cartel with >50% hashpower would be the end of Bitcoin anyway. > > > Regards, > ZmnSCPxj > _______________________________________________ > bitcoin-dev mailing list > bitcoin-dev@lists.linuxfoundation.org > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev > --000000000000e8366005a9ae07e9 Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable
Hi ZmnSCPxj,

1. If all miners are= rational and non-myopic, they will support the attack. They don't need= to cooperate, it's not the end of Bitcoin, but they all have to know e= veryone is rational and non-myopic. If you want to be secure in a situation= like this then mad-htlc helps. Otherwise you can stick with htlc. To be cl= ear, assuming it away means assuming at least some miners are altruistic or= suboptimal.

2. I believe what Itay meant when he said myopic is in= cluded in non-myopic is that non-myopic will never choose a worse strategy = than myopic. They both have the same utility function, but the non-myopic h= as more freedom. Specifically, if there are enough miners that are either i= rrational or myopic, and the bribe is small, then the best non-myopic strat= egy and the best myopic strategy is to not accept the bribe. (I think we= 9;re all in agreement on this one, it's just about terminology)
Best,
Ittay=C2=A0


On Fri, Jul 3, 2020 at 3:38 PM Zmn= SCPxj via bitcoin-dev <bitcoin-dev@lists.linuxfoundation.org> wrote:
Good morning Ittay,

> Hi all,
>
> Itay from MAD-HTLC here. I feel like some details got lost along the w= ay so please let me get these sorted out.
>
> 1. Myopic and non-myopic miners:
> When we use the term=C2=A0myopic=C2=A0we mean a miner that optimizes t= ransaction selection for the next block with respect only to the next block= . The term=C2=A0non-myopic=C2=A0refers to a miner that optimizes transactio= n selection for the next block with respect to several future blocks. To ac= commodate for the stochastic=C2=A0nature of block creation these optimizati= ons are of the=C2=A0expected revenue.=C2=A0However,=C2=A0neither of these m= ean that these miners choose to act in a way that reduces their expected re= venue -- specifically, if from a=C2=A0non-myopic's miner perspective in= cluding Alice's immediate transaction is better off than waiting for Bo= b's future transaction, then this is what they do.
>
> Consequently, saying that "being myopic" dominates "bei= ng non-myopic" is incorrect -- myopic is=C2=A0included=C2=A0in being n= on-myopic, thus cannot be better than it.

The term "dominates" here is a technical term in game theory.

A strategy dominates over another strategy if, in a mixed environment, the = first strategy always wins more points than the second strategy, no matter = what proportion they may initially start in the mixed environment.

For example, in an environment of prisoner dilemma games, a tit-for-tat str= ategy dominates over the always-betray strategy, which dominates over alway= s-cooperate strategy.

The above is the use of the term "dominate", and not that somehow= one strategy "contains" the other.
Always-betray does not contain always-cooperate.

It is immaterial that the non-myopic "contains" myopic strategy a= s a sub-strategy.
Sometimes, overriding a sub-strategy can lead to worse outcomes and you are= better off sticking to the sub-strategy rather than an extended strategy t= hat sometimes overrides the sub-strategy

(notice how mixed teams of computer+human are no longer dominant in chess, = because computer chess AIs are now so sophisticated that on average, the hu= man overriding the computer strategy often leads to worse outcomes than jus= t following the computer; yet about a decade ago such mixed computer+human = teams were dominant over pure-computer and pure-human teams; yet you could = say the same, that the computer+human "includes" the pure-compute= r strategy, but nowadays does ***not*** dominate it).

Or: worse is better.


What matters is, if you make them compete in an environment, myopic strateg= ies will consistently beat non-myopic strategies because the myopic miners = will impose costs on the non-myopic miners.


>
> So, the next issue to address is estimation of how much of the hash ra= te is actually non-myopic. Currently that answer is simple -- probably 0. B= itcoin Core (97% of the blocks) doesn't offer these optimizations, and = most likely other clients do not have these as well. But, we showed this is= rather trivial to implement (150 LoC in Bitcoin Core), and theoretically c= an be included in Core's next version AFAIK. Moreover, any miner can si= mply apply our patch independently, achieving the same effect.
>
> Please note more elaborate optimizations are in miners' best inter= est, especially as mining incentives transition from block minting to fees = -- the latter are becoming the main income source, and I believe less sophi= sticated miners will miss out substantially. You can check out Phil Daian&#= 39;s paper about front-running in Ethereum for example:=C2=A0https:/= /arxiv.org/abs/1904.05234

Yes, but again: myopic strategies dominate over non-myopic strategies, thus= implementing non-myopic strategies is pointless, since they will lose reve= nue in an environment where even a single miner is myopic.

It is immaterial that it takes only 150 LoC to implement non-myopia: if it = earns less money in an environment where even a minority of blocks are crea= ted by myopic miners (much less 97%), nobody will use the non-myopic strate= gy and they will remain at negligible near-0% hashrate.

As they say, "you can't get to there from here".


> As common in game-theory papers, our analysis does assume=C2=A0Common = Knowledge=C2=A0-- all participants know all other participants, their avail= able strategies and utilities=C2=A0(Tejaswi et al.'s paper makes the sa= me assumption). As commented before, true, this is not always the case -- n= odes might have different mempools, and some might not have applied the opt= imization patch and act myopically. Such miners are therefore "resisti= ng" the attack -- as stated, by including Alice's transaction they= ruin other miners' potential profit from Bob's high fee transactio= n.

The only additional assumption you are missing is that miners care about *t= hemselves* and not about *all miners*.

Non-myopia may earn more money for *all* miners if *all* miners use it, but= if a *single* miner starts using myopic strategies in a non-myopic environ= ment, they will earn more funds than their non-myopic competitors and thus = dominate, shifting the percentages until almost all miners are using myopic= strategies.
That they require less processing ("keep it simple, sir") is just= gravy on top.


The only way for non-myopic miners to win is to form a cartel, and a miner = cartel with >50% hashpower would be the end of Bitcoin anyway.


Regards,
ZmnSCPxj
_______________________________________________
bitcoin-dev mailing list
= bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mail= man/listinfo/bitcoin-dev
--000000000000e8366005a9ae07e9--