cover_image

GKR 协议实现：深入代码

Kurt Pan XPTY
2025年08月09日 00:00

原文：https://blog.lambdaclass.com/gkr-protocol-implementation-deep-dive-into-the-code/

译者：Kurt Pan

介绍

GKR（Goldwasser–Kalai–Rothblum）协议提供了一种高效的方法来验证算术电路上的计算，避免了重复执行并减少了验证者的工作量。在我们之前的文章《GKR 协议：一个循序渐进的示例》中，我们详细探讨了该协议的工作原理，重点介绍了其数学结构，并演示了一个具体的手工示例。GKR 目前用于提升查找论证的性能，这对于证明零知识虚拟机的执行至关重要。

  • https://blog.lambdaclass.com/gkr-protocol-a-step-by-step-example/
  • https://eprint.iacr.org/2023/1284

本文旨在解释我们在 Lambdaworks 中实现该协议的方法，展示如何描述和验证算术电路，以及证明者和验证者在实际中的运作方式。我们还将了解如何应用 Fiat-Shamir 转换使协议变为非交互式，以及如何将 Sumcheck 协议调整并集成为验证每个电路层的核心组件。

  • https://github.com/lambdaclass/lambdaworks/pull/1011

如果你不熟悉该协议或需要复习，建议从上面链接的上一篇文章开始。

警告：此处介绍的 GKR 实现仅供教育用途，请勿用于生产环境。需注意的是，对于更通用的电路，该协议容易受到实际攻击，因为它依赖于 Fiat-Shamir 转换（参见"如何证明虚假陈述"）。

电路结构

GKR 电路由多个层级构成。每层包含多个门电路，每个门电路对前一层的输出进行运算。门电路可以是加法运算，也可以是乘法运算。为了兼容协议，每层必须包含 2 的幂次方个门电路。


上篇文章中用作示例的算术电路

在某些情况下，如果所有门都是乘法，我们可以使用更高效的版本。

电路 API

电路构建的主要结构有：

  • Circuit — 由层向量（从上到下排序，从输出层开始，不包括输入层）、输入的数量以及索引输入层所需的变量数量组成。

    pub struct Circuit {
        /// 第一层是输出层，不包括输入层
        layers: Vec<CircuitLayer>,

        /// 输入数量
        num_inputs: usize,
        input_num_vars: usize, // 输入数量的 log2
    }

  • CircuitLayer — 包含门向量以及索引这些门所需的变量数量。

    pub struct CircuitLayer {
        pub gates: Vec<Gate>,
        pub num_of_vars: usize, // 该层门数量的 log2
    }

  • Gate — 单个门，具有其类型和输入索引。

  • GateType — Add 或 Mul 。

电路门

电路中的每个门要么是加法门（Add），要么是乘法门（Mul）。门的类型决定了前一层的输出如何组合：

  • Add：门输出其两个输入线的总和。
  • Mul：门输出其两个输入线的乘积。

例如：

let gate_1 = Gate::new(GateType::Mul, [0, 1]); // 将前一层索引 0 和 1 的输出相乘
let gate_2 = Gate::new(GateType::Add, [2, 3]); // 将前一层索引 2 和 3 的输出相加



示例：博客文章电路

为了说明这一点，我们逐步讲解 GKR 博客文章中使用的电路的具体构造。该电路在代码库中以 lambda_post_circuit() 的形式提供，可以直接使用，也可以将其作为电路的模板。

pub fn lambda_post_circuit() -> Result<Circuit, CircuitError> {
    use crate::circuit::{Circuit, CircuitLayer, Gate, GateType};
    Circuit::new(
        vec![
            // 层 0（输出层）：两个门
            CircuitLayer::new(vec![
                Gate::new(GateType::Mul, [0, 1]), // 将前一层的输出 0 和 1 相乘
                Gate::new(GateType::Add, [2, 3]), // 将前一层的输出 2 和 3 相加
            ]),
            // 层 1：四个门
            CircuitLayer::new(vec![
                Gate::new(GateType::Mul, [0, 1]), // 将两个输入相乘
                Gate::new(GateType::Add, [0, 0]), // 将第一个输入与自身相加
                Gate::new(GateType::Add, [0, 1]), // 将两个输入相加
                Gate::new(GateType::Mul, [0, 1]), // 再次将两个输入相乘
            ]),
        ],
        2, // 两个输入
    )
}

