Hashing and Signing

In 1976, Whitfield Diffie and Martin Hellman published a six-page paper that upended the entire field of cryptography.^† For centuries, encryption had required both parties to share a secret key in advance—meet in person, exchange code books, use a trusted courier. Diffie and Hellman showed that this wasn't necessary: you could use mathematical trapdoor functions to create "public key" systems where anyone could encrypt a message, but only the holder of a private key could decrypt it. Their paper also introduced the concept of digital signatures—a way to prove authorship without revealing secrets. What they didn't know was that a young mathematician named Ralph Merkle had independently arrived at essentially the same insight a year earlier—his paper, submitted to the Communications of the ACM in 1975, sat in a reviewer's pile for three years because no one understood it.

And neither Diffie, Hellman, nor Merkle knew that the British signals intelligence agency GCHQ had gotten there first. In 1970, a cryptographer named James Ellis wrote an internal paper describing the concept of "non-secret encryption"—what we now call public-key cryptography. Three years later, his colleague Clifford Cocks devised a practical implementation based on the difficulty of factoring large numbers—the same mathematical foundation that RSA would independently discover in 1977. All of it remained classified until 1997. The most consequential idea in modern cryptography was invented three times, on two continents, across a decade—and for most of that time, none of the inventors knew about the others.

From Diffie–Hellman came RSA, then PGP, then the cypherpunks' dream of digital cash. From the cypherpunks—David Chaum, Adam Back, Wei Dai, Hal Finney—came the building blocks that Satoshi Nakamoto assembled into Bitcoin. Every Bitcoin transaction is authorized by a digital signature: a mathematical proof that the holder of a specific private key approved the transfer. But a signature must be over something—it signs a specific message, and any change to that message invalidates the signature. The question is: what message does a Bitcoin signature sign?

The answer is not "the transaction." It can't be, because the transaction contains the signature. Instead, Bitcoin uses a carefully constructed sighash—a digest computed from a modified version of the transaction where the signature itself has been surgically removed. This chapter traces that process byte by byte, using the same Block 170 transaction we parsed in Chapters 1 and 2.

3.1Transaction Digests: SHA-256d

Bitcoin uses double SHA-256 (SHA-256d) as its universal hash function. The txid computation from Chapter 1 is one instance; the sighash computation below is another; block headers, Merkle trees, and address derivation all use the same construction:

\[H(m) = \text{SHA-256}(\text{SHA-256}(m))\]

3.1.1Why Double Hashing?

