I’m participating in Chaincode Labs’ Bitcoin Protocol Development seminar and this week we are taking a deep dive into SegWit. One of the things SegWit fixed was something called the quadratic sighash problem.

In a nutshell, this was an issue where signature validation was taking O(n²) time to complete. Not good if you care about making Bitcoin’s barrier to entry as low as possible. Something like the quadratic sighash problem can prevent people with low compute resources (such as mobile or raspberry pi nodes) from participating in the network. If the problem really gets out of hand, it could prevent anyone without specialized hardware from running a node. Less people running nodes = more centralization.

There was also a legitimate attack vector where miners could create blocks that take so long to validate, no one could keep up with the chain. With no one checking the work, miners are free to do as they please.

Resources

Before I go further I want to mention three fantastic resources where of my understanding on this comes from. This post is just a repackaging of a very specific part of these resources, but with diagrams.

1. fjahar’s How SegWit solved the quadratic sighash problem
2. Andrew Chow’s Stack Overflow answer
3. Rusty Russell’s investigation into The Megatransaction: Why Does It Take 25 Seconds?

Let’s talk about signature verification

To verify any signature, you need three things

• signature
• public key
• message that was signed

The signature and public key are provided, but the message must be reconstructed.

Signature hashing algorithm = how the message is created

The signature hashing algorithm before SegWit

Before SegWit, here’s how we’d construct the message:

For each input,

1. Take the transaction and remove all other input scripts. Don’t remove the other inputs entirely, just the scripts! We still need to keep other data on the inputs like the previous transaction ID and the output index.
2. For the input we care about, replace the input script with the script from the previous transaction output
3. Perform a double-SHA-256 hash on all of it

Those steps produce the message that can be used for signature verification. The key to understanding this problem is actually by focusing on what happens in step 1.

So how is this quadratic/O(n²)?

For each input, you massage the transaction a little bit, and hash it twice. That doesn’t seem very quadratic. It seems linear, O(n) for n inputs.

The second n, the one that makes it O(n²) comes from the increased size of the message each time an input is added.

An example is probably the best way to illustrate this.

Let’s start with a transaction that has two inputs

We can start constructing the messages for each input. For step 1, we remove the input scripts for the inputs we don’t care about.

That’s probably what you’d expect it to look like. Not so bad. For this transaction with 2 inputs, there are a total of 4 things that will need to be hashed to finish building the messages:

1. Message for input 1: input 1 (with script)
2. Message for input 1: input 2
3. Message for input 2: input 1
4. Message for input 2: input 2 (with script)

4 is conveniently the same as 2², but let’s get another data point to show this relationship is indeed quadratic.

Now let’s look at an example with three inputs

Like before, we’ll start constructing the message for each input. Here’s what step 1 would look like for each input:

So we have three inputs, three messages… but wait! Each of those messages is larger! There are now a total of 9 things that will need to be hashed to finish building the messages:

1. Message for input 1: input 1 (with script)
2. Message for input 1: input 2
3. Message for input 1: input 3
4. Message for input 2: input 1
5. Message for input 2: input 2 (with script)
6. Message for input 2: input 3
7. Message for input 3: input 1
8. Message for input 3: input 2
9. Message for input 3: input 3 (with script)

As you can see, these messages, and the actions needed to construct them, get bigger and bigger the more inputs there are. Not only are you creating more messages, but the size of each message grows!

SegWit fixes this

By defining a new signature hashing algorithm (via BIP-143 which was deployed with SegWit), and moving the witness (signature) data out to a separate part of the transaction, SegWit fixed the quadratic sighash problem. The signature hashing algorithm now includes a reusable “midstate”. This eliminated step 1 in the old signature hashing algorithm and reduced the time complexity to O(n).

In a way, it’s poetic that SegWit was activated by means of a UASF. Had the quadratic sighash problem gone unchecked, we may have found ourselves in a world where few normal Bitcoin users could run nodes. And in that world, a UASF is not even an option.

For additional background and information on how SegWit brings the signature hashing algorithm down to O(n) time, please see the resources linked at the beginning of this post.