計算 zk-SNARK 證明的複雜性

免責聲明：我沒有密碼學背景，我所問的一切都是我從最近幾天瘋狂閱讀這個主題中學到的。任何幫助深表感謝。

問：生成 zkSNARK 證明和驗證它的計算複雜度是多少？

具體來說，生成和驗證證明涉及多少雙線性對、曲線點加法和標量乘法？這些與系統中的約束數量呈線性關係嗎？

在這裡，我可以看到每個驗證都需要驗證者計算 $ 11 $ 曲線配對， $ 3*m $ 標量乘法，和 $ 3(m+1) $ 曲線點添加。首先，我的理解正確嗎？二、什麼是 $ m $ ? 那是約束的數量嗎？第三，如果我知道約束的數量，我如何類似地計算證明者必須計算的配對、加法和乘法的數量？

它取決於使用的​​協議。最後一個效率更高的是Groth16，它在其證明中僅使用 3 個曲線點。您可以在 Groth 論文的表 2 中看到密鑰的大小和證明。配對的計算複雜度取決於使用什麼曲線。一般來說，ZoKrates/Ethereum 和 ZCash 使用 bn256 曲線參數，並且在它們的包中使用的配對算法（至少在golang 中）是 miller ate 配對的算法 1。

你看 zk-SNARK 是各種工作的融合，它的複雜性取決於每天都在發展的實現。

引用自：https://crypto.stackexchange.com/questions/76393