summaryrefslogtreecommitdiff
path: root/bf/518dddc480cbb9bf130deef70a10e7dc909574
blob: 7d89cf8c7a7c8d1ed823e9383cb725237c5f5859 (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
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
Return-Path: <johanth@gmail.com>
Received: from smtp3.osuosl.org (smtp3.osuosl.org [140.211.166.136])
 by lists.linuxfoundation.org (Postfix) with ESMTP id DE10BC0032
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Thu,  5 Oct 2023 07:38:38 +0000 (UTC)
Received: from localhost (localhost [127.0.0.1])
 by smtp3.osuosl.org (Postfix) with ESMTP id C6EB86F51D
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Thu,  5 Oct 2023 07:38:38 +0000 (UTC)
DKIM-Filter: OpenDKIM Filter v2.11.0 smtp3.osuosl.org C6EB86F51D
Authentication-Results: smtp3.osuosl.org;
 dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com
 header.a=rsa-sha256 header.s=20230601 header.b=fdLL+emN
X-Virus-Scanned: amavisd-new at osuosl.org
X-Spam-Flag: NO
X-Spam-Score: -2.099
X-Spam-Level: 
X-Spam-Status: No, score=-2.099 tagged_above=-999 required=5
 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1,
 DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1, FREEMAIL_FROM=0.001,
 RCVD_IN_DNSWL_NONE=-0.0001, SPF_HELO_NONE=0.001, SPF_PASS=-0.001]
 autolearn=ham autolearn_force=no
Received: from smtp3.osuosl.org ([127.0.0.1])
 by localhost (smtp3.osuosl.org [127.0.0.1]) (amavisd-new, port 10024)
 with ESMTP id 8NKti06Cqvu5
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Thu,  5 Oct 2023 07:38:37 +0000 (UTC)
Received: from mail-yb1-xb2a.google.com (mail-yb1-xb2a.google.com
 [IPv6:2607:f8b0:4864:20::b2a])
 by smtp3.osuosl.org (Postfix) with ESMTPS id 304CA616E2
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Thu,  5 Oct 2023 07:38:37 +0000 (UTC)
DKIM-Filter: OpenDKIM Filter v2.11.0 smtp3.osuosl.org 304CA616E2
Received: by mail-yb1-xb2a.google.com with SMTP id
 3f1490d57ef6-d868d8363e6so782937276.2
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Thu, 05 Oct 2023 00:38:37 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
 d=gmail.com; s=20230601; t=1696491516; x=1697096316;
 darn=lists.linuxfoundation.org; 
 h=content-transfer-encoding:cc:to:subject:message-id:date:from
 :in-reply-to:references:mime-version:from:to:cc:subject:date
 :message-id:reply-to;
 bh=clvD2+SSCKbZpc01LIItZmWyvgF0rATpmCPOyx8zj4E=;
 b=fdLL+emNORekYtGp3sdAh0TpKjjJSP401xXhFIhXi3JGv2AywffjU3JKhfbr26sktp
 xV+UxdN0R17etNxp9BzwmO9b9nXthf0Aoy7GZsB/nCkXdKEVVUSsjrgrvRZbsyC/+nqK
 pL8PpqvT8qsI9DTgoTXO9pgnnLxjEZfJQ1xmKi3Za+Zi8WjpUuhjsPlwFnK/aq8OPu2E
 /9r6X+3sHcD7sKTlBqYYp+HxaeYQjAHuy0lATMR+pufqn/aIK9PdR2Wlrdpw89vmZz/s
 2wTHHF2iWkvDrQiMxt+fDzYPNzKAvs4jTuU2J6r0XtJ0GzXSaTkUaixOnrJwvzzCA8pJ
 Kjtg==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
 d=1e100.net; s=20230601; t=1696491516; x=1697096316;
 h=content-transfer-encoding:cc:to:subject:message-id:date:from
 :in-reply-to:references:mime-version:x-gm-message-state:from:to:cc
 :subject:date:message-id:reply-to;
 bh=clvD2+SSCKbZpc01LIItZmWyvgF0rATpmCPOyx8zj4E=;
 b=PEMgQFHBSNu/96vVjGmDoACbrTMnDhH994WKZuPhIDpuf25FplVDpF5kMY9NBb/KfI
 KW0R23gYHQ06ei8HBpqX5OBJ7wMHY6j5FPJYA8y2VqJGseOjLZMU77qbJRPdaSbSvLn9
 5043fNt6y7hQJNMSSlfRCRRV/iaYzTSu/y/vJXpolSvgt95zlKJueS6qFlAHuf49wTf9
 oaG4GlLs/TTYDSHVK28oW+IWb+BVVNCg13sIjOBG1HDLYJLkzxhzbRBxAwGaBr3QJFiG
 sTzP92MUC+Y6IDe+GpheOY6Dm7EXtsu2l5+VhN0/ZiXKDXS+cl3ydCGpWwhwgsg5JYE6
 TcBg==
