多项式路径

以下研究基于 Arantxa Zapico 最近在 为什么你应该关心多项式 的 PROGCRYPTO 演讲以及 Eli Ben-Sasson、Alessandro Chiesa 和 Nicholas Spooner 关于 交互式神谕证明 的研究论文。

这篇文章是一个总体概述。随着零知识证明和密码协议领域的快速发展，研究和理解新兴技术从不同角度来看至关重要。

这篇文章代表了这样一种探索，旨在揭开 PIOPs 的神秘面纱，并展示它们在重新塑造隐私保护计算领域的潜力。

引言

一个高效的证明系统的概念，其中一个计算资源有限的验证者可以被说服相信任意复杂计算的正确性，是复杂性理论和密码学的基础。从高层次来看，证明系统作为数学基础，允许一个实体（证明者）说服另一个实体（验证者）某个陈述是真的，其中验证者拥有有限的资源，并且在确保各种数字协议的安全性和功能性方面也至关重要，从区块链交易到安全多方计算。

这些证明系统中效率的本质无法夸大；它直接转化为更低的计算成本和更广泛的采用，使安全的数字交互在规模上变得更可接触和可持续。

历史上，这一优化追求通过交互式证明（IPs）和 概率可验证证明（PCPs） 的发展得到了推动，每一个都标志着我们在用最小资源进行验证方面的重大进展。

• IPs 在证明者和验证者之间引入了双向通信，超越了静态证明。

• PCPs 通过检查证明的小部分来展示 probabilistic 验证声明，开创了“次线性”方法。

这些为协调严格验证与现实世界效率限制奠定了基础。但为了实现更广泛的应用，需要新一代证明系统。交互式神谕证明（IOPs）应运而生。

现实世界中的证明系统

在今天的许多数字系统中，一方需要说服另一方某些陈述为真或计算是正确的，而不披露私密的基础数据。例如，希望存储遗传数据的客户可能需要验证云服务器正确地对其进行了分析而不透露实际的健康数据。或者，一个客户可能需要验证在线卖家安全地处理了敏感交易而不分享细节。

交互式神谕证明 作为一种框架出现，允许通过证明者和验证者之间的问询和响应的往返方式实现这种说服。证明者将私密数据计算编码成一种“神谕”表示，它隐藏了原始内容。通过要求证明者在这些编码数据上执行某些操作并返回结果，验证者逐渐被说服，无需查看基础输入。

IOPs 的工作原理

1. 证明者将私密敏感数据编码为一个“神谕” - 一种隐蔽原始内容的密码承诺

2. 验证者向证明者发送隐藏数据的挑战或查询

3. 证明者在不解密的情况下对神谕编码的数据执行操作

4. 证明者返回证明以确认计算已正确完成

5. 验证者检查证明的格式是否正确

6. 步骤 2-5 在交互式往返中重复，直到验证者被说服其真实性

关键特点

• 计算完整性验证无需暴露原始数据

• 通过对话逐步建立信心

• 对于证明者和验证者来说，查询和响应高效

交互性和加密使得 IOPs 对处理敏感或机密数据的 web3 平台有独特的用途。通过保持数据供应和计算的私密性，同时允许验证，IOPs 克服了透明性与隐私之间的权衡。

交互式神谕证明与多项式结合

引入的交互式神谕证明范式提供了一条更实用的路径，用于对加密数据进行验证。然而，实际实施代表秘密计算的“神谕”的技术可能会显著影响效率和灵活性。

这就引出了多项式 - 具有有用计算属性的代数结构。通过将敏感数据编码成多项式系数，我们可以在从未解密实际内容的情况下评估、转换和推理关于加密信息。

欢迎来到 PIOPs

多项式交互式神谕证明（PIOPs） 专门利用多项式承诺方案，以高效地实现 IOPs。它们在多变量多项式方程中表示秘密，每个项由变量指数、编码数据的系数以及将其联系在一起的模运算组成。

多项式是构建高效零知识证明系统的强大工具。具体而言，有一种框架称为多项式交互式神谕证明（PIOPs），它使证明者能够说服验证者某些关于特定数据集或计算是真实的陈述，而无需揭示实际的基础数据或计算。

