# bbbq-1 — Problem Statement DEF CON 2026 finals, King-of-the-Hill. Instruction set: `BBBQ-ISA.md`. > **The objective is to make the reported `score` as small as possible.** It is a cost > function, not a reward: every term is added, and lower is better. Producing the correct > output is only the entry condition — a program that fails the gate is not scored at all. --- ## 1. 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, divides each bucket sum by 1337, and emits the four quotients — that is, the integer mean of each of the four lanes. What is graded is a **cost function that you minimise**: peak queue occupancy, imbalance across the four queues at that peak, instruction count, and 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. --- ## 2. 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 | --- ## 3. The input and the required output ### Input The seed keys a ChaCha20 stream: constants `expand 32-byte k`, the 32 seed bytes as eight little-endian `u32` key words, block counter starting at 0, stream id 0. Output blocks are consumed in order, one `u32` word at a time. The stream supplies **5348 records**. Each record consumes two words — the first as the low half, the second as the high half — and forces bit 63: ``` record[i] = (w[2i+1] << 32) | w[2i] | (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 ] # floor division; exactly 4 values, in this order ``` `5348 = 4 × 1337`, so each bucket holds exactly 1337 records and each output is the floor of the arithmetic mean of one lane. Every record lies in `[2^63, 2^64)`, so every output does too — expect values around `1.5 × 2^63 ≈ 1.38e19`. The bucket sums are computed without wrapping: the reference accumulates each bucket as a `u128` (1337 records of up to `2^64` need 75 bits) and then calls `__udivti3(bucket, 1337)`. The quotient always fits in a `u64` because `bucket < 1337 × 2^64`. Note that the division is applied to the exact sum, not per record: `⌊Σx / n⌋` is not `Σ⌊x / n⌋`, so the full-width sum has to be formed before dividing. --- ## 4. 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 §3 ``` 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. --- ## 5. 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.** All four terms are added, and the objective is to minimise the total. The binary only reports the number; it does not rank. ### What each term charges for | Term | Charges for | Range | |---|---|---| | `high_water_mark` | peak number of values held in queues | 0 upward | | `1 + covariance` | imbalance across the four queues at that peak | 1.0 when the four lengths are equal, up to `1 + √3 = 2.7320508` when all values sit in one queue | | `ln(insn_count)` | number of instructions retired | ~9 at 8 k instructions, ~11 at 60 k, ~14 at 1 M | | `program_size_bytes × 0.00004` | size of the submitted file | 1 point per 25 000 bytes, i.e. per 6 250 instruction words | --- ## 6. Verification Everything above is reproduced from the binary's own output, not inferred from the decompile alone. - **Input model.** ChaCha20 was reimplemented independently and the required output recomputed from it. All four values match `bbbq-1`'s `output` field exactly, on four different seeds. A `% 1337` reduction of the same sums yields entirely different numbers (e.g. `[681, 485, 811, 307]` for seed `00…ff`), so the operation is division, and the reference helper is `__udivti3`, not `__umodti3`. - **Score formula.** `high_water_mark`, `covariance` and the full `score` were recomputed from `queue_lengths_at_hwm`, `insn_count` and the file size; the difference from the reported `score` is exactly `0.0` on all four seeds. - **Gate and error paths.** Every row of the §2 table was executed against `bbbq-1` and its exit code checked. A program that halts cleanly but emits the wrong output, one that runs off the end, one with a reserved bit set and one with an invalid opcode all produce the same `"bad input"` line with exit 1. - **Limits.** The queue check (`>= 0x10000000`) and the instruction check (`insn_count >= 2^32`) were located in the disassembly; they are not reachable in a normal run.