From 9f642244b9a5e5f89faf264833c85a0bbc16e380 Mon Sep 17 00:00:00 2001 From: Jeremy Rubin Date: Mon, 10 Jan 2022 20:23:07 -0800 Subject: [BIP-119] Add notes and warnings about DoS during validation of CTV. --- bip-0119.mediawiki | 40 +++++++++++++++++++++++++++++++++++++++- 1 file changed, 39 insertions(+), 1 deletion(-) (limited to 'bip-0119.mediawiki') diff --git a/bip-0119.mediawiki b/bip-0119.mediawiki index e887caf..9649065 100644 --- a/bip-0119.mediawiki +++ b/bip-0119.mediawiki @@ -170,14 +170,17 @@ specification for the semantics of OP_CHECKTEMPLATEVERIFY. Where bool CheckDefaultCheckTemplateVerifyHash(const std::vector& hash) { + // note: for anti-DoS, a real implementation *must* cache parts of this computation + // to avoid quadratic hashing DoS, including return GetDefaultCheckTemplateVerifyHash(current_tx, current_input_index) == uint256(hash); } The hash is computed as follows: - + // 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(), @@ -185,6 +188,7 @@ The hash is computed as follows: 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) @@ -198,6 +202,7 @@ The hash is computed as follows: << 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) @@ -474,6 +479,38 @@ unintentional introduction of the 'half spend' problem. Templates, as restricted as they are, bear some risks. +====Denial of Service and Validation Costs==== + +CTV is designed to be able to be validated very cheaply without introducing DoS, either by checking a +precomputed hash or computing a hash of fixed length arguments (some of which may be cached from more +expensive computations). + +In particular, CTV requires that clients cache the computation of a hash over all the scriptSigs, sequences, +and outputs. Before CTV, the hash of the scriptSigs was not required. CTV also requires that the presence of +any non-empty scriptSig be hashed, but this can be handled as a part of the scriptSigs hash. + +As such, evaluating a CTV hash during consensus is always O(1) computation when the caches are available. +These caches usually must be available due to similar issues in CHECKSIG behavior. Computing the caches +is O(T) (the size of the transaction). + +An example of a script that could experience an DoS issue without caching is: + +``` + 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) +times as well (although cheaper than hashing, still a DoS). As such, CTV caches hashes and computations +over all variable length fields in a transaction. + +For CTV, the Denial-of-Service exposure and validation costs are relatively clear. Implementors must be careful +to correctly code CTV to make use of existing caches and cache the (new for CTV) computations over scriptSigs. +Other more flexible covenant proposals may have a more difficult time solving DoS issues as more complex computations may +be less cacheable and expose issues around quadratic hashing, it is a tradeoff CTV makes in favor of cheap and secure +validation at the expense of flexibility. For example, if CTV allowed the hashing only select outputs by a bitmask, +caching of all combinations of outputs would not be possible and would cause a quadratic hashing DoS vulnerability. + ====Permanently Unspendable Outputs==== The preimage argument passed to CHECKTEMPLATEVERIFY may be unknown or otherwise unsatisfiable. @@ -565,6 +602,7 @@ Given the simplicity of this approach to implement and analyze, and the benefits applications, CHECKTEMPLATEVERIFY's template based approach is proposed in lieu of more complete covenants system. + ====Future Upgrades==== This section describes updates to OP_CHECKTEMPLATEVERIFY that are possible in -- cgit v1.2.3 From 526e9797a782cc81ae41cb548ad0ecc7004147f8 Mon Sep 17 00:00:00 2001 From: Jeremy Rubin Date: Wed, 12 Jan 2022 09:53:55 -0800 Subject: [BIP-119] Complete fragmented sentence Co-authored-by: flack --- bip-0119.mediawiki | 4 +++- 1 file changed, 3 insertions(+), 1 deletion(-) (limited to 'bip-0119.mediawiki') diff --git a/bip-0119.mediawiki b/bip-0119.mediawiki index 9649065..1068e24 100644 --- a/bip-0119.mediawiki +++ b/bip-0119.mediawiki @@ -171,7 +171,9 @@ Where bool CheckDefaultCheckTemplateVerifyHash(const std::vector& hash) { // note: for anti-DoS, a real implementation *must* cache parts of this computation - // to avoid quadratic hashing DoS, including + // 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); } -- cgit v1.2.3