From Tests to Proofs: Formal Verification of the Nexbid Auction Engine

Unit tests check a finite number of cases. We mathematically proved the Nexbid Auction Engine correct in Lean 4 — for all possible inputs.

When an advertiser invests CHF 10,000 in a campaign budget, they want guarantees. Not "our tests are green," but "it is mathematically impossible for your system to overspend my budget." That's exactly what we now deliver. The Problem with Tests Unit tests are the foundation of modern software engineering. But they have a fundamental limitation: they check only a finite number of cases. A test with 1,000 inputs proves nothing about input 1,001. For business-critical financial logic — auctions, budgets, billing — that's not enough. Formal verification solves this problem. Instead of testing individual cases, you prove properties for all possible inputs. Not probabilistically, but mathematically — if the compiler accepts the proof, it is correct. What We Proved We rebuilt the core algorithms of the Nexbid Auction Engine in Lean 4 — a theorem prover and functional programming language — and formally verified 13 theorems: Theorem Property What It Guarantees T1 Score ∈ [0, 1] No score overflow, no negative scores T2 Normalization ∈ [0, 1] Bids correctly normalized T3 Eligibility correct Only solvent participants T4 Winner has max score Auction fairness T5 Winner is eligible Winner can pay T6 No eligible ↔ no winner No phantom winners T7a-e Budget never overspent Financial safety How It Works Lean 4 is simultaneously a programming language and a proof system. You write the function and the proof of its correctness in the same file. The compiler checks both. An example: The scoring formula score = w_bid × bid + w_sim × similarity + w_qual × quality + w_ctx × context. We prove: For ALL valid inputs (each value in [0,1]) and ALL valid weights (non-negative, sum = 1): The score always lies in [0, 1]. This is not a test with samples. It is a mathematical truth — proven simultaneously for infinitely many input combinations. Budget Safety: The CAS Invariant Budget management uses a Compare-And-Swap (CAS) pattern: A decrement is only executed if the remaining budget covers the amount. We prove five properties: T7a: After every decrement: spent ≤ total T7b: Spent increases by exactly the deducted amount T7c: Total budget never changes T7d: Failure means insufficient budget T7e: Spent is monotonically increasing (no resets) Design Decisions Rational numbers instead of floats: IEEE 754 floats have rounding errors. 0.3 is not exactly representable. In Lean we use Rat (fractions): 3/10 is exact. Proofs over exact arithmetic are stronger. Integers for budgets: …

Author
Holger von Ellerts
Published
2026-03-20
Topics
Verification, Research, Open Source