密码学 - 斯巴达

Spartan 是一种基于 sum-check 的 zkSNARK，具有极其高效的证明者。它还具有几个独特的属性，这些属性与客户端证明特别相关，例如身份验证和其他零知识至关重要的用例。以下是一些亮点：

• Spartan 可以用任何多线性多项式承诺方案实例化（例如，Binius、HyperKZG、Samaritan、WHIR、Mercury、BaseFold、PST13、Dory、Hyrax）。根据所使用的多项式承诺方案，可以实现不同的属性（例如，小域或大域、后量子或前量子安全性、透明或通用设置、基于哈希或基于曲线、二进制域或素数域）。
• Spartan 在算术化方面具有灵活性：它可以支持 R1CS、Plonkish、AIR 及其推广 CCS。Spartan 协议本身在内部使用 lookup 参数，因此还可以使用 Spartan 证明 lookup 约束。
• 证明者的工作自然地分为一个依赖于 witness 的部分和一个独立于 witness 的部分（很大一部分，高达 90%，的证明者工作发生在独立于 witness 的部分）。后一部分可以委托给任何不受信任的实体，而不会违反零知识。请注意，其他流行的 zkSNARK（例如，Groth16、Plonk、HyperPlonk、Honk）不具备 witness 相关部分和 witness 独立部分之间如此清晰的分解。
• Spartan 证明者的 witness 相关工作已被更新的研究证明对 MPC 友好，从而允许委托整个 Spartan 证明者。
• 对于一致的约束系统，可以通过消除证明者的 witness 独立工作来进一步优化 Spartan 的证明者，这占证明者工作的大约 90%。

尽管有几篇论文描述了 Spartan 和后续工作，但即使是专家也对 Spartan 协议缺乏了解。本文档的主要目标是提供对 Spartan 协议的简要介绍。虽然我们的目标是精确，但为了清晰和易于理解，我们有时可能会滥用符号。

采用和用例

Spartan 已在各种设置中采用（证明机器执行，又名 zkVM，独立证明系统，coSNARK，folding 方案等）。

由于其轻量级的证明者以及将其大部分证明者工作卸载到不受信任实体的独特属性（不牺牲零知识）（我们将在下面详细介绍），World 计划使用 Spartan 作为其证明方案（有关详细信息，请参见此推文）。其他正在进行的工作也在探索如何利用 Spartan 的委托证明属性。

Spartan 还用作一种证明系统，用于压缩 folding 方案生成的证明，在执行许多 folding 步骤之后（有关详细信息，请参见 Nova 和 MicroNova）。随后，一种提前停止的 Spartan 促成了更有效的 folding 方案的创建，称为 HyperNova。最近还引入了一种提前停止的 HyperNova，称为 NeutronNova。这是目前最高效的 folding 方案，尤其是在分组设置中。在 NeutronNova 之前，folding 方案存在一个或多个缺点。NeutronNova 获得了先前方案的最佳属性，同时解决了它们的缺点（有关详细信息，请参见此主题）。此外，HyperNova 已适应 lattice 设置，以构建后量子安全 folding 方案，包括 LatticeFold、LatticeFold+ 和 Neo。这些方案已引起人们的极大兴趣，可为下一代 zkVM 提供动力。

Spartan 为 Jolt 的所有组件提供支持，Jolt 是一种最先进的 zkVM，Spartan 的原始实现为 Jolt 的实现提供了一个起点。具体来说，Jolt 使用 Spartan 来证明 R1CS 约束。此外，Spartan 的一个内部组件 Spark 被重构为用于巨型结构化表的 lookup 参数（有关详细信息，请参见 Lasso）。该组件用于证明指令执行。此外，Spark 的前身 Spice 用于证明读写内存操作和寄存器操作。

由于其轻量级的证明者及其在承诺方案和字段方面的灵活性，Spartan 擅长证明某人持有有效的身份证明文件（例如，护照、JWT、驾驶执照）。实际上，几个 项目使用 Spartan 来证明 ECDSA 签名和哈希函数的有效性。另请参见较早的 Spartan-ecdsa 项目，甚至更早的 标准化工作。

Spartan 的独特属性

