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
|
Return-Path: <aj@erisian.com.au>
Received: from smtp1.osuosl.org (smtp1.osuosl.org [140.211.166.138])
by lists.linuxfoundation.org (Postfix) with ESMTP id F39A3C000D
for <bitcoin-dev@lists.linuxfoundation.org>;
Fri, 10 Sep 2021 07:42:29 +0000 (UTC)
Received: from localhost (localhost [127.0.0.1])
by smtp1.osuosl.org (Postfix) with ESMTP id E268D83E60
for <bitcoin-dev@lists.linuxfoundation.org>;
Fri, 10 Sep 2021 07:42:29 +0000 (UTC)
X-Virus-Scanned: amavisd-new at osuosl.org
X-Spam-Flag: NO
X-Spam-Score: -1.499
X-Spam-Level:
X-Spam-Status: No, score=-1.499 tagged_above=-999 required=5
tests=[BAYES_00=-1.9, KHOP_HELO_FCRDNS=0.398, SPF_HELO_NONE=0.001,
SPF_NONE=0.001, UNPARSEABLE_RELAY=0.001]
autolearn=no autolearn_force=no
Received: from smtp1.osuosl.org ([127.0.0.1])
by localhost (smtp1.osuosl.org [127.0.0.1]) (amavisd-new, port 10024)
with ESMTP id lHt-NPyUaasd
for <bitcoin-dev@lists.linuxfoundation.org>;
Fri, 10 Sep 2021 07:42:29 +0000 (UTC)
X-Greylist: from auto-whitelisted by SQLgrey-1.8.0
Received: from azure.erisian.com.au (cerulean.erisian.com.au [139.162.42.226])
by smtp1.osuosl.org (Postfix) with ESMTPS id 1938683E59
for <bitcoin-dev@lists.linuxfoundation.org>;
Fri, 10 Sep 2021 07:42:28 +0000 (UTC)
Received: from aj@azure.erisian.com.au (helo=sapphire.erisian.com.au)
by azure.erisian.com.au with esmtpsa (Exim 4.92 #3 (Debian))
id 1mObB2-00070Z-32; Fri, 10 Sep 2021 17:42:25 +1000
Received: by sapphire.erisian.com.au (sSMTP sendmail emulation);
Fri, 10 Sep 2021 17:42:19 +1000
Date: Fri, 10 Sep 2021 17:42:19 +1000
From: Anthony Towns <aj@erisian.com.au>
To: Jeremy <jlrubin@mit.edu>
Message-ID: <20210910074219.GA23578@erisian.com.au>
References: <20210909064138.GA22496@erisian.com.au>
<20210909065330.GB22496@erisian.com.au>
<CAD5xwhgFZPkQ2GbtphQ1DdzMDyeUEt0fKbA5g3jVoGRDVW4kKQ@mail.gmail.com>
MIME-Version: 1.0
Content-Type: text/plain; charset=iso-8859-1
Content-Disposition: inline
Content-Transfer-Encoding: 8bit
In-Reply-To: <CAD5xwhgFZPkQ2GbtphQ1DdzMDyeUEt0fKbA5g3jVoGRDVW4kKQ@mail.gmail.com>
User-Agent: Mutt/1.10.1 (2018-07-13)
X-Spam-Score-int: -18
X-Spam-Bar: -
Cc: Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Subject: Re: [bitcoin-dev] TAPLEAF_UPDATE_VERIFY covenant opcode
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: Fri, 10 Sep 2021 07:42:30 -0000
On Thu, Sep 09, 2021 at 12:26:37PM -0700, Jeremy wrote:
> I'm a bit skeptical of the safety of the control byte. Have you considered the
> following issues?
> If we used the script "0 F 0 TLUV" (H=F, C=0) then we keep the current
> script, keep all the steps in the merkle path (AB and CD), and add
> a new step to the merkle path (F), giving us:
> EF = H_TapBranch(E, F)
> CDEF =H_TapBranch(CD, EF)
> ABCDEF = H_TapBranch(AB, CDEF)
>
> If we recursively apply this rule, would it not be possible to repeatedly apply
> it and end up burning out path E beyond the 128 Taproot depth limit?
Sure. Suppose you had a script X which allows adding a new script A[0..n]
as its sibling. You'd start with X and then go to (A0, X), then (A0,
(A1, X)), then (A0, (A1, (A2, X))) and by the time you added A127 TLUV
would fail because it'd be trying to add a path longer than 128 elements.
But this would be bad anyway -- you'd already have a maximally unbalanced
tree. So the fix for both these things would be to do a key path spend
and rebalance the tree. With taproot, you always want to do key path
spends if possible.
Another approach would be to have X replace itself not with (X, A) but
with (X, (X, A)) -- that way you go from:
/\
A X
to
/\
A /\
X /\
B X
to
/\
/ \
A /\
/ \
/ \
/\ /\
C X B X
and can keep the tree height at O(log(n)) of the number of members.
This means the script X would need a way to reference its own hash, but
you could do that by invoking TLUV twice, once to check that your new
sPK is adding a sibling (X', B) to the current script X, and a second
time to check that you're replacing the current script with (X', (X',
B)). Executing it twice ensures that you've verified X' = X, so you can
provide X' on the stack, rather than trying to include the script's on
hash in itself.
> Perhaps it's OK: E can always approve burning E?
As long as you've got the key path, then I think that's the thing to do.
> If we used the script "0 F 4 TLUV" (H=F, C=4) then we keep the current
> script, but drop the last step in the merkle path, and add a new step
> (effectively replacing the *sibling* of the current script):
> EF = H_TapBranch(E, F)
> ABEF = H_TapBranch(AB, EF)
> If we used the script "0 0 4 TLUV" (H=empty, C=4) then we keep the current
> script, drop the last step in the merkle path, and don't add anything new
> (effectively dropping the sibling), giving just:
> ABE = H_TapBranch(AB, E)
>
> Is C = 4 stable across all state transitions? I may be missing something, but
> it seems that the location of C would not be stable across transitions.
Dropping a sibling without replacing it or dropping the current script
would mean you could re-execute the same script on the new utxo, and
repeat that enough times and the only remaining ways of spending would
be that script and the key path.
> E.g., What happens when, C and E are similar scripts and C adds some clauses
> F1, F2, F3, then what does this sibling replacement do? Should a sibling not be
> able to specify (e.g., by leaf version?) a NOREPLACE flag that prevents
> siblings from modifying it?
If you want a utxo where some script paths are constant, don't construct
the utxo with script paths that can modify them.
> What happens when E adds a bunch of F's F1 F2 F3, is C still in the same
> position as when E was created?
That depends how you define "position". If you have:
/\
R S
and
/\
R /\
S T
then I'd say that "R" has stayed in the same position, while "S" has
been lowered to allow for a new sibling "T". But the merkle path to
R will have changed (from "H(S)" to "H(H(S),H(T))").
> Especially since nodes are lexicographically sorted, it seems hard to create
> stable path descriptors even if you index from the root downwards.
The merkle path will always change unless you have the exact same set
of scripts, so that doesn't seem like a very interesting way to define
"position" when you're adding/removing/replacing scripts.
The "lexical ordering" is just a modification to how the hash is
calculated that makes it commutative, so that H(A,B) = H(B,A), with
the result being that the merkle path for any script in the the R,(S,T)
tree above is the same for the corresponding script in the tree:
/\
/\ R
T S
Cheers,
aj
|
