From 9f642244b9a5e5f89faf264833c85a0bbc16e380 Mon Sep 17 00:00:00 2001
From: Jeremy Rubin <j@rubin.io>
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<unsigned char>& 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:
+
+```
+<H> 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 <j@rubin.io>
Date: Wed, 12 Jan 2022 09:53:55 -0800
Subject: [BIP-119] Complete fragmented sentence

Co-authored-by: flack <flack@contentcontrol-berlin.de>
---
 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<unsigned char>& 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

