2

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:

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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