HN 日本語サマリー

← 一覧へ戻る
プログラミング

Leanによる形式検証入門 Part 1

Introduction to Formal Verification with Lean Part 1 (hashcloak.com)

201 pointsby badcryptobitch38 コメント

要約

この記事は、Lean証明支援系を用いた形式検証の入門です。形式検証とは何か、そしてLeanを使って数学的証明を記述し、機械でチェックする方法を解説します。チュートリアルでは、ビット文字列とXOR関数をLeanで定義することから始め、ワンタイムパッド暗号プロトコルの形式検証を行います。

全文翻訳

チュートリアル:Lean を用いた形式検証入門 (Part 1)

形式検証は、(数学的な)命題の正しさを検証するためのツールです。ペンと紙で数学の証明を書く代わりに、形式検証ツールを使ってコードで証明を記述し、機械的にチェックすることで、証明が正しいことを確実に知ることができます。これらのツールの例としては、Rocq (旧 Coq)、Isabelle、そしてこのチュートリアルのトピックである Lean があります。

このチュートリアルでは、暗号に関するいくつかの簡単な命題とその証明を Lean で記述します。したがって、形式検証の初心者や、形式検証の基本知識を復習したい暗号エンジニアにとって楽しいものとなることを目指します。

具体的には、Lean の非常に基本的な部分を walkthrough し、その後、Claude Shannon によって最初に普及しましたが、Frank Miller および Gilbert Vernam によって以前に記述された、ワンタイムパッド (OTP) プロトコルを形式的に検証します。

このチュートリアルの目標は、ワンタイムパッドのような、より単純な暗号プロトコルに関する形式的な定義と証明を Lean に移植することです。定義と証明の主な情報源として、Dan Boneh と Victor Shoup の『A Graduate Course in Applied Cryptography』を使用します。

このチュートリアルの終わりまでに、VCV-io のような、他の形式化された暗号化の Lean 証明を理解できるようになるはずです。

免責事項:これは決して Lean におけるベストプラクティスを与えることを意図したものではなく、むしろ暗号関係者にとって理解しやすく楽しいものとなるような入門を目指しています。

Lean プログラミング言語 & 証明支援系

Lean は、2013 年に Leonardo de Moura によって、当時 Microsoft Research に在籍していた際に作成されました。これは関数型プログラミング言語であり、定理証明支援系です。

数学者は、公理、補題、定理を記述し、必要に応じて証明を追加するためにこれを使用できます。証明が Lean によってコンパイルされた場合、それは正しいことを意味します(Lean コンパイラへの信頼を前提とします)。チェック可能な証明という利点に加えて、証明をサブ証明に分割しやすく、共同作業も容易になります。さらに、Lean は自動的に検索して欠落している部分を適用することで、証明の完了を支援できます。

しかし、Lean は「単なる」プログラミング言語でもあります。具体的には、純粋な関数型プログラミング言語であり、プログラムに副作用がなく、関数が第一級の値として扱われます。後者については、チュートリアルでさらに詳しく見ていきます。

Lean を始めるための優れたリソースはたくさんあります。いくつか例を挙げます。

(多くの素晴らしいリソースがすでに存在しているにもかかわらず、私がこの特定の演習を作成した理由は、暗号との特定の重複があるためです。VCV-io は暗号化に関する素晴らしい証明を持っていますが、初心者には高度すぎ、チュートリアルがありません。)

チュートリアル

始めましょう。チュートリアルは、簡単な「Hello World!」の後、4つのパートに分かれています (パート 2 が最も長いです)。すべて Lean 4 で記述されており、皆さんがコードを一緒に書くことを想定しています。

行番号付きで表示されるコードは、最終結果に必要なコードです。行番号のないコードは、まだ完了していないか、何かを確認するためだけのものですので、安全に削除できます。

最後に、サブセクションの冒頭には、そのセクションで共有される新しい概念を含む小さなコメントがあります。

Lean での Hello world

  • Lean InfoView
  • eval

Lean をローカルにダウンロードするか、https://live.lean-lang.org/ のようなオンラインエディタを使用できます。これは(以下のような)見た目になります。左側で Lean を書き、右側は Lean InfoView で、役立つ情報やヒントが表示されます。

[画像]

すべてが正常に機能することを確認するために、次のようなものを記述します。

#eval 1+1

そして、結果が右側の InfoView に表示されることを確認してください。

伝統的な「Hello World!」は、次のいずれかで実行できます。

#eval "Hello World!"#eval String.append "Hello " "World!"#eval String.append "Hello " (if 1 > 2 then "Lean!" else "World!")

Lean のいくつかのプロパティ:

  • 標準的な数学的慣習に従います:例 #eval 4 + 5 * 6 は 4+(5*6)=34 と評価されます。

  • 関数引数を保持するための括弧はありません。つまり、Lean では f(x) ではなく f x と記述します。

  • 関数は Lean における第一級の値であり、数値や文字列のような値と同様に扱われます。

