Block Assembly and Mempool Policy

Prerequisites: UTXOs, transaction inputs/outputs, sorting, and integer comparison. You will turn a candidate list into a deterministic sequence while maintaining a changing view of available outputs and a strict size budget.

1. Separate this policy from full validation

The exercise assumes individually valid non-coinbase candidates: positive sizes, unique nonzero IDs, no repeated input within a transaction, and nonnegative output counts. Fees and subsidy fit uint64 when summed; size arithmetic fits int. The block budget is at least the 100-byte coinbase size. Signature checks, network consensus rules, and package-aware selection are outside this task. Candidate transactions may conflict with each other or have dependencies; selection must handle those histories.

Sort candidates once by fee/size descending, then by fee descending, then by lexicographic ID bytes ascending. Scan once. A skipped candidate is never retried, even if its inputs become available later. This deliberate limitation makes it possible to trace the exact policy without assuming a production miner.

2. Compare rates without rounding

For positive sizes, compare feeA * sizeB with feeB * sizeA. For A=(fee 7, size 3) and B=(fee 9, size 4), compare 28 with 27; A has the higher rate. Integer division would give 2 for both and incorrectly invoke the fee tie-breaker. Cross-products can exceed uint64 even when individual fees fit, so use math/big or an exact overflow-safe comparison.

3. Follow one complete selection history

The initial UTXOs are u and v. The budget is 500 bytes and the subsidy is 50 units. Every candidate creates one output. Sort this pool by the rates shown:

Candidate	Input	Bytes	Fee	Fee/byte
C (child of P)	P:0	100	500	5
P (parent)	u	200	400	2
D (conflicts with P)	u	100	150	1.5
E	v	200	200	1

Begin with size 100 for coinbase and no selected fees.

Visit	Decision	Available outputs afterward	Total size	Fees
C	Skip: P:0 does not exist yet	u, v	100	0
P	Include: u exists, 300 fits	v, P:0	300	400
D	Skip: P already spent u	v, P:0	300	400
E	Include: v exists, 500 fits exactly	P:0, E:0	500	600

The result is [coinbase, P, E], with reward 50 + 600 = 650. C stays excluded. Its dependency becomes available too late for this single-pass policy. Checking every candidate against the initial UTXOs would incorrectly include D. Repeating scans would change the specified selection algorithm.

4. Make inclusion atomic

Use a temporary UTXO map so selection does not consume the caller's state. First check capacity and every input; only after all checks pass, delete spent inputs, add the candidate's output outpoints, and update totals. A candidate with inputs [available, missing] must leave the first input untouched when it is rejected. Likewise a transaction that exceeds the budget contributes no fee. The returned coinbase is first, but its output is not made spendable to candidates in this exercise.

Record these invariants after each candidate: total size equals 100 plus selected sizes, total fees equal selected fees, and each accepted input was available at inclusion time. The temporary map reflects exactly the accepted transactions.

5. Greedy has a measurable limitation

With 300 payload bytes available, consider independent A=(200 bytes, fee 400), B=(150,285), and C=(150,285). Greedy picks A at rate 2, then neither B nor C fits. Its fee is 400. Selecting B+C would fit exactly and yield 570. The required algorithm is deterministic; it does not promise optimal revenue. Dependencies give another limitation: evaluating a parent and child together could justify selecting a low-rate parent, but this exercise never forms packages.

6. Transfer the reasoning

A 400-byte total budget leaves 300 after coinbase. Sorted candidates are X=(200 bytes, fee 600, spends u), Y=(150,300, spends v), and Z=(100,100, spends v). Both u and v initially exist. Predict the selected IDs, total size, and reward with subsidy 50.

Check the state changes

X fits, giving total size 300. Y would raise it to 450, so skip Y without spending v. Z then fits exactly at total size 400. Select X and Z; reward is 50 + 600 + 100 = 750. Stopping at the first oversized candidate would miss Z.

Implement Block Assembly, using separate comparison, eligibility, and mutation steps. Try missing-input rejection after a valid first input, rate ties, an exact fit, and a parent sorted after its child. Then take the checkpoint.