Spartan 协议的一个独特属性是，它可以自然地分为两部分：(1) 涉及 witness 的核心协议，以及 (2) 证明对编码约束/电路的稀疏多项式的评估的 Spark 协议。

出于零知识的目的，只有第一部分需要由持有秘密 witness 的证明者运行。第二部分可以外包给任何不受信任的实体。请注意，不受信任的实体可以比逐个证明更有效地证明一批关于同一稀疏多项式的声明：不受信任的方首先执行

n-to-

1 归约，然后仅运行一次 Spark 协议（我们将在另一篇文章中详细介绍）。不受信任的实体还可以使用另一个证明系统（例如，MicroSpartan，Groth16）生成单个证明，以证明多个 Spartan 证明的正确性。

请注意，其他证明系统（例如 Plonk 或 Groth16）不满足证明者工作在 witness 相关部分和 witness 独立部分之间的这种类型的分解。HyperPlonk 采用了 Spartan 的技术，但紧随 Plonk 的蓝图，因此它也没有此功能。

Spartan 的核心协议（与 witness 相关）包括对 witness 的承诺，两个 sum-check 调用以及在单个随机点证明 witness 多项式。与许多其他 zkSNARK 协议（例如 Plonk，Groth16）相比，这非常轻量级。最近的工作 表明 Spartan 的核心协议对 MPC 友好，从而可以创建由 Spartan 提供支持的 coSNARK。由于 Spark 协议无需通过 MPC 协议运行，因此允许在 coSNARK 设置中使用整个 Spartan 协议。

一致的约束系统

如果所证明的约束系统是结构化的（例如，同一子约束系统的重复副本），则可以进一步优化 Spartan，从而减少对 Spark 协议的依赖。

验证者可以自己评估所需的稀疏多项式，而不是将负责证明与约束系统相关的稀疏多项式的 Spark 证明者外包给不受信任的实体。对于某些约束系统（例如，一致性约束（如 AIR）），评估所需稀疏多项式的成本与电路的大小成对数关系，因此对于一致性电路，可以完全省略 Spark 证明者。SuperSpartan 论文 详细描述了如何通过利用一致性结构来快速评估稀疏多项式。

另一个示例是 Phalanx，它考虑了“编码迭代顺序计算的 R1CS”的情况。它引入了三个顺序 sum-check（而不是 Spartan 的两个 sum-check），其中最外面的 sum-check 用于 folding

n 个相同的 R1CS 副本到一个副本中。然后，将核心 Spartan 协议应用于单个小的 R1CS 副本。Jolt 也应用 Spartan 来证明迭代的 R1CS，但是每次迭代都很小（少于 100 个约束）。为此，Jolt 使用两个顺序 sum-check 调用，并优化第二个 sum-check 以利用重复的结构（有关详细信息，请参见此链接）。

算术化

为简单起见，本文档重点介绍 R1CS。

令约束系统在有限域上定义

F，其中：

• 三个稀疏矩阵

A,B,C∈Fm×m.

实例-witness 对的定义如下：

• 一个公共输入/输出向量

x∈Fnx.

• 一个 witness 向量

w∈Fnw.

不妨假设，

nw=nx+1 （我们在下面使用它）。

定义：

z:=(w,1,x)∈Fm,with m=nw+1+nx.

一个有效的赋值满足：

Az∘Bz=Cz,

其中

∘ 表示元素乘法。

预处理 / 计算承诺 / 全息术

每个矩阵

M∈{A,B,C} 以稀疏格式存储：

令

N 是

M 中的非零条目的数量。 编码：

• rowM∈[m]N：非零条目的行索引，
• colM∈[m]N：列索引，
• valM∈FN：对应的值。

此表示形式可实现有效的稀疏矩阵-向量积，并构成 Spartan 内部 Spark 协议的基础。

Spark，Lookup 表和辅助材料

Spartan 在内部调用 Spark，后者依赖于 lookup 参数 来检查稀疏多项式求值（例如，矩阵-向量积）的正确性。这些参数将

rowM 和

colM 视为对结构化 lookup 表的地址查询。

为了启用 lookup 参数，在预处理期间包括其他辅助材料。确切的材料取决于 lookup 协议的选择：

