Our mission at Ulvetanna is to accelerate the computation of zk-SNARK computation, using a combination of hardware acceleration, high-performance software engineering, and algorithmic innovations. The team's work on Caulk+ is one such innovation which contributes to the state-of-the-art in prover-efficient cryptographic lookup arguments. Modern zk-SNARKs have seen dramatic performance improvments recently by incorporating lookup arguments — protocols that reduce the complexity of the ZK circuit by proving inclusion of some circuit values in a precomputed table. Our paper extends the work of Caulk, a new lookup argument which supports lookups into large tables. The key contribution of our work is replacing a complex subprotocol with a less expensive polynomial divisibility check. Consequently, we devise a dramatic simplification of the original work with improved asymptotic prover complexity that is independent of the table size!
The full article, Caulk+: Table-independent lookup arguments, is available on ePrint.
