halo2

重要提示: 这个库正在积极开发中，不应该在生产软件中使用.

文档

最低支持的 Rust 版本

需要 Rust 1.51 或者更高.

最低支持的 rust 版本 可以在 未来更改, 但是这会带来小版本的改变

并行控制方案

halo2 当前为并行计算使用 rayon . 设置 线程数量数量时使用 RAYON_NUM_THREADS 环境变量

许可证

Copyright 2020-2021 The Electric Coin Company.

你可以在 Bootstrap 开源许可证 1.0 版下使用这个包， 或者您可以选择任意更高版本 . 看这个文件 COPYING 去了解更多详细信息, 看这个文件 LICENSE-BOSL 了解 Bootstrap 开源许可证 1.0 版条款.

BOSL的目的是允许对包进行商业改进，同时确保所有改进都是开源的 . 看 这 去了解 BOSL 为什么存在.

翻译说明

Thanks for halo2 Book team's clear explanation about halo2 design and protocol. It's really wonderful :)

halo2 Book清晰系统地讲解了halo2零知识证明的原理：电路算术表示，查找证明，置换证明以及整个协议的形式化表示。同时该文档也讲解零知识证明基础原理，是入门PLONK系零知识证明的极佳入门材料。

在查看halo2实现代码的基础上，对照halo2 Book设计，总结出halo2 Book对应的中文翻译。国内零知识证明技术相关的正规教程/教材比较少，有些术语并没有合适或者统一的翻译。针对用到的术语，整理了一个术语表。有些术语实在无法精准翻译，直接用英文代替。此翻译对应的halo2 Book的最后一个提交信息如下：

658c2db4217b1b19b17ecd29577c0e370e1c4997

halo2 Book的翻译以严格准守原文本意为原则，但是水平有限，有翻译不妥的地方，欢迎更多的小伙伴指正。最后感谢参与翻译和校对的小伙伴们。

Github: Halo2 Book (Chinese)

术语表

• PLONKish: PLONK系

• argument: 证明

• language: 语言

• relation: 关系

• statement: 论述

• witness: 论据

• soundness: 可靠性

• circuit: 电路

• public input: 公开输入

• private input: 隐私输入

• arithmetization：算术化

• custom gate: 自定义门

• lookup: 查找表

• field：域

• grand product: 大乘积

• generalization: 泛化

• selector: 选择子

• row: 行

• column: 列

• cell：单元格

• lagrange basis polynomial: 拉格朗日基多项式

• floor planner：布局器

• gadget：小工具

• scalar: 标量

• vanishing polynomial：消退多项式

相关概念

首先，我们将描述零知识证明系统halo2依赖的算术化(电路描述方法); 其次介绍电路实现的相关抽象概念。

证明系统

证明系统 的目标是能够证明有趣的数学或者密码学论述.

通常，在一个给定的协议中，我们想要证明不同公共输入的一系列论述。证明者需要展示他们知道一些隐私输入，满足论述。

为此，我们描绘了一个关系，$\mathcal{R}$，这个关系指定哪些公共输入和隐私输入组合是有效的。

上面的术语和 ZKProof Community Reference 保持一致

准确地说，我们应该区分关系$\mathcal{R}$ 和它在证明系统中实现。后者我们称为电路。

我们用来表示特定证明系统的电路的语言叫做算术化。通常，算术化会以多项式约束的形式定义电路。这些约束作用于某个域上的变量。

将一个特定关系的表达成电路的过程有时也叫作 "算术化", 但是我们避免这种叫法。

为了生成一个论述的证明, 证明者需要知道电路需要的隐私输入以及中间值，这些称为advice。

我们假设我们能通过隐私和公开输入计算出advice。这些advice值依赖于我们实现的电路，而不仅仅取决于论述。

隐私输入和advice一起称为论据（ witness）。

有些作者将隐私输入看成论据, 但是在我们看来, 论据还包括advice，即论据包括证明者提供给电路的所有值。

举个例子, 假设我们想证明原像 $x$ 经过哈希函数 $H$ 得到摘要 $y$：

• 原像 $x$是隐私输入

• 摘要$y$是公开输入

• 关系为 $\{(x,y):H(x)=y\}$.

• 对于特定的公共输入 $Y$, 论述是$\{(x):H(x)=Y\}$.

• advice是实现哈希函数的电路中的所有中间值。论据是$x$和advice。

非交互式证明允许证明者对特定的论述和论据生成一个证明。证明可以使验证者相信存在论据使论述成立。这种证明不能错误地说服验证者的安全特性称为可靠性。

非交互式知识证明（NARK）进一步使验证者确信证明者知道使论述成立的论据。这个安全属性称为知识可靠性，它暗示了可靠性。

在实践中，对于密码协议来说，知识可靠性比可靠性更有用：如果我们对在某个协议中Alice是否持有密钥感兴趣，我们需要Alice证明她知道密钥，而不仅仅是密钥存在。

知识的可靠性是通过一个提取器来证明。提取器精确观察证明生成过程，能计算出论据。

如果证明是可塑的，这个性质有点微妙。 也就是说，有些证明系统，在不知道论据的情况下，在现有证明的基础上修改生成新的证明。使用了可塑证明系统的协议需要考虑这一点。

即使没有可塑性, 证明也很可能回放。举个例子，在我们的例子中，我们不希望Alice能够提交别人生成的证明，证明她知道密钥。

如果一个证明没有论据相关信息(除了论据信息存在和证明者知道这些信息外)， 我们说这样的证明系统是零知识的。

如果证明系统能生成简短的证明 - 相对电路大小多项式对数大小的话，我们说，证明是简洁的。 一个简洁的NARK叫做 snark(简洁的非交互式证明 - Succinct Non-Interactive Argument of Knowledge)。

根据这个定义, 一个SNARK不需要关于电路大小的多项式对数级验证时间。有些论文使用术语有效性（efficient）来描述具有这种性质的SNARK，但我们将避免使用这个术语，因为它对于支持聚合或递归验证的SNARK来说，语义是模糊的，我们稍后会讲。

zk-SNARK 叫做零知识SNARK。

PLONK化算术化

halo2采用的算术化来自于 PLONK，或者更准确地说，来自它的扩展UltraPLONK，支持自定义门和查找表。我们称之为PLONK化（ PLONKish）。

PLONK化电路是用矩形矩阵定义的。矩阵的行，列，单元格 和传统矩阵叫法意义一致。

PLONK化电路依赖配置 （configuation）：

• 一个有限域$\mathbb{F}$，其中单元格的值(给定论述和论据)是$\mathbb{F}$的元素。

• 矩阵中列的个数是固定的。列可能是fixed、advice或者instance。Fixed列在电路中是固定的；advice列是论据信息；instance列通常用作公开输入（技术上讲, 它们可以是证明者和验证者之间共享的任何元素）。

• 一些列参与相等约束。

• 多项式阶的范围。

• 一系列多项式约束。这些多项式每一行在 $\mathbb{F}$ 上的取值为零。多项式约束中的变量可以是给定列当前行中的单元格，也可以是给定列中与这行相关的行（比如模$n$)。每个多项式的最高阶由多项式阶的范围限定。

• 一系列的查找表论据，定义了查找表的输入和查找表相关的列。

PLONK化电路还定义:

• 矩阵的行数为 $n$。$n$ 必须对应于${\mathbb{F}}^{\times }$的乘法子群的大小；通常是2的幂次。

• 一系列相等约束，指定两个给定单元格必须具有相等的值。

• 固定列中每行的固定值。

根据电路，我们可以生成电路证明和验证操作所需要的证明密钥 和验证密钥。

请注意，我们指定了列的顺序、多项式约束、查找表论据和相等约束，这些并不影响电路的含义。但这些使得证明和验证密钥的确定性的生成过程变得更加容易。

通常，配置将定义多项式约束，这些约束由定义在fixed列中的选择子关闭和开启。例如，一个约束 $q_i\cdot p(...)=0$ 可以通过在第i行设置$q_i=0$来关闭。在这种情况下，我们通常将多个选择子控制的一组约束，称一个门（gate）。通常标准门支持一些通用操作，比如域上的乘法和除法， 自定义门支持更专门的操作。

芯片

先前的章节介绍了一个低层的电路描述。在实现电路时， 我们通常会使用上层的API，这些API具有以可审核、高效、模块化和表达性强等特征。

在这些API中使用的一些术语和概念来源于集成电路的设计和布局。关于集成电路，通过组合特定功能的芯片更容易获得上述诸多特征。

举个例子， 我们可能有实现特定密码学原语的芯片，比如说哈希或者加密函数，或者像标量乘法或配对算法。

在UPA中，在实现了域上乘法和加法的标准门上可以构造任何电路逻辑。然而， 使用自定义门电路可以获得更高的效率。

采用我们的API， 我们可以设计使用自定义门的芯片。这些API是一个抽象层， 将上层的芯片设计和低层复杂的自定义门隔离开。

尽管有时我们需要 "身兼两职"， 既要写上层的电路， 又要写上层电路所需要的芯片。这样做的目的是使代码更易于理解、审计和维护/重用。通过这种方法也排除了一些潜在的实现的错误。

UPA中的门通过相对引用 引用单元格，比如给定列中的某个单元格，或者某个选择子的相对偏移的单元格。当偏移非零时， 我们称之为 偏移引用 (也就是说， 偏移引用是相对引用的子集)。

和绝对引用 相反， 相对引用在相等约束中使用， 能指向任意单元格。

偏移引用的原因是减少配置中列的数量，从而减少证明的大小。如果没有偏移引用，则需要单独列来保存自定义门引用的每个值， 并我们需要使用相等约束，约束电路的其他单元格和该列中的单元格。使用偏移引用， 我们不仅需要更少的列， 我们也不需要为所有这些列增加约束，从而提高电路效率。

R1CS(对于一些读者来说，可能这个算术化更熟悉， 如果不是，也不要担心)电路包含了“海量的门”，这些门并没有语义上的顺序。 另一方面， UPA电路中的采用偏移引用， 行顺序非常重要。我们做一些简单的假定和定义一些抽象概念来控制电路结构复杂性: 小工具，内部实现电路构造，在小工具之间我们不采用相对引用或者特殊的门布局。

我们把一个电路分到多个区域 ， 每一个区域都包含着一个不相交的单元格子集， 相对引用只在区域内使用。 芯片实现的部分职责是确保进行偏移引用的门被放置在区域的正确位置。