X-Gm-Message-State: AOJu0YzCLM11J7CQz4P1ApjZ2IJhDTZXwzLxYIxJZ+ZBFviDFqHugaWs
 pW1Mf9BQf3mUD/PL8nSPCDp7a4+WozME+I65Pao=
X-Google-Smtp-Source: AGHT+IHXEnsIpVRjsSFkvo6LLauYHPxgLf9yX5kBsvgwM96wjuh1mOjGpl/zx+BAsiX2FZ5P3Yi4mS3Wvhp98GoR3vQ=
X-Received: by 2002:a25:f624:0:b0:d81:c900:1f11 with SMTP id
 t36-20020a25f624000000b00d81c9001f11mr4375423ybd.26.1696491515774; Thu, 05
 Oct 2023 00:38:35 -0700 (PDT)
MIME-Version: 1.0
References: <CALZpt+F26bArqU7aZj8VN-zDN-3_VZS1K1ibaJOeCrsLDL2_4Q@mail.gmail.com>
 <OUAbM8ii-HE8M-kRAkMvdDkbiwKuG_wcYlrvC276eIsKXcW6Yh6iNcxy_PtchHNL3jIIc-nz-ucv2H11EznrZbYhKqyVPhE8__GeIDLxPNw=@protonmail.com>
 <CALZpt+Gyo1STD4zrge3yiuC1j_NpJ8ZDYzzzAGCcZpjKw0_9-w@mail.gmail.com>
 <CAD3i26DpcfZJ4M0bjrOnGg6bcQ0Lg0hO-13cihzP2CjnCOq=EQ@mail.gmail.com>
 <CALZpt+FT3qwP5MaZT4hbGYXvbECsAn7LvNbZC5vP-jGkbpOGVA@mail.gmail.com>
In-Reply-To: <CALZpt+FT3qwP5MaZT4hbGYXvbECsAn7LvNbZC5vP-jGkbpOGVA@mail.gmail.com>
From: =?UTF-8?Q?Johan_Tor=C3=A5s_Halseth?= <johanth@gmail.com>
Date: Thu, 5 Oct 2023 09:38:24 +0200
Message-ID: <CAD3i26A2CC2Acr7dUnVMVrs+ag0nNdwnwTPSuVCxVpy+tC8eOg@mail.gmail.com>
To: Antoine Riard <antoine.riard@gmail.com>
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
X-Mailman-Approved-At: Thu, 05 Oct 2023 09:48:58 +0000
Cc: Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Subject: Re: [bitcoin-dev] Solving CoinPool high-interactivity issue with
 cut-through update of Taproot leaves
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, 05 Oct 2023 07:38:39 -0000

Hi,

Yes, one would need to have the <data> be a merkle root of all
participants' keys and balances. Then, as you say, the scripts would
have to enforce that one correctly creates new merkle roots according
to the coin pool rules when spending it.

- Johan

On Thu, Oct 5, 2023 at 3:13=E2=80=AFAM Antoine Riard <antoine.riard@gmail.c=
om> wrote:
>
> Hi Johan,
>
> Thanks for the insight.
>
> From the proposed semantics of OP_CHECKCONTRACTVERIFY iirc:
>
> <data> <index> <pk> <taptree> <flags>
>
> I think this is not yet indicated how the participant's pubkeys and balan=
ces can be disaggregated from <data>, a partial subset push on the stack an=
d verifying that corresponding signatures are valid.
>
> One requirement of a cut-through update of taproot leaves is to verify th=
e authentication of the fan-out balances and pubkeys towards the "online" p=
artition. This subset is not known at pool setup, even if the contract or t=
ree construct can be equilibrated with some expectation.
>
> Otherwise, it sounds OP_CHECKCONTRACTVERIFY could be used to architect th=
e proposed design of coinpool and its cut-through mechanism. One hard issue=
 sounds to be efficient traversal, inspection and modification of the contr=
