# Your Code Has Bugs. Lean4 Has Proofs: Formal Verification for Engineers — Varun Pant, AWS

Varun Pant, AWS

AI Engineer World's Fair 2026

[Talk page](https://ai.engineer/talks/lRa9sPaMyy4-your-code-has-bugs-lean4-has-proofs) · [Video](https://www.youtube.com/watch?v=lRa9sPaMyy4)

## Your Code Has Bugs. Lean4 Has Proofs: Formal Verification for Engineers

Varun Pant explains how specifications, machine-generated proofs, and small independent checkers fit together—and how verification changes when production code lives in Rust rather than Lean.

### Define correctness before asking a machine to prove it

[0:12](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=12s)

Coding agents can produce hundreds or thousands of pull requests a week. Checking that output creates a different bottleneck: an LLM judge gives a probabilistic assessment, tests exercise selected inputs, and human review struggles to keep pace. Varun Pant, who builds AI products and leads formal-verification teams at AWS, introduces formal verification as a way to prove that an implementation satisfies a specified property across every input covered by that property. [0:12](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=12s)

The first engineering task is to write what “correct” means. In the spec-driven workflow Pant introduces with Kiro, a human can write a formal specification directly in **Lean** or write natural-language requirements that an AI formalizes. The specification then needs validation: someone reviews it, or tests whether it describes the expected behavior on concrete inputs. A proof establishes agreement with the specification; a mistaken specification can therefore produce a proved implementation of the wrong requirement.

That order matters because the specification sits upstream of both implementation and verification. It remains a “living, breathing artifact” that the builder works with as requirements develop. Once its meaning is settled, the coding agent implements it and the verification tool proves the implementation matches it. Pant’s division of labor is compact: “humans own the specification, and machines own the code and proof.”

### One language holds the function and its theorem

[2:11](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=131s)

Lean is both a programming language and a proof assistant. Definitions and proofs use the same language, so a Lean implementation does not need a separate translation into a proof language. Pant also emphasizes extensibility—Lean is implemented in Lean—and a small trusted kernel that checks proofs. Proofs can be exported for independent checking.

List reversal supplies the first concrete example. Reversing `[1, 2, 3]` produces `[3, 2, 1]`. The accompanying theorem describes how reversal interacts with concatenation: reversing `A` followed by `B` gives the reverse of `B` followed by the reverse of `A`. Here, the talk’s “plus” means joining lists, rather than adding their elements.

To see the change, split that same list into `A = [1, 2]` and `B = [3]`. Concatenation places the `A` block before the `B` block. Reversing the combined list moves the `B` block to the front and reverses the order inside `A`, yielding `[3, 2, 1]`. Reversing the blocks separately and joining them in the opposite order produces the same result: `[3] ++ [2, 1]`. This instance makes the property visible; the theorem expresses it for every pair of lists, rather than only these three elements.

Tactics construct the proof, and the kernel checks it. This separation provides a way to accept machine-generated proofs: the machine searches for an argument, while a much smaller component checks whether that argument establishes the theorem.

### Search like chess, then check the result independently

[3:16](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=196s)

Pant’s analogy is chess. The theorem is the goal, like checkmate; tactics are the moves used to reach it. Proof construction is interactive and branches into a search tree. A tactic may advance the proof, but a branch can also leave a goal unresolved. The prover then backtracks and tries another route. A plausible sequence of moves alone does not finish the job: the resulting proof must pass the kernel.

The kernel rejects an incorrect proof in Pant’s example. Confidence in the generator therefore does not substitute for checking its output. Pant describes open-source kernel implementations in C++, Rust, and Lean, and the possibility of writing an independent checker yourself. The trusted component remains the checker, even when proof search becomes large or complicated. [4:03](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=243s)

### A compression round trip becomes 32,000 lines of proof

[4:30](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=270s)

The next example puts both specification and implementation in Lean. Pant describes an open-source project in which AI converted zlib, the C compression library, to Lean over about a week. Its natural-language requirement is easy to understand: decompressing compressed data should return the original data. Written as an intended property, the round trip is `decompress(compress(data)) = data`. The [Lean theorem in Leo de Moura’s separate May 6, 2026 NFM presentation](https://leodemoura.github.io/static/nfm2026/) proves that round trip across compression levels for inputs satisfying `data.size < 1024 * 1024 * 1024`: strictly below 1 GiB. The proved claim therefore includes an input-size precondition that the plain-language requirement leaves unstated. [4:41](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=281s)

The AI first turns that requirement into a formal specification. After the specification is checked, it writes the Lean code and breaks the proof into helper lemmas—smaller claims that serve as subgoals. Tactics prove those claims, the claims assemble into the final theorem, and the independent kernel checks the result. Pant reports 32,000 lines of proof for this example. That quantity describes the proof artifact, rather than a count of test cases.

How does one readable requirement lead to such a large proof? The flow below separates the initial decision about meaning from the generated implementation and proof. Specification validation comes first. The AI then expands the problem into code and lemmas, and the kernel checks the assembled argument. The checker’s position at the end explains why validating the requirement cannot be delegated to proof checking.

From round-trip requirement to checked theorem
Validation precedes implementation. Helper lemmas divide the proof into manageable claims; the kernel checks their assembled result. The theorem in Leo de Moura’s separate NFM presentation, rather than one shown in Pant’s recording, covers inputs strictly below 1 GiB across compression levels.
- Round-trip requirement — Decompressing compressed data returns the original data.
- Formal specification — AI formalizes the requirement; a human reviews it or tests its meaning on inputs.
- Lean implementation — AI writes code after specification validation.
- Helper lemmas — AI decomposes the proof into subgoals and proves them with tactics.
- Final theorem — The proved lemmas assemble into the complete argument.
- Independent kernel — Checks the completed proof.
- Round-trip requirement → Formal specification (Formalize)
- Formal specification → Lean implementation (Implement after validation)
- Lean implementation → Helper lemmas (Generate proof subgoals)
- Helper lemmas → Final theorem (Assemble)
- Final theorem → Independent kernel (Check)

### Cedar connects Lean semantics to production Rust

[5:58](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=358s)

Production code can stay in Rust while Lean supplies its functional specification. Cedar, an open-source authorization policy language, illustrates this arrangement: its specification is written in Lean and its production implementation runs in Rust. The critical example is “forbid trumps permit.” Whenever a forbid policy is satisfied, the request must be denied, even when permission would otherwise be available. [5:58](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=358s)

The connection between the two implementations uses differential random testing. Each generated input goes to both the Rust production code and the Lean model, and their outputs are compared. Pant reports about 100 million such tests nightly and says no version ships until the agreement requirement is satisfied. This checks the Rust implementation against the formal model on sampled inputs; it does not establish a deductive proof that the Rust code agrees with the model for every input.

The practical choice is to keep a shipping implementation in Rust and use a Lean model as the reference for its behavior. For the forbid example, agreement means both paths return denial for the same request and policies. A difference exposes a disagreement that must be resolved before release. The model gives testing a precise expected result, rather than requiring each test author to invent one.

### Two routes from Rust to deductive verification

[6:59](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=419s)

Deductive verification offers another way to work with Rust. Before introducing the tools, Pant distinguishes a solver from Lean’s interactive proof search. Lean resembles a chessboard on which tactics advance a goal. A solver resembles a powerful calculator: it receives a formula and answers whether that formula is satisfiable or unsatisfiable—whether its constraints can hold together. [6:59](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=419s)

- **Verus: specifications alongside code.** Verus uses Z3 to verify Rust code with annotations expressing preconditions and postconditions. A precondition states what must hold before the operation; a postcondition states what must hold afterward. These specifications are checked statically by the verifier and erased at runtime, so they do not become runtime assertions.

- **Aeneas: translate Rust into Lean.** Aeneas starts from Rust’s mid-level intermediate representation and translates it into a functional form in Lean. The translated program can then use the theorem-proving approach introduced earlier: goals, tactics, and checked proofs.

These paths place the specification in different working environments. Verus keeps it close to the Rust code and uses a solver; Aeneas brings a functional translation into Lean for theorem proving. Both differ from Cedar’s differential-testing arrangement, where the production program and model are run on matching inputs and their outputs compared.

### Lower different languages into a shared verification core

[8:26](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=506s)

The final technical proposal extends the compiler idea beyond Rust. Pant describes [Strata](https://raw.githubusercontent.com/strata-org/Strata/main/README.md), an open-source AWS tool. A language-specific dialect represents a program at a high level, then lowers it into Strata Core, a common low-level representation written in Lean. The intended architecture lets that representation feed different verification engines: Lean proofs, SMT solvers, or model checkers. The [architecture documentation](https://raw.githubusercontent.com/strata-org/Strata/main/docs/Architecture.md) describes the implemented analysis as a verification-condition generator with an SMT interface; broader Lean reasoning and other engine integrations remain architectural goals. Support for arbitrary languages is likewise the intention of this work in progress, rather than a claim that every language is already supported. [8:26](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=506s)

What does a shared core buy? The diagram shows where language-specific work ends and analysis begins, distinguishing the implemented SMT route from proposed engine choices. Each language needs a dialect and lowering path, but the resulting program reaches the same core. That common representation allows an analysis to be reused across languages, with additional engines intended to extend the choice of verification method.

The closing recommendation starts smaller than that infrastructure: pick your most critical code and write what correct means. Pant points to using Lean in a browser, then having a coding agent implement the specification and a verification tool prove the result. A useful first target is a property whose meaning you can inspect and care about—a compression round trip or a denial rule—before asking a machine to expand it into a proof. That is the route toward the ending’s ambition of software that is “provably correct.” [9:17](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=557s)

A shared core supports reusable analysis
Language-specific translation precedes Strata Core. The documented implementation generates verification conditions and interfaces with SMT solvers; broader Lean reasoning and model-checker routes are architectural goals.
- Language-specific dialect — Represents a source program in a high-level intermediate form.
- Strata Core — Common low-level program representation written in Lean; implemented analysis generates verification conditions.
- Lean reasoning — goal — Broader theorem-proving support is a long-term architectural goal.
- SMT interface — implemented — Verification conditions are encoded for SMT solvers.
- Model checkers — goal — An intended external-engine integration.
- Language-specific dialect → Strata Core (Lower)
- Strata Core → Lean reasoning — goal (Architectural goal)
- Strata Core → SMT interface — implemented (Generate conditions and encode for SMT)
- Strata Core → Model checkers — goal (Architectural goal)

## Key takeaways

- A proof establishes that code satisfies its specification. Validate what the specification means before generating implementation and proof.
- Tactics construct proofs through search and backtracking; a small independent kernel checks the completed argument.
- Cedar compares production Rust with a Lean model using about 100 million differential random tests nightly. Verus and Aeneas provide different routes toward deductive verification of Rust.
- Start with critical code and a concrete property you can explain, then let the agent implement it and the verification tool prove it.

## Resources

- [Strata setup and verification guide](https://raw.githubusercontent.com/strata-org/Strata/main/README.md) — The project README provides prerequisites, build commands, and an example verification invocation for experimenting with Strata. This is a practical next step for the shared-core proposal, separate from the talk’s invitation to try Lean in a browser.
- [Strata Architecture](https://raw.githubusercontent.com/strata-org/Strata/main/docs/Architecture.md) — Explains dialect definitions, composition, transformations, and Strata Core. It distinguishes the broader engine architecture from the implemented verification-condition generator and SMT interface.

## Related talks

- [Spec-Driven Development: Agentic Coding at FAANG Scale and Quality — Al Harris, Amazon Kiro](https://ai.engineer/talks/HY_JyxAZsiE-spec-driven-development-agentic-coding-at-faang) — A companion on the specification-driven development workflow Pant introduces before adding formal proof.
- [Fuzzing in the GenAI Era](https://ai.engineer/talks/OMGPvW8TBHc-fuzzing-in-genai-era) — A related testing topic to explore alongside Cedar’s randomized comparisons between implementation and model.

## Slides

### The problem

LLM judging is probabilistic, tests cover only some inputs, and human review struggles to match agent speed. None establishes correctness for all inputs.

[0:12](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=12s) [Slide lists limitations of LLM judging, tests, and human review for proving code correct for all inputs.](https://assets.ai.engineer/sites/aiecode2025/sha256/82ad3171c18681d56195281234b079e6d946c7b65f23e613bd9ff3361cf55c21.webp)

The problem

Coding agents are generating more code than ever. How do you know it's correct?

LLM-as-judge? Probabilistic.
Tests? Only checks some inputs, not all.
Human code review? Doesn't scale to match agent speed.

None can say: "for ALL inputs, this is correct."

AWS Builder Center

### The problem

As coding agents produce more code, LLM judgments are probabilistic, tests cover selected inputs, and human review struggles to keep pace. Formal verification can prove code meets a specification for all inputs.

[0:36](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=36s) [Slide contrasts code review methods with formal verification for proving correctness.](https://assets.ai.engineer/sites/aiecode2025/sha256/2837b382e0e13396d67b59b204ef4108e62bf8fabfa497c855252bab97b089c7.webp)

The problem

Coding agents are generating more code than ever. How do you know it's correct?

LLM-as-judge? Probabilistic.
Tests? Only checks some inputs, not all.
Human code review? Doesn't scale to match agent speed.

None can say: "for ALL inputs, this is correct."
Formal verification can.

AWS Builder Center

### Formal verification

A developer defines correctness in a specification; a verification tool then proves that the code satisfies it for every possible input.

[0:49](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=49s) [Slide explains that a tool proves code satisfies a specification, alongside logos of verification tools.](https://assets.ai.engineer/sites/aiecode2025/sha256/4e9fb96e1b83da748b0d823facec76b7fd9d727b1e8cdfc2cd935c0a4fc5895c.webp)

Formal verification

Mathematical proof that code is correct — for ALL inputs.

You write WHAT correct means (the spec).
A tool proves your code satisfies it.

If the proof passes → it holds for every possible input.

Z3
CVC5
LEAN THEOREM PROVER
Dafny

AWS Builder Center

### How do you use formal verification?

Humans write and validate a specification. An AI coding agent implements it, and a verification tool proves the implementation matches the spec.

[2:02](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=122s) [Slide lists four steps from writing and validating a specification to proving an implementation matches it.](https://assets.ai.engineer/sites/aiecode2025/sha256/98a7ee9c1c5fa57fe9c9816bcafdb85fe2b0e828488ecac0165d7eab5bf054bc.webp)

How do you use formal verification?

Spec-driven development (e.g. with Kiro):

1. Write a SPEC — what "correct" means (write it formally, or describe intent and let AI autoformalize)
2. Validate the spec (human reviews it + test it holds on inputs)
3. AI coding agent implements from the specification
4. PROVE implementation matches spec

Humans own the spec. Machines own the code and proof.

AWS Builder Center

### What is Lean?

Lean uses one language for definitions and proofs, with no translation layer. It is implemented in Lean and has a small trusted kernel; proofs can be exported for independent checking.

[2:12](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=132s) [Slide describes Lean as a programming language and proof assistant with a small trusted kernel.](https://assets.ai.engineer/sites/aiecode2025/sha256/ef4785984d1bd527363ed2c4d48d9cdac5d476961dc851b1ae34ff62a492c885.webp)

What is Lean?

LEAN

A programming language and a proof assistant.

• Same language for definitions and proofs. No translation layer.
• Lean is implemented in Lean. Very extensible.
• Small trusted kernel. Proofs can be exported and independently checked.

AWS Builder Center

### Code and proof in the same language

A Lean file defines list reversal and proves that reversing appended lists yields the reverse of each list in opposite order. Tactics do the proof work; the kernel checks it.

[2:31](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=151s) [Lean code reverses a list and proves a property of reversing appended lists.](https://assets.ai.engineer/sites/aiecode2025/sha256/88107f3a0adc1fe5a998ec4776347105e1fc5cb4c79f7d78bd15fa6b769cd6ed.webp)

Code and proof in the same language

def reverse : List α → List α
  | [] => []
  | x :: xs => reverse xs ++ [x]

Code!

theorem reverse_append (xs ys : List α)
    : reverse (xs ++ ys) = reverse ys ++ reverse xs := by
  induction xs with
  | nil => simp [reverse]
  | cons x xs ih => simp [reverse, ih]

Proof!

#eval reverse [1, 2, 3]
[3, 2, 1]

All goals completed! 🐙

Here's a function that reverses a list in Lean. reverse [1,2,3] gives [3,2,1]

Using the theorem prover, we proved a property: reverse(A + B) = reverse(B) + reverse(A) — holds for every possible list.

Tactics do the work, kernel checks

AWS Builder Center

### Lean proof assistant

Like chess moves, tactics explore branches toward a goal. In the diagram, an LLM tries three tactics; omega proves the goal, and the kernel checks the result.

[3:27](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=207s) [A chessboard accompanies a diagram of an LLM trying tactics, proving a goal, and having the kernel confirm it.](https://assets.ai.engineer/sites/aiecode2025/sha256/2199b0bcbb972ce761c7756bd7e42091802a56eed7e38ec2deb9a10139b86cbf.webp)

Lean proof assistant

LLM

tactic (simp) X
tactic (omega)
tactic (rw) X

Goal proved ✓
Kernel confirms ✓

AWS Builder Center

### The kernel catches mistakes

A false claim that reversing [1, 2, 3] leaves it unchanged produces an unsolved goal. Lean’s small kernel checks proofs; the slide also lists independent kernels in C++, Rust and Lean.

[4:01](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=241s) [A false list-reversal claim produces an unsolved goal, alongside notes about the kernel and a checker comparison.](https://assets.ai.engineer/sites/aiecode2025/sha256/f8393e4416126e83cc76bc46f7f75ba32073b7503d81cb026125392356a79d02.webp)

The kernel catches mistakes

example : reverse [1, 2, 3] = [1, 2, 3] := by simp [reverse]
unsolved goals
⊢ False

• Incorrect proofs are rejected immediately.
• You only need to trust the small kernel.
• Multiple independent kernels: C++, Rust, Lean (https://arena.lean-lang.org/).

Checkers
Checker | Version | [illegible] | [illegible] | [illegible] | [illegible] | [illegible]
nanoda | master ([illegible]) | 100/100 | 43/43 | 9 | 23.4m | 7.9 GB
nanobruijn | master ([illegible]) | 102/102 | 50/50 | 0 | 27.7m | 5.5 GB
official-nightly | 2026-04-11 | 102/102 | 50/50 | 0 | 31.9m | 9.2 GB
official | 4.29.0 | 102/102 | 49/49 | 1 | 32.8m | 9.1 GB
official-v4.28.0 | 4.28.0 | 102/102 | 49/49 | 1 | 42.0m | 9.3 GB
mini | master ([illegible]) | 94/94 | 50/50 | 8 | - | -

AWS Builder Center

### Example 1: Spec and code in Lean

The first example puts both the specification and the code in Lean.

[4:28](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=268s) [Section title: Example 1: Spec and code in Lean.](https://assets.ai.engineer/sites/aiecode2025/sha256/b138de7b32ea76a55bc6ef2f1876917279fb512bf179486812ad57d854079a1a.webp)

Example 1: Spec and code in Lean

AWS Builder Center

### AI converted zlib to Lean

Pant presents the open-source lean-zip repository as an AI conversion of the C compression library zlib to Lean. He says the conversion took about a week.

[4:39](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=279s) [A repository screenshot accompanies the claim that AI converted the zlib C compression library to Lean.](https://assets.ai.engineer/sites/aiecode2025/sha256/13208fa03c0790da4b118e6706faaa4ad704e63274bf0e477d1ec815f33a3a57.webp)

AI converted zlib (a C compression library) to Lean

AWS Builder Center

Interface text:
kim-em / lean-zip  Public
Notifications  Fork 9  Star 91
Code  Issues 63  Pull requests 16  Actions  Projects  Security and quality  Insights
master  834 Branches  10 Tags  Go to file  Code
kim-em  feat: edits to README  [illegible]  8 hours ago  1,464 Commits
.claude  bench: sweep libdeflate over levels 1-12 (#2713)  last week
.github/workflows  Fix: master CI failing on lake exe test (Lean 4.29.1 regressi...  2 months ago
.pod  chore: ignore pod runtime caches; untrack accidentally co...  3 weeks ago
Zip  perf(matcher): use the updateHashesFast hot writes (~2...  5 days ago
ZipTest  refactor(wide): drop unused ugetUInt64LE reader (#2712)  last week
bench  perf(matcher): use the updateHashesFast hot writes (~2...  5 days ago
c  refactor(wide): drop unused ugetUInt64LE reader (#2712)  last week
plans  perf: pre-size packed-token array; retire UInt32-tables su...  2 weeks ago
progress  feat(decode): verified tree-free canonical Huffman decode...  last week
references  doc: restructure verification plan around roundtrip theorem  4 months ago
rust/miniz_oxide_shim  human-oversight: Track D Phase 0c — wire miniz_oxide vi...  2 months ago
scripts  Track E silent-skip family: tar-skipped-padded.tar fixture p...  last month
testdata  Track E silent-skip family: tar-skipped-padded.tar fixture p...  last month
.envrc  chore: add shell.nix and direnv support for NixOS builds  4 months ago
.gitattributes  feat: add comprehensive test suite, CI, Zstd/ZIP64/PAX su...  4 months ago

About
No description, website, or topics provided.
Readme
Apache-2.0 license
Activity
91 stars
1 watching
9 forks
Report repository
Releases
10 tags
Packages
No packages published
Contributors 2
kim-em Kim Morrison
claude Claude
Languages

### AI generated specifications

AI translates the compression round-trip requirement into a Lean equality with an output-size bound. The theorem ends in sorry, a proof placeholder; Pant stresses checking the specification.

[4:51](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=291s) [A natural-language compression round-trip specification alongside its AI-generated Lean formal specification.](https://assets.ai.engineer/sites/aiecode2025/sha256/c0498a1d2328530dc1e577fb5168f095da3718d0fb5520a59460acea11f479be.webp)

AI generated specifications

Natural Language Spec
"Decompressing the output of compress returns the original data, for every input and every compression level."

AI generated formal spec
theorem zlib_decompressSingle_compress
    (data : ByteArray) (level : UInt8) (maxOutputSize : Nat)
    (hsize : data.size ≤ maxOutputSize) :
    Zip.Native.ZlibDecode.decompressSingle
        (Zip.Native.ZlibEncode.compress data level) maxOutputSize
      = Except.ok data := by sorry

AWS Builder Center

### AI generated proofs

AI generated helper lemmas to prove the compression round-trip theorem. The slide shows a successful Lean build and identifies the proof as verified by the Lean kernel.

[5:18](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=318s) [Lean proof code and a successful build result, presented as verification by the Lean kernel.](https://assets.ai.engineer/sites/aiecode2025/sha256/7ef853bce9ec6f16edceda1ddde03a4f59183541aa28be992fcc12da0ca2b58d.webp)

AI generated proofs

AI generated helper lemmas → theorem proved

theorem zlib_decompressSingle_compress (data : ByteArray) (level : UInt8)
    (maxOutputSize : Nat) (hsize : data.size ≤ maxOutputSize) :
    ZlibDecode.decompressSingle (ZlibEncode.compress data level)
maxOutputSize = .ok data := by
  unfold ZlibDecode.decompressSingle
  rw [zlib_inflate_ok data level maxOutputSize hsize]
  have hsz := zlib_size_ge data level
  have htr := zlib_trailer_fits data level
  simp only [zlib_check, zlib_cm, zlib_win, zlib_fdict, zlib_adler,
if_true,
    bind, Except.bind, pure, Except.pure, beq_self_eq_true]
  have h1 : ¬ (2 + (Deflate.deflateRaw data level).size + 4 >
(ZlibEncode.compress data level).size) := by omega
  rw [if_neg h1, if_neg (by omega : ¬ (ZlibEncode.compress data level).size
< 6)]

Proof verified with Lean Kernel

$ lake build
Build completed successfully (73 jobs)

AWS Builder Center

### What you just saw

AI broke the problem into lemma subgoals, proved them with tactics, and assembled a theorem that the kernel checked. The example spans 1,100 theorems and ~32k lines of proof.

[5:32](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=332s) [Summary of AI-generated lemmas, tactics and theorem assembly, followed by kernel checking.](https://assets.ai.engineer/sites/aiecode2025/sha256/9547d964df453cda4d2772c1cc3f3ee225ebe1b5be0fe50cbde84eef9b2805a3.webp)

What you just saw

AI decomposed problem → lemmas
Proved each → tactics
Assembled → final theorem
Kernel checked → √

AI did the work. Kernel kept it honest.

(1,100 theorems across ~32k lines of proof!)

AWS Builder Center

### Example 2: Code in Rust, functional specification in Lean

Rust code can be paired with a functional specification or model written in Lean. Cedar is the example.

[5:56](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=356s) [Section title introducing Rust code with a functional specification in Lean.](https://assets.ai.engineer/sites/aiecode2025/sha256/c39822a9d67107f67f0ebf4d43cbec9e8932686bea11ae7e12367fbc5cb9771b.webp)

Example 2: Code in Rust, functional specification in Lean

AWS Builder Center

### Cedar: proved properties - verified authorization

Cedar’s Lean specification describes authorization properties: a satisfied forbid policy denies a request, while permission requires a satisfied permit policy. Its production code runs in Rust.

[6:05](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=365s) [Cedar authorization properties and verified components, with a screenshot of the Cedar website.](https://assets.ai.engineer/sites/aiecode2025/sha256/bd77f2cf9ed2a73c5e96f802616d8776f991d28ed6ca200fdbb52a2169e4c7e2.webp)

Cedar: proved properties - verified authorization

Cedar — open-source authorization policy language. Used by AWS Verified Permissions and AWS Verified Access.

Cedar spec: the model is written in Lean.

Three examples of verified components: evaluator, authorizer, validator.

• forbid_trumps_permit — if any forbid policy is satisfied, the request is denied.
• allowed_only_if_explicitly_permitted — a request is allowed only if at least one permit policy is satisfied.
• typecheck_is_sound — if the validator accepts a policy, evaluation produces a boolean.

FAST, SCALABLE ACCESS CONTROL

Cedar is a language for defining permissions as policies, which describe who should have access to what. It is also a specification for evaluating those policies. Use Cedar policies to control what each user of your application is permitted to do and what resources they may access.

Do the tutorial
Try it out in playground

May 10, 2023: Amazon Web Services announces the Open-Source release of the Cedar SDK. Learn more

AWS Builder Center

Interface text:
CEDAR
Overview
Learn
Policy playground
Integrations
Cedar SDK

### Example 3: Code in Rust, verify with Lean/solvers

The next example asks how to deductively verify Rust code using Lean or solvers.

[6:34](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=394s) [Section title introducing verification of Rust code with Lean or solvers.](https://assets.ai.engineer/sites/aiecode2025/sha256/76718d9d60730a7cd2038a2d59e7ef61b1bf3d2473a1dd7f67833b195bf71caf.webp)

Example 3: Code in Rust, verify with Lean/solvers

AWS Builder Center

### Verifying Rust: Verus and Z3

The example requires an index to be within the vector and ensures the updated element equals t. Verus checks these conditions statically and erases them at runtime.

[8:01](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=481s) [Verus code example highlights preconditions and postconditions, which are statically checked and erased at runtime.](https://assets.ai.engineer/sites/aiecode2025/sha256/6695ff44674e2456c8afafc7fde1fc54666f9a9136360c4d1c334bcd989942f6.webp)

Verifying Rust: Verus->Z3 Solver

Verus allows the programmer to add specifications:

fn vec_update_at_idx<T>(
    v: &mut Vec<T>,
    idx: usize,
    t: T
)
    requires
        idx < v.len(),
    ensures
        v[idx] == t,
{
    // ...
}

Static check, enforced by verifier
Erased at runtime

requires (precondition) = what must be true BEFORE
ensures (postcondition) = what must be true AFTER

AWS Builder Center

### Verifying Rust: Aeneas and Lean

Aeneas translates Rust’s mid-level intermediate representation into Lean, where the resulting program can be proved with a theorem prover.

[8:07](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=487s) [Pipeline from Rust through Charon and Aeneas to Lean and proof.](https://assets.ai.engineer/sites/aiecode2025/sha256/a1f4af053a5bf64477c5b3865783d4952e9b5fa1e8cfc7fe1f06cd70de6bdfb9.webp)

Verifying Rust: Aeneas → Lean

Rust → Charon (Mid-level IR) → Aeneas (functional translation) → Lean → Prove

AWS Builder Center

### Verifying programming languages with Strata

Strata is a work in progress that lowers language dialects to a common Core, then routes programs to SMT solvers, model checkers or Lean proofs.

[8:23](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=503s) [Work-in-progress Strata diagram connects language frontends through dialects and core to solvers, model checkers, and Lean proofs.](https://assets.ai.engineer/sites/aiecode2025/sha256/ba6b5c898e8d72da84937705def31c43fb176d23d135b72a744f8aceb739f77a.webp)

Verifying any programming language -> Strata (WIP!)

Frontends
Python
…
Java
Specifications
Rust

Strata Dialects
Python Dialect
Java Dialect
Laurel
Boole
Core
SMT
GOTO

Analyses
SMT Solvers
Model Checkers
Lean Proofs
…

translate
transform

https://github.com/strata-org/Strata
AWS Builder Center

### Get started

Open Lean in your browser, pick critical code, and specify what correctness means. Then have a coding agent implement it and a formal verification tool prove it.

[9:15](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=555s) [Lean browser link and three steps: choose critical code, specify correctness, and have a coding agent implement and prove it.](https://assets.ai.engineer/sites/aiecode2025/sha256/ec87996a5e7aafb00dca422514a8fa6111531cff96dbaaa7061780a8c2128fc4.webp)

Get started

Lean in browser: https://live.lean-lang.org/

1. Pick your most critical code
2. Write what "correct" means
3. Let your coding agent implement it and prove it

AWS Builder Center

## Full transcript

[0:01](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=1s) [music]

[0:12](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=12s) >> Coding agents are generating more code

[0:15](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=15s) than ever.

[0:16](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=16s) Builders are generating hundreds and

[0:18](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=18s) thousands of PRs every week.

[0:21](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=21s) How do you know that this is correct?

[0:24](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=24s) Using LM as a judge for the code? Well,

[0:26](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=26s) that's probabilistic.

[0:29](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=29s) Tests?

[0:30](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=30s) They only check some inputs, not all.

[0:33](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=33s) Human code review doesn't scale to match

[0:35](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=35s) agent speed.

[0:37](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=37s) None of these can say for all inputs the

[0:40](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=40s) code is correct.

[0:42](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=42s) Formal verification can.

[0:44](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=44s) Hi, I'm Varun Pant. I build AI products

[0:46](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=46s) at AWS leading teams at in formal

[0:49](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=49s) verification.

[0:51](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=51s) Formal verification provides

[0:53](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=53s) mathematical proof that code is correct.

[0:56](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=56s) For all inputs.

[0:57](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=57s) You write what correct means, which is

[0:59](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=59s) the specification, and a formal

[1:01](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=61s) verification tool proves that your code

[1:04](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=64s) satisfies it.

[1:05](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=65s) If the proof passes, it holds for every

[1:08](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=68s) possible input.

[1:11](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=71s) How do you use this?

[1:13](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=73s) Well, one way is back driven

[1:15](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=75s) development, for example, with Kiro.

[1:19](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=79s) You write what the specification is,

[1:21](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=81s) which is what correct means.

[1:23](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=83s) Either you write it formally, for

[1:25](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=85s) example, directly in Lean, or you write

[1:27](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=87s) it in natural language, and you let the

[1:29](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=89s) AI auto formalize it.

[1:32](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=92s) Now, this is really important. You then

[1:34](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=94s) validate the specification. So, either

[1:36](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=96s) the human reviews it, or you test that

[1:39](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=99s) it holds on some inputs. And this is

[1:41](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=101s) important because the specification is

[1:43](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=103s) upstream. It's a living, breathing

[1:45](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=105s) artifact that the builder interacts

[1:47](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=107s) with. You want this to be correct.

[1:49](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=109s) Everything else is downstream from this.

[1:52](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=112s) The AI coding agent then goes and

[1:54](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=114s) implements from the specification.

[1:57](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=117s) And the formal verification tool proves

[2:00](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=120s) that the implementation matches the

[2:01](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=121s) specification.

[2:04](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=124s) So, humans own the specification and

[2:06](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=126s) machines own the code and proof.

[2:10](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=130s) Lean is a programming language and a

[2:12](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=132s) proof assistant.

[2:14](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=134s) It is the same language for the

[2:16](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=136s) definitions and proofs. There's no

[2:18](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=138s) translation layer.

[2:20](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=140s) It is implemented in Lean, which means

[2:22](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=142s) it's very extensible. And this is

[2:24](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=144s) important. It has a small trusted

[2:26](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=146s) kernel.

[2:27](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=147s) Proofs can be exported and independently

[2:29](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=149s) checked.

[2:33](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=153s) So, here's an example of a Lean file

[2:36](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=156s) which has both the code and proof in the

[2:38](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=158s) same language. At the top, you'll see

[2:40](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=160s) the code, which is a function that

[2:42](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=162s) reverses a list in Lean. So, reverse of

[2:45](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=165s) one, two, and three gives three, two,

[2:46](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=166s) and one.

[2:47](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=167s) And right in the middle, you'll see a

[2:49](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=169s) theorem. This is the proof.

[2:52](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=172s) And this theorem prover approves a

[2:55](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=175s) property which says that reverse of A

[2:57](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=177s) plus B is in fact reverse of B plus

[2:59](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=179s) reverse of A.

[3:00](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=180s) And this holds for every possible input.

[3:04](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=184s) How do you do this? You have something

[3:06](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=186s) called as tactics which do the work,

[3:07](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=187s) which we'll get to in a second. And the

[3:09](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=189s) kernel, remember the small trusted

[3:11](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=191s) kernel?

[3:12](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=192s) That checks the work.

[3:16](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=196s) A good analogy to understand the Lean

[3:17](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=197s) proof assistant is that of chess. So, in

[3:20](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=200s) chess, your goal is to checkmate the

[3:22](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=202s) opponent. And you make a bunch of moves.

[3:24](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=204s) You move the knight, you move the

[3:26](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=206s) bishop.

[3:27](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=207s) Similarly, in Lean, you have a bunch of

[3:30](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=210s) tactics which are your moves. And it's

[3:33](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=213s) the same chess board. It's interactive.

[3:36](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=216s) You want to prove the goal, the theorem,

[3:38](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=218s) checkmate. And you're kind of going down

[3:41](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=221s) a tree. So, you're traversing the tree,

[3:43](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=223s) you're trying different tactics. Maybe

[3:45](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=225s) for some goals, you're not able to prove

[3:47](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=227s) it, so you backtrack and then you try

[3:49](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=229s) another a branch of the tree. Very

[3:51](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=231s) similar to chess.

[3:53](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=233s) And finally, you get a goal that

[3:55](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=235s) hopefully proves the theorem, and then

[3:57](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=237s) that small independent kernel confirms

[4:00](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=240s) and checks it.

[4:03](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=243s) The kernel catches the mistake. So,

[4:05](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=245s) here's an example at the top where an

[4:07](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=247s) incor- incorrect proof is rejected

[4:10](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=250s) immediately. And you only need to trust

[4:12](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=252s) the small kernel.

[4:14](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=254s) The good thing is that you can have

[4:16](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=256s) multiple independent kernels. You

[4:17](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=257s) yourself can actually go write one. It's

[4:19](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=259s) completely open source. You have kernels

[4:21](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=261s) in C++, Rust, Lean. That's uh a link to

[4:25](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=265s) the Arena Lang where you can go and add

[4:28](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=268s) a kernel.

[4:30](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=270s) So, let's look at some examples where

[4:32](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=272s) you can put this to practice. The first

[4:35](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=275s) one is having the specification and code

[4:38](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=278s) both being in Lean.

[4:41](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=281s) Now, this is open source Andreo. AI

[4:44](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=284s) converted zlib, which is a C compression

[4:46](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=286s) library, to Lean. Now, granted this

[4:48](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=288s) happened over a week or so.

[4:52](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=292s) But, kind of going back to our

[4:54](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=294s) specification methodology that we

[4:57](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=297s) mentioned where you had specification at

[4:58](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=298s) the top and then verification for the

[5:00](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=300s) code, we'll kind of see the same thing

[5:02](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=302s) here. So, the natural language

[5:04](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=304s) specification says that you decompress

[5:06](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=306s) the output

[5:08](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=308s) of compress returning the original data.

[5:11](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=311s) And then, you have an AI that generates

[5:13](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=313s) the formal spec. Now, remember this is

[5:15](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=315s) important. Checking the specification is

[5:17](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=317s) key.

[5:19](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=319s) After you do that, the AI goes and

[5:21](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=321s) writes your code in Lean, and then

[5:23](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=323s) generates these helper lemma subgoals,

[5:26](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=326s) and proves the theorem.

[5:28](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=328s) And at the bottom, you can see that it's

[5:30](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=330s) verified with that small independent

[5:32](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=332s) kernel.

[5:34](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=334s) So, what you just saw was that AI

[5:36](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=336s) decomposed the problem into lemmas,

[5:38](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=338s) which are subgoals. It proved each of

[5:40](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=340s) them using tactics. Remember the chess

[5:42](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=342s) moves that we were making?

[5:44](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=344s) And it assembled it into a final

[5:46](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=346s) theorem.

[5:47](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=347s) Checkmate.

[5:49](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=349s) And the kernel checked it.

[5:51](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=351s) And this particular example had 32,000

[5:54](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=354s) lines of proof. So, it was

[5:55](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=355s) pretty big.

[5:58](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=358s) Let's take another example. What if you

[6:00](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=360s) have code in Rust? Well, you can write

[6:02](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=362s) the functional specification of it or

[6:04](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=364s) the model in Lean.

[6:06](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=366s) An example of that is Cedar.

[6:08](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=368s) Cedar is an open-source authorization

[6:11](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=371s) policy language, which is used by AWS

[6:13](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=373s) verified permissions and access.

[6:15](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=375s) The specification of Cedar is written in

[6:18](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=378s) Lean. The production code runs in Rust.

[6:22](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=382s) Why is this important? Because

[6:24](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=384s) let's take an example. You have forbid

[6:26](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=386s) Trump's permit. You want to make sure

[6:28](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=388s) that for any forbid policy being

[6:30](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=390s) satisfied, the request is always denied.

[6:32](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=392s) This is key.

[6:36](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=396s) Here you can see the example of what I

[6:37](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=397s) was talking about, which is you have the

[6:39](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=399s) Rust production code and you have the

[6:41](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=401s) functional specification in Lean, and

[6:43](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=403s) you run differential random testing to

[6:45](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=405s) check that both of those for the same

[6:47](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=407s) inputs give the same output.

[6:50](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=410s) And there's about 100 million

[6:51](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=411s) differential random tests uh run

[6:53](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=413s) nightly.

[6:54](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=414s) No version ships until this is

[6:56](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=416s) satisfied.

[6:59](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=419s) Let's take another example. What if you

[7:01](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=421s) have code in Rust and you want to

[7:03](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=423s) deductively verify with Lean or solvers?

[7:07](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=427s) Before we go there, let's quickly talk

[7:09](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=429s) about this new term solvers. So,

[7:11](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=431s) remember we spoke of Lean being this

[7:13](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=433s) chessboard interactive where you're

[7:15](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=435s) making a bunch of moves trying to

[7:16](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=436s) checkmate.

[7:17](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=437s) A solver is a calculator, a very

[7:20](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=440s) powerful one. You feed in a formula and

[7:23](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=443s) it returns an output. In this case,

[7:26](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=446s) satisfiable or unsatisfiable.

[7:30](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=450s) So, an example of this is Verus, also an

[7:33](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=453s) open-source tool.

[7:35](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=455s) It uses this solver, this very powerful

[7:37](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=457s) calculator, Z3.

[7:39](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=459s) And if folks are familiar with adding

[7:42](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=462s) annotations, it's kind of similar to

[7:43](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=463s) that where you can add specifications in

[7:46](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=466s) the form of that. And the code is in

[7:49](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=469s) line. So, you see these two requires and

[7:52](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=472s) ensure keywords, that's what we call a

[7:54](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=474s) pre and post condition. What must be

[7:57](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=477s) true before and what must be true after.

[8:01](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=481s) And this is a static check. It's

[8:02](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=482s) enforced by the verifier and erased at

[8:05](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=485s) runtime. So, almost like ghost code.

[8:09](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=489s) Another example of this is Eneus,

[8:12](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=492s) which uses the mid-level intermediate

[8:14](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=494s) representation for Rust and does a

[8:16](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=496s) functional translation to Lean. And

[8:18](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=498s) right after that, you use the same

[8:20](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=500s) theorem prover, the same chessboard that

[8:21](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=501s) we spoke of.

[8:26](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=506s) Now, you may be asking, well, what if I

[8:28](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=508s) have any programming language?

[8:32](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=512s) We at AWS have been working on an

[8:34](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=514s) open-source tool called Strata. This is

[8:37](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=517s) work in progress, but the idea is that

[8:40](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=520s) you can have any programming language

[8:42](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=522s) and you yourself can create what we call

[8:44](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=524s) a dialect.

[8:46](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=526s) Think of this like a compiler. You have

[8:48](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=528s) a high-level intermediate representation

[8:50](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=530s) and you lower it down to a low-level

[8:51](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=531s) intermediate representation, which is

[8:53](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=533s) what Strata core is. Now, this is

[8:56](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=536s) written in Lean.

[8:58](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=538s) After you have all of these programs

[9:00](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=540s) talking in the same language, which is

[9:02](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=542s) the Strata core, you can dispatch it to

[9:04](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=544s) any of the engines. For example, the

[9:06](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=546s) Lean proof, remember the chessboard, or

[9:09](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=549s) the very powerful calculator, SMT

[9:11](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=551s) solvers, or model checkers.

[9:17](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=557s) So, you can get started with this today.

[9:19](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=559s) You can go to Lean in in your browser

[9:22](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=562s) with the link I pasted, and you can pick

[9:25](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=565s) your most critical code,

[9:27](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=567s) write what correct means, which is the

[9:28](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=568s) specification, which is very important,

[9:31](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=571s) and then you can let your coding agent

[9:32](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=572s) implement it and your formal

[9:34](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=574s) verification tool prove it.

[9:38](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=578s) So, hopefully in this brave new world,

[9:41](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=581s) we have software and systems that are

[9:43](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=583s) not probably correct, but probably

[9:45](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=585s) correct. Thank you.

[10:01](https://www.youtube.com/watch?v=lRa9sPaMyy4&t=601s) >> [music]
