summaryrefslogtreecommitdiff
path: root/eb/ff5bfc1d359fd3bdcf09039fdf1c278747db67
blob: 9dd2b82e86a31ce17d729e2caec3caae35326582 (plain)
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
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
Return-Path: <nadahalli@gmail.com>
Received: from hemlock.osuosl.org (smtp2.osuosl.org [140.211.166.133])
 by lists.linuxfoundation.org (Postfix) with ESMTP id A120FC0733
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Thu,  2 Jul 2020 12:23:04 +0000 (UTC)
Received: from localhost (localhost [127.0.0.1])
 by hemlock.osuosl.org (Postfix) with ESMTP id 8D05F8A998
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Thu,  2 Jul 2020 12:23:04 +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 vOlbf0CdYvek
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Thu,  2 Jul 2020 12:23:03 +0000 (UTC)
X-Greylist: domain auto-whitelisted by SQLgrey-1.7.6
Received: from mail-pg1-f179.google.com (mail-pg1-f179.google.com
 [209.85.215.179])
 by hemlock.osuosl.org (Postfix) with ESMTPS id 920818A840
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Thu,  2 Jul 2020 12:23:03 +0000 (UTC)
Received: by mail-pg1-f179.google.com with SMTP id o13so10428763pgf.0
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Thu, 02 Jul 2020 05:23:03 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025;
 h=mime-version:references:in-reply-to:from:date:message-id:subject:to
 :cc; bh=yWnN8HHEnKcgEjXTnVyjpz1/10TwyNecE7rWdwoN5/M=;
 b=LslQBwiKKXyeveupjnOIyJZ9NGXa6n0sjdCtikUabvHiz26NtFRwj1A2wWEgNt9ccX
 Knv8iMlkRIuaaxa4cPe7xGYxv6Fn9cEh8e4eT39rlXH7Yf2amkmheyer7KOlkO6rWw1P
 F6IVpSWh6GL6tjofWT3emDxbHyqI5Mdl266M6enxS3vRrihlBPJOzpSi0pZcDXVDZW90
 AvxYKEp6uaKqug9Qv0mVtRcVckBVBvTJI/Cqxo+jr9THH/cl99iPFOn+lje37rUOf+8x
 EUq7yqaxtauhe+4cEcULoFVCU6f3R4htyJmE5XNGQdR4Pb6SPN0jUL7WJ9P14KMPvEpZ
 3amg==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
 d=1e100.net; s=20161025;
 h=x-gm-message-state:mime-version:references:in-reply-to:from:date
 :message-id:subject:to:cc;
 bh=yWnN8HHEnKcgEjXTnVyjpz1/10TwyNecE7rWdwoN5/M=;
 b=NG4wKIaocYWLI5ub5YxE6IqGulAVULeOHuMgVuy6XPEq/C73lGVexqiNyxNN1RNaxk
 FHVmobyCkaxLUxccpFTmaGx2T9fB8qcpepqVwkorMhKff2FE03uQmZr/eKoJ9bJBiT0p
 kQEKTHuvSaLP7oW+AWCEwqwCS9C2WNzx90In90d4DuIoYKsURBEuh1BRSyvDVxf0v4V3
 rK2/grvkR3yE0zVw/V9d4kyBvLFBqnBtDi1d2BrQoQzIoKRqopr0DWX0CcvjJqmFYnXz
 519SEsLq+17C5lMwBIPCoZ0nJS5Ctuf81ocSU51u194hpOI7XnHNWkDxb4JuKw1zWaE5
 6BAA==
X-Gm-Message-State: AOAM531PwxTumEc9uI6Ds6x2RfB0mjbHU/FWBYmABnbPdqnqPXUN5hwD
 cZTvxr7RHF1aF5rgUjrTbG5//z9k6fyX11BZmpc=
X-Google-Smtp-Source: ABdhPJzR4HeiPyvpOQm8dBJCMs8cuTg2hyeZORE2E36tjQaS7bR0hk4kondd1Rnh4DdtPeOzdZtE23Joyy+PFeUNIXM=
X-Received: by 2002:a63:b255:: with SMTP id t21mr15201567pgo.78.1593692582905; 
 Thu, 02 Jul 2020 05:23:02 -0700 (PDT)
