I read ScriptSig content during signature (quadratic hashing) discussing quadratic hash problem.
Quadratic hash problem is the issue that signing (or verifying) transaction time grows with the square of the number of inputs (O(n^2) where n is the number of inputs).
Why is that so? I reason the following:
- For each input you construct different template. O(n)
- This template must be double-SHA-hashed. - Double-SHA-hash duration is dependent linearly on the size of the template?
- Double hashed template (of fixed length) is then signed. - as the leght is fixed this step is of fixed duration
As step 2 is dependent linearly on the size of the template, thus it is linearly dependent on the number of inputs, giving final time dependency relation O(n^2)?
More precisely O(n^2+m) where m is the number of outputs (as this contributes in step 2)?