给定一些区域和他们的形状， 我们将使用一个单独的布局器 来决定每个区域放置在哪里(即起始行在哪里)。 目前实现了一个通用的布局器，如果有需要，你可以实现你自己的布局器。

布局器一般会在矩阵中留空一些区域， 因为在给定的行中，电路没有使用所有可用的列。 它们尽最大可能由不需要偏移引用的门填充。这些门可以被放置在一行中的任何位置。

芯片也定义了查找表。 如果同一个查找表论据中定义了多个表， 可以使用标记列指明每行使用了哪一个表。也可以把多个表组合成一张表(受多项式阶范围限制)进行查找。

芯片组合

为了将几个芯片的功能结合起来，我们将它们组合成树状。 最高层次的芯片定义fixed列、advice列和instance列，然后指定它们在较低层次芯片上的分布。

在最简单的情况下，每个底层芯片将使用与其他芯片不相同的列。然而，在芯片之间共享列也是允许的。优化advice列的数量尤其重要，因为这会影响证明大小。

芯片组合的结果(可能在优化之后)是一个UPA配置。电路实现将在芯片上参数化，并且可以通过上层芯片使用支持的底层芯片的功能。

我们希望不那么专业的用户通常能够找到支持他们需要的操作的现有芯片，或者只需要对现有芯片做微小修改。专家级用户可以自己实现电路优化。 ECC 以善于优化电路而闻名 🙂。

小工具

当实现一个电路时，我们可以直接使用我们选择的芯片的功能。 但通常，我们会通过小工具 使用他们。 这种间接方式是很有用的，因为由于效率和UPA的限制，芯片接口通常依赖于底层的实现细节。小工具接口可以提供更加方便和稳定的API，这些API可以从繁琐的细节中抽象出来。

举个例子，比如哈希函数SHA-256。 支持SHA-256的芯片接口可能是依赖于哈希函数的内部设计，例如message schedule和压缩函数的隔离。 相应的小工具接口可以提供更加方便和熟悉的 update/finalize API，也能够在不需要芯片支持的情况下支持hash函数的部分功能，比如说 补齐功能。这有点像CPU上的加速指令并不是直接访问，而是通过软件库调用。

小工具同时能为上层电路提供一个模块化，可重用的抽象，类似于在像 libsnark，bellman这样的库中的使用。 不光函数进行抽象，类型也进行抽象，例如特定大小的椭圆曲线上的点或整数。

用户手册

你来这里可能是因为你想写电路？太好了！

本节将指导你通过halo2创建电路的过程。

开发者工具

Rust库 halo2 中包含了数个工具，为你设计并开发自己的电路提供帮助。

Mock prover

halo2::dev::MockProver 是一个用来调试电路用的工具。除此之外，它还可以用来在单元测试中快速检验电路正确性。

隐私输入和公开输入的计算过程，是和生成一个真正的证明一样。但是，MockProver::run 函数只会生成一个对象，它直接检验电路中每一条约束是否满足。如果电路中某个约束不满足，那这个对象就会返回关于该约束的一个细粒度的错误信息。

消耗估算器

程序 cost-model 可以根据电路设计所采用的不同参数，估算出，验证一个证明的时长，以及对应的证明大小。

用法: cargo run --example cost-model -- [OPTIONS] k

Positional arguments:
  k                       2^k 总行数的上界.

Optional arguments:
  -h, --help              打印此用法信息.
  -a, --advice R[,R..]    An advice column with the given rotations. May be repeated.
  -i, --instance R[,R..]  An instance column with the given rotations. May be repeated.
  -f, --fixed R[,R..]     A fixed column with the given rotations. May be repeated.
  -g, --gate-degree D     Maximum degree of the custom gates.
  -l, --lookup N,I,T      A lookup over N columns with max input degree I and max table degree T. May be repeated.
  -p, --permutation N     A permutation over N columns. May be repeated.

比如，估算有三个 advice列，一个 fixed 列（有相对引用）和门的最高次数为4的电路:

cargo run --example cost-model -- -a 0,1 -a 0 -a 0,-1,1 -f 0 -g 4 11
    Finished dev [unoptimized + debuginfo] target(s) in 0.03s
     Running `target/debug/examples/cost-model -a 0,1 -a 0 -a 0,-1,1 -f 0 -g 4 11`
Circuit {
    k: 11,
    max_deg: 4,
    advice_columns: 3,
    lookups: 0,
    permutations: [],
    column_queries: 7,
    point_sets: 3,
    estimator: Estimator,
}
Proof size: 1440 bytes
Verification: at least 81.689ms

一个简单例子

我们以一个简单电路为例，给大家介绍 halo2 所提供的应用编程接口，以及如何使用它们。示例电路有一个公开输入$c$, 可证明知道两个隐私输入$a$和$b$，使得下式成立。 $$a^2\cdot b^2=c$$

定义指令

首先，我们需要定义我们的电路所依赖的指令，指令介于高层的工具（gadgets）和底层的电路操作之间。指令既可以细粒度也可以粗粒度，但在实践中，指令的功能应当足够小，这样可以重复使用；但又要足够大，这样可以优化它的实现。设计者应当在这两者之间取得平衡。

在我们的样例电路中，我们将使用如下三种指令：

• 加载一个隐私数到电路中；
• 计算两个数的乘积；
• 将一个数设置为电路的公开输入。

我们还需要一个类型来表示其值为数的变量。

#![allow(unused)]
fn main() {
trait NumericInstructions<F: FieldExt>: Chip<F> {
    /// 用于表示一个数的变量
    type Num;

    /// 将一个数加载到电路中，用作隐私输入
    fn load_private(&self, layouter: impl Layouter<F>, a: Option<F>) -> Result<Self::Num, Error>;

    /// 将一个数加载到电路中，用作固定常数
    fn load_constant(&self, layouter: impl Layouter<F>, constant: F) -> Result<Self::Num, Error>;

    /// 返回 `c = a * b`.
    fn mul(
        &self,
        layouter: impl Layouter<F>,
        a: Self::Num,
        b: Self::Num,
    ) -> Result<Self::Num, Error>;

    /// 将一个数置为电路的公开输入
    fn expose_public(
        &self,
        layouter: impl Layouter<F>,
        num: Self::Num,
        row: usize,
    ) -> Result<(), Error>;
}
}

定义芯片的实现

在示例电路中，我还将构造一个芯片，其功能包含上述的有限域上的数值指令。

#![allow(unused)]
fn main() {
/// 这块芯片将实现我们的指令集！芯片存储它们自己的配置，
///  必要情况下也要包含 type markers
struct FieldChip<F: FieldExt> {
    config: FieldConfig,
    _marker: PhantomData<F>,
}
}

每一个"芯片"类型都要实现Chip接口。Chip接口定义了Layouter在做电路综合时可能需要的关于电路的某些属性，以及若将该芯片加载到电路所需要设置的任何初始状态。

#![allow(unused)]
fn main() {
impl<F: FieldExt> Chip<F> for FieldChip<F> {
    type Config = FieldConfig;
    type Loaded = ();

    fn config(&self) -> &Self::Config {
        &self.config
    }

    fn loaded(&self) -> &Self::Loaded {
        &()
    }
}
}

配置芯片

需要为芯片配置好实现我们想要的功能所需要的那些列、置换、门。

#![allow(unused)]
fn main() {
/// 芯片的状态被存储在一个 config 结构体中，它是在配置过程中由芯片生成，
/// 并且存储在芯片内部。
#[derive(Clone, Debug)]
struct FieldConfig {
    /// 对于这块芯片，我们将用到两个 advice 列来实现我们的指令集。
    /// 它们也是我们与电路的其他部分通信所需要用到列。
    advice: [Column<Advice>; 2],

    /// 这是公开输入（instance）列
    instance: Column<Instance>,

    // 我们需要一个 selector 来激活乘法门，从而在用不到`NumericInstructions::mul`指令的
    //  cells 上不设置任何约束。这非常重要，尤其在构建更大型的电路的情况下，列会被多条指令集用到
    s_mul: Selector,

    /// 用来加载常数的 fixed 列
    constant: Column<Fixed>,
}

impl<F: FieldExt> FieldChip<F> {
    fn construct(config: <Self as Chip<F>>::Config) -> Self {
        Self {
            config,
            _marker: PhantomData,
        }
    }

    fn configure(
        meta: &mut ConstraintSystem<F>,
        advice: [Column<Advice>; 2],
        instance: Column<Instance>,
        constant: Column<Fixed>,
    ) -> <Self as Chip<F>>::Config {
        meta.enable_equality(instance.into());
        meta.enable_constant(constant);
        for column in &advice {
            meta.enable_equality((*column).into());
        }
        let s_mul = meta.selector();

        // 定义我们的乘法门
        meta.create_gate("mul", |meta| {
            // 我们需要3个 advice cells 和 1个 selector cell 来实现乘法
            // 我们把他们按下表来排列：
            //
            // | a0  | a1  | s_mul |
            // |-----|-----|-------|
            // | lhs | rhs | s_mul |
            // | out |     |       |
            //
            // 门可以用任一相对偏移，但每一个不同的偏移都会对证明增加开销。
            // 最常见的偏移值是 0 (当前行), 1(下一行), -1(上一行)。
            // 针对这三种情况，有特定的构造函数来构造`Rotation` 结构。
            let lhs = meta.query_advice(advice[0], Rotation::cur());
            let rhs = meta.query_advice(advice[1], Rotation::cur());
            let out = meta.query_advice(advice[0], Rotation::next());
            let s_mul = meta.query_selector(s_mul);

            // 最终，我们将约束门的多项式表达式返回。
            // 对于我们的乘法门，我们仅需要一个多项式约束。
            //
            // `create_gate` 函数返回的多项式表达式，在证明系统中一定等于0。
            // 我们的表达式有以下性质：
            // - 当 s_mul = 0 时，lhs, rhs, out 可以是任意值。
            // - 当 s_mul != 0 时，lhs, rhs, out 将满足 lhs * rhs = out 这条约束。 
            vec![s_mul * (lhs * rhs - out)]
        });

        FieldConfig {
            advice,
            instance,
            s_mul,
            constant,
        }
    }
}
}

实现芯片功能

