Skip to content

What you have to trust

A proof is only worth as much as the reasons to believe it. This chapter asks what, exactly, you have to take on trust when the project says a property is proven, and how the project makes that list short.

Lean's checker

When you write a proof with tactics, the tactics don't decide whether it is correct. They build a proof: a term, a value of the statement's type. Then a small, separate program at the heart of Lean, the kernel, checks that term against the statement. Tactics such as simp and omega are large and clever, and could have bugs, but a bug in a tactic can only make it fail to build a proof, or build one the kernel then rejects. It can't make a false statement pass.

So the first thing you trust is the kernel: a program far smaller than the rest of Lean, and the same for everyone who uses it.

The second thing is that each statement says what you mean. Lean checks that the proof proves the statement; it can't check that the statement is the one you wanted. This is why every guarantee in the project has a plain-English headline beside its exact statement, and why the statements are worth reading for yourself.

sorry

sorry proves anything. It is there so you can leave a gap while you work on the rest of a proof. Lean accepts it with a warning:

/-- warning: declaration uses `sorry` -/
#guard_msgs in
theorem wrong : 2 + 2 = 5 := by
  sorry

/-- info: 'Learn.Engine.wrong' depends on axioms: [sorryAx] -/
#guard_msgs in
#print axioms wrong

/-- An argument that uses the wrong "fact" is accepted too. -/
theorem worse : 4 = 5 := by
  rw [← wrong]

/-- info: 'Learn.Engine.worse' depends on axioms: [sorryAx] -/
#guard_msgs in
#print axioms worse

wrong is false, and Lean accepted it. Worse, worse uses it, and gets no warning at all: the warning appears only where sorry is written, not in everything that depends on it. A gap can hide two files away from the theorem you're reading.

#print axioms finds it. It lists everything a theorem rests on without proof, following every theorem it uses, all the way down. sorry shows up as sorryAx, in wrong and in worse alike.

The project refuses gaps in two ways. make proofs first searches the files under Proofs/ for the word sorry, and fails if it finds one:

make proofs

That catches the obvious case, but a gap needn't be spelled sorry. The tactic admit does the same thing:

/-- warning: declaration uses `sorry` -/
#guard_msgs in
theorem hidden : 2 + 2 = 5 := by
  admit

/-- info: 'Learn.Engine.hidden' depends on axioms: [sorryAx] -/
#guard_msgs in
#print axioms hidden

So make proofs also asks Lean, for every theorem in every Proofs module, what it rests on, as #print axioms does, and fails if anything is there that shouldn't be. An admit in Proofs/ passes the search for sorry and is stopped by this second check, which names the theorem and sorryAx.

Axioms

An axiom is a statement accepted without proof. You can declare one, and Lean will believe it:

axiom magic : 2 + 2 = 5

theorem byMagic : 2 + 2 = 5 := magic

/-- info: 'Learn.Engine.byMagic' depends on axioms: [magic] -/
#guard_msgs in
#print axioms byMagic

This is why the list from #print axioms matters: a theorem is only as true as the axioms it rests on. Here are two of the project's guarantees:

/-- info: 'Proofs.Engine.rejected_action_changes_nothing' depends on axioms: [propext, Classical.choice] -/
#guard_msgs in
#print axioms Proofs.Engine.rejected_action_changes_nothing

/-- info: 'Proofs.Snap.whole_views_reveal_nothing_hidden' depends on axioms: [propext, Classical.choice, Quot.sound] -/
#guard_msgs in
#print axioms Proofs.Snap.whole_views_reveal_nothing_hidden

These three are Lean's standard axioms, which nearly all of mathematics in Lean rests on:

  • propext: two statements that imply each other are equal.
  • Classical.choice: from a proof that something exists, you may pick one. Among other things it gives you that every statement is either true or false.
  • Quot.sound: the rule for quotient types, from which Lean gets, among other things, that two functions giving equal results on every input are equal.

The project's proofs never mention them; they arrive through the library lemmas that simp and the other tactics use. The project accepts exactly these three, and no other.

decide and native_decide

You met decide in Snap: Lean works the statement out, and the kernel checks the working. There is a faster tactic, native_decide, which compiles the check to machine code and runs it. It is much faster on big computations, but the kernel can't check machine code. It can only take the compiled program's word for it:

theorem fiftyTwo : Games.Snap.deck.length = 52 := by decide

theorem fiftyTwoFast : Games.Snap.deck.length = 52 := by native_decide

/-- info: 'Learn.Engine.fiftyTwo' does not depend on any axioms -/
#guard_msgs in
#print axioms fiftyTwo

/-- info: 'Learn.Engine.fiftyTwoFast' depends on axioms: [fiftyTwoFast._native.native_decide.ax_1_1] -/
#guard_msgs in
#print axioms fiftyTwoFast

The decide proof rests on nothing at all. The native_decide proof rests on a new axiom that Lean made for it, which says, in effect, "the compiled program said so". That brings Lean's whole compiler into what you trust, so the project doesn't use native_decide, and the axiom check in make proofs would refuse it like any other.

The guarantees page

docs/GUARANTEES.md lists every guarantee in the project. Nobody writes it. Tools/Guarantees.lean is a Lean program that loads the checked proofs and writes the page from them: for each guarantee, its headline, its exact statement, a link to its proof and the axioms it rests on.

The axioms it accepts:

/-- The axioms Lean's own kernel and standard library rest on. Anything else
(above all `sorryAx`) is flagged on the page. -/
def standardAxioms : List Name := [``propext, ``Classical.choice, ``Quot.sound]

and the check make proofs runs over every theorem in every Proofs module, guarantee or not:

