From fa09f7f85711226b114b835d176bcb85895040a4 Mon Sep 17 00:00:00 2001 From: Jeremy Rubin Date: Thu, 28 Apr 2022 09:43:30 -0700 Subject: [BIP-119] Reimplement CTV in higher level pythonic pseduocode and clarify DoS Caching requirements. --- bip-0119.mediawiki | 130 ++++++++++++++++++++++++++++++++++++++++++++--------- 1 file changed, 108 insertions(+), 22 deletions(-) (limited to 'bip-0119.mediawiki') diff --git a/bip-0119.mediawiki b/bip-0119.mediawiki index 07ce53a..f4e65a8 100644 --- a/bip-0119.mediawiki +++ b/bip-0119.mediawiki @@ -161,8 +161,83 @@ forming a "Payment Pool". ==Detailed Specification== -The below code is the main logic for verifying CHECKTEMPLATEVERIFY, and is the canonical -specification for the semantics of OP_CHECKTEMPLATEVERIFY. +The below code is the main logic for verifying CHECKTEMPLATEVERIFY, described +in pythonic pseduocode. The canonical specification for the semantics of +OP_CHECKTEMPLATEVERIFY can be seen in the reference implementations. + +The execution of the opcode is as follows: + def execute_bip_119(self): + # Before soft-fork activation / failed activation + if not self.flags.script_verify_default_check_template_verify_hash: + # Potentially set for node-local policy to discourage premature use + if self.flags.script_verify_discourage_upgradable_nops: + return self.errors_with(errors.script_err_discourage_upgradable_nops) + return self.return_as_nop() + # CTV always requires at least one stack argument + if len(self.stack) < 1: + return self.errors_with(errors.script_err_invalid_stack_operation) + # CTV only verifies the hash against a 32 byte argument + if len(self.stack[-1]) == 32: + # Ensure the precomputed data required for anti-DoS is available, + # or cache it on first use + if self.context.precomputed_ctv_data == None: + self.context.precomputed_ctv_data = self.context.tx.get_default_check_template_precomputed_data() + if stack[-1] != self.context.tx.get_default_check_template_hash(self.context.nIn, self.context.precomputed_ctv_data) + return self.errors_with(errors.script_err_template_mismatch) + return self.return_as_nop() + # future upgrade can add semantics for this opcode with different length args + # so discourage use when applicable + if self.flags.script_verify_discourage_upgradable_nops: + return self.errors_with(errors.script_err_discourage_upgradable_nops) + else: + return self.return_as_nop() + +The computation of this hash can be implemented as specified below (where self +is the transaction type). Care must be taken that in any validation context, +the precomputed data must be initialized to prevent Denial-of-Service attacks. +Any implementation *must* cache these parts of the hash computation to avoid +quadratic hashing DoS. All variable length computations must be precomputed +including hashes of the scriptsigs, sequences, and outputs. See the section +"Denial of Service and Validation Costs" below. This is not a performance +optimization. + + def get_default_check_template_precomputed_data(self): + result = {} + # If there are no scriptSigs we do not need to precompute a hash + if any(inp.scriptSig for inp in self.vin): + result["scriptSigs"] = sha256(b"".join(ser_string(inp.scriptSig) for inp in self.vin)) + # The same value is also pre-computed for and defined in BIP-341 and can be shared + result["sequences"] = sha256(b"".join(struct.pack("& hash) { - // note: for anti-DoS, a real implementation *must* cache parts of this computation - // to avoid quadratic hashing DoS all variable length computations must be precomputed - // including hashes of the scriptsigs, sequences, and outputs. See the section - // "Denial of Service and Validation Costs" below. return GetDefaultCheckTemplateVerifyHash(current_tx, current_input_index) == uint256(hash); } @@ -255,20 +326,37 @@ The hash is computed as follows, where the outputs_hash and sequences_hash are c return h.GetSHA256(); } -In python, this can be written as (but note this implementation is DoS-able). - def get_default_check_template_hash(self, nIn): - r = b"" - r += struct.pack(" CTV CTV CTV... CTV -``` + CTV CTV CTV... CTV Such a script would cause the intepreter to compute hashes (supposing N CTV's) over O(N*T) data. If the scriptSigs non-nullity is not cached, then the O(T) transaction could be scanned over O(N) -- cgit v1.2.3 From cad2b3ee775876b3d59268cb66e9e1aa3eae4222 Mon Sep 17 00:00:00 2001 From: Jeremy Rubin Date: Thu, 28 Apr 2022 09:45:13 -0700 Subject: [BIP-119] Remove C++ Spec from BIP-119 entirely. --- bip-0119.mediawiki | 125 +---------------------------------------------------- 1 file changed, 2 insertions(+), 123 deletions(-) (limited to 'bip-0119.mediawiki') diff --git a/bip-0119.mediawiki b/bip-0119.mediawiki index f4e65a8..e0e3b05 100644 --- a/bip-0119.mediawiki +++ b/bip-0119.mediawiki @@ -163,7 +163,8 @@ forming a "Payment Pool". The below code is the main logic for verifying CHECKTEMPLATEVERIFY, described in pythonic pseduocode. The canonical specification for the semantics of -OP_CHECKTEMPLATEVERIFY can be seen in the reference implementations. +OP_CHECKTEMPLATEVERIFY as implemented in C++ in the context of Bitcoin Core can +be seen in the reference implementation. The execution of the opcode is as follows: def execute_bip_119(self): @@ -236,128 +237,6 @@ optimization. return sha256(r) - -The C++ is below: - - case OP_CHECKTEMPLATEVERIFY: - { - // if flags not enabled; treat as a NOP4 - if (!(flags & SCRIPT_VERIFY_DEFAULT_CHECK_TEMPLATE_VERIFY_HASH)) { - if (flags & SCRIPT_VERIFY_DISCOURAGE_UPGRADABLE_NOPS) - return set_error(serror, SCRIPT_ERR_DISCOURAGE_UPGRADABLE_NOPS); - break; - } - - if (stack.size() < 1) - return set_error(serror, SCRIPT_ERR_INVALID_STACK_OPERATION); - - // If the argument was not 32 bytes, treat as OP_NOP4: - switch (stack.back().size()) { - case 32: - if (!checker.CheckDefaultCheckTemplateVerifyHash(stack.back())) { - return set_error(serror, SCRIPT_ERR_TEMPLATE_MISMATCH); - } - break; - default: - // future upgrade can add semantics for this opcode with different length args - // so discourage use when applicable - if (flags & SCRIPT_VERIFY_DISCOURAGE_UPGRADABLE_NOPS) { - return set_error(serror, SCRIPT_ERR_DISCOURAGE_UPGRADABLE_NOPS); - } - } - } - break; - -Where - - bool CheckDefaultCheckTemplateVerifyHash(const std::vector& hash) { - return GetDefaultCheckTemplateVerifyHash(current_tx, current_input_index) == uint256(hash); - } - -The hash is computed as follows, where the outputs_hash and sequences_hash are computed as defined in BIP-341. - - /** Compute the (single) SHA256 of the concatenation of all scriptSigs in a tx. */ - template - uint256 GetScriptSigsSHA256(const T& txTo) - { - CHashWriter ss(SER_GETHASH, 0); - for (const auto& in : txTo.vin) { - ss << in.scriptSig; - } - return ss.GetSHA256(); - } - // not DoS safe, for reference/testing! - uint256 GetDefaultCheckTemplateVerifyHash(const CTransaction& tx, uint32_t input_index) { - return GetDefaultCheckTemplateVerifyHash(tx, GetOutputsSHA256(tx), GetSequenceSHA256(tx), input_index); - } - // not DoS safe for reference/testing! - uint256 GetDefaultCheckTemplateVerifyHash(const CTransaction& tx, const uint256& outputs_hash, const uint256& sequences_hash, - const uint32_t input_index) { - bool skip_scriptSigs = std::find_if(tx.vin.begin(), tx.vin.end(), - [](const CTxIn& c) { return c.scriptSig != CScript(); }) == tx.vin.end(); - return skip_scriptSigs ? GetDefaultCheckTemplateVerifyHashEmptyScript(tx, outputs_hash, sequences_hash, input_index) : - GetDefaultCheckTemplateVerifyHashWithScript(tx, outputs_hash, sequences_hash, GetScriptSigsSHA256(tx), input_index); - } - // DoS safe, fixed length hash! - uint256 GetDefaultCheckTemplateVerifyHashWithScript(const CTransaction& tx, const uint256& outputs_hash, const uint256& sequences_hash, - const uint256& scriptSig_hash, const uint32_t input_index) { - auto h = CHashWriter(SER_GETHASH, 0) - << tx.nVersion - << tx.nLockTime - << scriptSig_hash - << uint32_t(tx.vin.size()) - << sequences_hash - << uint32_t(tx.vout.size()) - << outputs_hash - << input_index; - return h.GetSHA256(); - } - // DoS safe, fixed length hash! - uint256 GetDefaultCheckTemplateVerifyHashEmptyScript(const CTransaction& tx, const uint256& outputs_hash, const uint256& sequences_hash, - const uint32_t input_index) { - auto h = CHashWriter(SER_GETHASH, 0) - << tx.nVersion - << tx.nLockTime - << uint32_t(tx.vin.size()) - << sequences_hash - << uint32_t(tx.vout.size()) - << outputs_hash - << input_index; - return h.GetSHA256(); - } - - - - case OP_CHECKTEMPLATEVERIFY: - { - // if flags not enabled; treat as a NOP4 - if (!(flags & SCRIPT_VERIFY_DEFAULT_CHECK_TEMPLATE_VERIFY_HASH)) { - if (flags & SCRIPT_VERIFY_DISCOURAGE_UPGRADABLE_NOPS) - return set_error(serror, SCRIPT_ERR_DISCOURAGE_UPGRADABLE_NOPS); - break; - } - - if (stack.size() < 1) - return set_error(serror, SCRIPT_ERR_INVALID_STACK_OPERATION); - - // If the argument was not 32 bytes, treat as OP_NOP4: - switch (stack.back().size()) { - case 32: - if (!checker.CheckDefaultCheckTemplateVerifyHash(stack.back())) { - return set_error(serror, SCRIPT_ERR_TEMPLATE_MISMATCH); - } - break; - default: - // future upgrade can add semantics for this opcode with different length args - // so discourage use when applicable - if (flags & SCRIPT_VERIFY_DISCOURAGE_UPGRADABLE_NOPS) { - return set_error(serror, SCRIPT_ERR_DISCOURAGE_UPGRADABLE_NOPS); - } - } - } - - - A PayToBareDefaultCheckTemplateVerifyHash output matches the following template: bool CScript::IsPayToBareDefaultCheckTemplateVerifyHash() const -- cgit v1.2.3 From 78fc9f2ceb1c4df79ca4089001529ef7cecbbcf9 Mon Sep 17 00:00:00 2001 From: Jeremy Rubin Date: Thu, 28 Apr 2022 09:47:43 -0700 Subject: [BIP-119]: Make IsPayToBareDefaultCheckTemplateVerifyHash Pythonic --- bip-0119.mediawiki | 11 ++++------- 1 file changed, 4 insertions(+), 7 deletions(-) (limited to 'bip-0119.mediawiki') diff --git a/bip-0119.mediawiki b/bip-0119.mediawiki index e0e3b05..ba29d05 100644 --- a/bip-0119.mediawiki +++ b/bip-0119.mediawiki @@ -239,13 +239,10 @@ optimization. A PayToBareDefaultCheckTemplateVerifyHash output matches the following template: - bool CScript::IsPayToBareDefaultCheckTemplateVerifyHash() const - { - // Extra-fast test for pay-to-basic-standard-template CScripts: - return (this->size() == 34 && - (*this)[0] == 0x20 && - (*this)[33] == OP_CHECKTEMPLATEVERIFY); - } + # Extra-fast test for pay-to-basic-standard-template CScripts: + def is_pay_to_bare_default_check_template_verify_hash(self): + return len(self) == 34 and self[0] == 0x20 and self[-1] == OP_CHECKTEMPLATEVERIFY + ==Deployment== -- cgit v1.2.3