#![allow(unused)]
fn main() {
/// 用于表示数的变量
#[derive(Clone)]
struct Number<F: FieldExt> {
    cell: Cell,
    value: Option<F>,
}

impl<F: FieldExt> NumericInstructions<F> for FieldChip<F> {
    type Num = Number<F>;

    fn load_private(
        &self,
        mut layouter: impl Layouter<F>,
        value: Option<F>,
    ) -> Result<Self::Num, Error> {
        let config = self.config();

        let mut num = None;
        layouter.assign_region(
            || "load private",
            |mut region| {
                let cell = region.assign_advice(
                    || "private input",
                    config.advice[0],
                    0,
                    || value.ok_or(Error::SynthesisError),
                )?;
                num = Some(Number { cell, value });
                Ok(())
            },
        )?;
        Ok(num.unwrap())
    }

    fn load_constant(
        &self,
        mut layouter: impl Layouter<F>,
        constant: F,
    ) -> Result<Self::Num, Error> {
        let config = self.config();

        let mut num = None;
        layouter.assign_region(
            || "load constant",
            |mut region| {
                let cell = region.assign_advice_from_constant(
                    || "constant value",
                    config.advice[0],
                    0,
                    constant,
                )?;
                num = Some(Number {
                    cell,
                    value: Some(constant),
                });
                Ok(())
            },
        )?;
        Ok(num.unwrap())
    }

    fn mul(
        &self,
        mut layouter: impl Layouter<F>,
        a: Self::Num,
        b: Self::Num,
    ) -> Result<Self::Num, Error> {
        let config = self.config();

        let mut out = None;
        layouter.assign_region(
            || "mul",
            |mut region: Region<'_, F>| {
                // 在这个 region 中，我们只想用一个乘法门，所以我们在 region 偏移 0 处，
                //  激活它；这意味着它将对 0偏移 和 1偏移处的两个 cells 进行约束。
                config.s_mul.enable(&mut region, 0)?;

                // 给我们的输入有可能在电路的任一位置，但在当前 region 中，我们仅可以用
                // 相对偏移。所以，我们在 region 内分配新的 cells 并限定他们的值与输入 cells 的值相等。
                let lhs = region.assign_advice(
                    || "lhs",
                    config.advice[0],
                    0,
                    || a.value.ok_or(Error::SynthesisError),
                )?;
                let rhs = region.assign_advice(
                    || "rhs",
                    config.advice[1],
                    0,
                    || b.value.ok_or(Error::SynthesisError),
                )?;
                region.constrain_equal(a.cell, lhs)?;
                region.constrain_equal(b.cell, rhs)?;

                // 现在我们可以把乘积放到输出的位置了。
                let value = a.value.and_then(|a| b.value.map(|b| a * b));
                let cell = region.assign_advice(
                    || "lhs * rhs",
                    config.advice[0],
                    1,
                    || value.ok_or(Error::SynthesisError),
                )?;

                // 最后，我们返回一个用来表示输出的变量，它会被用在电路的另一个部分。
                out = Some(Number { cell, value });
                Ok(())
            },
        )?;

        Ok(out.unwrap())
    }

    fn expose_public(
        &self,
        mut layouter: impl Layouter<F>,
        num: Self::Num,
        row: usize,
    ) -> Result<(), Error> {
        let config = self.config();

        layouter.constrain_instance(num.cell, config.instance, row)
    }
}
}

构造电路

既然我们已经有了所需要的指令，以及一块实现了这些指令的芯片，我们终于可以构造示例电路啦!

#![allow(unused)]
fn main() {
/// 完整的电路实现
///
/// 在这个结构体中，我们保存隐私输入变量。我们使用 `Option<F>` 类型是因为，
/// 在生成密钥阶段，他们不需要有任何的值。在证明阶段中，如果它们任一为 `None` 的话，
/// 我们将得到一个错误。
#[derive(Default)]
struct MyCircuit<F: FieldExt> {
    constant: F,
    a: Option<F>,
    b: Option<F>,
}

impl<F: FieldExt> Circuit<F> for MyCircuit<F> {
    // 因为我们在任一地方值用了一个芯片，所以我们可以重用它的配置。
    type Config = FieldConfig;
    type FloorPlanner = SimpleFloorPlanner;

    fn without_witnesses(&self) -> Self {
        Self::default()
    }

    fn configure(meta: &mut ConstraintSystem<F>) -> Self::Config {
        // 我们创建两个 advice 列，作为 FieldChip 的输入。
        let advice = [meta.advice_column(), meta.advice_column()];

        // 我们还需要一个 instance 列来存储公开输入。
        let instance = meta.instance_column();

        // 创建一个 fixed 列来加载常数
        let constant = meta.fixed_column();

        FieldChip::configure(meta, advice, instance, constant)
    }

    fn synthesize(
        &self,
        config: Self::Config,
        mut layouter: impl Layouter<F>,
    ) -> Result<(), Error> {
        let field_chip = FieldChip::<F>::construct(config);

        // 将我们的隐私值加载到电路中。
        let a = field_chip.load_private(layouter.namespace(|| "load a"), self.a)?;
        let b = field_chip.load_private(layouter.namespace(|| "load b"), self.b)?;

        // 将常数因子加载到电路中
        let constant =
            field_chip.load_constant(layouter.namespace(|| "load constant"), self.constant)?;

        // 我们仅有乘法可用，因此我们按以下方法实现电路：
        //     asq  = a*a
        //     bsq  = b*b
        //     absq = asq*bsq
        //     c    = constant*asq*bsq
        //
        // 但是，按下面的方法实现，更加高效: 
        //     ab   = a*b
        //     absq = ab^2
        //     c    = constant*absq
        let ab = field_chip.mul(layouter.namespace(|| "a * b"), a, b)?;
        let absq = field_chip.mul(layouter.namespace(|| "ab * ab"), ab.clone(), ab)?;
        let c = field_chip.mul(layouter.namespace(|| "constant * absq"), constant, absq)?;

        // 将结果作为电路的公开输入进行公开
        field_chip.expose_public(layouter.namespace(|| "expose c"), c, 0)
    }
}
}

测试电路的功能

可以用 halo2::dev::MockProver 对象来测试一个电路是否正常工作。构造电路的一组隐私输入和公开输入，这组输入可直接用来计算合法证明，但我们把这组输入传入到MockProver::run函数中之后，就能得到一个可用于检验电路中每一条约束是否满足的对象。而且电路验证不过，这个对象还能输出那条不满足的约束。

#![allow(unused)]
fn main() {
    // 我们电路的行数不能超过 2^k. 因为我们的示例电路很小，我们选择一个较小的值
    let k = 4;

    // 准备好电路的隐私输入和公开输入
    let constant = Fp::from(7);
    let a = Fp::from(2);
    let b = Fp::from(3);
    let c = constant * a.square() * b.square();

    // 用隐私输入来实例化电路
    let circuit = MyCircuit {
        constant,
        a: Some(a),
        b: Some(b),
    };

    // 将公开输入进行排列。乘法的结果被我们放置在 instance 列的第0行，
    // 所以我们把它放在公开输入的对应位置。
    let mut public_inputs = vec![c];

    // 给定正确的公开输入，我们的电路能验证通过
    let prover = MockProver::run(k, &circuit, vec![public_inputs.clone()]).unwrap();
    assert_eq!(prover.verify(), Ok(()));

    // 如果我们尝试用其他的公开输入，证明将失败！
    public_inputs[0] += Fp::one();
    let prover = MockProver::run(k, &circuit, vec![public_inputs]).unwrap();
    assert!(prover.verify().is_err());
}

完整例子

这里 有示例的所有源代码。

查找表

在正常的程序中，你可以采用内存换CPU的方法来提高性能，即为计算的某一部分预计算出查找表，并存在内存中。我们也可以在 halo2 电路中实现类似的策略。

我们可以将一个查找表理解成变量之间存在一个关系，该关系可以表示成一个表。假设在我们的约束系统中仅有一个查找证明，那么查找表的总大小的上限为电路规模，即每一个表项占用一行，每一个表查找占用一行。

实用的小方法

本节包含几个写 halo2 电路时能用帮上忙的小策略。

小范围（or 区间?）约束

在 R1CS 电路中，经常用到的一种约束就是布尔约束: $b\ast (1-b)=0$. 这种约束限定了 $b=0$ 或者 $b=1$.

类似地，在 halo2 电路中，你也可以限定一个 单元格 在一个小集合内取值。比如，若要限定 $a$的值落在区间 $[\mathrm{0..5}]$，你可以构建如下形式的门:

$$a\cdot (1-a)\cdot (2-a)\cdot (3-a)\cdot (4-a)=0$$

又比如，要限定 $c$ 等于 7 或 13，你可以用如下的门:

$$(7-c)\cdot (13-c)=0$$

基本原理就是，我们构建一个多项式约束，使得其根集合与我们想限定的取值集合相同。 R1CS 电路支持的多项式次数最大为2（因为所有的约束方程必须具有 $a\ast b=c$ 的形式）。 而 halo2 电路支持任意次数的多项式，只不过更高次数会带来更大的代价。

需要注意，这些根不必是常量；比如，可以用 $(a-x)\cdot (a-y)\cdot (a-z)=0$ 来限定 $a$ 等于集合 $\{x,y,z\}$ 中的任一元素。而且，

小集合插值

我们可以用 Lagrange 插值法构造一个多项式约束，证明 $f(X)=Y$，其中 $X\in \{x_i\},Y\in \{y_i\}$ 。

例如，假设我们想把两个比特的值通过插零扩展为“Spread”4个比特值。我们首先预计算出每一个点上的取值：

$$\begin{array}{rcl}00\to 0000& ⟹& 0\to 0\\ 01\to 0001& ⟹& 1\to 1\\ 10\to 0100& ⟹& 2\to 4\\ 11\to 0101& ⟹& 3\to 5\end{array}$$

然后，为每一个点计算出对应的 Lagrange 基多项式(basis polynomial)，其中 $k$ 是点的个数（在我们的例子中，$k=4$）：

$$l_j(X)=\prod _{0\le m<k,m\ne j}\frac{x-x_m}{x_j-x_m},$$

回顾一下，Lagrange 基多项式 $l_j(X)$ 满足如下性质：若 $X=x_j$, 则 $l_j(X)=1$；否则，$X=x_i(i\ne j)$，一定有 $l_j(X)=0$。

回到我们刚才举的例子，我们就计算出了4个 Lagrange 基多项式：

