關於Sinsemilla哈希函數在OlaVM中的應用

Sin7Y ｜2022-08-17 18:29

本文回應了Zcash協議的主要作者Daira Hopwood針對OlaVM提出的幾點問題，同時介紹了Sinsemilla 哈希函數的設計思想及其在OlaVM 中的應用。

很高興，我們在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)。

• c ollision 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中的應用

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哈希函數等。

引用

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