<blockquote>
  <p>Double-SHA-hash duration is dependent linearly on the size of the template?</p>
</blockquote>

<p>Yes, of course. </p>

<p>So, increasing the count of inputs twice we also increase the size of each template ~twice and the work for signing/verifying whole transaction increased quadratic</p>

CC BY-SA 3.0
2017-11-28T09:57:25.667Z
2017-11-28T09:57:25.667Z
amaclin
<p>I read <a href="https://bitcoin.stackexchange.com/questions/54548/scriptsig-content-during-signature-quadratic-hashing">ScriptSig content during signature (quadratic hashing)</a> discussing quadratic hash problem.</p>

<p>Quadratic hash problem is the issue that signing (or verifying) transaction time grows with the square of the number of inputs (<em>O(n^2) where n is the number of inputs</em>).</p>

<p>Why is that so? I reason the following:</p>

<ol>
<li>For each input you construct different template. <strong>O(n)</strong></li>
<li>This template must be double-SHA-hashed. - <strong>Double-SHA-hash duration is dependent linearly on the size of the template?</strong> </li>
<li>Double hashed template (of fixed length) is then signed. - <strong>as the leght is fixed this step is of fixed duration</strong></li>
</ol>

<p>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)?</p>

<p>More precisely O(n^2+m) where m is the number of outputs (as this contributes in step 2)?</p>

<transactions><hash><quadratic-hashing>
What causes quadratic hash problem?
croraf
# What causes quadratic hash problem?

(Asked by: username_0 on 2017-11-28)

I read [ScriptSig content during signature (quadratic hashing)](https://bitcoin.stackexchange.com/questions/54548/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:

1. For each input you construct different template. **O(n)**
2. This template must be double-SHA-hashed. - **Double-SHA-hash duration is dependent linearly on the size of the template?**
3. 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)?

**Tags:** transactions, hash, quadratic-hashing


---

## 1 answers

### Answer by username_1 on 2017-11-28. Score: 1

> Double-SHA-hash duration is dependent linearly on the size of the template?

Yes, of course.

So, increasing the count of inputs twice we also increase the size of each template ~twice and the work for signing/verifying whole transaction increased quadratic


---

