Introduction to Formal Verification with Lean Part 1(hashcloak.com)
233 points by badcryptobitch 3 days ago | 51 comments
tl;dr: A hands-on tutorial introducing formal verification in Lean 4 for cryptography engineers, using the One-Time Pad as a worked example. It walks through defining bitstrings and XOR over ℤ₂, proving XOR's commutativity, associativity, identity, and self-inverse properties using tactics like `Vector.ext`, `simp`, and `intro`, then defines a Shannon cipher as a Lean `structure` and proves OTP satisfies its correctness property. Based on Boneh & Shoup's textbook, it's aimed at beginners and serves as a stepping stone to more advanced formalizations like VCV-io.
HN Discussion:
  • Sharing supplementary Lean learning resources and tutorials for curious readers
  • ~Tactic-based proofs are aesthetically inferior and hard to read without interactive execution
  • Lean combined with compile-time checking and LLMs has a promising future
  • Questioning Lean's dominance versus alternatives like Isabelle or its maturity as an application language
  • Curious beginner questioning how formal verification differs from runtime assertions