現代零知識查找論證的比較性能分析

Abstract

摘要 零知識證明 (Zero-knowledge proofs, ZKP) 是區塊鏈擴展性與隱私保護的關鍵技術，尤其在 ZK rollup 解決方案中扮演核心角色，其透過將大量計算轉移至鏈下，有效提升交易吞吐量。然而，在這些系統中證明複雜的運算（例如虛擬機器的單個操作碼）仍然是主要的性能瓶頸。為此，查找論證 (Lookup Argument) 已成為一項關鍵的最佳化技術，它允許計算步驟的有效性可以根據預定義的表格進行高效驗證，從而避免了成本高昂的算術化過程。 儘管現存多種查找論證協定——包含 Plookup、Caulk、Baloo、CQ、Lasso 與 LogupGKR——各自具備不同的理論複雜度，但市場上始終缺乏一份全面性的實證效能比較，以指導開發者在實際應用中的選擇。 本論文對該領域作出四項關鍵貢獻：首先，我們增強並擴展了一個統一的 Rust 基準測試框架，提供多線性與單變數多項式版本，為未來查找論證研究奠定標準化基礎。其次，我們對六個主流協議進行了廣泛的基準測試，系統性地評估了在不同表格大小與查找密度下的證明者時間、驗證者時間、證明大小及預處理成本。第三，我們發現並解釋了 Lasso 的證明大小在 $K=12$ 時反直覺地減少的現象，揭示了均勻 Limb 分解 (uniform limb decomposition) 能在多項式承諾方案中實現更高效的批次處理。第四，我們確定了最佳的混合表格查找策略：小表格應使用 LogUp GKR，而大表格則受益於 Lasso 的分解方法。 研究結果從實證角度驗證了查找論證的技術演化路徑：從 Plookup 對表格大小的線性依賴 (O(N))，到 Caulk 雖然解決了前者問題卻引入了查找數量的平方級瓶頸 (O(n^2))，再到 Baloo 與 CQ 成功將其提升至準線性效率。更重要的是，本研究揭示了 Lasso 與 LogupGKR 等現代協議實現了性能上的典範移轉 (paradigm shift)，其證明者時間不僅比前代協議快上數個數量級，且在測試範圍內幾乎不受表格大小與查找數量的影響。 本論文的結論指出，最佳查找協議的選擇並非絕對，而是一個高度依賴於應用場景的工程決策，涉及在證明者時間、驗證成本、證明大小與預處理開銷之間的多維度權衡。我們提供的實證數據，成功地彌合了漸進理論與現實性能之間的鴻溝，為下一代零知識證明系統的開發者提供了關鍵且實用的選型指南。

Abstract Zero-knowledge proofs (ZKPs) are foundational to blockchain scalability and privacy, particularly in ZK-rollups, which enhance transaction throughput by offloading computation from the main chain. However, proving complex operations within these systems, such as individual virtual machine opcodes, remains a significant performance bottleneck. Lookup arguments have emerged as a critical optimization, enabling the efficient verification of computational steps against pre-defined tables, thereby avoiding costly arithmetization. While a proliferation of lookup protocols—including Plookup, Caulk, Baloo, CQ, Lasso, and LogupGKR—offer diverse theoretical complexities, a comprehensive empirical comparison to guide practical implementation has been lacking. This thesis makes four key contributions to the field: First, we enhanced and extended a unified Rust-based benchmarking framework that provides both multilinear and univariate polynomial versions, creating a standardized foundation for future lookup argument research. Second, we conducted an extensive benchmark of six prominent protocols, systematically evaluating prover time, verifier time, proof size, and preprocessing costs under varying table sizes and lookup densities. Third, we discovered and explained why Lasso's proof size counter-intuitively decreases at $K=12$, revealing that uniform limb decomposition enables more efficient batch processing in the Polynomial Commitment Scheme. Fourth, we identified an optimal hybrid table lookup strategy where small tables should use LogUp GKR while large tables benefit from Lasso's decomposition method. Our results empirically validate the theoretical evolution of these protocols, charting the progression from Plookup's table-size dependency (O(N)) and Caulk's lookup-count bottleneck (O(n^2)) to the quasi-linear efficiency of Baloo and CQ. Furthermore, we demonstrate that modern protocols like Lasso and LogupGKR achieve a paradigm shift in performance, offering prover times that are orders of magnitude faster and largely independent of table and lookup size within the tested ranges. This study concludes that the optimal choice of a lookup protocol is a highly context-dependent engineering decision, involving trade-offs between prover time, verification cost, proof size, and preprocessing overhead. The empirical data herein provides a crucial, practical guide for developers, bridging the gap between asymptotic theory and real-world performance to inform protocol selection in next-generation ZK-based systems.