Repository navigation
Description
VCVio's Interop/ package carries Rust code extracted by hax and Aeneas into VCVio. This issue records where it stands, and opens a discussion of how it should relate to neighbouring work. That includes @spitters's hax-lean, the verified hax pipeline that CatCrypt builds on.
Stability. Interop/ is experimental and changes much faster than the rest of VCVio. Any PR may rename its modules, restate its theorems or move its pins, without deprecations (#1092 states this in Interop/README.md). Core VCVio never depends on it, so it can still be reshaped around whatever is decided here.
What exists
-
One monad for Rust. hax and Aeneas both emit code in Aeneas's
Aeneas.Std.RustM.Interop.Rust.liftRustMlifts it into VCVio'sOracleComp.Interop/Rust/Triple.leancarries hax's and Aeneas's specifications into coreStd.WPtriples (feat(Interop): revive the hax and Aeneas bridges as Interop's own package #1074, feat(Interop): Aeneas's specifications in Std.WP, and its trees as PolyFun's #1075).
-
Aeneas's program logic.
Interop/Aeneas/shows that Aeneas's weakest preconditions over its interaction-treeRustMagree with PolyFun's (feat(Interop): Aeneas's weakest preconditions are PolyFun's readings #1081, with PolyFun feat(PRFTagReader): unlinkability reduction (closes #205); preserve auth track (#203) #426–BettersimualateQbridging withliftMarising fromPFunctor.lens#428). -
hax examples.
Interop/Hax/holds six small crates:- Barrett reduction and add-with-carry, from hax's own examples;
- ML-KEM's CBD(η = 1) sampler;
- three toys.
Their Rust contracts are proved with
hax_mvcgenand carried into VCVio, as far as the exact output distribution of the CBD sampler (feat(Interop): port the hax examples to Aeneas's scalars #1084). Onmainthe Lean code is transcribed by hand. feat(Interop): extract the hax examples with the hax CLI #1088, still open, extracts it with the hax 0.5.0 CLI through Charon and Aeneas, commits the output and checks it against a fresh extraction in CI. -
Pins. hax
a045d15a(0.5.0), Aeneas2b9e3ea4, Lean and Mathlib v4.35.0.
hax-lean
In its README's words, hax-lean is the "formal verification of the hax compiler phases that lower a Rust subset to a purely functional form, with the haxpipeT CLI that drives the pipeline on hax JSON dumps". CatCrypt uses its extractions for EdDSA, Sigma protocols, X3DH, PQXDH and the Double Ratchet, and as the input to its compiler. Two facts bear on connecting it with Interop/.
- The runtimes agree. hax-lean's
RustMis ported from Aeneas6852e647(HaxLean/Rust/Primitives.lean): a value, a failure, or divergence. At the Aeneas revision VCVio pins,RustMis an interaction tree whose only effect, a failure, has no answer.- The two are isomorphic monads: a bijection that preserves
pureandbind, in about 50 lines with standard axioms only (below). - The machine-integer types are the same structure over
BitVec.
- The two are isomorphic monads: a bijection that preserves
- One compatibility problem. Both declare
Aeneas.Std.RustMand the rest ofAeneas.Std.- So no Lean project can import hax-lean together with Aeneas or hax's Lean library, including VCVio's
Interop/. CatCrypt's extractions and VCVio's bridges can't currently meet in one project. - Anything joint needs this resolved. There are several ways: a namespace of hax-lean's own for the ported library, or a dependency on Aeneas, which hax-lean currently avoids because Aeneas requires Mathlib. Which fits best is Bas's call.
- So no Lean project can import hax-lean together with Aeneas or hax's Lean library, including VCVio's
Questions
- hax-lean's runtime. Is its ported library meant to follow upstream Aeneas, or to stay its own model? Would one shared
RustMhelp on the CatCrypt side, taken either from Aeneas or from a core of it that builds without Mathlib? - A bridge from
haxpipeT. Once the names are separate, VCVio could carryhaxpipeT's monadic output (--emit-monadic) intoliftRustM. That takes the isomorphism plus one lemma per guarded operation, relating it to Aeneas's checked operation. Would that be useful for CatCrypt, or does the useful direction run the other way? - The two Lean routes. hax 0.5.0's Lean backend goes through Charon and Aeneas, while the engine-based Lean backend is now
legacy-lean. How do you see hax-lean relating to the Charon and Aeneas route?- One option is cross-checking: extract a crate both ways and prove the two definitions agree.
- If that's of interest, which crates would make good shared targets, for example parts of ML-KEM or CatCrypt's protocols?
- Anything in the way. Is there anything in
Interop/that gets in the way of CatCrypt or hax-lean, or that should change while it is still unstable?
The isomorphism, checked against Aeneas 2b9e3ea4
import Aeneas
open Aeneas.Std
namespace FlatCheck
universe u v
/-- hax-lean's `RustM` shape, restated locally. -/
inductive FRustM (α : Type u) where
| ok (v : α)
| fail (e : Error)
| div
def FRustM.bind {α : Type u} {β : Type v} : FRustM α → (α → FRustM β) → FRustM β
| .ok v, f => f v
| .fail e, _ => .fail e
| .div, _ => .div
instance : Monad FRustM where
pure := .ok
bind := FRustM.bind
def toITree {α : Type u} : FRustM α → RustM α
| .ok v => .ok v
| .fail e => .fail e
| .div => .div
def ofITree {α : Type u} (x : RustM α) : FRustM α :=
match x.match with
| .ok a => .ok a
| .vis (.fail e) _ => .fail e
| .div => .div
theorem vis_eq_fail {α : Type u} (i : RustEffect.Input) (k : RustEffect.Output i → RustM α) :
∃ e, RustM.vis i k = RustM.fail e := by
cases i with
| fail e => exact ⟨e, by rw [RustM.fail_eq_vis]; congr; funext x; exact x.elim⟩
theorem ofITree_toITree {α : Type u} (x : FRustM α) : ofITree (toITree x) = x := by
cases x <;> simp [toITree, ofITree]
theorem toITree_ofITree {α : Type u} (x : RustM α) : toITree (ofITree x) = x := by
cases x using RustM.cases with
| ret a => simp [ofITree, toITree]
| vis i k =>
obtain ⟨e, he⟩ := vis_eq_fail i k
rw [he]; simp [ofITree, toITree]
| div => simp [ofITree, toITree]
def equiv {α : Type u} : FRustM α ≃ RustM α :=
⟨toITree, ofITree, ofITree_toITree, toITree_ofITree⟩
theorem toITree_pure {α : Type u} (a : α) : toITree (pure a : FRustM α) = pure a := rfl
theorem toITree_bind {α β : Type u} (x : FRustM α) (f : α → FRustM β) :
toITree (x >>= f) = toITree x >>= (toITree ∘ f) := by
cases x <;> simp [toITree, Bind.bind, FRustM.bind, Function.comp]
end FlatCheck
Activity
spitters commentedon Nov 13, 2026
Thanks for writing this up. Answers in order.
1. hax-lean's runtime. hax-lean keeps its own flat
RustM(a value, a failure or divergence), portedfrom Aeneas and built without Mathlib; it does not track upstream Aeneas. We will move the ported library
out of
Aeneas.Stdinto a namespace of hax-lean's own, which removes the clash on our side without adependency on Aeneas. That rename touches about 520 sites across hax-lean and the CatCrypt repositories
and none in VCVio; an
Aeneas.Stdalias kept in one prelude module lets Aeneas's printed output stillelaborate against our copy, and VCVio need not import that module.
Your isomorphism is the right relation between the two monads, and it has a reading that we can use
on both sides. In catcrypt-vcvio we wrote Rust's effects as a polynomial signature,
rustSig = C Error + 1,with a Rust program with oracle access a term of PolyFun's free monad over
rustSig + spec.toPFunctor(Signature.lean).
Neither operation has an answer, so without oracles the free monad over
C E + 1has exactly threekinds of terms, a value, a failure at some
e : Eand divergence. AtE = Aeneas.Std.Error, hax-lean'sRustMis that free monad, and your isomorphism shows that Aeneas's interaction-treeRustMis too.rustSiguses VCVio's richerError(seven kinds against Aeneas's two); the embedding of Aeneas'serrors makes
C Aeneas.Std.Error + 1a sub-signature ofrustSig.RustOracleComp spec = ExceptT Error (OptionT (OracleComp spec))and the failure-onlyOptionT (OracleComp spec)are handlers of thesignature, and
liftRustMis the fold oftoRustProgfollowed by the interpretation(HaxSignature.lean).
To move statements between the two monads we would use parametricity rather than rewriting by hand.
We have a container extension of ParamTransfer, our parametricity transfer library: a relation between two polynomial functors,
with levels on shapes and on positions, lifts to their free monads, and a program-tree type equivalent
to a free monad over a signature inherits that relation at every level. Both
RustMs are such types,so a triple, a panic-freedom statement or a run lemma proved for one transfers to the other by the
transfer tactic; we are finishing this instance for hax-lean's
RustM, with a triple and apanic-freedom statement transferred as tests. A sub-signature, such as the one above or the signature after Aeneas adds
an effect, is related to the larger one by an injective lens; we are adding that case, which transfers
every statement about the image of a smaller-signature program and, correctly, no statement quantified
over all programs of the smaller signature to the larger one.
2. A bridge from
haxpipeT. Yes, useful in both directions. On our side the lift exists:hax-lean's
RustMlifts intoRustOracleCompas a monad morphism(HaxRustM.lean), its
triples transfer to
Std.WPtriples there, and a function panic-free on a precondition runs to a pointmass on it
(HaxWP.lean).
haxpipeT --emit-readingprints, beside the--emit-monadicoutput, a theorem relating each printedfunction to the reading of its extracted literal; composed with hax-lean's range checker this gives
panic-freedom on the checked range with no proof per function (
ok_of_reading, in a compiler commit not yet published). After the rename, thebridge into VCVio's
liftRustMis the isomorphism (or the two handlers) plus one lemma per guardedoperation, as you say. Those lemmas exist for our copy: a table relates each of hax-lean's 83 runtime
operations to the Aeneas
Stdoperation on successful runs(RustSemantics.lean).
3. The two Lean routes. hax-lean reads the frontend's JSON export and proves its own lowering phases;
it does not go through Charon and Aeneas. Our compiler reads both routes. Besides the hax front it has an
Aeneas front:
reifyAeneas%reads the Lean that the Aeneas backend prints, elaborated against hax-lean'scopy of
Aeneas.Std, into the compiler'sNFProgIR with a proof of its denotation. The two entries areinstances of one structure
NFEntry, and the compiler correctness and constant-time theorems are statedonce for both
(AeneasFront/README.md;
three functions of Aeneas's test suite are compiled to x86 with both theorems).
BackendLoops.lean
relates hax's
fold_rangeand Aeneas'sloopover a range. No function has yet been extracted both ways,and no theorem equates two extractions; the operation table, the loop lemma and the reading theorems
above are what that theorem would compose, so cross-checking is of interest to us. For shared targets
we would take protocol code above the arithmetic layer, which is where our compiler works (its kernels
are linked code); we can propose a list.
Iterator adapters, signed scalars and structures in the Aeneas front are in commits not yet published.
4. Anything in the way. Only the namespace clash, which the rename above removes. The pins agree
(Lean and Mathlib v4.35.0). Interop being unstable suits us. One question back: would
Interop/take thesignature-plus-handler form for its run lemmas, so that the lemmas of
Run.leanbecome equations of onehandler? Then the two sides can share the lemmas proved against the signature.
dtumad commentedon Nov 13, 2026
Thanks for the detailed answers. The rename settles the clash on both sides, and reading both
RustMs as the free monad overC Error + 1gives the isomorphism a clean reason.On your question: yes,
Interop/should take the signature-plus-handler form. The plan is a follow-upInterop/PR, after #1088:RustOracleCompas one handler;liftRustMas the reading of Aeneas'sRustMinto that free monad, followed by the fold;Run.leanas the handler's equations.Then the assumption that
failis Aeneas's only event lives in that one reading. That is also the direction forholds_iff_of_triple, which you raised on #1088.Your
Signature.leanalready has this shape. Would you rather contribute it toInterop/directly, or have us port it with credit?On cross-checking: a list of protocol-level shared targets would be welcome when you have one.
spitters commentedon Nov 14, 2026
Thanks. We will contribute it directly: a PR against
Interop/once #1088 is merged, with the signaturerustSig, Rust programs as its free monad,RustOracleCompand the failure-onlyOptionT (OracleComp spec)as handlers, and the embedding ofAeneas.Std.ErrorintoError. YourliftRustMand the restatedRun.leanlemmas can then go on top of it in the same PR or in yours, whichever you prefer.Shared targets for cross-checking. These are Rust functions above the arithmetic layer, where both extractions should succeed and where both libraries have a security statement to connect them to:
encapsulateanddecapsulateover the CPA scheme, with the implicit-rejection branch), with the CPA operations as opaque calls; on your sideCryptoFoundations/FujisakiOkamotoandLatticeCrypto/MLKEM/Security.lean.Examples/Schnorrand the Fiat–Shamir transforms.For each we would extract the function both ways, relate the two Lean terms through the operation table and the loop lemma, and state the equality of the two extractions as one theorem per function.
dtumad commentedon Nov 16, 2026
Thanks, that's the best route. We'll put
liftRustMand the restatedRun.leanlemmas in a follow-up PR on top of yours. That keeps your PR to the signature and its handlers, and keeps the changes to existingInterop/Rustproofs, such asholds_iff_of_triple, in a PR that can be reviewed on its own.Both targets look right to us: each sits above the arithmetic layer, and each connects to a security statement on our side. Which Rust sources do you have in mind for them? Neither has a crate under
Interop/Hax/yet.spitters commentedon Nov 16, 2026
The two crates are now in CatCrypt-core/rust, each with its hax extraction and a Lean bridge to our security theorems:
schnorr-hax:keygen,signandverify, generic over a traitSchnorrCryptowith the scalar and group operations, the generator and the challenge hash. The tests instantiate the trait with secp256k1 and the BIP-340 hashes and reproduce the BIP-340 signature vectors.Schnorr/SurfaceDeps.leaninterprets the trait through a group and shows that the EUF-CMA game in the ROM, run on the extracted functions, is the game of our Schnorr proof, so its discrete-log bound holds for them (schnorr_extracted_rom_eufcma).mlkem-fo-hax: the Fujisaki–Okamoto layer of ML-KEM-768 (FIPS 203, Algorithms 16–18), generic over a traitFoOpswith K-PKE's three operations, H, G, J and the ciphertext comparison, so K-PKE and the hashes are opaque calls. The tests instantiate the trait with a FIPS 203 K-PKE and SHA-3, reproduce the NIST known-answer vectors, and agree byte for byte with libcrux-ml-kem 0.0.10 on random inputs.KEM/MlkemFo/SurfaceDeps.leanshows that, when the trait's operations implement a PKE schemePon encodings, the extracted functions compute the FIPS 203 transform ofPwith two random oracles, and its IND-CCA bound holds for the KEM built from them (extFO_indcca).Both are in the subset our hax-lean pipeline extracts; whether Charon and Aeneas take them unchanged is the first thing to check on your side. The FO layer of libcrux-ml-kem (
ind_cca.rs), with its CPA scheme opaque, would be the deployed form of the second target after these.dtumad commentedon Nov 21, 2026
Thanks, both crates look like good targets. We'll start by running Charon and Aeneas on
schnorr-haxandmlkem-fo-haxas they are, and report what needs changing; libcrux'sind_cca.rscan follow once the FO crate goes through.#1088 has merged, so your
rustSigPR againstInterop/can go ahead whenever it suits you. #1178 (open) touches the sameRustOracleCompcontracts andSpec.liftRustM, so whichever lands second will rebase onto the other, and ourliftRustMfollow-up then goes on top of both.dtumad commentedon Nov 21, 2026
#1209 reorganizes
Interop/into sub-projects, one Lake package each, grouped by trusted base rather than by kind of content. Today'sRust/,Aeneas/andHax/directories becomeInterop/Aeneas: everything whose Lean code comes through Charon and Aeneas, including the crates extracted with the hax 0.5 CLI. The lift and theStd.WPtriples are unchanged; only the module paths move (Interop.Aeneas.Lift.*,Interop.Aeneas.Hax.*).Each sub-project requires VCVio by path and only its own tools, and its README states its trusted base, its assumptions and the implementations it covers. A hax-lean sub-project could sit beside
Interop/Aeneasas its own package. Since the two never share a Lake project, that also sidesteps theAeneas.Stdname clash.For your
rustSigPR: if it lands before #1209, we'll carry it across; after #1209, it targetsInterop/Aeneas/.