基於 QAP 的 zkSnark 的證明者成本
在 CGPR（連結到論文）第 3.5 節中，提到證明者的成本是 $ O(|C| \log(|C|)) $ ，給定電路的大小是 $ |C| $ .
在我看來，生成的 QAP 中的多項式次數應該是 $ O(|C|) $ . 證明者的成本不是 $ O(|C|) $ ? 我在這裡錯過了一些步驟嗎？
關鍵是他們在那裡使用了通用電路：
當我們為電路 SAT 構造一個 SNARK 時，我們使用一個通用電路的 QSP ，它有大小 $ O(|C| \log |C|) $ 在哪裡 $ |C| $ 是可滿足性問題中電路的最大尺寸。
通用電路是可以計算任何其他電路的電路。這種概括是額外的對數因子出現的地方。這在第 3 節的開頭進行了解釋：
要直接與 Groth 進行比較，我們可以處理 $ u $ 通過構造自適應選擇電路 $ R $
$$ (a relation) $$從通用電路。在這種情況下，電路計算的大小 $ R $ 可能大於 $ |u| $ 通過一個對數因子，這相應地將 CRS 大小和證明者計算增加到 $ \tilde{O}(|u|) $ . 如果 $ u $ …可以非自適應地選擇，我們的方案變得更有效率。
這 $ \tilde{O} $ 符號隱藏對數因子。最後他們提到知道具體的電路 $ u $ 會更有效率 - 這就是你的想法。自適應穩健性的原因是因為這更正確地模擬了協議在實際情況中的使用方式 - 通常您會期望證明者在開始證明之前看到 CRS，因此他們可以選擇他們的陳述（可能是錯誤的）試圖基於 CRS （自適應地）證明。
本文解釋了一種有效的通用電路結構，並解釋了這種電路在預備階段是如何工作的（例如，參見第 4-7 頁）。直覺地說，引入對數因子是因為這些電路往往是遞歸建構的，每個子問題的大小大約是一半，所以我們在處理二叉樹時得到了通常的對數因子。為了更好地解釋，我認為論文本身是最好的閱讀材料。