多项式之所以对这一过程如此有用的关键原因在于，它提供了一种将非常大的数据集“编码”的方法，将其表示为多项式的系数向量。因此，你可以有一个包含 2^20 个元素的数据集，构造一个次数为 2^20-1 的多项式，具有每个数据元素作为系数。这个多项式可能非常庞大，但有一个有用的特性 - 如果在任何给定点对多项式进行评估，你将仅得到一个单一的数值结果。因此，它将庞大的数据集“压缩”为一个数字。

这意味着证明者可以将该评估的多项式值（仅一个数字）发送给验证者，作为编码所有基础数据的承诺。然后，证明者可以通过操作多项式 - 执行诸如多项式相乘、评估它们等操作 - 来证明关于数据的特定陈述，而无需揭示数据，使用 PIOPs。验证者只看到多项式值，而不是实际数据。

这种多项式表达方式能够在隐蔽数据集上执行间接操作，以及零知识证明已正确执行计算。我们可以通过代数规则相乘编码、评估承诺，并证明关于加密内容的陈述。

因此在 PIOP 中，证明者承诺将机密数据转换为一种多项式表示，模糊了原始基础元素。然后，验证者发出挑战以展示对这一编码信息的关系。只要遵循数学规则，验证者在未接触源秘密的情况下获取信服。

Kate 承诺方案 (KZG) 在 PIOPs 中的作用

Kate 承诺方案 (KZG) 在启用高效和安全的证明系统中发挥了至关重要的作用。KZG 是一种多项式承诺方案，这意味着它允许我们承诺一个多项式，稍后证明该多项式在某些点的特定值。

想象一下你有一个大数据向量，比如一个交易列表或数据库。与直接处理整个向量不同，你可以将这些数据编码成一个多项式。向量的每个元素成为多项式的一个系数。这就是 KZG 的用武之地。

在 KZG 中，证明者通过使用数学群中一个秘密元素的幂来承诺多项式。这个秘密元素就像特殊的密钥，允许证明者和验证者在不揭示实际数据的情况下处理多项式。证明者向验证者发送承诺，其大小远小于原始向量。

稍后，当证明者想要证明关于数据的某些事情时，他们可以使用已承诺的多项式。例如，证明者可能想要显示这个多项式在某一点的评估结果是特定值。为此，他们利用 KZG 方案生成证明，这涉及对多项式和秘密元素进行一些数学运算。

KZG 的美在于，它允许高效的证明和汇聚。证明者无需单独证明向量的每个元素，而是可以创建一个覆盖多个元素的单一证明。这使得证明大大较小且更快地被验证。

KZG 在基于多项式的交互式证明系统中 (PIOPs) 被使用。在 PIOP 中，证明者和验证者使用多项式进行通信。证明者发送多项式，验证者通过在特定点查询它们来检查多项式。KZG 使得证明者能够在这一框架内创建简洁且令人信服的证明。

KZG 的一个有趣方面是 Lagrange 基础。通过使用 Lagrange 基础对数据进行编码，证明者可以高效地证明向量中单个元素的值。Lagrange 基础中的每个多项式设计为在其对应元素上返回 1，而在其他所有元素上返回 0。这个属性使得在不揭示整个向量的情况下，证明特定元素变得变得简单。

PIOPs: zkSNARKs 的构建模块

零知识简洁非交互式知识论证（zkSNARKs）是一种强大的密码工具，允许一方在不揭示任何额外信息的情况下向另一方证明一个陈述为真。PIOPs 在构建有效 zkSNARKs 中发挥了至关重要的作用，为使用多项式进行编码和操作数据提供了基本框架。

在 zkSNARK 中，证明者希望说服验证者他们掌握满足某个计算陈述的秘密值，而不揭示秘密自身。PIOPs 通过允许证明者将秘密值和计算陈述编码为多项式表示，从而实现这一要求。

然后，证明者使用多项式的性质生成简洁的证明，表明编码的秘密满足编码的计算陈述。这个证明使用多项式承诺和零知识协议构建，确保验证者可以在不获知任何有关秘密的信息的情况下验证证明的有效性。

