# LeanDY: Type-Based and Trace-Based Symbolic Protocol Verification in Lean

Crypto.world

> Existing symbolic verification splits into two camps: fully automated trace-based tools (ProVerif, Tamarin) that are hard to apply to stateful, unbounded, cross-layer protocols, and type-based or…

**arXiv**: 2607.03406

**Published**: 2026-07-03

**Authors**: Simon Jeanteur, Lorenzo Veronese, Magdalena Solitro, Matteo Maffei

## AI summary

LeanDY: Type-Based and Trace-Based Symbolic Protocol Verification in Lean

## Overview

**Research area:** Cryptography and Security — symbolic (Dolev–Yao) formal verification of cryptographic protocols, with a focus on blockchain and layer-2 protocols, mechanized in the Lean proof assistant.

**Technical level:** Advanced. The paper assumes familiarity with symbolic protocol verification, refinement/security type systems, trace invariants, and interactive theorem proving.

**Scope (one sentence):** The paper presents LeanDY, a Lean library that unifies compositional type-based reasoning with trace-based inductive reasoning to verify stateful, unbounded protocols, including support for XOR-based conditional secrecy, and demonstrates it on a SegWit-style blockchain model and payment channels.

## What This Paper Is About

Existing symbolic verification splits into two camps: fully automated trace-based tools (ProVerif, Tamarin) that are hard to apply to stateful, unbounded, cross-layer protocols, and type-based or interactive approaches (such as DY* in F*) that are modular but require substantial manual proof effort. LeanDY bridges these by letting type-based proofs be complemented with trace-level inductive reasoning inside Lean, so protocol-specific automation can be extended with interactive proofs when needed. The goal is a single mechanized framework that handles mutable state, dynamic compromise, XOR, and conditional secrecy — secrets that stay private only until a protocol condition (an event) is reached.

## Key Contributions

1. **LeanDY, a Lean library for protocol verification** supporting dynamic compromise, mutable state, conditional secrecy properties, and XOR. It combines a high degree of automation from the type-based approach with the ability to fall back to interactive trace-based proofs.
2. **A type-based treatment of conditional secrecy for XOR-based protocols**, integrated into LeanDY, including chained release patterns where one released secret unlocks the next.
3. **A mechanized model of SegWit-style blockchain primitives** in LeanDY, covering Bitcoin-like transaction structure, witness-based scripts, and timelocks.
4. **An in-depth formalization of payment channels** built on that blockchain model, verifying punishment mechanisms and properties that depend on chain liveness.

The authors state the complete library, blockchain primitives, payment-channel formalization, and additional example protocols are available online (Jeanteur et al., 2026).

## Main Findings

- **Two verification styles coexist in one framework:** Type-based reasoning is used per message exchange, while trace-based reasoning (a global trace invariant, `valid_trace`) covers goals the type system cannot express, such as cross-layer reasoning, liveness, and punishment arguments.
- **Labels are generalized into trace properties:** Unlike the original DY* labels, LeanDY encodes a label as a structure with a `corrupt₀` predicate over traces plus a proof of monotonicity. This allows arbitrary, protocol-specific labels to be defined without modifying the base library, and enables conditional secrecy and temporal relationships between events.
- **Conditional swap labels are definable:** The `releasable` label swaps one label for another once a trace event `e` has occurred, formalizing the paper's notation `[L₁/L₂]_E`. Events are assumed irreversible, so swaps are permanent.
- **XOR labels are derived automatically:** Once a small set of protocol terms is annotated, LeanDY derives labels for algebraically related XOR expressions using the meet of operand labels; the label condition becomes the conjunction of the operand conditions (e.g., `rk_alice = T₂ ⊕ T₃` gets the conjunction of `Close_B`, `Close_C`, and `Close_D`).
- **A security lattice is established:** Lifting the information-flow preorder `≤_tr` to equivalence classes of labels (`𝔩_tr`) yields a complete lattice (Property 1), with `Pub` as top, `Sec` as bottom, and `meet`/`join` as the lattice operations.
- **Quotienting removes equational-theory busywork:** Symbolic bytes are exposed as equivalence classes of byte strings with the same normal form under the normalization function `γ`, so users reason with ordinary equality on the quotient type `𝔹` instead of manually applying constructor/destructor reduction rules.
- **Worked correspondence-assertion proof:** For the conditional-release example with two intermediaries, the paper proves the atomicity-style property `End ⟹ Close_B ∧ Close_C ∧ Close_D` by analyzing each participant in isolation under the invariant that everything sent on the network has label `Pub`.
- **Compromise is handled compositionally:** Replacing `Sec` with `Priv^n` labels and combining them with meet captures chains of compromise, and the security goal is restated so each event is either triggered or the corresponding principal is compromised.
- **Not reported:** The paper contains no quantitative evaluation — no benchmark suite, dataset size, proof-engineering statistics, line counts, or timing measurements appear in the provided content.

