<p><strong>Note:</strong> As of 2020 this answer is obsolete, as BIP143 / SegWit has been in use for years which fixes this concern.</p>
<hr />
<p>You can fix it this way, and someone is in the process of doing so.</p>
<p>The problem with hashing the entire transaction is that in order to create a transaction hash, you must know the signature. However, in order to create the signature, you need to know the transaction hash. To make this work, you need to avoid hashing the scriptSig. This is what Bitcoin does, but the way it's implemented prevents you from taking the hash for one output and using it for another.</p>
<p><a href="https://github.com/bitcoin/bips/blob/master/bip-0143.mediawiki" rel="nofollow noreferrer">BIP143</a> (part of segregated witness) proposes a system where data is (mostly) hashed once.</p>
<blockquote>
<p>A new transaction digest algorithm is defined, but only applicable to
sigops in version 0 witness program:</p>
<p>Double SHA256 of the serialization of:</p>
<ol>
<li>nVersion of the transaction (4-byte little endian)</li>
<li>hashPrevouts (32-byte hash)</li>
<li>hashSequence (32-byte hash)</li>
<li>outpoint (32-byte hash + 4-byte little endian)</li>
<li>scriptCode of the input (serialized as scripts inside CTxOuts)</li>
<li>value of the output spent by this input (8-byte little endian)</li>
<li>nSequence of the input (4-byte little endian)</li>
<li>hashOutputs (32-byte hash)</li>
<li>nLocktime of the transaction (4-byte little endian)</li>
<li>sighash type of the signature (4-byte little endian)</li>
</ol>
</blockquote>
<p>This gets run for each input. Every part of this is fixed length, except for scriptCode, but there's no way to make one scriptCode be hashed by multiple inputs. There are three inputs based on variable-length information, hashPrevouts, hashSequence, and hashOutputs, but there's limited potential for mischief there. All methods of computing them either hash one input/output, or are shared by the entire transaction, or are all zeroes.</p>
<p>Validating very large BIP143 transactions will take linear time, and be dominated by signature verification. However, BIP143 transactions cannot be made right now, as segregated witness has not been accepted by the miners.</p>

CC BY-SA 3.0
2017-02-09T21:47:22.783Z
I understand that signatures can't be signed, I guess I don't know why the hash for each input Sig is different? If all sigs are removed prior to hashing, why isn't the whole blob hashed just once for the entire transaction?
pinhead
CC BY-SA 3.0
2017-02-09T22:28:02.137Z
Because each hash is hashing something slightly different. The references of BIP143 go into more detail about this, but you should especially look at https://en.bitcoin.it/wiki/OP_CHECKSIG TL;DR: the input you're signing for has a part of the scriptPubKey of the previous transaction in it. This is consensus-critical; changing it requires a hardfork or the creation of a new way of signing transactions.
Nick ODell
CC BY-SA 3.0
2017-02-09T22:31:57.973Z
But it's only critical to consensus for `OP_CHECKSIG` right? What if there was just a new op code that signed differently?
pinhead
CC BY-SA 3.0
2017-02-09T22:36:30.693Z
That's only for OP_CHECKSIG, correct. The new opcode is a data push of one byte of 0 to 16.
Nick ODell
CC BY-SA 3.0
2017-02-09T22:43:29.983Z
Right so why not add a `OP_CHECKSIG2` and new tx/address type as a soft fork that hashes the whole tx minus sigs one time and uses that hash for each input?
pinhead
CC BY-SA 3.0
2017-02-09T22:53:17.953Z
That would be a reasonable solution, and it would work well in most cases. However, 143 allows ANYONECANPAY and SINGLE, which wouldn't work if only hashing once.
Nick ODell
CC BY-SA 4.0
2017-02-09T20:35:55.917Z
2021-01-23T18:26:22.727Z
2021-01-23T18:26:22.727Z
Nick ODell
<p>I don't think you can softfork CHECKSIG like that. Script would look like this</p>

<p>sig pubkey DUP HASH keyhash EQUALVERIFY NOPX/CHECKSIG2</p>

<p>New client would verify this and end up with a valid tx. Old client would do nothing at NOPX and end up with an invalid tx.</p>

CC BY-SA 3.0
2017-02-11T10:58:00.523Z
2017-02-11T10:58:00.523Z
ManfredMacx
<p>Why can't "we" fix the quadratic hashing problem with <code>OP_CHECKSIG</code> with a soft fork?</p>

