密码学专家解答10个关键技术问题

密码学是电子设备和互联网的基础组成部分，用于保护信用卡、手机、网页浏览（希望您正在使用TLS！）甚至绝密军事数据。在区块链领域，密码学同样至关重要，以太坊等区块链依赖哈希、Merkle树和ECDSA签名等原语来运行。配对、全同态加密和零知识证明等创新技术也已进入区块链领域。

对许多人来说，密码学就像一个复杂难解的"数学魔法"谜题。作为区块链安全工程师，我一直对密码学着迷但从未深入探讨。幸运的是，我在Trail of Bits的同事是世界级密码学专家！我向他们提出了十个问题，帮助您解开密码学的一些奥秘。请注意，有些问题相当高级，可能需要额外的背景知识。但如果您是 aspiring 的密码学爱好者，请不要气馁——继续阅读！

1. SNARK中最常用的承诺方案有哪些？

多项式承诺方案是一种协议，证明者承诺某个多项式并生成证明表明承诺有效。该协议包含三个主要算法：

• Commit
• Open
• Verify

在提交阶段，证明者发送其承诺——即他们在给定点对多项式f的评估声称值（即值a使得f(x) = a）。承诺应具有约束性，意味着一旦证明者承诺某个多项式，他们就不能"改变主意"并为不同的多项式生成有效证明。它也可能具有隐藏性，即在密码学上难以提取值x使得f(x) = a。

在开放阶段，证明者发送证明表明承诺有效。在验证阶段，验证者检查该证明的有效性。如果证明有效，我们知道证明者以高概率知道x使得f(x) = a。

我们已经熟悉一种类型的向量承诺——Merkle树。多项式承诺方案的性质类似，但适用于多项式。生产中最常用的承诺方案有：

• KZG (Kate-Zaverucha-Goldberg)，例如用于EIP 4844中的danksharding
• FRI (Fast Reed-Solomon Interactive Oracle Proofs of Proximity)，用于STARKs
• 像Pedersen承诺这样的承诺用于Bulletproofs等证明系统（被Monero和Zcash使用）

KZG承诺利用了这样一个事实：如果多项式f(x0) = u在某个点x0，那么f(x) - u必须有因子(x - x0)。根据Schwartz-Zippel引理，如果我们选择足够大的域，不同的多项式g(x) - u被(x - x0)整除的可能性非常小。在高层次上，我们可以利用这一点来承诺f(x)的系数并生成证明，验证者可以通过椭圆曲线配对极快地检查，而不揭示多项式本身。

FRI使用纠错码来"提升"验证者发现无效承诺的概率。然后我们可以使用Merkle树承诺纠错多项式的评估。开放涉及向验证者提供Merkle认证路径。

Pedersen承诺使用离散对数问题。具体来说，给定群元素基(g0, g1, … gn)，我们可以承诺系数a0, … an，如C = g0 * a0 + g1 * a1 + … + g1 * an。我们可以将其与内积参数（超出本文范围）结合，生成基于内积参数的多项式承诺方案，具有开放和验证算法。

KZG具有非常小的证明大小，仅包含一个群元素。然而，这涉及可信设置，必须删除可信设置参数，否则任何人都可以伪造证明。FRI不需要可信设置且可能具有后量子安全性，但证明大小非常大。最后，Pedersen承诺和IPA不需要可信设置但需要线性验证时间。

还存在其他承诺方案，如Dory、Hyrax和Dark，但在实践中使用较少。

要了解更多关于这些承诺的信息，请查看我们的ZKDocs页面。

2. 哈希无处不在，但很少有人理解其内部工作原理。您能澄清流行结构（如MD、Sponge）并强调它们的区别吗？

大多数人熟悉的哈希函数，如MD5和SHA1，都是Merkle-Damgard结构。我们都熟悉和喜爱的keccak256函数是海绵结构。

在Merkle-Damgard结构中，任意长度的消息被解析为具有特定大小的块。

关键部分是压缩函数应用于每个块，使用前一个块作为下一个压缩函数的密钥（对于第一个块，我们使用IV或初始化向量代替）。Merkle-Damgard结构表明，如果压缩函数是抗碰撞的，整个哈希函数也将是抗碰撞的。

相比之下，海绵结构不使用压缩函数。海绵结构的核心包括两个阶段：一个"吸收"阶段，其中消息的部分与初始状态进行XOR运算，同时应用置换函数；然后是一个"挤压"阶段，其中输出的部分被提取并作为哈希输出。

