密码学专家解答10大核心技术问题

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

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

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

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

最常见的生产环境承诺方案包括：

• KZG（Kate-Zaverucha-Goldberg），用于EIP 4844中的danksharding
• FRI（快速Reed-Solomon交互式Oracle邻近证明），用于STARKs
• Pedersen承诺，用于Bulletproofs等证明系统（被Monero和Zcash使用）

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

2. 哈希函数的流行构造及其区别？

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

在Merkle-Damgard构造中，任意长度消息被解析为特定大小的块。关键部分是压缩函数应用于每个块，使用前一个块作为下一个压缩函数的密钥（对于第一个块，使用IV或初始化向量）。如果压缩函数具有抗碰撞性，整个哈希函数也将具有抗碰撞性。

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

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

3. 椭圆曲线密码学的理论攻击

ECC通常被视为密码学中复杂且有些神秘的部分，容易受到各种技术攻击。两个著名的理论攻击是Weil下降攻击和MOV攻击。

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

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

4. 后量子密码系统概述

基于格的密码学使用格，这些格是基向量集合的整数线性组合。关于格存在许多难题，例如最短向量问题（给定基，找到格中最短向量）和最近向量问题（给定格和格外点p，找到格中离p最近的点）。已知这些问题的算法，即使是量子算法，也需要指数时间。我们可以利用这些难题构建密码系统。

基于同源性的密码学涉及使用同源，即椭圆曲线之间的同态。我们可以使用这些同源创建标准椭圆曲线Diffie-Hellman密钥交换的后量子版本。在高层面上，我们可以使用底层同源作为私钥，公共椭圆曲线的图像作为公钥，而不是发送群元素作为公钥和随机整数作为私钥。

5. Fiat-Shamir启发式方法的安全注意事项

Fiat-Shamir用于将交互式Oracle证明系统转换为非交互式证明系统。这允许证明者证明计算结果而不需要验证者在线。这是通过获取公共输入的哈希并将该哈希解释为随机输入来实现的。

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

• 哈希必须包含所有公共输入；这个概念通常称为强Fiat-Shamir变换
• 即使使用强Fiat-Shamir变换，也可能出现更微妙的理论问题
• 协议必须具有"逐轮"安全的概念

6. PLONK交互式Oracle证明系统的改进

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

不同协议之间的关键因素是对证明者效率的改进以及增加的灵活性。PLONK变体包括：

• Turboplonk：支持超过两个输入的自定义门
• UltraPLONK：支持查找表
• Hyperplonk：消除对数论变换（NTT）的需求

7. zkEVM的设计决策

zkEVM的类型基于与以太坊的"完全兼容"程度：

• 类型1：与以太坊的执行和共识层完全等效
• 类型2：EVM等效，但外部对象行为不同
• 类型3：使用更少的等效性，移除ZK不友好的部分
• 类型4：将Solidity等语言编译为ZK友好格式

8. zkEVM的进一步改进

虽然理论上构建zkEVM和创建高效证明的主要挑战可以通过plonkish算术化、查找表和增量可验证组合（IVC）的组合来解决，但在真正实现ZK证明承诺的大规模可扩展性之前，仍存在许多工程挑战。

可能的进一步优化包括：

• 使用更小的字段
• 硬件改进和并行化
• 理论改进

9. 秘密共享方案及常见错误

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

需要注意的几个安全问题：

• 无意中向参与者共享0点会泄露秘密
• 确保共享之间的差值不为0或模等价
• 创建可验证秘密共享承诺时，确保验证承诺多项式的次数

10. 递归证明的折叠方案

折叠方案是增量可验证计算问题的一种解决方案。折叠方案起源于Nova，引入了一个新想法：验证者不是每次调用F时验证SNARK，而是将当前实例"折叠"到累加器中。在执行结束时，验证电路只需检查累加器的一致性。

对折叠方案已经进行了几次更新和改进。例如，Sangria方案将折叠推广到Plonkish算术化而不仅仅是R1CS。HyperNova将Nova推广到可定制约束系统（CCS），这是一个可以表达Plonkish和AIR算术化的更通用约束系统。

迈向更好的密码学安全

密码学不断发展，理论与实践之间的差距越来越小。更多有趣的密码协议和新颖实现随处可见，包括多方计算、增量可验证组合、全同态加密以及其间的一切。