Which kinds of transactions show quadratic signature-hashing scaling?

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?

• – Murch
Jun 8 '17 at 5:43

Quadratic means that something grows as a square function of something else. If you're just talking about a single 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.

• 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?" Jun 8 '17 at 15:24
• 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. Jun 9 '17 at 1:23

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 Russel explained the conundrum in his blog when he analyzed 'The Megatransaction: Why Does It Take 25 Seconds?'.

• 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? Jun 8 '17 at 15:15
• Yes, exactly. I've updated my answer.
– Murch
Jun 8 '17 at 15:23