关于Sinsemilla哈希函数在OlaVM中的应用

快链头条
2022-08-17 20:54
新闻
3599

很高兴,我们在2022年7月25日发布了OlaVM,一个EVM兼容的ZKVM方案。由于ZKEVM本身一直是个热门的赛道,所以OlaVM一经发布,就很荣幸的受到了行业内大佬们的一些关注。

在这里,我们首先非常感谢Daira Hopwood大佬(也是Zcash协议的主要作者)针对OlaVM的设计提出的一些问题。其中,比较核心的一点是ECDSA和Schnorr签名算法里Hash的选择问题,具体的表述如下图所示:

关于Sinsemilla哈希函数在OlaVM中的应用

Daira Hopwood的意思可以简单理解为:Sinsemilla Hash的安全级别只有collision-resistant, 因此不能当做一个random oracle(RO);而在ECDSA和Schnorr签名算法中,为了足够的安全,需要要求这个Hash可以当做random oracle(RO)。为了能更好的理解,我们需要先了解一些概念。

1.cryptographic hash function (CHF)的安全属性有哪些?

根据论文 Cryptographic Hash-Function Basics里的定义可知,CHF对应的安全属性有以下3类:

• preimage-resistance — 基本上对于所有预先指定输出,要找到任何散列到该输出的输入,在计算上是不可行的,例如,当给定任意未知输入的 y 时,要找到使 h(x')=y 的所有原像(preimage) x'。

 2nd-preimage resistance — 要找到与任何指定输入具有相同输出的任何第二输入,在计算上是不可行的,例如,给定x,要找到一个第二原像 x' = x,使 h(x') = h(x)。

• collision resistance — 要找到任意两个散列到相同输出的不同输入,在计算上是不可行的,例如,使h(x') = h(x)。

需要注意的是:

a. 2nd-preimage resistance可以归约为collision resistance, 即collision resistance满足,则2nd-preimage resistance必定满足。

b. preimage-resistance不可以归约为collision resistance, 即collision resistance满足,则preimage resistance未必满足。

2. 什么是random oracle(RO)?

random oracle(RO)用以下模型来描述:

• 有一个黑盒子。盒子里住着一个侏儒,还有一本大书和一些骰子。

• 我们可以向盒子里输入一些数据(任意比特序列)。

• 给定侏儒一些事先没有看到的输入,他用骰子在一些常规空间(oracle输出空间)中均匀且随机地生成一个新的输出。侏儒还会在书中写下输入和新生成的输出。

• 如果给定侏儒一个已经看到的输入, 他就用书来恢复他上次返回的输出,并再次返回。

简单来概括下RO的行为,假设输入为 x:

• 如果 x 之前输入过,则直接返回对应的 H [x].

• 如果 x 未曾输入过,则RO会在完全随机的在值域里生成一个由0,1组成的字符串。

需要注意的是:

• 这里的完全随机意味着,连RO自己都不知道最终会是一个什么值,它是没有规则可循的,这是和Hash的主要区别,任何Hash都是有自己的计算规则的。

但是在现实的世界中,实现一个真正的RO是很困难的;因此,我们需要为RO寻找一个潜在候选者,需要尽可能的使得输出看起来是随机的。Hash函数是一个不错的选择,一个安全的Hash函数需要满足preimage-resistance、2nd-preimage resistance、collision resistance。一个可以当做RO的Hash是肯定要满足这三个属性的,但是满足这三个属性的Hash不一定就可以当做RO;它们之间是一种必要不充分关系。更多的细节可以参考What is the "Random Oracle Model" and why is it controversial?

3. Hash在ECDSA和Schnorr签名算中的要求?

在论文On the security of ECDSA with additive key derivation and presignatures和On the Exact Security of Schnorr-Type Signatures in the Random Oracle Model中提到,ECDSA和Schnorr签名算法里的Hash函数都需要可以被认为是RO,才是安全的。根据前面的描述,则这个Hash需要满足CHF的所有安全属性preimage-resistance、2nd-preimage resistance、collision resistance。

关于Sinsemilla哈希函数在OlaVM中的应用

关于Sinsemilla哈希函数在OlaVM中的应用

4. 关于Sinsemilla哈希函数?

Sinsemilla哈希函数是由Daira Hopwood 和 Sean Bowe 一起设计,底层依赖ECDLP(Elliptic Curve Discrete Logarithm Problem)。在固定长度的输入下,Sinsemilla哈希函数满足collision resistance,不满足preimage resistant属性,原因可以参考Daira Hopwood回答

根据Zcash协议说明书,设计Sinsemilla哈希函数的初衷是为了在零知识证明算法Halo2的执行过程中,充分利用Lookup-friendly的优势,来提高Halo2的执行效率;因此,Sinsemilla哈希函数是一个Lookup-friendly的哈希函数,它更适合用于承诺的计算和Merkle tree root的计算。

关于Sinsemilla哈希函数在OlaVM中的应用

5. 总结

再次感谢Daira Hopwood的指导,让我们对cryptographic hash function (CHF)的使用有了更深的认知。我们将继续广泛听取意见,在高效性和安全性方面对设计方案进行持续优化。

Sinsemilla哈希函数会仍然用于Olavm设计中的其他合适模块;签名部分的Hash函数,我们将会在安全的哈希函数中,择优选择,比如Poseidon哈希函数、Reinforced Concrete哈希函数等。

关于我们

Sin7y成立于2021年,由顶尖的区块链开发者组成。我们既是项目孵化器也是区块链技术研究团队,探索EVM、Layer2跨链隐私计算、自主支付解决方案等最重要和最前沿的技术。

微信公众号:Sin7Y

GitHub | Twitter | Telegram | MediumMirror | HackMD | HackerNoon

温馨提示:
快链头条登载此文本着传递更多信息的缘由,并不代表赞同其观点或证实其描述。
文章内容仅供参考,不构成投资建议。投资者据此操作,风险自担。
提示:投资有风险,入市须谨慎。本资讯不作为投资理财建议。