Skip to content

Commit 72422ce

Browse files
jl2012sipa
jl2012
authored and
sipa
committed
Implement Tapscript script validation rules (BIP 342)
This adds a new `SigVersion::TAPSCRIPT`, makes the necessary interpreter changes to make it implement BIP342, and uses them for leaf version 0xc0 in Taproot script path spends.
1 parent 330de89 commit 72422ce

File tree

6 files changed

+234
-19
lines changed

6 files changed

+234
-19
lines changed

‎src/script/interpreter.cpp‎

Lines changed: 168 additions & 18 deletions
Original file line numberDiff line numberDiff line change
@@ -342,13 +342,10 @@ class ConditionStack {
342342
};
343343
}
344344

345-
/** Helper for OP_CHECKSIG and OP_CHECKSIGVERIFY
346-
*
347-
* A return value of false means the script fails entirely. When true is returned, the
348-
* fSuccess variable indicates whether the signature check itself succeeded.
349-
*/
350-
static bool EvalChecksig(const valtype& vchSig, const valtype& vchPubKey, CScript::const_iterator pbegincodehash, CScript::const_iterator pend, unsigned int flags, const BaseSignatureChecker& checker, SigVersion sigversion, ScriptError* serror, bool& fSuccess)
345+
static bool EvalChecksigPreTapscript(const valtype& vchSig, const valtype& vchPubKey, CScript::const_iterator pbegincodehash, CScript::const_iterator pend, unsigned int flags, const BaseSignatureChecker& checker, SigVersion sigversion, ScriptError* serror, bool& fSuccess)
351346
{
347+
assert(sigversion == SigVersion::BASE || sigversion == SigVersion::WITNESS_V0);
348+
352349
// Subset of script starting at the most recent codeseparator
353350
CScript scriptCode(pbegincodehash, pend);
354351

@@ -371,6 +368,66 @@ static bool EvalChecksig(const valtype& vchSig, const valtype& vchPubKey, CScrip
371368
return true;
372369
}
373370

371+
static bool EvalChecksigTapscript(const valtype& sig, const valtype& pubkey, ScriptExecutionData& execdata, unsigned int flags, const BaseSignatureChecker& checker, SigVersion sigversion, ScriptError* serror, bool& success)
372+
{
373+
assert(sigversion == SigVersion::TAPSCRIPT);
374+
375+
/*
376+
* The following validation sequence is consensus critical. Please note how --
377+
* upgradable public key versions precede other rules;
378+
* the script execution fails when using empty signature with invalid public key;
379+
* the script execution fails when using non-empty invalid signature.
380+
*/
381+
success = !sig.empty();
382+
if (success) {
383+
// Implement the sigops/witnesssize ratio test.
384+
// Passing with an upgradable public key version is also counted.
385+
assert(execdata.m_validation_weight_left_init);
386+
execdata.m_validation_weight_left -= VALIDATION_WEIGHT_PER_SIGOP_PASSED;
387+
if (execdata.m_validation_weight_left < 0) {
388+
return set_error(serror, SCRIPT_ERR_TAPSCRIPT_VALIDATION_WEIGHT);
389+
}
390+
}
391+
if (pubkey.size() == 0) {
392+
return set_error(serror, SCRIPT_ERR_PUBKEYTYPE);
393+
} else if (pubkey.size() == 32) {
394+
if (success && !checker.CheckSchnorrSignature(sig, pubkey, sigversion, execdata, serror)) {
395+
return false; // serror is set
396+
}
397+
} else {
398+
/*
399+
* New public key version softforks should be defined before this `else` block.
400+
* Generally, the new code should not do anything but failing the script execution. To avoid
401+
* consensus bugs, it should not modify any existing values (including `success`).
402+
*/
403+
if ((flags & SCRIPT_VERIFY_DISCOURAGE_UPGRADABLE_PUBKEYTYPE) != 0) {
404+
return set_error(serror, SCRIPT_ERR_DISCOURAGE_UPGRADABLE_PUBKEYTYPE);
405+
}
406+
}
407+
408+
return true;
409+
}
410+
411+
/** Helper for OP_CHECKSIG, OP_CHECKSIGVERIFY, and (in Tapscript) OP_CHECKSIGADD.
412+
*
413+
* A return value of false means the script fails entirely. When true is returned, the
414+
* success variable indicates whether the signature check itself succeeded.
415+
*/
416+
static bool EvalChecksig(const valtype& sig, const valtype& pubkey, CScript::const_iterator pbegincodehash, CScript::const_iterator pend, ScriptExecutionData& execdata, unsigned int flags, const BaseSignatureChecker& checker, SigVersion sigversion, ScriptError* serror, bool& success)
417+
{
418+
switch (sigversion) {
419+
case SigVersion::BASE:
420+
case SigVersion::WITNESS_V0:
421+
return EvalChecksigPreTapscript(sig, pubkey, pbegincodehash, pend, flags, checker, sigversion, serror, success);
422+
case SigVersion::TAPSCRIPT:
423+
return EvalChecksigTapscript(sig, pubkey, execdata, flags, checker, sigversion, serror, success);
424+
case SigVersion::TAPROOT:
425+
// Key path spending in Taproot has no script, so this is unreachable.
426+
break;
427+
}
428+
assert(false);
429+
}
430+
374431
bool EvalScript(std::vector<std::vector<unsigned char> >& stack, const CScript& script, unsigned int flags, const BaseSignatureChecker& checker, SigVersion sigversion, ScriptExecutionData& execdata, ScriptError* serror)
375432
{
376433
static const CScriptNum bnZero(0);
@@ -381,6 +438,9 @@ bool EvalScript(std::vector<std::vector<unsigned char> >& stack, const CScript&
381438
// static const valtype vchZero(0);
382439
static const valtype vchTrue(1, 1);
383440

441+
// sigversion cannot be TAPROOT here, as it admits no script execution.
442+
assert(sigversion == SigVersion::BASE || sigversion == SigVersion::WITNESS_V0 || sigversion == SigVersion::TAPSCRIPT);
443+
384444
CScript::const_iterator pc = script.begin();
385445
CScript::const_iterator pend = script.end();
386446
CScript::const_iterator pbegincodehash = script.begin();
@@ -389,15 +449,18 @@ bool EvalScript(std::vector<std::vector<unsigned char> >& stack, const CScript&
389449
ConditionStack vfExec;
390450
std::vector<valtype> altstack;
391451
set_error(serror, SCRIPT_ERR_UNKNOWN_ERROR);
392-
if (script.size() > MAX_SCRIPT_SIZE)
452+
if ((sigversion == SigVersion::BASE || sigversion == SigVersion::WITNESS_V0) && script.size() > MAX_SCRIPT_SIZE) {
393453
return set_error(serror, SCRIPT_ERR_SCRIPT_SIZE);
454+
}
394455
int nOpCount = 0;
395456
bool fRequireMinimal = (flags & SCRIPT_VERIFY_MINIMALDATA) != 0;
457+
uint32_t opcode_pos = 0;
458+
execdata.m_codeseparator_pos = 0xFFFFFFFFUL;
459+
execdata.m_codeseparator_pos_init = true;
396460

397461
try
398462
{
399-
while (pc < pend)
400-
{
463+
for (; pc < pend; ++opcode_pos) {
401464
bool fExec = vfExec.all_true();
402465

403466
//
@@ -408,9 +471,12 @@ bool EvalScript(std::vector<std::vector<unsigned char> >& stack, const CScript&
408471
if (vchPushValue.size() > MAX_SCRIPT_ELEMENT_SIZE)
409472
return set_error(serror, SCRIPT_ERR_PUSH_SIZE);
410473

411-
// Note how OP_RESERVED does not count towards the opcode limit.
412-
if (opcode > OP_16 && ++nOpCount > MAX_OPS_PER_SCRIPT)
413-
return set_error(serror, SCRIPT_ERR_OP_COUNT);
474+
if (sigversion == SigVersion::BASE || sigversion == SigVersion::WITNESS_V0) {
475+
// Note how OP_RESERVED does not count towards the opcode limit.
476+
if (opcode > OP_16 && ++nOpCount > MAX_OPS_PER_SCRIPT) {
477+
return set_error(serror, SCRIPT_ERR_OP_COUNT);
478+
}
479+
}
414480

415481
if (opcode == OP_CAT ||
416482
opcode == OP_SUBSTR ||
@@ -568,6 +634,15 @@ bool EvalScript(std::vector<std::vector<unsigned char> >& stack, const CScript&
568634
if (stack.size() < 1)
569635
return set_error(serror, SCRIPT_ERR_UNBALANCED_CONDITIONAL);
570636
valtype& vch = stacktop(-1);
637+
// Tapscript requires minimal IF/NOTIF inputs as a consensus rule.
638+
if (sigversion == SigVersion::TAPSCRIPT) {
639+
// The input argument to the OP_IF and OP_NOTIF opcodes must be either
640+
// exactly 0 (the empty vector) or exactly 1 (the one-byte vector with value 1).
641+
if (vch.size() > 1 || (vch.size() == 1 && vch[0] != 1)) {
642+
return set_error(serror, SCRIPT_ERR_TAPSCRIPT_MINIMALIF);
643+
}
644+
}
645+
// Under witness v0 rules it is only a policy rule, enabled through SCRIPT_VERIFY_MINIMALIF.
571646
if (sigversion == SigVersion::WITNESS_V0 && (flags & SCRIPT_VERIFY_MINIMALIF)) {
572647
if (vch.size() > 1)
573648
return set_error(serror, SCRIPT_ERR_MINIMALIF);
@@ -1001,6 +1076,7 @@ bool EvalScript(std::vector<std::vector<unsigned char> >& stack, const CScript&
10011076

10021077
// Hash starts after the code separator
10031078
pbegincodehash = pc;
1079+
execdata.m_codeseparator_pos = opcode_pos;
10041080
}
10051081
break;
10061082

@@ -1015,7 +1091,7 @@ bool EvalScript(std::vector<std::vector<unsigned char> >& stack, const CScript&
10151091
valtype& vchPubKey = stacktop(-1);
10161092

10171093
bool fSuccess = true;
1018-
if (!EvalChecksig(vchSig, vchPubKey, pbegincodehash, pend, flags, checker, sigversion, serror, fSuccess)) return false;
1094+
if (!EvalChecksig(vchSig, vchPubKey, pbegincodehash, pend, execdata, flags, checker, sigversion, serror, fSuccess)) return false;
10191095
popstack(stack);
10201096
popstack(stack);
10211097
stack.push_back(fSuccess ? vchTrue : vchFalse);
@@ -1029,9 +1105,32 @@ bool EvalScript(std::vector<std::vector<unsigned char> >& stack, const CScript&
10291105
}
10301106
break;
10311107

1108+
case OP_CHECKSIGADD:
1109+
{
1110+
// OP_CHECKSIGADD is only available in Tapscript
1111+
if (sigversion == SigVersion::BASE || sigversion == SigVersion::WITNESS_V0) return set_error(serror, SCRIPT_ERR_BAD_OPCODE);
1112+
1113+
// (sig num pubkey -- num)
1114+
if (stack.size() < 3) return set_error(serror, SCRIPT_ERR_INVALID_STACK_OPERATION);
1115+
1116+
const valtype& sig = stacktop(-3);
1117+
const CScriptNum num(stacktop(-2), fRequireMinimal);
1118+
const valtype& pubkey = stacktop(-1);
1119+
1120+
bool success = true;
1121+
if (!EvalChecksig(sig, pubkey, pbegincodehash, pend, execdata, flags, checker, sigversion, serror, success)) return false;
1122+
popstack(stack);
1123+
popstack(stack);
1124+
popstack(stack);
1125+
stack.push_back((num + (success ? 1 : 0)).getvch());
1126+
}
1127+
break;
1128+
10321129
case OP_CHECKMULTISIG:
10331130
case OP_CHECKMULTISIGVERIFY:
10341131
{
1132+
if (sigversion == SigVersion::TAPSCRIPT) return set_error(serror, SCRIPT_ERR_TAPSCRIPT_CHECKMULTISIG);
1133+
10351134
// ([sig ...] num_of_signatures [pubkey ...] num_of_pubkeys -- bool)
10361135

10371136
int i = 1;
@@ -1392,10 +1491,19 @@ static const CHashWriter HASHER_TAPTWEAK = TaggedHash("TapTweak");
13921491
template<typename T>
13931492
bool SignatureHashSchnorr(uint256& hash_out, const ScriptExecutionData& execdata, const T& tx_to, uint32_t in_pos, uint8_t hash_type, SigVersion sigversion, const PrecomputedTransactionData& cache)
13941493
{
1395-
uint8_t ext_flag;
1494+
uint8_t ext_flag, key_version;
13961495
switch (sigversion) {
13971496
case SigVersion::TAPROOT:
13981497
ext_flag = 0;
1498+
// key_version is not used and left uninitialized.
1499+
break;
1500+
case SigVersion::TAPSCRIPT:
1501+
ext_flag = 1;
1502+
// key_version must be 0 for now, representing the current version of
1503+
// 32-byte public keys in the tapscript signature opcode execution.
1504+
// An upgradable public key version (with a size not 32-byte) may
1505+
// request a different key_version with a new sigversion.
1506+
key_version = 0;
13991507
break;
14001508
default:
14011509
assert(false);
@@ -1452,6 +1560,15 @@ bool SignatureHashSchnorr(uint256& hash_out, const ScriptExecutionData& execdata
14521560
ss << sha_single_output.GetSHA256();
14531561
}
14541562

1563+
// Additional data for BIP 342 signatures
1564+
if (sigversion == SigVersion::TAPSCRIPT) {
1565+
assert(execdata.m_tapleaf_hash_init);
1566+
ss << execdata.m_tapleaf_hash;
1567+
ss << key_version;
1568+
assert(execdata.m_codeseparator_pos_init);
1569+
ss << execdata.m_codeseparator_pos;
1570+
}
1571+
14551572
hash_out = ss.GetSHA256();
14561573
return true;
14571574
}
@@ -1561,9 +1678,13 @@ bool GenericTransactionSignatureChecker<T>::CheckECDSASignature(const std::vecto
15611678
template <class T>
15621679
bool GenericTransactionSignatureChecker<T>::CheckSchnorrSignature(Span<const unsigned char> sig, Span<const unsigned char> pubkey_in, SigVersion sigversion, const ScriptExecutionData& execdata, ScriptError* serror) const
15631680
{
1564-
assert(sigversion == SigVersion::TAPROOT);
1681+
assert(sigversion == SigVersion::TAPROOT || sigversion == SigVersion::TAPSCRIPT);
15651682
// Schnorr signatures have 32-byte public keys. The caller is responsible for enforcing this.
15661683
assert(pubkey_in.size() == 32);
1684+
// Note that in Tapscript evaluation, empty signatures are treated specially (invalid signature that does not
1685+
// abort script execution). This is implemented in EvalChecksigTapscript, which won't invoke
1686+
// CheckSchnorrSignature in that case. In other contexts, they are invalid like every other signature with
1687+
// size different from 64 or 65.
15671688
if (sig.size() != 64 && sig.size() != 65) return set_error(serror, SCRIPT_ERR_SCHNORR_SIG_SIZE);
15681689

15691690
XOnlyPubKey pubkey{pubkey_in};
@@ -1674,6 +1795,28 @@ static bool ExecuteWitnessScript(const Span<const valtype>& stack_span, const CS
16741795
{
16751796
std::vector<valtype> stack{stack_span.begin(), stack_span.end()};
16761797

1798+
if (sigversion == SigVersion::TAPSCRIPT) {
1799+
// OP_SUCCESSx processing overrides everything, including stack element size limits
1800+
CScript::const_iterator pc = scriptPubKey.begin();
1801+
while (pc < scriptPubKey.end()) {
1802+
opcodetype opcode;
1803+
if (!scriptPubKey.GetOp(pc, opcode)) {
1804+
// Note how this condition would not be reached if an unknown OP_SUCCESSx was found
1805+
return set_error(serror, SCRIPT_ERR_BAD_OPCODE);
1806+
}
1807+
// New opcodes will be listed here. May use a different sigversion to modify existing opcodes.
1808+
if (IsOpSuccess(opcode)) {
1809+
if (flags & SCRIPT_VERIFY_DISCOURAGE_OP_SUCCESS) {
1810+
return set_error(serror, SCRIPT_ERR_DISCOURAGE_OP_SUCCESS);
1811+
}
1812+
return set_success(serror);
1813+
}
1814+
}
1815+
1816+
// Tapscript enforces initial stack size limits (altstack is empty here)
1817+
if (stack.size() > MAX_STACK_SIZE) return set_error(serror, SCRIPT_ERR_STACK_SIZE);
1818+
}
1819+
16771820
// Disallow stack item size > MAX_SCRIPT_ELEMENT_SIZE in witness stack
16781821
for (const valtype& elem : stack) {
16791822
if (elem.size() > MAX_SCRIPT_ELEMENT_SIZE) return set_error(serror, SCRIPT_ERR_PUSH_SIZE);
@@ -1688,12 +1831,12 @@ static bool ExecuteWitnessScript(const Span<const valtype>& stack_span, const CS
16881831
return true;
16891832
}
16901833

1691-
static bool VerifyTaprootCommitment(const std::vector<unsigned char>& control, const std::vector<unsigned char>& program, const CScript& script)
1834+
static bool VerifyTaprootCommitment(const std::vector<unsigned char>& control, const std::vector<unsigned char>& program, const CScript& script, uint256& tapleaf_hash)
16921835
{
16931836
const int path_len = (control.size() - TAPROOT_CONTROL_BASE_SIZE) / TAPROOT_CONTROL_NODE_SIZE;
16941837
const XOnlyPubKey p{uint256(std::vector<unsigned char>(control.begin() + 1, control.begin() + TAPROOT_CONTROL_BASE_SIZE))};
16951838
const XOnlyPubKey q{uint256(program)};
1696-
uint256 tapleaf_hash = (CHashWriter(HASHER_TAPLEAF) << uint8_t(control[0] & TAPROOT_LEAF_MASK) << script).GetSHA256();
1839+
tapleaf_hash = (CHashWriter(HASHER_TAPLEAF) << uint8_t(control[0] & TAPROOT_LEAF_MASK) << script).GetSHA256();
16971840
uint256 k = tapleaf_hash;
16981841
for (int i = 0; i < path_len; ++i) {
16991842
CHashWriter ss_branch{HASHER_TAPBRANCH};
@@ -1766,9 +1909,16 @@ static bool VerifyWitnessProgram(const CScriptWitness& witness, int witversion,
17661909
if (control.size() < TAPROOT_CONTROL_BASE_SIZE || control.size() > TAPROOT_CONTROL_MAX_SIZE || ((control.size() - TAPROOT_CONTROL_BASE_SIZE) % TAPROOT_CONTROL_NODE_SIZE) != 0) {
17671910
return set_error(serror, SCRIPT_ERR_TAPROOT_WRONG_CONTROL_SIZE);
17681911
}
1769-
if (!VerifyTaprootCommitment(control, program, exec_script)) {
1912+
if (!VerifyTaprootCommitment(control, program, exec_script, execdata.m_tapleaf_hash)) {
17701913
return set_error(serror, SCRIPT_ERR_WITNESS_PROGRAM_MISMATCH);
17711914
}
1915+
execdata.m_tapleaf_hash_init = true;
1916+
if ((control[0] & TAPROOT_LEAF_MASK) == TAPROOT_LEAF_TAPSCRIPT) {
1917+
// Tapscript (leaf version 0xc0)
1918+
execdata.m_validation_weight_left = ::GetSerializeSize(witness.stack, PROTOCOL_VERSION) + VALIDATION_WEIGHT_OFFSET;
1919+
execdata.m_validation_weight_left_init = true;
1920+
return ExecuteWitnessScript(stack, exec_script, flags, SigVersion::TAPSCRIPT, checker, execdata, serror);
1921+
}
17721922
if (flags & SCRIPT_VERIFY_DISCOURAGE_UPGRADABLE_TAPROOT_VERSION) {
17731923
return set_error(serror, SCRIPT_ERR_DISCOURAGE_UPGRADABLE_TAPROOT_VERSION);
17741924
}

‎src/script/interpreter.h‎

Lines changed: 28 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -86,6 +86,8 @@ enum
8686
// "Exactly one stack element must remain, and when interpreted as a boolean, it must be true".
8787
// (BIP62 rule 6)
8888
// Note: CLEANSTACK should never be used without P2SH or WITNESS.
89+
// Note: WITNESS_V0 and TAPSCRIPT script execution have behavior similar to CLEANSTACK as part of their
90+
// consensus rules. It is automatic there and does not need this flag.
8991
SCRIPT_VERIFY_CLEANSTACK = (1U << 8),
9092

9193
// Verify CHECKLOCKTIMEVERIFY
@@ -108,6 +110,8 @@ enum
108110

109111
// Segwit script only: Require the argument of OP_IF/NOTIF to be exactly 0x01 or empty vector
110112
//
113+
// Note: TAPSCRIPT script execution has behavior similar to MINIMALIF as part of its consensus
114+
// rules. It is automatic there and does not depend on this flag.
111115
SCRIPT_VERIFY_MINIMALIF = (1U << 13),
112116

113117
// Signature(s) must be empty vector if a CHECK(MULTI)SIG operation failed
@@ -122,13 +126,19 @@ enum
122126
//
123127
SCRIPT_VERIFY_CONST_SCRIPTCODE = (1U << 16),
124128

125-
// Taproot validation (BIP 341)
129+
// Taproot/Tapscript validation (BIPs 341 & 342)
126130
//
127131
SCRIPT_VERIFY_TAPROOT = (1U << 17),
128132

129133
// Making unknown Taproot leaf versions non-standard
130134
//
131135
SCRIPT_VERIFY_DISCOURAGE_UPGRADABLE_TAPROOT_VERSION = (1U << 18),
136+
137+
// Making unknown OP_SUCCESS non-standard
138+
SCRIPT_VERIFY_DISCOURAGE_OP_SUCCESS = (1U << 19),
139+
140+
// Making unknown public key versions (in BIP 342 scripts) non-standard
141+
SCRIPT_VERIFY_DISCOURAGE_UPGRADABLE_PUBKEYTYPE = (1U << 20),
132142
};
133143

134144
bool CheckSignatureEncoding(const std::vector<unsigned char> &vchSig, unsigned int flags, ScriptError* serror);
@@ -168,16 +178,32 @@ enum class SigVersion
168178
BASE = 0, //!< Bare scripts and BIP16 P2SH-wrapped redeemscripts
169179
WITNESS_V0 = 1, //!< Witness v0 (P2WPKH and P2WSH); see BIP 141
170180
TAPROOT = 2, //!< Witness v1 with 32-byte program, not BIP16 P2SH-wrapped, key path spending; see BIP 341
181+
TAPSCRIPT = 3, //!< Witness v1 with 32-byte program, not BIP16 P2SH-wrapped, script path spending, leaf version 0xc0; see BIP 342
171182
};
172183

173184
struct ScriptExecutionData
174185
{
186+
//! Whether m_tapleaf_hash is initialized.
187+
bool m_tapleaf_hash_init = false;
188+
//! The tapleaf hash.
189+
uint256 m_tapleaf_hash;
190+
191+
//! Whether m_codeseparator_pos is initialized.
192+
bool m_codeseparator_pos_init = false;
193+
//! Opcode position of the last executed OP_CODESEPARATOR (or 0xFFFFFFFF if none executed).
194+
uint32_t m_codeseparator_pos;
195+
175196
//! Whether m_annex_present and (when needed) m_annex_hash are initialized.
176197
bool m_annex_init = false;
177198
//! Whether an annex is present.
178199
bool m_annex_present;
179200
//! Hash of the annex data.
180201
uint256 m_annex_hash;
202+
203+
//! Whether m_validation_weight_left is initialized.
204+
bool m_validation_weight_left_init = false;
205+
//! How much validation weight is left (decremented for every successful non-empty signature check).
206+
int64_t m_validation_weight_left;
181207
};
182208

183209
/** Signature hash sizes */
@@ -186,6 +212,7 @@ static constexpr size_t WITNESS_V0_KEYHASH_SIZE = 20;
186212
static constexpr size_t WITNESS_V1_TAPROOT_SIZE = 32;
187213

188214
static constexpr uint8_t TAPROOT_LEAF_MASK = 0xfe;
215+
static constexpr uint8_t TAPROOT_LEAF_TAPSCRIPT = 0xc0;
189216
static constexpr size_t TAPROOT_CONTROL_BASE_SIZE = 33;
190217
static constexpr size_t TAPROOT_CONTROL_NODE_SIZE = 32;
191218
static constexpr size_t TAPROOT_CONTROL_MAX_NODE_COUNT = 128;

0 commit comments

Comments
 (0)