<p>Update <code>NO_OPx</code> to <code>OP_CHECKSIG2</code> with soft fork, where <code>OP_CHECKSIG2</code> doesn't quadratically hash (uses a single tx hash of all data for each input maybe?). Create a new transaction type for the new process like P2SH and after wide enough network adoption, soft-fork to invalidate any old <code>OP_CHECKSIG</code> transactions the way BIP 66 worked?</p>

<p>Or is there a fundamental problem with my assumption that "uses a single tx hash of all data for each input maybe" is possible at all?</p>

<transactions><scalability><checksig><quadratic-hashing>
Quadratic hashing problem: Why not just create new OP code "CHECKSIG2" to fix?
pinhead
# Quadratic hashing problem: Why not just create new OP code "CHECKSIG2" to fix?

(Asked by: username_0 on 2017-02-09)

Why can't "we" fix the quadratic hashing problem with `OP_CHECKSIG` with a soft fork?

Update `NO_OPx` to `OP_CHECKSIG2` with soft fork, where `OP_CHECKSIG2` doesn't quadratically hash (uses a single tx hash of all data for each input maybe?). Create a new transaction type for the new process like P2SH and after wide enough network adoption, soft-fork to invalidate any old `OP_CHECKSIG` transactions the way BIP 66 worked?

Or is there a fundamental problem with my assumption that "uses a single tx hash of all data for each input maybe" is possible at all?

**Tags:** transactions, scalability, checksig, quadratic-hashing


---

## 2 answers

### Answer by username_1 on 2017-02-09. Score: 3

**Note:** As of 2020 this answer is obsolete, as BIP143 / SegWit has been in use for years which fixes this concern.

---

You can fix it this way, and someone is in the process of doing so.

The problem with hashing the entire transaction is that in order to create a transaction hash, you must know the signature. However, in order to create the signature, you need to know the transaction hash. To make this work, you need to avoid hashing the scriptSig. This is what Bitcoin does, but the way it's implemented prevents you from taking the hash for one output and using it for another.

[BIP143](https://github.com/bitcoin/bips/blob/master/bip-0143.mediawiki) (part of segregated witness) proposes a system where data is (mostly) hashed once.

> A new transaction digest algorithm is defined, but only applicable to
> sigops in version 0 witness program:
>
> Double SHA256 of the serialization of:
>
> 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)

This gets run for each input. Every part of this is fixed length, except for scriptCode, but there's no way to make one scriptCode be hashed by multiple inputs. There are three inputs based on variable-length information, hashPrevouts, hashSequence, and hashOutputs, but there's limited potential for mischief there. All methods of computing them either hash one input/output, or are shared by the entire transaction, or are all zeroes.

Validating very large BIP143 transactions will take linear time, and be dominated by signature verification. However, BIP143 transactions cannot be made right now, as segregated witness has not been accepted by the miners.

> **Comments:**
> **username_0**: I understand that signatures can't be signed, I guess I don't know why the hash for each input Sig is different? If all sigs are removed prior to hashing, why isn't the whole blob hashed just once for the entire transaction?  
> **username_1**: Because each hash is hashing something slightly different. The references of BIP143 go into more detail about this, but you should especially look at https://en.bitcoin.it/wiki/OP_CHECKSIG TL;DR: the input you're signing for has a part of the scriptPubKey of the previous transaction in it. This is consensus-critical; changing it requires a hardfork or the creation of a new way of signing transactions.  
> **username_0**: But it's only critical to consensus for `OP_CHECKSIG` right? What if there was just a new op code that signed differently?  
> **username_1**: That's only for OP_CHECKSIG, correct. The new opcode is a data push of one byte of 0 to 16.  
> **username_0**: Right so why not add a `OP_CHECKSIG2` and new tx/address type as a soft fork that hashes the whole tx minus sigs one time and uses that hash for each input?  
> **username_1**: That would be a reasonable solution, and it would work well in most cases. However, 143 allows ANYONECANPAY and SINGLE, which wouldn't work if only hashing once.  

---

### Answer by username_2 on 2017-02-11. Score: 0

I don't think you can softfork CHECKSIG like that. Script would look like this

sig pubkey DUP HASH keyhash EQUALVERIFY NOPX/CHECKSIG2

New client would verify this and end up with a valid tx. Old client would do nothing at NOPX and end up with an invalid tx.


---