しかし、先走りすぎないようにしましょう。必要な Lean のトピックは、進むにつれて学んでいきます。

本には何が書いてあるか? つまり、Lean に移植したいものは何か?

何を定義したいかは多かれ少なかれわかっていますが、Lean を使用するには明確さと正確さが必要です。具体的に何を定義したいのか、そしてそれをどのように定義するのか? このために Boneh & Shoup の本 を使用します。これにより、必要な数学はすでに記述されており、Lean への翻訳だけを心配すればよくなります。

まず、シャノン暗号 (2.1.1) の定義があり、3つのプロパティがあります。最初の 2 つは暗号化関数と復号化関数が何であるかを伝え、最後の 1 つは正しさのプロパティであり、暗号化後の復号化が元のメッセージを返すことを示します。

[画像]

私たちが興味を持っている具体的な例はワンタイムパッドであり、暗号化と復号化は単純に XOR 演算です。

[画像]

チュートリアルのかなりの部分が、ビット単位の排他的論理和 (XOR) のプロパティの証明に費やされます。

[画像]

そして最後に、ワンタイムパッドがシャノン暗号であることを、正しさのプロパティを満たすことを証明することで示すことができます。

[画像]

この最初のチュートリアルでは、次の簡単な手順を実行します。

  1. ビット文字列と XOR 関数を定義する

  2. XOR の必要なプロパティを証明する

    • 交換律

    • 結合律

    • 単位元

    • 自己逆元

  3. シャノン暗号を定義する。これには以下が含まれます。

    • 暗号化関数

    • 復号化関数

    • 復号化が暗号化を「元に戻す」プロパティ(正しさ)

  4. 暗号化と復号化が XOR である OTP がシャノン暗号であることを示す。

準備はいいですか?始めましょう。

チュートリアル Part 1: BitString と XOR の定義

ワンタイムパッドは、キー K、メッセージ M、暗号文 C のすべてが同じ長さ L のビット文字列であるという前提で定義されます。K := M := C := {0,1}ᴸ。

XOR の定義では、2 を法とする加算が必要です。したがって、{0,1}ᴸ を ℤ₂ᴸ と見なし、Lean で ℤ₂ 上の算術を使用すると便利です。

有限体
  • ライブラリのインポート
  • Zmod n

まず、Lean の数学ライブラリから有限体ライブラリ ZMod をインポートします。

import Mathlib.Data.ZMod.Basic

この事前定義されたライブラリ ZMod n は、モジュラ算術が事前に実装されている整数 modulo n を定義します。(Cmd/Ctrl キーを押しながらクリックすることで、すでに実装されている型についてさらに詳しく読むことができます。例えば、ZMod n を確認してください。)

ZMod に慣れるために、簡単なモジュラ算術を試してみてください。例えば、5 + 6 mod 7 です。

#eval (5: ZMod 7) + (6: ZMod 7)

これで、ZMod 2 の要素のベクトルである新しい型を作成することにより、K、M、L のドメインを定義できます。

BitString の定義
  • Vector
  • 依存型
  • check

Lean の良い点は、ビット文字列の長さ L を固定する必要がないことです。数学で行うように、単に L を ℕ (自然数) として指定できます。(Lean で ℕ を記述するには、「\N」と入力します。)

事前定義された型 Vector α n は、型 α の要素を持つ長さ n のベクトルを作成します。したがって、カスタム型 ℤ₂ᴸ を定義するために Vector (ZMod 2) L を使用できます。

def BitString (L: ℕ): Type := Vector (ZMod 2) L

これは依存型であり、ℕ の異なる値に対して異なるインスタンス化を提供します。確認できます。

#check BitString 5 --BitString 5 : Type

#eval は評価するものが何もないため機能しませんが、#check は式の型を表示します。この場合、うまく機能します。

XOR の定義
  • 暗黙的なパラメータ
  • カリー化
  • ラムダ関数

次に、ビット文字列 x = [x₁, …, x<0xE2><0x82><0x97>] と y = [y₁, …, y<0xE2><0x82><0x97>] を入力として、xor 関数を [x₁ +₂ y₁, …, x<0xE2><0x82><0x97> +₂ y<0xE2><0x82><0x97>] と定義します。ここで +₂ は 2 を法とする加算です。

Lean でこれをどのように定義できるでしょうか? 数学での関数シグネチャを考えてみましょう:ℤ₂ᴸ × ℤ₂ᴸ → ℤ₂ᴸ。これを実現するにはいくつかの方法があります(Lean では常に物事を達成するための多くの方法があります)。ここでは次のようにします。

def xor {L: ℕ} (x y: BitString L): (BitString L)

ここでは、パラメータ L は暗黙的です。次に「関数本体」が必要です。

2つの入力ベクトルを簡単に反復処理し、それらを要素ごとに加算するには、ベクトルで利用可能な事前定義関数 zipWith を使用できます。zipWith の型を理解しましょう。

