Exploring the Power of SNARKs: Privacy, Efficiency, and Applications in Modern Computing

Lecture 2.2

Structure:

Introduction

Arithmetic Circuits and SNARKs

Types of SNARK Systems

Setup Procedures for SNARKs

Proof systems

Knowledge soundness

Conclusion

Introduction:

Arithmetic circuits are essential building blocks for defining SNARKs, which are succinct, non-interactive arguments of knowledge. These circuits are directed acyclic graphs that perform various polynomial-time computations, such as computing hash functions and verifying digital signatures. SNARKs provide a way to prove the correctness of a computation without revealing the inputs, ensuring both privacy and efficiency. There are different types of SNARK systems, each with its own properties and trade-offs regarding proof size, verifier time, and setup procedure.

Arithmetic Circuit:

An arithmetic circuit is a computation model used for defining SNARKs. It is a directed acyclic graph where the inputs are labeled by variables (e.g., X1, X2) and the inner nodes are labeled by arithmetic operations (+, -, *). An arithmetic circuit computes an n-variate polynomial and has a specific evaluation method.

Examples of Interesting Arithmetic Circuits:

Arithmetic circuits can perform polynomial-time computations. Examples include computing hash functions like SHA-256 and verifying digital signatures. The size of the circuit (number of gates) depends on the complexity of the computation.

Structured vs Unstructured Circuits:

Structured circuits are built in layers, with a fixed arithmetic circuit repeated multiple times. Unstructured circuits have wires that can go anywhere. Some SNARK techniques apply to both structured and unstructured circuits, while others apply only to structured circuits.

NARK: Non-Interactive Argument of Knowledge:

A NARK is applied to an arithmetic circuit and consists of a pre-processing algorithm (setup algorithm) that outputs public parameters for the prover (PP) and verifier (VP). The prover generates a proof that the circuit output is zero, and the verifier checks the proof. A NARK has to satisfy completeness (the verifier always accepts valid proofs), knowledge soundness (the prover knows a valid witness), and optionally zero-knowledge (the proof reveals nothing about the witness).

SNARK: Succinct Argument of Knowledge:

A SNARK is a NARK with additional requirements: the proof must be short (sublinear in the size of the witness) and fast to verify (sublinear in the size of the circuit). In practice, SNARKs are strongly succinct, meaning the proof size and verification time are logarithmic in the size of the circuit. The pre-processing step is essential, as it generates a summary of the circuit for the verifier, enabling the verifier to check the proof without knowing the entire circuit.

zk-SNARK: A zk-SNARK is a SNARK that is also zero-knowledge, meaning the proof does not reveal any information about the witness.

The trivial SNARK is not a SNARK

The trivial SNARK, where the prover sends the witness to the verifier as proof, is not a SNARK for three reasons:

• The witness may be long, and we want a short proof.
• Computing C(x,w) may be hard since the circuit C could be complex, and a fast verifier is crucial.
• We might want to keep the witness secret, but the trivial SNARK reveals it to the verifier.

Preprocessing step

The preprocessing step generates parameters for the prover and verifier. There are three types of setup procedures:

• Trusted setup per circuit: Requires a fresh setup for every circuit and secret random bits must be kept secret from the prover.
• Trusted but universal setup: Consists of a one-time setup (S init) and a deterministic algorithm (S index) to generate parameters for multiple circuits.
• Transparent setup: No secret data is required, and anyone can verify the setup ran correctly.

Proof systems

Four widely deployed SNARK systems are:

• Groth'16: Short 200-byte proofs, constant verifier time, but requires a trusted setup per circuit.
• Plonk and Marlin: Slightly longer 400-byte proofs, constant verifier time, and universal trusted setup.
• Bulletproofs: Logarithmic proof size, linear verifier time, and transparent setup.
• Starks: Longer proofs, logarithmic verifier time, and transparent setup.

Knowledge soundness

Knowledge soundness means that if the verifier accepts a proof, the prover knows a witness W. This is formally defined using an extraction algorithm that interacts with a malicious prover (adversary A) and extracts a witness from it with roughly the same probability that the adversary convinces the verifier.

Conclusion:

In summary, SNARKs provide an efficient way to prove the correctness of computations performed by arithmetic circuits while preserving the privacy of inputs. They have found applications in blockchain technology, privacy-preserving protocols, and more. Different SNARK systems offer various properties and trade-offs, making them suitable for different use cases. The key properties of SNARKs, such as knowledge soundness and zero-knowledge, ensure that they provide a secure and reliable way to verify proofs without revealing sensitive information. As technology advances, the development of more efficient and secure SNARK systems will continue to play a crucial role in enhancing privacy and efficiency in various computational settings.

P.S.

I believe that constructive feedback is essential for personal and professional growth, and I welcome any comments or thoughts you may have regarding my article. Your feedback will help me improve my writing and provide better content for you in the future.

If you found this article valuable, I encourage you to follow me on LinkedIn to stay updated on my latest posts. Your support and engagement mean a lot to me, and I am grateful for every like, comment, and share.

Thank you for your time, and I look forward to connecting with you.