Is "Pinocchio zk-SNARK" a specific type of "zk-SNARK"? And if yes, what is difference?
Add a comment
|
2 Answers
Pinocchio is one of the early implementation of SNARK ( Succinct Non Interactive Arguments of Knowledge) without the aid of Probabilistic Checkable Proofs (PCP). In 2010, Groth constructed a Non Interactive Zero Knowledge (NIZK) argument in the common reference string (CRS) model. Interestingly, his argument does not use PCPs. In 2011, Lipmaa reduced the CRS size to quasi-linear, but with prover computation still quadratic. Rosario Gennaro, Craig Gentry, Bryan Parno and Mariana Raykova (GGPR) invented a new characterization of the NP complexity class, called Quadratic Span Programs (QSPs). This has helped in the construction of succinct arguments of NP-statements that are quick to construct and verify, much better than Probabilistically Checkable Proofs (PCPs).
In Pinocchio, the client creates a public evaluation key to describe her computation; this setup is proportional to evaluating the computation once. The worker then evaluates the computation on a particular input and uses the evaluation key to produce a proof of correctness. The proof is only constant size, regardless of the computation performed or the size of the inputs and outputs. Anyone can use a public verification key to check the proof. Pinocchio achieves strong asymptotic efficiency by refining the Quadratic Arithmetic Programs of GGPR.
Pinocchio was originally conceived as an efficient public verifiable computation (PVC) scheme. However it generalises to zero-knowledge proofs at a negligible cost over the base protocol. Thus Pinocchio toolchain became a reference for SNARK architecture. Pinocchio takes a high-level C program all the way through to a distributed set of executables that run the program in a verified fashion. It supports both arithmetic circuits, via Quadratic Arithmetic Programs, and Boolean circuits via Quadratic Span Programs.
Yes, Pinocchio is a practical zk-SNARK that allows a prover to perform cryptographically verifiable computations with verification effort potentially less than performing the computation itself. A recent propo- sal showed how to make Pinocchio adaptive (or “hash-and-prove”), i.e., to enable proofs with respect to computation-independent commitments. This enables computations to be chosen after the commitments have been produced, and for data to be shared between different computations in a flexible way. Unfortunately, this proposal is not zero-knowledge. In par- ticular, it cannot be combined with Trinocchio, a system in which Pinoc- chio is outsourced to three workers that do not learn the inputs thanks to multi-party computation (MPC).
