The “Pinocchio” protocol is I believe the first practical, usable implementation of a zk-Snark, a result that comes after a few decades of academic work carried out by a number of extremely brilliant people.
By working my way backward through the various citations and references, I will try to trace a possible timeline of the journey from what appear to be the first seeds of the idea all the way to the software in production on real systems today. My reconstruction is probably quite inaccurate and most certainly not complete; I will happily add more details if anyone feels like offering insight. In the meantime, I believe this can be a smooth introduction to the concept, so I think it’s worth a post.
The research threads that brought to this achievement, are rooted originally in the work on verifiable computation (i.e. the ability to give a proof of having performed a defined “program”) via probabilistic proofs (as in the example with the “snooker balls” in one of my first posts, we don’t get formal proof, but a probabilistic one). If we have to pick a “start year” (assuming that it makes sense to define a beginning with regards to research), we could choose 1985, with the publication of the “The Knowledge Complexity of Interactive Proof-System” paper (Goldwasser, Micali, Rackoff). In that paper, we can already find the concept of interactive proofs and “0 knowledge”. Then in the early 90’s there was a series of very promising progress with the introduction of Probabilistically Checkable Proofs, new complexity theory theorems, the first papers on efficient verifiers and verifying outsourced computation, ... very good stuff, but still just theory.
In 2007, we had a new important leap forward, with a paper that presented a prover for delegated computation that could run in polynomial time (Goldwasser, Kalai, Rothblum). Still just theory, but with a hint that all this could maybe become real one day. In 2010 another key paper introduced the concept of non-interactive verifiable computation (Gennaro, Gentry and Parno). Better and better, but still just theory.
From 2011 on, researchers started thinking that all this could be not just theory; finally in 2013 the “Pinocchio: Nearly Practical Verifiable Computation” (Parno, Howell, Gentry, Raykova) paper was out. In literature it is cited as [PHGR13]: and you can find that acronym in a lot of real software code. Pinocchio is a “built system for efficiently verifying general computations while relying only on cryptographic assumptions”; the paper defines and details all the elements to build a specific zk-Snark, and defines it as “nearly practical”. The “Succinct Non-Interactive Zero Knowledge for a von Neumann Architecture” (Ben-Sasson, Chiesa, Tromer, Virza) paper, first published at the end of 2013, showed that an implementation of Pinocchio was actually practical. In the B appendix of that last paper, "The PGHR zk-SNARK protocol", the authors presented the full protocol on one page, ready to be implemented.
A good overview of the "history" of zero-knowledge was offered by Jens Groth at the 2nd ZKPROOF WORKSHOP in Berkley, which I was fortunate enough to attend. His presentation is available here.
PS - the “Succinct Non-Interactive Zero Knowledge for a von Neumann Architecture” paper was modified and re-published in February 2019, to fix a mistake in the original paper, a mistake that could have potentially caused serious damages. More to come on this!