值得注意的是，与Merkle-Damgard结构相比，海绵结构不易受长度扩展攻击，因为并非所有最终结果都用作哈希函数的输出。

3. 椭圆曲线密码学（ECC）更加神秘，被认为是密码学中的主要"黑盒"。存在许多陷阱和技术攻击。您能阐明一些对椭圆曲线的理论攻击，如Weil下降和MOV攻击吗？

ECC通常被视为密码学中复杂且有些神秘的部分，容易受到各种技术攻击。两个显著的理论攻击是Weil下降和MOV攻击。让我们稍微揭开这些攻击的神秘面纱。

本质上，ECC的安全性依赖于在椭圆曲线上解决某个数学问题（称为离散对数问题）的难度。标准椭圆曲线被特别选择是因为它们使这个问题难以破解。这就是为什么在实践中，Weil下降和MOV攻击通常对标准曲线不可行。

Weil下降攻击：这种方法涉及使用代数几何的概念，特别是一种称为Weil下降的技术。其思想是将离散对数问题从其原始形式在椭圆曲线（复杂的代数结构）上转换为在更简单的代数结构（如超椭圆曲线）上的类似问题。这种转换可以使用已知算法（如指数积分法）使问题更容易解决，但前提是原始椭圆曲线足够简单。标准化曲线通常足够复杂以抵抗这种攻击。

MOV攻击：这种攻击使用称为Weil配对的数学函数将椭圆曲线离散对数问题（ECDLP）转换为有限域中的离散对数问题，这是一个不同的数学设置。这种攻击的可行性取决于称为嵌入度的属性，它本质上衡量ECDLP可转换为有限域设置的程度。如果嵌入度低，MOV攻击可以通过将问题转移到存在更有效攻击方法的域来显著削弱安全性。然而，常用的椭圆曲线被选择具有高嵌入度，使得MOV攻击不实用。

总之，虽然这些对椭圆曲线的理论攻击听起来令人生畏，但在标准密码应用中仔细选择椭圆曲线通常会使这些攻击无效。

4. 随着技术的进步和量子计算机威胁的临近，人们已经努力创建后量子密码系统，如基于格的密码学和基于同源的密码学。您能概述这些系统吗？

基于格的密码学使用格（显然），这是一组基向量的整数线性组合。关于格有许多困难问题，如最短向量问题（给定基，找到格中最短的向量）和最近向量问题（给定格和格外的点p，找到格中离p最近的点）。下图取自EuroCrypt 2013的演示，说明了这一点：

有趣的是，可以证明大多数关于格的困难问题实际上与最短向量问题一样困难。

这些问题的已知算法，甚至是量子算法，都需要指数时间。我们可以利用这些困难问题来构建密码系统。

另一方面，基于同源的密码学涉及使用同源（显然），这是椭圆曲线之间的同态。我们基本上可以使用这些同源来创建标准椭圆曲线Diffie-Hellman密钥交换的后量子版本。在5000英尺的级别上，我们可以使用底层同源作为私钥，公共椭圆曲线的像作为公钥，而不是发送群元素作为公钥，随机整数作为私钥。如果Alice和Bob组合彼此的同源并计算曲线的j不变量，他们可以各自获得共享秘密，因为j不变量是一个数学函数，对于同构椭圆曲线是相同的。

然而，基于超奇异同源的Diffie-Helman密钥交换受到不需要量子计算机的密钥恢复攻击，因此不安全。目前正在进行更多研究，以开发实际上对量子计算机安全的基于同源的密钥交换算法。

5. Fiat-Shamir启发式在交互式预言证明领域广泛使用。关于这种启发式及其理论安全性，有哪些值得注意的地方？

Fiat-Shamir用于将交互式预言证明系统转换为非交互式证明系统。

顾名思义，这允许证明者证明计算结果，而不需要验证者在线。这是通过获取公共输入的哈希并将该哈希解释为随机输入来完成的。如果哈希函数是真正的随机预言——即如果哈希函数可以近似随机性——那么我们可以以这种方式模拟验证者的随机硬币。

有几个与安全相关的问题需要注意：

哈希必须包含所有公共输入；这个概念通常称为强Fiat-Shamir变换。弱Fiat-Shamir变换仅包含一个或有限数量输入的哈希，而强Fiat-Shamir变换涉及所有公共输入的哈希。正如您可以想象的，弱Fiat-Shamir变换是不安全的，因为它允许证明者伪造恶意证明。

