UltraGroth 原理分析

UltraGroth 协议详解

引言

查找检查 (Lookup checks) 是一种令人惊叹且优雅的技术，可以减少算术电路的约束数量。 实际上，当通过特定的零知识协议实现算术电路时，通常需要实现非原生操作，例如位移、异或 (XORing) 或范围检查。 当在 BN254 域上实现此类操作时，这些操作通常会花费很多：例如，任何

ℓ 位操作至少需要

ℓ 个约束，至少要计算整数的位分解。

为了解决这个问题，plookup 提出了一种有效的方法，将查找优化集成到基于 PlonK 的证明系统中。通过查找，许多此类非原生操作需要明显更少的约束（例如，对小尺寸的 limbs 进行范围检查本质上只需单个约束）。不久之后，另一个称为 logup 的协议以 sumcheck 的方式启用了查找检查，这证明更有效。

虽然 PlonK 和基于 sumcheck 的协议越来越受到关注，特别是因为原生有效查找支持，但 Groth16 由于其非交互性质，无法享受相同的优化。 事实上，正如我们将看到的，查找检查需要采样随机标量，以在随机点进行某些检查，但直到今天，这在 Groth16 中实际上是不可行的。

这非常不幸！ Groth16 虽然已经有近 10 年的历史，但仍然可以说是零知识领域中验证器效率最高的协议（可能除了比特币上一些最近开发的奇异 SNARK）。它的证明是恒定的——仅仅是椭圆曲线上的 3 个点（

2G1+G2），并且它的验证仅包括计算 3 个配对操作。由于这种效率，它目前被用作以太坊中的主要 ZK 验证机制（特别是，ecPairing 被实现为预编译合约）。因此，如果 Groth16 也具有查找检查来加速非原生操作，那岂不是很好吗？

概要 (tl;dr)

UltraGroth 旨在对 Groth16 协议进行微不足道的修改，以有效地采样随机域元素，并进一步将它们作为信号传递给电路。 这种可能性的主要含义当然是查找检查！

此外，这种修改保留了 Groth16 的所有验证优势：在 UltraGroth 的基本形式中，它仅添加一个

G1 点到证明中，每个随机性只需进行一次配对操作和一次哈希操作。

UltraGroth 已经使用的一个例子是 Bionetta–一个基于 R1CS 的 zkML 框架，由 Rarimo 使用。当在电路中实现

ReLU(x)=max{0,x} 非线性时，在普通的 Groth16 中，需要对

x 执行完整的位分解，因此每次调用花费

≈254 个约束。因此，神经网络的电路大小大约为

O(n)，其中

n=254L，其中

L 是 ReLU 调用的次数。 使用 UltraGroth，我们将约束的数量减少到亚线性复杂度：

O(n/log⁡n)。 你可以在我们的 UltraGroth+Bionetta 博客中查看一些详细信息。

历史记录

在深入研究细节之前，我们简要地提及一下该协议的历史，这非常有趣。 本博客基于 2023 年 Lev Soukhanov 的原始 帖子。 但是，当我们准备 Bionetta 的会议论文时，我们发现他的构造只不过是

MIRAGE 协议 的概括，该协议早在 2020 年就发布了！ （在随后的符号中，MIRAGE 是一个 UltraGroth 协议，其中

d=1）。更令人惊讶的是，似乎独立于 Lev Soukhanov 的构造，Alex Ozdemir、Evan Laufer 和 Dan Boneh 在 2024 年推出了 MIRAGE+ 协议，该协议用于证明 RAM 计算的正确性。 这项协议令人难以置信，但也与 Lev Soukharnov 的构造相吻合（尽管我相信前者更严格地概括了该构造）。 也就是说，据我所知，Lev Soukhanov 的构造是第一个将 MIRAGE 推广到多轮交互协议的构造。

所有三篇论文（包括 Bionetta）都证明了该构造的完整性、可靠性和零知识性，因此可以安全地将以下协议集成到生产系统中。 当然，我们将在本博客中省略一些形式，并建议查看

MIRAGE+ 协议 论文以获取证明细节，以防有人感兴趣。

最后，我个人的观点是，这种构造被大大低估了，并且令人惊讶的是它尚未在生产中使用。 实际上，集成查找检查仅需付出额外的配对成本，这使得在 Groth16 中包装非原生协议（例如，zk-STARK）更加有效（高达

×20 倍）。

警告

