解除Fiat-Shamir的安全隐患

Fiat-Shamir变换是零知识证明（ZKPs）和多方计算（MPC）中的重要构建块。它使得基于交互式协议的零知识证明能够变为非交互式。本质上，它将对话转化为文档。这种能力是SNARKs和STARKs等强大技术的核心。非常有用！

但Fiat-Shamir变换，像几乎所有其他密码学工具一样，比看起来更微妙，一旦出错就会造成灾难性后果。由于这类错误频繁发生，Trail of Bits发布了一个名为Decree的新工具，帮助开发者指定他们的Fiat-Shamir转录本，并更容易地将上下文信息包含在转录本输入中。

Fiat-Shamir概述

许多零知识证明有一个常见的三步协议结构：

Peggy向Victor发送一组对某些值的承诺。
Victor回应一个随机挑战值。
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实现的基础，结果证明是错误的。

缺乏执行

即使有转录本规范，也很难验证规范是否被遵循。

今天使用的证明系统和协议极其复杂。对于某些zkSNARKs，Fiat-Shamir转录本可以包括在子程序的子程序的子程序中生成的值。协议可能要求Peggy生成满足特定属性的值，然后才能用于证明并因此集成到转录本中。这导致软件中复杂的调用树和许多条件块。在“if”块中处理的转录本值很容易在相应的“else”块中被跳过。

此外，这些协议的复杂性可能导致复杂的架构和长函数。随着函数变长，很难验证所有期望的值是否被包含在转录本中。转录本值通常是非常复杂计算的结果，并且通常在计算后不久添加到转录本中。这意味着与转录本相关的调用可能相隔几十行，或埋藏在完全不同模块的子程序中。遗漏的转录本值很容易在噪音中丢失。

不是凭命令，而是凭Decree

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

Decree的第一个大特性是，在初始化Fiat-Shamir转录本时，它需要预先指定所需的转录本值以及期望的挑战列表。尝试在所有期望值提供之前生成挑战会被标记为错误。尝试向转录本添加规范中未期望的值会被标记为错误。尝试向转录本添加已定义的值会被标记为错误。尝试无序请求挑战……你懂的。

这种规范和执行机制由Decree结构体提供，它建立在受人尊敬的Merlin库之上。使用Merlin意味着底层的哈希和挑战生成机制是可靠的。Decree旨在管理对底层Merlin转录本的访问，而不是替换其密码学内部。

例如，我们可以稍微修改我们的集成测试，实现Girault的识别协议。在我们修改的示例中，我们将首先进行以下调用：

1
2


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

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

我们可以同时将所有这些值添加到转录本，或者随着它们被计算而添加：

1
2
3
4


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

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

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

1
2
3
4
5
6


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结构体也不限于单步协议。一旦给定规范中的所有挑战都已生成，Decree转录本可以扩展以处理进一步的输入值和挑战，携带所有先前的状态信息。对于多阶段证明，扩展调用有助于划分协议阶段的开始和结束。

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

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


/// 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值：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


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)]标志，我们设置了结构体以自动将所有其他值添加到转录本；将z添加到证明使其准备好发送给验证者。

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

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

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