Proof

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 3 planted bugs foundall planted bugs
  • 0 false positivesno finding outside the plant
  • 1 design38 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.

Date
Check pack

Download the watchdog check pack zip, 21 kB

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.

Replay: sh replay.sh

SHA-256 fe54982d8060c34c7bf98ceb2fc0522b51ef4b97507c9a0bb771d1605956e1d6

Counterexample, finding irq_asserts_on_timeout

Counterexample for irq_asserts_on_timeoutReset releases, enable is high, timeout_val is 0 and count is 0, so the property requires irq to assert on the next cycle. irq stays 0 while the check is active.clkrst_nenablekicktimeout_val10count0irqcheck activeirq must be 1 here
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
  • 258 LUTs at 2 levelsthis network
  • 264 LUTs at 2 levelspublished
  • 257 LUTsproven impossible
  • 129 LUTs7-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]

Check pack

Download the decoder check pack zip, 17.2 MB

Netlist, both CNF formulas, both LRAT proofs, the Lean 4 sources, checker versions, one replay command, SHA-256 of every file.

Replay: sh replay.sh

SHA-256 a01e53dc81f0e09cd4cbe7e7b0ee50e39c0e2c7d2baf3590d4c9cad6aa112592

258 against 264, with 257 proven impossible

LUT count for the 8-input decoder257 LUTs and fewer: proven impossible. 258 LUTs: this network. 264 LUTs: published.255256257258259260261262263264265257: proven impossible258: this network264: published
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

The 258-LUT network for the 8-input decoder8 inputs. Shared LUT Y0 reads inputs 0, 1, 2, 3, 4, 5; shared LUT Y1 reads inputs 2, 3, 4, 5, 6, 7. 256 output LUTs in 2 levels: 128 read Y0 and 128 read Y1, each with five inputs.x0x1x2x3x4x5x6x7Y0Y1256 output LUTs, level 2level 1

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.