即使使用强Fiat-Shamir变换，也可能出现更微妙的理论问题。协议必须具有"逐轮"安全性的概念，这大致意味着作弊证明者必须"一次性"幸运，因此不能研磨哈希直到收到"幸运"输入。这通常意味着使用Fiat-Shamir的逐轮协议需要更高的安全参数，如128位安全性。幸运的是，像SumCheck和Bulletproofs这样的系统被证明是逐轮安全的，因此可以安全地使用强Fiat-Shamir启发式来创建非交互式公共硬币协议。

Fiat-Shamir变换被广泛使用，在实现时必须极其谨慎，因为即使是微小的配置错误也可能允许恶意证明者伪造证明，这可能带来灾难性后果。要了解更多关于Fiat-Shamir以及潜在陷阱的信息，请参阅此概述博客文章以及另一篇关于Frozen Heart漏洞的博客文章。

6. PLONK交互式预言证明系统最近取得了显著进展。您能详细说明正在改进的内容以及如何改进吗？

交互式预言证明是SNARKs中的主要信息理论组件，允许证明者生成证明，以高概率发现虚假证明的方式说服验证者"知识"。

不同协议之间的关键因素是它们对证明者效率的改进以及增加的灵活性。例如，PLONK证明系统通常需要大量电路门，许多传统计算在电路内编码效率低下。此外，证明者必须将这些门编码为多项式，这需要大量计算时间。PLONK的变体旨在解决这些问题；这些包括：

• Turboplonk：支持具有两个以上输入的自定义门，而普通PLONK每个门只允许两个输入。使用Turboplonk可以为复杂算术操作（如位移和XOR）提供更多灵活性。
• UltraPLONK：支持查找表，证明者可以证明"电路困难"计算（如SHA-256）及其输入/输出对作为见证的一部分存在。更具体地说，对包含这些值的特定单元格启用的额外约束可以轻松验证其有效性。
• Hyperplonk：消除了对数论变换（NTT）的需求。PLONK证明系统通常需要大的乘法子群来计算NTT，您可以将其视为密码学友好的离散傅里叶变换版本。Hyperplonk改用sumcheck协议和多线性承诺，这消除了大部分证明者开销。

目前，大多数API支持UltraPLONK扩展（例如，对于Halo2和Plonky2），因为这支持自定义门和查找。Hyperplonk很有前途，但仍在微调中，在常见库中使用不多。PLONK IOP不断改进以更快并更好地支持递归计算，正在开发更多变体。

7. 我们经常听到zkEVMs和构建它们的项目，如Scroll、Polygon和zkSync。您能解释构建zkEVM涉及的各种设计决策吗？（类型1/2/3等）

您可以根据与以太坊的"完全兼容"程度来思考不同类型的zkEVMs，类型1最等效，类型4最不等效。

类型1 zkEVMs在各个方面等同于以太坊的执行和共识层，这保持了下游工具的兼容性，并允许轻松验证L1块。然而，它们带来了最多的证明者开销，因为EVM本身包含许多ZK不友好技术（keccak、Merkle树、堆栈）。目前，PSE团队和Taiko正在构建类型1 zkEVM。

类型2 zkEVMs旨在与EVM等效。类型2和类型1之间的区别在于EVM之外的对象，如状态trie和块验证，将表现不同，因此大多数以太坊客户端本身将不兼容此zkEVM。优点是更快的证明时间，而主要缺点是较少等效。例如，类型2 zkEVM可能使用修改的状态trie而不是以太坊使用的Merkle tries。Scroll团队和Polygon都旨在成为类型2 zkEVM，但在当前状态下，将它们指定为类型3更合适。

类型3 zkEVMs也具有更快的证明时间，但通过使用更少的等效性来实现。这些VM移除难以在电路中本地执行的EVM部分，如keccak256，并用ZK友好哈希函数（如Poseidon）替换它们。此外，它们可能使用不同的内存模型，而不是像EVM那样简单地基于堆栈；例如，它们可能使用寄存器。Linea是类型3 zkEVM的一个例子；然而，像Scroll和Polygon一样，他们正在改进以使其成为类型2。

最后一种zkEVM是类型4，它旨在采用像Solidity和Vyper这样的语言，并将其编译为ZK友好格式以生成证明。显然，这是最不等效的（以至于它甚至可能没有EVM兼容字节码），但权衡是证明生成最快。zkSync的zkEVM是类型4 zkEVM的一个例子。

