From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from fraxinus.osuosl.org (smtp4.osuosl.org [140.211.166.137]) by lists.linuxfoundation.org (Postfix) with ESMTP id 181A5C0733 for ; Fri, 3 Jul 2020 12:38:49 +0000 (UTC) Received: from localhost (localhost [127.0.0.1]) by fraxinus.osuosl.org (Postfix) with ESMTP id 1429E87E0A for ; Fri, 3 Jul 2020 12:38:49 +0000 (UTC) X-Virus-Scanned: amavisd-new at osuosl.org Received: from fraxinus.osuosl.org ([127.0.0.1]) by localhost (.osuosl.org [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id hKpURWVmUAD0 for ; Fri, 3 Jul 2020 12:38:47 +0000 (UTC) X-Greylist: domain auto-whitelisted by SQLgrey-1.7.6 Received: from mail-40137.protonmail.ch (mail-40137.protonmail.ch [185.70.40.137]) by fraxinus.osuosl.org (Postfix) with ESMTPS id C21A587E06 for ; Fri, 3 Jul 2020 12:38:46 +0000 (UTC) Date: Fri, 03 Jul 2020 12:38:37 +0000 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=protonmail.com; s=protonmail; t=1593779924; bh=OwMaxwmGVTTwIOHruky4ZC2oZp9K3O9/GJSN01Yc3IA=; h=Date:To:From:Cc:Reply-To:Subject:In-Reply-To:References:From; b=C50SpylgCu/OS363vLB4uz9oCP9ZN95ZooVSDzz40PxbZynxTzNylOrCSA1VmW9Zj 14MICDVNCjcDrJok1KpN2NjS+e4CMpTD/wjs6Og6J32Q1f2b3PpXZUFw0gbRF8oxn1 sW1jG1C+QLPD3Ih6/hoRZ9Gnb/EgRtoAt8WRaFvQ= To: Itay Tsabary From: ZmnSCPxj Reply-To: ZmnSCPxj Message-ID: In-Reply-To: References: <-R0O_3IqpmbxNSONd1A2peCnpEIRs73ZELJgsBf06ygq4BGMo3Hg9h4OlXiGuIUyaITWixSY7LlgVyJ2MkAFQb7Y6I1gC8AXiAeS7eMlSso=@protonmail.com> MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: quoted-printable Cc: Bitcoin Protocol Discussion , Matan Yehieli 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: Fri, 03 Jul 2020 12:38:49 -0000 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=C2=A0myopic=C2=A0we mean a miner that optimizes tran= saction selection for the next block with respect only to the next block. T= he term=C2=A0non-myopic=C2=A0refers to a miner that optimizes transaction s= election for the next block with respect to several future blocks. To accom= modate for the stochastic=C2=A0nature of block creation these optimizations= are of the=C2=A0expected revenue.=C2=A0However,=C2=A0neither of these mean= that these miners choose to act in a way that reduces their expected reven= ue -- specifically, if from a=C2=A0non-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=C2=A0included=C2=A0in 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 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 strat= egy "contains" the other. Always-betray does not contain always-cooperate. It is immaterial that the non-myopic "contains" myopic strategy as a sub-st= rategy. 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-computer 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 rate = is actually non-myopic. Currently that answer is simple -- probably 0. Bitc= oin Core (97% of the blocks) doesn't offer these optimizations, and most li= kely 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 i= ncluded 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, es= pecially as mining incentives transition from block minting to fees -- the = latter are becoming the main income source, and I believe less sophisticate= d miners will miss out substantially. You can check out Phil Daian's paper = about front-running in Ethereum for example:=C2=A0https://arxiv.org/abs/190= 4.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 Kno= wledge=C2=A0-- all participants know all other participants, their availabl= e strategies and utilities=C2=A0(Tejaswi et al.'s paper makes the same assu= mption). As commented before, true, this is not always the case -- nodes mi= ght have different mempools, and some might not have applied the optimizati= on patch and act myopically. Such miners are therefore "resisting" the atta= ck -- as stated, by including Alice's transaction they ruin other miners' p= otential profit from Bob's high fee transaction. 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