# bbbq-1 — Problem Statement DEF CON 2026 finals, King-of-the-Hill. Instruction set: `BBBQ-ISA-1.md` (unchanged from `bbbq`). --- ## 1. Change from `bbbq` | | `bbbq` | `bbbq-1` | |---|---|---| | instruction set | 40 valid opcodes | **identical** | | input | 256 values, each a `u32` zero-extended | **5348 values, full 64-bit, bit 63 always set** | | task | sort ascending, emit 256 values | **four bucketed checksums, emit 4 values** | | score | `hwm × (1+cv) + ln(insn_count)` | same **plus `program_size_bytes × 0.00004`** | | queue / instruction limits | `0x0FFFFFFF` / `2^32` | **identical** | Every program written for `bbbq` fails on `bbbq-1`. --- ## 2. The task Write a program for a 4-queue virtual machine that reads 5348 values from an input stream, sums them into four buckets by stream index modulo 4, reduces each bucket modulo 1337, and emits the four results. Producing the correct output is only the entry condition. What is graded is a **cost function that you minimise**: peak queue occupancy, imbalance across the four queues at that peak, instruction count, and — new in `bbbq-1` — the size of the submitted program. **Submission artifact:** a `program.bbbq` file — a raw array of little-endian `u32` instruction words. No header, no magic, no metadata. Size must be a non-zero multiple of 4. --- ## 3. Invocation ``` ./bbbq-1 ``` `seed_hex` must decode to exactly 32 bytes; it seeds a ChaCha20 PRNG. | Situation | Output | Exit | |---|---|---| | no/too few args | `usage: ./bbbq-1 ` | 2 | | seed not hex | `bbbq: seed_hex is not valid hex` | 2 | | seed wrong length | `bbbq: seed_hex must decode to exactly 32 bytes, got N` | 2 | | empty program file | `bbbq: empty input` | 2 | | program size not a multiple of 4 | `bbbq: ` | 2 | | program ran but failed the gate | `{"success":false,"detail":"bad input","error":"bad input"}` | 1 | | success | scored JSON (§5) | 0 | --- ## 4. The input and the required output ### Input The PRNG produces **5348 records**. Each record is assembled from two 32-bit PRNG words `lo` and `hi` as ``` record = (hi << 32) | lo | (1 << 63) ``` so **bit 63 is always set** — every record is a full 64-bit value in `[2^63, 2^64)`, and two records never fit in one queue slot. The stream is **read-once**: `IN`, `INQ` and `VIN` consume from it, nothing rewinds it, and once exhausted further reads are silently ignored. ### Required output ``` bucket[k] = Σ { record[i] : i ≡ k (mod 4) } # exact, 128-bit, no wrapping OUT = [ bucket[0] % 1337, bucket[1] % 1337, bucket[2] % 1337, bucket[3] % 1337 ] # exactly 4 values, in this order ``` `5348 = 4 × 1337`, so each bucket holds exactly 1337 records. The reference implementation accumulates each bucket as a `u128` (1337 records of up to `2^64` need 75 bits) and then calls `__umodti3(bucket, 1337)`. A program does **not** need 128-bit arithmetic: since `(Σx) mod m ≡ (Σ (x mod m)) mod m`, reducing every record modulo 1337 before accumulating keeps every intermediate under 2674. `VIN` (`0x2E`) pushes four consecutive stream values into `Q0 Q1 Q2 Q3` respectively, which is exactly this bucketing. --- ## 5. The gate Two conditions, both required, plus a clean halt: ``` halt_status == 0 # the program executed HALT (0x29) OUT.len() == 4 OUT == the four values defined in §4 ``` Two hard limits abort the run before it can be graded: | Limit | Value | Halt status | |---|---|---| | combined queue length | `0x0FFFFFFF` = 268 435 455 | 3 | | instruction count | `2^32` | 4 | **There is no diagnostic feedback.** An invalid opcode, running off the end of the program, a queue overflow, an instruction-limit blowout and a wrong result all produce the same byte-identical failure line. The binary cannot be used to debug a program. --- ## 6. The score After **every single instruction** the VM samples its four queue lengths and reduces them to one number: ``` lens = [len(Q0), len(Q1), len(Q2), len(Q3)] total = sum(lens) mean = total / 4 cv = 0 if mean <= 0 = sqrt( sum((l - mean)^2 for l in lens) / 4 ) / mean otherwise metric = total * (1 + cv) ``` It retains the sample with the **largest `metric`** over the whole run — the program's worst moment — and reports that sample: ``` score = high_water_mark * (1 + covariance) + ln(insn_count) + program_size_bytes * 0.00004 ``` - `high_water_mark` — `total` at that worst moment - `covariance` — `cv` at that moment; the field name is a misnomer, it is a coefficient of variation - `insn_count` — instructions retired over the whole run - `program_size_bytes` — the size of the submitted file, i.e. `4 × word_count` The `0.00004` multiplier is a `double` constant at file offset `0x3590`; the term is added, not subtracted. `"halted"` and `"correct"` are hardcoded `true` in the success path and carry no information. ### Direction **Lower is better.** The binary only reports the number; it does not rank. Every term is a cost, and `high_water_mark` is standard peak-occupancy terminology. ### What each term costs | Term | Charges for | Notes | |---|---|---| | `high_water_mark` | peak values held in queues | The task no longer forces anything to be retained — each record can be reduced and discarded as it arrives — so this term is not bounded below by the input size the way it was in `bbbq`. | | `1 + covariance` | imbalance across the four queues at that peak | 1.0 when perfectly even, up to `1 + √3 = 2.7320508` when everything sits in one queue. A multiplier, so it is the harshest term per unit. | | `ln(insn_count)` | run length | Logarithmic and therefore weak: halving the instruction count saves `ln 2 = 0.693`. At minimum roughly 5348 records must be consumed, so a few tens of thousands of instructions is the realistic scale, i.e. ~10–11. | | `program_size_bytes × 0.00004` | code size | New in `bbbq-1`. 250 bytes per point. A 1 000-word program costs 0.16; a fully unrolled 300 000-word program costs 48. This is what makes unrolling expensive. |