通过利用 PIOPs 的效率和安全性，zkSNARKs 可以实现显著的特性：

1. 简明性：证明非常简短，甚至针对复杂计算也可以快速验证。

2. 非交互性：证明可以离线生成，稍后验证，无需进一步交互。

3. 零知识：证明除了计算声明的有效性外，不会揭示任何关于秘密的信息。

PIOPs 和 zkSNARKs 的结合为保护隐私的应用打开了广泛的可能性，如机密交易、匿名凭证和对加密数据的可验证计算。

让我们通过一个非常简化的数学示例来探讨多项式 IOPs 如何在 SNARKs 的背景下工作。我们将使用一个简单的算术电路来说明这一过程。

假设我们有以下算术电路： (a + b) * (c - d) = e

我们希望证明我们知道满足该方程的 a、b、c 和 d 的值，而不揭示实际的值。

步骤 1：将值编码为多项式 首先，我们将值 a、b、c 和 d 编码为多项式的系数。假设：

• a = 3，由多项式 A(x) = 3 表示

• b = 1，由多项式 B(x) = 1 表示

• c = 4，由多项式 C(x) = 4 表示

• d = 2，由多项式 D(x) = 2 表示

步骤 2：构造约束多项式 我们创建一个代表算术电路的约束多项式。在这种情况下，约束多项式将是： CP(x) = (A(x) + B(x)) * (C(x) - D(x))

替换值后： CP(x) = (3 + 1) * (4 - 2) CP(x) = 4 * 2 CP(x) = 8

步骤 3：承诺多项式 证明者通过使用像 KZG（Kate-Zaverucha-Goldberg）这样的多项式承诺方案，对多项式 A(x)、B(x)、C(x) 和 D(x) 进行承诺。这些承诺是加密值，隐藏了实际多项式，但允许后续的评估和验证。

步骤 4：证明约束多项式的评估等于期望值 证明者需要说服验证者约束多项式 CP(x) 的评估等于期望值（在这种情况下为 8），而不揭示 a、b、c 和 d 的实际值。

为此，证明者生成一个 PIOP 证明：

1. 证明者在验证者选择的随机点 z 处评估多项式 A(x)、B(x)、C(x) 和 D(x)。

2. 证明者使用 A(z)、B(z)、C(z) 和 D(z) 的评估，计算 CP(x) 在相同点 z 处的评估。

3. 证明者将 A(z)、B(z)、C(z)、D(z) 和 CP(z) 的评估发送给验证者，同时附上这些评估与多项式承诺一致的证明。

步骤 5：验证 PIOP 证明 验证者检查 PIOP 证明：

1. 验证者验证评估 A(z)、B(z)、C(z) 和 D(z) 是否与多项式承诺一致。

2. 验证者使用接收到的评估计算机会预期的 CP(z) 值，并检查是否与声称的值相匹配（在此案例中为 8）。

如果 PIOP 证明成功验证，验证者就会相信证明者知道 a、b、c 和 d 的值，符合算术电路的要求，同时不揭示实际的数值。

这是一个简化的示例，但它展示了在 SNARK 证明系统中使用 PIOPs 相关的关键步骤。

在实践中，算术电路可能更加复杂，且多项式通常具有更高的次数。PIOP 证明确保证明者能够说服验证者算术电路的可满足性，同时保留输入值的隐私。

揭开 PIOPs 的神秘面纱

PIOPs 的核心有两个关键概念：

• 多项式编码作为锁住的箱子

• 一种对话式验证舞蹈

多项式编码作为锁住的箱子

一个有用的类比是将多项式编码视为特殊的锁住箱子，允许在不打开内容的情况下进行有限操作。

具体而言，证明者首先将敏感原始数据（例如财务记录、医疗数据等）以数字形式编码。该长字符串变成多元多项式方程的系数向量。

我们可以将这一多项式承诺方案可视化为将敏感数据密封在一个由数学锁保护的加密箱子里。这个箱子隐藏了所有实际值，仅显示外壳。

然而，该箱子允许选择性地应用某些钥匙，以证明的方式重新塑造和变换其外部，间接作用于内容：

