比较两种用于多方计算和零知识证明的哈希函数
作者: Burcu Yıldız (Anoma - https://anoma.network/) 和 Mary Maller (以太坊基金会 - https://ethereum.foundation/)
总结:在我们的报告比较两种用于多方计算和零知识证明的哈希函数中,我们比较了用于多方计算(MPC)和零知识证明(ZKP)的哈希函数Poseidon和Hydra。我们的观察结果表明使用Hydra更加高效。
MPC和ZKP
零知识证明(ZKP)和MPC都是有用于隐私和完整性的先进密码学应用。在零知识证明中,单个参与方证明计算输出已正确计算,而不透露任何秘密输入值。在MPC中,多个参与方计算输出,而不向彼此透露任何秘密输入值。ZKP和MPC解决方案的联合使用在不同应用中很有前景,包括Anoma的私有求解协议。主要效率指标是ZKP的R1CS约束数量,以及MPC的轮数和乘法三元组数量,这些都根本取决于非线性操作的数量。但是,对于MPC和ZKP,非线性操作的确切依赖关系以及相应的优化是不同的。
哈希函数
密码学哈希函数是密码学中的关键构建块,被用于众多应用。哈希函数Poseidon广受青睐用于零知识应用(例如FileCoin、Dusk Network、LoopRing),并且是为此目的量身定制的。哈希函数Hydra被提出并优化用于MPC计算。Hydra在Eurocrypt 2023上发表,相比竞争对手具有更少的总轮数和传输数据。我们在报告中回答了以下问题:
针对零知识和MPC应用分别优化的哈希函数Poseidon和Hydra,在另一种应用中的表现如何?
我们的技术
我们对Poseidon和Hydra的比较包括理论和实验两个部分,目标是在Pallas曲线(255位素数域)上实现128位安全性。通过计算算法的乘法深度和乘法复杂度,我们理论上估计了哈希函数在ZKP中的效率,即R1CS约束数量;在MPC中的效率,即所需的轮数和乘法三元组数量。我们的实验结果包括MPC协议的基准测试,以获得总运行时间、交换数据量和每个参与方的CPU时间的估计。我们根据输出长度、参与方数量和Poseidon的参数(如果适用)以可视化的方式呈现结果。
此外,我们还研究了Poseidon和Hydra作为对称密钥加密的构建块。我们考虑了Poseidon的双重海绵认证加密框架和Hydra的流密码,如Hydra论文中所建议的。我们报告了与上述段落中描述的类似比较。
结果
我们观察到,对于我们关注的效率指标,Hydra通常优于Poseidon。当所需的摘要长度较长时,例如用作伪随机数生成器,Hydra特别高效。另一方面,Hydra仅限于某些输入长度,而Poseidon可接受各种输入长度。如果输入/输出长度是固定和已知的,Poseidon的各种参数可以优化性能;尽管Hydra仍然似乎更优。
当需要加密大量明文时,Hydra计算更加高效。然而,尽管Hydra论文中提到了一种方法,但目前还没有任何(理论或实际)基于Hydra的认证加密实现。我们对Poseidon的考虑已经是针对认证加密的。
欢迎读者查看我们的报告,了解更多关于哈希函数、我们的设置、结果和讨论(包括构建适用于MPC和ZKP应用的哈希函数的考虑)的详细信息。
