Halo2 prover time

There’s been lot of speculation and discussion around how Halo2 would be used in zcash. I wanted to ask a more fundamental question.

At a high level, the prover time in Halo2 is same as (probably worse than) bulletproofs (note I’m only focusing on prover time, not verifier time or proof sizes). This is because the prover has to prove one inner product instance of size bigger than circuit size. Bulletproofs are known to be very slow (orders of magnitude) compared to efficient SNARKs such as Groth16 in terms of prover time because the prover has to do expensive exponentiations in each round of the bulletproof proof generation.

If I’m reading graphs correctly, I think this already shows up in Halo paper where generating a proof takes ~1600 seconds for a million gate circuit whereas similar proof generation for Groth takes 50-60 seconds or less.

So I’m confused how this is a better choice than Groth16? I get the absence of trusted setup, and I get that PLONK custom gates save some (maybe 2-3x?), but this still seems too expensive to make zcash more usable or cheap enough for mobile devices to create transactions.

Can someone explain why this is not an issue?

Beyond this, I’m also not sure how such proofs will get aggregated so that block verifiers don’t have to incur extremely slow verification times of halo/bulletproofs.

7 Likes

(I :heart: powers of tau, literally like the coolest exercise ever and I have always opposed the “compromised ceremony” detractors. It was great but I degress. We move forward and if it doesn’t work then we have something that does on the side and thats not bad)

1 Like