diff options
author | ZmnSCPxj <ZmnSCPxj@protonmail.com> | 2020-07-03 12:38:37 +0000 |
---|---|---|
committer | bitcoindev <bitcoindev@gnusha.org> | 2020-07-03 12:38:49 +0000 |
commit | ca29ac06a9759d5623fc333d105d155bdf5e8534 (patch) | |
tree | d4ef714d303c6ab06f94d1b2bbc80abb8a1589a7 | |
parent | 99a7e176dab95a15523df17bb6c6e0f5f3ccfe22 (diff) | |
download | pi-bitcoindev-ca29ac06a9759d5623fc333d105d155bdf5e8534.tar.gz pi-bitcoindev-ca29ac06a9759d5623fc333d105d155bdf5e8534.zip |
Re: [bitcoin-dev] MAD-HTLC
-rw-r--r-- | 49/fbd78dc9295a3d8aeb1843d2bc435b0886c85f | 177 |
1 files changed, 177 insertions, 0 deletions
diff --git a/49/fbd78dc9295a3d8aeb1843d2bc435b0886c85f b/49/fbd78dc9295a3d8aeb1843d2bc435b0886c85f new file mode 100644 index 000000000..1c4562e0a --- /dev/null +++ b/49/fbd78dc9295a3d8aeb1843d2bc435b0886c85f @@ -0,0 +1,177 @@ +Return-Path: <ZmnSCPxj@protonmail.com> +Received: from fraxinus.osuosl.org (smtp4.osuosl.org [140.211.166.137]) + by lists.linuxfoundation.org (Postfix) with ESMTP id 181A5C0733 + for <bitcoin-dev@lists.linuxfoundation.org>; + 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 <bitcoin-dev@lists.linuxfoundation.org>; + 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 <bitcoin-dev@lists.linuxfoundation.org>; + 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 <bitcoin-dev@lists.linuxfoundation.org>; + 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 <sitay@campus.technion.ac.il> +From: ZmnSCPxj <ZmnSCPxj@protonmail.com> +Reply-To: ZmnSCPxj <ZmnSCPxj@protonmail.com> +Message-ID: <aclYsaioe3eOlsNxU1STxY6TOHstjBAsqxDKGln-D0A-p9J5-y2evQJdOe8DtWsK_iQioHxuc8J8eM8hXBihah_DudLzdKQ6mPPE8Dn5xkY=@protonmail.com> +In-Reply-To: <CAF-fr9Z7Xo8JmwtuQ7LE3k1=er+p7s9zPjH_8MNPwbxAfT1z7Q@mail.gmail.com> +References: <CABT1wW=X35HRVGuP-BHUhDrkBEw27+-iDkNnHWjRU-1mRkn0JQ@mail.gmail.com> + <CAAifmATmQSUUsEbouVYTNNMu-BT8vQiGvh3jwLNK4CUB11s7mg@mail.gmail.com> + <Fh70O0CqbkbLaOUEqRzIG3MOOZi_tYz69xRDPlIlF5tgTIPdYF9LyeoJjypo-agN9-WkuoXJD896R6CQygTozeHA_CFULp3k7007PioaDrs=@protonmail.com> + <CAAifmARxvG+_Wo3zba6MCd=jxwesb2JhWAwRErq6QPVTe1AQEA@mail.gmail.com> + <YhzMZ419vB1BY4Opd3lwfSSJ6_4AIQUDDtZPPhyB2HgskDZv0DKCQlEOAFklskLp1mj5AZrI43VPXOslX25MO-3Fijl9pBWrWYlYiaERr70=@protonmail.com> + <CAAifmATpg21K=yvi8OaPgr2esdtciu_uNLmNbA8983iht7Ru_Q@mail.gmail.com> + <-R0O_3IqpmbxNSONd1A2peCnpEIRs73ZELJgsBf06ygq4BGMo3Hg9h4OlXiGuIUyaITWixSY7LlgVyJ2MkAFQb7Y6I1gC8AXiAeS7eMlSso=@protonmail.com> + <CAAifmASfZbw3KgRBwbZoXwUmfpXGyaForwbVnh+KsB3+5s+WAg@mail.gmail.com> + <CAF-fr9Z7Xo8JmwtuQ7LE3k1=er+p7s9zPjH_8MNPwbxAfT1z7Q@mail.gmail.com> +MIME-Version: 1.0 +Content-Type: text/plain; charset=utf-8 +Content-Transfer-Encoding: quoted-printable +Cc: Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>, + Matan Yehieli <matany@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 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 + |