Pinocchio：可验证计算再探

1. 介绍

1.1 动机

想象一下，你想进行一个复杂的计算，但你的计算机无法完成，或者你需要从一个你不信任的计算机那里获取结果。如何在不自己重做或理解复杂细节的情况下，确保它被正确完成？2013 年推出的 Pinocchio 使用 SNARK 提供了一个解决方案。这项技术使证明者能够简洁地证明其计算的正确性，并且能够验证它们，而无需透露细节。虽然 Pinocchio 本身已经进化，不再以其原始形式使用，但理解它有助于我们理解驱动当今区块链技术的 SNARK，包括 ZK Rollups，从而增强可扩展性和隐私。

1.2 什么是 SNARK？

所以，Pinocchio 是一个 SNARK 协议，但什么是 SNARK？SNARK 代表 Succinct, Non-Interactive Argument of Knowledge (简洁、非交互式知识论证)。简洁，因为我们将拥有易于验证的小型证明。非交互式，因为生成的证明可以用来 убедить 任意数量的验证者，而无需与证明者进行直接交互。知识论证，因为我们以非常高的概率知道证明者没有作弊。本质上，SNARK 协议为我们提供了一种将复杂计算“压缩”成小型、易于验证的证明的方法。

1.3 为什么我们需要 SNARK？

能够证明计算的有效性而无需提供其代码听起来很酷，但在现实世界中有哪些应用？它用在哪里？

一个典型的例子是 ZK Rollups。区块链是可验证的计算机；它们通过让每个节点重新执行每个交易并达成共识来实现这种可验证性。问题在于，最弱的设备成为了瓶颈。与 web2 中发生的情况相反，添加更多硬件并不能使它们更快：系统变得更加健壮和可靠，但最弱的设备仍然限制着它。使用 SNARK，我们可以用证明的验证来替换重新执行，这要快得多（提高了吞吐量）。此外，我们可以创建包含整个交易块的证明，从而实现有效的扩展。总而言之，我们可以将执行移至链下 rollup，并在链上验证其 доказательства，从而使系统能够扩展。

2. 协议的准备工作：从代码到 QAP

2.1 算术电路

要能够使用任何 SNARK 协议，我们必须做的第一件事是找到一种有效且系统的方式来表示计算代码。这就是算术电路所做的：算术电路是一种计算模型，用于以结构化的方式表示算术运算。它提供了一种系统的方式来描述和计算复杂的数学函数。要了解有关算术电路的更多信息，你可以查看我们的文章 如何将代码转换为算术电路。

现在，如果证明者想要证明在给定特定输入的情况下，特定代码返回某些输出，她可以简单地将相应的算术电路发送给验证者，而无需任何其他协议。问题在于，这样的测试根本不简洁，实际上几乎就像完全发送输入和代码一样。这就是为什么，为了获得简洁的证明，我们将不得不将算术电路转换为我们所说的 R1CS，然后将获得的 R1CS 转换为 QAP。

下面我们将广泛解释 R1CS 和 QAP 是什么。请注意，伴随此解释可能会对理解有所帮助，相应的实现可以在 来自 Lambdaworks 库的 Pinocchio 中找到。

2.2 R1CS

R1CS 代表 Rank-1 Constraint System (秩为 1 的约束系统)。它允许我们使用 矩阵 方程以结构化的方式表达电路变量之间的关系。更具体地说，给定一个具有有效解 $c$ 的算术电路，我们的目标是创建一个形式为 $A c \odot B c = C c$ 的方程组，其中 $A$、$B$ 和 $C$ 是矩阵：

为了充分理解什么是 R1CS 以及如何构建它们，我们建议阅读 这篇文章。不过，我们在此列出将算术电路转换为 R1CS 的步骤。

1. 识别电路中使用的所有变量。我们称它们为 $c = (1, c_1, \dots, cN, c{N+1}, \dots, c_m)$，其中 ${c_1, \dots, cN}$ 是公共变量，${c{N+1}, \dots, c_m}$ 是电路的中间变量和私有变量。
2. 将电路表示为一个方程组，其中变量为 ${ci}{i=1}^m$，并且每个方程只有一次乘法。我们将每个方程称为约束，$n$ 为约束的数量。
3. 以以下方式构建矩阵 $A \in \mathbb{F}p^{n \times m}$：$a{ik}$ 是变量 $c_k$ 在约束 $i$ 的左侧条目的系数。

（如果你不知道 $\mathbb{F}_p^{n \times m}$ 是什么意思，请不要担心，你可以将其视为 $\mathbb{R}^{n \times m}$，因此 $A$ 只是一个数字矩阵）。

