1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
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
|