如何构建你的电路

  1. 确定输入的数量。每个输入将通过其索引（从 0 开始）引用。
  2. 构建第一层：第一层中的每个门都对输入进行操作。使用 Gate::new(GateType::Add, [i, j]) 或 Gate::new(GateType::Mul, [i, j]) 来对输入索引 i 和 j 进行加法或乘法。
  3. 构建后续层：每个门都对前一层的输出进行操作。索引始终指的是前一层输出的顺序。由于层是按照电路从顶部（输出层）到底部的顺序排列的，因此每个新层都应插入到 layers 向量的开头。
  4. 重复直到到达输出层。
  5. 将所有层封装在 Circuit::new(layers, num_inputs) 调用中。

重要：

  • 每层必须具有 2 的幂数量的门。
  • 索引必须有效（即，不超出前一层的界）。

电路自动验证

构建 Circuit 时，会自动执行几项检查以确保电路格式正确：

  • 2 的幂次门：每层必须具有一定数量的 2 的幂次门。这是协议高效运行的必要条件。
  • 有效输入索引：每个门的输入索引必须指向前一层的有效输出。如果索引超出范围，则构建失败。
  • 2 的幂次输入：电路输入的数量也必须是 2 的幂次。

如果任何条件不满足，构造函数都会返回一个描述性错误（以 Result::Err 的形式）。这可以防止创建无效电路，并有助于在开发早期发现错误。

GKR 协议

我们看看该协议的每个步骤是如何在代码中实现的。我们的目标是演示它如何利用 Sumcheck 协议，将电路某一层计算正确性的声明递归地归约到下一层计算正确性的声明，从输出层一直到输入层。

在我们的实现中，利用 Fiat-Shamir 转换来使协议变得非交互式，这导致外表上与上一篇文章中描述的版本略有不同。

证明者

证明结构

证明者负责求值电路并构建证明，使验证者确信该求值的正确性。证明者的核心逻辑位于 prover.rs 中，你可以在其中找到结构体 GKRProof ，其包含以下内容：

  • 电路的输入和输出值。
  • 每个电路层的 Sumcheck 证明具有：
    • 轮单变量多项式 。
    • 单变量多项式  的复合。

回顾一下多项式  和  是什么。在每个电路层以及其 Sumcheck 的每一轮  中，证明者必须通过固定第一个变量并对所有其他变量求和来计算单变量多项式 。例如，在我们之前的文章中，在层 0 中， Sumcheck 进行了四轮，最终得到以下多项式：

其中  是随机挑战。

另一方面，对于每一层 ，多项式  是  的组合，其中  是将节点位置映射到其实际值的函数的多线性多项式扩展，而  是从  到  的线。在前面的例子中，是  和 。

在代码库中，你会看到：

pub struct GKRProof<F: IsField> {
    pub input_values: Vec<FieldElement<F>>,
    pub output_values: Vec<FieldElement<F>>,
    pub layer_proofs: Vec<LayerProof<F>>,
}

各电路层的证明为：

pub struct LayerProof<F: IsField> {
    pub sumcheck_proof: GKRSumcheckProof<F>,
    pub poly_q: Polynomial<FieldElement<F>>,
}

最后，sumcheck_proof 包含轮多项式  以及这些轮中使用的挑战，以便证明者和验证者都可以计算出线 。

pub struct GKRSumcheckProof<F: IsField> {
    pub round_polynomials: Vec<Polynomial<FieldElement<F>>>,
    pub challenges: Vec<FieldElement<F>>,
}

建立证明

证明者使用 Prover::generate_proof() 方法构建证明。此函数获取电路及其输入，对其进行求值，并生成证明。将此函数分解为以下步骤：

  1. 电路求值：证明者根据给定的输入求值整个电路。

    let evaluation = circuit.evaluate(input);

  2. 脚本初始化：