4. 类似地，构造矩阵 $B$，其行表示每个约束乘法的右侧。
5. 构造矩阵 $C$，其行表示每个约束的结果值。
6. 最后，当且仅当 $A c \odot B c = C c$ 时，$c$ 才是算术电路的解，其中 $\odot$ 表示 Hadamard 乘积。

2.3 QAP

所以现在我们知道程序可以表示为算术电路，并进一步转换为 R1CS。但是，由于需要大量的操作，特别是对于复杂的计算，直接评估 R1CS 进行验证仍然不简洁。二次算术程序 (QAP) 通过提供更有效的表示来解决此问题。

QAP 将 R1CS 的约束编码为 多项式 集。这允许将多个约束批量处理成单个多项式方程。但是，为什么使用多项式会使证明简洁？这完全归功于被称为 Schwartz-Zippel 引理 的数学结果。要详细了解为什么这个引理使证明简洁以及我们如何将 R1CS 转换为 QAP，我们建议阅读 ZK RareSkills 书的这一章。我们的目标是能够测试 R1CS 解的有效性，检查某个多项式是否具有给定的属性。我们在此处留下带有符号的步骤，我们将在协议中使用的符号：

1. 接收 R1CS：$A c \odot B c = C c$，其中 $A, B, C \in \mathbb{F}_p^{n \times m}$ 且 $c \in \mathbb{F}_p^m$。
2. 将 $A$、$B$ 和 $C$ 的每一列转换为多项式：

对于每个 $k \in {1, \dots, m}$，将 $(1, \dots, n)$ 与 $(a{1k}, \dots, a{nk})$ (A 的第 $k$ 列) 进行内插。我们将生成的多项式称为 $v_k(x)$。

类似地，$w_k(x)$ 和 $y_k(x)$ 分别内插 $B$ 和 $C$ 的列。

3. 定义多项式 $p(x) = (\sum_{k=1}^m c_k vk(x)) (\sum{k=1}^m c_k wk(x)) - \sum{k=1}^m c_k y_k(x), t(x) = (x-1)(x-2) \dots (x-n)$。我们将 $t(x)$ 称为消失多项式。
4. 最后，当且仅当存在一个多项式 $h$ 时，$c$ 才是 R1SC 的解，使得 $p(x) = h(x) t(x)$。这可以通过选择一个随机 $s$ 并验证 $p(s) = h(s) t(s)$ 来检查。

3. Pinocchio 协议

3.1 背后的想法

现在我们准备好理解协议。它从一次性设置开始，在该设置中生成两个密钥，用于证明和验证这些计算。执行计算的证明者使用她的密钥来创建一个证明，该证明的大小很小且恒定，与计算的复杂性无关。然后通过数学检查有效地验证此证明，以确保计算已正确完成。该系统不仅支持公共验证，允许任何拥有验证密钥的人检查证明，而且还可以扩展以提供保护隐私的零知识证明。

3.2 数学预备知识

理解 Pinocchio 协议需要熟悉关键的数学概念，主要是椭圆曲线、有限域和群论。这些构成了 Pinocchio（以及一般的 SNARK 协议）中密码运算和安全证明的基础。有关椭圆曲线的详细探索，请参阅我们的 文章，我们在其中讨论了它们。有关诸如群和域之类的基本结构的入门知识，请参阅我们的 开发人员数学生存工具包。这些资源提供了理解 Pinocchio 复杂设计所需的背景知识。

3.3 理解协议的一些观察结果

• 证明者和验证者就一个配对友好的椭圆曲线以及 группы $G_1$ 和 $G_2$ 的生成器达成一致，分别用 $g_1$ 和 $g_2$ 表示。在我们的例子中，我们选择 BLS12-381。
• 从技术上讲，没有必要使用两个群来实现该协议。也就是说，可以使用 $G_1 = G_2 = G$ 和 $g_1 = g_2 = g$ 来解释整个实现。事实上，在原始 Pinocchio 论文中，你可以这样找到它。然而，I 类配对（即那些域形式为 $G \times G$ 的配对）非常低效。此外，BLS12-381 和 BN254 是与以太坊相关的曲线，这就是为什么我们通常选择在它们上工作。
• 我们使用 $++$ 来表示群 $G_1$ 和 $G_2$ 的运算。例如，$\alpha_v \cdot g_2 = \underbrace{g_2 + \dots + g2}{\alpha_v \text{ 次}}$。

3.4 协议