def zipWith (f : α → β → φ) (as : Vector α n) (bs : Vector β n) : Vector φ n

これは、関数 f と 2 つのベクトル as と bs を引数として取り、as と bs と同じ長さのベクトルを返します。ベクトルの要素の型は異なる場合があることに注意してください(xor の場合はそうではありませんが)。

関数型 f : α → β → φ は次を意味します:型 α の要素と型 β の要素を取り、型 φ の要素を返します。数学では α × β → φ と記述します。Lean が使用するアプローチはカリー化 と呼ばれます。複数の引数を持つ関数は、それぞれ単一の引数を受け取る関数のシーケンスとして表現されます。これにより、部分適用が可能になり、コードが非常に柔軟になります。したがって、f : α → β → φ を f : α → (β → φ) として読み取ることができ、型 α の最初の要素を与えると、型 β の要素を与えて型 φ の結果を得る関数 β → φ が得られることがわかります。

したがって、zipWith が行うことは、2つのベクトルを並行して走査し、現在の 2 つの要素に対して操作 f を実行することです。xor の場合、x と y を走査して 2 を法として加算させたいのです。

def xor {L: ℕ} (x y: BitString L): (BitString L) :=  -- TODO define f  Vector.zipWith f x y

パズルの最後のピースは、zipWith に渡したい関数 f を定義する方法です。要素の加算を実行する必要があることを知っています。ここでは、以前見たように、コンパクトな方法で記述できるラムダ関数を使用できます。例えば fun x => x + 1 (自然数の後続を返す)。

まとめると:

def xor {L: ℕ} (x y: BitString L): (BitString L) :=  Vector.zipWith (fun a b => a + b) x y

BitString の型が ℤ₂ の要素を持っているため、加算は自動的に mod 2 の加算になるため、これは正しく機能することに注意してください。

チュートリアル Part 2: XOR のプロパティの証明

さて、いよいよ本番です!

明確にするために、現時点で少なくとも持っているべき内容は次のとおりです。

import Mathlib.Data.ZMod.Basicdef BitString (L: ℕ): Type := Vector (ZMod 2) Ldef xor {L: ℕ} (x y: BitString L): (BitString L) :=  Vector.zipWith (fun a b => a + b) x y

または、あなたにとって機能する同等のバージョン!さらに 1 行追加します。xor 定義の前に次を追加します。

namespace BitString

これにより、証明を開始したときに、Lean が既に存在する別の xor 定義と混同しないようになります 😅

引き続き、Boneh & Shoup の本に従い、XOR の定義 (例 2.1) で言及されているプロパティを証明していきます。まず、交換律から始めます。

[画像]

XOR の交換律の証明; x ⊕ y = y ⊕ x

まず、XOR の交換律、つまり x ⊕ y = y ⊕ x を証明します。この最初のプロパティの証明には最も時間がかかります。なぜなら、チュートリアルで最初の Lean 証明が含まれているからです。これは 3 つのステップに分かれています。

交換律の補題の定義
  • Lean におけるゴール
  • 補題の定義
  • sorry

交換律のプロパティを補題として定義し、それを証明します。補題を書き終えるとすぐに、Lean はそれを証明すべき「ゴール」と呼びます。あなたのタスクは、現在のゴールを、すでに真実であることがわかっているものに近い、より小さなサブゴールに減らすことです。証明は、プログラミングの問題を小さなサブ問題に分割するのと似た、一連の削減になります。

Lean における補題(または定理)の要素は次のとおりです。

lemma <lemma_name> <lemma_arguments> : <lemma_statement> := <proof>

この場合、<lemma_arguments> は 2 つの BitString、x と y で構成されます。

<lemma_statement> は、x と y について証明したい交換律のプロパティを表現する必要があります:xor x y = xor y x。

補題の名前は好みに依存します。私はエレガントに短い xor_comm_property を選びました。BitString については、暗黙的なパラメータ L が必要であることに注意してください。

lemma xor_comm_property {L: ℕ} (x y : BitString L) : xor x y = xor y x :=    sorry -- 証明を追加するまでプレースホルダーです

sorry プレースホルダーは私の奇妙な発明ではなく、これは実際の Lean のプレースホルダーであり、「まだ証明していなくてすみません」と読むことができます。

交換律の補題の証明:ステップ 1
  • タクティクス、by
  • ⊢
  • Vector.ext

私たちはタクティクス を使用して証明を構築します。これは現在のゴールを削減するのに役立つ指示です。例えば、次のようなさまざまなオプションのステップがあります。

  • ゴールを同等な形式に書き換える

  • ゴールを複数のサブゴールに分割する

  • すでに真実であることがわかっているものと一致した場合にゴールを閉じる

sorry を削除し、by に置き換えることから始めます。これは、タクティクスを使用して証明することを示します。Lean がゴールの状態と進捗状況を示してくれるため、これは役立ちます。見た目は次のようになります。

