A side note on my brief hiatus:
Hello, fren. It's been a while since my last article came out. I've found it quite challenging over the past month to put any of my thoughts or the information I'm attempting to convey into words. The days all merge seamlessly into one, and the fifteen concurrently running trains of thought in my head don't allow me to form coherent sentences.
I've been fixated on the best way to communicate the complex information I want to convey. Edit this, edit that, or perhaps eliminate it entirely, until I'm staring at a blank screen. Wondering if what you seek is present in what I write.
I've finally realized that no matter how much I obsess over writing a good article, the result can constantly be improved upon. There will always be the occasional error, content that’s too detailed or too superficial, or poorly framed sentences. I'm going to write again like I used to, write because I want to.
I didn't expect to be appreciated when I first began posting, but I got lucky. Some people liked what I wrote and were kind enough to get in touch and tell me that. That's the kind of positive reinforcement that keeps people going- it's what helps me keep going. I began writing with the hope that my articles might help someone, at some point in time.
Obsessing over improvement to the point where I feel I'm left with nothing to post defeats that purpose. After all, done is better than perfect. I'm going to stop being so picky and since I have a bunch of drafts right now, the plan is just to post more often. You can expect 2-3 articles each week. While I don't have a laundry list of what I want to write about, there are a couple of topics I'm interested in. A lot of amazing things are being developed right now, with loads to be fascinated with.
So, stu is back, and back for good. I'm grateful to have an audience of any size that likes to read what I write, so thank you for being here.
The ongoing ZK series, so far:
Part 1: The Idea Behind ZKPs
Part 2: A Mathematical Introduction to ZK Proofs
While this article does not cover any ZK concepts, it builds on the previous article and lays the groundwork for the third installment of the series.
Revisiting Proof Systems
In general, proof systems are described in terms of the verification process. This process can be viewed as an entity, called the Verifier. The proof for a certain claim is not intrinsic to the system, it is provided by an external source, which can be thought of as another entity called the Prover. The proof system just confirms the validity of proofs, rather than producing any proofs on its own.
The goal of an interactive proof system is to record everything that can be efficiently verified through interaction with the outside world. This interaction can be complex and many messages might be exchanged, as long as the total time the verifier spends is polynomial in the shared input.
Let’s recall an excerpt from the last article:
While no false statement can be proved (in a proof system), not every true statement has an efficient proof system in which that statement can be proved. The gist here is that we confine ourselves to the class of valid statements that do have “efficient proof systems”, and this efficiency is in turn associated with the efficiency of the verification process.
Note: This fundamental fact relates to the undecidability of the Halting Problem; it is given precise meaning in results such as Gödel's Incompleteness Theorem and Turing's theorem.
Since efficient procedures are associated with probabilistic polynomial-time algorithms, we choose to focus only on probabilistic polynomial-time verifiers.
Complexity Classes
Computation complexity theory categorizes computational problems based on the amount of resources required to solve them, such as time and storage. A few of these classes will be mentioned in the sections that follow, so here's a quick rundown:
The complexity class P is the set of decision problems that can be solved by a deterministic Turing machine in polynomial time.
The complexity class NP is the set of decision problems verifiable by a non-deterministic Turing machine in polynomial time.
The class IP consists is the set of problems solvable by an interactive proof system.
The class PSPACE is the set of all decision problems that can be solved by a Turing machine using a polynomial amount of space.
The asymmetry between the complexity of the verification task and the complexity of the theorem-proving task is captured by the complexity class NP. If you’ve ever tried your hand at a Sudoku puzzle, you know that there’s often a huge difference between solving it from scratch and verifying a given solution. P is the class of decision problems that can be efficiently solved. NP is the class of decision problems whose solutions can be efficiently verified.
The complexity class NP serves as a formal model for the class of problems with efficiently verifiable solutions: given an input x, we can easily verify that x is a YES instance of the problem (or equivalently, x is in the language). The solution to an NP class problem can be verified in polynomial time.
Combining Interaction and NP
Let’s introduce interaction to the NP scenario. Instead of having the Prover send written proof to the Verifier, we’d now have an interrogatory proof system — the Verifier asks questions, and the Prover responds. In the end, the Verifier decides whether or not to accept the input.
By “interaction”, we mean that the Verifier and the Prover are two deterministic functions. A message sent during any round of interaction is a function of the input and all the messages sent and received during the previous rounds. Formalizing the interaction between two deterministic functions and then defining the class of deterministic Interactive Proof systems or dIP.
The class dIP contains all languages with a k(n)-round deterministic interactive proof systems with k(n) polynomial in n. Turns out, NP = dIP. So by assuming a deterministic Verifier, there’s no improvement (over NP) in the class of languages that we can prove.
The Class IP
NP can be thought of as a class of interactive proof systems (i.e., NP ⊆ IP) in which the interaction is unidirectional (from the Prover to the Verifier) and the Verifier is deterministic (and never makes an error). Both restrictions are lifted in general interactive proof systems: the interaction is bidirectional, and the verifier is probabilistic (and has a small probability of erring). We do so because in order to realize the full potential of interaction, we need to let the Verifier be probabilistic.
We allow the Verifier to accept a proof for a wrong statement (or come to a wrong conclusion) with a small probability. However, this probability is over the Verifier’s random choices (or coin tosses) and the Verifier will reject proofs for a wrong statement with a good probability (regardless of the strategy used by the Prover). Combining bidirectional interaction and randomization has a huge effect: the set of languages which have interactive proof systems (the class IP) now jumps from NP to PSPACE.
The class IP remains unchanged if we replace the constant 2/3 in the completeness requirement by 1. However, replacing the constant 1/3 by 1 in the soundness condition reduces the class IP to NP — it is equivalent to having a deterministic Verifier.
The Proving Power of Interactive Proof Systems
Let’s wrap up by discussing the structure of the class IP.
Completeness and Soundness: We focus the interactive proof systems in which the Verifier always accepts input IN the language. This implies perfect completeness (i.e., the completeness error equals zero). We can convert any interactive proof into an interactive proof system (for the same language) where the Verifier always accepts input in the language.
Only languages in NP, on the other hand, have interactive proof systems in which the Verifier always rejects inputs that are NOT IN the language. This implies complete soundness (i.e., the soundness error equals zero).Privacy of the Verifier’s coins: Arthur-Merlin proofs or public-coin proof systems are a special case of interactive proof systems where the Verifier only needs to send the outcome of its coin tosses and nothing else. Any interactive proof system for a given language can be transformed into a public-coin proof system for the same language, while preserving perfect completeness.
Languages having interactive proof systems: Every language in PSPACE has an interactive proof system. In fact, IP equals PSPACE.
Number of interactive rounds: In the generic interactive proof system for languages in PSPACE, the number of communicative rounds is polynomially linked to the length of the input.
This marks the end of the article. ヽ(•‿•)ノ
The next part of the ZK-series comes out tomorrow.
If you have any suggestions, comments or just want to say ‘hi’ – you can find me on Twitter at @gryptooo . Thanks for reading. :)