在以下部分中，我们将介绍该协议，其中包含来自我们使用 Lambdaworks 库制作的 实现 的一些代码片段。

设置

从 $\mathbb{F}_p$ 中选择八个私有随机元素 $s$、$\alpha_v$、$\alpha_w$、$\alpha_y$、$\beta$、$r_v$、$r_w$、$\gamma$，并设置 $r_y = r_v \cdot r_w$。这组元素被称为有毒废物，一旦生成密钥就应丢弃并完全遗忘。

pub struct ToxicWaste {
    rv: FE,
    rw: FE,
    s: FE,
    // .... (其他元素)

impl ToxicWaste {
    pub fn sample() -> Self {
        Self {
            s: sample_fr_elem(),
            alpha_v: sample_fr_elem(),
            // ... (其他元素)
        }
    }

    pub fn ry(&self) -> FE {
        &self.rv * &self.rw
    }
}

在设置中生成两个公钥：评估密钥 (evaluation key)，发送给证明者；验证密钥 (verification key)，发送给验证者。

验证密钥

1. $g_2$
2. $\alpha_v \cdot g_2$
3. $\alpha_w \cdot g_2$
4. $\alpha_y \cdot g_2$
5. $\gamma \cdot g_2$
6. $\beta \gamma \cdot g_2$
7. $r_y t(s) \cdot g_1$
8. ${r_v v_k(s) \cdot g1}{k \in {0, \dots, N}}$
9. ${r_w w_k(s) \cdot g2}{k \in {0, \dots, N}}$
10. ${r_y y_k(s) \cdot g1}{k \in {0, \dots, N}}$

为了在 rust 中实现这一点，我们首先需要创建一个包含每个元素的 VerificationKey 结构，然后生成它。

pub struct VerificationKey {
    pub g2: G2Point,
    pub g2_alpha_v: G2Point,
    pub g2_alpha_w: G2Point,
    // ...
}

pub fn generate_verification_key(
    qap: QuadraticArithmeticProgram,
    toxic_waste: &ToxicWaste,
) -> VerificationKey {
    let g1: G1Point = Curve::generator();
    let g2: G2Point = TwistedCurve::generator();

    // 声明其余需要的变量
    // ...

    VerificationKey {
        g2: g2.clone(),
        g2_alpha_v: g2.operate_with_self(toxic_waste.alpha_v.representative()),
        // ...
    }
}

评估密钥

1. ${r_v v_k(s) \cdot g1}{k \in {N+1, \dots, m}}$
2. ${r_w w_k(s) \cdot g1}{k \in {N+1, \dots, m}}$
3. ${r_w w_k(s) \cdot g2}{k \in {N+1, \dots, m}}$
4. ${r_y y_k(s) \cdot g1}{k \in {N+1, \dots, m}}$
5. ${r_v \alpha_v v_k(s) \cdot g1}{k \in {N+1, \dots, m}}$
6. ${r_w \alpha_w w_k(s) \cdot g1}{k \in {N+1, \dots, m}}$
7. ${r_y \alpha_y y_k(s) \cdot g1}{k \in {N+1, \dots, m}}$
8. $(r_v \beta v_k(s) + r_w \beta w_k(s) + r_y \beta y_k(s)) \cdot g_1$
9. ${s^i \cdot g2}{i \in {1, \dots, d}}$，其中 $d$ 是 $t(x) = (x-1) \dots (x-n)$ 的度数。也就是说，$d = n$ 是 R1SC 矩阵的行数（即约束数）。

pub struct EvaluationKey {
    pub g1_vk: Vec<G1Point>,
    pub g1_wk: Vec<G1Point>,
    pub g2_wk: Vec<G2Point>,
    // ...
}

pub fn generate_evaluation_key(
    qap: &QuadraticArithmeticProgram,
    toxic_waste: &ToxicWaste,
) -> EvaluationKey {
    let g1: G1Point = Curve::generator();
    let g2: G2Point = TwistedCurve::generator();
    let (v_mid, w_mid, y_mid) = (qap.v_mid(), qap.w_mid(), qap.y_mid());

    // 声明其余需要的变量
    // ...

    EvaluationKey {
        g1_vk: vs_mid.iter()
            .map(|vk| g.operate_with_self((rv * vk.evaluate(&s))
            .representative()))
            .collect(),
,
        // ...
    }
}

拥有 EvaluationKey 和 VeifiationKey 之后，我们可以实现设置：

pub fn setup(
    qap: &QuadraticArithmeticProgram,
    toxic_waste: ToxicWaste,
) -> (EvaluationKey, VerificationKey) {
    (generate_evaluation_key(&qap, &toxic_waste),
     generate_verification_key(qap.clone(), &toxic_waste))
}

证明

证明者的步骤如下：

1. 使用输入值评估电路并获得 $c_{N+1}, \dots, c_m$ 中间值。

2. 计算多项式 $p(x) = (\sum_{k=1}^m c_k vk(x)) (\sum{k=1}^m c_k wk(x)) - \sum{k=1}^m c_k y_k(x)$。

3. 计算多项式 $h(x) = \frac{p(x)}{t(x)}$。

4. 生成证明 $\pi = (V, W_1, W_2, Y, V', W', Y', Z, H)$，计算其元素：

   • $V = \sum_{k=N+1}^m c_k \cdot r_v v_k(s) \cdot g_1 \text{ 来自评估密钥}$
   • $W1 = \sum{k=N+1}^m c_k \cdot r_w w_k(s) \cdot g_1$
   • $W2 = \sum{k=N+1}^m c_k \cdot r_w w_k(s) \cdot g_2$
   • $Y = \sum_{k=N+1}^m c_k \cdot r_y y_k(s) \cdot g_1$
   • $V' = \sum_{k=N+1}^m c_k \cdot r_v \alpha_v v_k(s) \cdot g_1$
   • $W' = \sum_{k=N+1}^m c_k \cdot r_w \alpha_w w_k(s) \cdot g_1$
   • $Y' = \sum_{k=N+1}^m c_k \cdot r_y \alpha_y y_k(s) \cdot g_1$
   • $Z = \sum_{k=N+1}^m c_k \cdot (r_v \beta v_k(s) + r_w \beta w_k(s) + r_y \beta y_k(s)) \cdot g_1$
   • $H = h(s) \cdot g2 = \sum{i=1}^d h_i \cdot s^i \cdot g_2$

5. 发送公共值 $(c_1, \dots, c_N)$ 和证明 $\pi$。

pub fn generate_proof(
    evaluation_key: &EvaluationKey,
    qap: &QuadraticArithmeticProgram,
    qap_c_coefficients: &[FE],
) -> Proof {
    // 我们将调用 {c_{N+1}, ... , c_m} cmid。
    let cmid = &qap_c_coefficients[qap.number_of_inputs..qap_c_coefficients.len() - qap.number_of_outputs];

    // 我们将 cmid 的每个 FieldElement 转换为 UnsignedInteger，以便我们可以将它们乘以 g1。
    let c_mid = cmid
        .iter()
        .map(|elem| elem.representative())
        .collect::<Vec<_>>();

    let h_polynomial = qap.h_polynomial(qap_c_coefficients);
    let h_coefficients = h_polynomial.coefficients
        .iter()
        .map(|elem| elem.representative())
        .collect::<Vec<_>>();
    let h_degree = h_polynomial.degree();

    Proof {
        v: msm(&c_mid, &evaluation_key.g2_vk_s).unwrap(),
        w1: msm(&c_mid, &evaluation_key.g2w_wk).unwrap(),
        w2: msm(&c_mid, &evaluation_key.g2w_wk).unwrap(),
        //...

    }
}

验证

为了防止恶意证明者欺骗验证者，他必须确保两件事：首先，满足 QAP 多项式的请求条件（编号 4）；其次，证明的元素已从 QAP 正确生成。为了实现这一点，验证者将进行三个检查。第一个检查将确保 QAP 的有效性，其他两个检查将确保证明元素的正确构造。

我们将用 $e$ 表示其第一个参数来自 $G_1$，第二个参数来自 $G_2$ 的配对。

检查 1：QAP 的正确性

为了确保提供的证明对应于 QAP 的有效解，从而对应于正确的计算结果，验证者需要 убедиться $p(s) = h(s) t(s)$。为了实现这一点，他可以简单地检查 $e(V{io} + V, W{io} + W_2) = e(r_y t(s) \cdot g1, H) e(Y{io} + Y, g_2)$，为了简化符号，我们称为

• $V_{io} = r_v v_0(s) \cdot g1 + \sum{k=1}^N c_k r_v v_k(s) \cdot g_1$
• $W_{io} = r_w w_0(s) \cdot g2 + \sum{k=1}^N c_k r_w w_k(s) \cdot g_2$
• $Y_{io} = r_y y_0(s) \cdot g1 + \sum{k=1}^N c_k r_y y_k(s) \cdot g_1$

pub fn check_divisibility(
    verification_key: &VerificationKey,
    proof: &Proof,
    c_io: &[FE],
) -> bool {
    // 我们将使用 hiding_v、hiding_w 和 hiding_y 作为配对的参数。

    // 我们将 c_io 转换为 UnsignedInteger。
    let c_io = c_io
    .iter()
    .map(|elem| elem.representative())
    .collect::<Vec<_>>();

    let v_io = verification_key.g1_vk[0]
        .operate_with(&msm(&c_io, &verification_key.g1_vk[1..]).unwrap());

    // 与 w_io 和 y_io 相同。
    //...

    Pairing::compute(
        &v_io.operate_with(proof.v),
        &w_io.operate_with(proof.w)
    ).unwrap()
    == Pairing::compute( ... , ...).unwrap()
    * Pairing::compute( ... , ...).unwrap()

}

$V$、$W$ 和 $Y$ 的正确构造：

检查 2： 验证者检查证明者是否使用 QAP 的多项式来构造 $V$、$W$ 和 $Y$，并且他没有提供随意的值，这些值只是通过了先前的检查。

因此，在此检查中，目标是验证 $V$ 是否是 $g_1$ 乘以 $v_k(s){k \in 1, \dots, m}$ 的一些线性组合，并且类似地，对于 $W$ 和 $Y$：

• $e(V', g_2) = e(V, \alpha_v \cdot g_2)$
• $e(W', g_2) = e(W, \alpha_w \cdot g_2)$
• $e(Y', g_2) = e(Y, \alpha_y \cdot g_2)$

pub fn check_appropriate_spans(
    verification_key: &VerificationKey,
    proof: &Proof
) -> bool {
    let b1 = Pairing::compute(&proof.v_prime, &verification_key.g2)
        == Pairing::compute(&proof.v, &verification_key.g2_alpha_v);
    let b2 = Pairing::compute( ... , ... )
        == Pairing::compute(... , ... );
    let b3 = // ...

    b1 && b2 && b3
}

为什么这会奏效？

如果此检查通过，则验证者可以确保，例如，$V' = \alpha_v V$。查看评估密钥，他看到证明者不知道 $\alpha_v$ 的原始值。因此，证明者可以构造 $V$ 和 $V'$ 使得它们满足此等式的唯一方法是使用 $v_k(s){k \in 1, \dots, m}$ 的线性组合。类似地，他可以 убедиться $W$ 和 $Y$ 如此构造。

检查 3： 先前的检查不足以确保正确构造证明元素。我们还需要验证证明者在先前检查的每个线性组合 $V$、$W$ 和 $Y$ 中使用了相同的系数集 $c_1, \dots, c_m$。

$e(Z, \gamma \cdot g_2) = e(V + W + Y, \beta \gamma \cdot g_2)$

pub fn check_same_linear_combinations(
    verification_key: &VerificationKey,
    proof: &Proof
) -> bool {
    Pairing::compute(&proof.z, &verification_key.g2_gamma)
    == Pairing::compute(
        &proof.v
            .operate_with(&proof.w)
            .operate_with(&proof.y),
        &verification_key.g2_beta_gamma
    )
}

放在一起

pub fn verify(verification_key:&VerificationKey,
    proof: &Proof,
    c_inputs_outputs: &[FE]
) -> bool {
    let b1 = check_divisibility(verification_key, proof, c_inputs_outputs);
    let b2 = check_appropriate_spans(verification_key, proof);
    let b3 = check_same_linear_combinations(verification_key, proof);

    b1 && b2 && b3
}

6. 将 SNARK 变成 ZK-SNARK

零知识是什么意思？我们希望验证者不可能从证明中获得任何信息，因为它看起来与随机数据无法区分。

为了使其具有零知识性，证明者必须采样一些随机值 $\delta_v, \delta_w, \delta_y$ 并对多项式进行以下更改：

$v_{mid}(x) + \delta_v t(x), v(x) + \delta_v t(x), w(x) + \delta_w t(x)$ 和 $y(x) + \delta_y t(x)$。

你可以在 Why and How zk-SNARK Works 的第 4.13 章 中详细了解协议的 zk 适配。

7. 总结

在本文中，我们介绍了 Pinocchio 协议背后的主要思想以及我们使用 Lambdaworks 库的实现。我们首先看到了将代码转换为 QAP 的步骤。然后，我们介绍了实际协议，解释了它的工作原理以及为什么我们需要每个不同的检查来实现安全性。最后，我们观察到，虽然其主要目标是实现可验证的计算，但它可以通过最少的额外工作来合并零知识属性。

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