How Bitcoin works, block by block

Mt. Gox went dark last night. The site is a blank page, trading is stopped, and a document that’s supposed to be an internal “crisis strategy” draft is circulating which says 744,408 bitcoins are missing. Nobody outside the company knows if that document is real. A handful of the other big exchanges put out a joint statement saying Gox’s problems are Gox’s and not Bitcoin’s, and this morning there’s a short note from Mark Karpelès on the front page saying they’re working on a solution. Karpelès stepped down from the Bitcoin Foundation board over the weekend.

The story so far, as best I can piece it together: on February 7th Gox stopped all bitcoin withdrawals, then on the 10th put out a statement blaming “transaction malleability”, a quirk in how Bitcoin identifies transactions. The core developers replied, fairly sharply, that malleability has been known since 2011 and the problem is how Gox’s own software handled it. A day later someone started exploiting it against other exchanges too, and Bitstamp and BTC-e paused withdrawals for a few days while they checked their code.

I’ve had a dozen people at work and outside it ask me what malleability actually is, and I realized I couldn’t explain it without first explaining the whole thing from the bottom. So this is that. It’s long, and if you already know how a transaction is signed you can skip to the malleability section.

Coins don’t exist, outputs do

The thing that confused me most when I first read Satoshi’s paper is that there’s no such thing as a coin, or even an account balance. What exists is a big shared list of transactions, and each transaction does two things: it consumes some outputs of earlier transactions (its inputs), and it creates new outputs, each one an amount plus a little script that says who can spend it.

If Alice wants to pay Bob 1 BTC, her wallet finds an earlier output that paid her, say 1.5 BTC, and builds a transaction that spends it:

• input: “output #0 of transaction 4a5e…”, plus Alice’s signature and public key
• output 1: 1.0 BTC, spendable by whoever can sign for Bob’s address
• output 2: 0.4999 BTC back to Alice (the change)

The missing 0.0001 BTC is the fee, which goes to whoever mines the block. Outputs are spent whole, so you always get change back, like paying for a coffee with a twenty. “Your balance” is just the sum of all unspent outputs your keys can sign for, which your wallet adds up for you.

The input refers to the earlier transaction by its transaction ID, the txid, which is the SHA-256 hash of the serialized transaction, hashed twice (Bitcoin does SHA-256 of SHA-256 almost everywhere). Hold on to that, because it’s the whole malleability story.

Signatures

Alice proves the output is hers by signing the new transaction with her private key, using ECDSA on the secp256k1 curve. The signature and her public key go into the input, in a field called the scriptSig. Anyone can check that the public key hashes to the address the old output was paid to, and that the signature is valid for that key. I went through the general idea of public key signatures in the post on public key crypto back in September; Bitcoin uses elliptic curves rather than RSA, but the shape is the same: only the private key can make it, anyone can check it.

There’s a chicken-and-egg problem here, though. The signature lives inside the transaction, so the signature can’t be a signature over the whole transaction, including itself. What Bitcoin does is sign a copy of the transaction with the input scripts blanked out (well, replaced with something else, but not the signature). So the signature covers the inputs being spent, the amounts and the destinations, everything that matters. It doesn’t cover the scriptSig itself.

Blocks and mining

Now, nothing stops Alice from signing two different transactions that spend the same output, one to Bob and one back to herself. Each looks valid by itself. The network needs a way to agree which one happened first, without a bank in the middle to decide, and that’s what the block chain is for.

Transactions get broadcast to everyone, and miners collect them into blocks. A block has an 80-byte header, and the important fields in it are the hash of the previous block’s header, a Merkle root (a single hash that summarizes every transaction in the block), a timestamp and a 32-bit number called the nonce. Because each header includes the hash of the one before it, the blocks form a chain, and changing anything in an old block changes its hash, which breaks the link from every block after it.

To add a block, a miner has to find a header whose double SHA-256 hash, read as a number, is below a target. There’s no shortcut for this. A good hash function’s output looks random, so the only way to find one is to try nonces (and when you run out of nonces, change a field in the first transaction and start again) until you get lucky.

You can get a feel for it in a few lines of Python. Here I’m hashing a string with a counter on the end and looking for hashes that start with some number of zero hex digits:

import hashlib
s = 'alice pays bob 1 BTC'
i = 0
while not hashlib.sha256(('%s %d' % (s, i)).encode()).hexdigest().startswith('0000'):
    i += 1

