summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorZmnSCPxj <ZmnSCPxj@protonmail.com>2020-07-03 12:38:37 +0000
committerbitcoindev <bitcoindev@gnusha.org>2020-07-03 12:38:49 +0000
commitca29ac06a9759d5623fc333d105d155bdf5e8534 (patch)
treed4ef714d303c6ab06f94d1b2bbc80abb8a1589a7
parent99a7e176dab95a15523df17bb6c6e0f5f3ccfe22 (diff)
downloadpi-bitcoindev-ca29ac06a9759d5623fc333d105d155bdf5e8534.tar.gz
pi-bitcoindev-ca29ac06a9759d5623fc333d105d155bdf5e8534.zip
Re: [bitcoin-dev] MAD-HTLC
-rw-r--r--49/fbd78dc9295a3d8aeb1843d2bc435b0886c85f177
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
+