后续的解释将非常技术性，因此，如果你想要更简单、更直接的概述，还可以查看我们的简短的内部分布式实验室演示文稿。

查找检查

在此，我们重述最初在 logup 中提出的一些关键结果。

假设查找表由

{ti}i∈[v] 给出，而要进行查找检查的 witness 部分是

{zi}i∈[n]：也就是说，我们证明包含关系

{zi}i∈[n]⊆{ti}i∈[v]。 例如，设置

ti:=i 对于

v=2w 检查每个

zi 是否为

w 位整数。 执行此类包含检查的一种方法如下。

定理。 给定两个元素序列

{ti}i∈[v] 和

{zi}i∈[n]，如果且仅当存在多重性集合

{μi}i∈[v] 时，包含检查

{zi}i∈[n]⊆{ti}i∈[v] 以极高的概率满足，其中

μi=#{j∈[n]:zj=ti} 使得对于随机采样的

γ←RF:

∑i∈[n]1γ+zi=∑i∈[v]μiγ+ti

更具体地说，在

F 中的随机点检查这种相等性会导致最多

(n+v)/|F| 的可靠性误差，对于大的

|F| 来说，这变得可以忽略不计。

现在，等式的右侧，假设我们已经采样了

随机数

γ←F，可以在

v 个约束中计算，而

左侧在额外的

n 个约束中计算（回想一下，反转花费单个约束来证明）。 同样，由于 Groth16 本质上是一个非交互协议（这意味着，与基于 PlonK 或 sumcheck 的协议相比，它不是通过将交互协议转换为非交互协议来构建的），因此目前还没有有效的方法来采样

γ（除了可能成本高昂的电路内哈希）。 然而，我们确实提出了一种通过将 Groth16 变成“类交互”证明系统来采样

γ 的方法。

下面的 UltraGroth 构造本质上致力于采样

γ 并将其作为信号可靠地传递到电路。

其他一些含义

总的来说，采样随机数除了查找检查之外，还可以实现许多应用。 例如，假设你有矩阵

A,B∈Fn×n，并且你想编写一个计算其乘积的电路：

C=AB。 一种简单的方法是按定义来计算它。 但是，这样的电路花费

O(n3) 个约束，这很多。 事实证明，采样随机数可以大大减少这一点。 实际上，可以应用 Freiveld 协议：首先采样

γ←RFn，而不是检查

AB=C，检查矩阵

AB 和

C 是否将

γ 投影到同一向量（这看起来有点类似于 Schwartz-Zippel 引理，但在矩阵世界中）：

(AB)γ=Cγ⟺A(Bγ)=Cγ

现在请注意，这可以在大约

3n2 个约束中实现：首先乘以

u←Bγ，然后乘以

Au 并将其与乘积

Cγ 进行比较。 请注意，矩阵向量乘积可以在

n2 个约束中实现，这比具有

n3 个约束的矩阵矩阵乘积有效得多。

但是，目前，在 Circom 中无法将

γ 作为信号传递到电路。 实际上，可以编写 signal input gamma[n] 并将其标记为公共信号，但是如何确保验证者 witness 中的相应值确实由证明者均匀地随机采样？ 因此，让我们看看如何解决它。

UltraGroth

Groth16 回顾

我们首先提醒读者 Groth16 的构造。 如果你对 Groth16 的知识感到满意，请随时跳过此部分。

R1CS 算术化

我们从 R1CS 开始。 回想一下，R1CS 以以下形式编码程序：

Lz⊙Rz=Oz,

其中

L,R,O∈Fm×n 是常数矩阵，

z∈Fn 是编码所有中间计算的解 witness，

m 是约束的数量，并且

n 是 witness 的大小。 R1CS 极其有用的一个属性是，信号的任何线性组合都需要 0 个约束才能实现，这在许多其他算术化系统中不存在，例如 PlonK。

二次算术程序 (QAP)

由于零知识协议通常在多项式上运行，因此我们以多项式形式编码 R1CS。 我们构建多项式

{ℓi(X)}i∈[n],{ri(X)}i∈[n],{oi(X)}i∈[n]⊆F≤m[X]，它们插值对应矩阵

L,R,O 的列。 也就是说，

ℓi(ωj)=Li,j,ri(ωj)=Ri,j,oi(ωj)=Oi,j,i∈[n],j∈[m]

现在，R1CS 检查表示为多项式恒等式：