[画像]

InfoView では、Lean は次のように述べています。ゴールは、L ∈ ℕ および x,y が BitString L 型の場合に x.xor y = y.xor x を示すことです。(ゴールは常に ⊢ の前に付きます。)

証明に移りましょう。何を知っていますか? すべてのインデックス i について、両辺の対応する要素を計算すると、それらは等しくなります:(x.xor y)[i] = (y.xor x)[i]。なぜなら、ℤ₂ における加算の交換律により (x[i] + y[i]) = (y[i] + x[i]) となるからです。

したがって、ゴールを L 個のサブゴールに分割し、i を範囲指定できれば、残りのゴールは両辺の単一要素の等しさの証明になります。

これを L 個のサブゴールに分割するには、外延性補題を使用できます。これは、「2つのものは、それらが同じもので構成されている場合に同じである」と述べています。これは多くの型に適用できる一般的なタイプの補題であり、ベクトルについては Vector.ext (参照) を介してアクセスできます。次のように使用できます。

lemma xor_comm_property {L: ℕ} (x y : BitString L) : xor x y = xor y x :=    by      apply Vector.ext

これで、エディタでゴールが次のように変更されます。

L : ℕx y : BitString L⊢ ∀ (i : ℕ) (x_1 : i < L), (x.xor y)[i] = (y.xor x)[i]

まだ L ∈ ℕ と BitString L 型の x,y がありますが、ゴールは次のようになります。すべての i ∈ ℕ で i < L の場合:(x.xor y)[i] = (y.xor x)[i]。これが実際に何を意味し、証明をどのように続けるかについては、次のステップを参照してください。

交換律の補題の証明:ステップ 2
  • intro
  • simp

ペンと紙での証明では、任意の i を固定して、それに対する等しさの証明に進むことで証明を続けることができました。「i ∈ で i < L とする」と始めて、その固定された i に対する等しさの証明に進むかもしれません。Lean では、次のように表現できます。

  1. まず、自由変数 i ∈ ℕ を intro i で固定します。

  2. 次に、仮説 i < L を intro h_i_lt_L(「仮説 i は L より小さい」)で導入します。

intro はゴールの先頭を剥がし、証明のローカル「コンテキスト」に入れます。変数を固定する(1 のように)か、追加の仮説を導入する(2 のように)かのどちらかです。

それらを 1 行に連続して記述できます。

lemma xor_comm_property {L: ℕ} (x y : BitString L) : xor x y = xor y x :=    by      apply Vector.ext      intro i h_i_lt_L

これでゴールは次のようになります。

L : ℕx y : BitString Li : ℕh_i_lt_L : i < L⊢ (x.xor y)[i] = (y.xor x)[i]

ゴールの前にある部分 ⊢ は、コンテキストにあるすべてです。固定した変数と導入した仮説です。ゴールは、今証明するために残っているものです。

