Chain selection and reversible state

A block tree contains several histories; the UTXO map represents exactly one of them. Keep those two ideas separate. Blocks, Height, and TotalWork describe accepted branches. Tip identifies the active branch, and UTXO must equal the unspent outputs obtained by executing that branch from genesis.

Work selects a history

For a child b, compute Height[b] = Height[parent] + 1 and TotalWork[b] = TotalWork[parent] + b.Work. The exercise supplies work directly; it does not derive work from a proof-of-work target. Height alone cannot select the winner when per-block work differs. A candidate with equal total work is stored but leaves the current tip unchanged. Here the return value reorg=true means any active-tip change, including an ordinary extension.

Consider G(work=1) → A(work=2) → C(work=2), whose total is 5. The competing branch is G → B(work=3) → D(work=2), whose total is 6. B alone has total 4 and loses; D makes its branch win. Both tips have height 2, so the fork search walks C and D back to A and B, then to G. For unequal heights, first move only the deeper pointer upward until the heights match, then move both together. The first identical block is the common ancestor; it is never disconnected.

Work through the UTXO transition

Let genesis create g:50. A spends g and creates a:40; C spends a and creates c:35. B instead spends g and creates b:45; D spends b and creates d:42. The suffix after each colon is an output value, not an identifier.

Step	Operation	UTXO afterward
Active C	Starting state	{c:35}
Disconnect C	Remove c, restore a	{a:40}
Disconnect A	Remove a, restore g	{g:50}
Connect B	Consume g, create b	{b:45}
Connect D	Consume b, create d	{d:42}

Old blocks are disconnected from tip toward fork; new blocks are connected from fork toward tip. Applying D before B fails because b does not yet exist. Undo records store the previous output, including its value, because the spending transaction cannot reconstruct it.

The subtle case: a spend inside one block

Suppose one block contains g → x followed by x → y. Its final state is {y}. After disconnecting that block the state must be {g}, never {g,x}. An undo list that indiscriminately records every spent input restores x even though x was created after the block began.

The supplied interface uses a flat undo list. Therefore record only consumed outputs that existed before this block. Track the outpoints created while applying the block and omit them from the undo list. Disconnect by removing all outputs created by the block, then restoring the saved pre-block outputs. An alternative design could store per-transaction undo and reverse transactions, but that is a different representation.

A rejected candidate must leave no trace

Now let D contain two transactions: the first validly spends b, while the second spends an unknown outpoint. If the implementation has already disconnected A and C or deleted b from the live map, simply returning false leaves Tip=C paired with the wrong UTXO state. Restoring the tip variable alone does not fix this.

Build a private UTXO view of the candidate's parent: copy the active map, disconnect back to the common ancestor, then connect the parent's branch in forward order. Validate the entire candidate in that view. Only after success publish its metadata and undo record; publish the private UTXO view and new tip only if total work is strictly greater. Invalid candidates, including losing side branches, leave all state maps unchanged and return (false,false).

This also explains why a valid sibling may spend g even when g is absent from the active tip's UTXO. Validation uses the candidate's parent history, not whatever branch happens to be active. Known accepted IDs are idempotent no-ops; a rejected ID must not accidentally become a known accepted block.

Scope and reconstruction checks

The constructor assumes a valid genesis and callers treat stored blocks as immutable. The exercise checks missing/repeated spends, malformed coinbase inputs, repeated transaction IDs within a block, live output overwrites, and work overflow. It omits signatures, value conservation, coinbase subsidy rules, networking, persistence and crash recovery. Copying a view makes a function call atomic in this in-memory model; it is not a durable database transaction.

Predict these outcomes before checking the answers:

1. A shorter branch has total work 12; the active longer branch has total 11. Answer: activate the shorter valid branch; height only aids ancestry.
2. A losing side branch spends an output created only on the active sibling. Answer: reject it without mutation; that output is absent at its parent.
3. A block creates x, spends x, then is disconnected. Answer: x remains absent; only pre-block consumed outputs are restored.
4. Two siblings both have total work 8. Answer: retain the active sibling and store the other valid candidate.

For the production mechanisms behind these ideas, see Bitcoin Core's chain activation and disconnect/connect implementation. Its cache layers, validation rules and disk recovery are substantially broader than this exercise's model.