由于我们实现了协议的非交互式版本，证明者必须承诺电路、其输入和输出。这通过定义一个 DefaultTranscript 来实现，我们可以从中进行承诺并采样新值。证明者和验证者都将这些数据附加到脚本中。为了附加到电路中，他们需要将其转换为字节，使用函数 circuit_to_bytes() （可在文件 lib.rs 中找到）来完成此操作。稍后将在 Fiat-Shamir 小节中讨论更多关于脚本的内容。

  1. 采样：
    证明者对第一个  进行采样，以固定变量 ，并开始进行 sumcheck 。回想一下，变量  可以包含多个比特，因此  的大小与 （称为 ）相同。

    let k_0 = circuit.num_vars_at(0).ok_or(ProverError::CircuitError)?;
    let mut r_i: Vec<FieldElement<F>> = (0..k_0)
        .map(|_| transcript.sample_field_element())
        .collect();

  2. Sumcheck 逐层迭代：对于每一层，证明者按照以下步骤应用 Sumcheck 协议：

  • 构建函数：
    证明者构建他想要应用 Sumcheck 的函数，

使用方法 Prover::build_gkr_polynomial()。

请注意，此方法返回两个项，而不是一个。

更具体地说返回一个包含两个元素的向量，其元素本身是两个多线性多项式的向量：

第一个项或向量：

第二项或向量：

这是必要的，因为 lambdaworks 的 Sumcheck 实现只接受多线性多项式的乘积。因此，我们将多项式  拆分为两个多线性多项式的乘积项。

let gkr_poly_terms =
        Prover::build_gkr_polynomial(circuit, &r_i, w_next_evals, layer_idx)?;
  • 应用 GKR Sumcheck Prover：
    我们使用专为 GKR 协议设计的Sumcheck 实现。稍后我们将详细介绍新的 Sumcheck 实现，但需要注意以下三个关键变化：
    I) 我们需要一个以脚本作为输入的sumcheck证明者，这样我们就可以为证明者和验证者维护相同的脚本，该脚本是在开始时创建的。
    II) 新的 Sumcheck 还会返回执行过程中采样的随机值。这使得证明者和验证者稍后都能根据这些值计算函数 。
    III) GKR  Sumcheck 允许我们同时处理的两个项。
let sumcheck_proof = gkr_sumcheck_prove(gkr_poly_terms, &mut transcript)?;
  • Sumcheck 最终声明：
    证明者采样一个新的域元素 （在代码中称为 r_new），在其处求值线 ，并计算复合多项式 。 的求值使用函数 line() 计算，该函数可以在 lib.rs 中找到（因为证明者和验证者都会用到它）。另一方面，多项式  使用方法 Prover::build_polynomial_q() 计算。为了计算这个多项式，证明者需要插值三个点，因为  的次数为 2（因为  是线性的，而  在每个变量中都是多线性的）。
// 我们博客文章中的 r*
let r_new = transcript.sample_field_element();

// 使用线函数构造下一轮的随机点
//  l(x) = b + x * (c - b)
let (b, c) = sumcheck_challenges.split_at(num_vars_next);
// r_i = l(r_new)
r_i = crate::line(b, c, &r_new);

let poly_q = Prover::build_polynomial_q(b, c, w_next_evals.clone())?;
  1. 做出证明：最后，证明者拥有做出证明的所有要素。
let proof = GKRProof {
    input_values: input.to_vec(),
    output_values,
    layer_proofs,
};

验证者

