A shallow dive into formal verification

Special thanks to Yoichi Hirai, Justin Drake, Nadim Kobeissi and Alex Hicks for feedback and review

特别感谢 Yoichi Hirai、Justin Drake、Nadim Koheissi 和 Alex Hicks 的反馈和审核

Over the last couple of months, a new programming paradigm has been rapidly gaining traction within Ethereum's frontier research and development circles, and many other corners of computing: writing code directly either in very low-level languages (eg.

在过去的几个月里，一种新的编程范式在以太坊的前沿研究和开发圈以及计算的许多其他领域迅速受到关注：用非常低级的语言（例如，直接编写代码）。

EVM bytecode, assembly language) or in Lean, and verifying its correctness with automatically-checkable mathematical proofs written in Lean.

EVM 字节码、汇编语言）或精益，并使用精益编写的可自动检查的数学证明来验证其正确性。

If done right, this has potential to both output extremely efficient code, and be far more secure than the way programming has been done before.

如果做得好，这有可能输出极其高效的代码，并且比以前的编程方式安全得多。

Yoichi Hirai calls this the " final form of software development ".

平井阳一 (Yoichi Hirai) 将此称为“软件开发的最终形式”。

This post will attempt to demystify the basics of what is going on here, what formal verification of software can do, and where its weaknesses and limits are, in Ethereum and beyond.

这篇文章将试图揭开以太坊及其他领域的基础知识，包括软件的形式化验证可以做什么，以及它的弱点和限制在哪里。

Formal verification refers to writing proofs of mathematical theorems in such a way that these theorems can be checked automatically.

形式验证是指以可以自动检查这些定理的方式编写数学定理的证明。

To give a reasonably simple but still interesting example, let's take a basic theorem about the Fibonacci sequence: every third number is even, the others are odd.

为了给出一个相当简单但仍然有趣的例子，让我们看一个关于斐波那契数列的基本定理：每三个数字都是偶数，其他数字都是奇数。

1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 ...

1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 ...

A simple way to prove this is proof by induction , walking forward three at a time.

证明这一点的一个简单方法是通过归纳法证明，一次向前走三个。

First, the base case.

首先，基本情况。

Let F 1 = F 2 = 1 and F 3 = 2.

令 F 1 = F 2 = 1 且 F 3 = 2。

By inspection, we see that the statement ("F i is even for multiples of 3, odd otherwise") is true, up to x = 3 .

通过检查，我们看到语句（“对于 3 的倍数，F i 是偶数，否则是奇数”）是正确的，直到 x = 3 。

Now, the inductive case.

现在，归纳案例。

Assume that the statement is true up to 3k+3 , ie.

假设该陈述在 3k+3 以内为真，即。

we already know that F 3k+1 , F 3k+2 , F 3k+3 are odd, odd, even.

我们已经知道 F 3k+1 、 F 3k+2 、 F 3k+3 是奇数、奇数、偶数。

We can compute the parity of the next triple:

我们可以计算下一个三元组的奇偶校验：

Thus, we've gone from knowing that the statement is true up to 3k+3 , to knowing that the statement is true up to 3k+6 .

因此，我们从知道该陈述在 3k+3 以内为真，到知道该陈述在 3k+6 以内为真。

We can apply this inference over and over again, and thereby be sure that the rule holds for all integers.

我们可以一遍又一遍地应用这个推论，从而确保该规则适用于所有整数。

This argument is convincing to a human.

这个论点对于人类来说是有说服力的。

But what if you want to prove something a hundred times more complicated, and you want to be really really sure you didn't make a mistake?

但是，如果您想证明复杂一百倍的事情，并且想非常确定自己没有犯错误怎么办？

Well, you can make a proof that is convincing to a computer.

好吧，你可以做出一个对计算机来说有说服力的证明。

It's the same reasoning, but expressed in Lean , a programming language often used for writing and verifying mathematical proofs.

这是相同的推理，但用 Lean 表达，这是一种通常用于编写和验证数学证明的编程语言。

This looks different than the "human" proof I gave above, and for good reason: what is intuitive to a computer (in the old sense of "computer" - a "deterministic" program made up of if/then statements - not an LLM) is very different from what is intuitive to a human.

这看起来与我上面给出的“人类”证明不同，并且有充分的理由：计算机的直觉（在“计算机”的旧意义上 - 由 if/then 语句组成的“确定性”程序 - 不是法学硕士）与人类的直觉非常不同。

In the above proof, you're not highlighting the fact that fib(3k+4) = fib(3k+3) + fib(3k+2) , rather you're highlighting the fact that fib(3k+3) + fib(3k+2) is odd, and Lean's appropriately grandiosely-named omega tactic automatically combines that with its knowledge about the definition of fib(3k+4) .

在上面的证明中，您没有强调 fib(3k+4) = fib(3k+3) + fib(3k+2) 的事实，而是强调 fib(3k+3) + fib(3k+2) 是奇怪的事实，而 Lean 恰当地冠冕堂皇的 omega 策略自动将其与其有关 fib(3k+4) 定义的知识结合起来。

In more complicated proofs, you sometimes have to explicitly specify at each step what law of mathematics allows you to take the step you're taking, sometimes with obscure names like Prod.mk.inj .

在更复杂的证明中，您有时必须在每一步明确指定什么数学定律允许您采取您正在采取的步骤，有时使用诸如 Prod.mk.inj 之类的晦涩名称。

But on the other hand, you can expand huge polynomial expressions in one step, and justify it simply by writing single-line expressions like "omega" or "ring".

但另一方面，您可以一步展开巨大的多项式表达式，并通过编写单行表达式（例如“omega”或“ring”）来简单地证明它的合理性。

The unintuitiveness and tediousness here is a big part of why, despite the existence of machine-verifiable proofs for almost 60 years , the area has remained niche.

