ZK introduction
ZK introduction
ZK theory basis and developments
Theory basis
Zero knowledge Proof is composed of Mathematical Logic（mainly complexity and a few proof theory）and Cryptography.
For proof theroy, if logic is the science of valid inference, then proofs embody its heart. There are two properties for the proof system, Soundness and Completeness.
- Given a certain proof system, the soundness theorem says that only valid sentences are provable in it.
- The completeness theorem says that every valid sentence is provable in it.
zero knowledge proof doesn't give you an a right proof. It's about minimizing the probability that someone is lying to you.
Principles
Suppose that you have a public input \(x\), a private input \(w\), and a (public) function \(f(x,w)->\{True, False\}\), which performs some kind of verification on the inputs. With a ZK-SNARK, you can prove that for some given \(f\) and \(x\), you know the an \(w\) such that \(f(x,w) = True\), without revealing what \(w\) is. Additionally, the verifier can verify the proof much fast than computate \(f(x,w)\) themselves directly, even if they konw \(w\).
Three properties:
- Completeness: it should convince the verifier that the prover knows what they say they know
- Soundness: if the information is false, it cannot convince the verifier that the prover’s information is true
- Zero-knowledge: it should reveal nothing else to the verifier
If verifier accepts, then it learns no additional information from the interaction, because \(verifier^*\) could have simulated the entire dialog or interaction on his own.
\(verifier^*\): any verifier that even deviates from the prescribed instruction of the protocol.
ZK-SNARKs
Zero-Knowledge Succinct Non-interactive ARguments of Knowledge, a type of non-interactive ZKP
Zero-Knowledge, because they don’t reveal any knowledge to the verifier succinct, because the proof can be verified quickly non interactive, because repeated interaction is not required between prover and verifier and arguments of knowledge, because they present sound proof.
Drawbacks
- It can't produce a 100% airtight proof. It can only infinitely reduce the probability that someone is faking a proof.
- The algorithm is rather intensive, requiring either a large number of interactions between verifier and prover or, in case of SNARK's, requiring a lot of computations that could make it impossible to run on slow or mobile devices. But that limitation can be overcome. The Zcash team for instance has been at hard at work to improve their algorithm so it can also run on lower powered devices such as a smartphone.
Developments
zkp is first proposed in a paper from 1985 called “The Knowledge Complexity of Interactive Proof-Systens. It develops from non-interactive form to interactive form.
interactive proof: The claimed statement is verified probabilistically by by utilizing a computational hard problem (NP-hard problem), a challenge-response protocol (randomness), and interactivity.
non-interactive proof: The verifier is replaced with a simulator, and the randomness challenge and interactivity can be achieved by two ways to hidden randomness,random oracle model (ROM) and common reference string model (CRS).
you run the protocol with a simulator (who is just a verifier, but the random choices are done differently), and then you can give the transcript of the protocol to anyone and convince them that the proof is real. Therefore, the proof is actually the transcript of the protocol between prover and the simulator (verifier). The verification process involves verifying whether the transcript is correct or not.