8. 我们目前有zkEVMs在生产中，Scroll、zkSync和Polygon都有主网部署。我们可以对这些zkEVMs进行多少改进以解锁消费者级证明/验证？

尽管理论上构建zkEVM和创建高效证明的主要挑战可以通过plonkish算术化、查找表和增量可验证组合（IVC）的组合来解决，但在我们真正创建ZK证明承诺的大规模可扩展性之前，仍然存在许多工程挑战。当前在32核Intel Xeon Platinum CPU上生成128K Pedersen哈希的UltraPLONK证明的基准测试显示，证明时间相当快，仅需约三秒；然而，内存需求仍然非常高，约130 GB。可以进行许多可能的进一步优化：

使用更小的字段：现代CPU在64位字上操作，而SNARKs内的计算通常在椭圆曲线群上操作，这些群约为256位。这意味着电路内的字段元素必须拆分为多个limb，这会产生大量计算成本。通过使用像Goldilocks这样更小的字段并执行基于FRI的验证（参见"您能概述SNARKs中最常用的承诺方案吗？"），可以以更大的证明大小和更慢的验证为代价加速证明者计算。

硬件改进和并行化：许多FPGA和ASIC可用于优化SNARK生成。SNARK证明通常涉及大量哈希和椭圆曲线操作。事实上，约60%的证明生成包括多标量乘法（MSMs）。因此，使用为这些操作设计的专用硬件可以显著提高性能。此外，专用计算硬件也可以更高效地执行NTTs。ZK领域的许多团队，如Ingonyama，正尝试使用FPGA/GPU硬件加速来加速这些操作。此外，虽然电路合成的部分不能并行化，但像见证生成这样的事情可以并行完成，这进一步加速了证明生成。Matter Labs的Boojum就是这样一个SNARK证明系统。

最后，仍然有许多理论改进可以进一步加速证明生成和验证。除了进一步工作加速递归SNARK证明（如Goblin Plonk）外，像Lasso这样更快的查找参数也将导致改进的性能。椭圆曲线操作本身的算法可以优化。例如，通过曲线自同态和Barrett约简，标量乘法可以比标准的"双倍加"算法快得多。使用扭曲爱德华曲线而不是Weierstrass形式表示点也可以加速点加法。最后，像Binius这样的SNARKs使用二进制字段塔变得更硬件友好。

随着SNARK改进越来越先进，SNARKs很快在消费者级硬件上运行是现实的。未来，可能在智能手机上生成zkSNARK。

9. 您能讨论像Shamir秘密共享这样的秘密共享方案、它们的潜在用例以及您观察到的常见错误吗？

Shamir秘密共享（SSS）是一种在各种方之间拆分一组秘密的方法，使得一组方可以合作恢复秘密，但任何少于阈值的参与者无法学习任何信息。

Shamir秘密共享的主要思想使用任何p + 1个点唯一确定p次多项式的事实。通过使用拉格朗日插值，阈值参与者可以合作恢复共享秘密（在这种情况下，多项式的常数项）。可验证秘密共享扩展了SSS，并涉及发布对共享集的基于离散对数的承诺。秘密共享广泛用于像tECDSA这样的阈值签名和各种多方计算协议。

与所有密码方案一样，有一些需要注意的陷阱可能使SSS或Feldman的可验证秘密共享完全不安全：

• 无意中向参与者共享0点会泄露秘密。根据定义，因为0点是参与者必须合作恢复的秘密。然而，由于多项式是在有限域上定义的，必须注意不要生成任何模等价的共享为0。
• 确保共享之间的差不为0或模等价。为了重新计算共享秘密，使用拉格朗日插值，这涉及计算共享之间差的模逆。如果共享之间的差为0，则协议失败，因为0没有模逆。
• 当为可验证秘密共享创建承诺时，确保验证承诺多项式的次数（即生成方发送的系数数量）。恶意方可能发送比必要更多的系数，增加每个人的阈值。

10. 用于递归证明的折叠方案最近变得非常流行。您能大致总结一下它们的工作原理吗？

很高兴！折叠方案是增量可验证计算问题的一种解决方案。增量可验证计算（IVC）背后的问题是：给定函数F和初始输入v0，其中v_i = F^i(v0)，您能验证每个索引i处F的计算吗？一个具体示例是拥有EVM状态转换函数F和世界状态w0。IVC询问是否可能验证先前状态转换函数的执行，直到最终状态：

先前对IVC的方法涉及让证明