As mentioned in Chapter 1, SHA-256 (like all Merkle–Damgård hash functions) is vulnerable to length-extension attacks: given \(H(m)\) and the length of \(m\), an attacker can compute \(H(m \| pad \| m')\) without knowing \(m\). Applying SHA-256 twice eliminates this:

\[\text{SHA-256}(\text{SHA-256}(m \| \text{pad} \| m')) \neq \text{SHA-256}(\text{SHA-256}(m))\]

The outer hash completely scrambles the intermediate value, breaking the extension chain. This is the same principle behind HMAC, and it costs only one extra hash computation—a negligible overhead.

3.2The Sighash Algorithm (Legacy)

When OP_CHECKSIG executes (Chapter 2, Section 2.5), it must compute the message that was signed. For pre-SegWit transactions, this follows the legacy sighash algorithm.

But first, let's see why we need an algorithm at all. The problem is a circular dependency: the signature lives inside the transaction, but it must sign a hash of the transaction. You can't hash the bytes until you know the signature, and you can't produce the signature until you've hashed the bytes:

The algorithm below performs this replacement step by step.

Step 1: Copy the Transaction

Start with a complete copy of the spending transaction—our Block 170 transaction, all 275 bytes.

Step 2: Clear All ScriptSigs

Set the scriptSig of every input to empty (zero-length). If the transaction had multiple inputs, each one's scriptSig would become a zero-length field with a varint of 00.

Step 3: Insert the Subscript

For the input being validated (input 0 in our case), replace the empty scriptSig with the subscript—the scriptPubKey of the UTXO being spent. For our transaction, this is the Block 9 coinbase output's P2PK script:

This is Satoshi's public key followed by OP_CHECKSIG—the locking script that protects the 50 BTC coinbase output.

Step 4: Append the SIGHASH Type

Append the SIGHASH flag as a 4-byte little-endian integer. For SIGHASH_ALL (0x01):

The Complete Sighash Preimage

The modified transaction—with the scriptSig replaced by the subscript and the SIGHASH type appended—is 274 bytes:

Compare this to the original transaction from Chapter 1. Two differences:

1. The 72-byte scriptSig (47304402...0901) has been replaced by the 67-byte scriptPubKey of the UTXO being spent (410411db...a3ac). The varint changed from 48 (72) to 43 (67).
2. Four bytes 01 00 00 00 (SIGHASH_ALL) have been appended after the locktime.

Step 5: Double SHA-256

Hash the 274-byte preimage with SHA-256d:

Note how completely different the two hashes are: the intermediate value starts with 4c98... and the final sighash starts with 7a05.... Not a single byte in common—this is SHA-256's avalanche effect in action.

This 32-byte sighash is the message that Satoshi's private key signed. The ECDSA signature in the scriptSig—the \((r, s)\) pair we parsed in Chapter 1—is a signature over exactly these 32 bytes.

3.3SIGHASH Flags

The last byte of every DER-encoded signature is the SIGHASH flag. Our Block 170 signature uses 0x01 (SIGHASH_ALL), but five other valid flags exist. Before we enumerate them, it helps to understand why there are six in the first place.

3.3.1The Two Questions Every Signature Answers

A Bitcoin transaction can have many inputs and many outputs. When you sign one of those inputs, your signature does not have to cover the entire transaction. It can be selective—and the SIGHASH flag is how you express that selectivity. Specifically, every signature answers two independent questions:

1. Which outputs does my signature lock down? In other words: where is the money going? Do I care about all the outputs, just one, or none at all?
2. Which inputs does my signature lock down? In other words: who is paying? Do I commit to the full list of inputs, or just my own?

Now let's walk through what each choice means and—crucially—when you would actually want it.

3.3.2The Output Dimension: ALL, NONE, SINGLE

SIGHASH_ALL (0x01) — "I lock down every output."

The default. Your signature covers every output in the transaction: every recipient address, every amount. If anyone changes even one output—redirects a payment, adjusts a value, adds a new recipient—your signature breaks.

This is what you want for an ordinary payment. You're saying: "I authorize spending my coins, and I specify exactly where every satoshi goes. No surprises." Over 99.9% of all Bitcoin signatures use this flag.

SIGHASH_NONE (0x02) — "I lock down zero outputs."

Your signature covers the inputs but commits to no outputs at all. In the sighash preimage, the output list is emptied entirely (output count set to zero).

Why would anyone do this? Because sometimes the person authorizing the spend is not the person choosing the destination. Imagine Alice and Bob run a small business together. Alice controls the company's UTXO, but Bob handles payments. Alice signs with SIGHASH_NONE: she authorizes spending the coins but leaves the outputs blank. Bob fills in the recipients and amounts, then broadcasts. Alice trusted Bob to choose wisely—her signature doesn't constrain him.

The danger is obvious: if anyone intercepts this partially-signed transaction before Bob fills it in and broadcasts, they can redirect the funds anywhere. This is a loaded gun with no safety.

SIGHASH_SINGLE (0x03) — "I lock down one output."

Your signature covers only the output at the same index as your input. If you're signing input 2, the signature covers output 2—and nothing else. Other outputs can be added, removed, or changed freely.

This is the "I care about my side of the deal" flag. Think of a multi-party transaction where several participants each contribute an input and expect a corresponding output. Alice signs input 0, committing only to output 0 (the payment to her counterparty). Bob signs input 1, committing only to output 1 (his payment). Neither participant's signature constrains the other's output. Each person locks down their own piece of the transaction and leaves the rest open.

The earliest confirmed SIGHASH_SINGLE transaction is e81298f2...0224 in Block 233,999 (May 1, 2013).^† It is a P2PKH transaction with one input (16,515,733 sats), one output (25,000 sats), and the remaining 16,490,733 sats (0.165 BTC) lost as fees—likely an accident by someone experimenting with non-standard sighash types. Across 800,000 blocks, only 2,385 inputs ever used bare SIGHASH_SINGLE, making it the rarest of all six standard types.

3.3.3The Input Dimension: ANYONECANPAY

Now we come to the second question: who is paying?

Notice something about the three base types above. ALL, NONE, and SINGLE differ in how they treat outputs, but they all treat inputs the same way: the signature commits to every input in the transaction. If someone adds a new input, removes an existing one, or changes the order—any signature using a bare base type breaks.

This means the set of participants is locked. Once you sign, the transaction's input list is frozen. No one else can contribute funds after the fact.

For a standard payment, that's exactly what you want. But what about a transaction that's meant to be collaborative—one where multiple parties independently contribute inputs to achieve a shared goal?

That is what ANYONECANPAY (0x80) enables. It is a single-bit modifier that flips the input dimension: instead of committing to all inputs, your signature commits to only your own input. Everyone else's inputs are excluded from the sighash preimage entirely. Other parties can freely add their own inputs (with their own signatures) without breaking yours.

The name says it all: anyone can pay. Your signature says "I'm putting my coins on the table," but it makes no demands about who else joins the transaction.

How it works mechanically

ANYONECANPAY is combined with a base type by ORing the high bit: 0x80 | 0x01 = 0x81, 0x80 | 0x02 = 0x82, 0x80 | 0x03 = 0x83. This gives three new flags, for a total of six:

Why it matters: the six flags as building blocks

Each of the six combinations enables a distinct class of transaction. The best way to understand them is through concrete scenarios:

Specimen: The first 0x81 on mainnet

Five months after Maxwell's BitcoinTalk post, someone tested the mechanism for real. Block 207,733 (November 13, 2012) contains the earliest confirmed SIGHASH_ALL|ANYONECANPAY transaction on Bitcoin mainnet:^†

01000000 02 f6044c0a d485f633 b41f97d0
d793eb28 37ae40f7 38ff6d5f 50fdfd10
528c1d76 01000000 6b 483045 02205853
c7f13957 85bfabb0 3c57e962 eb076ff2
4d8e4e57 3b04db13 b45ed3ed 6ee20221
009dc82a e43be9d4 b1fe2847 754e1d36
dad48ba8 01817d48 5dc529af c516c2dd
b481 2103 05584980 367b321f ad7f1c1f
4d5d723d 0ac80c1d 80c8ba12 34396548
364537a ffffffff 9c6af0df 6669bcde
d19e317e 25bebc8c 78e48df8 ae1fe02a
7f030818 e71ecd40 01000000 6c 493046
02210082 69c9d7ba 0a7e730d d16f4082
d29e3684 fb7463ba 064fd093 afc170ad
6e038802 2100bc6d 76373916 a3ff6ee4
1b2c7520 01fda3c9 e048bcff 0d81d05b
39ff0f42 17b281 21 03aae303 d8254215
45c5bc7c cd5ac87d d5add3bc c3a432ba
7aa2f266 1699f9f6 59 ffffffff 01 e093
04000000 0000 19 76a914 5c11f917 883b
927eef77 dc57707a eb853f6d 3894 88ac
00000000

Field | Value | Key Detail

Input 0 | 1D9vyX...W87 (200,000 sats) | Sighash: 81

Input 1 | 137Co4...wys (200,000 sats) | Sighash: 81

Output 0 | 19PphS...r83 (300,000 sats) | P2PKH

Fee | 100,000 sats (293 sat/byte) |

This is an assurance contract in the wild. Two parties each contributed 200,000 satoshis, pooled into a single 300,000-sat output (the remaining 100,000 going to fees—high by modern standards, but this was 2012 and the experimenters likely considered it the cost of testing). Each signer committed to the same output but only their own input. The coordinator—whoever assembled and broadcast the final transaction—could not have altered the destination without invalidating both signatures.

Look at the sighash bytes. Input 0's signature ends with ...b4 81, and Input 1's ends with ...b2 81. In both cases, the final byte before the pubkey push is 0x81—not 0x01. That single bit flip in the high nibble (0x80 | 0x01 = 0x81) is the entire difference between "I lock down every input" and "anyone can pay."

The partially signed state

Before this transaction was broadcast, it existed as an incomplete artifact—a partially signed transaction with room for more inputs. Here is what it looked like after Pledger A signed but before Pledger B joined:

01000000                              Version 1
01                                    1 input (only Pledger A so far)

  f6044c0a d485f633 b41f97d0 d793eb28   Prev txid (Pledger A's UTXO)
  37ae40f7 38ff6d5f 50fdfd10 528c1d76
  01000000                               Prev vout: 1
  6b                                     ScriptSig: 107 bytes
    48 3045...ddb4 81                      72-byte sig, sighash 0x81
    21 0305...537a                         33-byte compressed pubkey
  ffffffff                               Sequence

01                                    1 output
  e093040000000000                      300,000 sats (0.003 BTC)
  19 76a914 5c11f917...6d3894 88ac     P2PKH to 19PphS...r83

00000000                              Locktime

Now Pledger B signs their own input with 0x81 and hands it to the coordinator. The coordinator inserts it:

01000000
02                        <-- input count changes: 01 -> 02

  [Pledger A's input]       107-byte scriptSig, sighash 0x81
                            (UNCHANGED -- signature still valid)

  [Pledger B's input]       108-byte scriptSig, sighash 0x81
    9c6af0df 6669bcde...     Prev txid (Pledger B's UTXO)
    01000000                  Prev vout: 1
    6c                        ScriptSig: 108 bytes
      49 3046...b281            73-byte sig, sighash 0x81
      21 03aa...f659            33-byte compressed pubkey
    ffffffff                  Sequence

01 e093040000000000         Output (UNCHANGED)
   19 76a914...88ac
00000000                    Locktime

Now the math works: \(200,000 + 200,000 = 400,000\) input satoshis, covering the \(300,000\)-sat output with \(100,000\) left for fees. The coordinator broadcasts. Block 207,733 confirms it.

Had the coordinator tried to change the output—redirect the 300,000 sats to a different address, or alter the amount—both signatures would have broken, because both committed to all outputs via the ALL half of 0x81. The pledgers trusted no one with the destination; they only left the door open for more contributors.

How 0x81 changes the sighash preimage

To see exactly what ALL|ANYONECANPAY does at the byte level, compare it to the standard SIGHASH_ALL preimage from Section 3.2. Recall that the sighash preimage is a modified copy of the transaction, serialized and double-hashed to produce the 32-byte message that gets signed.

With SIGHASH_ALL (0x01), the preimage includes every input and every output:

[version]   [input_count=N]  [input_0] [input_1] ... [input_N-1]
            [output_count=M] [output_0] [output_1] ... [output_M-1]
            [locktime]       [01000000]  <-- sighash type (4 bytes, LE)

With ALL|ANYONECANPAY (0x81), the input list is replaced with only the signer's own input:

[version]   [input_count=1]  [my_input_only]
            [output_count=M] [output_0] [output_1] ... [output_M-1]
            [locktime]       [81000000]  <-- sighash type (4 bytes, LE)

1. The input count is forced to 01 regardless of how many inputs the final transaction contains.
2. The only input serialized is the one being signed—all other inputs are stripped out.

When the coordinator assembles the final transaction with five pledgers' inputs, each signature validates against a preimage that contains only that pledger's input plus the shared outputs. The signatures are composable—they can be combined in any order, and adding a sixth pledger doesn't invalidate the first five.

The final sighash type field is 81 00 00 00—the four-byte little-endian encoding of \(0x81 = 129\), which is 128 + 1 = ANYONECANPAY | ALL.

3.4ECDSA Signatures

The sighash is the 32-byte message. The private key produces an ECDSA signature over it.

Before tracing the algorithm, we need the curve parameters.

3.4.1Signing (Private Key Operation)

Given private key \(d\), message hash \(z\) (the sighash), and curve order \(n\):

1. Choose a random nonce \(k ∈ [1, n-1]\).
2. Compute the curve point \(R = kG\).
3. Set \(r = x_{R} \pmod{n}\) (the \(x\)-coordinate of \(R\)). If \(r = 0\), choose a new \(k\).
4. Compute \(s = k^{-1}(z + r \cdot d) \pmod{n}\). If \(s = 0\), choose a new \(k\).
5. The signature is \((r, s)\).

3.4.2Verification (Public Key Operation)

Given public key \(Q = dG\), message hash \(z\), and signature \((r, s)\):

1. Compute \(u_{1} = z \cdot s^{-1} \pmod{n}\).
2. Compute \(u_{2} = r \cdot s^{-1} \pmod{n}\).
3. Compute the curve point \(R' = u_{1} G + u_{2} Q\).
4. The signature is valid if and only if \(x_{R'} \equiv r \pmod{n}\).

This is the operation that OP_CHECKSIG performs in step 6 (Chapter 2).

The entire security of Bitcoin rests on the hardness of the elliptic curve discrete logarithm problem: given \(Q = dG\), computing \(d\) is infeasible with classical computers.

3.5DER Encoding Revisited

Chapter 1 traced the DER structure of our specimen's signature. Here we formalize the encoding rules that apply to every pre-Taproot Bitcoin signature:

Here is our Block 170 specimen's actual DER-encoded signature, byte by byte:

The encoding rules:

1. The outer structure is a DER SEQUENCE (tag 0x30).
2. Each component (\(r\) and \(s\)) is a DER INTEGER (tag 0x02).
3. Integers are big-endian and use minimal encoding: no leading zero bytes unless the high bit is set (which would make the integer negative in DER's signed representation).
4. If the high bit of \(r\) or \(s\) is set (\(\geq\) 0x80), a leading 0x00 byte is prepended, increasing the length by 1. In our specimen, neither \(r\) (0x4e) nor \(s\) (0x18) has its high bit set, so both are exactly 32 bytes.
5. The SIGHASH flag byte is appended outside the DER structure—it is not part of the ASN.1 encoding.

This variable-length encoding is why the DER signature structure ranges from 70 to 72 bytes: each of \(r\) and \(s\) is 32 or 33 bytes depending on the high bit, plus 6 bytes of DER overhead (tags and lengths). Add the 1-byte SIGHASH flag appended outside the DER structure, and the total data pushed into the scriptSig ranges from 71 to 73 bytes. Our Block 170 specimen has \(r = 32\) bytes and \(s = 32\) bytes (neither has a high bit set), so the DER structure is 70 bytes and the total push is 71 bytes.

3.6Transaction Malleability

Why does this matter? Because other transactions might reference this txid. If Alice sends coins to Bob in transaction A, and Bob immediately spends them in transaction B (which references A's txid as an input), a malleated version of A with a different txid would invalidate B. Bob's transaction points to a txid that no longer exists.

This was not a theoretical problem. In February 2014, the Mt. Gox exchange blamed transaction malleability for the loss of approximately 850,000 BTC (worth $450 million at the time).^† While the actual causes of Mt. Gox's collapse were more complex, malleability attacks were real and documented.

The fix came in two stages:

1. BIP 62/66/146^†: tightened DER encoding rules and required low-\(s\) signatures, eliminating the most common malleation vectors.
2. Segregated Witness (BIP 141^†): moved the signature data out of the transaction structure that the txid hashes, making txids completely immutable. This is Part III of this book.

3.7BIP 143: The SegWit Sighash

The legacy sighash algorithm has a critical performance flaw: it hashes the entire transaction once per input. For a transaction with \(n\) inputs, this means \(O(n^{2})\) hashing work—each of the \(n\) inputs requires hashing a modified version of the full transaction, including all \(n\) inputs.

For typical transactions (1–5 inputs), this is negligible. But adversarial transactions can exploit it: a transaction with 10,000 inputs requires 100 million hash operations to validate, creating a denial-of-service vector.

BIP 143^† (introduced with SegWit) replaces the legacy algorithm with a new sighash that uses precomputed components:

1. hashPrevouts: SHA-256d of all input outpoints (txid:vout), computed once.
2. hashSequence: SHA-256d of all input sequence numbers, computed once.
3. hashOutputs: SHA-256d of all outputs (value + scriptPubKey), computed once.

These three digests are computed once and reused for every input. Each input's sighash then combines the precomputed hashes with the input-specific data (outpoint, script, value, sequence). Total hashing work: \(O(n)\) instead of \(O(n^{2})\).

BIP 143 also fixes another legacy deficiency: the sighash preimage includes the value of the input being spent (in satoshis). The legacy algorithm does not—it only includes the scriptPubKey. This means hardware wallets verifying a legacy transaction must separately look up each input's value, which is impractical. With BIP 143, the value is committed to in the sighash, and the hardware wallet can verify it directly.

We'll see BIP 143 in action in Chapter 8 when we parse our first SegWit transaction.

Looking Ahead

With Chapters 1, 2, and 3, we have the complete toolkit for parsing Bitcoin transactions:

• Chapter 1: the raw byte structure (version, inputs, outputs, locktime).
• Chapter 2: the Script VM that validates them.
• Chapter 3: the cryptographic glue that authorizes them.

Part II applies these tools to Bitcoin's historical transaction types, starting with P2PK (the type we've been analyzing) and progressing through P2PKH, P2SH, and bare multisig. Each chapter will introduce a new specimen from the blockchain and parse it with the same byte-by-byte approach—but now you'll understand not just what the bytes mean, but why they're there and how the cryptographic machinery behind them works.

Exercises

Litmus

1. What is the key difference between the sighash preimage and the original transaction? Name both changes.
2. The SIGHASH flag 0x01 is called SIGHASH_ALL. What does "all" refer to?
3. True or false: the txid and the sighash are computed by hashing the same byte sequence.
4. In ECDSA signing, what catastrophic failure occurs if the same nonce \(k\) is used for two different messages?
5. Why is a DER-encoded signature sometimes 71 bytes and sometimes 72 bytes?

Hands-On

1. Take the sighash preimage shown in this chapter (274 bytes) and verify the sighash digest using any SHA-256 tool (Python's hashlib, OpenSSL, or an online calculator). Confirm you get 7a05c614...220bcb19.
2. Construct the sighash preimage for a hypothetical transaction with two inputs (both SIGHASH_ALL). Describe how the preimage differs when signing input 0 vs.input 1. (Focus on which scriptSig gets replaced and which gets set to empty.)
3. Look up DER encoding rules (ITU-T X.690). Given \(r\) = 0x00FF... (first byte \(\geq\) 0x80), write the complete DER INTEGER encoding. How many bytes does it use?
4. The SIGHASH_SINGLE bug returns a hash of 01 00 … 00 (32 bytes) when the input index exceeds the output count. Verify: if you know the "message" is always this constant, what does that imply about the security of the signature?

Proofs

1. Sighash circularity. Prove that the legacy sighash algorithm avoids circularity: the sighash digest does not depend on the signature, even though the signature is inside the transaction. Trace the dependency chain precisely.
2. Quadratic hashing. Show that the legacy sighash algorithm requires \(O(n \cdot m)\) bytes of hashing for a transaction with \(n\) inputs and total size \(m\). Explain why BIP 143 reduces this to \(O(m)\).
3. Low-\(s\) uniqueness. Prove that for any valid ECDSA signature \((r, s)\) on secp256k1, either \(s \leq n/2\) or \(n - s \leq n/2\), but not both (assuming \(s \neq 0\) and \(s \neq n/2\)). Why does requiring \(s \leq n/2\) eliminate the malleability vector?

Connections

1. Schnorr vs.ECDSA. Taproot (Chapter 12) replaces ECDSA with Schnorr signatures. Research the key differences: linearity (enabling key and signature aggregation), fixed 64-byte encoding (no DER), and the lack of a malleability vector. Why is linearity important for multisig?
2. Mt. Gox and malleability. Research the February 2014 Mt. Gox malleability incident. What specific form of malleability was exploited? Could SegWit (had it existed in 2014) have prevented the attack? What other factors contributed to Mt. Gox's collapse?

Bridge

1. From P2PK to P2PKH. We've spent three chapters on the simplest transaction type: P2PK. P2PKH adds a hash layer: the output stores a 20-byte hash instead of a 65-byte key, and the spender must provide both the signature and the public key. How does this change the sighash computation? (Hint: the subscript changes.)
2. The address question. P2PK has no addresses—the "address" is the raw public key. P2PKH introduced Base58Check addresses starting with "1". What information does a P2PKH address encode? How is the 20-byte hash derived from the public key? What is the role of the checksum? (Chapter 5 answers all of these.)

Solutions

Litmus Solutions

L1. Two changes: (1) the scriptSig of the input being signed is replaced with the scriptPubKey of the UTXO being spent (the "subscript"), and (2) the SIGHASH flag is appended as a 4-byte little-endian integer after the locktime.

L2. "All" refers to all inputs and all outputs. The signature commits to the complete transaction structure: every input's outpoint and sequence, and every output's value and scriptPubKey. Changing any of them invalidates the signature.

L3. False. The txid hashes the original complete transaction (including the scriptSig with the signature). The sighash hashes a modified version where the scriptSig is replaced with the subscript and the SIGHASH type is appended. They are different byte sequences and produce different hashes.

L4. The private key is exposed. If two signatures \((r, s_{1})\) and \((r, s_{2})\) share the same \(r\) (which implies the same nonce \(k\)), an attacker can compute \(d = (s_{1} z_{2} - s_{2} z_{1})/(s_{2} r - s_{1} r) \pmod{n}\) and recover the private key.

L5. Because of DER encoding's minimal-encoding rule for integers. Each component (\(r\) and \(s\)) is 32 bytes if its leading byte is \(<\) 0x80, or 33 bytes if the leading byte is \(\geq\) 0x80 (a zero byte is prepended to keep the integer positive). The DER overhead is fixed at 6 bytes (SEQUENCE tag + length, two INTEGER tags + lengths). The SIGHASH flag adds 1 byte outside the DER structure. The total:

Our Block 170 specimen has \(r = 32\) bytes and \(s = 32\) bytes, so the scriptSig pushes 71 bytes (70 DER + 1 SIGHASH).

Hands-On Solutions

H1. Using Python:

import hashlib
preimage = bytes.fromhex("0100000001c997a5e5...01000000")
h = hashlib.sha256(hashlib.sha256(preimage).digest()).digest()
print(h.hex())
# Expected: 7a05c6145f10101e9d6325494245adf1
#           297d80f8f38d4d576d57cdba220bcb19

(Use the full 274-byte preimage from the chapter.)

H2. For a two-input transaction with SIGHASH_ALL:

• Signing input 0: replace input 0's scriptSig with output 0's subscript (the scriptPubKey of the UTXO it spends). Set input 1's scriptSig to empty (varint 00). Append 01000000.
• Signing input 1: replace input 1's scriptSig with output 1's subscript. Set input 0's scriptSig to empty. Append 01000000.

Each input's sighash is computed independently. The preimage differs in which scriptSig is replaced and which is zeroed.

H3. If \(r\) = 00FF... (33 bytes with leading zero):

• Tag: 02 (INTEGER)
• Length: 21 (33 in decimal)
• Value: 00 FF ... (33 bytes, the leading 00 prevents the high bit of FF from making the integer negative)

Total: \(2 + 33 = 35\) bytes for this integer. Without the high-bit issue, it would be \(2 + 32 = 34\) bytes.

H4. If the sighash is always the constant 01 00 00 …\ 00, then every signature for this input signs the same "message." This means that any valid signature for this public key on this constant is valid. An attacker who obtains any signature from this key on this message—from any transaction that triggered the bug—can reuse that signature. Worse, the constant is known to everyone, so an attacker can generate a valid signature if they have the private key for any input that uses SIGHASH_SINGLE with an out-of-range index. This effectively makes such inputs "anyone can spend" if any such signature has ever been published.

Proofs Solutions

P1. The sighash computation takes the transaction bytes and performs two modifications: (a) replaces the scriptSig with the subscript (scriptPubKey), and (b) appends the SIGHASH type. The scriptSig contains the DER-encoded signature—but this signature is removed in step (a) and replaced with the subscript. Therefore, the sighash preimage does not contain the signature. The hash of the preimage (the sighash) is then compared against the signature via ECDSA verification.

Dependency chain: sighash \(←\) preimage \(←\) (transaction \(-\) scriptSig \(+\) subscript \(+\) SIGHASH type). The signature is in the scriptSig, which is removed. No circularity.

P2. For the legacy algorithm, each of \(n\) inputs requires:

• A copy of the full transaction (\( m\) bytes, where \(m\) is the total size).
• Modifications to the scriptSig fields (\(O(m)\) work to serialize).
• A SHA-256d hash of the modified transaction (\(O(m)\) hashing).

Total: \(n\) inputs \(\times \) \(O(m)\) per input \(= O(n \cdot m)\). Since \(m \geq O(n)\) (each input contributes at least 41 bytes), this is \(O(n^{2})\) in the worst case.

BIP 143 precomputes hashPrevouts, hashSequence, and hashOutputs—each is a single pass over the transaction data, totaling \(O(m)\). Each input's sighash then combines fixed-size components (the three precomputed hashes plus input-specific data), requiring \(O(1)\) hashing per input. Total: \(O(m) + n \cdot O(1) = O(m)\).

P3. The secp256k1 curve has order \(n\) (a 256-bit prime). For any \(s ∈ [1, n-1]\), define \(s' = n - s\). Then \(s + s' = n \equiv 0 \pmod{n}\), so \(s' ∈ [1, n-1]\).

If \(s \leq n/2\), then \(s' = n - s \geq n/2\). If \(s > n/2\), then \(s' < n/2\). Since \(n\) is odd (it's prime and \(> 2\)), \(n/2\) is not an integer, so \(s \neq n/2\), and exactly one of \(s, s'\) is \(< n/2\).

Both \((r, s)\) and \((r, s')\) are valid signatures because ECDSA verification checks \(x_{R}' = r\) where \(R'\) depends on \(s^{-1}\), and \((n-s)^{-1} = -(s^{-1})\), which merely negates the \(y\)-coordinate of \(R'\) without changing the \(x\)-coordinate.

Requiring \(s \leq n/2\) (the "low-\(s\)" rule) means there is exactly one valid encoding for every signature. A third party cannot flip \(s\) to \(n - s\) to change the scriptSig bytes (and thus the txid) while keeping the signature valid.

Connections Solutions

C1. Key differences between Schnorr (BIP 340^†) and ECDSA:

• Linearity: Schnorr signatures are linear: \(sig(k_{1} + k_{2}, m) = sig(k_{1}, m) + sig(k_{2}, m)\). This enables key aggregation (MuSig2): \(n\) signers can combine their public keys into a single key and produce a single signature that verifies against it. For \(n\)-of-\(n\) multisig, this reduces on-chain cost from \(n\) signatures to 1.
• Fixed encoding: Schnorr signatures are always exactly 64 bytes (\(R_{x} \| s\), both 32 bytes). No DER, no variable length, no malleability from encoding flexibility.
• No \(s\) malleability: the verification equation pins \(s\) uniquely (there is no \(n - s\) variant).
• Batch verification: multiple Schnorr signatures can be verified together faster than individually, improving block validation speed.

Linearity matters for multisig because it makes \(n\)-of-\(n\) multisig indistinguishable from a single-key spend on-chain—better privacy and lower fees.

C2. The Mt. Gox incident primarily involved \(s\)-value malleation: attackers took valid withdrawal transactions, flipped \(s\) to \(n - s\) (both valid), re-broadcast the malleated version, and when it confirmed first, the txid changed. Mt. Gox's system tracked withdrawals by txid, so it believed the original transaction had failed and re-issued the withdrawal. This allowed attackers to receive double payouts.

SegWit would have prevented this entirely: the signature moves to the witness, which is excluded from the txid hash. Changing the witness changes the wtxid but not the txid, so Mt. Gox's tracking system would not have been fooled.

However, Mt. Gox's problems went far beyond malleability: poor accounting practices, alleged internal theft by CEO Mark Karpelès (later convicted of data manipulation in Japan), and a years-long undetected hot wallet drain that predated the malleability attacks. Malleability was the visible symptom, not the root cause.

Bridge Solutions

B1. In P2PKH, the scriptPubKey is OP_DUP OP_HASH160 OP_PUSHBYTES_20 <20-byte hash> OP_EQUALVERIFY OP_CHECKSIG (25 bytes). This becomes the subscript in the sighash preimage—instead of the 67-byte P2PK scriptPubKey, the sighash uses the 25-byte P2PKH scriptPubKey. Everything else about the sighash algorithm remains identical. The preimage is shorter because the subscript is shorter.

B2. A P2PKH address encodes three things:

• A version byte (0x00 for mainnet P2PKH).
• The 20-byte hash: RIPEMD-160(SHA-256(compressed_pubkey)). This is OP_HASH160 applied to the public key.
• A 4-byte checksum: the first 4 bytes of SHA-256d(version \(\|\) hash). This detects typos—if you mistype one character of an address, the checksum almost certainly fails.

The concatenation (version \(+\) hash \(+\) checksum \(=\) 25 bytes) is then encoded in Base58—a character set that excludes visually ambiguous characters (0/O/I/l)—producing the familiar "1…" addresses:

1A1zP1eP5QGefi2DMPTfTL5SLmv7DivfNa

Chapter 5 traces this derivation byte by byte.