MIME-Version: 1.0
References: <CABT1wW=X35HRVGuP-BHUhDrkBEw27+-iDkNnHWjRU-1mRkn0JQ@mail.gmail.com>
 <CABT1wW=KWtoo6zHs8=yUQ7vAYcFSdAzdpDJ9yfw6sJrLd6dN5A@mail.gmail.com>
 <20200628121517.f3l2mjcy7x4566v3@ganymede>
 <WYQRrIi65yvBWc9qsqCxHWadrMFtYPh2wI-IzVS15FBTFmpIXqHwj5yrj3Igpr-9sKygWsH4DkI_maWcULKKQb51Xp_xZBvKuPF_HmCvqb4=@protonmail.com>
 <CAAifmATmQSUUsEbouVYTNNMu-BT8vQiGvh3jwLNK4CUB11s7mg@mail.gmail.com>
 <Fh70O0CqbkbLaOUEqRzIG3MOOZi_tYz69xRDPlIlF5tgTIPdYF9LyeoJjypo-agN9-WkuoXJD896R6CQygTozeHA_CFULp3k7007PioaDrs=@protonmail.com>
In-Reply-To: <Fh70O0CqbkbLaOUEqRzIG3MOOZi_tYz69xRDPlIlF5tgTIPdYF9LyeoJjypo-agN9-WkuoXJD896R6CQygTozeHA_CFULp3k7007PioaDrs=@protonmail.com>
From: Tejaswi Nadahalli <nadahalli@gmail.com>
Date: Thu, 2 Jul 2020 14:22:51 +0200
Message-ID: <CAAifmARxvG+_Wo3zba6MCd=jxwesb2JhWAwRErq6QPVTe1AQEA@mail.gmail.com>
To: ZmnSCPxj <ZmnSCPxj@protonmail.com>
Content-Type: multipart/alternative; boundary="000000000000490db305a97478cf"
X-Mailman-Approved-At: Thu, 02 Jul 2020 13:29:09 +0000
Cc: Matan Yehieli <matany@campus.technion.ac.il>,
 Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>,
 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: Thu, 02 Jul 2020 12:23:04 -0000

--000000000000490db305a97478cf
Content-Type: text/plain; charset="UTF-8"

On Wed, Jul 1, 2020 at 6:58 PM ZmnSCPxj <ZmnSCPxj@protonmail.com> wrote:

> And your paper posits that if a miner is weak, its best strategy is to
> take the myopic strategy and include the currently-valid Alice transaction.
>

Yes. The proof is quite trivial and follows from the definition of weak: if
the myopic miner's hashpower percentage is p_i, and it's lower than f/b,
that means that f > b*p_i. By including the currently-valid Alice
transaction, the myopic miner could make f, which is higher than their
expected gain, which is b*p_i. The myopic miner has a p_i chance of mining
the first block when Bob's transaction becomes valid, and it's most likely
to stay valid for just 1 block, as every miner would want that immediately
when it gets valid. This is where we disagree with the MAD-HTLC paper. They
assume that there are not any miners with sub-1% hashrate around. We find
that there are many such miners, and with channel_reserve_satoshi set to 1%
of the channel value, Alice can bump her fees to at least 1% of the channel
value without worry (because she will get Bob's channel_reserve_satoshi's
for herself if Bob is cheating by releasing a previous commitment TXN).

We additionally also show that when strong miners know that weak miners are
around, some of their strategies get dominated as well, and they will be
forced to include Alice's transaction as well. This, if there is just one
*known* weak miner, things are good for Alice. As an FYI, in our paper
Alice is the cheater and Bob is the victim. There were reasons to "reverse
the convention", so to speak - but that's for another day :-)


>
> Thus, if Alice even *matches* Bob, it seems to me that this ratio f / b is
> 1.0 implying a miner can only be powerful if it has already 51%-attacked
> Bitcoin (which tends to invalidate all our security assumptions of
> higher-layer protocols anyway, since a 51% attacker can censor anything
> with impunity).
>

We assume that Bob will bribe with the entire channel value - because he
has received commensurate goods and services off-chain. So, Alice will find
it difficult to match Bob's bribe, but she doesn't have to.


>
> Of course, Bob can offer up to the entire fund amount, for free, to miners
> as a bribe, without loss to Bob.
>

Yes. Precisely.


>
> For more realistic scenarios where no miner has 100% hashrate, then Alice
> can make all miners weak by being willing to pay up to 50% of the fund as
> fee, as a miner that achieves greater than 50% hashrate share would already
> effectively pwnzored Bitcoin and gained UNLIMITED POWAH anyway.
>

But she doesn't have to go as far as 50%. Just 1% seems quite reasonable,
given a reasonable timelock. We have a closed form solution for the
timelock T as well. In Lightning's case, with 1% channel_reserve_satoshis
around, we arrive at T = 316, which is much longer than the current default
of 144.


>
> So it looks to me that scorched-earth is a possible mitigation against
> this attack.
>

