The Vermilion Experiment: Implementing a Lean Back End for Verus
an experimental Lean backend for the Verus
以下正文同步自 Hacker News 最新,版权归原站所有,已转换为易读排版。
by Ilya Sergey
·
October 18, 2026
· 27 min read
verification
rust
verus
lean
smt
ai
In this post, we discuss Vermilion, an experimental Lean backend for the Verus verifier for Rust, bringing interactive proofs and Lean’s mathematical libraries to programs with ordinary Verus specifications.
The Rust examples and Lean proofs in this post, together with instructions for checking them, are collected in the open source repository.
A program verifier connects two descriptions of the same computation: a program, which tells the machine how to calculate the result, and a specification, which says what the result should satisfy. For example, a sorting function’s specification might require that the output is ordered and contains exactly the elements of the input. The specification leaves open the choice of the exact algorithm to do so.
One common way to check the alignment between the program and its spec is to turn them together into a collection of mathematical propositions, called verification conditions, or VCs. Each proposition captures something that must hold at a particular point in the program: an addition must not overflow, a function call must satisfy its precondition, or a returned value must satisfy the promised postcondition. If we can prove all these propositions, and the translation produced the right propositions, we have established that the program satisfies its specification.
Verifiers such as Dafny, Verus, and F* use SMT solvers to discharge many of these obligations automatically. SMT stands for satisfiability modulo theories: a solver searches for an assignment of values that makes a formula true, using built-in reasoning about domains such as integers, arrays, and bit vectors. To prove a VC proposition, a verifier asks whether its negation is satisfiable. If the answer is no, the VC holds. Z3 and cvc5 are two widely used solvers; both Dafny and Verus normally use Z3.
This style of verification is commonly called auto-active. The programmer provides specifications and proof guidance in the source of the program, including assertions, auxiliary lemmas, and loop invariants. The verifier then attempts the proofs automatically. The division of labour is quite compelling: humans state the intended properties, while the solver takes care of much of the logical bookkeeping.1
There is a separate question about the verifier itself: why should proving its VCs establish anything about the original program? A foundational verifier answers this question with a machine-checked soundness proof, connecting the generated obligations to a formal semantics of the program. For instance, Velvet, which we discussed earlier on this blog, derives its verification machinery from a semantics embedded in the Lean theorem prover. A conventional, non-foundational verifier leaves this connection in its trusted implementation (which might have bugs). It can be carefully designed and extensively tested, but a bug in the translation may still produce an incorrect verification result.
Building a foundational verifier for a realistic language is a daunting task. Before proving anything about verification conditions, we need a mathematical account of what programs in that language mean, including their memory operations and exceptional behaviours. Rust makes this especially interesting with its ownership discipline, lifetimes, and unsafe interfaces. Existing foundational Rust verifiers, such as RefinedRust, cover restricted fragments of the language. Extending these foundations to the breadth of Rust used in practice remains a substantial research problem.
Our experiment dubbed Vermilion (“Verified Rust Meets Lean”) starts with a more modest question: how much can we gain by keeping an existing Rust verifier’s translation and changing the means by which its verification conditions are proved?
SMT solvers are amazing at the kinds of reasoning that arise repeatedly in program verification. Given suitable bounds, they can prove that an array access is valid, establish a simple arithmetic fact, and combine facts from several branches. This automation is a large part of what makes Verus pleasant to use.
Unfortunately, it is also incomplete. A true statement may require induction, a carefully chosen existential witness, or a mathematical lemma that the solver has never been told about. Even a statement within the solver’s usual reach can fail because the relevant quantified fact was not instantiated at the right argument. Verus exposes some control over this process through triggers. Consider a specification fragment saying that every element of a sequence is bounded:
forall|i: int| 0 <= i < s.len() ==> #[trigger] s.index(i) <= bound
The annotation tells the solver to use occurrences of s.index(...) as candidates for instantiating i. If the proof context contains s.index(3), this gives the solver a reason to consider the quantified statement at i = 3. Choosing triggers well can make a proof succeed; choosing them poorly can leave useful facts unused or cause an explosion of instantiations. The Verus guide explains the rules. The mathematical meaning of the assertion is unchanged. Programming with triggers is manageable when the missing step is obvious. It becomes frustrating when we already know a proof but must work out how to communicate it through the solver’s instantiation strategy. Verus provides proof functions and assertion blocks for doing so, yet the final step still goes through its automated proving machinery.
A verifier embedded in Lean would have another route available. We can inspect a goal, introduce a witness, perform induction, or apply a library theorem directly. We used this combination of automatic and interactive reasoning in the Velvet post. The recent paper on building Veil in Lean discusses the broader design: making verification conditions ordinary Lean goals gives the verifier access to the proof assistant’s existing proof mode, UI, and toolchain.
The same observation applies to mathematical libraries. An SMT-based verifier needs a library of definitions and lemmas expressed in its own specification language. Verus already has a substantial one, called vstd, so users certainly do not start from nothing. Still, if an algorithm needs matrix algebra, somebody must supply the relevant definitions and laws in that ecosystem. A theorem in a Lean library cannot simply be invoked by a Verus proof.
Lean and Rocq have extensive mathematical libraries built over years of formalisation. Lean’s Mathlib includes linear algebra, number theory, and much more. If our verification conditions use its mathematical objects, we can reuse theorems about them. This suggests the experiment: combine Verus’s ability to handle realistic Rust with Lean’s proof mode and mathematical vocabulary.
To see where a Lean backend belongs, let us look briefly at Verus’s translation pipeline. Verus starts with Rust extended by specification and proof constructs, usually written inside a verus! macro. Its frontend uses the Rust compiler infrastructure and performs the additional checks that separate executable code, specifications, and proofs. The frontend produces VIR, Verus’s intermediate representation. Subsequent passes simplify VIR into SST, a representation that separates statements from expressions and makes the verification-relevant operations explicit. The usual backend translates SST into AIR, a solver-oriented representation, and eventually sends SMT queries to Z3.
Vermilion branches off at SST, before the SMT-specific encoding:
Rust + Verus specifications
|
Verus frontend and VIR
|
Verus simplification
|
SST
/
/
Verus backend Vermilion adapter
| |
AIR Small textual IR
| |
SMT queries Lean VC generator
| |
Z3 Lean theorems
|
Automation or proof scripts
|
Lean kernel
Both routes reuse Verus’s frontend and SST construction. Vermilion’s verification runs use the Lean route; the Z3 route is used separately for comparisons.
SST is a convenient place to make this change because much of the difficult work has already happened. Names and types have been resolved, complex source expressions have been decomposed, and checks for operations such as bounded integer addition have been inserted. Function contracts and loop invariants are available explicitly. So we can focus on turning this representation into mathematical obligations.
For example, suppose the source computes let y = x + 1 on u32 values and then asserts that y > 0. An abbreviated, readable version of the SST looks like this:
Assert 0 (HasType u32 (x + 1)) Assume (HasType u32 (x + 1)) Assign y (Clip u32 (x + 1)) Assert 1 (y > 0) Assume (y > 0) Return y
This is pseudocode for the SST nodes, with temporary names and source locations removed. The full representation is available in the Vermilion repository. HasType u32 expresses the range check that prevents overflow. Clip converts the mathematical result back to the machine integer range. Once the range check is proved, clipping preserves the result. The Assume following an Assert makes an established fact available to later checks; the assertion itself must still be proved.
VC generation then follows familiar logical rules. An assignment substitutes the assigned expression for the variable’s subsequent uses. An assertion becomes a goal under the facts available at that point. A conditional adds its condition to one branch and its negation to the other. A function call requires proving the callee’s precondition, after which the callee’s postcondition describes the result. This is modular reasoning: callers can use a contract without expanding the callee’s implementation.
These rules can be described using weakest precondition calculus: the conditions that must hold before a command for a desired property to hold afterwards. Weakest-precondition reasoning works backwards from the desired result. Vermilion’s implementation instead traverses the statements forwards, accumulating hypotheses and emitting obligations at each check. These are ordinary logical transformations; the resulting propositions do not require SMT-LIB as their output language.
The implementation keeps the Rust and Lean sides separate. A Rust adapter lowers SST to a small textual IR; Lean parses that IR and constructs the theorem statements. It also retains source locations, so a failed theorem can be reported at the corresponding Rust expression. The Vermilion design document describes these stages in more detail.
Let us follow a simple example from the Vermilion test suite:
fn increment(x: u32) -> (y: u32) requires x < 100, ensures y == x + 1, { let y = x + 1; assert(y > 0); y }
Here, requires states the precondition, and ensures states the postcondition. The return value is named y so that the specification can refer to it. As in the rest of the Rust snippets below, the surrounding imports and verus! wrapper are omitted.
Vermilion represents a u32 value as a Lean integer together with an explicit range hypothesis. The predicate Vermilion.inUnsignedRange 32 x means $0 \leq x < 2^{32}$. This representation lets arithmetic tactics reason about ordinary integers while keeping the machine bounds visible.
The first generated obligation in Lean is the inserted overflow check:
theorem assert_0 (x : Int) (requires_0 : Vermilion.inUnsignedRange 32 x) (requires_1 : x < 100) : Vermilion.inUnsignedRange 32 (x + 1) := by vrml
The theorem says exactly what we expect: adding one to a nonnegative integer smaller than 100 produces a value that fits in 32 bits. vrml is Vermilion’s default proof tactic; we will return to it shortly.
The next obligation comes from our explicit assertion:
theorem assert_1 (x : Int) (requires_0 : Vermilion.inUnsignedRange 32 x) (requires_1 : x < 100) (assert_0 : Vermilion.inUnsignedRange 32 (x + 1)) : ((x + 1) % 4294967296) > 0 := by vrml
Notice two details. First, the earlier overflow check i
正文由 探How 从来源站点 RSS 同步,内容未经改写;遇到排版缺失或需要图片、视频时请以原文为准。