# BLK-002: Cost-Aware Bundle Iteration

> **Authoritative requirement:** [BLK-002](../NORMATIVE.md#BLK-002)
> **Verification:** [VERIFICATION.md](../VERIFICATION.md)
> **Tracking:** [TRACKING.yaml](../TRACKING.yaml)
> **Spec reference:** [SPEC.md](../../../../resources/SPEC.md) — Section 6

---

## Summary

BLK-002 specifies the bundle iteration strategy used by `build_block_generator()`. Bundles MUST be processed in the order provided by the caller, and each bundle's CLVM cost is computed to determine whether it fits within the remaining cost budget. Bundles that would exceed `max_cost` are skipped (not rejected as errors), and iteration continues to subsequent bundles that may fit. The caller is responsible for pre-sorting bundles by fee/cost ratio before passing them in.

This mirrors Chia L1's `create_block_generator()` at [`mempool.py:505`](https://github.com/Chia-Network/chia-blockchain/blob/main/chia/full_node/mempool.py#L505), where the mempool maintains bundles sorted by fee-per-cost ratio and the block builder greedily adds them until the block is full. On L1, bundles that exceed the remaining cost budget are skipped, not treated as errors, because a smaller bundle later in the list might still fit.

The iteration order is significant for fee optimization. By requiring the caller to pre-sort by fee/cost ratio (highest first), the greedy algorithm maximizes total fee revenue for the block producer. This separation of concerns keeps `build_block_generator()` focused on assembly while leaving prioritization policy to the caller.

---

## Specification

### Iteration Algorithm

```rust
// Pseudocode for the iteration logic inside build_block_generator()
let mut remaining_cost = max_cost;
let mut included_bundles = Vec::new();

for bundle in bundles {
    // Run CLVM to compute this bundle's cost
    let bundle_cost = compute_bundle_cost(bundle, context)?;

    if bundle_cost > remaining_cost {
        // Skip this bundle — it doesn't fit
        continue;
    }

    // Include this bundle
    remaining_cost -= bundle_cost;
    included_bundles.push(bundle);
}
```

### Behavioral Rules

1. **Order preservation**: Bundles MUST be evaluated in the exact order provided by the `bundles` slice. The function MUST NOT reorder, sort, or shuffle bundles internally.

2. **Cost computation**: For each bundle, the function MUST execute the bundle's CLVM programs to determine its actual cost. The cost MUST NOT be estimated or approximated.

3. **Skip on exceed**: If a bundle's cost would cause the cumulative total to exceed `max_cost`, that bundle MUST be skipped. Skipping is not an error condition.

4. **Continue after skip**: After skipping a bundle, the function MUST continue evaluating subsequent bundles. A later bundle with lower cost may still fit within the remaining budget.

5. **Caller sorts**: The function MUST NOT sort bundles by fee, cost, or any other criteria. Sorting is the caller's responsibility. This matches L1's pattern where `create_block_generator()` receives pre-sorted items from the mempool.

6. **Cost accounting**: The total cost reported in `BlockGeneratorResult.cost` MUST equal the sum of costs of all included bundles.

### L1 Correspondence

| dig-clvm Behavior | Chia L1 Behavior | Source |
|-------------------|-----------------|--------|
| Iterate in order, skip on exceed | `create_block_generator()` iterates mempool items | [`mempool.py:505`](https://github.com/Chia-Network/chia-blockchain/blob/main/chia/full_node/mempool.py#L505) |
| Caller pre-sorts by fee/cost | Mempool maintains fee-sorted order | [`mempool.py` fee sorting](https://github.com/Chia-Network/chia-blockchain/blob/main/chia/full_node/mempool.py) |
| Skip, don't error | L1 skips transactions that don't fit | [`mempool.py:505`](https://github.com/Chia-Network/chia-blockchain/blob/main/chia/full_node/mempool.py#L505) |

---

## Acceptance Criteria

- [ ] Bundles are processed in the exact order they appear in the input slice (verified by inspecting which bundles appear in the output)
- [ ] A bundle whose cost exceeds the remaining budget is skipped without producing an error
- [ ] After skipping an expensive bundle, a cheaper subsequent bundle is still included if it fits
- [ ] `bundles_included` accurately reflects the number of bundles that were added to the block
- [ ] `cost` in the result equals the sum of individual costs of all included bundles
- [ ] The function does not internally reorder or sort the input bundles

---

## Implementation Notes

- The cost of each bundle must be determined by actually running its CLVM programs, not by using a cached or estimated value. This ensures accuracy even if the bundle's cost depends on the current chain state.
- The skip-and-continue strategy means that `bundles_included` may be less than the total number of bundles in the input, even if some later bundles have lower cost. This is intentional: the greedy approach with caller-provided ordering is the standard block-building heuristic.
- Performance consideration: each bundle requires CLVM execution to determine its cost. For large mempools, the caller should pre-filter obviously oversized bundles before calling `build_block_generator()`.
- The remaining cost budget decreases monotonically. Once it reaches zero, all subsequent bundles will be skipped (though the function should still iterate to completion for correctness).

---

## Verification

### Test Plan

| Test Case | Input | Expected Outcome |
|-----------|-------|------------------|
| All bundles fit | 3 bundles, total cost < `max_cost` | `bundles_included == 3`, `cost == sum of all 3` |
| Second bundle too expensive | Bundle A (cost 100), Bundle B (cost 9999), Bundle C (cost 50); `max_cost = 200` | B skipped, A and C included, `bundles_included == 2` |
| First bundle fills block | Bundle A (cost = `max_cost`), Bundle B (cost 1) | Only A included, `bundles_included == 1` |
| All bundles too expensive | 3 bundles each exceeding `max_cost` | `bundles_included == 0` (or error, implementation-defined) |
| Order preservation | Bundles [A, B, C] with distinct additions | Additions in result appear in A, B, C order |
| Cost accumulation accuracy | Known-cost bundles | `result.cost` matches sum of individual `run_spendbundle` costs |

### Verification Method

- **Simulator test**: Create bundles with known costs using `chia-sdk-test::Simulator`. Pass them to `build_block_generator()` with a `max_cost` that forces some to be skipped. Verify `bundles_included` and the specific bundles that were included.
- **Order test**: Create bundles with distinguishable outputs (different `CREATE_COIN` amounts). Verify the additions in the result preserve the input order.

---

## Source Citations

- Chia L1 `create_block_generator()`: [`mempool.py:505`](https://github.com/Chia-Network/chia-blockchain/blob/main/chia/full_node/mempool.py#L505)
- L1 block cost constant `MAX_BLOCK_COST_CLVM`: [`default_constants.py:68`](https://github.com/Chia-Network/chia-blockchain/blob/main/chia/consensus/default_constants.py#L68)

---

## References

- [BLK-001](BLK-001.md) — `build_block_generator` entry point
- [BLK-004](BLK-004.md) — `BlockGeneratorResult` structure (contains `bundles_included` and `cost`)
- [SPEC.md Section 6](../../../../resources/SPEC.md) — Path B flow diagram
