很高兴，我们在2022年7月25日发布了OlaVM，一个EVM兼容的ZKVM方案。由于ZKEVM本身一直是个热门的赛道，所以OlaVM一经发布，就很荣幸的受到了行业内大佬们的一些关注。
在这里，我们首先非常感谢Daira Hopwood大佬(也是Zcash协议的主要作者)针对OlaVM的设计提出的一些问题。其中，比较核心的一点是ECDSA和Schnorr签名算法里Hash的选择问题，具体的表述如下图所示：
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。
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的计算。
5. 总结
再次感谢Daira Hopwood的指导，让我们对cryptographic hash function (CHF)的使用有了更深的认知。我们将继续广泛听取意见，在高效性和安全性方面对设计方案进行持续优化。
Sinsemilla哈希函数会仍然用于Olavm设计中的其他合适模块；签名部分的Hash函数，我们将会在安全的哈希函数中，择优选择，比如Poseidon哈希函数、Reinforced Concrete哈希函数等。
引用
1. OlaVM：https://ethresear.ch/t/whitepaper-olavm-an-ethereum-compatible-zkvm/13144
2. Daira Hopwood：https://twitter.com/feministPLT
3. Zcash协议：https://zips.z.cash/protocol/protocol.pdf
4. ECDSA：https://en.wikipedia.org/wiki/Elliptic_Curve_Digital_Signature_Algorithm
5. Schnorr：https://en.wikipedia.org/wiki/Schnorr_signature
6. Sinsemilla Hash：https://zips.z.cash/protocol/protocol.pdf
7. Cryptographic Hash-Function Basics：https://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=C7364E9082B2726A10E1C712B476C82A?doi=10.1.1.3.6200&rep=rep1&type=pdf
8. random oracle(RO)：https://en.wikipedia.org/wiki/Random_oracle
9. What is the "Random Oracle Model" and why is it controversial：https://crypto.stackexchange.com/questions/879/what-is-the-random-oracle-model-and-why-is-it-controversial
10. On the security of ECDSA with additive key derivation and presignatures：https://www.shoup.net/papers/2021-1330.pdf
11. On the Exact Security of Schnorr-Type Signatures in the Random Oracle Mode：https://eprint.iacr.org/2012/029.pdf
12. ECDLP(Elliptic Curve Discrete Logarithm Problem)：https://link.springer.com/referenceworkentry/10.1007/978-1-4419-5906-5_246
13. 回答：https://twitter.com/feministPLT/status/1551856467145269249
14. Poseidon：https://eprint.iacr.org/2019/458.pdf
15. Reinforced Concrete：https://eprint.iacr.org/2021/1038.pdf
关于我们
Sin7Y成立于2021年，由顶尖的区块链开发者和密码学工程师组成。我们既是项目孵化器也是区块链技术研究团队，探索EVM、Layer2、跨链、隐私计算、自主支付解决方案等最重要和最前沿的技术。
微信公众号：Sin7Y
GitHub：Sin7Y
Twitter：@Sin7Y_Labs
Medium：Sin7Y
Mirror：Sin7Y
HackMD：Sin7Y
HackerNoon：Sin7Y
Email：contact@sin7y.org
APP 
