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
|
Return-Path: <ZmnSCPxj@protonmail.com>
Received: from hemlock.osuosl.org (smtp2.osuosl.org [140.211.166.133])
by lists.linuxfoundation.org (Postfix) with ESMTP id D4074C016E
for <bitcoin-dev@lists.linuxfoundation.org>;
Mon, 29 Jun 2020 18:05:19 +0000 (UTC)
Received: from localhost (localhost [127.0.0.1])
by hemlock.osuosl.org (Postfix) with ESMTP id BFC3C893A2
for <bitcoin-dev@lists.linuxfoundation.org>;
Mon, 29 Jun 2020 18:05:19 +0000 (UTC)
X-Virus-Scanned: amavisd-new at osuosl.org
Received: from hemlock.osuosl.org ([127.0.0.1])
by localhost (.osuosl.org [127.0.0.1]) (amavisd-new, port 10024)
with ESMTP id 2xiZ3AbPXPGj
for <bitcoin-dev@lists.linuxfoundation.org>;
Mon, 29 Jun 2020 18:05:18 +0000 (UTC)
X-Greylist: domain auto-whitelisted by SQLgrey-1.7.6
Received: from mail-40132.protonmail.ch (mail-40132.protonmail.ch
[185.70.40.132])
by hemlock.osuosl.org (Postfix) with ESMTPS id DC8DE89394
for <bitcoin-dev@lists.linuxfoundation.org>;
Mon, 29 Jun 2020 18:05:17 +0000 (UTC)
Date: Mon, 29 Jun 2020 18:05:10 +0000
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=protonmail.com;
s=protonmail; t=1593453915;
bh=jHxUZ9WM3RJtFLYTOJyqim+EjObGyCjJeQR4RGx/R2I=;
h=Date:To:From:Cc:Reply-To:Subject:In-Reply-To:References:From;
b=mAiCV+DrX/0MqzDkysCXqHQhV2v6ZA64i4iex8mkVD4ewx0zmAlr4b6a4Kj6pke3G
vuL9XJfPfdM6h9pBzGF1jGPx0Sq3Ku/TKWWCVD81GonbXilE6aGpmM41FPq7JHG9ze
Gnjwzxhusz9l6zAmhJbTYGtGrUx4g7BdFfc8sMks=
To: "David A. Harding" <dave@dtrt.org>,
Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
From: ZmnSCPxj <ZmnSCPxj@protonmail.com>
Reply-To: ZmnSCPxj <ZmnSCPxj@protonmail.com>
Message-ID: <WYQRrIi65yvBWc9qsqCxHWadrMFtYPh2wI-IzVS15FBTFmpIXqHwj5yrj3Igpr-9sKygWsH4DkI_maWcULKKQb51Xp_xZBvKuPF_HmCvqb4=@protonmail.com>
In-Reply-To: <20200628121517.f3l2mjcy7x4566v3@ganymede>
References: <CABT1wW=X35HRVGuP-BHUhDrkBEw27+-iDkNnHWjRU-1mRkn0JQ@mail.gmail.com>
<CABT1wW=KWtoo6zHs8=yUQ7vAYcFSdAzdpDJ9yfw6sJrLd6dN5A@mail.gmail.com>
<20200628121517.f3l2mjcy7x4566v3@ganymede>
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: quoted-printable
Cc: Matan Yehieli <matany@campus.technion.ac.il>,
Itay Tsabary <sitay@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: Mon, 29 Jun 2020 18:05:19 -0000
Good morning Dave, et al.,
> > Myopic Miners: This bribery attack relies on all miners
> >
> >
> > being rational, hence considering their utility at game conclu-
> > sion instead of myopically optimizing for the next block. If
> > a portion of the miners are myopic and any of them gets to
> > create a block during the first T =E2=88=92 1 rounds, that miner would
> > include Alice=E2=80=99s transaction and Bob=E2=80=99s bribery attempt w=
ould
> > have failed.
> > In such scenarios the attack succeeds only with a certain
> > probability =E2=80=93 only if a myopic miner does not create a block
> > in the first T =E2=88=92 1 rounds. The success probability therefore
> > decreases exponentially in T . Hence, to incentivize miners
> > to support the attack, Bob has to increase his offered bribe
> > exponentially in T .
>
> This is a good abstract description, but I think it might be useful for
> readers of this list who are wondering about the impact of this attack
> to put it in concrete terms. I'm bad at statistics, but I think the
> probability of bribery failing (even if Bob offers a bribe with an
> appropriately high feerate) is 1-exp(-b*h) where `b` is the number of
> blocks until timeout and `h` is a percentage of the hashrate controlled
> by so-called myopic miners. Given that, here's a table of attack
> failure probabilities:
>
> "Myopic" hashrate
> B 1% 10% 33% 50%
> l +---------------------------------
> o 6 | 5.82% 45.12% 86.19% 95.02%
> c 36 | 30.23% 97.27% 100.00% 100.00%
> k 144 | 76.31% 100.00% 100.00% 100.00%
> s 288 | 94.39% 100.00% 100.00% 100.00%
>
> So, if I understand correctly, even a small amount of "myopic" hashrate
> and long timeouts---or modest amounts of hashrate and short
> timeouts---makes this attack unlikely to succeed (and, even in the cases
> where it does succeed, Bob will have to offer a very large bribe to
> compensate "rational" miners for their high chance of losing out on
> gaining any transaction fees).
>
> Additionally, I think there's the problem of measuring the distribution
> of "myopic" hashrate versus "rational" hashrate. "Rational" miners need
> to do this in order to ensure they only accept Bob's timelocked bribe if
> it pays a sufficiently high fee. However, different miners who try to
> track what bribes were relayed versus what transactions got mined may
> come to different conclusions about the relative hashrate of "myopic"
> miners, leading some of them to require higher bribes, which may lead
> those those who estimated a lower relative hash rate to assume the rate
> of "myopic" mining in increasing, producing a feedback loop that makes
> other miners think the rate of "myopic" miners is increasing. (And that
> assumes none of the miners is deliberately juking the stats to mislead
> its competitors into leaving money on the table.)
A thought occurs to me, that we should not be so hasty to call non-myopic s=
trategy "rational".
Let us consider instead "myopic" and "non-myopic" strategies in a populatio=
n of miners.
I contend that in a mixed population of "myopic" and "non-myopic" miners, t=
he myopic strategy is dominant in the game-theoretic sense, i.e. it might e=
arn less if all miners were myopic, but if most miners were non-myopic and =
a small sub-population were myopic and there was no easy way for non-myopic=
miners to punish myopic miners, then the myopic miners will end up earning=
more (at the expense of the non-myopic miners) and dominate over non-myopi=
c miners.
Such dominant result should prevent non-myopic miners from arising in the f=
irst place.
The dominance results from the fact that by accepting the Alice transaction=
, myopic miners are effectively deducting the fees earned by non-myopic min=
ers by preventing the Bob transaction from being confirmable.
On the other hand, even if the non-myopic miners successfully defer the Ali=
ce transaction, the myopic miner still has a chance equal to its hashrate o=
f getting the Bob transaction and its attached fee.
Thus, myopic miners impose costs on their non-myopic competitors that non-m=
yopic miners cannot impose their myopic competitors.
If even one myopic miner successfully gets the Alice transaction confirmed,=
all the non-myopic miners lose out on the Bob bribe fee.
So I think the myopic strategy will be dominant and non-myopic miners will =
not arise in the first place.
Regards,
ZmnSCPxj
|
