zkSnarks - why isn't PCD more widely used?

Question

I've been reading the paper Scalable Zero Knowledge from Cycles of Elliptic Curves, which elegantly solves (what seems to me) the main problem with zkSnarks; namely that performing non-trivial computations requires building enormous arithmetic circuits. The authors do this by showing how to compose verified computations via circuits that verify the proofs generated by other circuits.

My question is why this technique doesn't appear to be getting much use. Is the overhead from the proof-verifying circuit the main reason? I understand that vnTinyRam (the verifiable simulated CPU they introduce in the paper referenced) executes instructions very slowly, but is this because of the generality of the simulated CPU or is the overhead inherent in the PCD approach?

Answer 1

There are two types of overhead in PCD systems:

1. Overhead of proof verification: Computing the pairings necessary to verify prior proofs is expensive, and adds overhead unrelated to the statement you're trying to prove.
2. Overhead of predicates: In the Scalable SNARKs paper, each recursion level verifies the execution of the vnTimyRAM CPU. This involves verifying the CPU execution itself, as well as authenticating that the memory accessed during this step is correct. Checking CPU execution is cheap; it requires roughly a thousand gates. Memory checking, however, is very expensive; each access requires verifying a Merkle tree path. While the authors try to mitigate via the efficient Ajtai hash function, the overhead due to this check is still the largest in the circuit.

Together, these overheads are much more expensive per cycle than other approaches for verifying RAM computations; the primary reason to use recursive SNARKs is for the lower memory consumption.