3

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?

Improve this question
1

2 Answers 2

Reset to default
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.

Improve this answer
2
  • 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
    Commented Jun 8, 2017 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.
    – Pieter Wuille
    Commented Jun 9, 2017 at 1:23
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?'.

Improve this answer
2
  • 3
    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
    Commented Jun 8, 2017 at 15:15
  • 1
    Yes, exactly. I've updated my answer.
    – Murch ♦
    Commented Jun 8, 2017 at 15:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.