<p>Quadratic means that something grows as a square function of something else. If you're just talking about a one-input transaction, there is nothing that changes.</p>
<p>The quadratic hashing issue is that the amount of data to hash to compute or verify signatures grows as a square of the number of non-segwit inputs.</p>

CC BY-SA 3.0
2017-06-08T15:24:02.363Z
So the nature of the input/output scripts doesn't matter. The O(n2) dependence is caused by the current hashing method, which affects every mainnet transaction today? In this case, why use the term "certain transactions" in the quote for the original question and not "all transactions?"
Rich Apodaca
CC BY-SA 3.0
2017-06-09T01:23:49.300Z
Right, every transaction is subject to the "sighashing time scales quadratically with number of inputs", but only for some transactions (=those with many inputs) that results in noticably slower validation.
Pieter Wuille
CC BY-SA 4.0
2017-06-08T05:45:04.910Z
2022-04-27T14:46:58.360Z
2022-04-27T14:46:58.360Z
Pieter Wuille
<p>The quadratic hashing issue appears in the verification of all pre-segwit transaction formats. It stems from the method of verifying the input scripts.</p>
<p>For each input the transaction has, all the other inputs are stripped from the transaction to check that remaining input against the output it spends as wells as the corresponding signature. As the effort of stripping the transaction is linearly dependent on the number inputs and the stripping is repeated for each input, we do n-times work that scales linearly with n: <code>O(n)*O(n) = O(n²)</code>, the cost grows quadratically with the number of inputs. This means that with twice the number of inputs, the computational effort for the verification quadruples.</p>
<p>Rusty Russell explained the conundrum in his blog when he analyzed <a href="http://rusty.ozlabs.org/?p=522" rel="nofollow noreferrer">'The Megatransaction: Why Does It Take 25 Seconds?'</a>.</p>

CC BY-SA 3.0
2017-06-08T15:15:49.940Z
Checking I understand. n is the number of inputs. There's a linear time dependence O(n) for hashing a single input. There's a second linear time dependence O(n) because the procedure is repeated for every input. The combination of time dependencies gives O(n2) scaling. In other words, doubling the number of inputs (for one transaction or millions) quadruples the signature hashing time. This applies to every non-segwit transaction and is independent on the content of the input/output scripts themselves. Right?
Rich Apodaca
CC BY-SA 3.0
2017-06-08T15:23:15.933Z
Yes, exactly. I've updated my answer.
Murch
CC BY-SA 4.0
2017-06-08T05:53:09.160Z
2022-04-27T14:48:21.743Z
2022-04-27T14:48:21.743Z
Murch
<p>It has been stated:</p>

<blockquote>
  <p>A major problem with simple approaches to increasing the Bitcoin blocksize is that for certain transactions, signature-hashing scales quadratically rather than linearly.</p>
</blockquote>

<p><a href="https://bitcoincore.org/en/2016/01/26/segwit-benefits/#linear-scaling-of-sighash-operations" rel="nofollow noreferrer">https://bitcoincore.org/en/2016/01/26/segwit-benefits/#linear-scaling-of-sighash-operations</a></p>

<p>What are some examples of transactions with this behavior, and what do they have in common?</p>

<p>Does a simple one-input-two-output Alice-pays-Bob transaction show quadratic signature-hashing scaling?</p>

CC BY-SA 3.0
2017-06-08T05:43:08.247Z
related: [Rusty Russel's blog: 'The Megatransaction: Why Does It Take 25 Seconds?'](http://rusty.ozlabs.org/?p=522)
Murch
<segregated-witness><transaction-verification><scalability><quadratic-hashing>
Which kinds of transactions show quadratic signature-hashing scaling?
Rich Apodaca
# Which kinds of transactions show quadratic signature-hashing scaling?

(Asked by: username_0 on 2017-06-08)

It has been stated:

> A major problem with simple approaches to increasing the Bitcoin blocksize is that for certain transactions, signature-hashing scales quadratically rather than linearly.

<https://bitcoincore.org/en/2016/01/26/segwit-benefits/#linear-scaling-of-sighash-operations>

What are some examples of transactions with this behavior, and what do they have in common?

Does a simple one-input-two-output Alice-pays-Bob transaction show quadratic signature-hashing scaling?

**Tags:** segregated-witness, transaction-verification, scalability, quadratic-hashing

> **Comments:**
> **username_1**: related: [Rusty Russel's blog: 'The Megatransaction: Why Does It Take 25 Seconds?'](http://rusty.ozlabs.org/?p=522)  

---

## 2 answers

### Answer by username_2 on 2017-06-08. Score: 5

Quadratic means that something grows as a square function of something else. If you're just talking about a one-input transaction, there is nothing that changes.

The quadratic hashing issue is that the amount of data to hash to compute or verify signatures grows as a square of the number of non-segwit inputs.

> **Comments:**
> **username_0**: So the nature of the input/output scripts doesn't matter. The O(n2) dependence is caused by the current hashing method, which affects every mainnet transaction today? In this case, why use the term "certain transactions" in the quote for the original question and not "all transactions?"  
> **username_2**: Right, every transaction is subject to the "sighashing time scales quadratically with number of inputs", but only for some transactions (=those with many inputs) that results in noticably slower validation.  

---

### Answer by username_1 on 2017-06-08. Score: 3

The quadratic hashing issue appears in the verification of all pre-segwit transaction formats. It stems from the method of verifying the input scripts.

For each input the transaction has, all the other inputs are stripped from the transaction to check that remaining input against the output it spends as wells as the corresponding signature. As the effort of stripping the transaction is linearly dependent on the number inputs and the stripping is repeated for each input, we do n-times work that scales linearly with n: `O(n)*O(n) = O(n²)`, the cost grows quadratically with the number of inputs. This means that with twice the number of inputs, the computational effort for the verification quadruples.

Rusty Russell explained the conundrum in his blog when he analyzed ['The Megatransaction: Why Does It Take 25 Seconds?'](http://rusty.ozlabs.org/?p=522).

> **Comments:**
> **username_0**: Checking I understand. n is the number of inputs. There's a linear time dependence O(n) for hashing a single input. There's a second linear time dependence O(n) because the procedure is repeated for every input. The combination of time dependencies gives O(n2) scaling. In other words, doubling the number of inputs (for one transaction or millions) quadruples the signature hashing time. This applies to every non-segwit transaction and is independent on the content of the input/output scripts themselves. Right?  
> **username_1**: Yes, exactly. I've updated my answer.  

---

