SegWit signing algorithm and its improvement

Question

I was reading about Segregated Witness upgrade from the book Mastering Bitcoin by Andreas and there were some questions I have not figured out. I am appreciated to get some of your help!

A) There was a passage of the book talking about SegWit helps reduce the complexity of the signing algorithm.

Segregated Witness upgrades the signature functions (CHECKSIG, CHECKMULTISIG, etc.) to reduce the algorithm’s computational complexity. Before segwit, the algorithm used to produce a signature required a number of hash operations that was proportional to the size of the transaction. Data-hashing computations increased in O(n^2) with respect to the number of signature operations, introducing a substantial computational burden on all nodes verifying the signature. With segwit, the algorithm is changed to reduce the complexity to O(n).

What is the original algorithm here whose complexity is O(n^2) (is it ECDSA or something else)? And also what is the new SegWit signing algorithm, and how it got the complexity of O(n)?

B) There was also a passage talking about SegWit improvement.

Segregated Witness signatures incorporate the value (amount) referenced by each input in the hash that is signed. Previously, an offline signing device, such as a hardware wallet, would have to verify the amount of each input before signing a transaction. This was usually accomplished by streaming a large amount of data about the previous transactions referenced as inputs. Since the amount is now part of the commitment hash that is signed, an offline device does not need the previous transactions. If the amounts do not match (are misrepresented by a compromised online system), the signature will be invalid

What does it mean by saying Segregated Witness signatures incorporate the value (amount) referenced by each input in the hash that is signed. and Since the amount is now part of the commitment hash that is signed, an offline device does not need the previous transactions.? Does it mean that in Legacy block, the variable transfer value is not included in the hash, and now SegWit includes it?
And I cant understand how this make offline device not to need previous transactions' info (although I do understand that every offline devices need previous utxo to sign a transaction)

Answer 1

To be clear, this is talking about the way the message that is signed is computed. It is unrelated to transaction or block hashes and the signature algorithm itself, just how Bitcoin determines what data is actually covered by the signature and how that is serialized. This data is hashed in order to be used in the signature algorithm. This is referred to as the sighash algorithm. This sighash is generated by the signer and verifiers, so both signers and verifiers need to be able to generate the exact same sighash, otherwise signatures will be invalid.

Prior to segwit, the sighash algorithm would take the entire spending transaction, remove all of the scriptSigs from every input, and then fill in the input that the signature will go in with either the scriptPubKey or the redeemScript (for P2SH) and sign that. This ends up being O(n^2) because as the number of inputs grows, the amount of data hashed by for each input also grows. So the total amount of data hashes grows quadratically. The amount of data being hashed can have a large effect on how quickly transactions are validated.

For example, a transaction with 2 inputs will require 2 sighashes to be computed, in which 2 inputs of data will need to be hashed in each sighash. The total amount of data hashed is 4 inputs of data. If a transaction has 4 inputs, there will be 3 sighashes computed, with 3 inputs of data in each sighash, for a total of 9 inputs hashed.

Segwit solves this problem by defining a new sighash algorithm used when spending segwit inputs only. It instead precomputes the hash of the inputs that is then used in the sighashes for each input. As this is only done once for the entire transaction, the amount of data hashed only grows linearly - each additional input is a bit more data to be hashed in the precomputed hash, and one additional sighash to be computed.

As Segwit defines a new sighash algorithm for segwit inputs only, this algorithm can also include new information that was not previously covered by the sighash. So it also includes the amount of the input being spent, not just the scriptPubKey. This allows offline signers to be sure that some kinds of attacks where they are lied to about the value of an input.

Offline signers need to know the value of an input in order to run checks on the amounts and be sure that the transaction does not do something unexpected with the amounts. If the offline signer were just told the amount by the online wallet, it cannot be sure that the amount is actually correct. So for non-segwit inputs, they ask for the entire previous transaction. This way they can check the amount in the output itself and make sure that the transaction id matches.

With Segwit, the amount is directly included in the sighash itself. This means that if the offline signer were given the wrong amount, its sighash would contain the wrong amount. When a verifier checks the transaction, they would compute a different sighash containing the correct amount, and this would result in a failed signature, and thus a failed transaction. Because offline signers know that a wrong amount will just result in an invalid transaction, they don't need the entire previous transaction in order to trust that the amount they are given is correct.

Except there are a few other attacks that still require the full previous transaction. Unfortunately these were not theorized when segwit was being implemented. So offline signers should still ask for full previous transactions when signing segwit inputs. https://bitcoin.stackexchange.com/a/113785/48884 has a more detailed answer on the attacks that including the amounts mitigates, and the attacks that are still possible.