Each result below is stated once, with its method, its limits and its trust boundary, and comes with a check pack that reruns it.
Watchdog
Claim
Blind test, 3 of 3 planted bugs found, 0 false positives, on one 8‑bit watchdog.
Result
3 of 3planted bugs foundall planted bugs
0false positivesno finding outside the plant
1design38 lines of Verilog, 1,271 bytes, 8-bit
Method
Blind meant this: an examiner wrote the watchdog RTL with three bugs planted and sealed the answer key. We received the RTL and a four-sentence English specification, and nothing else.
Twelve properties were generated from the specification. The owner of the specification accepted eleven as stating it.
Formal checking found six violations of accepted properties. Each one was reproduced by an independent replay of the unchanged RTL against the unchanged property.
The report was then graded against the sealed key: the six findings map to the three planted bugs, and none points at behaviour that was not planted. Five further properties hold by induction.
Limits
One design: 38 lines of Verilog, 1,271 bytes, an 8-bit counter with a programmable timeout.
Three planted bugs and a four-sentence specification.
The properties were accepted by the owner of the specification before any verdict was graded.
Trust boundary
The replay proves that the unchanged RTL violates each accepted property.
That each property states the intended behaviour rests on its acceptance by the owner of the specification. The pack carries each property beside the specification so you can read them together.
The RTL, the specification, the six formal tasks with their accepted properties, the recorded verdicts and counterexample traces, one replay command, SHA-256 of every file.
Crop of the recorded counterexample trace. Reset releases with enable high, timeout_val at 0 and count at 0. The accepted property requires irq on the next cycle; the design keeps irq at 0.
The six recorded verdicts the replay compares against
bmc_irq_asserts_on_timeoutfailed assertion formal_wrapper.a_irq_asserts_on_timeout at property_bmc_irq_asserts_on_timeout.sv:37.140-37.186 step 3
bmc_timeout_zero_immediate_irqfailed assertion formal_wrapper.a_timeout_zero_immediate_irq at property_bmc_timeout_zero_immediate_irq.sv:37.128-37.178 step 3
cover_timeout_max_no_wrapformal_wrapper.c_timeout_max_no_wrap at property_cover_timeout_max_no_wrap.sv:37.5-37.279
bmc_reset_clears_statefailed assertion formal_wrapper.a_reset_clears_state at property_bmc_reset_clears_state.sv:37.17-37.84 step 1
bmc_count_increments_when_enabledfailed assertion formal_wrapper.a_count_increments_when_enabled at property_bmc_count_increments_when_enabled.sv:37.96-37.176 step 3
bmc_count_holds_when_disabledfailed assertion formal_wrapper.a_count_holds_when_disabled at property_bmc_count_holds_when_disabled.sv:37.97-37.164 step 4
Decoder
Claim
On the EPFL benchmark "dec" (8‑input decoder), a 6‑input LUT network of 258 LUTs at 2 levels, against the published 264, plus a certified proof that 257 LUTs do not suffice (SAT refutation checked by cake_lpr, plus a Lean 4 proof). Also exactly 129 LUTs for the 7‑input decoder.
Result
258LUTs at 2 levelsthis network
264LUTs at 2 levelspublished
257LUTsproven impossible
129LUTs7-input decoder, exact
Method
Two shared 6-input LUTs, one reading inputs 0 to 5 and one reading inputs 2 to 7, were found by exact SAT synthesis. Each of the 256 outputs is one LUT that reads one shared LUT and five inputs.
The netlist is checked against the benchmark by exhaustive simulation of all 256 input patterns on all 256 outputs, and by combinational equivalence checking.
Lower bound: the 256 outputs are distinct minterms, so each needs its own LUT, and a 257-LUT network has exactly one more. Whether one more LUT can serve all 256 outputs is written as a SAT formula. A SAT solver refutes it and writes an LRAT proof; cake_lpr checks that proof.
A Lean 4 development proves the same bound for every network of 6-input LUTs over 8 inputs that computes the decoder, with its own encoder and the refutation checked inside Lean. It also proves 129 as the lower bound for the 7-input decoder, and a 129-LUT network for that decoder exists.
Limits
One circuit of the EPFL suite: dec, the 8-input decoder. The 7-input result is the decoder one size down.
The cost measured is the number of 6-input LUTs. Levels are LUT levels.
The construction with two shared LUTs applies to decoders.
Trust boundary
cake_lpr verifies that the LRAT file refutes the formula it is given: the encoded formula is unsatisfiable.
The Lean 4 proof covers every step from the definition of a 6-input LUT network computing the decoder, through the lemmas and the Lean encoder, to the refutation of the formula that encoder writes.
Outside the Lean proof: that its network definition states what you mean by a LUT network (Model.lean, one file to read); Lean’s kernel, and Lean’s compiler for the one evaluation of the built-in LRAT checker; the separate encoder of the 257-LUT formula, whose refutation cake_lpr checks and whose correctness rests on the written proof; and the 258-LUT netlist, checked against the benchmark by simulation and equivalence checking.
Date
Status: [PLACEHOLDER, owner to set: internal result / preprint link / submitted]
6-input LUTs needed for the EPFL "dec" benchmark. The shaded range is ruled out by the certified refutation.
The checkers passing
Decoder check pack; output as recorded
$ cake_lpr bound/bound_257.cnf bound/bound_257.lrat
s VERIFIED UNSAT
$ lake build DecoderOptimality.Main
# last lines of the output
'DecoderOptimality.lowerBound' depends on axioms: [propext,
Classical.choice,
Quot.sound,
DecoderOptimality.Certificate.cert_ok._native.native_decide.ax_1_1]
'DecoderOptimality.lowerBound7' depends on axioms: [propext, Classical.choice, Quot.sound]
The 258-LUT network
258 LUTs: shared LUTs Y0 and Y1 at level 1, then one LUT per output at level 2. Each square is one output; its colour is the shared LUT it reads (128 read Y0, 128 read Y1). Every output LUT also reads five of the eight inputs.