$$\begin{array}{ccc}{l}_0(X)& =& \frac{(X-3)(X-2)(X-1)}{(-3)(-2)(-1)}\\ l_1(X)& =& \frac{(X-3)(X-2)(X)}{(-2)(-1)(1)}\\ l_2(X)& =& \frac{(X-3)(X-1)(X)}{(-1)(1)(2)}\\ l_3(X)& =& \frac{(X-2)(X-1)(X)}{(1)(2)(3)}\end{array}$$

那么，我们就得到了如下所示的多项式约束：

$$\begin{array}{cccccccccccl}& f(0)\cdot l_0(X)& +& f(1)\cdot l_1(X)& +& f(2)\cdot l_2(X)& +& f(3)\cdot l_3(X)& -& f(X)& =& 0\\ ⟹& 0\cdot l_0(X)& +& 1\cdot l_1(X)& +& 4\cdot l_2(X)& +& 5\cdot l_3(X)& -& f(X)& =& 0.\end{array}$$

设计

语言方面的注解

我们用和其他语言稍微不同的语言描述PLONK的相关概念。总体上：

1. 我们把PLONK相关的证明看成表，每一列对应一根“线”。表中元素我们称为“单元格”。
2. 我们喜欢说“选择子多项式”和“固定列”。当一个在固定列的单元格用来控制一个行中的约束是否开启的时候，我们称“选择子约束“。
3. 其他多项式，我们称为”advice列“。这些列由证明者提供。
4. 我们用”规则“字眼表述一个”门“，比如 $$A(X)\cdot q_A(X)+B(X)\cdot q_B(X)+A(X)\cdot B(X)\cdot q_M(X)+C(X)\cdot q_C(X)=0.$$
   • TODO: Check how consistent we are with this, and update the code and docs to match.

证明系统

Halo2的证明系统可以分解成五个部分：

1. 对电路中的主要模块多项式承诺：
   • 单元格的赋值
   • 查找表证明中的置换和乘积
   • 相等约束的置换
2. 电路中和零相关的部分，构造消退证明：
   • 标准的和自定义门
   • 查找表规则
   • 相等约束规则
3. 在所有需要的点上，获取上述多项式的取值：
   • 所有自定义门上的偏移信息
   • 消退证明的各个部分
4. 构建多点打开证明，检查所有的多项式取值和相应的承诺是否一致
5. 采用内积证明为多点打开证明生成证明

这些部分依次在本章节讲解。

举个例子

为了辅助我们的解释，我们时不时地用如下的约束系统：

• 四个advice列 $a,b,c,d$
• 一个fixed列 $f$
• 三个自定义门：
  • $a\cdot b\cdot c_{-1}-d=0$
  • $f_{-1}\cdot c=0$
  • $f\cdot d\cdot a=0$

太长不读

Halo2协议的简洁描述整理在如下的表格中。这部分会被Halo2的论文和安全性证明替代，目前作为后面子章节的总结：

Then the prover and verifier:

• Construct $\text{finalPoly}(X)$ as a linear combination of $\mathbf{Q}$ and $U$ using powers of $x_4$;
• Construct $\text{finalPolyEval}$ as the equivalent linear combination of ${\mathbf{q}}_{\text{evals}}$ and $u_{\text{eval}}$; and
• Perform $\text{InnerProduct}(\text{finalPoly}(X),x_3,\text{finalPolyEval}).$

TODO: Write up protocol components that provide zero-knowledge.

查找表（Lookup）论据

halo2实现任意集合的数据查找，相比Plookup简单。

语言（Language）说明

除了 语言的一般说明:

• $Z(X)$多项式（针对置换论据的大乘积论据多项式）称为“置换乘积”列。

技术描述

为了解释简单，我们先描述一个忽略零知识证明的论据描述的简单版本。

查找可以表示成 $2^k$行表（编号从0开始）的“子集”。$A$和$S$列分别是“子集”和“全集”。

“子集”论据保证$A$列中的元素都在 $S$列中。这意味着，$A$列中多个位置的元素对应着$S$列中同一位置的元素，并且$S$列中的某些元素可以不出现在$A$列的任何位置上。

• $S$ 列并不一定是固定的。也就是说，我们可以支持固定元素的查找或者动态查找（后者采用advice列）。
• $A$ 和$S$列中的元素可以重复。如果$A$ 和$S$列中的元素个数不正好是$2^k$的话，可以用$A$ 和$S$列中任意元素进行扩展。
  • 或者我们可以增加一个“查找选择子”，控制在$A$列中的哪些元素参与查找。采用这种方法可以替换下述公式中的$A(X)$ 。如果一个元素不需要查找，用$S_0$替换$A$。

假设 ${\ell }_i$ 是拉格朗日基多项式，在$i$行多项式为1，其他行为0。

从$A$ 和$S$列的置换开始。假设它们的置换分别为$A^{\prime }$ 和 $S^{\prime }$列。我们可以通过置换论据$Z$约束它们之间的置换关系： $$\begin{gathered} Z(\omega X)\cdot (A^{\prime }(X)+\beta )\cdot (S^{\prime }(X)+\gamma )-Z(X)\cdot (A(X)+\beta )\cdot (S(X)+\gamma )=0 \\ {\ell }_0(X)\cdot (1-Z(X))=0 \end{gathered}$$

也就是说，在除以0不发生的情况下，对所有的$i\in [0,2^k)$满足： $$\begin{gathered} Z_{i+1}=Z_i\cdot \frac{(A_i+\beta )\cdot (S_i+\gamma )}{(A_i^{\prime }+\beta )\cdot (S_i^{\prime }+\gamma )} \\ {Z}_{2^k}=Z_0=1. \end{gathered}$$

这个版本的论据证明$A^{\prime }$ 和 $S^{\prime }$列是$A$ 和$S$列的置换，但是并没有指明具体的置换关系。$\beta$ 和$\gamma$ 是独立因子。采用这两个因子，可以将两个置换论据组合在一起，不需要担心相互干扰。

这些置换的目的是让证明者提供的$A^{\prime }$ 和 $S^{\prime }$列满足一定的条件：

1. $A^{\prime }$列中相同的元素位置靠在一起。这可以通过某种排序算法实现。重要的是，相同的元素在$A^{\prime }$列中挨在一起，并且$A^{\prime }$列是$A$列的置换。
2. $A^{\prime }$列中挨在一起的相同元素的第一个元素存在于$S^{\prime }$列中。除去这个限制外，$S^{\prime }$列是$S$列的一个任意置换。

现在我们通过如下的规则限制$A_i^{\prime }=S_i^{\prime }$ 或者 $A_i^{\prime }=A_{i-1}^{\prime }$： $$(A^{\prime }(X)-S^{\prime }(X))\cdot (A^{\prime }(X)-A^{\prime }({\omega }^{-1}X))=0$$

除此之外，我们通过如下的规则限制$A_0^{\prime }=S_0^{\prime }$：

$${\ell }_0(X)\cdot (A^{\prime }(X)-S^{\prime }(X))=0$$

