What it costs to rewrite history

A block's hash is taken over its position, its timestamp, its entry, the previous block's hash and its nonce. The first four are what the block is for and cannot be altered without altering the record. The nonce is different. It says nothing, carries no meaning, and exists so that the hash can be moved without the record being touched.

That is why the nonce looked like a flaw when it was introduced. It is the handle the whole mechanism turns on. Set a rule about what an acceptable hash must look like, and the nonce becomes the only thing anyone can turn while looking for one.

• Nonce. A number in every block that can be set to anything without changing what the block says.
• Difficulty. How many leading zero characters a block's hash is required to have before the block is accepted.
• Mining. Trying nonce values until the block's hash meets that requirement.
• Attempt. One nonce tried and one hash computed. The unit every cost figure here is counted in.
• Expected attempts. 16 to the power of the difficulty, because each hexadecimal character takes one of 16 values and the leading ones must all land on zero.
• Mean. The average over many independent blocks. The only honest way to state a mining cost.
• Spread. How far individual runs sit from that mean. At difficulty 4 the measured runs went from 149 attempts to 339,789.
• Reforge. Redoing a block and every block after it, now at a price per block. Practitioner session 5.

A digest is written in hexadecimal, so each character is one of sixteen. A hash function with no gradient scatters its output evenly across every possible digest, which means the first character lands on zero about one time in sixteen. Requiring two leading zeros asks for two independent one in sixteen events at once, and so on upwards.

That gives the expected attempt counts directly: 16, 256, 4,096 and 65,536 for difficulties 1 to 4. It is worth noticing what this expectation is not. It is not a limit, not a guarantee, and not a schedule. It is the average of a process whose individual outcomes are wild.

Session 2 left the attacker needing to redo blocks 2, 3, 4 and 5. At difficulty 0 each of those cost one computation. At difficulty 3 each one costs a mean of 4,115 attempts, measured over 120 trials, and the attacker has to pay that four times over rather than once.

There is a second cost that is easy to miss. While the attacker is redoing four blocks, an honest register is still adding new ones, and every new block is another block the attacker must also redo before the rewritten version can be as long as the real one. The work is not a fixed bill, it is a race against a register that keeps moving.

One camp treats proof of work as a security mechanism in the full sense. There is no administrator to appeal to, so the only thing that can deter a rewrite is making it cost more than it is worth, and a cost that anybody can verify from the data alone is exactly the right shape for a system with nobody in charge.

The other camp says calling cost security mislabels a deterrent as a guarantee. A cryptographic property holds regardless of who is attacking. A cost only holds while the attacker's budget is smaller than the honest work being done, which is a claim about economics, not about mathematics, and it can change without anything in the code changing.

Both positions are held by people who understand the mechanism perfectly well, and the disagreement is about what kind of assurance has been bought rather than about how the mechanism works. It matters in a procurement conversation because the two camps write very different warranties.

Mining behaves like drawing until a rare event happens. The average wait is exactly what the arithmetic predicts, and a single wait can be almost anything. At difficulty 1 the measured runs went from 1 attempt to 101 around a mean of 16. At difficulty 4 they went from 149 to 339,789 around a mean of 74,190, all over 150 trials.

The practical consequence is that a lucky attacker exists, always, and does not need to be clever. Difficulty does not promise that a rewrite is slow. It promises that rewriting a long stretch of register, block after block, is slow on average, and averages only assert themselves over many blocks.

Three questions, in order. How many runs is that averaged over. What were the smallest and largest results. And was the measurement taken on the same configuration you are being sold. A supplier who has the first two answers has measured something. A supplier who has only a single impressive figure has run the thing once.

This generalises well past mining. Any figure produced by a process with a long tail behaves the same way, and a benchmark quoted from one run of a model, one load test or one query plan carries exactly the same defect.

Difficulty raises the cost of producing a block for everybody, honest or not. On a register maintained by many independent parties, the honest total is large and an attacker has to outspend it, so the price is paid by the attacker and inherited by everyone else as protection.

On a register where one organisation runs all the machines, the same rule raises that organisation's own running cost and raises nothing for an insider, because the insider is the one with the capacity. Adding difficulty to a single operator register buys a slower system and very little else, which is an awkward result for a lot of internal chain projects.