UltraGroth：一种改进的Groth16零知识证明系统

类 Groth16 系统中的挑战轮

这是我之前帖子的延续和澄清，其中非常粗略地描述了一种将查找（以及任何其他挑战参数）添加到 Groth16 的可能方案。

它产生了一些吸引力和评论。我主要想感谢陈伟康，他给了我一些关于类似方法（基于 LegoSNARK）的参考资料，并确认应该可以消除不同参数系统之间的所有接口（大致类似于 Pinoccio 的工作方式），而是使用一个单一的 Groth16 风格的方程式。

看来这确实是可能的。我在这里描述了协议，并提供了一个证明草图。

让我们首先回顾一下正常的 Groth16 协议

说实话，这变得相当长。可以跳过，但在这里查看零知识/可靠性证明以理解我对 UltraGroth 的论证是有意义的。

R1CS 在正常的 Groth16 中，我们从 rank 1 约束系统 R1CS 开始：

Lw∘Rw=Ow

这里，

L,R,O 是大小为

m×n 的矩阵，其中

m 是见证向量的大小

wi, 以及

n 是约束的数量，并且

∘ 是 Hadamard 乘积。

因此，单个约束对应于矩阵的行：

Liw∗Riw=Oiw

(∑jLjiwj)∗(∑jRjiwj)=∑jOjiwj

见证的某些索引子集也被称为“公共输入”，并将由证明公开，所有其他索引都是私有的。

现在，我们将约束集映射到 pairing-friendly 曲线标量字段中的某个集合

S 中 - 我将表示

xi 对应于约束的点

i。

Z(x)=∏i(x−xi) 表示这个集合的 vanishing polynomial，我们还通过它们在集合上的值的 Lagrange 插值来定义

Lj(x),Rj(x),Oj(x)：

Lj(xi)=Lji（对于

R,O 相同)。

然后，R1CS 问题可以重新表述为找到这样的见证向量

wj，使得

(∑jwjLj(x))(∑jRj(x))−(∑jOj(x)) 在

S 上消失，<=> 可被

Z(x) 整除，<=> 存在这样的

H(x)（度数最多为

n）使得：

L(x)R(x)−O(x)=Z(x)H(x)

其中

L=∑jwjLj(x)

R=∑jwjRj(x)

O=∑jwjOj(x)

Groth16 参数

现在，让我们回忆一下如何将这个问题转化为 zk-proof。

我们有以下 toxic waste 元素：

(α,β,γ,δ,τ)，并且引用字符串计算如下：

[α]1,[β]1,[β]2,[γ]2,[δ]1,[δ]2,

对于

0≤k≤n:

Zk=[τkZ(τ)δ]1 <– 这些将允许我们计算

[H(τ)Z(τ)δ]1

Aj=[Lj(τ)]1,Bj=[Rj(τ)]2,

Bj′=[Rj(τ)]1

对于

j∈priv:

Cj=[Oj(τ)+βLj(τ)+αRj(τ)δ]1

对于

j∈pub:

Cj=[Oj(τ)+βLj(τ)+αRj(τ)γ]1

[…]

Groth16 证明者（给定上述多项式形式的 R1CS 的解）创建两个随机盲化标量

r,s 并计算以下内容：

A=[α]1+∑jwjAj+r[δ]1

B=[β]2+∑jwjBj+s[δ]2,

B′=[β]1+∑jwjBj′+s[δ]1

C=∑j∈privwjCj+∑hkZk+rB′+sA−rs[δ]1

并且

IC 由双方从公共输入计算得出：

IC=∑j∈pubwjCj

验证者执行以下检查：

⟨A,B⟩=⟨[α]1,[β]2⟩+⟨C,[δ]2⟩+⟨IC,[γ]2⟩

为什么这对于有效的 R1CS 实例成立

让我们看看为什么这有效：

首先，展开此检查以查看其是否通过。我将计算 LHS 和 RHS（并稍微滥用符号，省略将其强制转换为乘法组

[]m）。我还将使用“A, B, C”作为其 dlog 作为标量的简写。

LHS：

AB=(α+∑jwjLj(τ)+rδ)(β+∑jwjRj(τ)+sδ)

RHS：

αβ+Cδ+ICγ=αβ+∑jwj(Oj(τ)+βLj(τ)+αRj(τ))+H(τ)Z(τ)+rδB+sδA−rsδ2

现在，对 LHS 进行小的修改可以清楚地看到所有带有

δ 的项都将被抵消：

LHS：

AB=sAδ+rBδ−rsδ2+(α+∑jwjLj(τ))(β+∑jwjRj(τ)).

其余的是直接检查。