由于第二个规则，第一个规则中的($A^{\prime }(X)-A^{\prime }({\omega }^{-1}X)$ 这一项在$0$行没有效果，尽管 ${\omega }^{-1}X$ “能反转”。

这些约束规则一起有效的限制了$A^{\prime }$列（也就是$A$列）中的每个元素都存在于 $S^{\prime }$列中（也就是$S$列）。

加入零知识

为了在PLONK算法为基础的证明系统中加入零知识，我们需要在每列的最后加入$t$个随机元素。这些需要对查找论据进行调整，因为这些随机的元素并不满足之前的约束。

我们限制有效的行数为$u=2^k-t-1$。我们增加两个选择子：

• $q_{blind}$ 在最后 $t$ 行设置为1，其他行设置为0；
• $q_{last}$ 只在$u$行设置为1，其他行设置为0 （也就是说，它设置在有效行和盲化行的交界处）。

我们将之前的规则限制在有效行上：

$$\begin{gathered} (1-(q_{last}(X)+q_{blind}(X)))\cdot (Z(\omega X)\cdot (A^{\prime }(X)+\beta )\cdot (S^{\prime }(X)+\gamma )-Z(X)\cdot (A(X)+\beta )\cdot (S(X)+\gamma ))=0 \\ (1-(q_{last}(X)+q_{blind}(X)))\cdot (A^{\prime }(X)-S^{\prime }(X))\cdot (A^{\prime }(X)-A^{\prime }({\omega }^{-1}X))=0 \end{gathered}$$

在$0$行的限制规则保持不变：

$$\begin{gathered} {\ell }_0(X)\cdot (A^{\prime }(X)-S^{\prime }(X))=0 \\ {\ell }_0(X)\cdot (1-Z(X))=0 \end{gathered}$$

因为我们不能再依赖在 ${\omega }^{2^k}$点的环绕保证$Z$为1，相反我们要约束$Z({\omega }^u)$ 为1。这里有个难点：如果在任意$i\in [0,u)$， $A_i+\beta$ 或者 $S_i+\gamma$为0的话，置换论据可能不成立。虽然这种情况在 $\beta$ 和$\gamma$的取值下概率可以忽略，但是，对于完美零知识和完备性来说是个障碍（攻击者可以构造这样的情况）。

确保完美的完备性和零知识，我们允许$Z({\omega }^u)$为0或者1: $$q_{last}(X)\cdot (Z(X{)}^2-Z(X))=0$$

如果$A_i+\beta$ 和 $S_i+\gamma$在某些$i$ 上为0，我们可以在$i<j\le u$范围设置$Z_j=0$，满足上述的约束。

注意的是，挑战因子$\beta$ 和$\gamma$ 是在$A$ 和$S$列（以及$A^{\prime }$ 和 $S^{\prime }$列）承诺后生成的，证明者无法伪造$A_i+\beta$ 和 $S_i+\gamma$为0的情况。因为这种情况的概率可以忽略，可行性不受影响。

开销

• 原始$A$列和固定$S$列。
• 置换函数 $Z$。
• 两个置换$A^{\prime }$ 和 $S^{\prime }$列。
• 约束方程（门）的阶都不高。

泛化

halo2的查找论据实现实现了上述技术的泛化：

• $A$ 和$S$列扩展为多列，这些列之间通过随机挑战因子进行组合。$A^{\prime }$ 和 $S^{\prime }$列还是单列。
  • $S$列的各列承诺可以提前计算。这样在挑战因子确定后，利用Pedersen承诺的同态性质，可以很简便的组合成$S$列的承诺。
  • $A$列可以是采用相对引用的任意多项式表达式。这些可以替换到约束规则中去，受制于最大的阶。这样可能可以省去一个或者多个advice列。
• 这样的话，查找论据可以通过子集论据实现任意长度的关系。也就是说，为了约束$\mathcal{R}(x,y,...)$，将$\mathcal{R}$看成是$S$（通过前面的方法），并且检查关系成立 $(x,y,...)\in \mathcal{R}$。
  • 如果$\mathcal{R}$代表一个函数，同样需要检查输入是否在域中。这是我们想要的，经常会省去额外的范围检查。
• 我们可以在同一个电路中支持多表。利用标示列将多个表组合成一张表。
  • 标示列可以和之前提到的“查找选择子”合并。

这些泛化和Plookup论文的第4和第5节中的技术类似。和Plookup的区别是子集论据。相关技术，子集论据也适用；举个例子，Plookup论文的第5节中的优化范围检查技术同样可以用在子集论据中。

置换证明

假设halo2电路中的门要“本地”操作（就是在当前行或者事先定义好的相关行进行操作） 这通常需要将某个任意单元格的值拷贝到当前行，以便在门中使用。该工作就由一条相等约束来描述， 该约束就强制要求源和目的单元格中包含相同的值。

我们通过构造一个代表这些约束的置换来实现这些相等约束，进而在最终的证明中包含一个置换证明来确保约束成立。

相关记号

置换就是一个集合以一对一的方式自己到自己的一个映射。一个置换可以唯一分解成多个轮换的组合（每个轮换都是首尾相接的，轮换和轮换之间排序）。

通常，我们使用 轮换记号 来表示置换。令 $(abc)$ 代表如下轮换：$a$ 映射到 $b$，$b$ 映射到 $c$，$c$ 映射到 $a$ （显然，该法则可以推广到任意大小的轮换）。把两个或更多的轮换一个接一个的写在一起就代表了一个相关置换的组合。 比如， $(ab)(cd)$ 就代表了 $a$ 映射到 $b$，$b$ 映射到 $a$，$c$ 映射到 $d$，$d$ 映射到 $c$ 的置换。

构造置换

目标

我们希望构造这样一个置换，在同一个相等约束下的这些变量自己形成一个轮换。举例来说，假设我们有一个定义了如下相等约束的电路：

• $a\equiv b$
• $a\equiv c$
• $d\equiv e$

由上可得相等约束集合 $\{a,b,c\}$ 和 $\{d,e\}$。于是我们构造了如下的置换：

$$(abc)(de)$$

该置换就定义了一个由 $[a,b,c,d,e]$ 到 $[b,c,a,e,d]$ 的一个映射。

算法

我们需要持续记录这些轮换的集合，实际上也就是 一些不相交集合的集合. 我们已经知道针对该问题的一种高效的数据结构；为了简单起见，我们选择了一个虽然不是渐进最优，但是确是很容易实现的方法。

我们采取如下方法来表示当前的状态：

• 数组 $\mathsf{mapping}$ 来表示置换本身；

• 一个辅助的数组 $\mathsf{aux}$ 用来记录每个轮换中代表元素；

• 还有一个数组 $\mathsf{sizes}$ 用来记录每个轮换的元素个数。

我们在一个给定的轮换 $C$ 中选取一个不变的值 $c$，对每一个 $C$ 中的元素 $x$，$\mathsf{aux}(x)$ 都得到相同的值，即 $c\in C$。有了这个值，对于给定的两个给定的元素 $x$ 和 $y$，我们可以通过检查 $\mathsf{aux}(x)=\mathsf{aux}(y)$ 是否成立，来快速判断它们是否在同一个轮换中。$\mathsf{sizes}(\mathsf{aux}(x))$ 也代表了包含 $x$ 的轮换的大小。（只有 $\mathsf{sizes}(\mathsf{aux}(x))$ 是有保证的，而不是 $\mathsf{sizes}(x)$。）

本算法是以表示一个单位置换开始： 对所有 $x$，我们令 $\mathsf{mapping}(x)=x$，$\mathsf{aux}(x)=x$，和 $\mathsf{sizes}(x)=1$。

按如下步骤增加一条相等约束 $left\equiv right$：

1. 检查 $left$ 和 $right$ 是否已经在同一个轮换中了，也就是检查 $\mathsf{aux}(left)=\mathsf{aux}(right)$ 是否成立。如果是此种情况，那么不许做任何事情。

2. 否则，$left$ 和 $right$ 就一定分属不同的轮换。令 $left$ 是相对大的轮换，而 $right$ 则为相对小的那个， 如果 $\mathsf{sizes}(\mathsf{aux}(left))<\mathsf{sizes}(\mathsf{aux}(right))$，那我们就交换一下使其满足需求。

3. 令 $\mathsf{sizes}(\mathsf{aux}(left)):=\mathsf{sizes}(\mathsf{aux}(left))+\mathsf{sizes}(\mathsf{aux}(right))$。

4. 下一步对right（较小的）轮换中每一个元素 $x$ 令 $\mathsf{aux}(x):=\mathsf{aux}(left)$。

5. 通过交换 $\mathsf{mapping}(left)$ 和 $\mathsf{mapping}(right)$ 中的元素（的轮换），将较小的轮换接入到较大的轮换中去。

举个例子，假设两个不相交的轮换 $(ABCD)$ 和 $(EFGH)$：

A +---> B
^       +
|       |
+       v
D <---+ C       E +---> F
                ^       +
                |       |
                +       v
                H <---+ G

在增加约束 $B\equiv E$ 后，上文算法将得出如下的轮换：

A +---> B +-------------+
^                       |
|                       |
+                       v
D <---+ C <---+ E       F
                ^       +
                |       |
                +       v
                H <---+ G

Broken alternatives

如果不检查 $left$ 和 $right$ 是否在同一个轮换中，那么我们可能就会丢掉某些相等约束。 举个例子，如果我们有如下的约束:

• $a\equiv b$
• $b\equiv c$
• $c\equiv d$
• $b\equiv d$

如果在处理一条新的相等约束时仅仅只执行上述算法中的第五步，那么我们得到的最终结果将是 $(ab)(cd)$，而不是正确的结果 $(abcd)$。

证明说明

我们需要检查 $m$ 列中所有单元格的置换，该 $m$ 列分别由其拉格朗日基的多项式 $v_0,\dots ,v_{m-1}$ 来表示。

我们用 ${\mathbb{F}}^{\times }$ 中不同的元素来标记 $m$ 列中 每个单元格。

假设我们有基于这些标记的一个置换： $$\sigma (\mathsf{column}:i,\mathsf{row}:j)=(\mathsf{column}:i^{\prime },\mathsf{row}:j^{\prime }).$$ 其中这些轮换就对应了相等约束。

我们考虑对 $\{(label,value)\}$ 的集合，当且仅当对每对的label都按照 $\sigma$ 进行置换后，得到了与原集合相同的集合， 才能证明集合中的每个对是相等的。

因为所有的标记都是不同的，最终就可以用一个代表相等约束的集合来代替多个代表相等关系的集合，而这进一步使我们可以用乘积证明来检查置换的正确性。

令 $\omega$ 是 $2^k$ 次单位根，$\delta$ 是 $T$ 次单位根，满足 $T\cdot 2^S+1=p$，其中 $T$ 是奇数并且 $k\le S$。 在置换证明中，我们用 ${\delta }^i\cdot {\omega }^j\in {\mathbb{F}}^{\times }$ 作为第 $j$ 行、第 $i$ 列的单元格的标记。

$\sigma$ 由 $m$ 个多项式组成的一个向量，其中对每一项 $s_i(X)$ 满足 $s_i({\omega }^j)={\delta }^{i^{\prime }}\cdot {\omega }^{j^{\prime }}$。

注意，可以用一个包含 $m$ 个多项式的向量来标识一个置换，其中每一项 ${\mathsf{ID}}_i({\omega }^j)$ 都满足 ${\mathsf{ID}}_i({\omega }^j)={\delta }^i\cdot {\omega }^j$。

我们用一个挑战 $\beta$ 将每一个 $(label,value)$ 对压缩成 $value+\beta \cdot label$。与在 查找表 的积证明中所做的一样，我们也使用一个挑战 $\gamma$ 来盲化我们每一个积项。

假定有一个在 $m$ 列，即：$v_0,\dots ,v_{m-1}$ 上的一个置换，表示为 $s_0,\dots ,s_{m-1}$，我们想要确保如下等式成立： $$\prod _{i=0}^{m-1}\prod _{j=0}^{n-1}\left(\frac{v_i({\omega }^j)+\beta \cdot {\delta }^i\cdot {\omega }^j+\gamma }{v_i({\omega }^j)+\beta \cdot s_i({\omega }^j)+\gamma }\right)=1$$

上式中 $v_i({\omega }^j)+\beta \cdot {\delta }^i\cdot {\omega }^j$ 代表置换前的对 $(label,value)$，$v_i({\omega }^j)+\beta \cdot s_i({\omega }^j)$ 则代表其置换的对 $(\sigma (label),value)$。

令多项式 $Z_P$ 满足 $Z_P({\omega }^0)=Z_P({\omega }^n)=1$ 并且对 $0\le j<n$: $$\begin{array}{rl}{Z}_P({\omega }^{j+1})& =\prod _{h=0}^j\prod _{i=0}^{m-1}\frac{v_i({\omega }^h)+\beta \cdot {\delta }^i\cdot {\omega }^h+\gamma }{v_i({\omega }^h)+\beta \cdot s_i({\omega }^h)+\gamma }\\ & =Z_P({\omega }^j)\prod _{i=0}^{m-1}\frac{v_i({\omega }^j)+\beta \cdot {\delta }^i\cdot {\omega }^j+\gamma }{v_i({\omega }^j)+\beta \cdot s_i({\omega }^j)+\gamma }\end{array}$$

接下来只需要强制满足如下的规则对证明来说就足够了： $$\begin{gathered} Z_P(\omega X)\cdot \prod _{i=0}^{m-1}\left(v_i(X)+\beta \cdot s_i(X)+\gamma \right)-Z_P(X)\cdot \prod _{i=0}^{m-1}\left(v_i(X)+\beta \cdot {\delta }^i\cdot X+\gamma \right)=0 \\ {\ell }_0\cdot (1-Z_P(X))=0 \end{gathered}$$

注意，上述第一条规则对其处理的多项式的假设是，其约束的列数 $m$ 要符合PLONK设置的次数界限。接下来，将在下文阐述如何处理列数超出边界的情况。

用于表示一个置换的经过优化的简单方法是由Vitalik Buterin为 PLONK 提出的，并且在 PLONK 论文的第8节有阐述 注意在实践中，对 Halo 2 所用的曲线来说，其有相等约束的列数通常不会超过其边界 $T$， 在此条件下，所有的 ${\delta }^i$ 就都是不同二次平方非剩余。

零知识调整

与查找表证明类似，我们也需要调整上述的证明来处理每列的最后 $t$ 行，因为它们被填入了随机值（也就是这些行不满足上面的积证明）。

我们限定有用的行数是 $u=2^k-t-1$，同时我们增加两个选择子，这两个选择子与查找表证明中定义的是一样的：

• $q_{blind}$ 只在最后 $t$ 行设为 $1$ ，而在其他地方则为 $0$。
• $q_{last}$ 则旨在 $u$ 行设为 $1$，其他行则为 $0$ （这就是说，它只在有用行和盲化行之间的那一行起作用）。

我们将在那些有用的行真正应用上文的积规则：

$(1-(q_{last}(X)+q_{blind}(X)))\cdot$ $\left(Z_P(\omega X)\cdot \prod _{i=0}^{m-1}\left(v_i(X)+\beta \cdot s_i(X)+\gamma \right)-Z_P(X)\cdot \prod _{i=0}^{m-1}\left(v_i(X)+\beta \cdot {\delta }^i\cdot X+\gamma \right)\right)=0$

在 $0$ 行的的规则仍然是相同的，即：

$${\ell }_0(X)\cdot (1-Z_P(X))=0$$

由于我们再也不能依赖全景来确保每一个积证明 $Z_P$ 都在 ${\omega }^{2^k}$ 等于 $1$，那么我们实际上应该约束 $Z({\omega }^u)=1$。这也就带来了在查找证明中同样的问题。于是，我们也就需要允许 $Z({\omega }^u)$ 等于 $0$ 或者 $1$：

$$q_{last}(X)\cdot (Z_P(X{)}^2-Z_P(X))=0$$

通过这种方式，我们就获得了良好的完备性和零知识性。

支持大列

在halo2的实现中，实际上并不限制相等约束可以占用的行数。因此，就必须解决上述方法中可能导致的积规则中的多项式可能超出PLONK设置的次数边界的问题。一个简单办法是直接升高次数边界，但是在没有其他规则需要用到如此大的次数的情况下，这一办法是低效的。

另一种方法，我们把积证明分割成 $b$ 个，每个都是其中 $m$ 列的证明，即：$Z_{P,0},\dots Z_{P,b-1},$同时增加一条规则，就是每个积（证明）最终的积被设置成下一个积（证明）的起始值。

这就是说，对于 $0\le a<b$ 我们有：

$(1-(q_{last}(X)+q_{blind}(X)))\cdot$ $\left(Z_{P,a}(\omega X)\cdot \prod _{i=am}^{(a+1)m-1}\left(v_i(X)+\beta \cdot s_i(X)+\gamma \right)-Z_P(X)\cdot \prod _{i=am}^{(a+1)m-1}\left(v_i(X)+\beta \cdot {\delta }^i\cdot X+\gamma \right)\right)$ $=0$

简单起见，上述规则假设总列数是 $m$ 的整数倍； 如果不是，那么我们就让最后一个列集合少于 $m$ 个项。

对第一个列集合，我们有

$${\ell }_0\cdot (1-Z_{P,0}(X))=0$$

而对于剩余的每一个列集合 $0<a<b$，我们将使用如下规则将 $Z_{P,a-1}({\omega }^u)$ 拷贝到下一个列集合的最开始，$Z_{P,a}({\omega }^0)$：

$${\ell }_0\cdot \left(Z_{P,a}(X)-Z_{P,a-1}({\omega }^{u}X)\right)=0$$

与起始算法相同，对最后一个列集合，我们约束 $Z_{P,b-1}({\omega }^u)$ 为 $0$ 或者 $1$。

$$q_{last}(X)\cdot \left(Z_{P,b-1}(X{)}^2-Z_{P,b-1}(X)\right)=0$$

与上文的证明相同，这也提供了同样的完备性和零知识性。

电路承诺

对电路赋值进行承诺

在生成证明之前，证明者已经有了一张能够满足约束条件的单元格赋值表。赋值表有 $n=2^k$ 行；其列被划分为三类： advice, instance, fixed 。我们定义 $F_{i,j}$ 表示第 $j$ 行的第 $i$ 个fixed列，不失一般性，定义 $A_{i,j}$ 为第 $j$ 行的第 $i$ 个advice或instance列。

我们区分开fixed 列的原因是它们是由验证者提供的，而advice 列和instance 列是由证明者提供的。实际上，证明者和验证者都需要计算instance 列和fixed 列的承诺，只有对advice 列的承诺在证明中。

为对表中的各个赋值进行承诺，我们为每列构造一个次数为 $n-1$ 的拉格朗日多项式，其取值域大小为 $n$ （令 $\omega$ 为其 $n$ 次单位根）。

• 令 $a_i({\omega }^j)=A_{i,j}$ ，通过插值得到 $a_i(X)$ 多项式
• 令 $f_i({\omega }^j)=F_{i,j}$ ，通过插值得到 $f_i(X)$ 多项式

然后对每列的多项式创建一个盲化承诺（blinding commitment） ：

$$\mathbf{A}=[\text{Commit}(a_0(X)),\dots ,\text{Commit}(a_i(X))]$$ $$\mathbf{F}=[\text{Commit}(f_0(X)),\dots ,\text{Commit}(f_i(X))]$$

其中 $\mathbf{F}$ 在生成密钥的时候被创建，使用 $1$ 作为盲因子。 $\mathbf{A}$ 由证明者计算并发送给验证者 。

对查找表置换进行承诺

验证者随机选择一个 $\theta$ ，用于确保同一个查找表内不同的列线性无关。接着证明者对每个查找表的置换进行承诺

• 给定一个查找表，其输入列多项式为 $[A_0(X),\dots ,A_{m-1}(X)]$ ，其真值表列的多项式为 $[S_0(X),\dots ,S_{m-1}(X)]$, 证明者构造两个压缩后的多项式

  $$A_{\text{compressed}}(X)={\theta }^{m-1}{A}_0(X)+{\theta }^{m-2}{A}_1(X)+\cdots +\theta A_{m-2}(X)+A_{m-1}(X)$$ $$S_{\text{compressed}}(X)={\theta }^{m-1}{S}_0(X)+{\theta }^{m-2}{S}_1(X)+\cdots +\theta S_{m-2}(X)+S_{m-1}(X)$$

• 之后证明者对 $A_{\text{compressed}}(X)$ 和 $S_{\text{compressed}}(X)$ 依照 查找表证明 的规则进行排列，得到 $A^{\prime }(X)$ 和 $S^{\prime }(X)$.

证明者为所有的查找表创建盲化承诺：

$$\mathbf{L}=\left[(\text{Commit}(A^{\prime }(X))),\text{Commit}(S^{\prime }(X))),\dots \right]$$