• 特殊钥匙可以通过在特定点处评估多项式编码，拉伸/压缩箱子

• 其他钥匙可以验证模旋转或重组其结构的操作

• 一些钥匙附上有效转换的加密证明

因此，通过要求进行正确类型的操作，并验证所用钥匙遵循数学规则，我们可以获得对隐蔽原始数据被妥善处理的信心，而无需直接接触。多项式编码充当数据容器，我们可以在不公开内容的情况下进行计算。

1. 敏感原始数据：

   • 在过程的开始，我们有一些希望保护的敏感信息。这可能包括财务记录或医疗数据。

   • 我们不希望任何人可以直接看到这些数据，因为它们是私密和机密的。

2. 将数据编码为多项式系数：

   • 为了保持敏感数据的安全，我们需要将其转化为隐藏原始信息的不同形式。

   • 在这一步中，我们将原始数据转换为一个称为多项式系数的数字列表。

   • 想象它就像通过一个特殊机器将数据打乱成秘密代码。

3. 系数向量：

   • 编码数据后，我们最终会得到一个被称为系数向量的数字列表。

   • 在图片中，系数向量显示为 (3, 1, 4, 1, 5, 9, ...).

   • 这个向量中的每个数字代表一部分编码数据。

4. 多项式编码（锁住的箱子）：

   • 现在，我们将系数向量放在一个名为多项式编码的特殊“锁住的箱子”里。

   • 这个锁住的箱子就像一个安全容器，只能被拥有正确密钥的人打开，以隐藏编码数据。

   • 该箱子遮掩了原始敏感数据，因此即使某人获得了箱子，他们也无法看到里面的内容。

5. 隐私：

   • 锁住的箱子（多项式编码）旨在保护敏感数据的隐私。

   • 如图所示，有一个箭头指向锁住的箱子以表示“隐私”部分。

   • 这意味着原始数据对于没有权限解锁的人保持隐藏和不可访问。

6. 应用特殊钥匙（评估钥匙）：

   • 现在，假设我们希望对编码数据进行一些操作或计算，而不揭示实际信息。

   • 为此，我们使用一个名为评估钥匙的特殊钥匙。

   • 在图中，从锁住的箱子到“应用特殊钥匙”步骤有一条箭头。

   • 评估钥匙允许我们以特定方式与锁住的箱子互动，而不实际打开它或看到里面的原始数据。

7. 在特定点评估多项式：

   • 我们可以使用评估钥匙做的一件事情是在特定点评估多项式（编码数据）。

   • 这意味着我们插入一个特定的值并根据锁住箱内的编码数据计算结果。

   • 就像向锁住的箱子提问并在未查看原始数据的情况下获得答案。

8. 评估结果（单一数字）：

   • 当我们在特定点评估多项式时，我们得到一个单一数字作为结果。

   • 这个数字是我们对编码数据执行的计算的结果。

   • 我们可以继续使用这个结果进行进一步的计算或者比较，而无须知晓隐藏在锁住箱子里的实际敏感信息。

因此，总之，这个过程让我们能够采取敏感数据，将其编码成一种特殊的形式（多项式系数），并将其锁在一个安全的箱子内（多项式编码）。然后，我们可以使用一个特殊的钥匙（评估钥匙）对编码数据进行计算，而不会看到原始信息。这样，我们可以在保护数据隐私的同时处理数据。

一种对话式验证舞蹈

不同于静态证明，验证过程通过证明者和验证者之间的交互“舞蹈”进行。

验证者发布一系列量身定制的多项式操作挑战，以确认对隐蔽数据进行的计算是否正确。证明者在响应每个挑战时操纵多项式箱，发送回变换后的编码及执行的证据。

只要这些响应系统地遵循有效的代数规则，验证者就逐渐被说服原始数据的正确处理。通过引导这一对话，看到正确使用的钥匙解锁中间证明状态，信心逐步建立。

因此，PIOPs 将交互性与多项式密码学结合，促进了基于数学形式化的对话，同时足够灵活以适用于需要验证敏感数据计算的实际应用。对话过程在保护基础秘密的同时提供信心。

在这张图中：