∑i∈[n]ziℓi(X)⋅∑i∈[n]ziri(X)=∑i∈[n]zioi(X)+tΩ(X)h(X),

其中

h(X) 是由证明者计算的多项式，而

tΩ(X):=∏h∈Ω(X−h) 是

Ω={ωj}j∈[m] 的消失多项式。 我们正式定义 QAP 关系如下：

RQAP={x={zi}i∈IXw={zi}i∈IW|∑i∈[n]ziℓi(X)⋅∑i∈[n]ziri(X)=∑i∈[n]zioi(X)+tΩ(X)h(X)forsomeh(X)∈F[X]}

这里，

IX⊆[n] 是公共输入的索引集，而

IW:=[n]∖IX 编码私有输入。 为了具体起见，假设我们有

l:=|IX| 个公共输入，因此

n−l=|IW| 个私有信号。

Groth16 构造

此外，我们以乘法形式编写群运算。 Groth16 系统在双线性群

G=(G1,G2,GT,e) 上运行，该双线性群具有非退化的、可有效计算的配对运算

e:G1×G2→GT，该配对运算满足双线性性质，这在历史上使得构造大量 zk-SNARK 成为可能：

e(g1α,g2β)=e(g1αβ,g2)=e(g1,g2αβ)=e(g1,g2)αβ。 令

g1,g2,gT 是对应群的生成元。 现在我们指定证明构造。

Setup(1λ,RQAP)。 用

fi(X):=βℓi(X)+αri(X)+oi(X) 表示

ℓi,ri,oi 的随机线性组合。 在可信设置期间，生成有毒废料

α,β,γ,δ,τ←RF 并计算以下公共参数：

pp←(g1α,g1β,g1δ,g2β,g2γ,g2δ,{g1τi,g2τi,g1τit(τ)/δ}i∈[n],{g1fi(τ)/γ}i∈IX,{g1fi(τ)/δ}i∈IW)

vp←(g1,g2,g2γ,g2δ,gTαβ,{g1fi(τ)/γ}i∈IX)

Prove(pp,x,w)。 证明者采样随机标量

r,s←RF 并输出证明

π←(g1a(τ),g1c(τ),g2b(τ))，其中：

a(X)=α+∑i∈[n]ziℓi(X)+rδ,b(X)=β+∑i∈[n]ziri(X)+sδ,

c(X)=δ−1(∑i∈IWzifi(X)+h(X)tΩ(X))+a(X)s+b(X)r−rsδ

Verify(vp,x,π)。 收到

π 后，验证者将证明解析为

(πA,πC,πB)，并且当且仅当以下检查成立时才接受证明：

e(πA,πB)=e(g1α,g2β)⋅e(g1i(τ),g2γ)⋅e(πC,g2δ),

其中

i(X):=γ−1∑i∈IXzifi(X)。

效率

按照 Groth16 原始论文的表示法，假设

G1 和

G2 指数运算的成本分别为

E1 和

E2。 假设配对操作的成本为

E。 然后，证明者的工作是

O(n⋅E1+n⋅E2) 个操作，而验证是

3E+O(l⋅E1)。

两轮交互式 R1CS

最后，这是我们最终引入新构造的部分。 假设我们将 R1CS 分成多轮。 考虑我们要实现查找检查的情况。 在这种情况下，如果我们可以将以下交互协议 (IP) 编译到关系

RQAP 的 zk-SNARK 中，那将是很好：

• 第 0 轮：证明者运行电路而不施加查找检查。 证明者将结果的 witness

w0 发送给验证者。 验证者以随机挑战回应

x1←RF。

• 第 1 轮：证明者计算对应于查找检查的 witness

w1（也就是说，验证等式

∑i1x1+zi=∑iμix1+ti），使用验证者提供的随机性

x1。 证明者根据

RQAP 发送

w1 和多项式

h(X)。

• 最后，验证者检查相同的 QAP 方程

ℓ(X)r(X)=o(X)+tΩ(X)h(X)。

我们想通过应用 Fiat-Shamir 启发式方法将这种 IP 编译到 zk-SNARK 中。 但是，这里存在一个问题：

x1 必须通过哈希先前的 transcript 来获得，该 transcript 是公共语句

x0 和 witness

w0。 但是，鉴于整个 Groth16 证明系统仅将验证方程编译为三个点，我们如何哈希 witness

w0？

现在，假设我们将公共信号

