比較兩種用於多方計算和零知識證明的雜湊函式
作者: 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應用的雜湊函式的考慮)的詳細資訊。