一旦我们理解了证明者的作用，就很容易理解验证者需要做什么。它只需遵循与证明者相同的步骤，使用证明的元素并在每个步骤执行必要的检查。使用方法 Verifier::verify() 按照以下步骤验证证明：

  1. 脚本初始化：
    就像证明者一样，首先创建一个脚本并附加电路（双方都知道）、输入以及证明者在证明中发送的输出。

  2. 初始和计算：
    对  的域元素进行采样，以固定变量  并将初始和设置为 ，其中  是将输出门映射到求值值的函数的多线性多项式扩展。证明者将这些值作为证明的一部分发送。

    let output_poly_ext = DenseMultilinearPolynomial::new(proof.output_values.clone());
    let mut claimed_sum = output_poly_ext
        .evaluate(r_i.clone())
        .map_err(|_e| VerifierError::MultilinearPolynomialEvaluationError)?;

  3. 逐层验证：对于每一层 ，验证者执行以下操作：

    • 验证sumcheck证明：
      验证者使用函数 gkr_sumcheck_verify 检查当前层的 Sumcheck 证明。该函数确保证明者提供的单变量多项式序列  的次数为 2，并且与每个 Sumcheck 轮  中声明的和一致；即：
      ，。

      let (sumcheck_verified, sumcheck_challenges) = gkr_sumcheck_verify(
          claimed_sum.clone(),
          &layer_proof.sumcheck_proof,
          &mut transcript,
      )?;
      if !sumcheck_verified {
          return Ok(false);
      }

    • *使用组合多项式  检查最后一轮 *：
      为了验证最后一轮 Sumcheck 的最终结果，验证者需要值  和 。然而，多项式  对他来说是未知的：验证者没有电路求值。因此，他使用证明者提供的组合多项式  执行最终校验。回想一下，如果证明者没有作弊，那么  和  也成立。因此，验证者必须检查

      let last_poly = layer_proof.sumcheck_proof.round_polynomials.last().unwrap();
      let last_challenge = sumcheck_challenges.last().unwrap();
      let expected_final_eval = last_poly.evaluate::<F>(last_challenge);

      let q_at_0 = layer_proof.poly_q.evaluate(&FieldElement::zero());
      let q_at_1 = layer_proof.poly_q.evaluate(&FieldElement::one());

      let add_eval = circuit.add_i_ext(&r_i, layer_idx).evaluate(sumcheck_challenges.clone())?;
      let mul_eval = circuit.mul_i_ext(&r_i, layer_idx).evaluate(sumcheck_challenges.clone())?;

      let final_eval = add_eval * (&q_at_0 + &q_at_1) + mul_eval * q_at_0 * q_at_1;
      if final_eval != expected_final_eval {
          return Ok(false);
      }

    • 采样一个新的挑战并更新求值点：
      验证者从脚本中采样一个新的域元素 ，然后使用线函数计算下一层的下一个求值点 。通过在新的挑战下求值复合多项式  来更新声明的和：。

      let r_new = transcript.sample_field_element();
      let num_vars_next = circuit.num_vars_at(layer_idx + 1).ok_or(VerifierError::CircuitError)?;
      let (b, c) = sumcheck_challenges.split_at(num_vars_next);
      r_i = crate::line(b, c, &r_new);
      claimed_sum = layer_proof.poly_q.evaluate(&r_new);

  4. 最终输入检查：
    处理完所有层后，验证者检查最终声明的和是否与最终求值点  处输入值的多线性扩展求值结果相匹配。在上一篇文章的示例中，这将是 。这确保了从输出到输入的整个计算都是一致的。

    let input_poly_ext = DenseMultilinearPolynomial::new(proof.input_values.clone());
    if claimed_sum
        != input_poly_ext
            .evaluate(r_i)
            .map_err(|_| VerifierError::MultilinearPolynomialEvaluationError)?
    {
        return Ok(false);
    }

如果所有检查都通过，验证者就接受该证明为有效。否则，该证明在第一次检查失败时就被拒绝。此过程使验证者能够高效地确认计算的正确性，而无需重新执行整个电路。

Sumcheck 协议

Sumcheck 协议是 GKR 协议的核心组件。它的作用是使证明者能够说服验证者，使其相信多线性多项式乘积的和是正确的，而无需验证者直接计算和。实现这一目标的方法是将原始求和归约到一系列单变量多项式的校验，每个变量对应一个校验。

快速回顾：校验了什么求和？

在 GKR 协议的每一层 ，证明者和验证者需要检查以下形式的求和：

其中  是编码该层电路的接线和值的多线性多项式， 是该层的变量数（取决于索引下一层门所需的比特数）。

Sumcheck 协议使得证明者通过发送一系列单变量多项式  来说服验证者所声称的值  是正确的，这样，在第   轮中：

其中  表示前几轮采样的挑战， 表示当前轮次的变量，其余变量进行求和。轮次数（以及  多项式的数量）始终等于被检查层的  变量数。

在每一轮中，验证者都会检查sumcheck性质：

然后为下一轮采样一个新的挑战 。所有轮次结束后，验证者将剩下关于  的声明，并将与下一层进行验证。

拆分 GKR 多项式以进行 Sumcheck

GKR 多项式  表示两个相邻层之间的关系，其公式如下：

为了应用 Sumcheck 协议，该多项式被分成两个项，每个项都是两个多线性多项式的乘积：

  • 第一项：
  • 第二项：

这种拆分是必要的，因为sumcheck实现需要多线性多项式的乘积。在代码中，这由函数 Prover::build_gkr_polynomial 处理（参见证明者部分），该函数返回一个包含两个元素的向量，每个元素都是由两个多线性多项式（每个元素的因式）组成的向量。然后，这些元素被传递给sumcheck证明者，后者在每一轮中同时处理这两个元素。

代码库中的实现

Sumcheck 协议的逻辑在 sumcheck.rs 中实现。该文件包含证明者和验证者用于对每个电路层执行 Sumcheck 轮次的函数。

证明者：逐步生成sumcheck证明

在每一层，证明者构建 Sumcheck 证明如下：

1. 构建 GKR 多项式项

对于当前层，构建 GKR 多项式，并根据协议要求将其拆分为两项：

let factors_term_1 = terms[0].clone();
let factors_term_2 = terms[1].clone();

let mut prover_term_1 = Prover::new(factors_term_1)?;
let mut prover_term_2 = Prover::new(factors_term_2)?;

2. 计算初始声称的和

证明者计算两个项的初始和并将它们相加：

let claimed_sum_term_1 = prover_term_1.compute_initial_sum()?;
let claimed_sum_term_2 = prover_term_2.compute_initial_sum()?;
let claimed_sum = claimed_sum_term_1 + claimed_sum_term_2;

3. 逐轮应用 Sumcheck 协议

在每一轮中，证明者都会计算每个项的单变量多项式，将其相加，并将结果附加到记录中。每个得到的多项式  都收集在一个向量中：

let mut proof_polys = Vec::with_capacity(num_vars);
for j in 0..num_vars {
    let g_j_term_1 = prover_term_1.round(current_challenge.as_ref())?;
    let g_j_term_2 = prover_term_2.round(current_challenge.as_ref())?;
    let g_j = g_j_term_1 + g_j_term_2;
    // ...将 g_j 附加到脚本...
    proof_polys.push(g_j);
    // ...采样挑战，更新 current_challenge...
}

4. 收集证明数据

经过所有轮次后，多项式向量和挑战用于构建 Sumcheck 证明对象：

let sumcheck_proof = GKRSumcheckProof {
    round_polynomials: proof_polys,
    challenges,
};

5. 发送给验证者

将 Sumcheck 证明作为整体 GKR 证明的一部分，验证者将在下一阶段进行检查。

验证者：逐步sumcheck验证

在每一层，验证者按如下方式处理sumcheck证明：

1. 每轮检查次数以及总和性质

对于收到的每个单变量多项式 ，检查其次数最多为 2，并且其在 0 和 1 处的求值总和是否与预期值（初始声明或在前一次质询中求值的前一个多项式）匹配：

// 检查 g_j 的次数不超过理论上限
if g_j.degree() > 2 {
    returnErr(crate::verifier::VerifierError::InvalidDegree);
}
let g_j_0 = g_j.evaluate::<F>(&FieldElement::zero());
let g_j_1 = g_j.evaluate::<F>(&FieldElement::one());
let sum_evals = &g_j_0 + &g_j_1;

