Introduction to ZKIP

1. Proof

   The prover has a claim and sends a proof to the verifier. The verifier uses proof to determine whether the claim is accepted.

   • witness

2. NP-Proof

   • What is added on top of Proof

     The prover has a claim x which is equivalent to a NP decision problem. The prover sends a witness w of which length is polynomial in the length of x. The verification time cost is also polynomial in the length of x.

   • e.g.

     • claim - x: N is a product of 2 large primes. |x| = $lo{g}_{2}N$ (length of binary string N)
     • 123
     • proof - w: {p,q} are one set of 2 large primes. |w| = $lo{g}_{2}p+lo{g}_{2}q$ (length of binary string p and q)
     • verification: check if N===p*q. Time cost of multiplication is $O(1)$

3. NP-language

   It is an equivalent class of a claim which there is a NP-Proof

   • Definition: $\mathcal{L}$ is an NP-language if there is a verifier can accept all elements $x\in \mathcal{L}$ in poly(|x|) time with a poly(|x|) long proof( or witness ).
     • otherwise for $x\notin \mathcal{L}$, it can’t be accepted by any verifier in poly(|x|) time with a poly(|x|) long proof( or witness ).