act <data>.
>
> Best,
> Antoine
>
> Le mar. 3 oct. 2023 =C3=A0 12:24, Johan Tor=C3=A5s Halseth <johanth@gmail=
.com> a =C3=A9crit :
>>
>> Hi, Antoine.
>>
>> It sounds like perhaps OP_CHECKCONTRACTVERIFY can achieve what you are
>> looking for: https://lists.linuxfoundation.org/pipermail/bitcoin-dev/202=
3-May/021719.html
>>
>> By committing the participants' pubkeys and balances in the dynamic
>> data instead of the taptree one can imagine a subset of online users
>> agreeing to pool their aggregated balances in a new output, while the
>> offline users' funds would remain inaccessible by them in a second
>> output.
>>
>> The way this would work is by spending the coinpool utxo with a
>> transaction having two outputs: one output that is the "remainder" of
>> the previous coinpool (the offline users), and the second output the
>> new coinpool among the online users*.
>>
>> When the offline users are back online, they could all agree to
>> continue using the original coinpool utxo.
>>
>> * assuming Eltoo in case an offline user comes back online and double
>> spends the UTXO.
>>
>> - Johan
>>
>>
>> On Wed, Sep 27, 2023 at 12:08=E2=80=AFPM Antoine Riard via bitcoin-dev
>> <bitcoin-dev@lists.linuxfoundation.org> wrote:
>> >
>> > Hi Zeeman,
>> >
>> > See my comments at the time of OP_EVICT original publication.
>> >
>> > https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2022-February/=
019939.html
>> >
>> > "I think in the context of (off-chain) payment pool, OP_EVICT requires
>> > participant cooperation *after* the state update to allow a single
>> > participant to withdraw her funds.
>> >
>> > I believe this is unsafe if we retain as an off-chain construction sec=
urity
>> > requirement that a participant should have the unilateral means to enf=
orce
>> > the latest agreed upon state at any time during the construction lifet=
ime".
>> >
>> > I think this level of covenant flexibility is still wished for CoinPoo=
l as a fundamental property, and this is offered by TLUV or MERKLESUB.
>> > On the other hand, I think OP_EVICT introduces this idea of *subgroup =
novation* (i.e `K-of-N`) of a PT2R scriptpubkey.
>> >
>> > To the best of my understanding, I think there is not yet any sound co=
venant proposal aiming to combine TLUV and EVICT-like semantics in a consis=
tent set of Script primitives to enable "cut-through" updates, while still =
retaining the key property of unilateral withdraw of promised balances in a=
ny-order.
>> >
>> > I might go to work on crafting one, though for now I'm still intereste=
d to understand better if on-chain "cut-through" is the best direction to s=
olve the fundamental high interactivity issue of channel factory and paymen=
t pool over punishment-based ideas.
>> >
>> > Best,
>> > Antoine
>> >
>> > Le mar. 26 sept. 2023 =C3=A0 07:51, ZmnSCPxj <ZmnSCPxj@protonmail.com>=
 a =C3=A9crit :
>> >>
>> >> Good morning Antoine,
>> >>
>> >> Does `OP_EVICT` not fit?
>> >>
>> >> https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2022-February=
/019926.html
>> >>
>> >> Regards,
>> >> ZmnSCPxj
>> >>
>> >>
>> >> Sent with Proton Mail secure email.
>> >>
>> >> ------- Original Message -------
>> >> On Monday, September 25th, 2023 at 6:18 PM, Antoine Riard via bitcoin=
-dev <bitcoin-dev@lists.linuxfoundation.org> wrote:
>> >>
>> >>
>> >> > Payment pools and channel factories are afflicted by severe interac=
tivity constraints worsening with the number of users owning an off-chain b=
alance in the construction. The security of user funds is paramount on the =
ability to withdraw unilaterally from the off-chain construction. As such a=
ny update applied to the off-chain balances requires a signature contributi=
on from the unanimity of the construction users to ensure this ability is c=
onserved along updates.
>> >> > As soon as one user starts to be offline or irresponsive, the updat=
es of the off-chain balances must have to be halted and payments progress a=
re limited among subsets of 2 users sharing a channel. Different people hav=
e proposed solutions to this issue: introducing a coordinator, partitioning=
 or layering balances in off-chain users subsets. I think all those solutio=
ns have circled around a novel issue introduced, namely equivocation of off=
-chain balances at the harm of construction counterparties [0].
>> >> >
>> >> > As ZmnSCPxj pointed out recently, one way to mitigate this equivoca=
tion consists in punishing the cheating pre-nominated coordinator on an ext=
ernal fidelity bond. One can even imagine more trust-mimized and decentrali=
zed fraud proofs to implement this mitigation, removing the need of a coord=
inator [1].
>> >> >
>> >> > However, I believe punishment equivocation to be game-theory sound =
should compensate a defrauded counterparty of the integrity of its lost off=
-chain balance. As one cheating counterparty can equivocate in the worst-ca=
se against all the other counterparties in the construction, one fidelity b=
ond should be equal to ( C - 1 ) * B satoshi amount, where C is the number =
of construction counterparty and B the initial off-chain balance of the che=
ating counterparty.
>> >> >
>> >> > Moreover, I guess it is impossible to know ahead of a partition or =
transition who will be the "honest" counterparties from the "dishonest" one=
s, therefore this ( C - 1 ) * B-sized fidelity bond must be maintained by e=
very counterparty in the pool or factory. On this ground, I think this miti=
gation and other corrective ones are not economically practical for large-s=
cale pools among a set of anonymous users.
>> >> >
>> >> > I think the best solution to solve the interactivity issue which is=
 realistic to design is one ruling out off-chain group equivocation in a pr=