IX 的索引集划分为两个部分（对应于每一轮）：

IX⟨0⟩ 和

IX⟨1⟩。 相应的私有信号由

IW⟨0⟩ 和

IW⟨1⟩ 索引，它们划分

IW。 在上面的示例中，

IX⟨0⟩ 对应于关系

RQAP 中的常规公共信号，而

IX⟨1⟩ 索引单个解 witness 元素，该元素对应于采样的随机数

x1。

想法如下：我们将多项式

c(X)（如上面的 Groth16 构造中所述）分成两部分

c0(X) 和

c1(X)。 第一部分对应于由

(IX⟨0⟩,IW⟨0⟩) 索引的第一轮，其形成方式如下：采样

r0←RF，添加有毒参数

δ0，并计算点

πC⟨0⟩←g1c0(τ)，其中：

c0(X)=δ0−1∑j∈IW⟨0⟩zjfj(X)+r0δ

请注意，点

πC⟨0⟩ 编码第 0 轮中的所有 witness 元素。 因此，为了采样随机数，我们可以哈希证明者参数和该点：

x1←H(pp,πC⟨0⟩)。 然后，点

πA=g1a(τ) 和

πB=g1b(τ) 的计算方式与常规 Groth16 中的方式相同，而第三部分

πC⟨1⟩=g1c1(τ) 的计算方式如下：

c1(X)=δ−1(∑j∈IW⟨1⟩zjfj(X)+h(X)tΩ(X))+a(X)s+b(X)r−r0δ0−rsδ

从本质上讲，这种构造确保

δ0c0(X)+δc1(X) 给出的正是原始 Groth16 中的多项式

δc(X)。 这允许证明者构造一个元组

π=(πA,πB,πC⟨0⟩,πC⟨1⟩) 的证明，并且验证者使用以下方式检查该证明：

e(πA,πB)=e(g1α,g2β)⋅e(g1i(τ),g2γ)⋅e(πC⟨0⟩,g2δ0)⋅e(πC⟨1⟩,g2δ),

其中

i(X)=γ−1∑i∈IXzifi(X) 与以前相同。 与 Groth16 中一样，可以预先计算项

e(g1α,g2β)，因此验证的成本为 4 个配对操作。

注意

如前所述，上述协议本质上是

MIRAGE 协议，并且可以按原样实现。 它是完整的、可靠的并且是零知识的。 在后续章节中，我们将把该协议推广到 1 轮以上。

推广到多轮

为了推广上述协议，我们将

(d+1) 轮二次算术程序（或简称

dQAP）定义如下：

RdQAP={xi={zj}j∈IX⟨i⟩wi={zj}j∈IW⟨i⟩for i∈[d+1]|∑i∈[n]ziℓi(X)⋅∑i∈[n]ziri(X)=∑i∈[n]zioi(X)+tΩ(X)h(X)forsomeh(X)∈F[X]},

其中索引

{IX⟨i⟩}i∈[d+1] 和

{IW⟨i⟩}i∈[d+1] 划分

[n]。 在此表示法中，所有

{wi}i∈[d+1] 称为私有 witness，

x0 是公共语句，而

{xi}i∈[d+1]∖{0} 是挑战（将通过 UltraGroth 对其进行采样）。

由于证明者和验证者参与交互协议，因此证明者无法在没有验证者随机性的情况下自行计算整个 witness。 因此，我们将策略定义为函数的集合

S={Si}i∈[d]，每个函数都根据先前的 witness 和挑战以及验证者采样的当前挑战来计算给定轮的 witness。 换句话说，

wi=Si(x0,…,xi,w0,…,wi−1)

注意

例如，0QAP 表示常规的 Groth16 构造，其中策略

S0 是常规的 witness 计算器：

w0=S0(x0)。 涉及查找检查的协议是 1QAP 上的 SNARK，其中

S0 计算没有查找约束的 R1CS witness，而

S1 基于采样的随机数

x1，施加查找检查条件：

w1=S1(x0,x1,w0)。

现在，我们可以描述

RdQAP 上的 UltraGroth 协议。

Setup(1λ,RdQAP)。 与前面的章节一样，用

fi(X):=βℓi(X)+αri(X)+oi(X) 表示

ℓi,ri,oi 的随机线性组合。 在可信设置期间，生成有毒废料

α,β,γ,{δi}i∈[d+1],τ←RF 并计算以下公共参数：

