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
|
Return-Path: <aj@erisian.com.au>
Received: from whitealder.osuosl.org (smtp1.osuosl.org [140.211.166.138])
by lists.linuxfoundation.org (Postfix) with ESMTP id 45325C077D
for <bitcoin-dev@lists.linuxfoundation.org>;
Fri, 6 Dec 2019 04:52:04 +0000 (UTC)
Received: from localhost (localhost [127.0.0.1])
by whitealder.osuosl.org (Postfix) with ESMTP id 3B7B4883BB
for <bitcoin-dev@lists.linuxfoundation.org>;
Fri, 6 Dec 2019 04:52:04 +0000 (UTC)
X-Virus-Scanned: amavisd-new at osuosl.org
Received: from whitealder.osuosl.org ([127.0.0.1])
by localhost (.osuosl.org [127.0.0.1]) (amavisd-new, port 10024)
with ESMTP id 35+Sw21+pwa4
for <bitcoin-dev@lists.linuxfoundation.org>;
Fri, 6 Dec 2019 04:52:03 +0000 (UTC)
X-Greylist: from auto-whitelisted by SQLgrey-1.7.6
Received: from azure.erisian.com.au (cerulean.erisian.com.au [139.162.42.226])
by whitealder.osuosl.org (Postfix) with ESMTPS id 3800C883B8
for <bitcoin-dev@lists.linuxfoundation.org>;
Fri, 6 Dec 2019 04:52:03 +0000 (UTC)
Received: from aj@azure.erisian.com.au (helo=sapphire.erisian.com.au)
by azure.erisian.com.au with esmtpsa (Exim 4.89 #1 (Debian))
id 1id5aw-0005Bi-6O; Fri, 06 Dec 2019 14:51:59 +1000
Received: by sapphire.erisian.com.au (sSMTP sendmail emulation);
Fri, 06 Dec 2019 14:51:53 +1000
Date: Fri, 6 Dec 2019 14:51:53 +1000
From: Anthony Towns <aj@erisian.com.au>
To: Russell O'Connor <roconnor@blockstream.io>
Message-ID: <20191206045153.dufkatmm6izcy4dw@erisian.com.au>
References: <CAMZUoKm7Y8bRJ+hqmvyPwwTWHaMA7JJc5TZdx7Eufax9G0D=Gg@mail.gmail.com>
<20191128080659.msrpdpcjhhvbqtv2@erisian.com.au>
<CAMZUoKmYi6btmhN8NmePPZNpPtXwNp=EpyYrxo7P2Ug7fnPSwQ@mail.gmail.com>
<20191203083538.ggiginwo5k6m4ywq@erisian.com.au>
<CAMZUoKkRVE-1hPvAZmo4QfLRBgeXzxk0bBncN9eZ110+Hb7T+A@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: <CAMZUoKkRVE-1hPvAZmo4QfLRBgeXzxk0bBncN9eZ110+Hb7T+A@mail.gmail.com>
User-Agent: NeoMutt/20170113 (1.7.2)
X-Spam-Score-int: -18
X-Spam-Bar: -
Cc: Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Subject: Re: [bitcoin-dev] Signing CHECKSIG position in Tapscript
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, 06 Dec 2019 04:52:04 -0000
On Thu, Dec 05, 2019 at 03:24:46PM -0500, Russell O'Connor wrote:
Thanks for the careful write up! That matches what I was thinking.
> This analysis suggests that we should amend CODESEPARATORs behaviour to update
> an accumulator (presumably a running hash value), so that all executed
> CODESEPARATOR positions end up covered by the signature.
On IRC, gmaxwell suggests "OP_BREADCRUMB" as a name for (something like)
this functionality.
(I think it's a barely plausible stretch to use the name "CODESEPARATOR"
for marking a position in the script -- that separates what was before
and after, at least; anything more general seems like it warrants a
better name though)
> That would provide a
> solution to the above problem for those cases where taproot's MAST cannot be
> used. I'm not sure if it is better to propose such an amendment to
> CODESEPARATOR's behaviour now, or to propose to soft-fork in such optional
> behaviour at a later time.
> However, what I said above was even too simplified.
FWIW, I think it's too soon to propose this because (a) it's not clear
there's a practical need for it, (b) it's not clear the functionality is
quite right (opcode vs more automatic sighash flag?), and (c) as you say,
it's not clear it's powerful enough.
> In general, a policy of the form.
> (Exists w[1]. C[1](w[1]) && PK[1,1](w[1]) && ... && PK[1,m[1]](w[1]) || ...
> || (Exists w[n]. C[n](w[n]) && PK[n,1](w[n]) && ... && PK[n,m[n]](w[n]))
> where each term could possibly be parameterized by some witness value (though
> at the moment there isn't enough functionality in Script to parameterize the
> pubkeys in any reasonably way and it maybe isn't even possible to parameterise
> the conditions in any reasonable way). In general, you might want your
> signature to cover (some function of) this witness value. This suggests that
> we would actually want a CODESEPARATOR variant that pushes a stack item into
> the accumulator that gets covered by the signature rather than pushing the
> CODESEPARATOR position. Though at this point the name CODESEPARATOR is
> probably not suitable, even if it subsumes the functionality.
> Again, I'm not
> sure if it is better to propose such a replacement for CODESEPARATOR's
> behaviour now, or to propose to soft-fork in such optional behaviour at a later
> time.
Last bit first, it seems pretty clear to me that this is too novel an
idea to propose it immediately -- we should explore the problem space
more first to see what's the best way of doing it before coding it into
consensus. And (guessing) I think the tapscript upgrade methods should
be fine for handling this later.
I think the annex is also not general enough for what you're thinking
here, in that it wouldn't allow for one signature to constrain the witness
data more than some other signature -- so you'd need to determine all
the constraints for all signatures to finish filling out the annex,
and could only then start signing.
I think you could conceivably do any/all of:
* commit to a hash of all the witness data that hasn't been popped off
the stack ("suffix" commitment -- the data will be used by later script
opcodes)
* commit to a hash of all the witness data that has been popped off the
stack ("prefix" commitment -- this is the data that's been used by
earlier script opcodes)
* commit to the hash of the current stack
That would be expensive, but still doable as O(1) per opcode / stack
element. I think any other masking would mean you'd have potentially
O(size of witness data) or O(size of stack) runtime per signature which
I think would be unacceptable...
I guess a general implementation to at least think about the possibilities
might be an "OP_DATACOMMIT" opcode that pops an element from the stack,
does hash_"DataCommit"(element), and then any later signatures commit
to that value (maybe with OP_0 OP_DATACOMMIT allowing you to get back to
the default state). You'd either need to write your script carefully to
commit to witness data you're using elsewhere, or have some other new
opcodes to do that more conveniently...
CODESEP at position "x" in the script is equivalent to "<x> DATACOMMIT"
here, I think. "BREADCRUMB .. BREADCRUMB" could be something like:
OP_0 TOALT [at start of script]
..
FROMALT x CAT SHA256 DUP TOALT DATACOMMIT
..
FROMALT y CAT SHA256 DUP TOALT DATACOMMIT
if the altstack was otherwise unused, I guess; so the accumulator
behaviour probably warrants something better.
It also more or less gives you CHECKSIGFROMSTACK behaviour by doing
"SWAP OP_DATACOMMIT OP_CHECKSIG" and a SIGHASH_NONE|ANYPREVOUTANYSCRIPT
signature.
But that seems like a plausible generalisation to think about?
Cheers,
aj
|