零知识

现在，让我们回顾一下为什么这是完全零知识的，以及为什么这在代数群模型中是计算上可靠的。

零知识： 显然，

A,B 是均匀分布的（因为证明者加起来随机均匀分布的元素

r[δ]1,s[δ]2)。

如果其他变量固定，则

C 是唯一确定的（因为这是一个线性方程），因此，此方程的解空间上的证明概率分布是均匀随机的。

注意： 甚至存在更强的引人入胜的属性，即重新随机化。这意味着拥有正确的证明三元组 (A, B, C) 可以在所有证明的空间中构造一个新的均匀随机分布的证明 (A', B', C')，而无需知道原始的见证。可悲的是，此属性将在我扩展的 UltraGroth 协议中被破坏。

代数群模型中的可靠性

AGM 中的可靠性： 我不会详细介绍 AGM，但这具有以下直觉：假设

α,β,γ,δ,τ 是变量（即，我们现在根据这些变量在有理函数环中计算）。然后，对手尝试构造一个证明，其中

A 和

C 是表达式

α,β,δ,τkZ(τ)δ,Lj(τ),Rj(τ) 的线性组合，对于

j∈priv:

Oj(τ)+βLj(τ)+αRj(τ)δ, 对于

j∈pub:

Oj(τ)+αRj(τ)+βLj(τ)γ

并且

B 是

β,δ,γ,Rj(τ) 的线性组合

让我们假设他们成功了，即表达式满足

AB=αβ+Cδ+ICγ

首先，让我们注意到

A 必须包含

α 并且

B 必须包含

β。此外，让我们在不失一般性的前提下以这样一种方式重新调整它们，使两者都具有系数

1。

然后禁止

β 出现在

A 中，因为

β2 不能出现在 RHS 上。

现在，让我们看看

A 中不应有分母中带有

δ 或

γ 的项。事实上，如果存在，它们与

β 的乘积将不会被 LHS 中的任何内容取消，也不会被 RHS 中的任何内容取消（因为 RHS 在

δ=0 处没有极点）。

我们还注意到，

γ 出现在

B 中是不受欢迎的，因为

γα 不能出现在 RHS 中。

因此，我们处于以下情况：

A=α+∑ajLj(τ)+∑qjRj(τ)+rδ 并且

B=β+∑bjRj(τ)+sδ。我们既没有证明

aj≠bj，也没有证明

qj=0，也没有说明关于

C 的任何内容。

WLOG，让我们通过删除

rδ 和

sδ 来修改

A 和

B，并通过减去

sA、

rB 并添加

rsδ 来修改

C。我们已成功地将

δ 从 LHS 中排除，现在它具有以下形式：

A=α+∑ajLj(τ)

B=β+∑bjRj(τ)+∑qjLj(τ)

在这种形式中，任何非零

Lj(τ)、

Rj(τ) 或

α 或

β 出现在

C 中都被严格禁止 - 这将导致 RHS 中出现可被

δ 整除的未抵消项。

由于微不足道的原因，分子中带有

γ 的项也被禁止出现在

C 中。

因此，

C 具有以下形式：

C=∑j∈privcjOj(τ)+βLj(τ)+αRj(τ)δ+∑hkZ(τ)τkδ.

不失一般性，假设非零

Lj(τ)-s 和

Rj(τ)-s（分别地）之间没有线性依赖关系。如果存在，我们可以使用它们使一些系数消失，并在此假设下进行操作。

还假设在这种形式下，

B 中出现的

Lj(τ)-s 的线性组合不能表示为

Rj-s 的总和-如果可以，请在

B 中进行这种替换以增加消失系数的数量，然后继续。

现在，我们要证明经过这样的变换后，

qj=0，并且

aj=bj=cj。事实上，获取所有带有

β 的项，我们看到 RHS 包含

∑cjβLj(τ)，而 LHS 包含

∑ajLj(τ)，这意味着

aj=cj，因为我们没有非平凡的线性组合。

类似地，RHS 中所有带有

α 的项都包含

∑cjαRj(τ)，而 LHS 包含

∑bjαRj(τ)+∑qjαLj(τ)。由于我们对不存在线性组合的假设，所有

qj 都被迫消失，并且

bj=cj。

UltraGroth 参数

假设我们的 R1CS 电路具有附加结构。也就是说，索引集合

1..n 的私有部分被分成

d+1 部分，

round0, …,

roundd。此外，一些公共输入被称为“挑战”，并且挑战集被分成

d 部分。向量空间

Ck 将表示 round

k 中挑战的空间。

让我们将空间

Vk 定义为具有非平凡系数索引的向量空间

roundk。然后，“旧”见证存在于

⨁kVk⊕公共输入中。

我们将第

k+1 轮策略定义为函数

Fk:Ck×⨁i≤kVk→Vk+1

第

0 轮的策略只是

V0 中的一个向量。

我们将完整见证定义为每个回合的这种策略集，这些策略在连续使用时，对于随机挑战，以极大的概率成功。

定义：代数见证 是在挑战空间

Fq(C) 上的有理函数域上 R1CS 的解，使得第 k+1 轮见证仅取决于直到第 k 轮的挑战。

代数见证很容易暗示上述策略。

思考代数见证是有用的，但在实践中使用它们可能不是那么有用 - 在有理函数域中的计算并不那么友好。我相信上面提到的关于策略的一般定义是一个更充分的抽象；即，在实践中，电路的见证将是一堆函数，用于对见证向量的已计算部分执行一些计算。

---

现在，我们将使用 Fiat-Shamir 启发式来模拟验证者的挑战响应。让我们构造以下 toxic waste：

α,β,γ,δ0,...,δd,τ

并获得以下引用字符串：

所有与以前一样，

δ 在 G1 和 G2 中都是已知的，并且对于私有索引，

Cj 的计算方式与

j∈roundk 相同：

Cj=Oj(τ)+βLj(τ)+αRj(τ)δk.

现在，对于除最后一轮之外的每一轮，让我们假设证明者还向验证者公开一些点

C(k)，并且诚实的证明者设置

C(k)=∑j∈roundkwjCj+rk[δd]1，其中

rk 是盲化因子。

然后，验证者通过设置

acck+1=Hash(acck,C(k)) 并将

wj=Hash(j,acck+1) 来发送挑战输入集

wj|j∈challk+1。

!! 注意：重要的是，我们不能简单地将挑战设置为 j 和 C^(k) 的哈希值，而不会冒着证明者追溯地重绕前几轮而不更改 C^(k) 的风险，这在某些情况下是可能的。

在我们以非交互方式运行此过程后，我们获得了完整的见证向量

w。然后我们执行与普通 R1CS 相同的计算以获得

H(x)。

然后，诚实的证明者选择另外两个随机值

r,s，并设置以下内容：

A=[α]1+∑jwjAj+rδd

B=[β]2+∑jwjBj+sδd

IC=∑j∈pubwjCj - 这里与任何地方一样，pub 输入包括挑战

对于 k < d，与以前一样

C(k)=∑j∈roundkwjCj+rk[δd]1

C(d)=∑j∈rounddwjCj+∑s≤nhsZs+sA+rB′−∑k<drk[δk]1−rs[δd]1

然后，以下等式 (*) 成立：

⟨A,B⟩=⟨α,β⟩+⟨IC,[γ]2⟩+∑k≤d⟨C(k),[δk]2⟩

完整验证算法检查此等式、公共输入的正确性和挑战的正确性。

为什么这个等式成立

事实上，这是一个直接的检查。与普通 Groth16 唯一足够不同的是盲化因子。让我们看看它是如何工作的：

C(k) 中的因子

rkδd 乘以

δk，这与来自

C(d) 的项

−rkδkδd 完全抵消。其余的盲化因子看起来与 Groth16 中的完全相同。

零知识

我声称诚实的验证者产生一个均匀随机的证明。原因是对于 k<d，

A,B 和

C(k) 都是等分布的，然后

C(d) 是唯一的。

可靠性？

我在这里感觉有点不稳定。无论如何，让我们继续在 AGM + ROM 中处理哈希。然后，我们首先证明以下引理：

引理： 等式 (*) 的任何解都是 R1CS 的有效解，并且

Ck 是对回合见证的约束性承诺。

在 AGM 中此等式的解导致 R1CS 这一事实可以通过以下技巧来完成。AGM 中的解是用某些多项式表示的解（即将 toxic waste 视为变量）。让我们在此解中替换

δk=δ,∀k。

也很容易看出不允许

C(k) 包含来自不同回合的任何

Cj 的，因为这会导致无法抵消的

δkδs 因子（它不能来自 RHS，因为

A 不允许带有非平凡分母的项，类似于普通 Groth16 的证明）。它们可能还包含其他一些术语，但是因为我们不知道它们之间的任何线性依赖关系，所以它仍然是一个约束性承诺。

◻。

因此，与验证者通信的交互式协议（我们通过 Fiat-Shamir 模拟）可以表示如下：证明者提供一些对见证各部分的承诺序列，然后生成一个有效的零知识证明，其中包含它已承诺的见证。

我不知道我是否在这里搞砸了，需要校对/审查。

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