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
|
Return-Path: <laolu32@gmail.com>
Received: from smtp4.osuosl.org (smtp4.osuosl.org [140.211.166.137])
by lists.linuxfoundation.org (Postfix) with ESMTP id 79383C002C
for <bitcoin-dev@lists.linuxfoundation.org>;
Sat, 16 Apr 2022 02:43:23 +0000 (UTC)
Received: from localhost (localhost [127.0.0.1])
by smtp4.osuosl.org (Postfix) with ESMTP id 5198D41A6B
for <bitcoin-dev@lists.linuxfoundation.org>;
Sat, 16 Apr 2022 02:43:23 +0000 (UTC)
X-Virus-Scanned: amavisd-new at osuosl.org
X-Spam-Flag: NO
X-Spam-Score: -1.847
X-Spam-Level:
X-Spam-Status: No, score=-1.847 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_ENVFROM_END_DIGIT=0.25, FREEMAIL_FROM=0.001,
FUZZY_CPILL=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
Authentication-Results: smtp4.osuosl.org (amavisd-new);
dkim=pass (2048-bit key) header.d=gmail.com
Received: from smtp4.osuosl.org ([127.0.0.1])
by localhost (smtp4.osuosl.org [127.0.0.1]) (amavisd-new, port 10024)
with ESMTP id fZ6TF9qvS2OE
for <bitcoin-dev@lists.linuxfoundation.org>;
Sat, 16 Apr 2022 02:43:21 +0000 (UTC)
X-Greylist: whitelisted by SQLgrey-1.8.0
Received: from mail-wr1-x429.google.com (mail-wr1-x429.google.com
[IPv6:2a00:1450:4864:20::429])
by smtp4.osuosl.org (Postfix) with ESMTPS id 61ABD41A5F
for <bitcoin-dev@lists.linuxfoundation.org>;
Sat, 16 Apr 2022 02:43:21 +0000 (UTC)
Received: by mail-wr1-x429.google.com with SMTP id q3so11806186wrj.7
for <bitcoin-dev@lists.linuxfoundation.org>;
Fri, 15 Apr 2022 19:43:21 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20210112;
h=mime-version:references:in-reply-to:from:date:message-id:subject:to
:cc; bh=jRQu5cO+8lQo4zGKRTR0yUFNrJjZv3Ae+3ZHzBxeh+g=;
b=WCyHTSYfO0Y5cYCFwyTdJc/8/7FqtCpU6o9zdxGSOIvruInfu0kQR7h63F7PI2rY/p
8+rGfL1ADRYvgJgqQVUyWpPHUi7Vm6N6qUj+IwDyNIjmoTVfCkUT0FnHjCjCKKwgiBSv
WMSFd1PXMYCknBMywrUVRRALGVDUjamrYftRogg9kPCkmomoDKOz1wRDVA4ZvPY0dGbM
8qQsnOEq6kDqYvBy7voLJTeeswBTpPW/ND04kGUb6MzS9TaJoydCP6MGqdnd5tKmlzrF
BB2kAjIlV8SbgXDEBsk1inNZt4S2sHE2WwtBH4mf4V9u3o8bWkeZz5+QJo9tH7f2r5fj
ZGkA==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
d=1e100.net; s=20210112;
h=x-gm-message-state:mime-version:references:in-reply-to:from:date
:message-id:subject:to:cc;
bh=jRQu5cO+8lQo4zGKRTR0yUFNrJjZv3Ae+3ZHzBxeh+g=;
b=C24kjhqlWjOFnQRAzfKUXNQKRPf4Mh9PJRe2ubusawJwLR7gQIFKR+2VDXS7JyAWhE
wSbGrXl8lD76+7P1DX+DcsWJaGHwDxx6jscr5IcmBR23ZG2NYE76n3flc3TVEctCJh6b
ObFWCb78pz8AdtqTg9iL3dZyxfO1Ptgv/B1vEH7hG3tyU30cutqhFK1YO1DRG0NfRwaA
BWnoSwJ7auX9NAj+cJqQRWxOrfcjQsrfPF5IiSCivWv3U5hUjtKhnCICXRr/Vinx+4e/
LEKwv57rAd/OT60iWsSdbnObafg5bZKYiu2BCwPU7KDGW6RYDglsencY+tmYUkHOxptM
513g==
X-Gm-Message-State: AOAM531vBMpm3oBaU7xoHGeUcdA2hMqCOw7gbUeUz2RlhN/CYGa4OEY7
ZNM3BL48KatJ16ihxOHR97YfTDABXTWQyIWq8pntUmIZiqo=
X-Google-Smtp-Source: ABdhPJx5Qu/He7CcM0c6w1SYj4Q9uGygQNLzW/HbVPv31Cm4bDx4PooMvPWTvr8u5Ykm93ilBvgEH7wtfkioweX3NNI=
X-Received: by 2002:adf:914f:0:b0:1ed:bb92:d0cc with SMTP id
j73-20020adf914f000000b001edbb92d0ccmr1102133wrj.297.1650076999240; Fri, 15
Apr 2022 19:43:19 -0700 (PDT)
MIME-Version: 1.0
References: <CAO3Pvs_pkYAYsrAEtv3KuJevXQHBLZQ-ihjP4Ur_A1NjJRA+Lw@mail.gmail.com>
<CAPv7TjYTjvSV7UFgOwif6tFj3jVxDfJdW-p_cyPoAGGWKQbwRQ@mail.gmail.com>
<CAO3Pvs_-igT37fcD29=ATSRX7dW5mGKrLGrXp=iJjaN_t3NGww@mail.gmail.com>
In-Reply-To: <CAO3Pvs_-igT37fcD29=ATSRX7dW5mGKrLGrXp=iJjaN_t3NGww@mail.gmail.com>
From: Olaoluwa Osuntokun <laolu32@gmail.com>
Date: Fri, 15 Apr 2022 19:43:08 -0700
Message-ID: <CAO3Pvs9kdOQWv14RRTnX7fYxhPDUP-JRyXc6uXqU0t+twCeAew@mail.gmail.com>
To: Ruben Somsen <rsomsen@gmail.com>
Content-Type: multipart/alternative; boundary="00000000000064523705dcbc7d9c"
Cc: Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Subject: Re: [bitcoin-dev] Taro: A Taproot Asset Representation Overlay
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: Sat, 16 Apr 2022 02:43:23 -0000
--00000000000064523705dcbc7d9c
Content-Type: text/plain; charset="UTF-8"
Hi y'all,
> In terms of achieving this level of binding within the Taro tree itself, I
> can think of three options:
The earlier BIP draft just sort of said "the commitment should be unique"
and hand waved away the exact algorithm used to verify this key property. I
thought about a few ways to do this, but most of them can't work, as the
taproot tree is always sorting the siblings before hashing them into a
parent.
This sorting means that all ordering information is lost, and can't be
obtained again afaict.
To get around this limitation, I've proposed a concrete scheme here to both
verify that the commitment is in a unique place within the tree, and also
that it doesn't exist anywhere else in the transaction (assumes widespread
usage of BIP 86): https://github.com/Roasbeef/bips/pull/21.
A series of inclusion and non-inclusion proofs are used to construct+verify
this property. At a high level the scheme takes advantage of the tagged hash
scheme used in taproot: leaves use "TapLeaf" as the tag, and branches use
"TapBranch" as the tag. Building upon this, we then require the Taro
commitment to be in the leftmost/rightmost (remember ordering info is lost)
of the tree. From here we can decompose things into a few different cases:
* The control block proof is 32 bytes, meaning there's only a single
element, so verify the taro commitment and the taproot commitment is
correct.
* The proof is instead 64 bytes, meaning there's a leaf at depth 1 with a
sibling:
* If the sibling is a leaf, then verify the pre-image is 32 bytes and
the tagged hash calc matches up.
* If the sibling is a branch, then verify that hashing the two opaque
siblings that make it up gives the same branch (tap hash branch).
From the PoV of wallets, this isn't too hard to manage as a Taro library can
just take the existing root of the wallet's scripts, and merge that into a
new root with the Taro leaf hanging off to the side.
As an aside, one thing that's missing in the ecosystem today is a
standardized algorithm for constructing a taproot tree given a set of script
leaves. The tree constructor has a lot of freedom to do things like put more
common things higher up in the tree, or always try to make the tree uniform,
etc, etc. The btcsuite libraries use a simple algo [1] I came up with that
just merges leaves into branches until there're no leaves left (even number)
or there's one leaf, with that last leaf being merged with the final branch.
After that you just keep on merging. It's not the most optimized/efficient
routine but it's simple which counts for a lot IMO.
Admittedly as is defined in my PR above, Taro is a bit demanding w.r.t
commitment space: it wants the highest position in the tree as that's easy
to verify and makes a smaller proof. The impact for items in the script tree
itself isn't too bad as it just means an extra 32 byte hash in the control
block proof when it comes to reveal time, and that's witness data which is
discounted at the block size level.
Zooming out a bit, assuming that applications/protocols start making more
structured commitments in the tapscript tree, it may make sense to roll out
a distinct BIP that carves out an explicit structure/split. As an example, a
new standard could be created that pushes all the actual scripts to the
"left" and everything else to the "right". In the "right" part of the tree,
we can use w/e tree structure we want, so we aren't bound by the sorting
quirk. If each project picks some 32-byte value (a hash of the name or w/e),
then another SMT (or w/e other merklalized k-v map) can be used to place
each root commitment in a unique location in the tree. Maybe something like
this also becomes the basis of future consensus-critical commitments (utxo
commitments, etc, etc)?
-- Laolu
[1]:
https://github.com/btcsuite/btcd/blob/99e4e00345017a70eadc4e1d06353c56b23bb15c/txscript/taproot.go#L618
--00000000000064523705dcbc7d9c
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
<div dir=3D"ltr">Hi y'all, <br><br>> In terms of achieving this leve=
l of binding within the Taro tree itself, I<br>> can think of three opti=
ons:<br><br>The earlier BIP draft just sort of said "the commitment sh=
ould be unique"<br>and hand waved away the exact algorithm used to ver=
ify this key property. I<br>thought about a few ways to do this, but most o=
f them can't work, as the<br>taproot tree is always sorting the sibling=
s before hashing them into a parent.<br>This sorting means that all orderin=
g information is lost, and can't be<br>obtained again afaict.<br><br>To=
get around this limitation, I've proposed a concrete scheme here to bo=
th<br>verify that the commitment is in a unique place within the tree, and =
also<br>that it doesn't exist anywhere else in the transaction (assumes=
widespread<br>usage of BIP 86): <a href=3D"https://github.com/Roasbeef/bip=
s/pull/21">https://github.com/Roasbeef/bips/pull/21</a>.<br><br>A series of=
inclusion and non-inclusion proofs are used to construct+verify<br>this pr=
operty. At a high level the scheme takes advantage of the tagged hash<br>sc=
heme used in taproot: leaves use "TapLeaf" as the tag, and branch=
es use<br>"TapBranch" as the tag. Building upon this, we then req=
uire the Taro<br>commitment to be in the leftmost/rightmost (remember order=
ing info is lost)<br>of the tree. From here we can decompose things into a =
few different cases:<br><br>=C2=A0 * The control block proof is 32 bytes, m=
eaning there's only a single<br>=C2=A0 =C2=A0 element, so verify the ta=
ro commitment and the taproot commitment is<br>=C2=A0 =C2=A0 correct.<br><b=
r>=C2=A0 * The proof is instead 64 bytes, meaning there's a leaf at dep=
th 1 with a<br>=C2=A0 =C2=A0 sibling:<br>=C2=A0 =C2=A0 * If the sibling is =
a leaf, then verify the pre-image is 32 bytes and<br>=C2=A0 =C2=A0 =C2=A0 t=
he tagged hash calc matches up.<br>=C2=A0 =C2=A0 * If the sibling is a bran=
ch, then verify that hashing the two opaque<br>=C2=A0 =C2=A0 =C2=A0 sibling=
s that make it up gives the same branch (tap hash branch).<br><br><br>From =
the PoV of wallets, this isn't too hard to manage as a Taro library can=
<br>just take the existing root of the wallet's scripts, and merge that=
into a<br>new root with the Taro leaf hanging off to the side. <br><br>As =
an aside, one thing that's missing in the ecosystem today is a<br>stand=
ardized algorithm for constructing a taproot tree given a set of script<br>=
leaves. The tree constructor has a lot of freedom to do things like put mor=
e<br>common things higher up in the tree, or always try to make the tree un=
iform,<br>etc, etc. The btcsuite libraries use a simple algo [1] I came up =
with that<br>just merges leaves into branches until there're no leaves =
left (even number)<br>or there's one leaf, with that last leaf being me=
rged with the final branch.<br>After that you just keep on merging. It'=
s not the most optimized/efficient<br>routine but it's simple which cou=
nts for a lot IMO.<br><br>Admittedly as is defined in my PR above, Taro is =
a bit demanding w.r.t<br>commitment space: it wants the highest position in=
the tree as that's easy<br>to verify and makes a smaller proof. The im=
pact for items in the script tree<br>itself isn't too bad as it just me=
ans an extra 32 byte hash in the control<br>block proof when it comes to re=
veal time, and that's witness data which is<br>discounted at the block =
size level.<br><br>Zooming out a bit, assuming that applications/protocols =
start making more<br>structured commitments in the tapscript tree, it may m=
ake sense to roll out<br>a distinct BIP that carves out an explicit structu=
re/split. As an example, a<br>new standard could be created that pushes all=
the actual scripts to the<br>"left" and everything else to the &=
quot;right". In the "right" part of the tree,<br>we can use =
w/e tree structure we want, so we aren't bound by the sorting<br>quirk.=
If each project picks some 32-byte value (a hash of the name or w/e),<br>t=
hen another SMT (or w/e other merklalized k-v map) can be used to place<br>=
each root commitment in a unique location in the tree. Maybe something like=
<br>this also becomes the basis of future consensus-critical commitments (u=
txo<br>commitments, etc, etc)?<br><br>-- Laolu<br><br>[1]: <a href=3D"https=
://github.com/btcsuite/btcd/blob/99e4e00345017a70eadc4e1d06353c56b23bb15c/t=
xscript/taproot.go#L618">https://github.com/btcsuite/btcd/blob/99e4e0034501=
7a70eadc4e1d06353c56b23bb15c/txscript/taproot.go#L618</a><br></div>
--00000000000064523705dcbc7d9c--
|