証明を完了するために、タクティク [simp](https://lean-lang.org/theorem_proving_in_lean4/Tactics/?terms=simp#using-the-simplifier)(「シンブリファイア」)を使用して、等しい式を置き換えます。まず、x.xor y と y.xor x の xor の定義を展開できます。

lemma xor_comm_property {L: ℕ} (x y : BitString L) : xor x y = xor y x :=    by      apply Vector.ext      intro i h_i_lt_L      simp[xor]

これでゴールは次のようになります。

L : ℕx y : BitString Li : ℕh_i_lt_L : i < L⊢ x[i] + y[i] = y[i] + x[i]

そして、この時点で、ℤ₂ における加算の交換律により、これが真であることがわかっています。これは add_comm と呼ばれる、ZMod からすでに証明されているプロパティです。

simp[add_comm] を追加すれば完了です。これで最初の証明が完了しました!

lemma xor_comm_property {L: ℕ} (x y : BitString L) : xor x y = xor y x :=    by      apply Vector.ext      intro i h_i_lt_L      simp[xor]      simp[add_comm]

右側の InfoView でゴールがなくなったことを確認してください 🫡

[画像]

次に進む前に、いくつかの免責事項があります。これはこのプロパティを証明する最も速く、最も短く、最もエレガントな方法でしょうか?いいえ、いいえ、おそらくいいえです。

ここでの目標は、私たちがやっているすべてのステップを正確に理解することです。実際には、Lean は多くのことを自動的に解決してくれます。しかし、教育目的のためには、すべてのサブステップを見て理解することが役立つと思います。そのため、私は長くて機械的なアプローチを取っています。さらに、自動化されたものに進む前に、ペンと紙での証明が Lean にどのように翻訳されるかを理解することが目標です。しかし、証明を好きなように短くしたり、変えたりするのは自由です!

XOR の結合律の証明; x ⊕ (y ⊕ z) = (x ⊕ y) ⊕ z
  • simp での自動適用
  • simp での式のマージ

一般的なアイデアがわかったので、次の証明ステップははるかに速くなります。このステップでは、xor が結合律を満たすこと、つまり x ⊕ (y ⊕ z) = (x ⊕ y) ⊕ z を示します。まず、補題の定義です。

lemma xor_assoc_property {L: ℕ} (x y z: BitString L) : xor x (xor y z) = xor (xor x y) z :=   sorry

ここでも、Vector.ext を使用して、左辺と右辺のランダムな単一エントリのレベルでこの等しさを証明します。

lemma xor_assoc_property {L: ℕ} (x y z: BitString L) : xor x (xor y z) = xor (xor x y) z :=   by    apply Vector.ext

InfoView は次のように表示します。

L : ℕx y z : BitString L⊢ ∀ (i : ℕ) (x_1 : i < L), (x.xor (y.xor z))[i] = ((x.xor y).xor z)[i]

前のステップでは、変数 i を固定し、i < L であるという仮説を導入しました。しかし、ここでは Lean は魔法を適用して、simp でこれらの部分を解決できます。これは、渡された書き換えを適用するだけでなく、適用可能なすべての証明済みプロパティとタクティクスを検索し、何が機能するかを自動的に判断します。

したがって、この等式を証明することにすぐに進むことができます。

(x.xor (y.xor z))[i] = ((x.xor y).xor z)[i]

ここでも、xor の定義を展開すると、一歩近づきます。simp[xor] と記述し、L 個のサブゴールへの展開も自動的に適用されることを確認してください。

lemma xor_assoc_property {L: ℕ} (x y z: BitString L) : xor x (xor y z) = xor (xor x y) z :=   by    apply Vector.ext    simp[xor]

i ごとのゴールは次のようになります。

x[i] + (y[i] + z[i]) = x[i] + y[i] + z[i]

この時点で、ℤ₂ における加算の結合律 [add_assoc](https://leanprover-community.github.io/mathlib4_docs/Mathlib/Algebra/Group/Defs.html#add_assoc) を使用してゴールを閉じることができます。新しい行 simp[add_assoc] を記述する代わりに、前の simp にマージできます。

lemma xor_assoc_property {L: ℕ} (x y z: BitString L) : xor x (xor y z) = xor (xor x y) z :=  by    apply Vector.ext    simp[xor, add_assoc]

これによりゴールが閉じられ、xor の結合律プロパティが証明されます。

ここにはまだある程度の Lean の魔法が自動的に適用されていることに注意してください。厳密に言えば、x[i] + (y[i] + z[i]) = x[i] + y[i] + z[i] は add_assoc で期待される a + b + c = a + (b + c) の形式ではありません(括弧の違いに注意してください)。もちろん、この場合同じ意味であることを知っています。そして、これは誰かが依存しているライブラリのどこかに定義されており、独自の定義/証明にはより厳密さが必要になる可能性があることを意味すると考えられます。

XOR の単位元 ID を定義し、正しさを証明する
  • Vector.replicate
  • ラムダ関数を使用した Vector.ext の使用

次に必要なのは、xor の単位元です。そのような要素 ID については、すべての x に対して x ⊕ ID = x が成り立つ必要があります。

xor は ℤ₂ における加算と等しいため、単位元はすべての要素が 0 であるビット文字列であるべきです。なぜなら、2 を法とする 0 との加算は単位元だからです。

例えば L=5 のような長さのゼロの BitString をどのように作成しますか? 長さ 5 のベクトルをゼロで埋めて BitString (ℤ₂ の要素を持つベクトル) にキャストします。

#eval (Vector.replicate 5 0: BitString 5)

InfoView では、これがゼロで埋められた長さ 5 の BitString を与えることがわかります。これで、このアイデアを ID に一般化できます。

def BitString_ID {L: ℕ} : BitString L := Vector.replicate L 0

そして、このプロパティが成り立つことを示したいのです。すべての x に対して:x ⊕ ID = x。

lemma xor_show_identity {L: ℕ} (x: BitString L): xor x BitString_ID = x :=    sorry

前のステップから、この戦略が機能することを知っています。

  -- by  --   apply Vector.ext  --   intro i  --   simp[xor, BitString_ID]

したがって、少し異なるものを試してみましょう。再び Vector.ext を使用しますが、呼び出し方が異なります。今回は Vector.ext 自体のシグネチャを最初に確認します(ここでは L で n を置き換えて明確にしています)参照。

protected theorem ext {xs ys : Vector α L} (h : (i : Nat) → (_ : i < L) → xs[i] = ys[i]) : xs = ys := sorry
  • {xs ys : Vector α L} は、xs と ys が暗黙的な型であることを意味します。Lean がそれらを推論します。

  • (h : (i : Nat) → (_ : i < L) → xs[i] = ys[i]) は、渡す必要がある引数です。

  • xs = ys が成り立つことです。

h : (i : Nat) → (_ : i < L) → xs[i] = ys[i] を渡す方法を考えてみましょう。これは 2 つの引数、i と、長さ L に対する i < L の証明を受け取ります。出力は xs[i] = ys[i] の証明であるべきです。この証明は simp[xor, BitString_ID] を使用して与えられることを知っています。

引数を記述するために、以前見たようにラムダ関数を使用できます。まとめると、次のようになります。

lemma xor_show_identity {L: ℕ} (x: BitString L): xor x BitString_ID = x :=  Vector.ext fun i i_less_than_L => by simp [xor, BitString_ID]

実際、Lean の魔法のおかげで、Vector.ext fun _ => by simp [xor, BitString_ID] を使用するだけでも正しく推論されます。

XOR の自己逆元を証明する; x ⊕ x は ID を与える
  • exact?、exact
  • mpr
  • rfl

証明する最後のプロパティは、各要素がそれ自身の逆元であることです。すべての x に対して:x ⊕ x = ID。

開始するには、補題のシグネチャを作成し、上記で見たテクニックを適用します。

lemma xor_self_inverse {L: ℕ} (x: BitString L): xor x x = BitString_ID :=  by    apply Vector.ext    intro i i_less_than_L    simp[xor, BitString_ID]

これにより、次のポイントに到達します。

[画像]

xor と BitString_ID の定義を展開するために simp[xor, BitString_ID] を使用し、i ごとのゴールを絞り込み、intro i と intro i_less_than_L を使用して、i ごとに x[i] + x[i] = 0 を示すだけになりました。

ℤ₂ ではこれが成り立つことを知っていますが、Lean ではどのように記述しますか?

Lean は非常に役立ち、自動的に解決するだけでなく、提案も提供してくれることがわかりました。証明の次の行に exact? と入力し、InfoView の提案を確認してください。

[画像]

まずアドバイスに従い、次にそれが何をするかを理解しましょう。exact? を exact CharTwo.add_eq_zero.mpr rfl に置き換えて、ゴールが閉じることを確認してください 🎉

次に、ステップごとに見ていきましょう。CharTwo.add_eq_zero という名前から、これは特性 2 の環における加算のプロパティがそれ自身にゼロに等しいことを適用すると推測できます。コード内の名前を Cmd/Ctrl キーを押しながらクリックすることで、いつでも詳細を確認できます。この場合、定理は次のことを述べています(参照)。

theorem CharTwo.add_eq_zero {R : Type u_1} [Ring R] [CharP R 2] {a b : R} :    a + b = 0 ↔ a = b

iff(↔)は 2 つの関数を提供します。

  • mp: 左から右へ (a + b = 0) → (a = b)

  • mpr: 右から左へ (a = b) → (a + b = 0)

作業中の補題に適用すると、CharTwo.add_eq_zero.mpr は次のように述べています。x[i] = x[i] の証明が与えられると、x[i] + x[i] = 0 が続くということです。

最後に必要なのは [rfl](https://leanprover-community.github.io/mathlib4_docs//Init/Prelude.html#rfl) です。これは、計算によって等しい 2 つのものを等しいとみなします。この場合、x[i] = x[i] の証明として使用でき、これらを組み合わせることで完全なゴールが証明されます。

lemma xor_self_inverse {L: ℕ} (x: BitString L): xor x x = BitString_ID :=   by    apply Vector.ext    intro i i_less_than_L    simp[xor, BitString_ID]    exact CharTwo.add_eq_zero.mpr rfl

チュートリアル Part 3: Shannon Cipher の定義

  • structure を使用して新しい型を作成する

このチュートリアルの終わりに近づいています。最後のピースは、本に従って Shannon Cipher を定義し、次にワンタイムパッドが実際に Shannon Cipher であることを示すことです。

まず、フォローしている本からの定義を思い出しましょう。

[画像]

新しい型を導入する必要があります。これには以下が含まれます。

  • 暗号化関数

  • 復号化関数

  • 正しさのプロパティ

これには、Lean の構造体を使用します。これは他の言語の struct と同様です。例えば、x と y の両方が Float である点(Point)を定義したい場合:

structure Point where  x : Float  y : Float

これを私たちのケースに ShannonCipher 用にどのように適用できますか?まず、メッセージ空間 M、キー空間 K、暗号文空間 C の特定の定義にする必要があります。

型に対してジェネリックな構造体を作成するには、次のようにします。

structure Point (T: Type) where  x : T  y : T

したがって、スケルトンを作成して埋めましょう。

structure ShannonCipher (K M C: Type) where  enc: sorry  dec: sorry  correctness: sorry

これは K、M、C が同じ型を持つことを要求しないことに注意してください。(K M C: Type) と記述することは、(K: Type) (M: Type) (C: Type) と同等であり、これらが個別のジェネリック型であることをより明確に示す可能性があります。

次に、ShannonCipher のフィールドの型を定義します。暗号化はキーとメッセージを取り、暗号文空間に出力します。数学での関数シグネチャは K × M → C です。Lean では、これは K → M → C と表現されます(以前のカリー化の説明を思い出してください)。

復号化関数は、キーと暗号文を取り、メッセージ空間に出力します。これらの部分を定義に追加しましょう(Lean で → を取得するには「\r」と入力します)。

structure ShannonCipher (K M C: Type) where  enc: K → M → C  dec: K → C → M  correctness: sorry

最後に、正しさの定義があります。本によれば、このプロパティは次のとおりです。

∀ k ∈ K, m ∈ M: dec(k, enc(k,m)) = m

Lean では、次のように記述できます(Lean で ∀ を取得するには「\forall」と入力します)。

correctness: ∀ (k: K) (m: M), dec k (enc k m) = m

Lean は k と m の型も推論できます。したがって、最終的な定義は次のようになります。

structure ShannonCipher (K M C: Type) where  enc: K → M → C  dec: K → C → M  correctness: ∀ k m, dec k (enc k m) = m

3 つの異なる型で ShannonCipher をインスタンス化できることを再確認します。

#check ShannonCipher Nat String Bool

最後のステップに進みましょう!

チュートリアル Part 4: ワンタイムパッドが ShannonCipher であることの証明

  • 構造体型の値を作成する
  • fun args => のための構文糖衣

最後に、ワンタイムパッドを ShannonCipher としてインスタンス化します。これを行うには、次のことを行う必要があります。

  1. (K M C: Type) に正しい値を渡す。

  2. enc/dec を xor の適用として定義する。

  3. 正しさのプロパティを証明する。本に記載されている証明に従います。

構造体で定義された型の値を作成するには、すべてのフィールドに値を指定します。前のサブセクション Point の structure 例に従って、点 (0,0) は次のように値として定義できます(Functional Programming in Lean の例、参照)。

structure Point where  x : Float  y : Floatdef origin : Point := { x := 0.0, y := 0.0 }

さらに、Point のジェネリックバージョン(structure Point (T: Type) where ...)を使用した場合は、型を明示的に追加する必要があります。

def origin : Point Float := { x := 0.0, y := 0.0 }

OTP の場合、K := M := C := {0,1}ᴸ と設定します。これは以前定義した BitString (L: ℕ) 型なので、OTP は次のように開始できます。

def OneTimePad (L : ℕ) : ShannonCipher (BitString L) (BitString L) (BitString L) :=
  {
    enc := sorry,
    dec := sorry,
    correctness := sorry
  }

enc と dec の定義には、再びラムダ関数を使用できます。

enc := fun k m => xor k mdec := fun k c => xor k c

Lean では物事を異なる方法で表現できるため、構文糖衣を使用して上記のコードを少し異なる方法で表現できます。fun args => は、引数 args を := の左側に移動することで置き換えることができます。

enc k m := xor k mdec k c := xor k c

最後のステップは correctness の値です。これは証明であるべきです。本に記載されているとおりに証明を記述します。例 2.1 から思い出してください。

[画像]

次のプロパティが適用される順序は次のとおりです。

  1. 実際の暗号化関数を xor に置き換える

  2. 実際の復号化関数を xor に置き換える

  3. xor の結合律

  4. xor の自己逆元

  5. ID との加算が自己逆元を与える

sorry を by に置き換えて証明を開始し、Lean InfoView がゴールとして何を示しているかを確認します。

def OneTimePad (L: ℕ ): ShannonCipher (BitString L) (BitString L) (BitString L) :=
{
  enc k m := xor k m
  dec k c := xor k c
  correctness := 
    by
}

L : ℕ に対してゴール ⊢ ∀ (k m : BitString L), k.xor (k.xor m) = m を示します。

[画像]

これは、Lean がすでにステップ 1 と 2 を実行したことを意味します。したがって、証明した補題 xor_assoc_property を参照することで、結合律を直接適用できます。

correctness :=
    by
      simp[xor_assoc_property]

これにより、ゴールは ∀ (k m : BitString L), (k.xor k).xor m = m に変更されます。次に、補題 xor_self_inverse を使用してステップ 4 を適用します。

correctness :=
    by
      simp[xor_assoc_property]
      simp[xor_self_inverse]

ゴールは ∀ (k m : BitString L), BitString_ID.xor m = m になりました。ステップ 5 の証明を適用するには xor_show_identity 補題を使用したいのですが、直接試すと次のようになります。

[画像]

「simp は進歩しなかった」- なぜでしょうか? xor x BitString_ID = x としてプロパティを定義しましたが、現在のゴールは BitString_ID.xor m = m です。これは同じであることを知っていますが、厳密には同じであることを示していません。しかし、交換律プロパティ xor x y = xor y x を補題 xor_comm_property で示したので、それを最初に適用すればうまくいくはずです。

正しさのプロパティが証明されたことを確認します。

correctness :=
    by
      simp[xor_assoc_property]
      simp[xor_self_inverse]
      simp[xor_comm_property]
      simp[xor_show_identity]

これで、本に従ってワンタイムパッドを Shannon Cipher として定義する作業が完了しました。これで、暗号化の本を手に取り、その内容を Lean で実装する方法が(少し)わかりました。これは非常にクールではありませんか?

[画像]

さて、チュートリアルのパート 2 で完全なセキュリティを証明するために、もう少しクリーンにしておきましょう。(この作業はすぐに開始します™)

xor を定義する前に namespace BitString を追加したことを思い出してください。これは、Lean が xor を既に実装されている関数と解釈して、自動的に物事を解決し始めるのを防ぐためでした。名前空間は、その中で定義したすべてのものをコレクションとして作成します。この場合、BitString の「コレクション」に xor が含まれるのは理にかなっていますが、ShannonCipher や OneTimePad の定義は含まれません。

このままにしておくと、新しいファイルを追加して OTP 定義を参照したい場合、BitString.OneTimePad のようになります。クリーンではありません!

これを解決するには、xor 補題の後に次を追加します。

end BitString

次に、以前定義した機能を使用するために、OneTimePad 定義の前に次を追加します。

open BitString

すると、完全なコードは次のようになります。

import Mathlib.Data.ZMod.Basicdef BitString (L: ℕ): Type := Vector (ZMod 2) Lnamespace BitStringdef xor {L: ℕ} (x y: BitString L): (BitString L) :=  Vector.zipWith (fun a b => a + b) x y-- commutativitylemma xor_comm_property {L: ℕ} (x y : BitString L) : xor x y = xor y x :=    by      apply Vector.ext      intro i h_i_lt_L      simp[xor]      simp[add_comm]-- associativitylemma xor_assoc_property {L: ℕ} (x y z: BitString L) : xor x (xor y z) = xor (xor x y) z :=  by    apply Vector.ext    simp[xor, add_assoc]def BitString_ID {L: ℕ} : BitString L := Vector.replicate L 0-- identitylemma xor_show_identity {L: ℕ} (x: BitString L): xor x BitString_ID = x :=  Vector.ext fun i i_less_than_L => by simp [xor, BitString_ID]-- self-inverselemma xor_self_inverse {L: ℕ} (x: BitString L): xor x x = BitString_ID :=  by    apply Vector.ext    intro i i_less_than_L    simp[xor, BitString_ID]    exact CharTwo.add_eq_zero.mpr rflend BitStringstructure ShannonCipher (K M C: Type) where  enc: K → M → C  dec: K → C → M  correctness: ∀ k m, dec k (enc k m) = mopen BitStringdef OneTimePad (L: ℕ ): ShannonCipher (BitString L) (BitString L) (BitString L) :={  enc k m := xor k m  dec k c := xor k c  correctness :=    by      simp[xor_assoc_property]      simp[xor_self_inverse]      simp[xor_comm_property]      simp[xor_show_identity]}

チュートリアルをフォローした場合は、どう思ったか教えてください。パート 2 のために私に促してください。LinkedIn または Twitter 経由で。

エピローグ: ブロックチェーンにおける形式検証について

最近、ブロックチェーンの世界で形式検証の取り組みについて耳にしたことがあるかもしれません。例えば、Zcash は、重大なバグが発見された後、開発チーム Shielded Labs が Orchard サーキットを形式的に検証することを目指していると発表しました。Ethereum の次のアップグレード提案セットに取り組んでいる lean Ethereum チーム(別の「lean」)は、構築中の zkVM を形式的に検証することを目指しています。Nethermind は昨年、Succinct の SP1 のチップの 1 つを Lean で形式的に検証しました。

最近数ヶ月で、Vitalik と zkSecurity はこのトピックに関する優れたブログ記事を公開しました。Yoichi Hirai (zkSecurity) による『The Final Form of Software Development』は、AI エージェントが RISC-V アセンブリコードを書き、そのコードの正しさのために Lean で証明を伴うワークフローを説明しています。そして、Vitalik のブログ記事 は、形式検証とは何か、そしてそれをソフトウェア、特に Ethereum を改善するためにどのように実際に使用できるかについて論じています。

形式検証は、私たちが使用するシステムにより大きな信頼を持つことを助けることができます。しかし、それは「完璧な」解決策でもありません。システムに関する証明を書くとき、実際に書かれたコードと証明している定理の間には常にステップがあります。例えば、元のコードはコンパイルされ、その正確な意味を知りません。あるいは、書かれたコードをモデル化する必要があります(これは誤って行う可能性があります)。

コードの形式検証の文脈と落とし穴、そしてそれが依然として非常に価値がある理由についてさらに学ぶには、lean Ethereum で形式検証の取り組みを主導している Alexander Hicks との zkPodcast のエピソード をお勧めします。