Pigeon: A Space-Efficient zkSNARK with Optimal Proving Time

The Hong Kong University of Science and Technology
Department of Computer Science and Engineering


MPhil Thesis Defence


Title: "Pigeon: A Space-Efficient zkSNARK with Optimal Proving Time"

By

Mr. Christodoulos PAPPAS


Abstract:

We present Pigeon, the first space-efficient zkSNARK for the correct 
computation of layered data- parallel arithmetic circuits with asymptotically 
optimal prover time. More precisely, for any layered data-parallel arithmetic 
circuit C, Pigeon has proving complexity of O(|C|) field/group operations, 
proof size and verification time of O(√|C|) while the space complexity is O(|x| 
+ √|C| + Seval), where Seval << |C| is the space needed to evaluate the circuit. 
Pigeon is built upon a novel space- efficient sumcheck protocol for inner 
products that rely on folding schemes for sumcheck instances and achieves 
linear proving time-a logarithmic improvement over the state of the art. We 
then use it to instantiate a space-efficient variant of the GKR protocol. 
Finally, we compile our modified GKR using two space-efficient Polynomial 
commitment schemes. The first uses the Kopis scheme while the second relies on 
the Brakedown scheme along with additional optimizations concretely reducing 
its proof size. By doing so, we obtain two instantiations of Pigeon with 
different performance and security guarantees. In particular, the first has a 
small proof size and verification times, while the second enjoys a considerably 
faster prover and is post-quantum. Our experimental results for three use cases 
(arbitrary data parallel circuits, multiplication trees, batch SHA256 hashing) 
indicate Pigeon outperforms the prior state-of-the-art space-efficient SNARK 
for arithmetic circuits Gemini (Bootle et al., EUROCRYPT'22) by 4-128× in 
prover space and 5.6-27.6× in prover time. Even more interestingly, compared 
to standard GKR-based zkSNARKs, uses 32-1000× less space while having no more 
than 2× proving overhead.


Date:                   Wednesday, 21 August 2024

Time:                   2:00pm - 4:00pm

Venue:                  Room 3494
                        Lifts 25/26

Chairman:               Prof. Cunsheng DING

Committee Members:      Dr. Dimitris PAPADOPOULOS (Supervisor)
                        Dr. Amir GOHARSHADY