尽管机器可验证的证据已经存在了近 60 年，但该领域仍然处于小众地位，其中的不直观和乏味是一个重要原因。

But on the other hand, a lot of formerly impossible things are now rapidly becoming possible, thanks to the rapid progress of AI.

但另一方面，由于人工智能的快速进步，许多以前不可能的事情现在正在迅速变得可能。

So far you might be thinking: okay, so we can have computers verify proofs about mathematical theorems, so we finally know for sure which of our crazy new results about prime numbers or whatever are true, and which are just mistakes inside hundred-page long pdf papers.

到目前为止，您可能会想：好吧，这样我们就可以让计算机验证数学定理的证明，这样我们终于可以确定关于素数或其他什么的疯狂新结果中哪些是真实的，哪些只是数百页长的 pdf 论文中的错误。

Maybe we'll even figure out if Shinichi Mochizuki is right about the ABC conjecture !

也许我们甚至会弄清楚望月新一的 ABC 猜想是否正确！

But aside from curiosity value, so what?

但除了好奇心价值之外，那又怎样呢？

There are many possible answers.

有很多可能的答案。

But one answer that is very dear to me, is verifying correctness of computer programs , especially programs that are doing anything cryptographic or security-related.

但我非常喜欢的一个答案是验证计算机程序的正确性，尤其是执行任何与加密或安全相关的程序。

After all, a computer program is a mathematical object, and so proving that a computer program behaves in a certain way is a mathematical theorem.

毕竟，计算机程序是一个数学对象，因此证明计算机程序以某种方式运行就是一个数学定理。

Suppose, for example, you wanted to prove whether or not an encrypted messenger like Signal is actually secure.

例如，假设您想证明像 Signal 这样的加密信使是否确实安全。

You could write down what "secure" mathematically means in this context.

您可以写下在此上下文中“安全”的数学含义。

At a high level, you're proving that, assuming some cryptographic assumptions are true, only someone who has the private key can learn anything about the contents of the messages.

在较高的层面上，您证明，假设某些加密假设成立，只有拥有私钥的人才能了解有关消息内容的任何信息。

In reality, there are many different security properties that matter.

事实上，有许多不同的安全属性都很重要。

Well, as it turns out, there is a group trying to figure out exactly this !

好吧，事实证明，有一个小组正试图弄清楚这一点！

This is what one of their security theorems looks like:

他们的安全定理之一如下所示：

The passive_secrecy_le_ddh theorem is a tight reduction showing that X3DH's passive message secrecy is at least as hard as the DDH assumption under the Random Oracle Model.

Passive_secrecy_le_ddh 定理是一个严格约简，表明 X3DH 的被动消息保密性至少与随机预言模型下的 DDH 假设一样困难。

If an adversary can break X3DH's passive message secrecy, then they can also break DDH.

如果对手可以破解 X3DH 的被动消息保密性，那么他们也可以破解 DDH。

Since DDH is assumed to be hard, X3DH is also secure against passive attacks.

由于假定 DDH 是硬的，因此 X3DH 也能安全地抵御被动攻击。

This theorem proves that if an adversary can passively observe Signal's key exchange messages, they cannot distinguish the resulting session key from a random key with better than negligible probability.

该定理证明，如果对手可以被动地观察 Signal 的密钥交换消息，他们就无法以大于可忽略的概率区分生成的会话密钥和随机密钥。

If you combine this with a proof that the AES encryption is implemented correctly, you get a proof that the Signal protocol's encryption is secure against passive attackers.

如果将此与 AES 加密已正确实施的证明结合起来，您将获得信号协议的加密可安全抵御被动攻击者的证明。

Similar verification projects exist that prove secure implementations of TLS and other pieces of in-browser cryptography.

存在类似的验证项目，可以证明 TLS 和其他浏览器内加密技术的安全实现。

If you formally verify end-to-end , then you are proving not just that some description of the protocol is secure in theory, but that the specific piece of code that the user runs is secure in practice.

如果您正式验证端到端，那么您不仅证明了协议的某些描述在理论上是安全的，而且证明了用户运行的特定代码片段在实践中是安全的。

And from a user's perspective, this greatly improves trustlessness : in order to fully trust the code, you don't need to check over the entire code, you simply need to check over the statements that are proven about it.

从用户的角度来看，这极大地提高了去信任性：为了完全信任代码，您不需要检查整个代码，您只需检查已证明的语句即可。

Now, there are some big important asterisks to keep in mind here, particularly with regard to what that all-important word "secure" actually means.

现在，这里需要记住一些重要的星号，特别是关于最重要的词“安全”的实际含义。

It's very easy to forget to prove the claims that are actually important.

人们很容易忘记证明那些真正重要的主张。

It's very easy to find situations where there is no simpler description of the claims that need to be proven than the code itself.

很容易发现没有比代码本身更简单的需要证明的声明的描述的情况。

It's very easy to sneak in assumptions into the proofs that end up not actually true.

很容易在证明中加入一些假设，但结果实际上并不正确。

And it's very easy to decide that only one part of the system really needs to be formally proven, but then still get hit by a critical bug in the other parts (or even hardware).

而且很容易决定系统只有一个部分确实需要进行正式证明，但随后仍然会受到其他部分（甚至硬件）中的严重错误的影响。

Even the Lean implementation itself can have bugs.

即使是精益实施本身也可能存在错误。

But before we talk about all of these annoying nuances, let's first dig deeper into the kind of utopia that formal verification done ideally and correctly could potentially bring.

但在我们讨论所有这些恼人的细微差别之前，让我们首先深入探讨理想且正确地完成形式验证可能带来的乌托邦。

Bugs in computer code become more scary when you put cryptocurrency into immutable onchain smart contracts from which North Korea can automatically drain all your money with no recourse if there's a bug in the code.

当你将加密货币放入不可变的链上智能合约中时，计算机代码中的错误变得更加可怕，如果代码中存在错误，朝鲜可以自动耗尽你所有的钱，而没有追索权。

Bugs in computer code become even more scary when this all gets wrapped in zero-knowledge proofs, so if someone manages to hack the zero-knowledge proof system, they can extract all the money, and we have no idea what went wrong - or worse, when something has gone wrong.

当这一切都包含在零知识证明中时，计算机代码中的错误变得更加可怕，因此，如果有人设法破解零知识证明系统，他们就可以提取所有资金，而我们不知道出了什么问题 - 或者更糟糕的是，当出现问题时。

Bugs in computer code become even even more scary when we have powerful AI models, like Claude Mythos but after two more years of improvement, that can automate discovering them.

当我们拥有强大的人工智能模型（例如克劳德神话）时，计算机代码中的错误变得更加可怕，但经过两年多的改进，可以自动发现它们。

Some people are responding to this reality by advocating giving up on the fundamental idea of smart contracts, or even that the cyber domain even can be a domain where defenders can have an asymmetric advantage against attackers.

一些人通过主张放弃智能合约的基本理念来应对这一现实，甚至认为网络领域甚至可以成为防御者可以对攻击者拥有不对称优势的领域。

to harden a system you need to spend more tokens discovering exploits than attackers will spend exploiting them

要强化系统，您需要花费比攻击者利用它们花费更多的代币来发现漏洞

We built our profession around deterministic code.

我们围绕确定性代码建立了我们的职业。

Write it, test it, ship it, know it works - but in my experience that contract is breaking.

编写它、测试它、发布它、知道它有效——但根据我的经验，合同正在被破坏。

Inside the top few percent of operators at truly AI-native companies, the codebase has started to become something you believe works, with a probability you can no longer precisely state.

在真正的人工智能原生公司的前几%的操作员中，代码库已经开始成为你认为有效的东西，你可能无法再准确地说明这一点。

Worse, some think that the only solution is to give up on open source .

更糟糕的是，有些人认为唯一的解决办法就是放弃开源。

This would be a bleak future for cybersecurity.

对于网络安全来说，这将是一个黯淡的未来。

It's especially an extremely bleak future for those of us who care about internet decentralization and freedom.

对于我们这些关心互联网去中心化和自由的人来说，这是一个极其黯淡的未来。

The entire cypherpunk ethos is fundamentally based on the idea that on the internet, the defender has an advantage: it's much easier to build a digital "castle" (whether that means encryption, signatures or proofs) than to destroy one.

整个密码朋克精神从根本上来说是基于这样一种理念：在互联网上，防御者具有优势：建造一座数字“城堡”（无论这意味着加密、签名还是证明）比摧毁一座要容易得多。

If we lose that, then internet security can only come from economies of scale, from going all over the world to chase down possible attackers, and more generally from a binary choice between domination and doom.

如果我们失去了这一点，那么互联网安全只能来自规模经济，来自遍布世界各地追捕可能的攻击者，更普遍地来自统治与厄运之间的二元选择。

I disagree, and I have a much more optimistic vision of the future of cybersecurity.

我不同意，而且我对网络安全的未来抱有更加乐观的看法。

I think the challenge brought by powerful AI bug-finding is a serious challenge, but it is a transitional challenge.

我认为强大的人工智能查错带来的挑战是一个严峻的挑战，但它是一个过渡性的挑战。

Once the dust settles and we get into the new equilibrium, we will get to something far more defense-favoring than what we had before.

一旦尘埃落定，我们进入新的平衡，我们将得到比以前更有利于防御的东西。

You may need to reprioritize everything else to bring relentless and single-minded focus to the task, but there is light at the end of the tunnel.

你可能需要重新安排其他事情的优先顺序，以不懈地、一心一意地专注于任务，但隧道尽头总会有光明。

We are extremely proud of how our team rose to meet this challenge, and others will too.

我们对我们的团队如何应对这一挑战感到非常自豪，其他人也会如此。

Our work isn't finished, but we've turned the corner and can glimpse a future much better than just keeping up.

我们的工作尚未完成，但我们已经度过了难关，并且可以看到比仅仅跟上更好的未来。

Defenders finally have a chance to win, decisively.

防守者终于有机会获胜，而且是决定性的。

The defects are finite, and we are entering a world where we can finally find them all.

缺陷是有限的，我们正在进入一个最终可以找到所有缺陷的世界。

Now, if you Ctrl+F for the words "formal" and "verification" in Mozilla's post, you will find zero hits for either.

现在，如果您在 Mozilla 的帖子中按 Ctrl+F 键输入“正式”和“验证”一词，您会发现其中任何一个的点击率都是零。

The positive future of cybersecurity does not strictly depend on formal verification, or for that matter any other single technology.

网络安全的积极未来并不严格依赖于形式验证，或任何其他单一技术。

There are many technologies that have contributed to number go down over the decades:

几十年来，有许多技术导致了数字下降：

Formal verification, aided by AI, should be viewed not as totally new paradigm, but as a powerful accelerant of a trend and a paradigm that was already marching forward.

在人工智能的帮助下，形式化验证不应被视为全新的范式，而应被视为趋势和已经向前发展的范式的强大促进剂。

Formal verification is not a panacea.

形式验证并不是万能的。

But it is particularly well-suited for situations where the goal is much simpler than the implementation .

但它特别适合目标比实现简单得多的情况。

This is particularly true in some of the most devilishly hard pieces of technology that we will need to deploy in the next major iteration of Ethereum : quantum-resistant signatures, STARKs, consensus algorithms, and ZK-EVMs.

在我们需要在以太坊的下一个主要迭代中部署的一些最困难的技术中尤其如此：抗量子签名、STARK、共识算法和 ZK-EVM。

A STARK is a very complex piece of software .

STARK 是一个非常复杂的软件。

But the core security property that it achieves is simple to understand and formalize: if you see a proof that points to a hash H of program P , input x , and output y , then either (i) the hash algorithm used in the STARK is broken, or (ii) P(x) = y .

但它实现的核心安全属性很容易理解和形式化：如果您看到一个指向程序 P 、输入 x 和输出 y 的哈希 H 的证明，那么要么 (i) STARK 中使用的哈希算法被破坏，要么 (ii) P(x) = y 。

And so we have the Arklib project, which is trying to create a fully formally-verified implementation of a STARK (see also, VCV-io , which provides the foundational oracle computation infrastructure that can be used to formally verify all kinds of other cryptographic protocols, many of which are dependencies in a STARK).

因此，我们有了 Arklib 项目，它试图创建一个经过完全正式验证的 STARK 实现（另请参阅 VCV-io，它提供了基础的预言机计算基础设施，可用于正式验证各种其他加密协议，其中许多是 STARK 中的依赖项）。

is formally-verifying all kinds of other cryptographic algorithms, many of which are dependencies in a STARK).

正在正式验证各种其他加密算法，其中许多是 STARK 中的依赖项）。

Even more ambitious is evm-asm : a project building an entire EVM implementation that is formally verified.

更雄心勃勃的是 evm-asm：一个构建经过正式验证的完整 EVM 实现的项目。

Here, the security property is not so clean: basically, the goal is to prove equivalence to a different implementation of the EVM written in Lean - though the implementation can be written to maximize intuitiveness and readability without regard for concrete efficiency.

在这里，安全属性并不那么清晰：基本上，目标是证明与用 Lean 编写的 EVM 的不同实现的等效性 - 尽管可以编写实现以最大化直观性和可读性，而不考虑具体效率。

It's possible that we'll have ten implementations of the EVM, all provably equivalent to each other, all with the same fatal flaw that somehow lets an attacker drain all the ETH from an address they have no permissions for.

我们可能会有十种 EVM 实现，所有这些都被证明是等效的，都具有相同的致命缺陷，以某种方式让攻击者从他们没有权限的地址中耗尽所有 ETH。

But that's vastly less likely than one EVM implementation having that kind of flaw today.

但与目前存在此类缺陷的 EVM 实现相比，这种情况的可能性要小得多。

And another security property whose importance we came to understand only after painful experience , DoS resistance, is easy to specify .

另一个安全属性（DoS 抵抗）是很容易指定的，我们只有在经历了痛苦的经历之后才认识到其重要性。

A huge part of the value-add in all of these cases is that the proofs are truly end-to-end.

在所有这些情况下，增值的很大一部分是证明是真正的端到端的。

Often, the nastiest bugs are interaction bugs, that sit at the edge of two sub-systems that are considered separately.

通常，最严重的错误是交互错误，它们位于单独考虑的两个子系统的边缘。

For a human, it's too difficult to reason about the entire system end-to-end.

对于人类来说，端到端地推理整个系统太困难了。

But an automated rule-checking system can.

但自动规则检查系统可以。

Let's look again at evm-asm .

让我们再看看 evm-asm 。

This is an EVM implementation.

这是一个 EVM 实现。

But it's an EVM implementation written directly in RISC-V assembly .

但它是直接用 RISC-V 汇编语言编写的 EVM 实现。

RISC-V was chosen because the ZK-EVM provers being built generally work by proving RISC-V and compiling Ethereum clients to RISC-V.

选择 RISC-V 是因为正在构建的 ZK-EVM 证明器通常通过证明 RISC-V 并将以太坊客户端编译为 RISC-V 来工作。

So if you have an EVM implementation written in RISC-V directly, this should be the fastest possible implementation that you can get.

因此，如果您有直接用 RISC-V 编写的 EVM 实现，这应该是您可以获得的最快的实现。

RISC-V can also be emulated inside regular computers very efficiently (and RISC-V laptops exist ).

RISC-V 也可以在普通计算机内非常有效地进行模拟（并且存在 RISC-V 笔记本电脑）。

Of course, to be truly end-to-end, you have to formally verify the RISC-V implementation (or prover arithmetization) itself, but don't worry - that exists too .

当然，要实现真正的端到端，您必须正式验证 RISC-V 实现（或证明者算术）本身，但不用担心 - 这也存在。

Writing code directly in assembly is the sort of thing we used to do all the time, fifty years ago.

五十年前，我们经常用汇编语言直接编写代码。

Since then, we've moved away from that, toward writing code in high-level languages.

从那时起，我们就不再这样做，转而使用高级语言编写代码。

High-level languages take a penalty in efficiency, but in exchange they are must faster to write code in, and importantly, much faster to understand other people's code - a necessary thing for security.

高级语言会降低效率，但作为交换，它们必须更快地编写代码，而且重要的是，更快地理解其他人的代码——这是安全性所必需的。

With the combination of formal verification and AI, we have an opportunity to go "back to the future".

形式化验证与人工智能的结合，让我们有机会“回到未来”。

Specifically, we have AI write the assembly, and then write a formal proof verifying that the assembly has the desired properties.

具体来说，我们让人工智能编写程序集，然后编写正式的证明来验证程序集是否具有所需的属性。

At the very least, the desired property can just be perfect equivalence to an implementation optimized for readability and written in some human-friendly high-level language.

至少，所需的属性可以完美地等同于针对可读性进行优化并用某种人类友好的高级语言编写的实现。

Instead of there being a single code object that has to balance between readability and efficiency, we have two separate objects: one (the assembly implementation) that optimizes for efficiency only, taking into account the needs of the specific environment it's executing in, and another (the security claims, or the high-level-language implementation) that optimizes for readability only, and then we have a mathematical proof that proves the equivalence between the two.

我们没有一个必须在可读性和效率之间取得平衡的代码对象，而是有两个独立的对象：一个（程序集实现）仅针对效率进行优化，考虑到其执行的特定环境的需求，另一个（安全声明或高级语言实现）仅针对可读性进行优化，然后我们有一个数学证明来证明两者之间的等价性。

A user can (automatically) verify this proof once, and then from that point forward, they just run the fast version.

用户可以（自动）验证此证明一次，然后从那时起，他们只需运行快速版本。

This is powerful, and there is a reason why Yoichi Hirai has called it " the final form of software development ".

这很强大，平井洋一将其称为“软件开发的最终形式”是有原因的。

There is a tradition in cryptography and computer science that is almost as old as the tradition of formal methods: the tradition of criticizing formal methods (or reliance on "proofs" more generally).

密码学和计算机科学中有一个几乎与形式方法传统一样古老的传统：批评形式方法的传统（或更普遍地依赖“证明”）。

This literature is rich with practical examples.

这些文献中有丰富的实际例子。

Let's start with hand-written proofs from the older and simpler ages of cryptography, here criticized by Menezes and Koblitz in 2004 :

让我们从更古老、更简单的密码学时代的手写证明开始，梅内泽斯和科布利茨在 2004 年对此提出了批评：

In 1979 Rabin [51] produced an encryption function that ...

1979 年，Rabin [51] 提出了一个加密函数......

was in some sense "provably" secure, that is, it had a reductionist security property.

在某种意义上是“可证明”安全的，也就是说，它具有还原论的安全属性。

Reductionist security claim.

还原论安全主张。

Someone who can find messages m from the ciphertext y must also be able to factor n.

能够从密文 y 中找到消息 m 的人也必须能够分解 n。

Soon after Rabin proposed his encryption scheme, Rivest (see [63]) pointed out that, ironically, the very feature that gave it an extra measure of security would also lead to total collapse if it were confronted with a different type of adversary, called a "chosen-ciphertext" attacker.

在 Rabin 提出他的加密方案后不久，Rivest（参见 [63]）指出，具有讽刺意味的是，如果它遇到不同类型的对手（称为“选择密文”攻击者），为其提供额外安全措施的功能也会导致彻底崩溃。

Namely, suppose that the adversary could somehow fool Alice into decrypting a ciphertext of its own choosing.

也就是说，假设对手可以以某种方式欺骗爱丽丝解密自己选择的密文。

The adversary could then follow the same procedure that Sam used in the previous paragraph to factor n.

然后，对手可以遵循 Sam 在上一段中使用的相同程序来分解 n。

Menezes and Koblitz proceed to give a few more examples.

梅内塞斯和科布利茨继续举了几个例子。

The common pattern: designing cryptographic protocols around making them more "provable" often makes them less "natural", which makes it more likely that they break down in some situation that the designer did not even consider.

常见的模式是：围绕使加密协议更加“可证明”而设计，通常会使它们变得不那么“自然”，这使得它们更有可能在设计者甚至没有考虑到的某些情况下崩溃。

Now, let's go back to machine-verifiable proofs and code.

现在，让我们回到机器可验证的证明和代码。

Here's a paper from 2011 finding bugs in formally verified C compilers :

这是 2011 年发表的一篇论文，发现了经过正式验证的 C 编译器中的错误：

The second CompCert problem we found was illustrated by two bugs that resulted in generation of code like this:

我们发现的第二个 CompCert 问题是通过两个错误来说明的，这些错误导致生成如下代码：

Here, a large PowerPC stack frame is being allocated.

这里，正在分配一个大的 PowerPC 堆栈帧。

The problem is that the 16-bit displacement field is overflowed.

问题是16位位移字段溢出。

CompCert's PPC semantics failed to specify a constraint on the width of this immediate value, on the assumption that the assembler would catch out-of-range values.

CompCert 的 PPC 语义未能指定对此立即值的宽度的约束，假设汇编器会捕获超出范围的值。

In CompCert-KVX, commit e2618b31 fixed a bug— "nand" instructions would be printed as "and"; "nand" is selected only for the rare ~(a & b) pattern.

在 CompCert-KVX 中，提交 e2618b31 修复了一个错误——“nand”指令将被打印为“and”；仅针对罕见的 ~(a & b) 模式选择“nand”。

The bug was found by compiling randomly generated programs.

该错误是通过编译随机生成的程序发现的。

And today, in 2026, here's Nadim Kobeissi describing vulnerabilities in formally-verified software in Cryspen:

2026 年的今天，Nadim Koheissi 描述了 Cryspen 中经过正式验证的软件中的漏洞：

In November 2025, Filippo Valsorda independently reported [50] that libcrux-ml- dsa v0.0.3 produced different public keys and signatures on different platforms given identical deterministic inputs.

2025 年 11 月，Filippo Valsorda 独立报告 [50]，libcrux-ml-dsa v0.0.3 在给定相同的确定性输入的情况下在不同平台上生成了不同的公钥和签名。

The bug resided in the _vxarq_u64 intrin- sic wrapper (Listing 1.1), which implements the XAR operation used in SHA-3's Keccak-f permutation.

该错误存在于 _vxarq_u64 内在包装器中（清单 1.1），该包装器实现了 SHA-3 的 Keccak-f 排列中使用的 XAR 操作。

The fallback passed incorrect arguments to the shift oper- ations, corrupting SHA-3 digests on ARM64 platforms without hardware SHA-3 support.

回退将错误的参数传递给移位操作，从而在没有硬件 SHA-3 支持的情况下破坏了 ARM64 平台上的 SHA-3 摘要。

This is a Type I failure: the intrinsic was marked [1] , and the entire NEON backend had no completed proofs for runtime safety or correctness

这是 I 类故障：内在标记为 [1] ，并且整个 NEON 后端没有完整的运行时安全性或正确性证明

The libcrux-psq crate [13] implements a post-quantum pre-shared-key protocol.

libcrux-psq 箱 [13] 实现了后量子预共享密钥协议。

In the decrypt_out method, the AES-GCM 128 decryption path calls .unwrap() on the decryption result instead of propagating the error (Listing 1.3).

在decrypt_out方法中，AES-GCM 128解密路径对解密结果调用.unwrap()，而不是传播错误（清单1.3）。

A single malformed ciphertext crashes the process

单个格式错误的密文会导致进程崩溃

Nadim's post contains a categorization of formal verification of failure modes; he also gives other types of failure modes (eg.

Nadim 的帖子包含故障模式的形式验证的分类；他还给出了其他类型的故障模式（例如。

another major one is situations where "the formal specification itself is wrong, or the proofs contain false claims that are silently accepted by the build system").

另一个主要问题是“正式规范本身是错误的，或者证明包含构建系统默默接受的虚假声明”）。

Finally, we can look at formal verification failures at the boundary of software and hardware.

最后，我们可以看看软件和硬件边界上的形式验证失败。

A common issue here is verifying side-channel attack resistance.

这里的一个常见问题是验证侧信道攻击抵抗力。

Even if you have a perfectly secure form of encryption protecting your messages, if someone a few meters away can pick up on electrical fluctuations and extract your private key after a few hundred thousand encryptions, you're still insecure.

即使您有完全安全的加密形式来保护您的消息，如果几米外的人可以感知到电力波动并在数十万次加密后提取您的私钥，您仍然不安全。

Here's an article on "differential power analysis" , a now well-understood example of such a technique.

这是一篇关于“差分功率分析”的文章，这是这种技术现在广为人知的示例。

Differential power analysis is a common type of side channel attack.

差分功率分析是一种常见的侧信道攻击类型。

Source: Wikipedia

资料来源：维基百科

There have been attempts to prove security against such attackers.

人们已经尝试证明针对此类攻击者的安全性。

However, any such proof requires some kind of mathematical model of an attacker, that you can prove security against.

然而，任何此类证明都需要攻击者的某种数学模型，您可以证明其安全性。

Sometimes, the "d-probing model" is used: we assume there is a known limit on how many locations in a circuit an attacker can query.

有时，会使用“d-探测模型”：我们假设攻击者可以查询电路中的位置数量存在已知限制。

However, there are forms of leakage that such a model does not capture.

然而，这种模型无法捕捉到某些形式的泄漏。

A common issue, observed in this article , is transitional leakage : if you can observe a signal that depends not on the value at a location but on the change in that value, then often that is enough to recover the information you need from two values (the old and the new) rather than just one.

本文中观察到的一个常见问题是过渡泄漏：如果您可以观察到一个信号，该信号不依赖于某个位置的值，而是依赖于该值的变化，那么通常足以从两个值（旧值和新值）而不是仅从一个值恢复所需的信息。

This article gives a taxonomy of other forms of leakage.

本文对其他形式的泄漏进行了分类。

These lines of criticism of formal verification have, over the decades, helped to make formal verification much better.

几十年来，这些对形式验证的批评有助于使形式验证变得更好。

We are much better at watching out for these kinds of issues than we used to be.

我们比以前更善于关注此类问题。

But even today, it's not perfect.

但即使在今天，它也并不完美。

Zooming out, there is a common thread here.

缩小范围，这里有一个共同点。

Formal verification is powerful.

形式化验证是强大的。

But regardless of the marketing that makes it sound like formal verification gives you "provable correctness", so-called "provable correctness" fundamentally does not prove that software (or hardware) is "correct" .

但不管营销如何让形式验证听起来像是“可证明的正确性”，所谓的“可证明的正确性”从根本上来说并不能证明软件（或硬件）是“正确的”。

As understood by most human beings, "correct" means something like: "the behavior of the thing matches the user's understanding of the developer's intentions".

正如大多数人所理解的，“正确”意味着：“事物的行为符合用户对开发者意图的理解”。

And "secure" means something like: "the behavior of the thing does not deviate from the user's expectations in a way that is adverse to the user's interests".

而“安全”的意思是：“事物的行为不会以不利于用户利益的方式偏离用户的期望”。

In both cases, correctness and security boil down to a comparison between a mathematical object and human intention or expectation .

在这两种情况下，正确性和安全性都归结为数学对象与人类意图或期望之间的比较。

Human intention and expectation are technically mathematical objects - after all, human brains are part of the universe, which follows laws of physics that you could simulate if you had enough compute.

人类的意图和期望从技术上讲是数学对象——毕竟，人类大脑是宇宙的一部分，它遵循物理定律，如果你有足够的计算能力，你就可以模拟这些定律。

But they are incredibly complex mathematical objects, that neither computers or we ourselves can understand or even read.

但它们是极其复杂的数学对象，计算机或我们自己都无法理解甚至阅读。

For all intents and purposes, they are black boxes; we only understand anything about our intentions and expectations at all because we each have many years of experience observing our own thoughts and making inferences about the thoughts of others.

无论如何，它们都是黑匣子；我们只了解自己的意图和期望，因为我们每个人都有多年观察自己的想法并推断他人的想法的经验。

And because we cannot stick raw human intention inside a computer, formal verification has no way to prove comparisons against human intentions.

而且由于我们无法将人类的原始意图植入计算机中，因此形式验证无法证明与人类意图的比较。

And so, "provable correctness" and "provable security" are not, in fact, proving what we human beings understand by "correctness" and "security" - until we can simulate human brains, nothing can .

所以，“可证明的正确性”和“可证明的安全性”实际上并不是证明我们人类所理解的“正确性”和“安全性”——在我们能够模拟人脑之前，没有什么可以做到的。

I like to view test suites, type systems and formal verification, as all being different implementations of the same underlying approach to programming language safety - probably the only approach that makes any sense.

我喜欢查看测试套件、类型系统和形式验证，因为它们都是同一底层编程语言安全方法的不同实现——可能是唯一有意义的方法。

They are all about redundantly specifying our intentions in different ways, and then automatically checking that these different specifications are compatible with each other .

它们都是以不同的方式冗余地指定我们的意图，然后自动检查这些不同的规范是否彼此兼容。

Here, you are expressing your intention in three different ways:

在这里，您以三种不同的方式表达您的意图：

Running the file checks the formula against the examples.

运行该文件根据示例检查公式。

A type checker can verify that the types are compatible: adding two integers together is a valid thing to do, and produces another integer.

类型检查器可以验证类型是否兼容：将两个整数相加是有效的操作，并生成另一个整数。

Type systems are often a good way to check your work in physics: if you are computing an acceleration, and you get an answer whose units are \(\frac{m}{s}\) and not \(\frac{m}{s^2}\) , you know you've done something wrong.

类型系统通常是检查物理学工作的好方法：如果您正在计算加速度，并且得到的答案的单位是 \(\frac{m}{s}\) 而不是 \(\frac{m}{s^2}\) ，那么您就知道自己做错了。

And a bag-of-examples "definition", which test cases are an instance of, is often just a much more natural way for humans to deal with concepts than a direct explicit definition.

示例包“定义”（测试用例是其实例）通常是人类处理概念比直接显式定义更自然的方式。

The more different ways in which you can specify your intent, ideally very different ways that require you to approach the issue with different styles of thinking, the more likely it is that, if all of those expressions prove compatible with each other, you actually expressed the thing that you wanted.

你可以用越多不同的方式来表达你的意图，最好是非常不同的方式，要求你用不同的思维方式来处理问题，如果所有这些表达方式都证明彼此兼容，那么你实际上表达了你想要的东西的可能性就越大。

Safe programming is about expressing your intention in multiple different ways, and then automatically verifying that the expressions are all compatible with each other.

安全编程就是用多种不同的方式表达你的意图，然后自动验证这些表达方式是否彼此兼容。

Formal verification lets you extend this approach even further.

形式验证可以让您进一步扩展这种方法。

With formal verification, you can specify your intent in an almost arbitrary number of different redundant ways, and the program only verifies if they are all compatible .

通过形式化验证，您可以用几乎任意数量的不同冗余方式指定您的意图，并且程序仅验证它们是否全部兼容。

You can specify an optimized implementation and a very inefficient but human-readable implementation, and verify that they match.

您可以指定一个优化的实现和一个效率非常低但人类可读的实现，并验证它们是否匹配。

You can ask ten of your friends to provide lists of mathematical properties that your program should have, and then check if it passes them all - and if it doesn't, figure out if the program is wrong or the mathematical property.

您可以要求十个朋友提供您的程序应具有的数学属性列表，然后检查它是否通过所有这些数学属性 - 如果没有，请找出程序是否错误或数学属性。

And you can use AI to do all of the above extremely efficiently.

您可以使用人工智能非常高效地完成上述所有工作。

Realistically, you won't be writing proofs yourself.

实际上，您不会自己编写证明。

The entire reason why formal methods have not taken off is that most people can't wrap their heads around writing the damn things.

正式方法没有流行起来的全部原因是大多数人无法专心致志地写出那些该死的东西。

Can you tell me what the code below means?

你能告诉我下面的代码是什么意思吗？

(If you want to know, it's one of the many sub-lemmas in this proof of one particular security claim about a variant of SPHINCS signaures - namely, that, unless there is a hash collision, a signature for one message will require a value higher up on at least one hash ladder than a signature for any other message - and hence requires information that cannot be computed from that other signature)

（如果您想知道，这是关于 SPHINCS 签名变体的一个特定安全声明的证明中的许多子引理之一 - 也就是说，除非存在哈希冲突，否则一条消息的签名将需要在至少一个哈希梯上比任何其他消息的签名更高的值 - 因此需要无法从该其他签名计算的信息）

Instead of writing code and proofs by hand, you ask AI to write the program for you (either writing in Lean directly, or if you want speed, writing in assembly), and prove any desired properties along the way.

您不需要手动编写代码和证明，而是要求人工智能为您编写程序（直接用精益编写，或者如果您想要速度，则用汇编编写），并沿途证明任何所需的属性。

One of the nice things about this task is that it's inherently self-verifying, and so you don't need to supervise - you can just let the AI run for hours all on its own.

这项任务的好处之一是它本质上是自我验证的，所以你不需要监督——你可以让人工智能自行运行几个小时。

The worst thing that can happen is that it will go in circles without making progress (or, as my leanstral did on one occasion, decide to make its own job easier by replacing the statement that it's asked to prove).

可能发生的最糟糕的事情是它会原地踏步而没有取得进展（或者，正如我的lestral有一次所做的那样，决定通过替换要求证明的陈述来简化自己的工作）。

The thing you need to check at the end is that the statement proven matches what you want.

最后您需要检查的是已证明的陈述是否符合您的要求。

In the SPHINCS signature variant, here's the final statement:

在 SPHICS 签名变体中，最终声明如下：

IF the digits generated from one hash digest (dig1) are not equal to the digits generated from another hash digest (dig2)

如果从一个哈希摘要 (dig1) 生成的数字不等于从另一个哈希摘要 (dig2) 生成的数字

in the "extended digits" generated by adding a checksum (wotsFullDigits).

在“扩展数字”中添加校验和（wotsFullDigits）生成。

That is, inevitably in some places the digits in the extension of dig1 will be higher and in other places the digits in the extension of dig2 will be higher.

也就是说，不可避免地在某些地方dig1 扩展名中的数字会更高，而在其他地方dig2 扩展名中的数字会更高。

For writing proofs with LLMs, I've found Claude to be sufficient, and Deepseek 4 Pro to be sufficient.

对于用法学硕士撰写证明，我发现 Claude 就足够了，而 Deepseek 4 Pro 就足够了。

Leanstral , a smaller open-weights model specifically fine-tuned for writing Lean, is a promising alternative; with 119B params, 6B active per token, you can run it locally albeit slowly (I get ~15 tok/sec on my laptop ).

Leanstral 是一个较小的开放权重模型，专门针对编写 Lean 进行了微调，是一个有前途的替代方案；具有 119B 参数，每个令牌 6B 活动，您可以在本地运行它，尽管速度很慢（我在笔记本电脑上获得约 15 tok/秒）。

According to benchmarks, Leanstral outperforms much larger general-purpose models:

根据基准测试，Leanstral 的性能优于更大的通用模型：

In my personal experience so far, it's somewhat worse than Deepseek 4 Pro, but still effective.

就我个人目前的体验来看，它比 Deepseek 4 Pro 稍差一些，但仍然有效。

Formal verification will not solve all our problems.

形式化验证并不能解决我们所有的问题。

But if we want to have a model of internet security that is not based on everyone trusting a few powerful organizations, we need to be able to instead trust code - including trusting code in the face of powerful AI adversaries.

但如果我们想要建立一个不基于每个人都信任少数强大组织的互联网安全模型，我们就需要能够信任代码——包括在面对强大的人工智能对手时信任代码。

AI-assisted formal verification lets us take large steps in doing just that.

人工智能辅助的形式验证让我们在这方面迈出了一大步。

Like blockchains and ZK-SNARKs, AI and formal verification are very complementary technologies.

与区块链和 ZK-SNARK 一样，人工智能和形式验证是非常互补的技术。

Blockchains give you open verifiability and censorship resistance at the cost of privacy and scalability, and ZK-SNARKs give you back ...

区块链为您提供开放的可验证性和抗审查性，但以隐私和可扩展性为代价，而 ZK-SNARK 则给您回馈……

privacy and scalability (in fact, even more than you had before).

隐私性和可扩展性（事实上，甚至比以前更多）。

AI gives you the ability to write large volumes of code at the cost of accuracy, and formal verification gives you back ...

人工智能使您能够以准确性为代价编写大量代码，而形式验证则给您返回......

accuracy (in fact, even more than you had before).

准确性（事实上，甚至比以前更高）。

By default, AI will enable large amounts of very sloppy code, and the number of bugs will increase.

默认情况下，人工智能会生成大量非常草率的代码，错误的数量也会增加。

Indeed, in some situations it's the correct tradeoff to let the bugs increase: if the bugs are mild, even buggy software is better than not having that software.

事实上，在某些情况下，让错误增加是正确的权衡：如果错误很轻微，即使有错误的软件也比没有该软件好。

But there is an optimistic future for cybersecurity here: software will (continue to) split into "insecure edge pieces" around a "secure core" .

但这里的网络安全有一个乐观的未来：软件将（继续）分裂成围绕“安全核心”的“不安全边缘部分”。

The insecure edge pieces will be run in sandboxes, and trusted with the minimum authority they need to do their job.

不安全的边缘部分将在沙箱中运行，并获得完成其工作所需的最低权限。

The secure core will administer everything.

安全核心将管理一切。

If the secure core breaks, everything breaks - your personal data, your money, and more.

如果安全核心损坏，一切都会损坏 - 您的个人数据、您的金钱等等。

But if some insecure edge breaks, the secure core protects you.

但如果一些不安全的边缘断裂，安全的核心就会保护您。

When it comes to the secure core, we don't let the buggy code multiply .

当涉及到安全核心时，我们不会让有缺陷的代码成倍增加。

We act aggressively to keep the size of the secure core small, and indeed even shrink it further.

我们积极采取行动，保持安全核心的尺寸较小，甚至进一步缩小。

Instead, we put the entire extra horsepower that AI brings into making the secure core more secure, so that it can handle the extremely high trust burdens we are putting on it in a highly digitized society.

相反，我们将人工智能带来的全部额外能力用于使安全核心更加安全，以便它能够处理我们在高度数字化社会中施加的极高信任负担。

The kernel of your operating system (or at least part of it) will be one such secure core.

您的操作系统的内核（或至少其一部分）将是这样的安全核心之一。

Ethereum will be another.

以太坊将是另一个。

Hopefully, the hardware you use at least for all non-performance-intensive computations will be a third.

希望您至少用于所有非性能密集型计算的硬件将是第三个。

Something involving IoT will be a fourth.

涉及物联网的事物将是第四个。

At least here in these secure cores, the old maxim that bugs are inevitable and you can only strive to find them before the attacker does will become false, replaced by a more hopeful world where you get actual security.

至少在这些安全核心中，错误是不可避免的，你只能努力在攻击者发现它们之前找到它们的古老格言将变得错误，取而代之的是一个更有希望的世界，在那里你可以获得真正的安全。

But if you want to give up your assets and data to software that is written poorly and may accidentally send it all into a black hole, well, you'll have that freedom too.

但是，如果您想将您的资产和数据放弃给编写得很差并且可能会意外地将其全部发送到黑洞的软件，那么您也将拥有这种自由。