merc-verified

Formal verification of labelled transition system (LTS) algorithms. Rust implementations in crate/ are translated to Lean 4 via Aeneas and verified against formal definitions in MercVerified/.

We want to prove the correctness of the merc repository. For this we introduce a derived crate of (simplified) Rust code that we can translate to Lean and verify. The MercVerified/ directory contains the formal definitions and proofs, while Code contains the generated Lean code from the Rust implementations.

Prerequisites

• Rust (stable toolchain)
• Lean 4 (managed via elan)
• OCaml 5.3 (via opam, for building Aeneas)

Getting Started

1. Initialize the submodules

Use the following command to initialize the git submodule:

git submodule update --init --recursive

2. Build Charon and Aeneas

Charon compiles Rust to LLBC, and Aeneas translates LLBC to Lean.

# Install OCaml dependencies
opam switch create 5.3.0

opam install ppx_deriving visitors easy_logging zarith yojson core_unix odoc \
  ocamlgraph menhir ocamlformat.0.27.0 unionFind zarith progress domainslib

cd aeneas

# Build Charon (Rust → LLBC compiler)
eval $(opam env)
make setup-charon
cd ..

# Build Aeneas (LLBC → Lean translator)
make
cd ..

3. Generate Lean code from Rust

# Generate LLBC from the Rust crate
cd verified
../3rd-party/aeneas/charon/bin/charon cargo --preset=aeneas
cd ..

# Translate LLBC to Lean
./3rd-party/aeneas/bin/aeneas -split-files -backend=lean -dest=. -subdir=MercVerified/Code ./verified/verified.llbc

The generated Lean files will appear in MercVerified/Code/.

4. Build the Lean project

lake build

This builds both the formal definitions in MercVerified/ and the generated code in MercVerified/code/, checking all proofs.

5. Proving with AI agents

Install ripgrep for searching:

cargo install --locked ripgrep

Install the uv Python package manager for the lean-lsp-mcp. A MCP is a Model Context Protocol that allows AI agents to connect to external programs, in this case interacting with lean.

cargo install uv