• 经典 Spartan（如原始论文中所述）使用 Blum 等人的 离线内存检查 的变体（如 Spice 中所用），其中辅助材料是时间戳/计数器。
• 也可以使用其他 lookup 协议：
  • logUp：一种 lookup 参数，对于证明者而言效率较低，并且辅助材料与 Spice 的相似。它的效率较低，因为它要求证明者在 lookup 协议期间发送 oracle，而原始 Spartan 和 Shout（接下来介绍）中使用的协议则不需要。LogSpartan 和 DFS 都是在 Spark 中使用 LogUp 的 Spartan 变体。
  • Shout：一种新的 lookup 参数，旨在提高证明者的效率。最近，一篇 论文 中介绍了使用 Shout 作为 lookup 参数的 Spartan 版本，并将其分析为 Spartan++。

这些选项在实例化 Spartan 时提供了灵活性，可以在证明者时间、验证者复杂性和证明大小方面进行不同的权衡。

证明协议

我们用 多项式 IOP 模型 描述协议，在该模型中，证明者将其多项式作为消息发送，并且验证者可以请求在域中的任何点评估多项式。验证者还可以查询预处理步骤中的任何多项式。

通过使用 多项式承诺方案，此类多项式 IOP 被编译为 简洁的参数：证明者不是发送多项式，而是发送对多项式的简洁的承诺。当验证者查询多项式时，证明者发送一个评估以及一个证明，该证明表明评估与先前承诺一致。此编译导致 Spartan 简洁的交互式参数。然后可以使用 Fiat-Shamir 转换和零知识转换将其转换为 zkSNARK。

Spartan 的核心是 sum-check 协议。Sum-check 协议是一种交互式证明系统，允许证明者和验证者减少检查是否

T=∑x∈[m]g(x) 的任务，其中

g 是变量

x 中的多项式，以检查是否

eg=g(rx) 的任务，其中

eg 和

rx 是在 sum-check 协议过程中选择的。本质上，sum-check 协议将检查对

g 的评估总和的任务减少到在随机点进行

g 的单个评估。

(1) 核心协议（与 witness 相关）

现在，我们描述 Spartan 的核心协议。该协议最初在 Spartan 论文 的第 5.1 节中进行了描述。我们可以在以下论文中找到有关 Spartan 核心协议的其他描述：（i）Brakedown 的第 3 节，（ii）SuperSpartan 的图 2。

令

s=log⁡m. 当我们写

[m] 时，我们指的是表示从

0 到

m−1 的数字的位串集，即

{0,1}s.

为简单起见，我们将假定从向量到多线性扩展多项式的自然映射。

1. 证明者发送 声称的 witness 多项式

   w。（如上所述，当转换为 SNARK 时，这将是对多项式的承诺。）

2. 验证者选择

   τ∈Fs 并将其发送给证明者。

3. 令

   a=Az,

   b=Bz,

   c=Cz （即，

   a,b,c 是用矩阵-向量积计算的）。证明者和验证者运行 sum-check 协议 以检查是否：

   0=∑x∈[m]g(x),where g(x)=eq(τ,x)⋅(a(x)⋅b(x)−c(x)).

   Sum-check 协议将其简化为检查是否：

   eg=g(rx),

   其中

   eg 和

   rx 是在协议过程中选择的。

4. 证明者发送

   vA,vB,vC，据称等于

   a(rx),b(rx),c(rx)。

5. 如果以下条件不成立，则验证者拒绝：

   eg=eq(τ,rx)⋅(vA⋅vB−vC).

   验证者可以在对数时间内自行计算第一个量。

6. 证明者现在需要确定

   vA,

   vB, 和

   vC 的正确性。验证者选择一个随机值

   ρ∈F 并将其发送给证明者。

7. 验证者和证明者运行第二个 sum-check 以检查以下内容是否成立：

   T=∑y∈[m]h(y),

   其中：

   T=vA+ρ⋅vB+ρ2⋅vC,

   h(y)=(A(rx,y)+ρ⋅B(rx,y)+ρ2⋅C(rx,y))⋅z(y).

   这简化为检查是否

   eh=h(ry) 其中

   eh 和

   ry 是在 sum-check 协议过程中选择的。