1. 验证舞蹈的开始以“验证舞蹈的开始”提示为标志，表示证明者和验证者之间的互动过程的开始。

2. 验证舞蹈的进展包括一系列交互:

   • 验证者向证明者发出第一个多项式操作挑战（挑战 1），请求对敏感数据的多项式编码进行特定操作。

   • 证明者收到挑战 1，按要求操纵多项式而不揭示基础数据，并生成证明 1 以确认所请求操作的正确执行。

   • 证明者将证明 1 发回给验证者。

   • 验证者收到证明 1 并验证其正确性。如果证明有效，验证者对证明者的主张的信心开始增强。

   • 验证者向证明者发出第二个多项式操作挑战（挑战 2），请求对多项式编码进行另一特定操作。

   • 证明者收到挑战 2，适当地操纵多项式，生成证明 2，并将其发送回验证者。

   • 验证者收到证明 2 并验证其正确性。如果证明有效，验证者对证明者的主张的信心再次增强。

3. 图中还有一个可选的部分，验证者如有必要可以向证明者提出进一步的挑战。证明者以随后的证明进行响应，验证者则验证每个新的证明。这一过程可以持续，直到验证者满意为止，或达到预定的挑战次数。

4. 在所有挑战发布和相应证明得到验证后，验证舞蹈以“验证舞蹈结束”提示为标志，结束。

5. 如果证明者提供的所有证明有效且验证者的信心达到了足够的水平，验证者则向证明者发送消息，表示验证已成功。

证明者操纵多项式编码并提供证明，而验证者检查响应并逐步建立信心。通过多次挑战和证明逐步建立的验证者信心是 PIOP 验证过程的关键方面。

比较 PIOPs

正如我们所看到的，PIOPs 提供了一个强大的框架，用于实现对加密数据的高效和安全的计算验证。但它们与其他著名的证明系统有何比较？让我们仔细看看互动证明 (IPs)、概率可检查证明 (PCPs)、zkSNARKs 和 PIOPs 的关键特性，以理解它们独特的优势和差异。

注意：此表简化复杂的密码概念以便进行比较。每个证明系统的细节可能非常复杂，且各系统的实用性可能基于其应用的背景而有所不同。

尽管 IPs 和 PCPs 为互动和高效验证奠定了基础，但 zkSNARKs 和 PIOPs 则在这些基础上进一步发展，提供高效和保护隐私的解决方案。zkSNARKs 在提供简洁和非交互的零知识证明方面表现出色，非常适用于区块链应用。而 PIOPs 则在交互证明的优势与多项式承诺所提供的效率和隐私之间取得了平衡，使其在广泛的密码应用中变得灵活。每种证明系统在密码学领域中都各有其位置，依据应用的具体要求、效率、可扩展性、隐私和信任假设进行选择。

结论

在这篇文章中，我们探讨了 PIOPs 的迷人旅程，从其在交互式证明和概率可检查证明中的基础开始。我们看到 PIOPs 如何利用多项式编码的魔力创建“锁住的箱子”，使我们能够对加密数据进行计算而不揭示基础秘密。证明者和验证者之间的对话式验证之舞展示了 PIOPs 的优雅，因为它们通过一系列挑战和响应逐步建立对计算准确性的信心。

但真正的兴奋在于 PIOPs 的实际应用。正如我们所发现的，PIOPs 是开创性零知识简洁非交互式知识论证（zkSNARKs）的构建模块。通过实现高效和简洁的零知识证明，PIOPs 打开了一个保护隐私的协议的世界，从机密交易和匿名凭证到加密数据上的可验证计算。

当然，PIOPs 并不是密码证明系统领域中的唯一参与者。我们与互动证明、概率可检查证明和 zkSNARKs 的比较突出了每种方法的独特优势和权衡。尽管 PIOPs 可能并不是每种情况的完美选择，但其在效率、可扩展性和隐私之间的平衡令其成为广泛应用的引人注目的选择。

展望未来，PIOPs 的发展及其在隐私增强技术全景中塑造角色的前景确实令人兴奋。

在 l2iterative.com 找到 L2IV，并在 Twitter 上关注 @ l2iterative

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