Proofs are the basis for all mathematics. A proof is a claim or theorem you are trying to prove & sequence of derivations made to declare the theorem has been proved. eg. all angles in a triangle total 180° can be independently checked by anyone (verifier).
Proofs
Prover —> Makes Claim —> Verifier Chooses —> Accept/Reject
(Both the prover and verifier are algorithms)
In computer science the term for efficiently verifiable proofs is NP proofs. These short proofs can be verified in polynomial time. The broad idea being “There exists a solution to a theorem & it is passed over to the verifier to check it”
NP statements
In an NP-language = two conditions must hold:
Completeness: True claims will be accepted by verifier (allows honest provers to reach verification)
Soundness: False claims will have no proofs (for all cheating prover strategy they will be unable to prove correctness of incorrect claim).
Interaction: Rather than just reading the proof, the verifier engages with a prover back and forth over several message rounds.
Randomness: Verifier’s requests to prover are randomized and prover must be able to answer correctly to each.
IP statements
Using interaction and randomness together it is possible to prove a claim to a blind verifier in Probabilistic Polynomial Time (PPT).
Can Interactive Proofs efficiently verify more than NP proofs?
NP Proofs vs IP proofs: