解除 Fiat-Shamir 陷阱

Fiat-Shamir 转换是零知识证明 (ZKP) 和多方计算 (MPC) 中的一个重要组成部分。它允许基于交互式协议的零知识证明变为非交互式。本质上，它将对话转换为文档。这种能力是 SNARK 和 STARK 等强大技术的核心。非常有用的东西！

但是，与几乎任何其他密码学工具一样，Fiat-Shamir 转换比看起来更微妙，并且出错会是灾难性的。由于这类错误频繁发生，Trail of Bits 正在发布一个名为 Decree 的新工具，该工具将帮助开发人员指定其 Fiat-Shamir 记录，并使其更容易在记录输入中包含上下文信息。

Fiat-Shamir 概述

许多零知识证明都有一个通用的三步协议结构1：

1. Peggy 向 Victor 发送一组对某些值的承诺。
2. Victor 以一个随机的挑战值作为回应。
3. Peggy 回应一组既整合了步骤 (1) 中的承诺值，又整合了 Victor 的随机挑战值的值。

显然，步骤 (1) 和 (3) 的细节在不同的协议之间会有很大差异，但步骤 (2) 非常一致。这也是 Victor 必须参与的唯一部分。

如果我们可以消除 Victor 选择一个随机挑战值并将其传输给 Peggy 的整个部分，事情会变得更有效率。我们可以让 Peggy 选择，但这会给她太多的权力：在大多数协议中，如果 Peggy 可以选择挑战，她可以自定义挑战以伪造证明。更糟糕的是，即使 Peggy 无法选择挑战，但可以预测 Victor 将选择的挑战，她仍然可以自定义她对挑战的承诺以伪造证明。

Fiat-Shamir 转换允许 Peggy 生成挑战，但具有以下特点：

• Peggy 无法有意义地控制生成的挑战的结果。
• 一旦 Peggy 生成了一个挑战，她就不能修改她的承诺值。
• 一旦 Victor 拥有了承诺信息，他就可以重现 Peggy 生成的相同的挑战值。

Fiat-Shamir 转换的基本机制是将证明的所有公共部分（称为证明的记录）输入到一个哈希函数中，并使用哈希函数的输出生成挑战。我们还有另一篇 博文 更详细地描述了这一点。

拥有完整的记录对于安全地生成挑战至关重要。这意味着实施者需要清楚地指定和执行记录要求。

失败模式

我们在实践中看到几种 Fiat-Shamir 失败模式。

缺乏实现规范

我们经常观察到客户的记录是临时构建的，仅由实现指定。添加到记录中的值的列表、它们在记录中的包含顺序以及数据的格式只能通过查看代码来确定。

对于证明系统如此重要的组成部分来说，如此松散的做法是不好的，但我们在代码审查中一直看到这种情况。

不正确的形式规范

描述新的证明技术或 MPC 系统的论文必然会引用 Fiat-Shamir 转换，但这些论文的作者如何讨论这个主题会对实现的安全性产生很大的影响。

最佳情况是作者为安全地生成挑战提供详细的规范。一个简单、明确的记录值列表是最简单的，并且所有经验水平的实施者都可以访问。假设作者没有犯错，实施者有很大机会避免薄弱的 Fiat-Shamir 攻击。

当作者们挥挥手，除了说“这个协议可以使用 Fiat-Shamir 转换进行交互”之外，几乎没有说什么时，具体细节就留给了实施者。对于精通密码学、了解最新文献并了解 Fiat-Shamir 转换的细微之处的密码学家来说，这是劳动密集型的，但可行。然而，对于经验不足的开发人员来说，这是一个灾难的根源。

两全其美的情况是最糟糕的，即当作者含糊其辞，但试图给出未经证实的例子时。我们的 另一篇博文 包含了一个很好的例子：Bulletproofs 论文。作者的原始论文引用了 Fiat-Shamir 转换，并建议了挑战生成可能的样子。许多密码学家使用该示例作为其 Bulletproofs 实现的基础，但结果证明是错误的。

缺乏执行

即使存在记录规范，也很难验证该规范是否被遵循。

当今使用的证明系统和协议非常复杂。对于某些 zkSNARK，Fiat-Shamir 记录可以包括在子例程的子例程的子例程中生成的值。协议可能要求 Peggy 生成满足特定属性的值，然后才能在证明中使用，从而整合到记录中。这会导致复杂的调用树和软件中大量的条件块。在一个 “if” 块中处理的记录值很容易在相应的 “else” 块中被跳过。

此外，这些协议的复杂性可能导致复杂的架构和长函数。随着函数变得越来越长，验证所有期望的值是否包含在记录中变得困难。记录值通常是非常复杂的计算的结果，并且通常在计算后不久添加到记录中。这意味着与记录相关的调用可能相隔数十行，或者埋在完全不同的模块中的子例程中。很容易错过一个记录值并迷失在噪声中。

不是通过命令，而是通过法令

Trail of Bits 正在发布一个 Rust 库，以帮助开发人员避免这些陷阱。该库名为 Decree，旨在帮助开发人员创建和执行记录规范。它还包括一个新的 trait，旨在使记录值更容易包含上下文信息（如域参数），而开发人员和作者有时会遗漏这些信息。

Decree 的第一个重要功能是，在初始化 Fiat-Shamir 记录时，它需要预先指定所需的记录值以及预期的挑战列表。在提供所有期望的值之前尝试生成挑战会被标记为错误。尝试向记录中添加规范中未期望的值会被标记为错误。尝试向记录中添加已经定义的值会被标记为错误。尝试按顺序请求挑战......你明白了。

这种规范和执行机制由 Decree struct 提供，该 struct 建立在久经考验的 Merlin 库 之上。使用 Merlin 意味着底层哈希和挑战生成机制是可靠的。Decree 旨在管理对底层 Merlin 记录的访问，而不是替换其加密内部结构。

例如，我们可以稍微修改一下我们的 集成测试，该测试实现了 Girault 的身份验证协议。在我们的修改后的示例中，我们将从以下调用开始：

let mut transcript = Decree::new("girault",
     &["g", "N", "h", "u"], &["e", "f"]);

这将初始化 Decree struct，使其期望四个名为 g、N、h 和 u 的输入，以及两个名为 e 和 f 的输出。（对于 Girault 证明，我们只需要 e；包含 f 纯粹是为了说明目的。）

我们可以同时将所有这些值添加到记录中，也可以在计算它们时添加它们：

transcript.add_serial("h", &h)?;
transcript.add_serial("u", &u)?;
transcript.add_serial("g", &g)?;
transcript.add_serial("N", &n)?;

请注意，我们添加值到记录中的顺序与声明中给出的顺序不匹配。Decree 不会更新底层的 Merlin 记录，直到指定了所有值，此时输入会按字母顺序输入到记录中。更改 Decree 输入的排序方式不会影响生成的挑战。

然后我们可以生成我们的挑战：

let mut challenge_e: [u8; 128] = [0u8; 128];
let mut challenge_f: [u8; 32] = [0u8; 32];
transcript.get_challenge("e",
    &mut challenge_e)?;
transcript.get_challenge("f",
    &mut challenge_f)?;

当我们生成挑战时，顺序确实很重要：我们必须首先生成 e，因为 e 在声明中列在 f 之前。

Decree struct 也不仅限于单步协议。一旦给定的规范中的所有挑战都已生成，就可以扩展 Decree 记录以处理进一步的输入值和挑战，并携带所有先前的状态信息。对于多阶段证明，扩展调用有助于划定协议阶段的开始和结束时间。

包含上下文信息的能力由 Inscribe trait 提供，该 trait 可以为具有命名成员的结构派生。在派生 Inscribe trait 时，开发人员可以指定一个提供相关上下文信息的函数，例如椭圆曲线或有限域参数。此信息与结构成员的确定性序列化一起包含。如果结构成员 supporting Inscribe trait，那么它的上下文信息也将被包含。

我们可以使用 Inscribe trait 来简化 Schnorr 证明的处理：

/// Schnorr proof as a struct
    #[derive(Inscribe)]
    struct SchnorrProof {
        #[inscribe(serialize)]
        base: BigInt,
        #[inscribe(serialize)]
        target: BigInt,
        #[inscribe(serialize)]
        modulus: BigInt,
        #[inscribe(serialize)]
        base_to_randomized: BigInt,
        #[inscribe(skip)]
        z: BigInt,
    }

在填充了 SchnorrProof 结构的 base、target、modulus 和 base_to_randomized 值后，我们可以简单地将其添加到我们的记录中，生成我们的挑战，并更新 z 值：

let mut transcript = Decree::new(
    "schnorr proof", &["proof_data"],
&["z_bytes"]).unwrap();
transcript.add("proof_data", &proof)?;

let mut challenge_bytes: [u8; 32] = [0u8; 32];
transcript.get_challenge("z_bytes",
&mut challenge_bytes)?;
let chall = BigInt::from_bytes_le(Sign::Plus,
&challenge_bytes);
let proof.z = (&chall * &log) + &randomizer_exp;

通过在 z 成员上设置 #[inscribe(skip)] 标志，我们将 struct 设置为自动将每个其他值添加到记录中；将 z 添加到证明中使其准备好发送给验证者。

简而言之，Decree struct 帮助程序员定义、执行和理解他们的 Fiat-Shamir 记录，而 Inscribe trait 使开发人员更容易确保默认情况下包含重要的上下文数据（如椭圆曲线标识符）。虽然仍然有可能弄错 Fiat-Shamir 规范，但至少会更容易发现、测试和修复。

所以 试一试，让我们知道你的想法。

1许多更复杂的证明系统都具有此结构的多个实例。没关系；我们这里的想法可以扩展到这些系统。

• 原文链接： blog.trailofbits.com/202...
• 登链社区 AI 助手，为大家转译优秀英文文章，如有翻译不通的地方，还请包涵～