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
|
Return-Path: <salvatore.ingala@gmail.com>
Received: from smtp2.osuosl.org (smtp2.osuosl.org [IPv6:2605:bc80:3010::133])
by lists.linuxfoundation.org (Postfix) with ESMTP id 9A8ADC002A
for <bitcoin-dev@lists.linuxfoundation.org>;
Sun, 28 May 2023 10:24:28 +0000 (UTC)
Received: from localhost (localhost [127.0.0.1])
by smtp2.osuosl.org (Postfix) with ESMTP id 77716401A4
for <bitcoin-dev@lists.linuxfoundation.org>;
Sun, 28 May 2023 10:24:28 +0000 (UTC)
DKIM-Filter: OpenDKIM Filter v2.11.0 smtp2.osuosl.org 77716401A4
Authentication-Results: smtp2.osuosl.org;
dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com
header.a=rsa-sha256 header.s=20221208 header.b=FCYkIf+S
X-Virus-Scanned: amavisd-new at osuosl.org
X-Spam-Flag: NO
X-Spam-Score: -2.098
X-Spam-Level:
X-Spam-Status: No, score=-2.098 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,
HTML_MESSAGE=0.001, RCVD_IN_DNSWL_NONE=-0.0001, SPF_HELO_NONE=0.001,
SPF_PASS=-0.001] autolearn=ham autolearn_force=no
Received: from smtp2.osuosl.org ([127.0.0.1])
by localhost (smtp2.osuosl.org [127.0.0.1]) (amavisd-new, port 10024)
with ESMTP id ssPhx4LXX41K
for <bitcoin-dev@lists.linuxfoundation.org>;
Sun, 28 May 2023 10:24:27 +0000 (UTC)
X-Greylist: whitelisted by SQLgrey-1.8.0
DKIM-Filter: OpenDKIM Filter v2.11.0 smtp2.osuosl.org 1D054400D3
Received: from mail-oa1-x2e.google.com (mail-oa1-x2e.google.com
[IPv6:2001:4860:4864:20::2e])
by smtp2.osuosl.org (Postfix) with ESMTPS id 1D054400D3
for <bitcoin-dev@lists.linuxfoundation.org>;
Sun, 28 May 2023 10:24:27 +0000 (UTC)
Received: by mail-oa1-x2e.google.com with SMTP id
586e51a60fabf-19f22575b1aso1241284fac.0
for <bitcoin-dev@lists.linuxfoundation.org>;
Sun, 28 May 2023 03:24:26 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
d=gmail.com; s=20221208; t=1685269466; x=1687861466;
h=cc:to:subject:message-id:date:from:in-reply-to:references
:mime-version:from:to:cc:subject:date:message-id:reply-to;
bh=+2KhhuFznc7r3wM2Aj4U8T2ufYVI9Bs8Vt5C3PChbiw=;
b=FCYkIf+SJjjHllAJWxuhlki+9ThGYF1uwJxzMT6e0UR6rQ50mMOykeJ1hMPWWdegzT
6XUvoe6j2BBfF35fbUGf/n2Wgq9phM1i6UpISsS4kChz9rh/Nh6Wf5UfWP5nlP61N7BW
BoGNnS0cNP5pAl0uc1tJN1fJ/urANz0eDyzqnDd8nO2r9YKaDV3jfX0ibLy0U/dN4Fwk
IVrGX6+MM926+vTOFhq+vqIpQ3xMMJ71mErA9BAgCzmszPsaeV+AiZukYcNkXqWAljuw
EExkMhTHEXhDnrwGuAiSWNJljzG33nUM6pzMYilKIYUPGRs2IHb0ID8YwNRv90zHXLK5
VhCw==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
d=1e100.net; s=20221208; t=1685269466; x=1687861466;
h=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=+2KhhuFznc7r3wM2Aj4U8T2ufYVI9Bs8Vt5C3PChbiw=;
b=hA+Bu4BxmIyZ9l0B5CeqeaRdKDj1Pwr6GCERmdKh6VqR+aVutqvs9UFgzcFFp2Y+sw
ABRTmj4T+Oz4knYHB6PPFjt+X6ojDgksyOLh7KoQcDc8uChrB/m87alUsaSroakkRv3W
joDEXlJ8i/iu/Q9wV/uH5wnNP2hGqqxsSHGsP66rXT1cEl7UPphPxWZhHhQNdUr7WgEU
sLQo2IIGZVdWhl6A03SrBIEBPazQ10322J9eZlusntRFIhlsF8/gLGN53J7meqooXsJI
wkKKkWyRk80FWCcCBWy6l3F+kCOO0ann0wj15nqKNbvP23xkQAjwJxHpSIANe1B8384x
ArRA==
X-Gm-Message-State: AC+VfDwTcVcpjL2PFTWzPj1RpKN22rriY+38A9QTqjGE8kY9VVT33Rqc
NYkx6qEjACaJc1nIkcWM/VssnQGUoutbbaBqYzU=
X-Google-Smtp-Source: ACHHUZ7nsviblQPSTN891auPeuAftrCLKEqpQB8RJtl5Lfyz7g/i4kBwEF3F7fctoAM0D2XIUktTQWrxe8Nw8kTDvtA=
X-Received: by 2002:a05:6870:5316:b0:188:170:49f with SMTP id
j22-20020a056870531600b001880170049fmr3449328oan.56.1685269465800; Sun, 28
May 2023 03:24:25 -0700 (PDT)
MIME-Version: 1.0
References: <CAMhCMoH9uZPeAE_2tWH6rf0RndqV+ypjbNzazpFwFnLUpPsZ7g@mail.gmail.com>
<CALZpt+GVe0XTdWqV=LAcOj=nq+k2DEFqc+sKyxAujLDBR7bYbQ@mail.gmail.com>
<CAMhCMoEONv3jriBU3qwm0pt75iF_sgra1H2Z4rOF8u+e7hs_cw@mail.gmail.com>
<0f352f70-c93a-614f-e443-67d198ec2c26@protonmail.com>
<7f3674d1-c1ad-9a82-e30f-7cf24d697faf@protonmail.com>
<CAMhCMoGabEASO9CGc1hAMpYZn4nWH5D8XFs3eFcSSFAitSFUGA@mail.gmail.com>
<CAGpPWDZkUYW=Qb763TPzUa6yUf217nh0Bo+O9Qyf=WS2pUQUYA@mail.gmail.com>
<CAD3i26AXZKDCH3odhCjpMwzOTGQKSFqH9S+5N9UXNTb7CJHONA@mail.gmail.com>
<CAMhCMoFgto3Bu5+yEoqn1Jf8fNd+EQK-t_H3TKR2=3RXe8FdcQ@mail.gmail.com>
<CAMhCMoGdZsDO2eZYMf+G36gc5=-SB0HxHXbRSPx5OaCOjo5_Dw@mail.gmail.com>
<CAD3i26BoasDQGg1VOxaHJzoXXKnYKuBdXOq+wVZ=QhKbycobPA@mail.gmail.com>
<CAMhCMoH-MSfTeG6vnWPdG9bAxWXRatWQY8wUmOqM5mAyH=5n9Q@mail.gmail.com>
<CAD3i26DMGj=KRfi=gqHPdCZ_WyUAvWV50g7TcH4n2e3xSCx8Lg@mail.gmail.com>
In-Reply-To: <CAD3i26DMGj=KRfi=gqHPdCZ_WyUAvWV50g7TcH4n2e3xSCx8Lg@mail.gmail.com>
From: Salvatore Ingala <salvatore.ingala@gmail.com>
Date: Sun, 28 May 2023 12:24:14 +0200
Message-ID: <CAMhCMoHSonS2_wcCZYH9FhC5B5UCgf26JPhkK13pZCbo3ZO7JQ@mail.gmail.com>
To: =?UTF-8?Q?Johan_Tor=C3=A5s_Halseth?= <johanth@gmail.com>
Content-Type: multipart/alternative; boundary="000000000000dc270d05fcbe5fc6"
X-Mailman-Approved-At: Sun, 28 May 2023 10:25:42 +0000
Cc: Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Subject: Re: [bitcoin-dev] Merkleize All The Things
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 May 2023 10:24:28 -0000
--000000000000dc270d05fcbe5fc6
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
Hi Johan,
Exciting to finally see some merkleization, which was only confined
within the meme, up to this point!
> A simpler way IMO, would be to make OP_CICV and OP_COCV symmetrical:
> Have OP_CICV take an optional taproot and do the same check as is
> done for the output: Q =3D=3D tweak(tweak(X,D), T).
I think that's an excellent suggestion, which I was already exploring
for a different purpose: bringing externally signed data onto the
stack. My goal there was to allow eltoo-style replacement.
Until recently, I thought that a clean/efficient version of eltoo
would require OP_CHECKSIGFROMSTACK or ANYPREVOUT. However, extending
OP_CHECKINPUTCONTRACTVERIFY to enable introspection of other inputs
allows a reasonable workaround: producing a separate UTXO signed with
ANYONECANPAY, with the required data embedded as usual. Spending that
UTXO together with the channel's UTXO allows one to get that data
on the stack (with its signature already checked by consensus rules).
I drafted this idea in a gist [1].
Remark: it still seems easier (and probably slightly more efficient)
to build eltoo replacement with CSFS or APO in addition to MATT
opcodes.
A possible semantics for OP_CHECKINPUTCONTRACTVERIFY could then be
exactly symmetrical to that of OP_CHECKOUTPUTCONTRACTVERIFY, with
the exception that the special input index -1 would represent the
current input.
Pushing this further, another option that could be be worth exploring
is to have a single OP_CHECK_IN_OUT_CONTRACT_VERIFY opcode, with the
same semantics as OP_CHECKOUTPUTCONTRACTVERIFY from [2], but with an
additional `flags` argument, which is a bitmap where:
- the lowest-significant bit determines if the index refers to inputs
or outputs (where input index -1 refers to the current input)
- the second bit specifies if amounts should be preserved with
deferred checks as described in [2] (only applicable to outputs)
- other bits are OP_SUCCESS and reserved for future behaviors.
This would make the opcodes 1-2 bytes larger, but might allow greater
flexibility, and keep some room for future extensions.
> 2.To make fully functioning CoinPools, one would need functionality
> similar to OP_MERKLESUB[4]: remove some data from the merkle tree,
> and remove a key from the aggregated internal key.
It seems likely that efficient use of the taproot internal pubkey with
"dynamic key aggregation" is not possible with the current semantics
(unless one ventures into the fraud proof machinery, which seems
overkill!).
However, in constructions with MATT opcodes, I would never expect the
need for data to be stored in the taptree. In particular, for the case
of CoinPools, the pubkeys of the members could also be stored in the
embedded data, having a single "unilateral withdrawal" tapleaf.
Removing a key would then amount to replacing it with a fixed NUMS key
and computing the new root (re-using the same Merkle proof).
Note that this is not a lot costlier than using a tapleaf per user:
instead of paying the cost for the Merkle proof in the control block,
you pay for it explicitly in the Script witness.
Therefore, I would expect there to be reasonable CoinPools designs
without additional opcodes =E2=88=92 but I am only moderately confident as
this is beyond the level of sophistication I've been exploring so far.
Best,
Salvatore
[1] - https://gist.github.com/bigspider/041ebd0842c0dcc74d8af087c1783b63
[2] -
https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2023-April/021588.h=
tml
--000000000000dc270d05fcbe5fc6
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
<div dir=3D"ltr"><div dir=3D"ltr">Hi Johan,<br><br>Exciting to finally see =
some merkleization, which was only confined<br>within the meme, up to this =
point!<br><br>> A simpler way IMO, would be to make OP_CICV and OP_COCV =
symmetrical:<br>> Have OP_CICV take an optional taproot and do the same =
check as is<br>> done for the output: Q =3D=3D tweak(tweak(X,D), T).<br>=
<br>I think that's an excellent suggestion, which I was already explori=
ng<br>for a different purpose: bringing externally signed data onto the<br>=
stack. My goal there was to allow eltoo-style replacement.<br><br>Until rec=
ently, I thought that a clean/efficient version of eltoo<br>would require O=
P_CHECKSIGFROMSTACK or ANYPREVOUT. However, extending<br>OP_CHECKINPUTCONTR=
ACTVERIFY to enable introspection of other inputs<br>allows a reasonable wo=
rkaround: producing a separate UTXO signed with<br>ANYONECANPAY, with the r=
equired data embedded as usual. Spending that<br>UTXO together with the cha=
nnel's UTXO=C2=A0allows one to get that data<br>on the stack (with its =
signature already checked by consensus rules).<br>I drafted this idea in a =
gist [1].<br><br>Remark: it still seems easier (and probably slightly more =
efficient)<br>to build eltoo replacement with CSFS or APO in addition to MA=
TT<br>opcodes.<br><br>A possible semantics for OP_CHECKINPUTCONTRACTVERIFY =
could then be<br>exactly symmetrical to that of OP_CHECKOUTPUTCONTRACTVERIF=
Y, with<br>the exception that the special input index -1 would represent th=
e<br>current input.<br><br>Pushing this further, another option that could =
be be worth exploring<br>is to have a single OP_CHECK_IN_OUT_CONTRACT_VERIF=
Y opcode, with the<br>same semantics as OP_CHECKOUTPUTCONTRACTVERIFY from [=
2], but with an<br>additional `flags` argument, which is a bitmap where:<br=
>- the lowest-significant bit determines if the index refers to inputs<br>=
=C2=A0 or outputs (where input index -1 refers to the current input)<br>- t=
he second bit specifies if amounts should be preserved with<br>=C2=A0 defer=
red checks as described in [2] (only applicable to outputs)<br>- other bits=
are OP_SUCCESS and reserved for future behaviors.<br><br>This would make t=
he opcodes 1-2 bytes larger, but might allow greater<br>flexibility, and ke=
ep some room for future extensions.<br><br>> 2.To make fully functioning=
CoinPools, one would need functionality<br>> similar to OP_MERKLESUB[4]=
: remove some data from the merkle tree, <br>> and remove a key from the=
aggregated internal key.<br><br>It seems likely that efficient use of the =
taproot internal pubkey with<br>"dynamic key aggregation" is not =
possible with the current semantics<br>(unless one ventures into the fraud =
proof machinery, which seems<br>overkill!).<br><br>However, in construction=
s with MATT opcodes, I would never expect the<br>need for data to be stored=
in the taptree. In particular, for the case<br>of CoinPools, the pubkeys o=
f the members could also be stored in the<br>embedded data, having a single=
"unilateral withdrawal" tapleaf.<br>Removing a key would then am=
ount to replacing it with a fixed NUMS key<br>and computing the new root (r=
e-using the same Merkle proof).<br>Note that this is not a lot costlier tha=
n using a tapleaf per user:<br>instead of paying the cost for the Merkle pr=
oof in the control block,<br>you pay for it explicitly in the Script witnes=
s.<br><br>Therefore, I would expect there to be reasonable CoinPools design=
s<br>without additional opcodes =E2=88=92 but I am only moderately confiden=
t as<br>this is beyond the level of sophistication I've been exploring =
so far.<br><br>Best,<br>Salvatore<br><br>[1] - <a href=3D"https://gist.gith=
ub.com/bigspider/041ebd0842c0dcc74d8af087c1783b63">https://gist.github.com/=
bigspider/041ebd0842c0dcc74d8af087c1783b63</a><br>[2] - <a href=3D"https://=
lists.linuxfoundation.org/pipermail/bitcoin-dev/2023-April/021588.html">htt=
ps://lists.linuxfoundation.org/pipermail/bitcoin-dev/2023-April/021588.html=
</a></div></div>
--000000000000dc270d05fcbe5fc6--
|