1

One of the many benefits of SegWit is that it solves the O(n^2) signature hashing problem. What exactly is the O(n^2) hashing problem and how segregating signatures to separate witness field solve it?

5

Moving signatures to a separate field does not actually solve it. However one of the things that segwit did was to redefine the message that is hashed and signed. This is specified in BIP 143.

Signature verification requires three things: the public key, the signature, and the message that was signed. In Bitcoin, the public key and the signature are provided by the person spending an output (or in some cases the public key is provided in the output itself). What is missing is the message. Instead of having a user provided message, the message is actually the spending transaction itself or some variation of it. How this message is constructed is known as the signature hashing algorithm.

For non-segwit signatures, the message is typically the entire spending transaction with all scriptSigs empty except for the input that the signature will belong to. That input will contain the scriptPubKey of the output being spent. The important thing to note here is that the message contains all of the prevouts that are specified. And every single signature signs a similar message, but still has all of the inputs in each one.

If you were to add another input, this not only adds another signature that must be done, but also it increases the size of the data that must be hashed for every single signature in the transaction. This means that if a transaction has n inputs each requiring 1 signature (thus n signatures required), for every signature, n inputs must be hashed. This is done n times so every input is hashed n*n = n^2 times. Thus it is quadratic.

However segwit defines a new signature hashing algorithm for segwit inputs. The message that is signed is not the spending transaction with modifications, rather it is a completely different structure which contains data pulled from the transaction.

From BIP 143, the data that is serialized and then hashed is:

     1. nVersion of the transaction (4-byte little endian)
     2. hashPrevouts (32-byte hash)
     3. hashSequence (32-byte hash)
     4. outpoint (32-byte hash + 4-byte little endian) 
     5. scriptCode of the input (serialized as scripts inside CTxOuts)
     6. value of the output spent by this input (8-byte little endian)
     7. nSequence of the input (4-byte little endian)
     8. hashOutputs (32-byte hash)
     9. nLocktime of the transaction (4-byte little endian)
    10. sighash type of the signature (4-byte little endian)

The important thing to see here is that this by itself does not increase in size when more inputs are added. Almost everything has a fixed size, with the only thing having variable size being the scriptCode.

Now you may notice that this does contain hashPrevouts and hashSequence which are the hash of the prevouts and the hash of all of the sequence numbers, respectively. The amount of data that is hashed for these hashes will grow as more inputs are added. If implemented naively, signing and verifying segwit inputs would still be quadratic.

But by specifying the hash of the prevouts and the hash of the sequence numbers separately instead of interspersed throughout the message as non-segwit does, these hashes can be precomputed once and then reused for every signing and verifying operation in a transaction. Thus this allows for an optimization which makes this linear.

At signing or verifying time, the signer or verifier can first compute hashPrevouts, hashSequence, and hashOutputs once. These values remain the same for all inputs. Then for every signature, they compute the sighash which does not end up re-hashing the majority of the data and does not typically change in size from input to input. Thus since the amount of data being hashed really only changes when the transaction gains an input, and it only changes by a relatively fixed amount, segwit sighashing is linear.

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.