Proof of Work

Who gets to append the next block? In a permissionless network you can't vote — an attacker just fabricates a million identities and outvotes everyone (a Sybil attack). Nakamoto's 2008 answer: make block production cost something that can't be faked. One CPU-cycle, one vote — well, one hash, one lottery ticket.

Proof of Work: find a nonce such that hash(block) < target. SHA-256 output is uniformly distributed, so there is no cleverness available — you try nonces until one works:

The magic is the asymmetry: finding a valid nonce takes billions of tries, but checking one takes a single hash. A block carries its own proof of expenditure — no certificate authority, no trusted timestamping service, just arithmetic anyone can redo in a microsecond.

Target, difficulty, and leading zeros

The target is a 256-bit ceiling. Lower target = fewer acceptable hashes = harder. Expected attempts = 2^256 / target. Bitcoin's difficulty in the current era means roughly 4 × 10^23 expected hashes per block — which is why, at a network rate around 800 EH/s (8 × 10^20 hashes/second), a block still takes about 600 seconds to find. "Leading zeros" is the folklore version: requiring the hash to start with k zero hex characters is the same as target = 16^(64-k), so each extra zero multiplies expected work by 16. Real Bitcoin compares against a full numeric target so difficulty can move by 3%, not only by jumps of 16× — but for this course, counting zeros is exact enough.

What PoW buys — and what a 51% attacker gets

Honest miners spend electricity; the protocol pays them block rewards plus fees. To rewrite history an attacker must out-hash everyone else combined: with >50% of the hashrate they can, eventually, build a longer chain than the honest one. Be precise about what that enables and what it doesn't:

• Can: unwind and re-order recent blocks, double-spend their own transactions, censor transactions by mining empty blocks.
• Cannot: forge a signature, spend your coins, change the 21M supply, or alter old blocks cheaply — every rewritten block must be re-mined at full difficulty, so rewriting a week of history costs a week of the whole network's electricity.

A 51% attack is vandalism with a budget, not a skeleton key. (It's real, though — smaller PoW coins like Ethereum Classic have been successfully attacked.) The standing critique is energy: Bitcoin mining consumes an appreciable fraction of a percent of global electricity; Ethereum switched to Proof of Stake in 2022 largely for this reason.

Your exercise

For each line <data>|<difficulty>, find the smallest nonce ≥ 0 such that sha256("<data>:<nonce>") starts with <difficulty> zero hex chars, and print the nonce. Read the preimage carefully: the input separates fields with |, but the hash preimage joins data and nonce with a colon — for hello|2 you are hashing hello:614, not hello|614 and not hello614. That separator swap is the graded mistake: wrong-separator code returns a confidently wrong nonce on every test (hello|1 must print 7, hello|2 must print 614). Also start the search at nonce 0 — hello|0 expects 0 (difficulty zero: the empty prefix matches anything, and nonce 0 must be the one you try first, so loops that begin at 1 fail here), and bar|1 expects 1, which catches code that increments before returning and prints 2.