## Methodology in Plain English

The authors follow the "language and automation co-design" (LAC) principle: build a specialized language plus automation for the common case, and leave controlled escape hatches for everything else.

Concretely, a protocol is modeled as a state machine whose actions are recorded on a global, append-only trace. Trace entries are sent messages, principal compromises (which can occur at any time), serialized protocol states, and protocol-specific events. Security is proved by establishing a trace invariant: every possible state transition — including those made by a Dolev–Yao adversary — is shown to preserve it, so every reachable state satisfies it.

The heavy lifting is delegated to a type system. Every message put on the network must be typed as public and well-formed, so a secret can never be leaked by a well-typed program. For each message received, the label of the received value tells the prover which events must already have happened — because a conditionally secret value only became public after its condition event fired. Chaining these local, per-participant arguments yields a global ordering of events, which is exactly what a correspondence assertion (e.g., "if `End` happened, then `Close_B`, `Close_C`, `Close_D` happened") requires.

Protocols are written in an embedded domain-specific language in Lean. Users instantiate the protocol-specific parts of the invariant (states, events, validity predicates), prove each exchange valid with semi-automated support, and finally prove extrinsically that the invariant implies the intended security property. When automation stalls, the user drops into Lean's interactive mode. Finally, the authors apply the framework to a SegWit-style blockchain model and then build payment channels on top of it, checking punishment and liveness-dependent properties.

## Why This Matters

For research, LeanDY shows that the type-based and trace-based traditions can be reconciled in one mechanized artifact rather than treated as disjoint toolchains, and it is described as the first single mechanized framework to combine XOR support (previously handled in Horn-clause approaches) with conditional secrecy (previously studied in refinement-type systems). It also provides a mechanized model of Bitcoin-style transactions with a non-trivial layer-2 case study, addressing an area the paper notes has seen fewer machine-aided verification efforts than its importance warrants.

Real-world applications:

- **Payment-channel and layer-2 protocols:** the paper verifies punishment mechanisms and liveness-dependent properties on a payment-channel model, relevant to Lightning-style networks, which the paper says remain only partially verified.
- **Conditional-release and atomic-swap constructions:** the running example abstracts the conditional release chains used in payment-channel networks, atomic swaps with lock contracts, and the Tor network.
- **Multi-hop and cross-layer protocols:** the compositional style targets protocols spanning application-level and consensus-level specifications.
- **Protocols with algebraic primitives (XOR):** the label derivation avoids manual case analysis for XOR-heavy designs, which the paper notes are notoriously difficult symbolically.

Industry relevance: teams that need formal guarantees for blockchain, custody, or messaging protocols can keep high automation for routine properties and reserve interactive proof for the hard cross-layer and liveness arguments, rather than choosing between a limited automated tool and a full manual proof effort.

## Future Directions

- **Reducing manual intervention:** the paper identifies manual proof steps as the main limitation of advanced type-based approaches; a natural next step is extending the protocol-specific automation so fewer goals require interactive Lean proofs.
- **Scaling to fuller protocol formalizations:** the paper notes that full verification of the Lightning Network remains open, with prior work either bounded (Grundmann and Hartenstein, 2026) or based on a simplified abstraction (Fabiański et al., 2026).
- **Broadening the cryptographic and algebraic coverage:** beyond the primitives and XOR equational theory currently modeled, further primitives and richer equational theories would extend the class of verifiable protocols.
- **Evaluating the framework itself:** the provided content reports no user study, proof-effort metrics, or benchmark comparisons, so measuring automation coverage and proof size against DY* and against ProVerif/Tamarin on shared case studies is an obvious opening.

## Target Audience

Researchers and advanced practitioners in formal methods and security who work on symbolic protocol verification, proof-assistant-based verification (Lean, F*), or mechanized blockchain protocol analysis. It is most useful to readers already comfortable with Dolev–Yao attacker models and security type systems; newcomers will find the introduction and the conditional-release example accessible, but the library internals and typing rules require a stronger background.

## Authors’ abstract

Computer-aided formal verification is a widely used approach for the symbolic analysis of cryptographic protocols. However, many modern protocols rely on features that remain challenging for existing techniques. In particular, reasoning about state, time-dependent behavior, inductively defined data structures, unbounded executions, and conditional secrecy requires a level of expressiveness that is difficult to reconcile with effective automation. As a result, protocol…

[The full abstract on arXiv](https://arxiv.org/abs/2607.03406)

[Read the original paper](https://arxiv.org/abs/2607.03406)

---

Canonical: https://crypto.world/paper/leandy-type-based-and-trace-based-symbolic-protocol-verification-in-lean-2607.03406
