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
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
|
Return-Path: <jl2012@xbt.hk>
Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org
[172.17.192.35])
by mail.linuxfoundation.org (Postfix) with ESMTPS id B5B5ECDAC
for <bitcoin-dev@lists.linuxfoundation.org>;
Sat, 9 Feb 2019 16:49:16 +0000 (UTC)
X-Greylist: from auto-whitelisted by SQLgrey-1.7.6
Received: from sender-of-o51.zoho.com (sender-of-o51.zoho.com [135.84.80.216])
by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 5FE3613A
for <bitcoin-dev@lists.linuxfoundation.org>;
Sat, 9 Feb 2019 16:49:15 +0000 (UTC)
ARC-Seal: i=1; a=rsa-sha256; t=1549730948; cv=none; d=zoho.com; s=zohoarc;
b=kpbPYYnNhafvE/Z2QX4NAkDYeeqzlkTaCgQNfvFBKCssmMPLyT/h+TAapYie0Ln8FGHbGUnGWLmMhXScSEbzcpygdXmpPq9DLOZIdjBADNG9fKLCa/8J9N8KGLzpuN9+Cc01Ubq5e9cDIzRxOYSobNLy67t7WQAFqGFK+LFBc/A=
ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=zoho.com;
s=zohoarc; t=1549730948;
h=Content-Type:Content-Transfer-Encoding:Cc:Date:From:In-Reply-To:MIME-Version:Message-ID:References:Subject:To:ARC-Authentication-Results;
bh=DBTQFl5X6EeREOr/CJ6sZpMuYJJASJtN4nQiAlgXZOE=;
b=Rcw5iqzmyxn3Zo1RxOx78Z+GAJa916B3Fn8pTo6z/BTltvfc1HZUy0pH//QQ1WV9EPqwBh06e/XZuXMdpHUmcE0FuEMeoG2ix48IAJQG7heEFh1AGuShmszlhCPcBSLonn4aLbgqkwDz3iHWrdffk92l0yukpChxnRxTDmiVg4o=
ARC-Authentication-Results: i=1; mx.zoho.com; dkim=pass header.i=xbt.hk;
spf=pass smtp.mailfrom=jl2012@xbt.hk;
dmarc=pass header.from=<jl2012@xbt.hk> header.from=<jl2012@xbt.hk>
Received: from [10.8.0.105] (pcd687179.netvigator.com [218.102.219.179]) by
mx.zohomail.com with SMTPS id 1549730945987588.8970549640836;
Sat, 9 Feb 2019 08:49:05 -0800 (PST)
Content-Type: text/plain;
charset=utf-8
Mime-Version: 1.0 (Mac OS X Mail 12.0 \(3445.100.39\))
From: Johnson Lau <jl2012@xbt.hk>
In-Reply-To: <dceb1831-9bc7-eae7-fdf2-c907701c0efe@gmail.com>
Date: Sun, 10 Feb 2019 00:48:40 +0800
Content-Transfer-Encoding: quoted-printable
Message-Id: <E280BF09-ABE8-4AD8-BE29-A9D87AD09207@xbt.hk>
References: <9F8C0789-48E9-448A-A239-DB4AFB902A00@xbt.hk>
<9bae18fa-3266-61ce-0b62-6ee429198260@gmail.com>
<dceb1831-9bc7-eae7-fdf2-c907701c0efe@gmail.com>
To: Alejandro Ranchal Pedrosa <a.ranchalpedrosa@gmail.com>,
bitcoin-dev <bitcoin-dev@lists.linuxfoundation.org>
X-Mailer: Apple Mail (2.3445.100.39)
X-ZohoMailClient: External
X-Spam-Status: No, score=-1.9 required=5.0 tests=BAYES_00,MIME_QP_LONG_LINE,
RCVD_IN_DNSWL_NONE autolearn=ham version=3.3.1
X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on
smtp1.linux-foundation.org
X-Mailman-Approved-At: Sat, 09 Feb 2019 18:49:52 +0000
Subject: Re: [bitcoin-dev] Safer NOINPUT with output tagging
X-BeenThere: bitcoin-dev@lists.linuxfoundation.org
X-Mailman-Version: 2.1.12
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: Sat, 09 Feb 2019 16:49:16 -0000
In a 3 parties channel, let=E2=80=99s say the balance for A, B, C is 2, =
3, 6BTC respectively, there are few ways they could make the settlement =
tx.
The first type we may call it =E2=80=9Csimple settlement=E2=80=9D, which =
has 3 outputs with A=3D2, B=3D3, C=3D6.
The second type we may call it =E2=80=9Cfully combinatorial =
settlement=E2=80=9D, which has 3 outputs with (A & B), (B & C), and (A & =
C). The value distribution is flexible, but never exceed the total =
balance of the involved parties. For example, (A & B) may have any value =
between 0 and 5BTC. For the following example, I will use (A & B) =3D 3; =
(B & C) =3D 6; (A & C) =3D 2, but there are infinitely many valid =
combinations.
The third type we may call it =E2=80=9Cpartially combinatorial =
settlement=E2=80=9D. It may have 2 multi-sig outputs, for example, (A & =
B) =3D 4 and (B & C) =3D 7; or 1 multi-sig output and 1 single-sig =
output, for example, (A & B) =3D 5 and C=3D6 (known as "semi-cooperative =
channel closing=E2=80=9D SCCC in my last post)
I=E2=80=99ll just focus on the fully combinatorial settlement. The =
partial type works in the same way, with benefits and limitations.
In a combinatorial settlement, the multi-sig outputs are actually =
eltoo-style scripts. Therefore, A and B will further distribute the =
value of (A & B) by a 2-party eltoo channel (=E2=80=9Cbranch channels"). =
Again, there are infinitely many valid ways to distribute the values. If =
the AB branch channel is distributed as A=3D1 and B=3D2, then the BC =
channel must be B=3D1 and C=3D5, and the AC channel must be A=3D1 and =
C=3D1.
A clear benefit of this model is that any 2 parties could trade with =
each other, in the absence of any other party(s), as long as there is =
enough liquidity in their branch channel. There is also no way to =
=E2=80=9Cfork=E2=80=9D the state, because liquidity is restricted to =
each branch channel. In some way, this is like the existing lightning =
network where the 3 parties have direct channel with each other. =
However, this is superior to lightning network, because when the 3 =
parties are online simultaneously, they could re-distribute the channel =
capacities without closing any channels. They could even change it to a =
partially combinatorial settlement. If they find that A and C rarely =
trade with each other, they could remove the (A & C) output, and improve =
the capacities of the remaining channels. If C is going offline for a =
week, they could make it (A & B), C, (aka. SCCC) which will maximise the =
capacity of the AB branch channel, and minimise the cost in case C is =
not coming back.
A problem with combinatorial settlement is the increased costs of =
uncooperative settlement. It is more expensive, as more parties are =
missing. Simple settlement has the same settlement cost for any number =
of missing party. However, even if one party is missing, a simple =
settled channel will cease to function and force an immediate on-chain =
settlement. In combinatorial settlement, the surviving parties may keep =
trading, may or may not with reduced capacity depending on the exact =
settlement model, and in the meantime hope that the missing parties may =
return.
It requires 6 outputs for 4 parties doing fully combinatorial =
settlement, 10 outputs for 5 parties, 15 outputs for 6 parties, etc. =
However, in a many parties situation, not every parties might want to =
trade with all the other parties, and those branch channels might be =
omitted to improve the capacities of the other channels. If some pairs =
want to trade without a direct branch channel, they might try to find a =
third (internal) party to forward the tx. When the next time all parties =
are online, they could rearrange the branch channel capacities at no =
cost.
The combinatorial settlement model could be generalised to a =
hierarchical settlement model, where we might have 4 settlement outputs =
(A&B&C), (A&B&D), (A&C&D), (B&C&D) for a 4-party channel, and each =
settlement output will have 3 branch channels. If A is missing, for =
example, we will still have one BC branch channel, one BD branch =
channel, one CD branch channel, and one BCD 3-party branch channel. The =
benefit of having a BCD 3-party branch channel is the 3 parties could =
rearrange the channel capacities without involving A. Let=E2=80=99s say =
D is going for vacation, he could do a SCCC in the BCD branch channel to =
maximise the capacity of its BC channel. Without the involvement of A, =
however, the capacities of the other BC, BD, and CD branch channels are =
not modifiable, and B and C=E2=80=99s balance in the BD/CD channels are =
frozen during the absence of D.
As the number of parties increase, the number of settlement txs will =
grow factorially in a fully hierarchical settlement model, and will soon =
be out-of-control. The result could be catastrophic if many parties are =
gone. So the group needs to continuously evaluate the risks of each =
party being missing, and modify the settlement model accordingly.
> On 9 Feb 2019, at 6:01 PM, Alejandro Ranchal Pedrosa via bitcoin-dev =
<bitcoin-dev@lists.linuxfoundation.org> wrote:
>=20
> Hi all,
>>=20
>> Side note: I was not able to come up with an similar, eltoo-like =
protocol that works
>> if you can't predict in advance who will become absent.
>>=20
> An eltoo-like protocol that works (without going on-chain) if you =
can't predict in advance who will become absent would be a childchain. =
If the off-chain protocol can continue updating in the abscence of other =
parties, it means that other parties' signatures must not be required =
when they are not involved in the off-chain state update. If other =
parties' signatures must not be required, there must be a way of having =
a common verifiable 'last state' to prevent a party to simultaneously =
'fork' the state with two different parties, and double-spend. A =
solution for this is a childchain for Bitcoin. An example of this is =
what is known as a 'Broken Factory' attack [1] =
(https://bitcoin.stackexchange.com/questions/77434/how-does-channel-factor=
y-act/81005#81005)
>=20
>> If the expectation is that the unresponsive party returns, =
fungibility is
>> not reduced due to output tagging because the above scheme can be =
used
>> off-chain until the original channel can be continued.
>=20
> I believe that in many cases other parties won't be able to continue =
until the unresponsive parties go back online. That might be true in =
particular scenarios, but generally speaking, the party might have gone =
unresponsive during a factory-level update (i.e. off-chain closing and =
opening of channels), while some parties might have given out their =
signature for the update without receiving a fully signed transaction. =
In this case they do not even know which channel they have open (the one =
of the old state that they have fully signed, or the one for the new =
state that they have given out their signature for). This is known as a =
'Stale Factory', and can be exploited by an adversary in a 'Stale =
Factory' attack [1]. Even if they knew which state they are in (i.e. the =
party went unresponsive but not during a factory-level update), some of =
them might have run out of funds in some of their channels of the =
factory, and might want to update, while they will not be willing to =
wait for a party to go back online (something for which they also have =
zero guarantees of).
>=20
> An eltoo-like protocol that works (allowing going on-chain) if you =
can't in advance who will become absent, then this is precisely why =
'Transaction Fragments' have been suggested. They allow an eltoo-like =
protocol even when one cannot predict in advance who will become absent, =
or malicious (by publishing invalid states), cause the non-absent =
parties can unite their fragments and create a valid spendable =
factory-level transaction that effectively kicks out the malicious =
parties, while leaving the rest of the factory as it was. To the best of =
my understanding, the eltoo original proposal also allows this though.
>=20
> Best,
>=20
> Alejandro.
>=20
> [1]: Scalable Lightning Factories for Bitcoin, =
https://eprint.iacr.org/2018/918.pdf
>=20
>=20
> On 08/02/2019 20:01, Jonas Nick via bitcoin-dev wrote:
>> Output tagging may result in reduced fungibility in multiparty eltoo =
channels.
>> If one party is unresponsive, the remaining participants want to =
remove
>> the party from the channel without downtime. This is possible by =
creating
>> settlement transactions which pay off the unresponsive party and fund =
a new
>> channel with the remaining participants.
>>=20
>> When the party becomes unresponsive, the channel is closed by =
broadcasting the
>> update transaction as usual. As soon as that happens the remaining
>> participants can start to update their new channel. Their update =
signatures
>> must use SIGHASH_NOINPUT. This is because in eltoo the settlement =
txid is not
>> final (because update tx is not confirmed and may have to rebind to =
another
>> output). Therefore, the funding output of the new channel must be =
NOINPUT
>> tagged. Assuming the remaining parties later settle cooperatively, =
this loss
>> of fungibility would not have happened without output tagging.
>>=20
>> funding output update output =
settlement outputs update output
>> [ A & B & C ] -> ... -> [ (A & B & C & state CLTV) | (As & Bs & Cs) ] =
-> [ NOINPUT tagged: (A' & B'), -> ...
>> =
C' ]
>> If the expectation is that the unresponsive party returns, =
fungibility is
>> not reduced due to output tagging because the above scheme can be =
used
>> off-chain until the original channel can be continued.
>>=20
>> Side note: I was not able to come up with an similar, eltoo-like =
protocol that works
>> if you can't predict in advance who will become absent.
>>=20
>> On 12/13/18 12:32 PM, Johnson Lau via bitcoin-dev wrote:
>>> NOINPUT is very powerful, but the tradeoff is the risks of signature =
replay. While the key holders are expected not to reuse key pair, little =
could be done to stop payers to reuse an address. Unfortunately, =
key-pair reuse has been a social and technical norm since the creation =
of Bitcoin (the first tx made in block 170 reused the previous public =
key). I don=E2=80=99t see any hope to change this norm any time soon, if =
possible at all.
>>>=20
>>> As the people who are designing the layer-1 protocol, we could =
always blame the payer and/or payee for their stupidity, just like those =
people laughed at victims of Ethereum dumb contracts (DAO, Parity =
multisig, etc). The existing bitcoin script language is so restrictive. =
It disallows many useful smart contracts, but at the same time prevented =
many dumb contracts. After all, =E2=80=9Csmart=E2=80=9D and =E2=80=9Cdumb=E2=
=80=9D are non-technical judgement. The DAO contract has always been =
faithfully executed. It=E2=80=99s dumb only for those invested in the =
project. For me, it was just a comedy show.
>>>=20
>>> So NOINPUT brings us more smart contract capacity, and at the same =
time we are one step closer to dumb contracts. The target is to find a =
design that exactly enables the smart contracts we want, while =
minimising the risks of misuse.
>>>=20
>>> The risk I am trying to mitigate is a payer mistakenly pay to a =
previous address with the exactly same amount, and the previous UTXO has =
been spent using NOINPUT. Accidental double payment is not uncommon. =
Even if the payee was honest and willing to refund, the money might have =
been spent with a replayed NOINPUT signature. Once people lost a =
significant amount of money this way, payers (mostly exchanges) may =
refuse to send money to anything other than P2PKH, native-P2WPKH and =
native-P2WSH (as the only 3 types without possibility of NOINPUT)
>>>=20
>>> The proposed solution is that an output must be =E2=80=9Ctagged=E2=80=9D=
for it to be spendable with NOINPUT, and the =E2=80=9Ctag=E2=80=9D must =
be made explicitly by the payer. There are 2 possible ways to do the =
tagging:
>>>=20
>>> 1. A certain bit in the tx version must be set
>>> 2. A certain bit in the scriptPubKey must be set
>>>=20
>>> I will analyse the pros and cons later.
>>>=20
>>> Using eltoo as example. The setup utxo is a simple 2-of-2 multisig, =
and should not be tagged. This makes it indistinguishable from normal =
1-of-1 utxo. The trigger tx, which spends the setup utxo, should be =
tagged, so the update txs could spend the trigger utxo with NOINPUT. =
Similarly, all update txs should be tagged, so they could be spent by =
other update txs and settlement tx with NOINPUT. As the final =
destination, there is no need to tag in the settlement tx.
>>>=20
>>> In payer=E2=80=99s perspective, tagging means =E2=80=9CI believe =
this address is for one-time-use only=E2=80=9D Since we can=E2=80=99t =
control how other people manage their addresses, we should never do =
tagging when paying to other people.
>>>=20
>>> I mentioned 2 ways of tagging, and they have pros and cons. First of =
all, tagging in either way should not complicate the eltoo protocol in =
anyway, nor bring extra block space overhead.
>>>=20
>>> A clear advantage of tagging with scriptPubKey is we could tag on a =
per-output basis. However, scriptPubKey tagging is only possible with =
native-segwit, not P2SH. That means we have to disallow NOINPUT in =
P2SH-segwit (Otherwise, *all* P2SH addresses would become =E2=80=9Crisky=E2=
=80=9D for payers) This should be ok for eltoo, since it has no reason =
to use P2SH-segwit in intermediate txs, which is more expensive.
>>>=20
>>> Another problem with scriptPubKey tagging is all the existing bech32 =
implementations will not understand the special tag, and will pay to a =
tagged address as usual. An upgrade would be needed for them to refuse =
sending to tagged addresses by default.
>>>=20
>>> On the other hand, tagging with tx version will also protect =
P2SH-segwit, and all existing wallets are protected by default. However, =
it is somewhat a layer violation and you could only tag all or none =
output in the same tx. Also, as Bitcoin Core has just removed the tx =
version from the UTXO database, adding it back could be a little bit =
annoying, but doable.
>>>=20
>>> There is an extension to the version tagging, which could make =
NOINPUT even safer. In addition to tagging requirement, NOINPUT will =
also sign the version of the previous tx. If the wallet always uses a =
randomised tx version, it makes accidental replay very unlikely. =
However, that will burn a few more bits in the tx version field.
>>>=20
>>> While this seems fully compatible with eltoo, is there any other =
proposals require NOINPUT, and is adversely affected by either way of =
tagging?
>>> _______________________________________________
>>> bitcoin-dev mailing list
>>> bitcoin-dev@lists.linuxfoundation.org
>>> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>>>=20
>> _______________________________________________
>> bitcoin-dev mailing list
>> bitcoin-dev@lists.linuxfoundation.org
>> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
|