ophylactic fashion. The pool or factory funding utxo should be edited in an=
 efficient way to register new off-chain subgroups, as lack of interactivit=
y from a subset of counterparties demands it.
>> >> >
>> >> > With CoinPool, there is already this idea of including a user pubke=
y and balance amount to each leaf composing the Taproot tree while preservi=
ng the key-path spend in case of unanimity in the user group. Taproot leave=
s can be effectively regarded as off-chain user accounts available to reali=
ze privacy-preserving payments and contracts.
>> >> >
>> >> > I think one (new ?) idea can be to introduce taproot leaves "cut-th=
rough" spends where multiple leaves are updated with a single witness, inte=
ractively composed by the owners of the spent leaves. This spend sends back=
 the leaves amount to a new single leaf, aggregating the amounts and user p=
ubkeys. The user leaves not participating in this "cut-through" are inherit=
ed with full integrity in the new version of the Taproot tree, at the gain =
of no interactivity from their side.
>> >> >
>> >> > Let's say you have a CoinPool funded and initially set with Alice, =
Bob, Caroll, Dave and Eve. Each pool participant has a leaf L.x committing =
to an amount A.x and user pubkey P.x, where x is the user name owning a lea=
f.
>> >> >
>> >> > Bob and Eve are deemed to be offline by the Alice, Caroll and Dave =
subset (the ACD group).
>> >> >
>> >> > The ACD group composes a cut-through spend of L.a + L.c + L.d. This=
 spends generates a new leaf L.(acd) leaf committing to amount A.(acd) and =
P.(acd).
>> >> >
>> >> > Amount A.(acd) =3D A.a + A.c + A.d and pubkey P.(acd) =3D P.a + P.c=
 + P.d.
>> >> >
>> >> > Bob's leaf L.b and Eve's leaf L.e are left unmodified.
>> >> >
>> >> > The ACD group generates a new Taproot tree T' =3D L.(acd) + L.b + L=
.e, where the key-path K spend including the original unanimity of pool cou=
nterparties is left unmodified.
>> >> >
>> >> > The ACD group can confirm a transaction spending the pool funding u=
txo to a new single output committing to the scriptpubkey K + T'.
>> >> >
>> >> > From then, the ACD group can pursue off-chain balance updates among=
 the subgroup thanks to the new P.(acd) and relying on the known Eltoo mech=
anism. There is no possibility for any member of the ACD group to equivocat=
e with Bob or Eve in a non-observable fashion.
>> >> >
>> >> > Once Bob and Eve are online and ready to negotiate an on-chain pool=
 "refresh" transaction, the conserved key-path spend can be used to re-equi=
librate the Taproot tree, prune out old subgroups unlikely to be used and p=
rovision future subgroups, all with a compact spend based on signature aggr=
egation.
>> >> >
>> >> > Few new Taproot tree update script primitives have been proposed, e=
.g [2]. Though I think none with the level of flexibility offered to genera=
te leaves cut-through spends, or even batch of "cut-through" where M subgro=
ups are willing to spend N leaves to compose P new subgroups fan-out in Q n=
ew outputs, with showing a single on-chain witness. I believe such a hypoth=
etical primitive can also reduce the chain space consumed in the occurrence=
 of naive mass pool withdraws at the same time.
>> >> >
>> >> > I think this solution to the high-interactivity issue of payment po=
ols and factories shifts the burden on each individual user to pre-commit f=
ast Taproot tree traversals, allowing them to compose new pool subgroups as=
 fluctuations in pool users' level of liveliness demand it. Pool efficiency=
 becomes the sum of the quality of user prediction on its counterparties' l=
iveliness during the construction lifetime. Recursive taproot tree spends o=
r more efficient accumulator than merkle tree sounds ideas to lower the on-=
chain witness space consumed by every pool in the average non-interactive c=
ase.
>> >> >
>> >> > Cheers,
>> >> > Antoine
>> >> >
>> >> > [0] https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2022-Ap=
ril/020370.html
>> >> > [1] https://lists.linuxfoundation.org/pipermail/lightning-dev/2023-=
August/004043.html
>> >> > [2] https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2021-Se=
ptember/019420.html
>> >
>> > _______________________________________________
>> > bitcoin-dev mailing list
>> > bitcoin-dev@lists.linuxfoundation.org
>> > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev