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)