What are ZK-SNARKs?

SNARKs have gained considerable attention recently due to their broad utility in areas such as blockchain scalability, identity mechanisms, verifiable machine learning, and fighting against misinformation and fake news. We see new developments daily, but SNARKS have been around for a long time.

SNARKs allow one party, the prover, to prove to another, the verifier, that a given computation was computed correctly.

ZK-proofs are not a recent invention.

The definitions, foundations, important theorems, and even key protocols were established as early as the mid-1980s.

Some of the fundamental ideas that form the basis of modern SNARKs were proposed in the 1990s (Sumcheck), and 2000s (GKR).

However, their widespread adoption was hindered by the lack of a compelling use case (given the less developed state of the internet in the 1990s) and the significant computational power they required.

ZK-Proofs were introduced in a paper by Goldwasser, Micali, and Rackoff, which detailed the concepts of completeness, soundness, and zero-knowledge, and provided constructions for quadratic residuosity and non-residuosity; the foundations for future developments in the field.

In 1991, Babai, Fortnow, Lewin, and Szegedy published a paper entitled Checking Computations in Polylogarithmic Time. They presented a protocol in which “one PC can monitor the operation of a herd of supercomputers with powerful but unreliable software and untested hardware.”

In 2010, Kate, Zaverucha, and Goldberg introduced a commitment scheme for polynomials using a bilinear pairing group. The commitment consists of a single group element, and the committer can efficiently open to any correct evaluation of the polynomial.

Moreover, due to batching techniques, the opening can be done to several evaluations. KZG commitments provided one of the basic building blocks for several efficient SNARKs.

The first practical schemes for rather general computations started in 2014 with Pinocchio.

Pairing-friendly elliptic curves provided the first efficient constructions, with constant-sized proofs and verification linear in the size of the public input. However, these constructions relied on trusted setups, which were application-specific.

All proof systems come with advantages and disadvantages:

• Hash-based vs. elliptic curve-based proof systems.

• Post-quantum secure vs non-quantum secure systems.

• Large fields vs small fields.

• Trusted setup vs transparent.

• Constant sized vs sublinear proofs.

STARKs and Cairo-VM show the power of proving general computations run on top of a VM. Several teams such as Risc0, Polygon, SuccinctLabs, and a16z, have worked towards the development of general zkvms, where one can prove code written in a higher-level language such as Rust.

This makes writing provable applications much easier (since we need to write the code of the application without a lot of the earlier technical difficulties, reducing development and go-to-market time. Proving power has increased, while memory use has decreased in modern provers.

We expect a lot of improvements in provers; however, we will still have to verify the proofs on-chain, and this will be the main bottleneck for verifiable applications to be widely used.

Luckily, the future appears to be Aligned.

Want to see more on the origins of proof systems?

Check out this video by one of the authors of the original paper, Shafi Goldwasser.

https://youtu.be/uchjTIlPzFo?si=ybIJZ1lgQ4jf3sl2

If you want to learn more about Aligned and how we are accelerating Ethereum, read our whitepaper.

Stay tuned:  🐦 Twitter | 🗨️ Telegram | 👾 Discord | 🌐 Website | 📝 Manifesto