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 BIP 342
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
specification.
Tapscript has almost identical script semantics to those defined in BIP
141
for P2WSH spends, which themselves are almost identical to the semantics for
pre-segwit script.
The main differences between tapscript and P2WSH semantics are:
BIP 340 schnorr signature validation is used for all OP_CHECKSIG and
OP_CHECKSIGVERIFY evaluation, with a new signature hash
(observe the data input to the Verify function in the signature validation algorithm).
OP_CHECKMULTISIG and OP_CHECKMULTISIGVERIFY are disabled, with their
functionality replaced by OP_CHECKSIGADD.
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
src/script/interpreter.cpp
file,
inside the EvalScript() interpreter, the EvalChecksig() signature
verification code, and the ExecuteWitnessScript() and
VerifyWitnessProgram() functions.
Questions
Specification
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.
Why are OP_CHECKMULTISIG and 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?
Implementation
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?
Why is the script interpreter
loop
changed from a while loop to a for loop? What is the variable opcode_pos used
for?
Is nOpCount used during tapscript evaluation? Why/why not?
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?
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?
<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.
<@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.
<@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.
<@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.
<@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.
<@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?
<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
<@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?
<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)
<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?
<@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)
<sipa> robot-dreams: but musig adds complication for signers, and thresholds even more... so people may want to use individual checksigs/checksigadds instead
<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?
<@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
<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
<@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?
<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
<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."
<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?
<@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.
<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.
<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?
<@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
<@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?
<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
<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
<@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?
<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?
<@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
<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".
<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?
<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.
<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)
