Consensus

Proof of work

Chaining by hashing makes history detectable in the event of alteration, but does not, on its own, stop an attacker from recomputing the whole sequence of blocks. To make this recomputation economically infeasible, Bitcoin imposes a cost on the creation of each block: the proof of work.

The idea: make a block expensive to produce

Adding a block must not be free. The participants who propose blocks, the miners, must solve a computationally hard problem whose solution is nonetheless easy to verify.

The problem: find a number, the nonce ("number used once"), such that the hash of the block header, once this nonce is inserted, is below a target—in other words, that it begins with a certain number of zeros.

en-tête = numéro + racine de Merkle + empreinte précédente + nonce

On cherche nonce tel que  H(en-tête) < CIBLE
   c.-à-d.  H(en-tête) commence par (disons) 4 zéros.

nonce = 0      -> H = 9f3a...    (trop grand, raté)
nonce = 1      -> H = c17b...    (raté)
nonce = 2      -> H = 4e88...    (raté)
   ... des milliards d'essais ...
nonce = 726431 -> H = 0000a3d1... (< CIBLE : trouvé !)

Easy to verify, hard to produce

This is the fundamental asymmetry, the same philosophy as the one-way function:

Producing the solution: since the hash is unpredictable (avalanche effect), there is no cleverer method than to try billions of nonces at random. This requires enormous computing power, hence energy.
Verifying the solution: it is enough to compute a single hash and check that it is indeed below the target. Instantaneous.

Anyone can therefore check in a millisecond that a miner really did the work—without redoing that work.

The target and the difficulty

The lower the target (the more zeros required), the more tries are needed on average. The network automatically adjusts this difficulty so that a block is found at a regular interval (roughly every 10 minutes for Bitcoin), whatever the total power connected.

Why this protects history

Let us go back to the attacker who wants to modify an old block. Hashing already forced them to recompute all the following blocks. With proof of work, each of these recomputations requires finding a valid nonce, that is, redoing all the mining.

Falsifier le bloc N  =>  refaire la preuve de travail de N,
                         puis de N+1, N+2, ... jusqu'au sommet
   Pendant ce temps, le réseau honnête continue d'allonger
   la chaîne. L'attaquant doit donc miner PLUS VITE que
   tout le reste du réseau réuni. Économiquement infaisable.

This is why a block is considered all the more final as many blocks have been stacked on top of it: each one adds a layer of work to redo.

In summary