并发送给验证者 。

当验证者接收到 $\mathbf{A}$ ， $\mathbf{F}$ ，和 $\mathbf{L}$ 后，随机采样 $\beta$ 和 $\gamma$ 作为挑战，用于后续的置换和查找表证明验证。（随机采样是可以重复利用的，因为证明是相互独立的）。

对相等约束置换进行承诺

令 $c$ 为 相等约束所涉及的列数。

令 $m$ 为能容纳的 最大列数 ， $m$ 不能超过 PLONK 配置中多项式的次数上限。

令 $u$ 为 置换证明 章节中定义的可以“使用”的行数。

令 $b=\mathsf{ceiling}(c/m).$

证明者构造一个长度为 $bu$ 的向量 $\mathbf{P}$ ，对于每个列集合，有， $0\le a<b$ ，对于每一行有 $0\le j<u$

$${\mathbf{P}}_{au+j}=\prod _{i=am}^{\min (c,(a+1)m)-1}\frac{v_i({\omega }^j)+\beta \cdot {\delta }^i\cdot {\omega }^j+\gamma }{v_i({\omega }^j)+\beta \cdot s_i({\omega }^j)+\gamma }.$$

证明者计算 $\mathbf{P}$ 的”滚动乘积“, 从 $1$ 开始，并且多项式向量 $Z_{P,\mathrm{0..}b-1}$ 每个都有拉格朗日基表示，基于滚动乘积的长度为 $u$ 的切片，如 置换证明 章节中所描述的。

最后 证明者为每个 $Z_{P,a}$ 多项式创建盲化承诺：

$${\mathbf{Z}}_{\mathbf{P}}=\left[\text{Commit}(Z_{P,0}(X)),\dots ,\text{Commit}(Z_{P,b-1}(X))\right]$$

并发送给 验证者 。

对查找表置换进行承诺

除了需要对单独的相等约束进行承诺外，对每一个查找表， 证明者也需要对置换进行承诺。

• 证明者构造一个向量 $P$:

$$P_j=\frac{(A_{\text{compressed}}({\omega }^j)+\beta )(S_{\text{compressed}}({\omega }^j)+\gamma )}{(A^{\prime }({\omega }^j)+\beta )(S^{\prime }({\omega }^j)+\gamma )}$$

• 证明者构造多项式 $Z_L$ ，其拉格朗日基表示为 $P$ 多项式的“滚动乘积”，从 $Z_L(1)=1$ 开始。

$\beta$ 和 $\gamma$ 用于在组合 $A^{\prime }(X)$ 和 $S^{\prime }(X)$ 的同时保持这两者无关。 $\beta$ 和 $\gamma$ 是验证者在证明者创建多项式 $\mathbf{A}$ ， $\mathbf{F}$ ，和 $\mathbf{L}$ 之后采样的（因此承诺了在 查找表列中用到的单元格的值，以及每个 查找表的 $A^{\prime }(X)$ 和 $S^{\prime }(X)$ ）。

如之前一样， 证明者对每个 $Z_L$ 多项式都创建一个盲化承诺并发送给 验证者 ：

$${\mathbf{Z}}_{\mathbf{L}}=\left[\text{Commit}(Z_L(X)),\dots \right]$$

