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

Sin7y

特邀专栏作者

2022-08-17 12:54

本文約2640字，閱讀全文需要約4分鐘

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

很高興，我們在2022年7月25日發布了OlaVM，一個EVM兼容的ZKVM方案。由於ZKEVM本身一直是個熱門的賽道，所以OlaVM一經發布，就很榮幸的受到了行業內大佬們的一些關注。

大佬(也是Daira Hopwood大佬(也是和和ECDSA和Schnorr簽名算法裡Hash的選擇問題，具體的表述如下圖所示：

Daira Hopwood一級標題Sinsemilla Hash和ECDSA和Schnorr一級標題

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需要注意的是：

需要注意的是：

a. 2nd-preimage resistance可以歸約為collision resistance，即collision resistance滿足，則2nd-preimage resistance必定滿足。

一級標題未必一級標題

2. 什麼是random oracle(RO)？

random oracle(RO)用以下模型來描述：

• 有一個黑盒子。盒子裡住著一個侏儒，還有一本大書和一些骰子。

• 我們可以向盒子裡輸入一些數據（任意比特序列）。

• 給定侏儒一些事先沒有看到的輸入，他用骰子在一些常規空間（oracle輸出空間）中均勻且隨機地生成一個新的輸出。侏儒還會在書中寫下輸入和新生成的輸出。

• 如果給定侏儒一個已經看到的輸入，他就用書來恢復他上次返回的輸出，並再次返回。

簡單來概括下RO的行為，假設輸入為x：

• 如果x 之前輸入過，則直接返回對應的H [x].

• 如果x 未曾輸入過，則RO會在完全隨機需要注意的是：

需要注意的是：

• 這裡的完全隨機意味著，連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?

一級標題

和On the security of ECDSA with additive key derivation and presignatures和On the Exact Security of Schnorr-Type Signatures in the Random Oracle Model一級標題

4. 關於Sinsemilla哈希函數?

Sinsemilla哈希函數是由Daira Hopwood 和Sean Bowe一起設計，底層依賴ECDLP(Elliptic Curve Discrete Logarithm Problem)。在固定長度的輸入下，Sinsemilla哈希函數滿足collision resistance，根據的Daira Hopwood的根據。

根據一級標題一級標題