8. 为了方便上述检查，证明者发送：

   • ew=w(ry[1..])，其中

     ry[1..] 指的是向量

     ry 的一个切片，除了第一个条目。

   • eA=A(rx,ry)
   • eB=B(rx,ry)
   • eC=C(rx,ry)

9. 验证者计算：

   ez=(1−ry[0])⋅ew+ry[0]⋅(1,x)(ry[1..]),

   并检查：

   eh=(eA+ρ⋅eB+ρ2⋅eC)⋅ez.

   如果检查失败，则验证者 拒绝。

10. 由于验证者无法访问 oracle

    A,B,C（仅其稀疏表示形式），因此我们剩下检查

    eA,eB,eC 的正确性。通过为它们中的每一个调用 Spark 协议来完成此操作。（请注意，在编译的 zkSNARK 中，

    ew 的检查方式是让证明者发送证明，表明该评估与第一步发送的承诺一致。）

(2) Spark 协议（与 witness 无关）

现在，我们描述 Spark 协议，该协议使我们可以完成核心协议的最后一步。该协议最初在 Spartan 论文 的第 7.2.2 节中进行了描述。我们可以在 Brakedown 的第 6 节和 Lasso 的第 4 节中找到有关此协议的其他描述。我们将重点介绍一种稀疏多项式评估的情况，但是该协议自然地可以推广为一次证明一批评估声明。

为简单起见，我们专注于用两个“地址”向量来编码稀疏矩阵（

row 和

col）。如 Lasso 这篇论文中所述，可以将其推广成任意数量的向量。例如，可以将这些向量中的每一个进一步分成两个向量，从而得到总共四个向量。在此特定示例中，主要优点是进行 lookup 的表的大小从线性减小到约束数量的平方根。Lev Soukhanov 观察到，在这种情况下，与仅使用两个地址向量相比，可以在 Spark 的第一步中更有效地承诺 oracle。

每个矩阵

M∈{A,B,C} 使用以下内容表示：

• rowM∈[m]N
• colM∈[m]N
• valM∈FN

回想一下的

M 是多线性的延伸：

M(rx,ry)=∑z=0N−1eq(rx,rowM[z])⋅eq(ry,colM[z])⋅valM(z)

让我们构造两个结构化表

T1,T2∈Fm，这些条目如下。

• T1(i)=eq(rx,i) 适用于所有

i∈[m]

• T2(i)=eq(ry,i) 适用于所有

i∈[m]

证明者和验证者检查

eM=M(rx,ry) 以供每个

M∈{A,B,C} 如下所示。

1. 证明者通过对表进行 lookup 来发送 oracle：

   • E1(z)=T1[rowM[z]]

   • E2(z)=T2[colM[z]]

     适用于所有

     z∈[N]

2. 他们运行一个 sum-check 来验证：

eM=∑z∈[N]f(z),where f(z)=E1(z)⋅E2(z)⋅valM(z)

这减少到检查：

ef=f(rz)

对于一些随机点

rz 和

ef。

3. 证明者发送：
   • v1=E1(rz)
   • v2=E2(rz)
   • v3=valM(rz)
4. 验证者检查：

ef=v1⋅v2⋅v3

如果失败，则拒绝。

5. 验证者现在通过使用 lookup 参数 检查

E1 和

E2 的正确性。请注意，lookup 表的地址来自预处理阶段：

rowM 和

colM。请注意，大多数 lookup 参数都允许批量证明，因此可以一次证明

E1 和

E2 的正确性。

其他资源

• Spartan 描述了包括 Spark 在内的 Spartan 协议。
• Brakedown 论文提供了 Spartan 作为多项式 IOP 的描述
• SuperSpartan 论文表明 Spartan 支持 CCS，后者概括了 Plonkish、R1CS 和 AIR。
• Lasso 论文推广了 Spark
• MicroSpartan 描述了具有最小证明大小的 Spartan 变体；这在内部使用 LogUp。
• Shout 论文描述了 Shout lookup 参数，以及 Spartan 的变体，称为 SpeedySpartan 和 Spartan++
• Thaler 的书 提供了基础知识，包括 sum-check 协议、承诺方案、Spartan 和 Spark 的详细信息。

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