消退证明

在电路的所有赋值都已经承诺之后，证明者现在需要证明各种各样的电路关系都是满足的：

• 自定义门，用多项式 ${\text{gate}}_i(X)$ 表示。
• 查找证明的约束
• 相等约束置换的约束

从电路的列的角度看，每个关系都由一个 $d$ 次多项式表示（在所有关系中最大的的次数。假设对应一列的赋值多项式的次数是 $n-1$，那么从$X$ 的角度看，关系多项式的次数就是 $d(n-1)$

在我们的例子中，门多项式的次数是 $3n-3$。

• ${\text{gate}}_0(X)=a_0(X)\cdot a_1(X)\cdot a_2(X{\omega }^{-1})-a_3(X)$
• ${\text{gate}}_1(X)=f_0(X{\omega }^{-1})\cdot a_2(X)$
• ${\text{gate}}_2(X)=f_0(X)\cdot a_3(X)\cdot a_0(X)$

如果描述关系的多项式为 $0$，我们就说关系是满足的。一种表示这种此种约束的方法，就是将每个多项式关系都除以消除多项式 $t(X)=(X^n-1)$，消除多项式是以 ${\omega }^i$ 作为根的最低次数的单项式。如果关系多项式能被 $t(X)$ 整除，那么在域上这个关系多项式就等于 $0$。

这种朴素的构造方式的弊端在于，其需要对每个关系都需要有一个多项式承诺。相反，我们可以对电路中所有关系同时进行承诺：验证者取一个 $y$，然后证明者构造一个商多项式，

$$h(X)=\frac{{\text{gate}}_0(X)+y\cdot {\text{gate}}_1(X)+\cdots +y^i\cdot {\text{gate}}_i(X)+\dots }{t(X)},$$

其中分子是电路关系的随机的线性组合（证明者需要在验证者给出 $y$ 之前先承诺单元格赋值）。

• 如果分子多项式（以 $X$ 为自变量）能够被 $t(X)$ 整除，那么所有的关系都满足的概率就是非常高的
• 相反地，哪怕只有一个关系是不满足的，那么在点 $x$ 处，$h(x)\cdot t(x)$ 与分子多项式在该处的值就几乎不可能相等。也就是说，在此种情况下，分子多项式不能整除 $t(X)$。

承诺 $h(X)$

$h(X)$ 的次数是 $(d-1)n-d$ （因为分母 $t(X)$ 的次数是 $n$）。但是我们在 Halo 2 中的多项式承诺机制仅仅支持次数 $n-1$ 次的多项式的承诺（这是因为除了关系多项式的承诺，协议其他部分所需承诺的多项式的最大次数就是 $n-1$）。为了不给多项式承诺机制增加额外的成本，验证者就需要把 $h(X)$ 分割成多个，每个只有 $n-1$ 次的多项式的和，

$$h_0(X)+X^n{h}_1(X)+\cdots +X^{n(d-1)}{h}_{d-1}(X),$$

并对每一部分产生一个具有隐藏承诺。

$$\mathbf{H}=[\text{Commit}(h_0(X)),\text{Commit}(h_1(X)),\dots ,\text{Commit}(h_{d-1}(X))].$$

多项式求值

到这一步，电路所有的特点都已经被承诺了。现在，验证者想要验证一下证明者提供的承诺是不是正确的 $h(X)$。于是，验证者选取一个 $x$，证明者需要提供其所声称的所有多项式在 $x$ 处的值，包括电路中使用的所有相对偏移和 $h(X)$的值。

在我们的例子中，这就是：

• $a_0(x)$
• $a_1(x)$
• $a_2(x)$, $a_2(x{\omega }^{-1})$
• $a_3(x)$
• $f_0(x)$, $f_0(x{\omega }^{-1})$
• $h_0(x)$, ..., $h_{d-1}(x)$

验证者现在要验证这些值是不是满足 $h(X)$ 的形式：

$$\frac{{\text{gate}}_0(x)+\cdots +y^i\cdot {\text{gate}}_i(x)+\dots }{t(x)}=h_0(x)+\cdots +x^{n(d-1)}{h}_{d-1}(x)$$

如果这些值确实满足的门约束，那么验证者接下来就需要验证这些值本身与最初的电路承诺以及承诺 $\mathbf{H}$ 是否一致。为了高效实现此一目的，我们使用了多点打开证明。

多点打开证明

假设 $A,B,C,D$ 分别是多项式 $a(X),b(X),c(X),d(X)$ 的多项式承诺值。比如说，我们要打开多项式 $a,b$ 在点$x$的取值，与此同时，打开$c,d$ 在两个点$x,\omega x$ 的取值。（此处的 $\omega$ 是乘法子群的本原单位根）。

比较容易想到的方法是，为每一个点构造一个多项式$Q$（每一个打开点就会对应电路中的一个相对转动（rotation））。但这不是一个有效的方法；比如，$c(X)$ 会出现在多个多项式中。

相反地，我们按打开点的集合，将多项式承诺值组织在一起： $$\begin{array}{ccccc}& \{x\}& & \{x,\omega x\}& \\ & A& & C& \\ & B& & D& \end{array}$$

对于每一个组，我们将这些多项式合并成一个多项式集合，然后构造一个多项式$Q$， 并在该点打开所有相对偏移。

优化步骤

多点打开的优化算法的输入为：

• 验证者采样出一个随机点$x$，我们将计算多项式$a(X),b(X),c(X),d(X)$在该点的值；
• 证明者计算出那些我们想要的多项式点值：$a(x),b(x),c(x),d(x),c(\omega x),d(\omega x)$。

这些数据是 vanishing证明 的输出。

多点打开优化算法的步骤如下：

1. 采样一个随机点$x_1$，用来让 $a,b,c,d$ 线性无关；

2. 对于每一个点集，将对应的多项式集合聚合成一个多项式，得到新的多项式集合 q_polys。

   $$\begin{array}{rcclc}{q}_1(X)& =& a(X)& +& x_{1}b(X)\\ q_2(X)& =& c(X)& +& x_{1}d(X)\end{array}$$ 同理对于每一个点集，也计算出新的多项式点值集合 q_eval_sets。

            [
                [a(x) + x_1 b(x)],
                [
                    c(x) + x_1 d(x),
                    c(\omega x) + x_1 d(\omega x)
                ]
            ]

3. 根据q_eval_sets，构造插值多项式集合 r_polys: $$\begin{array}{cccc}{r}_1(X)s.t.& & & \\ & r_1(x)& =& a(x)+x_{1}b(x)\\ r_2(X)s.t.& & & \\ & r_2(x)& =& c(x)+x_{1}d(x)\\ & r_2(\omega x)& =& c(\omega x)+x_{1}d(\omega x)\end{array}$$

4. 构造 f_polys 来检查 q_polys 的正确性：

   $$\begin{array}{rcl}{f}_1(X)& =& \frac{q_1(X)-r_1(X)}{X-x}\\ f_2(X)& =& \frac{q_2(X)-r_2(X)}{(X-x)(X-\omega x)}\end{array}$$

   如果 $q_1(x)=r_1(x)$，则 $f_1(X)$ 应当是一个多项式； 如果 $q_2(x)=r_2(x)$并且 $q_2(\omega x)=r_2(\omega x)$，则 $f_2(X)$ 应当是一个多项式。

5. 采样一个随机数 $x_2$，用来让 f_polys 线性无关。

6. 构造 $f(X)=f_1(X)+x_2{f}_2(X)$。

7. 采样一个随机数$x_3$，并计算$f(X)$在该点的取值： $$\begin{array}{rcccl}f(x_3)& =& f_1(x_3)& +& x_2{f}_2(x_3)\\ & =& \frac{q_1(x_3)-r_1(x_3)}{x_3-x}& +& x_2\frac{q_2(x_3)-r_2(x_3)}{(x_3-x)(x_3-\omega x)}\end{array}$$

8. 采样一个随机数$x_4$，用来让 $f(X)$ 和 q_polys 线性无关。

9. 构造 final_poly多项式 \textrm{final_poly}(X) = f(X) + x_4 q_1(X) +x_4^2 q_2(X) final_poly多项式就是传入内积证明的多项式。

内积证明

Halo2 使用的多项式承诺算法，其多项式承诺打开证明是基于内积证明的。

待办事项：解释 Halo2 所使用的IPA变体。

它非常类似于论文BCMS20附录A.2节的 ${\text{PC}}_{\text{DL}}.\text{Open}$。详细细节参见此处比较。

与其他工作的比较

BCMS20 附录 A.2

BCMS20 附录 A.2 提出了一种与 BGH19 中类似的多项式承诺机制（BCMS20 是对原始的 Halo 论文的推广）。 Halo 2 这些工作的基础上，因此其自身也就使用了一种与 BCMS20 中很类似的多项式承诺机制。

下表提供了一个BCMS20和Halo 2中具有相同含义的变量的对照表（Halo 2的术语是建立在Halo论文基础上的）：

Halo 2的多项式承诺机制与BCMS20附录A.2的机制有两点不同：

1. $\text{Open}$ 算法的第8步将在内积证明之前计算一个“非隐藏”的承诺 $C^{\prime }$。 该承诺与 $C$ 拥有相同的打开之，只不过它是仅是一个对一个随便写的多项式的承诺。 协议的剩余部分则是没有盲化的。与之相比，Halo 2中我们会盲化我们产生的所有的承诺（即便对于instance和fixed多项式也是如此， 尽管对fixed多项式的盲化因子是1），这使得协议更容易推理(???)。该方法的结果是，验证者在协议的最后要去 处理累计的盲化因子，所以在协议一开始就推导一个（与第一种方法）等价的 $C^{\prime }$ 就没有必要了。

   • $C^{\prime }$ is also an input to the random oracle for ${\xi }_0$; in Halo 2 we utilize a transcript that has already committed to the equivalent components of $C^{\prime }$ prior to sampling $z$.（？？？）

2. The ${\text{PC}}_{\text{DL}}.\text{SuccinctCheck}$ subroutine (Figure 2 of BCMS20) computes the initial group element $C_0$ by adding $[v]H^{\prime }=[vϵ]H$, which requires two scalar multiplications. Instead, we subtract $[v]G_0$ from the original commitment $P$, so that we're effectively opening the polynomial at the point to the value zero. The computation $[v]G_0$ is more efficient in the context of recursion because $G_0$ is a fixed base (so we can use lookup tables).

