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
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
|
Return-Path: <dave@dtrt.org>
Received: from silver.osuosl.org (smtp3.osuosl.org [140.211.166.136])
by lists.linuxfoundation.org (Postfix) with ESMTP id C4088C016E
for <bitcoin-dev@lists.linuxfoundation.org>;
Sun, 28 Jun 2020 12:16:35 +0000 (UTC)
Received: from localhost (localhost [127.0.0.1])
by silver.osuosl.org (Postfix) with ESMTP id 94B5C20432
for <bitcoin-dev@lists.linuxfoundation.org>;
Sun, 28 Jun 2020 12:16:35 +0000 (UTC)
X-Virus-Scanned: amavisd-new at osuosl.org
Received: from silver.osuosl.org ([127.0.0.1])
by localhost (.osuosl.org [127.0.0.1]) (amavisd-new, port 10024)
with ESMTP id gq0GiRalJFXr
for <bitcoin-dev@lists.linuxfoundation.org>;
Sun, 28 Jun 2020 12:16:33 +0000 (UTC)
X-Greylist: from auto-whitelisted by SQLgrey-1.7.6
Received: from newmail.dtrt.org (li1228-87.members.linode.com [45.79.129.87])
by silver.osuosl.org (Postfix) with ESMTPS id 6858B20417
for <bitcoin-dev@lists.linuxfoundation.org>;
Sun, 28 Jun 2020 12:16:33 +0000 (UTC)
Received: from harding by newmail.dtrt.org with local (Exim 4.92)
(envelope-from <dave@dtrt.org>)
id 1jpWEZ-0002bq-95; Sun, 28 Jun 2020 08:16:31 -0400
Date: Sun, 28 Jun 2020 08:15:17 -0400
From: "David A. Harding" <dave@dtrt.org>
To: Stanga <stanga@gmail.com>,
Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Message-ID: <20200628121517.f3l2mjcy7x4566v3@ganymede>
References: <CABT1wW=X35HRVGuP-BHUhDrkBEw27+-iDkNnHWjRU-1mRkn0JQ@mail.gmail.com>
<CABT1wW=KWtoo6zHs8=yUQ7vAYcFSdAzdpDJ9yfw6sJrLd6dN5A@mail.gmail.com>
MIME-Version: 1.0
Content-Type: multipart/signed; micalg=pgp-sha512;
protocol="application/pgp-signature"; boundary="r7ohapeyprb3ykk3"
Content-Disposition: inline
In-Reply-To: <CABT1wW=KWtoo6zHs8=yUQ7vAYcFSdAzdpDJ9yfw6sJrLd6dN5A@mail.gmail.com>
User-Agent: NeoMutt/20180716
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: Sun, 28 Jun 2020 12:16:35 -0000
--r7ohapeyprb3ykk3
Content-Type: text/plain; charset=utf-8
Content-Disposition: inline
Content-Transfer-Encoding: quoted-printable
On Tue, Jun 23, 2020 at 09:41:56AM +0300, Stanga via bitcoin-dev wrote:
> Hi all,
>=20
> We'd like to bring to your attention our recent result concerning HTLC.
> Here are the technical report and a short post outlining the main points:
>=20
> * https://arxiv.org/abs/2006.12031
> * https://ittayeyal.github.io/2020-06-22-mad-htlc
Thank you for your interesting research! Further quotes are from your
paper:
> 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 wou=
ld
> 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.)
By comparison, "myopic" miners don't need to know anything special about
the past. They can just take the UTXO set, block height, difficulty
target, and last header hash and mine whatever available transactions
will give them the greatest next-block revenue.
In conclusion, I think:=20
1. Given that all known Bitcoin miners today are "myopic", there's no
short-term issue (to be clear, you didn't claim there was).
2. A very large percentage of the hashrate would have to implement
"rational" mining for the attack to become particularly effective.
Hopefully, we'd learn about this as it was happening and could adapt
before it became an issue.
3. So-called rational mining is probably a lot harder to implement
effectively than just 150 loc in Python; it probably requires a lot
more careful incentive analysis than just looking at HTLCs.[1]
4. Although I can't offer a proof, my intuition says that "myopic"
mining is probably very close to optimal in the current subsidy-fee
regime. Optimizing transaction selection only for the next block has
already proven to be quite challenging to both software and protocol
developers[2] so I can't imagine how much work it would take to build
something that effectively optimizes for an unbounded future. In
short, I think so-called myopic mining might actually be the most
rational mining we're capable of.
Nevertheless, I think your results are interesting and that MAD-HTLC is
a useful tool that might be particularly desirable in contracts that
involve especially high value or especially short timeouts (perhaps
asset swaps or payment channels used by traders?). Thank you again for
posting!
-Dave
[1] For example, your paper says "[...] the bribing cost required to
attack HTLC is independent in T, meaning that simply increasing the
timeout does contribute to HTLC=E2=80=99s security." This implies that
Alice, after she sees Bob's attempted bribe, could offer a counter
bribe that spends all output value to fees (the scorched earth
policy ZmnSCPxj describes) with a timelock set to the maximum
single-transaction value (block 500 million, due to be mined in
about 10 millennia, give or take a few centuries) and miners would
hold on to it until then, never mining Bob's lower-feerate bribe.
That's ridiculous, but it's understandable in your paper because
you're mainly analyzing time periods so short that you don't need to
worry much about the time-value-of-money discount (also mentioned by
ZmnSCPxj); however, your paper also says that your Python
implementation uses the same formulas in your paper to determine
whether or not a bribe will profitable, which would obviously be
wrong for a 10,000-year timelock.
[2] See the never ending discussions on this list and Lightning-Dev
about ancestor mining package size/depth limits and BIP125 opt-in
RBF rule #3.
--r7ohapeyprb3ykk3
Content-Type: application/pgp-signature; name="signature.asc"
-----BEGIN PGP SIGNATURE-----
iQIzBAEBCgAdFiEEgxUkqkMp0LnoXjCr2dtBqWwiadMFAl74idQACgkQ2dtBqWwi
adNmShAAmtcTRYxjozDgv/n6j1Hlq40lrNucJOYA/abRvDKTU/dXN1RmrpslzK0X
w2Piw0fI1mNRdX2MAnl8/PcBBmR4UNdg3hlZrTEDPtoJntp7trVKVwtZ47yQxaHE
zs4OtGHVereNJvexFtrPxYnzahGlQX3aDqblDaTR9ghgy70MZkw/k/LOTPekjz9w
KhVvjHJuFiGnD1d5FzCeJmCwQLmPW1gvqAFiO1CtP29wslUtyLhU6lJU561U34Kl
UQpSUZmK1CNnHiIiutNorxwFi/mwWN7zOYozTos6rMoZco9JYoOiH+Pkgta8HkjE
F/k0DrM5zZQfHPGF4amqhodhk2P+/9GdXXeeNIZuU4uR9JIML4RZ99OD16lJh1y+
3hiwTbsVKXbgd5Ce3gz1wm1rXQazxVxTK0uNj/a7PqshdVne3gYYFKlos9nLroei
sfQ4LoxsUaNiiokI0hzWiSZUMBL32z/+rUWd5cR10CMup/Nc2XvrOBBXXxTQHrwN
wPQjvkB1XduUOyvQbFgRhSu4mfMJOatgZ1lZNspVT00FPJx75a/ysaPoQxKiqztF
lFwaonUjt8jISThnIaopfiBP188jTVKCzYmEpHtrF9S/5IEsy/GmRAHrTeVX05oJ
to+pmCrSjnmCIde+eoohMUtvhQfcQ/RwyxINvN8ZAQ3PiqPWJjo=
=OplS
-----END PGP SIGNATURE-----
--r7ohapeyprb3ykk3--
|