Each hex digit is 4 bits, so a hash starting with one zero turns up about once in 16 tries, two zeros once in 256, four zeros once in 65,536. On my laptop I got one zero at i = 67, two at 802, three at 1,338 and four at 18,615. The four-zero hash was 00000be94df3…, which has five zeros by luck, after only 18,616 tries, well under the 65,536 you’d expect on average. That’s the variance miners live with: sometimes a block comes in a minute, sometimes it takes forty.

The real network is the same idea with an absurd number of zeros. Every 2,016 blocks (about two weeks) every node recalculates the target so that blocks keep arriving roughly every ten minutes, however much hardware is pointed at it. Right now that’s a lot of hardware, almost all of it custom ASICs. The miner who finds a block gets the fees in it plus a fixed reward, which started at 50 BTC, halved to 25 at the end of 2012 and halves every 210,000 blocks after that, which is where the 21 million cap comes from.*

Nodes always follow the chain with the most total work behind it. So if Alice tries to double-spend, both her transactions can be broadcast, but only one ends up in the chain everyone builds on, and to undo it later she’d need to redo the work for that block and every block since, faster than the rest of the network combined. That’s why merchants wait for “confirmations”: each block on top makes rewriting history much more expensive. Six is the usual number for anything large, about an hour.

Malleability

Back to the txid. It’s the hash of the whole serialized transaction, scriptSig included. But the signature doesn’t cover the scriptSig. So there’s a gap: somebody other than Alice can change the scriptSig in ways that keep the signature valid, and every change gives the transaction a different txid.

How do you change a signature without the private key? There are a few ways. The simplest is a property of ECDSA: a signature is a pair of numbers (r, s), and if (r, s) is valid then so is (r, n − s), where n is the order of the curve. The math doesn’t care. There are also several ways to encode the same signature in DER format with extra padding, and you can add harmless extra data-pushing opcodes to the scriptSig. None of these change who gets paid or how much.

So a relaying node, or anyone watching the network, can take Alice’s transaction, flip s, and broadcast the twin. Both are valid, both spend the same output, so only one can get into a block. If the twin wins, Bob still gets his bitcoin, exactly as intended. The only difference is that the transaction that confirmed has a txid Alice’s wallet has never heard of.

For a person that’s a non-event. For software that tracks payments by txid, it’s a trap. Imagine an exchange whose withdrawal system sends a payment, records txid 8c1f…, and then waits to see 8c1f… confirmed. It never shows up, because 3be0… confirmed instead. The system decides the withdrawal failed. Maybe it retries automatically, maybe the customer emails support saying “I never got my coins”, support looks it up, sees an unconfirmed transaction, and re-sends. Either way, the customer gets paid twice and the exchange’s books say they were paid zero times.

The fix on the exchange side is to not trust the txid as the identity of a payment. Check whether the outputs you were trying to spend got spent, and to where. That’s essentially what the developers said in their reply to Gox, and it’s what the other exchanges were scrambling to check when they paused withdrawals. The reference client has been tightening which signature encodings it will relay for a while, and I expect there’ll be a push to make one canonical form mandatory, but that only closes the encoding tricks. The underlying lesson for anyone writing software against Bitcoin is older than Bitcoin: an identifier that someone else can change isn’t an identifier you should key your accounting on.

So is that what happened to Gox?

I don’t know, and I don’t think anyone outside does yet. Malleability is real, and it’s plausible that Gox’s homegrown wallet code keyed everything off txids. And if any of Gox’s withdrawals sat unconfirmed for a while, for whatever reason, a twin had plenty of time to win the race.

But the leaked document says the losses went “unnoticed for several years”, and 744,408 BTC is something like 6% of all the bitcoins that have ever been mined. Losing that much through one class of bug, without anyone reconciling the wallet against the database once in all that time, is hard for me to believe. Every SaaS business I’ve worked on that handles money runs a daily reconciliation job, and the very first thing it would show is “the wallet has less in it than we think it does”. Either their accounting was astonishingly bad, or malleability is the part of the story that’s easy to explain to the press. Possibly both. We’ll find out when (if) there’s an audit.

What I’m fairly confident about is that this is a Gox failure and not a Bitcoin failure, in the sense that the protocol did exactly what it says it does. That’s not much comfort if your coins were on Gox. And if this ends up being the thing that gets ordinary people to stop keeping their coins on exchanges, that’d be one good thing to come out of it.

* 50 × 210,000 + 25 × 210,000 + 12.5 × 210,000 + … is 210,000 × 100 = 21,000,000, just under it in practice because of rounding to whole satoshis. It’s a geometric series, the kind of thing you do in the first month of a math degree and then never again.