Implement BIP 340-342 validation - Implement Tapscript script validation rules (BIP 342) (
consensus, taproot) Oct 14, 2020
The PR branch HEAD was 07dd29e1b5 at the time of this review club meeting.
This is the sixth in
a series of review club
meetings on the implementation of BIP 340-342.
This week we’ll look at another commit from the taproot PR (PR 19953) -
. Implement Tapscript script validation rules (BIP
The schnorr/taproot softfork proposal contains:
A new signature scheme (schnorr signatures), defined in
BIP 340 A new way to commit to a script or tree of scripts embedded within a public key (taproot), defined in
BIP 341 A new scripting language (tapscript), defined in
This week, we’re looking at the implementation of tapscript. You should read
the specification of BIP 342 before reviewing the code, and keep a copy handy
while you review to make sure that the implementation matches the
Tapscript has almost identical script semantics to
those defined in BIP
for P2WSH spends, which themselves are almost identical to the semantics for
The main differences between tapscript and P2WSH semantics are:
BIP 340 schnorr signature validation is used for all
OP_CHECKSIGVERIFY evaluation, with a new signature hash
(observe the data input to the
Verify function in the signature validation algorithm).
OP_CHECKMULTISIGVERIFY are disabled, with their
functionality replaced by
Certain opcodes are redefined to mean
OP_SUCCESS and cause validation to succeed immediately.
MINIMALIF becomes a consensus rule.
Almost all of the new code in this commit is in the
EvalScript() interpreter, the
verification code, and the
What additional data does the signature hash commit to, compared to P2WPKH
and P2WSH signatures? Hint: you’ll need to look at the
tapleaf hash definitions in BIP 341. You may also want to review the
review club notes from the session on taproot signature hashing.
OP_CHECKMULTISIGVERIFY disabled in
tapscript? How can you implement a multisig scheme in segwit v1?
What is the purpose of the new
OP_SUCCESS opcodes? How does their
functionality differ from
OP_NOP in pre-segwit and P2WSH script?
Why is MINIMALIF a consensus rule in tapscript?
EvalChecksig() (and the functions it calls) have both a return value and
success out parameter. What are those two values used for? Under what
circumstances can a signature validation fail, but script execution
Why does the
not apply to tapscript?
Why is the
changed from a while loop to a for loop? What is the variable
nOpCount used during tapscript evaluation? Why/why not?
What happens if a tapscript contains an
OP_CHECKSIGADD with a public key that isn’t a 32 byte array? Where is
that behaviour specified in the BIPs? Where is it implemented in the code?
What happens if a tapscript contains an
OP_CHECKSIGADD with an empty signature? Where is that behaviour
specified in the BIPs? Where is it implemented in the code?
Why are stack size limits
ExecuteWitnessScript()? Meeting Log
1 19:00 <@jnewbery> #startmeeting
2 19:00 <@jnewbery> Hi folks! Welcome to Bitcoin Core PR Review Club. Feel free to say 'hi' to let everyone know you're here.
5 19:00 <jonatack> bonsoir!
10 19:00 <@jnewbery> Is it anyone's first time at review club?
12 19:01 <b10c> Would anyone be interested in an auto-generated .ics calendar file for the PR review club with proper title and so on? I need something in my calendar otherwise I miss the meeting every other week.
15 19:01 <michaelfolkson> hi
16 19:01 <nir> hi! first time here
17 19:01 <@jnewbery> b10c: I think wumpus made a calendar with all of the Bitcoin Core meetings, including review club
18 19:01 <buzz08> hi, this is my first time too :-)
19 19:01 <@jnewbery> Yay! Welcome. We love new participants
20 19:01 <vaguely> welcome to the PR review party, nir buzz08
22 19:02 <@jnewbery> Before we begin, a reminder that I'm always looking for hosts for review club and suggestions of what PRs to cover. Feel free to message me anytime if you think you might want to host at some point.
24 19:02 <@jnewbery> You don't need to be the world's foremost authority on something to host. Just commit to spending some time writing notes and questions (I'll help!), and then show up and guide other people through what you've learned and what's interesting about the PR.
25 19:02 <nir> vaguely thank you!
26 19:02 <b10c> jnewbery: thanks! will have a look at that
27 19:02 <@jnewbery> Ok, onto this week's PR. Today we'll be talking about ...
28 19:02 <@jnewbery> 🚰 🚰 🚰 🚰 🚰 🚰 🚰 🚰 🚰 🚰 🚰 🚰 🚰 🚰 🚰 🚰 🚰 🚰 🚰 🚰 🚰 🚰 🚰 🚰 🚰 🚰 🚰
29 19:02 <@jnewbery> _________ _______ _______ _______ _______ _______ _________ _______ _________
30 19:02 <@jnewbery> \__ __/( ___ )( ____ )( ____ \( ____ \( ____ )\__ __/( ____ )\__ __/
31 19:02 <@jnewbery> ) ( | ( ) || ( )|| ( \/| ( \/| ( )| ) ( | ( )| ) (
32 19:02 <@jnewbery> | | | (___) || (____)|| (_____ | | | (____)| | | | (____)| | |
33 19:02 <@jnewbery> | | | ___ || _____)(_____ )| | | __) | | | _____) | |
34 19:02 <@jnewbery> | | | ( ) || ( ) || | | (\ ( | | | ( | |
35 19:02 <@jnewbery> | | | ) ( || ) /\____) || (____/\| ) \ \_____) (___| ) | |
36 19:03 <@jnewbery> )_( |/ \||/ \_______)(_______/|/ \__/\_______/|/ )_(
38 19:03 <@jnewbery> 📜 📜 📜 📜 📜 📜 📜 📜 📜 📜 📜 📜 📜 📜 📜 📜 📜 📜 📜 📜 📜 📜 📜 📜 📜 📜 📜
40 19:03 <pinheadmz> OH YES DUDE +1,000,000
42 19:03 <felixweis> amazing!
44 19:03 <@jnewbery> pinheadmz: thanks, you're an inspiration
45 19:03 <@jnewbery> First things first. Who's had a chance to review the commit (y/n). Absolutely no problem if you didn't have time this week. We'll walk though the changes together.
50 19:04 <robot-dreams> ish
60 19:04 <michaelfolkson> y
61 19:04 <@jnewbery> that's great. Lots of review
62 19:04 <@jnewbery> alright, let's get to it
63 19:04 <@jnewbery> 1. What additional data does the signature hash commit to, compared to P2WPKH and P2WSH signatures? Hint: you’ll need to look at the SigMsg() and tapleaf hash definitions in BIP 341. You may also want to review the review club notes from the session on taproot signature hashing.
66 19:05 <pinheadmz> for one i believe it commits to all the input values for the entire tx
67 19:05 <robot-dreams> Input amounts (so you can be confident of the fee when signing)
68 19:05 <benthecarman> input amounts and spks
69 19:05 <sipa> robot-dreams: which input amounts?
70 19:06 <pinheadmz> and i think we commit to the scriptPubKey which segwit v0 didnt ?
72 19:06 <pinheadmz> sipa all input amounts! unless SIGHASH_ANYONECANPAY is set
73 19:06 <sipa> pinheadmz: indeed!
74 19:07 <sipa> the sighash scheme is mostly in BIP341, with some additions in BIP342
75 19:07 <michaelfolkson> And the leaf version. Obviously that didn't exist for SegWit v0
76 19:07 <sipa> pinheadmz: and indeed, bip143 (the segwit v0 sighash scheme) didn't commit to the scriptPubKey
77 19:07 <@jnewbery> can anyone give me a link/reference for where the sighash is defined?
79 19:08 <@jnewbery> that's it sipa!
80 19:08 <robot-dreams> sipa: previous output spent by a particular input, as well as serialization of all spent output amounts in the transaction?
81 19:08 <felixweis> thats quite the commitment!
82 19:08 <michaelfolkson> Does SegWit v0 commit to the size of the script?
83 19:08 ⚡ michaelfolkson checks
84 19:08 <pinheadmz> oh yeah for bip342 theres also the leaf version and key version which is always 0x00 for now
85 19:08 <sipa> michaelfolkson: which script? :)
86 19:09 <@jnewbery> we covered the taproot signature hash in a previous review club ( https://bitcoincore.reviews/17977). There are also some other things that go into the hash when we're doing a script path spend. Can anyone find the reference for that?
87 19:09 <sipa> robot-dreams: right; bip143 already committed to the input amount being spent; bip341 changes that to cover _all_ input amounts of the transaction, in every input
88 19:09 <michaelfolkson> Trick question sipa? The Tapscript output script?
89 19:10 <robot-dreams> Thanks, that was not clear before
90 19:10 <sipa> michaelfolkson: the one being spent?
91 19:10 <sipa> michaelfolkson: or the one(s) being created?
92 19:10 <sipa> robot-dreams: and not just the amounts, all _all_ scriptpubkeys of the outputs being spent
94 19:12 <@jnewbery> ok, next question. 2. Why are OP_CHECKMULTISIG and OP_CHECKMULTISIGVERIFY disabled in tapscript? How can you implement a multisig scheme in segwit v1?
96 19:12 <pinheadmz> the BIP author (ahem) says those op codes are inefficeint
97 19:12 <nir> because they're inefficient
98 19:12 <benthecarman> they are replaced with OP_CHECKSIGADD
99 19:12 <pinheadmz> i suppose its because you dont know until you get to the end of the script if youve reached the threshold?
101 19:13 <pinheadmz> checksigadd does one at a time and drops a counter back on the stack
102 19:13 <pinheadmz> er, increments a counter
103 19:13 <sipa> why are they inefficient?
104 19:13 <@jnewbery> great. Yes, lots of good answers. checkmultisig is inefficient. It also makes batch validation difficult or impossible I believe
105 19:13 <pinheadmz> i was wondering if it also has something to do with batch verification
107 19:14 <pinheadmz> yeah but with op_CMS you still have an array of signatures on the input
108 19:14 <sipa> indeed, they're inherently incompatible with batch validation
109 19:14 <pinheadmz> sipa is it because op_checksig/multisig use a different transaction digest?
110 19:15 <sipa> in batch validation you need to know ahead of time which (msg,pubkey,sig) triplets are going to have to be valid, and which won't
111 19:15 <pinheadmz> and re: batch - im unclear what actually changes to make the new scheme more cmpatible
113 19:15 <sipa> OP_CMS can't do that, as the same signature is tried against multiple pubkeys
114 19:15 <pinheadmz> AHHHHhhhhhh 💡
115 19:15 <sipa> so it would require a combinatorial explosion
116 19:15 <michaelfolkson> sipa: The one being spent
117 19:16 <pinheadmz> i didnt realize that - so for CMS the order of pubkeys/signatures is not enforced?
118 19:16 <sipa> michaelfolkson: clearly segwitv0 does not commit to the taproot output being spent ;)
119 19:16 <@jnewbery> Anyone got an answer for: How can you implement a multisig scheme in segwit v1?
120 19:16 <sipa> pinheadmz: the order is enforced, but the combination isn't
121 19:16 <elle> i think the order is enforced but there is a placeholder for the missing ones?
122 19:16 <pinheadmz> oh right thanks elle / sipa
123 19:16 <sipa> elle: no placeholder, that's the problem!
124 19:17 <sipa> if there was a placeholder we'd be golden for batch validation
125 19:17 <nir> using Using a single OP_CHECKSIGADD-based script is an alternative
126 19:17 <robot-dreams> jnewbery: Do you have to use something like musig along CHECKSIGAD to get multisig in v1?
127 19:17 <b10c> jnewbery: MuSig?
128 19:17 <sipa> pinheadmz: if you have 2-of-3 with pubkeys [pA, pB, pC], you can spend it with sigs [sA, aB], [sA, sC], or [sB, sC]
129 19:17 <felixweis> in case you can't combine with MuSig?
130 19:17 <@jnewbery> nir: yes, we can create a tapscript with OP_CHECKSIGADD and all the pubkeys
131 19:17 <sipa> OP_CMS just tries all combinations
132 19:17 <michaelfolkson> No robot-dreams. You don't have to
133 19:17 <jesseposner> MuSig requires Schnorr
134 19:17 <pinheadmz> with musig you wnd up with one single signature, so that is actually different than checksigadd
135 19:18 <pinheadmz> if you are using musig you might not even need tapscript! (key path could suffice)
136 19:18 <@jnewbery> robot-dreams b10c: yes! an aggregation scheme like MuSig is another way to create a multisig scheme
137 19:18 <sipa> jesseposner: thankfully, BIP342 disables all ECDSA check opcodes and replaces them with Schnorr ones
138 19:18 <sipa> jnewbery: i suggest reading rationale 5 in BIP342
139 19:19 <elle> sipa: i meant op_checksig add. doesnt it have a placeholder?
140 19:19 <sipa> elle: ah, yes!
141 19:19 <sipa> sorry, i thought you were talking about OP_CMS
142 19:19 <elle> sipa: ok cool :)
143 19:19 <@jnewbery> so that's two ways of having a multisig scheme. Any others?
144 19:19 <nir> Native Schnorr threshold signatures?
145 19:20 <@jnewbery> nir: that's what I meant above by a aggregation scheme.
146 19:20 <b10c> jnewbery: I suppose you could do e.g. a 1-of-2 by having two branches with a single key spend each?
147 19:20 <sipa> jnewbery: i think there is an important distinction
148 19:20 <nir> ah, got it
149 19:20 <felixweis> only these 2
150 19:20 <michaelfolkson> MuSig-DN
151 19:20 <michaelfolkson> MuSig2
152 19:20 <sipa> michaelfolkson: doesn't change the script
153 19:21 <sipa> that's just signing protocol differences
154 19:21 <@jnewbery> b10c: yes, you can break down the different key combinations into different scripts in the tree
155 19:21 ⚡ michaelfolkson checking what question we're answering again
156 19:21 <sipa> you could have a merkle tree where every leaf is a K-of-K MuSig aggregate, or you can use a threshold scheme and just have the key path be the key for the K-of-N entirely (which arguably doesn't involve tapscript at all)
157 19:22 <robot-dreams> Sorry, I'm a little lost and I have a basic question. Unlike CHECKSIG, the new CHECKSIGADD involves an additional CScriptNum value. What's the context for this?
158 19:22 <willcl_ark> Hi! Sorry to miss the beginning of the review; going to try and read the backlog and catch up...
159 19:23 <@jnewbery> sipa: right. Which is why the question was framed as 'multisig scheme in segwit v1'. You can use a single tapscript, a tree of tapscripts, or just the keypath spend (no tapscripts at all)
160 19:23 <sipa> robot-dreams: OP_CHECKSIGADD is literally just a shorthand for OP_ROT OP_SWAP OP_CHECKSIG OP_ADD
162 19:23 <sipa> robot-dreams: because that's an expected common pattern that people would use to replace OP_CHECKMULTISIG
163 19:23 <pinheadmz> and amazingly, OP_ROT rotates exactly three elements, which is perfect for this use case.
164 19:23 <@jnewbery> and I think Murch might also have written something about implementing multisignature schemes in taproot
166 19:24 <@jnewbery> 3. What is the purpose of the new OP_SUCCESS opcodes? How does their functionality differ from OP_NOP in pre-segwit and P2WSH script?
167 19:24 <@jnewbery> thanks jonatack!
168 19:24 <glozow> Script upgradeability!
169 19:24 <pinheadmz> robot-dreams in english: every successful sig verification increments this counter by 1, then the number is returned to the stack
170 19:24 <pinheadmz> its like a small Katamari ball rolling over your signatures
171 19:24 <michaelfolkson> NOP was ignored. SUCCESS results in success instantly
172 19:25 <sipa> robot-dreams: so you can write a 4-of-5 multisig as "pA CS pkB CSA pkC CSA pkD CSA pkE CSA 4 EQUAL"
173 19:25 <vaguely> pinheadmz nice analogy
174 19:25 <robot-dreams> OH!! I didn't realize you would typically use it multiple times. That's why I thought you could ONLY use something like musig.
175 19:25 <sipa> robot-dreams: tapscript is, after, still a script
176 19:25 <@jnewbery> michaelfolkson: yes, exactly
177 19:25 <robot-dreams> That means CSA doesn't add any fancy Schnorr stuff, you could have also just used CS
178 19:25 <robot-dreams> if you wanted to use musig?
179 19:26 <robot-dreams> OK I was very confused but I think I'm good now, thanks
180 19:26 <@jnewbery> why would we want OP_SUCCESS instead of OP_NOP?
181 19:26 <pinheadmz> robot-dreams all sigs in taproot/tapscrtpt still use schnorr
182 19:26 <robot-dreams> OP_SUCCESS makes the entire script succeed just by its presence
183 19:26 <robot-dreams> That is much nicer for soft fork upgrades in the future
184 19:26 <michaelfolkson> I think glozow answered that jnewbery
186 19:26 <sipa> robot-dreams: yes, ideally you have just one signature check in a script, and it's a musig aggregate or native threshold
187 19:26 <felixweis> OP_SUCCESS instead of NOP allows for more versatile future softforking
188 19:26 <pinheadmz> jesseposner nice detail!
189 19:26 <@jnewbery> ah yes! Thanks glozow. Can you expand? Why is it better for upgradeability?
190 19:27 <sipa> robot-dreams: but musig adds complication for signers, and thresholds even more... so people may want to use individual checksigs/checksigadds instead
191 19:27 <@jnewbery> jesseposner: good answer!
192 19:27 <glozow> er, upgrades = restrict spending rules. If we have an automatic success now, it allows lots of flexibility for upgrades?
193 19:28 <glozow> I think i read something about being able to write to the stack with OP_SUCCESS whereas for the NOPS, you can only (1) fail or (2) continue without changing the stack?
194 19:28 <@jnewbery> OP_NOP is rather limited in the semantics it can be repurposed for. It must leave the stack unchanged. OP_SUCCESS can be repurposed to any semantic
195 19:28 <glozow> sorry I didn't prep very well for today :'(
196 19:28 <sipa> glozow: that's exactly it
197 19:28 <@jnewbery> glozow: exactly!
198 19:28 <sipa> NOPs cannot be redefined to do anything, except failing'
199 19:28 <felixweis> for instance future opcodes could read/consume/write 1 or more different stack elements
200 19:29 <sipa> they can't make any observable state changes, because that could result in non-softfork behavior
201 19:29 <@jnewbery> Last question on the spec, then we can move onto the implementation.
202 19:29 <@jnewbery> 4. Why is MINIMALIF a consensus rule in tapscript?
203 19:29 <pinheadmz> malleability!
204 19:29 <michaelfolkson> It was a consensus rule for SegWIt v0 too though right?
205 19:30 <@jnewbery> pinheadmz: I applaud your enthusiasm for malleability, but your answer could use a bit more detail
206 19:30 <pinheadmz> sorry had to get the door lol
208 19:30 <pinheadmz> becsuse lots of vsalues can be "true:
209 19:30 <pinheadmz> so a script that computes IF (9999999) will be the same result as IF(1)
210 19:30 <@jnewbery> michaelfolkson: no, it was added as a standardness rule for segwit v0, but is not consensus
213 19:31 <pinheadmz> minimalif is, i believe already a mempool policy rule
214 19:31 <sipa> yeah, that was something we learned when working on miniscript
215 19:31 <robot-dreams> Without MINIMALIF, would you be able to change the stack values in this way without invalidating any signatures?
216 19:31 <glozow> pinheadmz yup it is
217 19:31 <sipa> it's virtually impossible to write nontrivial malleability-resistant scripts without huge hacks
218 19:32 <@jnewbery> cool. Seems like you've all done a very close reading of the spec. That's great because now we can check that it was implemented properly
219 19:32 <willcl_ark> Otherwise people can replace the top stack element with another True or False value
220 19:32 <@jnewbery> any final questions on the spec before we move on to implementation?
221 19:32 <sipa> willcl_ark: in some cases at least, yes
222 19:32 <pinheadmz> bc input scripts (which contain signatures) can not be signed, and therefore are not invalidated if they are changed in flight, like a man-in-the-middle-attack
223 19:32 <@jnewbery> 1. EvalChecksig() (and the functions it calls) have both a return value and a success out parameter. What are those two values used for? Under what circumstances can a signature validation fail, but script execution succeed?
224 19:33 <pinheadmz> i think we covered this in a previous meeting
225 19:34 <pinheadmz> it can actually be ok for a sig to fail
226 19:34 <elle> i think sig validation can fail during checksigadd when we process the placeholder signatures
228 19:34 <pinheadmz> maybe the script requires a checksig to return false
229 19:34 <@jnewbery> elle: exactly right
230 19:34 <sipa> elle: define "fail" :)
231 19:35 <michaelfolkson> Requires pinheadmz?!
232 19:35 <michaelfolkson> When requires?
233 19:36 <pinheadmz> so maybe key/msg/sig do not match, thats opchecksig -> false
234 19:36 <sipa> michaelfolkson: e.g. a 2-of-3 policy using CSA will require one signature check to return false
235 19:36 <pinheadmz> maybe then theres an IF branch that follows som logic if false
236 19:36 <pinheadmz> but if your pubkey is 100 bytes for example, thats not just a checksig->false, thats an error
237 19:36 <sipa> pinheadmz: almost
238 19:36 <robot-dreams> I think one example where signature validation fails but script execution can succeed (according to `bool success` and return value) is when the signature is empty
239 19:36 <sipa> CS/CSA have a tri-state result: good signature, bad signature, abort script
240 19:37 <elle> sipa: hmmm will have to think about that one. But i mean 'result in checksigadd adding 0'
241 19:37 <sipa> elle: exactly
242 19:37 <pinheadmz> sipa what am i missing ?
243 19:37 <sipa> there is only one way to get that: the signature has to be empty
244 19:38 <@jnewbery> robot-dreams: right - an empty signature is used in cases where we want the signature check to fail, and script execution to continue
246 19:38 <sipa> pinheadmz: an actually non-empty invalid signature will abort the script
247 19:38 <@jnewbery> 2. Why does the MAX_SCRIPT_SIZE limit not apply to tapscript?
248 19:38 <michaelfolkson> I thought CSA was still minimum of 2 in 2-of-3. Not exactly 2
249 19:38 <sipa> it has to, anything else is not compatible with batching
250 19:38 <sipa> michaelfolkson: it is whatever you want it to be
251 19:38 <sipa> michaelfolkson: it's a script, you write it yourself
252 19:38 <felixweis> oh! now i see. i was thiking in sipas example before it was a typo but yeah now it makes sense. CS vs CSA
253 19:39 <sipa> michaelfolkson: e.g. A CS B CSA C CSA D CSA 4 EQUAL
254 19:39 <elle> Because we never need to reveal the entire script. Only its TaggedHash and merkle proof. So script size no longer matters.
256 19:39 <sipa> elle: eh no, the full script gets revealed
257 19:39 <sipa> but only the executed one
258 19:39 <robot-dreams> BIP 342 says "Since there is no scriptCode directly included in the signature hash (only indirectly through a precomputable tapleaf hash), the CPU time spent on a signature check is no longer proportional to the size of the script being executed."
259 19:39 <sipa> if the merkle tree contains multiple scripts, you only reveal the one you actually use
260 19:39 <robot-dreams> However, I'm not sure how / when you could do such precomputation
261 19:39 <elle> sipa: oh right! sorry
262 19:40 <sipa> robot-dreams: once per script
263 19:40 <sipa> it's already implemented
264 19:41 <pinheadmz> jnewbery i have a guess about max script size - because we have this other concept of a scriptop budget now
265 19:41 <pinheadmz> and the max block size / weight is still obviously a hard rule
266 19:41 <michaelfolkson> You'd never want to do that though right... haha. I demand one of my signatures fail. Otherwise fail the script.
267 19:41 <pinheadmz> but since this feels like a relaxation of a size rule im scratching my head over the soft-forkedness of it
268 19:42 <sipa> michaelfolkson: i don't see why not
270 19:42 <pinheadmz> i guess because for old nodes it just looks like a witness item, not necessarily s script
271 19:42 <sipa> michaelfolkson: there is no point in allowing more than 2 sigs for a 2-of-3 multisig... that's just adding cost and malleability
272 19:42 <robot-dreams> sipa: Are you referring to the precomputation in `VerifyTaprootCommitment`?
273 19:43 <sipa> robot-dreams: yes, and it being passed through to the script execution using ScriptExecutionData::m_tapleaf_hash
274 19:43 <Murch> pinheadmz: Since either only a signature is revealed for the key path and exactly one tap branch and one script in a leaf for a script path spend, why do you think maxscriptsize is hard?
275 19:44 <Murch> I'm not sure what you are thinking about
276 19:44 <sipa> pinheadmz: max script size is enforced (for witness v0) at script execution time
277 19:45 <@jnewbery> We're down to 15 minutes, so I'm going to keep moving through the questions. You're always welcome to ask questions about what we've been talking about before.
278 19:45 <sipa> for other witness versions, no script is executed, so no limit applies
279 19:45 <@jnewbery> 3. Why is the script interpreter loop changed from a while loop to a for loop? What is the variable opcode_pos used for?
281 19:45 <robot-dreams> One more thing I don't understand, previously, what was the expensive operation we were trying to avoid with a script size limit?
282 19:46 <pinheadmz> jnewbery i believe this is because the positon of the last OP_CODESEPARATOR is commited to by the signature
283 19:46 <michaelfolkson> Because now we know how many times we want to loop. No reason to switch otherwise
284 19:46 <sipa> robot-dreams: well, you'll need to ask satoshi i'm afraid
285 19:46 <@jnewbery> pinheadmz: yep
286 19:46 <sipa> there are justifications for it, but the exact rule and its design goals were never documented
287 19:47 <sipa> michaelfolkson: no
288 19:47 <michaelfolkson> Hmm do tell
289 19:47 <@jnewbery> we need to know what position we're in, so when we hit an OP_CODESEPARATOR we can save the position
290 19:47 <@jnewbery> because that's committed to in the signature hash
291 19:47 <pinheadmz> Murch i confused myself in thinking that a V1 script would be subject to same rules as V0 script. but its not, because on the blockchain its all just witness stack items. the v0 rules decide something is a script and impose a max limit.
292 19:48 <Murch> pinheadmz: I see
294 19:48 <@jnewbery> 4. Is nOpCount used during tapscript evaluation? Why/why not?
295 19:48 <jonatack> under "codesep_pos" i believe
296 19:48 <robot-dreams> Regarding the note "the CPU time spent on a signature check is no longer proportional to the size of the script being executed" from BIP 342, where was the previous signature check that was proportional to the size of the script being executed?
297 19:49 <jonatack> jnewbery: didn't prep but seems no
298 19:49 <jonatack> from quick look at the code
299 19:49 <@jnewbery> jonatack: you answered the easy question correctly :)
300 19:50 <@jnewbery> Why isn't nOpCount used for tapscript?
302 19:50 <jonatack> it's used in OP_CHECKMULTISIGVERIFY
303 19:50 <jonatack> which is disabled in per bip342
304 19:51 <sipa> robot-dreams: BIP143 includes the scriptCode in its hash, which means that every sigcheck needs to hash the entire script being hashed
305 19:51 <@jnewbery> robot-dreams: yes! "An opcode limit only helps to the extent that it can prevent data structures from growing unboundedly during execution (both because of memory usage, and because of time that may grow in proportion to the size of those structures). The size of stack and altstack is already independently limited. By using O(1) logic for OP_IF, OP_NOTIF, OP_ELSE, and OP_ENDIF as
306 19:51 <@jnewbery> suggested here and implemented here, the only other instance can be avoided as well."
307 19:51 <sipa> robot-dreams: so you could create a script whose execution time is proportional to its length (in witness v0)
308 19:52 <sipa> robot-dreams: another example is that until some time ago, OP_IF/OP_ELSE behavior was O(n) in the depth of nested IFs
309 19:52 <robot-dreams> sipa: Aren't you still doing this after BIP 341, since the tapleaf hash involves the entire script being executed?
310 19:52 <jonatack> that case appears to be line 476 after (sigversion == SigVersion::BASE || sigversion == SigVersion::WITNESS_V0)
311 19:52 <sipa> robot-dreams: no, because it's precomputed
312 19:52 <jonatack> if (opcode > OP_16 && ++nOpCount > MAX_OPS_PER_SCRIPT)
313 19:52 <sipa> that script hashing is done once per script, not per signature
314 19:52 <@jnewbery> jonatack: nOpCount is incremented for _every_ opcode encountered during script execution
315 19:53 <@jnewbery> (for pre-tapscript)
316 19:53 <@jnewbery> 5. What happens if a tapscript contains an OP_CHECKSIG, OP_CHECKSIGVERIFY or OP_CHECKSIGADD with a public key that isn’t a 32 byte array? Where is that behaviour specified in the BIPs? Where is it implemented in the code?
317 19:53 <jonatack> yes, pre-tapscript
318 19:54 <robot-dreams> If the public key is empty, then the script fails and terminates immediately; if it's any other size besides 0 or 32 bytes, signature validation is assumed to be successful unless the SCRIPT_VERIFY_DISCOURAGE_UPGRADABLE_PUBKEYTYPE flag is set
319 19:54 <@jnewbery> robot-dreams: yes. And when is that flag set/unset?
320 19:54 <pinheadmz> another upgrade path
321 19:54 <pinheadmz> i think james prestwich wrote something enumerating all the taproot/script upgrade paths
322 19:54 <@jnewbery> pinheadmz: Yet Another Upgrade Mechanism
323 19:55 <willcl_ark> so it lets you add new sighashes?
324 19:55 <pinheadmz> willcl_ark signature schemese
325 19:55 <willcl_ark> ah ok
328 19:55 <pinheadmz> so without changing anything else, if you have a signature scheme that requires a 45-byte public key that can be soft forked in just using the pubkey size as the flag
330 19:56 <pinheadmz> p.s. sipa any vague ideas or examples of how this could be used? (other schemese?)
331 19:56 <@jnewbery> 6. What happens if a tapscript contains an OP_CHECKSIG, OP_CHECKSIGVERIFY or OP_CHECKSIGADD with an empty signature? Where is that behaviour specified in the BIPs? Where is it implemented in the code?
332 19:56 <sipa> pinheadmz: ANYPREVOUT
333 19:56 <willcl_ark> jnewbery: does this mean that tagging has been accepted for oSIGHASH_NOINPUT? I seem to recall some debate around that...
334 19:56 <sipa> for example uses it think
335 19:56 <willcl_ark> wait, I'm confusing with ANYPREVOUT.
336 19:56 <@jnewbery> willcl_ark: I
337 19:57 <robot-dreams> pinheadmz: jnewbery: I don't understand the question, isn't SCRIPT_VERIFY_DISCOURAGE_UPGRADABLE_PUBKEYTYPE "policy" so nodes can set that flag however they want?
338 19:57 <pinheadmz> sipa hm, because bip341/2 commit to too much speicifc data from the prevout ?
339 19:57 <michaelfolkson> ANYPREVOUT is NOINPUT updated willcl_ark
340 19:57 <@jnewbery> 'm afraid I don't know the latest on SIGHASH_ANYPREVOUT
341 19:57 <pinheadmz> robot-dreams that is correct
342 19:57 <willcl_ark> :lightbulb.gif
343 19:57 <pinheadmz> robot-dreams so a 45 byte pubkey would be allowed in a block
344 19:57 <sipa> pinheadmz: you can't change sighashing for existing keys
345 19:57 <pinheadmz> but we dont really want nodes accepting to mempool or relaying without really understanding whats going on
346 19:58 <@jnewbery> robot-dreams: exactly. We set that flag as policy, so unconfirmed transactions with non 32-byte pubkeys would fail, but would be accepted if included in a block
347 19:58 <sipa> pinheadmz: so you either add new opcodes for the new sighash script, or you introduce them using a new pubkey type
348 19:58 <pinheadmz> sipa so anyprevout could still use bip340-2 all exactly the same but just toss an extra byte on the end of the pubkey?
350 19:58 <sipa> pinheadmz: yes
351 19:58 <pinheadmz> nice im up to three 💡 's today
352 19:59 <robot-dreams> stacie: Agreed, makes sense to me!
353 19:59 <@jnewbery> stacie: that's it!
354 19:59 <sipa> stacie: a few lines below your link, but indeed
355 19:59 <@jnewbery> ok, that's about time. The last question is left as an exercise for the reader
356 20:00 <jonatack> i wish ya'll would post filenames and linenos instead of links (GitHub loadly veerrryyy slowly for me)
357 20:00 <@jnewbery> oops, yes it's the else branch below that
358 20:00 <@jnewbery> jonatack: sorry, all the links are in interpreter.cpp today, the line number is the last few characters of the URL
359 20:00 <stacie> ah! that's correct :)
360 20:00 <pinheadmz> good jam everyone! thanks as always 🧠 jnewbery sipa
362 20:01 <@jnewbery> thanks all. Let's call it there
363 20:01 <Sound> Thanks! :jnewbery
364 20:01 <@jnewbery> #endmeeting
365 20:01 <robot-dreams> Thanks!
366 20:01 <jesseposner> thanks!
367 20:01 <glozow> thanks jnewbery!
368 20:01 <sipa> thanks for hosting, jnewbery!
370 20:01 <felixweis> thanks!
371 20:01 <willcl_ark> thanks all!
372 20:01 <michaelfolkson> Thanks jnewbery for doing aaaalll 6 Taproot sessions. Sad we can't do another 6!
373 20:01 <stacie> thanks jnewbery!
374 20:01 <emzy> Thanks all!
375 20:01 <jonatack> thanks!
376 20:01 <elle> that was great! thanks!
377 20:01 <buzz08> Thanks everybody. It was great to get to know so much stuff for the first time.
378 20:01 <@jnewbery> thanks for coming sipa!
379 20:01 <michaelfolkson> And thanks sipa for providing content for 6 PR review club sessions!
380 20:02 <willcl_ark> it'll be merged this week so we can do the next session on activation ;)
381 20:02 <nir> thanks everyone!
382 20:02 <michaelfolkson> The best way to get rid of sipa is to move onto activation
384 20:02 <sipa> michaelfolkson: i do hope there are not another 120 taproot sessions
385 20:03 <michaelfolkson> 120 Taproot activation sessions
387 20:03 <michaelfolkson> Haha
388 20:03 <jonatack> jnewbery: yes, i should have been parsing those github links rather than waiting a minute for the page to load
389 20:04 <willcl_ark> can't get the filename from them so easliy though
390 20:04 <@jnewbery> jonatack: it's annoying that the file name doesn't show up in them, but we were only in one file today
391 20:07 <robot-dreams> Can I follow up about MAX_SCRIPT_SIZE / precomputation? I think I'm still missing a lot of context about that.
392 20:07 <sipa> robot-dreams: happy to discuss
393 20:07 <robot-dreams> Thanks! So I think the basic pieces are, "when do we do signature checks" and "when do we call VerifyTaprootCommitment to precompute the tapleaf hash".
394 20:08 <robot-dreams> One guess is that we do signature checks much more often than calling VerifyTaprootCommitment, and that would resolve my confusion
395 20:11 <sipa> robot-dreams: yes, of course
396 20:12 <sipa> robot-dreams: VerifyTaprootCommitment is called once per script
397 20:12 <sipa> a script can contain many CS/CSA/CSV opcodes
398 20:14 <robot-dreams> Oh!! So we're trying to defend against the case where someone is like CS CS CS CS CS CS CS CS
399 20:15 <felixweis> there was a CS CS CS CS CS ... in the past
400 20:15 <robot-dreams> Am I understanding correctly that we could've made this precomputing optimization even without Taproot, but Taproot is a nice opportunity to make this change anyway?
402 20:16 <emzy> sadly you need a google account for it.
403 20:16 <wumpus> yes, i'm not trying to promote google or anything, you don't *need* to use it at all, was just fyi
404 20:17 <sipa> robot-dreams: no
405 20:17 <sipa> robot-dreams: because the bip143 sighash script inserts the full scriptCode in every sighash
406 20:18 <@jnewbery> thanks wumpus!
408 20:26 <robot-dreams> sipa: OK, I'm looking at `SignatureHash` vs `SignatureHashSchnorr` now. In both cases you have to include the script in what you're signing. In `SignatureHash` you include the entire script. In `SignatureHashSchnorr` you include the tapleaf hash.
410 20:26 <sipa> and the tapleaf has is constant size
411 20:26 <robot-dreams> so for a script that's like CS CS CS CS CS, in the `SignatureHash` case it's you're doing O(n^2) work in the number of CS that you have but in the `SignatureHashSchorr` case it's O(n)
412 20:27 <robot-dreams> Before Taproot you couldn't make such an optimization without changing consensus
413 20:28 <robot-dreams> Thanks so much sipa, this is very helpful
418 20:44 <jonatack> sipa: thanks for the paper