什麼是 O(n^2) 簽名雜湊問題，SegWit 如何解決它？
SegWit 的眾多好處之一是它解決了 O(n^2) 簽名雜湊問題。O(n^2) 散列問題到底是什麼以及如何將簽名隔離到單獨的見證欄位來解決它？
將簽名移動到單獨的欄位實際上並不能解決它。然而，segwit 所做的其中一件事是重新定義經過散列和簽名的消息。這是在BIP 143中指定的。
簽名驗證需要三件事：公鑰、簽名和已簽名的消息。在比特幣中，公鑰和簽名由花費輸出的人提供（或者在某些情況下，公鑰在輸出本身中提供）。缺少的是消息。該消息實際上是支出交易本身或它的某種變體，而不是使用者提供的消息。此消息的構造方式稱為簽名雜湊算法。
對於非隔離見證簽名，消息通常是整個支出交易，除了簽名將屬於的輸入之外，所有 scriptSigs 都是空的。該輸入將包含正在使用的輸出的 scriptPubKey。這裡要注意的重要一點是該消息包含所有指定的 prevout。每個簽名都簽署了類似的消息，但每個簽名中仍然包含所有輸入。
如果您要添加另一個輸入，這不僅會添加另一個必須完成的簽名，而且還會增加交易中每個簽名必須散列的數據大小。這意味著，如果交易的
n輸入每個都需要 1 個簽名（因此需要 n 個簽名），那麼對於每個簽名，n必須對輸入進行雜湊處理。這是完成的n時間，因此每個輸入都是散列n*n = n^2時間。因此它是二次的。然而，隔離見證為隔離見證輸入定義了一種新的簽名雜湊算法。簽名的消息不是經過修改的支出交易，而是一個完全不同的結構，其中包含從交易中提取的數據。
從 BIP 143 開始，序列化然後散列的數據是：
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)這裡要看到的重要一點是，當添加更多輸入時，它本身並不會增加大小。幾乎所有東西都有固定的大小，唯一可變大小的是 scriptCode。
現在您可能會注意到，這確實包含
hashPrevouts和hashSequencewhich 分別是 prevouts 的散列和所有序列號的散列。隨著更多輸入的添加，為這些散列散列的數據量將增加。如果實施得天真，簽名和驗證隔離見證輸入仍然是二次的。但是，通過單獨指定 prevout 的雜湊和序列號的雜湊，而不是像非隔離見證那樣散佈在整個消息中，這些雜湊可以預先計算一次，然後在交易中的每個簽名和驗證操作中重複使用。因此，這允許進行線性優化。
在簽名或驗證時，簽名者或驗證者可以首先計算
hashPrevouts、hashSequence和hashOutputs一次。對於所有輸入，這些值保持不變。然後對於每個簽名，他們計算 sighash，它最終不會重新散列大部分數據，並且通常不會在輸入之間改變大小。因此，由於被散列的數據量實際上僅在事務獲得輸入時才發生變化，並且僅變化相對固定的量，因此隔離見證 sighashing 是線性的。