let expected_sum = if j == 0 {
    claimed_sum.clone()
} else {
    let prev_poly = &proof_polys[j - 1];
    let prev_challenge = &challenges[j - 1];
    prev_poly.evaluate::<F>(prev_challenge)
};

if sum_evals != expected_sum {
    returnOk((false, challenges));
}

2. 更新脚本并采样下一个挑战

每一轮之后，验证者将多项式附加到脚本中并对下一个挑战进行采样：

let r_j = transcript.sample_field_element();
challenges.push(r_j.clone());

3. 接受或拒绝

如果所有轮次都通过了检查，则接受结果正确，无需直接计算全部结果。如果任何一轮检查失败，则立即拒绝该证明。

Sumcheck 协议的每一轮都会将变量数量减少一个，将多变量求和转换为一系列单变量校验。证明者执行主要计算，而验证者只需检查少量多项式求值和域运算。使用 Fiat-Shamir 转换可确保协议是非交互式的，所有挑战均由脚本导出。

Fiat-Shamir 转换：使其非交互

原始的 GKR 协议是交互式的，这意味着它需要证明者和验证者之间进行一系列的来回通信。虽然交互式证明在理论上是可靠的，但由于延迟和通信开销，它们在许多实际应用中并不实用。Fiat-Shamir 转换是一种密码学技术，用于将交互式证明系统转换为非交互式证明系统。

如何应用 Fiat-Shamir

在我们的实现中，Fiat-Shamir 转换将验证者的随机挑战替换为密码学哈希函数的输出，具体来说是来自 lambdaworks_crypto 包的 DefaultTranscript。这使得证明者能够确定性地生成所有必要的挑战，而无需与验证者进行任何交互。

  1. 脚本初始化：创建脚本，并填充与证明相关的公开信息。这些信息包括：

    通过包含这些信息，任何一方都可以重建相同的脚本并验证生成的挑战。

    • 电路结构（通过 circuit_to_bytes(circuit) 序列化）。
    • 公开输入值。
    • 声称的输出值。

  2. 挑战生成：在交互协议需要验证者进行随机挑战的每个步骤中，实现方式如下：

    • 将证明的当前状态（例如，证明者发送的多项式的系数）附加到脚本。
    • 使用 transcript.sample_field_element() 从脚本中采样一个随机域元素。该元素是通过密码学方式从脚本中所有先前的信息中派生出来的，因此在相关信息被承诺之前，证明者无法预测其结果。

关键挑战点

Fiat-Shamir 转换应用于 GKR 协议中的几个关键部分：

  • 初始随机值（）：对于输出层，采样初始随机挑战以开始逐层归约。
  • Sumcheck 挑战（）：在 Sumcheck 协议的每一轮中，都会根据脚本生成挑战。这些挑战对于验证者检查证明者的单变量多项式的一致性至关重要。
  • 线函数参数（ 或 r_new）：在每一层的 Sumcheck 之后，都会采样一个新的挑战 r_new。此挑战将在 line 函数中用于导出下一层的声明求和的求值点，从而有效地将证明中的各层关联起来。

通过利用 Fiat-Shamir 转换，GKR 实现达到了非交互性，使其更适用于实际应用中，因为在实际应用中，证明者和验证者之间可能无法进行持续通信，或者会导致不良延迟。这种变换是许多现代零知识证明系统的基石，能够在各种场景中实现高效且可验证的计算。

总结

在本文中，我们展示了如何实现 GKR 协议。从电路描述开始，证明者求值每一层，构建相应的多项式，并运行定制的 Sumcheck 协议，该协议的挑战通过 Fiat–Shamir 脚本生成。验证者使用相同的脚本，重复 Sumcheck 轮次，使用组合多项式  验证最终声明，并最终确认计算结果完全正确，直至公共输入。通过这种方式，原本可能成本高昂的电路重新执行被归约到一系列轻量级的代数检查。虽然此实现旨在用于教育用途，但它囊括了协议的每个基本步骤。