The Mt. Gox collapse and the malleability excuse (2014)

In February 2014 Mt. Gox, then handling most bitcoin trading, halted withdrawals and blamed transaction malleability: an attacker could alter a withdrawal’s signature encoding in flight, changing its txid; the exchange, which tracked withdrawals by txid, would not find it on chain, and paid again. Weeks later it filed for bankruptcy, about 850,000 bitcoins short.

Decker and Wattenhofer scanned the network for malleated transactions and found that malleability attacks could account for at most 386 bitcoins before the announcement, a tiny fraction of the loss. The coins had been disappearing for years. An exchange losing to malleability loses exactly the withdrawals it re-sends,

\[\text{loss} = \sum_{w \,:\, \mathrm{txid}(w) \notin \mathrm{chain}} a_w ,\]

and tracking withdrawals by an id that excludes the signature, as segregated witness’s txid later did, makes it zero.

import random

import matplotlib.pyplot as plt

import blockchainkit as bk

The exchange signs 200 withdrawals; an attacker malleates some in flight

A different signature over the same payment stands in for Bitcoin’s re-encoded signature: same payment, valid, different txid.

EXCHANGE_KEY = 7  # A fixed teaching key: never use such a key for real money.
hot_wallet = bk.crypto.public_key(EXCHANGE_KEY)
rng = random.Random(2014)
withdrawals = [
    bk.structures.Transaction(
        hot_wallet, bk.structures.address(bk.crypto.public_key(100 + i)), rng.randint(1, 50), i
    ).signed(EXCHANGE_KEY, signing_nonce=10_000 + i)
    for i in range(200)
]
malleated = set(rng.sample(range(200), 12))
confirmed = [
    tx.signed(EXCHANGE_KEY, signing_nonce=90_000 + i) if i in malleated else tx
    for i, tx in enumerate(withdrawals)
]
assert all(tx.is_valid() for tx in confirmed)

by_txid = bk.fraud.reissue_missing(withdrawals, confirmed, by="txid")
by_payment = bk.fraud.reissue_missing(withdrawals, confirmed, by="unsigned_id")
lost = sum(tx.amount for tx in by_txid)
print(f"tracking by txid: {len(by_txid)} withdrawals paid twice, {lost} coins lost")
print("tracking by unsigned id:", len(by_payment), "paid twice")
assert len(by_txid) == len(malleated) and by_payment == ()

tracking by txid: 12 withdrawals paid twice, 257 coins lost
tracking by unsigned id: 0 paid twice

What malleability could explain

fig, ax = plt.subplots(figsize=(7, 4))
ax.bar(
    ["missing at Mt. Gox", "malleability attacks\n(Decker and Wattenhofer)"],
    [850_000, 386],
    color=["#dc2626", "#2563eb"],
)
ax.set_yscale("log")
ax.set_ylabel("bitcoins")
ax.set_title("The excuse covers about 0.05% of the loss")
fig.tight_layout()

plt.show()

Exercise

Suppose the exchange waits for a customer to complain before re-sending, and a fraction \(c\) of customers whose withdrawal was malleated complain falsely. Write the expected loss for \(n\) withdrawals of mean size \(a\), a fraction \(m\) of them malleated.