pp=(g1α,g1β,{g1δi}i∈[d],g2β,g2γ,{g2δi}i∈[d],{g1τi,g2τi,g1τit(τ)/δd}i∈[n],{g1fi(τ)/γ}i∈IX,{g1fj(τ)/δi}(i,j)∈[d]×IW(i))

vp=(g1,g2,g2γ,{g2δi}i∈[d],gTαβ,{g1fi(τ)/γ}i∈IX)

Prove(pp,x0,S)。 证明者初始化累加器

a0:=H(pp)。 对于每一轮

i∈[d]，她进行以下步骤：

• 抽样

ri←RF

• 计算 witness

wi←Si(x0,…,xi,w0,…,wi−1)。

• 计算

πC⟨i⟩←g1ci(τ)，其中

ci(X):=δi−1∑j∈IW⟨i⟩zjfj(X)+riδd。

• 将累加器更新为

ai+1←H(ai,πC⟨i⟩)。

• 如果

i<d，对于每个

j∈IX⟨i+1⟩ 设置

zj←H(ai+1,g1j)。

完成

d 轮后，证明者执行以下操作：

• 从 QAP 中计算多项式

h(X)，与 Groth16 中相同。

• 采样随机的

r,s←F 并计算

πA←g1a(τ),

πB←g2b(τ) 和最后一块证明

πC⟨d⟩←gcd(τ)，其中

a(X),

b(X) 和

c(X) 定义如下：

a(X)=α+∑i∈[n]ziℓi(X)+rδd,b(X)=β+∑i∈[n]ziri(X)+sδd

cd(X)=δd−1(∑i∈IW⟨d⟩zifi(X)+h(X)tΩ(X))+a(X)s+b(X)r−∑i∈[d]riδi−rsδd

• 输出 证明

π=(πA,πB,πC⟨0⟩,…,πC⟨d⟩)∈G1×G2×G1d+1。

Verify(vp,x0,π)。 验证者重新计算所有挑战

{xi}i∈[d+1]∖{0} 并验证相应的公共信号是否正确。 然后，她检查：

e(πA,πB)=e(g1α,g2β)⋅e(g1i(τ),g2γ)⋅∏i∈[d+1]e(πC⟨i⟩,g2δi)

效率分析

最后，我们指定 UltraGroth 的效率。

• 证明者的工作本质上与 Groth16 中的工作相同：如果 witness 的总大小为

n，则证明者需要进行

O(n⋅E1+n⋅E2) 个操作，并进行一些额外的哈希运算（正式地，

∑i∈[d+1]∖{0}|xi| 个哈希运算，这在实践中可以忽略不计）。 但是请注意，由于这种 R1CS 拆分，电路的尺寸

n 大大减小：在许多情况下，它变为原始尺寸的亚线性。

• 验证者的工作是

(d+3)E+O(l⋅E1)。

• 证明大小为

1G2 点和

(d+2)G1 点。

实践实现和后续步骤

目前，我们已经在 Bionetta 项目中实现了 UltraGroth，用于

d=1，存储库如下：https://github.com/rarimo/ultragroth。 此外，我们还有一个自定义的 SnarkJS 分支，该分支实现了智能合约生成以及 witness 验证和导出操作。 但是，当前的实现非常不灵活，并且目前主要与 Bionetta 的 witness 生成器 结合使用。 该实现采用常规的 Circom 生成的 .wtns 和 .sym 文件，对其进行解析，找出哪个 witness 元素对应于随机数，并在证明过程中使用以上协议填充该点。

我们期待完成可以轻松集成到他人项目中的实现。 一种不错的实现方法是在 Circom 编译器中添加一个特殊的关键字。 例如，如果我们能编写 random signal r[N] 来用随机值填充向量 r，那就太好了，尽管这样的任务无疑具有挑战性。

致谢

当然，没有 Lev Soukhanov，这篇文章就不会存在。 我还要感谢 Artem Sdobnov、Vitalii Volovyk、Yevhenii Sekhin 和 Illia Dovgopoly 为 Bionetta 提供的 UltraGroth 实现。

总结

如果你实现涉及非原生操作的复杂电路（例如，包装某些 ZK 协议的验证），那么绝对值得研究一下 UltraGroth 协议。 通过微小的验证开销，可以极大地提高证明过程。 特别是，它使客户端 ZK 变得更加实用和现实，而又不会牺牲验证效率。

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