/-- Every theorem in every `Proofs` module, guarantee or bookkeeping, whose
proof depends on an axiom beyond the standard three: a `sorry` (`sorryAx`),
`native_decide` (which adds an axiom of its own for each use) or a declared
axiom. -/
def unsound (env : Environment) : MetaM (List (Name × List Name)) := do
  let mut bad := []
  for m in proofModules env do
    let some idx := env.getModuleIdx? m | continue
    let some md := env.header.moduleData[idx.toNat]? | continue
    for info in md.constants do
      unless info matches ConstantInfo.thmInfo _ do continue
      let extra := (← collectAxioms info.name).toList.filter (!standardAxioms.contains ·)
      unless extra.isEmpty do bad := (info.name, extra) :: bad
  return bad

collectAxioms is what #print axioms uses. Any theorem with an axiom outside the three is reported, and the program refuses to write the page.

To regenerate the page after changing a proof:

make guarantees

make proofs writes the page afresh and compares it with the committed one, and fails if they differ, with docs/GUARANTEES.md is out of date: run make guarantees. Change one headline in Proofs/Engine/Guarantees.lean and you will see it. So the page can't fall behind the proofs, and a proof's headline can't say one thing on the page and another in the code.

The proven code is the code that runs

A proof about step is worth having only if step is what decides your game. In this project it is, because nothing is translated by hand.

Lean compiles every definition to C. After

make lean

you can open .lake/build/ir/Games/Snap/Rules.c and find Snap's step as the C function lp_stichhalter_Games_Snap_step, compiled from the same definition the proofs are about.

The hosts reach the engine through a handful of functions marked @[export …] in Ffi/Export.lean, which gives each a fixed C name. Here is the one that starts a table:

def newBytes (game config : ByteArray) : Except String AnySession := do
  new (← utf8 "game" game) (← utf8 "config" config)

It takes raw bytes and lets Lean decode them, so no host code stands between what a client sent and what the engine reads. Every game is reached through one type with one case per game:

/-- Every registered game. Adding a game means adding a constructor here. -/
inductive AnySession where
  | counter (s : Session Games.Counter.State)
  | snap (s : Session Games.Snap.State)
  | lol (s : Session Games.LoL.State)
  | alba (s : Session Games.Alba.State)
  deriving Inhabited

Each case holds a session of its own game, so these functions just pass each request to that game's Session functions, the ones the proofs are about. capi/sh.c wraps them in a plain C interface, and both hosts use that:

  • the Go server links the compiled C, through cgo, into one native program;
  • the browser gets the very same C files, compiled to WebAssembly by wasm/build.sh:
make wasm

The engine imports nothing but Lean's Init and Std libraries, and does no input or output, so the same code builds for both. The web tests also check that the WebAssembly engine and the native one give the same answers.

What the proofs don't cover

The list of things you trust is short, but it isn't empty, and it is better to know it:

  • The tools. Lean's kernel, its compiler from Lean to C, the C compiler, and Lean's runtime (which manages memory). The proofs are about the Lean definitions; the compiler is trusted to run them faithfully.
  • The code around the engine. capi/sh.c, the Go server and the browser page aren't proven. They can't change the rules, because they never decide anything, but they could fail to deliver what the engine says.
  • The JSON text. The proofs are about Json values. Turning a value into text and back is done by Json.render and the parser in Engine/Json.lean, which are written as partial def:

    partial def render : Json → String
      | null => "null"
      | bool true => "true"
      | bool false => "false"
      | num n => toString n
      | str s => escape s
      | arr xs => "[" ++ ",".intercalate (xs.toList.map render) ++ "]"
      | obj kvs => "{" ++ ",".intercalate (kvs.toList.map fun (k, v) => escape k ++ ":" ++ render v) ++ "}"
    

    partial lets a function call itself without Lean checking that it stops, at the price that proofs can't see inside it. So no proof says that render writes each value correctly. The tests check it instead. - Ffi/Export.lean itself, which has no proofs of its own. It is short, and each case only passes the request on, but that is a fact you check by reading, not one Lean has checked. - The statements. Above all: that each guarantee says what the rules of the game mean. Lean can't check that, and you can: read them.

Exercises

  1. Print the axioms of Proofs.Engine.names_change_nothing_in_the_game and Proofs.Engine.only_admitted_events_are_shown, and compare them with what docs/GUARANTEES.md says.
  2. Without #print axioms, how could you tell that worse rests on a gap?
  3. Add a theorem to Proofs/Engine/Bookkeeping.lean whose proof is admit, and run make proofs. Which of its two checks stops it? Then put the file back with git restore Proofs/Engine/Bookkeeping.lean.
Solution
  1. Lean prints these, and the page agrees:

    /-- info: 'Proofs.Engine.names_change_nothing_in_the_game' depends on axioms: [propext, Classical.choice] -/
    #guard_msgs in
    #print axioms Proofs.Engine.names_change_nothing_in_the_game
    
    /-- info: 'Proofs.Engine.only_admitted_events_are_shown' depends on axioms: [propext, Quot.sound] -/
    #guard_msgs in
    #print axioms Proofs.Engine.only_admitted_events_are_shown
    

    They differ from each other because they use different library lemmas, not because one is more trustworthy: both stay within the standard three.

  2. You would have to read its proof, see that it uses wrong, then read wrong's proof, and so on down. That is exactly the search #print axioms does for you, and the reason the project runs it on every theorem rather than trusting the warnings.

  3. The search for the word sorry finds nothing, since the file says admit. Lean builds it with the warning declaration uses sorry, and then the axiom check fails: Unsound proofs: these theorems depend on non-standard axioms:, naming your theorem and sorryAx, then proofs are unsound (see above).