3. ${\text{PC}}_{\text{DL}}.\text{SuccinctCheck}$ 子程序 (BCMS20的图2所示) 会通过增加 $[v]H^{\prime }=[vϵ]H$ 来产生最开始的群元素 $C_0$，而这需要两次scalar乘。与之不同，我们的方法是用最初的承诺 $P$ 减去 $[v]G_0$，如此 我们就可以在0处很高效地打开多项式。而$[v]G_0$的计算在递归证明的情况下具有更高效率，这是因为 $G_0$ 是一个固定的基 （所以我们可以用查表(lookup tables)方法）。

Halo2 协议

预备工作

我们定义 $\lambda$ 作为一个安全参数，且除明确标注外，文档中所有的算法和敌手(adversaries)都是在该安全参数下运行时间为多项式的概率型图灵机。我们使用 $\text{negl}(\lambda )$ 表示一个在 $\lambda$ 下可忽略的函数。

密码学群

我们令 $\mathbb{G}$ 表示一个阶为素数 $p$ 的循环群，群的单位元记作 $\mathcal{O}$ 。将 $\mathbb{G}$ 中元素的标量表示为阶为 $p$ 的标量域 $\mathbb{F}$ 中的元素。群元素用大写字母表示，标量则用小写字母或希腊字母表示。群元素或标量所组成的向量用粗体字表示，例如 $\mathbf{a}\in {\mathbb{F}}^n$ 以及 $\mathbf{G}\in {\mathbb{G}}^n$ 。群上的运算记作加法，群元素 $G$ 和标量 $a$ 的乘法记作 $[a]G$ 。

我们会经常使用 $⟨\mathbf{a},\mathbf{b}⟩$ 表示长度相等的， ${\mathbb{F}}^n$ 上 $\mathbf{a},\mathbf{b}$ 两个向量的内积。同样地也用这种表示法描述群元素的一个线性组合 $⟨\mathbf{a},\mathbf{G}⟩$ ，其中 $\mathbf{a}\in {\mathbb{F}}^n,\mathbf{G}\in {\mathbb{G}}^n$ ，该内积的计算是通过群中的标量乘法和加法实现的。

我们使用 $0^n$ 描述域 $\mathbb{F}$ 中长度为 $n$ 的，只包含零元的向量。

离散对数关系问题 攻击者优势（advantage）的度量（metric）为： $${\mathsf{Adv}}_{\mathbb{G},n}^{\mathsf{dl}-\mathsf{rel}}(\mathcal{A},\lambda )=\text{Pr}\left[{\mathsf{G}}_{\mathbb{G},n}^{\mathsf{dl}-\mathsf{rel}}(\mathcal{A},\lambda )\right]$$ 其定义为赢得以下游戏的概率。 $$\begin{array}{ll}& \underline{\mathbf{Game}{\mathsf{G}}_{\mathbb{G},n}^{\mathsf{dl}-\mathsf{rel}}(\mathcal{A},\lambda ):}\\ & \mathbf{G}\leftarrow {\mathbb{G}}_{\lambda }^n\\ & \mathbf{a}\leftarrow \mathcal{A}(\mathbf{G})\\ & \text{Return}\left(⟨\mathbf{a},\mathbf{G}⟩=\mathcal{O}\wedge \mathbf{a}\ne 0^n\right)\end{array}$$ 即：如果攻击者能够给出一个 $\mathbf{a}$ 使得 $⟨\mathbf{a},\mathbf{G}⟩=\mathcal{O}\wedge \mathbf{a}\ne 0^n$ ，则它赢得这次游戏

给定一个长度为 $n$ 的向量 $\mathbf{G}\in {\mathbb{G}}^n$ ， 离散对数关系问题 指寻找一个 $\mathbf{g}\in {\mathbb{F}}^n$ 使得 $\mathbf{g}\ne 0^n$ 且 $⟨\mathbf{g},\mathbf{G}⟩=\mathcal{O}$ （我们称为 非平凡 离散对数关系）。该问题的难度和群中的离散对数问题紧密相连（[JT20] 引理3）。我们使用上面定义的游戏 ${\mathsf{G}}_{\mathbb{G},n}^{\mathsf{dl}-\mathsf{rel}}$ 描述该问题。

交互式证明

交互式证明是一个算法三元组 $\text{IP}=(\text{Setup},\mathcal{P},\mathcal{V})$ 。 $\text{Setup}(1^{\lambda })$ 算法用于生成某些被 $\mathsf{pp}$ 引用的 公开参数 。证明者 $\mathcal{P}$ 和验证者 $\mathcal{V}$ 是能够访问 $\mathsf{pp}$ 的交互式机器，我们用 $⟨\mathcal{P}(x),\mathcal{V}(y)⟩$ 表示在 $\mathcal{P}$ 和 $\mathcal{V}$ 之间执行的两方协议，其输入为 $x$ 和 $y$ 。协议的输出是一个 transcript ，包含了所有 $\mathcal{P}$ 和 $\mathcal{V}$ 之间交互的消息。在协议的最后，验证者输出一个决策位，表示它是否接受证明者的证明。

关于知识的零知识证明

知识证明是一种交互式证明，指证明者试图向验证者证明它知道一个 witness $w$ 使得 $(x,w)\in \mathcal{R}$ ，其中 $x$ 为一个 statement ， $\mathcal{R}$ 为多项式时间内可决定的 relation。我们假设证明者的计算能力是有限的，在这个假设下研究知识证明。

我们将从四个角度分析知识证明的安全程度：

• 完备性: 如果证明者有一个有效的 witness ，它是否 总是 能够向验证者证明这一点？完备性做出了一些假设，理解完备性将有助于理解其他的安全性
• 可靠性: 一个试图作弊的证明者能否向验证者成功证明一个错误的 statement ? 我们将发生这种情况的可能性称为 可靠性错误 。
• 知识可靠性: 当验证者确信 statement 是正确的时候，证明者是否实际拥有（“知道”）一个有效的 witness ？我们将验证者确信，但证明者并不拥有有效 witness 的可能性称为 知识错误 。
• 零知识性: 除了 statement 的正确性和证明者实际拥有该有效 witness 之外，验证者是否还获得了额外的知识？

首先，我们考察完备性的一个简单定义：

完美完备性： 一个交互式证明 $(\text{Setup},\mathcal{P},\mathcal{V})$ 是 完美完备的 当对于所有的多项式时间内可决定的关系 $\mathcal{R}$ 和所有非均匀的多项式时间攻击者 $\mathcal{A}$ 都有 $$Pr\left[(x,w)\notin \mathcal{R}\vee ⟨\mathcal{P}(\mathsf{pp},x,w),\mathcal{V}(\mathsf{pp},x)⟩\text{accepts}|\begin{array}{ll}& \mathsf{pp}\leftarrow \text{Setup}(1^{\lambda })\\ & (x,w)\leftarrow \mathcal{A}(\mathsf{pp})\end{array}\right]=1$$

可靠性

我们分析过程的复杂性在于：我们的协议被描述为交互式证明，但实际上通过 Fiat-Shamir 变换，它被实现为 非交互式 的。

Public coin： 我们将那种验证者发送的每个消息都来自新的随机性采样的交互式证明称为 public coin 式。

Fiat-Shamir 变换： 将验证者发送的消息替换为密码学上健壮的哈希函数以产生足够的随机性，即可将交互的 public coin 式证明在 随机预言机模型 中转换为 非交互式 的。

这种形式变换意味着在实际的协议中，一个试图作弊的证明者可以通过对 transcript 进行分叉，修改某个时刻自己应该发送给验证者的消息，从而轻易的达成状态“回卷”。因此，研究我们的协议在 Fiat-Shamir 变换之后的安全性是非常重要的。幸运的是我们可以依照 Ghoshal 和 Tessaro 提出的框架 ([GT20]) 来进行分析。

我们通过 状态恢复可靠性 的概念分析我们的协议。在该模型中，（作弊的）证明者可以“回卷”验证者至之前任意的状态。如果证明者能通过这种方式使验证者接受证明，则是对我们协议一次成功的攻击。

状态恢复可靠性： 令 $\text{IP}$ 是一个交互式的 argument ，包含有 $r>=r(\lambda )$ 个验证者挑战。令第 $i$th 个挑战是从 ${\mathsf{Ch}}_i$ 中采样获得，则一个具备状态恢复能力的证明者 $\mathcal{P}$ 的优势度量（advantage metric）为 $${\mathsf{Adv}}_{\text{IP}}^{\text{SRS}}(\mathcal{P},\lambda )=\text{Pr}\left[{\text{SRS}}_{\mathcal{P}}^{\text{IP}}(\lambda )\right]$$ 通过以下攻防游戏定义： $$\begin{array}{ll}\begin{array}{ll}& \underline{\mathbf{Game}{\text{SRS}}_{\text{IP}}^{\mathcal{P}}(\lambda ):}\\ & \text{win}\leftarrow \mathtt{false};\\ & \text{tr}\leftarrow ϵ\\ & \mathsf{pp}\leftarrow \text{IP}.\text{Setup}(1^{\lambda })\\ & (x,{\text{st}}_{\mathcal{P}})\leftarrow {\mathcal{P}}_{\lambda }(\mathsf{pp})\\ & \text{Run}{\mathcal{P}}_{\lambda }^{{\mathcal{O}}_{\text{SRS}}}({\text{st}}_{\mathcal{P}})\\ & \text{Return win}\end{array}& \begin{array}{ll}& \underline{\mathbf{Oracle}{\mathcal{O}}_{\text{SRS}}(\tau =(a_1,c_1,...,a_{i-1},c_{i-1}),a_i):}\\ & \text{If}\tau \in \text{tr}\text{then}\\ & \text{If}i\le r\text{then}\\ & c_i\leftarrow {\mathsf{Ch}}_i;\text{tr}\leftarrow \text{tr}||(\tau ,a_i,c_i);\text{Return}{c}_i\\ & \text{Else if}i=r+1\text{then}\\ & d\leftarrow \text{IP}.\mathcal{V}(\mathsf{pp},x,(\tau ,a_i));\text{tr}\leftarrow (\tau ,a_i)\\ & \text{If}d=1\text{then win}\leftarrow \mathtt{true}\\ & \text{Return}d\\ & \text{Return}\perp \end{array}\end{array}$$