I don't follow this. We show that a reasonable value of fees and timelock
are enough to avoid the attack. Why scorch the earth?

--000000000000490db305a97478cf
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr"><div dir=3D"ltr">On Wed, Jul 1, 2020 at 6:58 PM ZmnSCPxj &=
lt;<a href=3D"mailto:ZmnSCPxj@protonmail.com">ZmnSCPxj@protonmail.com</a>&g=
t; wrote:<br></div><div class=3D"gmail_quote"><blockquote class=3D"gmail_qu=
ote" style=3D"margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,20=
4);padding-left:1ex">And your paper posits that if a miner is weak, its bes=
t strategy is to take the myopic strategy and include the currently-valid A=
lice transaction.<br></blockquote><div><br></div><div>Yes. The proof is qui=
te trivial and follows from the definition of weak: if the myopic miner&#39=
;s hashpower percentage is p_i, and it&#39;s lower than f/b, that means tha=
t f &gt; b*p_i. By including the currently-valid Alice transaction, the myo=
pic miner could make f, which is higher than their expected gain, which is =
b*p_i. The myopic miner has a p_i chance of mining the first block when Bob=
&#39;s transaction becomes valid, and it&#39;s most likely to stay valid fo=
r just 1 block, as every miner would want that immediately when it gets val=
id. This is where we disagree with the MAD-HTLC paper. They assume that the=
re are not any miners with sub-1% hashrate around. We find that there are m=
any such miners, and with channel_reserve_satoshi set to 1% of the channel =
value, Alice can bump her fees to at least 1% of the channel value without =
worry (because she will get Bob&#39;s channel_reserve_satoshi&#39;s for her=
self if Bob is cheating by releasing a previous commitment TXN).</div><div>=
<br></div><div>We additionally also show that when strong miners know that =
weak miners are around, some of their strategies get dominated as well, and=
 they will be forced to include Alice&#39;s transaction as well. This, if t=
here is just one *known* weak miner, things are good for Alice. As an FYI, =
in our paper Alice is the cheater and Bob is the victim. There were reasons=
 to &quot;reverse the convention&quot;, so to speak - but that&#39;s for an=
other day :-)</div><div>=C2=A0</div><blockquote class=3D"gmail_quote" style=
=3D"margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding=
-left:1ex">
<br>
Thus, if Alice even *matches* Bob, it seems to me that this ratio f / b is =
1.0 implying a miner can only be powerful if it has already 51%-attacked Bi=
tcoin (which tends to invalidate all our security assumptions of higher-lay=
er protocols anyway, since a 51% attacker can censor anything with impunity=
).<br></blockquote><div><br></div><div>We assume that Bob will bribe with t=
he entire channel value - because he has received commensurate goods and se=
rvices off-chain. So, Alice will find it difficult to match Bob&#39;s bribe=
, but she doesn&#39;t have to.=C2=A0</div><div>=C2=A0</div><blockquote clas=
s=3D"gmail_quote" style=3D"margin:0px 0px 0px 0.8ex;border-left:1px solid r=
gb(204,204,204);padding-left:1ex">
<br>
Of course, Bob can offer up to the entire fund amount, for free, to miners =
as a bribe, without loss to Bob.<br></blockquote><div><br></div><div>Yes. P=
recisely.</div><div>=C2=A0</div><blockquote class=3D"gmail_quote" style=3D"=
margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-lef=
t:1ex">
<br>
For more realistic scenarios where no miner has 100% hashrate, then Alice c=
an make all miners weak by being willing to pay up to 50% of the fund as fe=
e, as a miner that achieves greater than 50% hashrate share would already e=
ffectively pwnzored Bitcoin and gained UNLIMITED POWAH anyway.<br></blockqu=
ote><div><br></div><div>But she doesn&#39;t have to go as far as 50%. Just =
1% seems quite reasonable, given a reasonable timelock. We have a closed fo=
rm solution for the timelock T as well. In Lightning&#39;s case, with 1% ch=
annel_reserve_satoshis around, we arrive at T =3D 316, which is much longer=
 than the current default of 144.=C2=A0</div><div>=C2=A0</div><blockquote c=
lass=3D"gmail_quote" style=3D"margin:0px 0px 0px 0.8ex;border-left:1px soli=
d rgb(204,204,204);padding-left:1ex">
<br>
So it looks to me that scorched-earth is a possible mitigation against this=
 attack.<br></blockquote><div><br></div><div>I don&#39;t follow this. We sh=
ow that a reasonable value of fees and timelock are enough to avoid the att=
ack. Why scorch the earth?</div></div></div>

--000000000000490db305a97478cf--