Evolution of Proofs in Computer Science: Zero-Knowledge Proofs Overview

Explore the evolution of proofs in computer science focusing on succinct zero-knowledge proofs, their significance, and impact on Bitcoin protocol and public ledgers. Learn about classical proofs, zero-knowledge proofs by Goldwasser-Micali-Rackoff, and interactive proofs in the realm of computer science.

• Computer Science
• Zero-Knowledge Proofs
• Bitcoin Protocol
• Interactive Proofs
• Evolution

cvesc Follow

Uploaded on Oct 03, 2024 | 0 Views

Download Presentation

Please find below an Image/Link to download the presentation.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

Presentation Transcript

1. The Evolution of Proofs in Computer Science: Succinct Zero-Knowledge Proofs 6.857 Lecture 13

2. Last Lecture: BitCoin Protocol Public Ledger Each user has to verify the validity of each payment in a block before adding the block to the public ledger This check is highly inefficient: It requires going over the entire public ledger!

3. Last Lecture: BitCoin Protocol Public Ledger zero-knowledge A succinct proof that my transaction is valid!

4. The Evolution of Proofs in Computer Science which leads to succinct zero-knowledge proofs

5. Classical Proofs ? ?

6. Classical Proofs http://t1.gstatic.com/images?q=tbn:ANd9GcRgVZaiUJw6jETLHjTP2kLvHubHBHBEgPR_7e5AejdA009zk8XWQw ? ?

7. Zero-Knowledge Proofs [Goldwasser-Micali-Rackoff85] Proofs that reveal no information beyond the validity of the statement

8. Zero-Knowledge Proofs [Goldwasser-Micali-Rackoff85] Impossible! This is information!

9. Interactive Proofs [Goldwasser-Micali-Rackoff85] ? ? Completeness: ? ? Pr ?,? ? = 1 2/3 Soundness: ? ?, ? Pr ? ,? ? = 1 1/3 Note: By repetition, we can get completeness 1 2 ?, and soundness 2 ?

10. Interactive Proofs [Goldwasser-Micali-Rackoff85] For ZK the prover needs to be randomized ? ? [Goldreich-Micali-Wigderson87]: Every statement that has a classical proofhas zero-knowledge (ZK) interactive proof, assuming one-way functions exist

11. Defining Zero-Knowledge ? ? This transcript reveals no information ? ? Formally: There exists a ??? algorithm ? (called a simulator), such that for every ? ?: ? ? (?,?)(?) Denotes the transcript

12. Graphs for which vertices can be colored by {1,2,3} s.t. no two adjacent vertices are colored by the same color ZK Proofs for NP For the ??-complete language of all 3-colorable graphs ? = ?,? Locked safe, reveals no information about its content ? ? Randomly permute the coloring, to obtain valid coloring (?1, ,??) ?? ?? Choose a random edge ?,? ? ?,? ? Open safes ?,? 1 ?but can be amplified via repetition. Soundness: Only 1

13. ZK Proofs for NP For the ??-complete language of all 3-colorable graphs ? ?,? : ? = ?,? 1. Choose a random ?,? ? 2. Choose random distinct colors ??,?? 3. The simulated transcript is: ? ? safes ?,? have values ??,?? ?? ?? ?,? ? ?,? ? Open safes ?,? Open safes ?,?

14. Implementing Digital Safes: Commitment Scheme A commitment scheme is a randomized algorithm ??? s.t.: Hiding: ?,? ??? ?;? ???(? ;? ). Binding: ?,? , ? ,? s.t. ? ? and ??? ?;? = ???(? ;? )

15. Using Commitments to Construct ZK Proofs For the ??-complete language of all 3-colorable graphs ? = ?,? ? ? Randomly permute the coloring, to obtain valid coloring (?1, ,??) ??? ?1, ,???(??) Choose a random edge ?,? ? ?,? ? Reveal ??,??, with corresponding randomness

16. Constructing a Commitment Scheme Construction 1: Let ?: 0,1 0,1 be an injective OWF. ??? ?;(?,?) = (? ? ,?,( ????) ?) Binding: Follows from the fact that ? is injective Hiding: Relies on the fact that if ? is one-way then: ? ? ,?, ???? ? ? ,? ,?) Known as a hard-core predicate [Goldreich-Levin89]

17. Constructing a Commitment Scheme Construction 2: Let ? be a group of prime order p, let ? ? be any generator, and be a random group element. ????,??,? = ???? Hiding: Information theoretically! Binding: Follows from the Discrete Log assumption. If ??? alg ? s.t. ? ?, = ?1,?2,?1,?2where ??1 ?1=??2 ?2then ?1+ ??1= ?2+ ??2 mod p, which implies that ? =?1 ?2 ?2 ?1 mod p

18. Constructing Zero-Knowledge Proofs This is perfect ZK! But only computationally sound ? ? Perfectly hiding ?, ? Randomly permute the coloring, to obtain valid coloring (?1, ,??) All powerful prover can break binding ????, ?1, ,????, (??) Choose a random edge ?,? ? ?,? ? Reveal ??,??, with corresponding randomness

19. Interactive Computationally Sound Proofs (a.k.a. Arguments) [Brassard-Chaum-Creapeau88] ? ? ? ? Completeness: ? ? Pr ?,? ? = 1 2/3 Soundness: ? ?, ??? ? Pr ? ,? ? = 1 1/3

20. So Far Non-succinct Constructed ZK proofs for all of NP using commitment schemes Constructed commitment schemes Based on injective OWF: computationally hiding, perfectly binding Computational ZK proofs Perfect ZK arguments Based on Discrete Log: perfectly hiding, computationally binding

21. Interactive Proofs are More Efficient! [Lund-Fortnow-Karloff-Nissan90, Shamir90] Example: Chess

22. Interactive Proofs are More Efficient! [Lund-Fortnow-Karloff-Nissan90, Shamir90] correctness of any computation can be proved: Time to verify Space required to do the computation Interactive Proof ?? = ??????

23. Interactive Proofs are More Efficient! [Lund-Fortnow-Karloff-Nissan90, Shamir90] correctness of any computation can be proved: Time to verify Space required to do the computation Succinct space succinct interactive proof

24. Interactive Proofs [Goldwasser-Micali-Rackoff85, Babai85] All ? ? Efficient powerful ? ?

25. Interactive Proofs [Goldwasser-Micali-Rackoff85, Babai85] ??? ? ? ?

26. Doubly Efficient Proofs [Goldwasser-K-Rothblum08] Proofs for any computation: Prover runtime computation runtime Verifier runtime |input|

27. Doubly Efficient Proofs [Goldwasser-K-Rothblum08] Proofs for any computation: Prover runtime computation runtime Verifier runtime |input| Theorem: For every computation represented as a circuit of size ?and depth ?, there exists a doubly efficient interactive proof for this computation, where the prover runs in time ?and the verifier runs in time ?

28. Succinct Zero-Knowledge Proofs Our succinct proofs are interactive! A succinct zero-knowledge proof that my transaction is valid!

29. Fiat-Shamir Paradigm for Reducing Interaction

30. The Fiat-Shamir Paradigm [Fiat-Shamir86] Computationally sound (argument) ? ? ??? ??? ?0 ?1 ?0,?1,?1, ,?3,?3 ?1 ?2 ?2 ?3 ?3 Check that ? [3] ??= ? ??,??,??, ,?? ? ,?? ? and that (??,??,??, ,??,??) is accepting

31. Non-Interactive Arguments Common Reference String (such as a hash function) ? ? ? ?

32. Succinct doubly-efficient public-coin interactive proof + Fiat-Shamir paradigm Succinct non-interactive argument (SNARG)

33. The Doubly-Efficient IP for bounded depth computations + Fiat-Shamir paradigm SNARG for bounded depth computations

34. From Theory to Practice Pepper [SMBW12] Ginger [SVPBBW12] Buffet [WSRBW15] Proof Carrying Data [BCTV14, CTV15] Scalable Zero Knowledge [BCTZ14]

35. Eliminating Depth Restriction Idea: Convert computation to low-depth circuit! ??? ?? 1 ... ? ?1 ?? ??? ?2 ?1 ? Run the doubly efficient IP on squashed circuit! ?1?2?3

36. Eliminating Depth Restriction Idea: Convert computation to low-depth circuit! ??? ?? 1 ... ? ?1 ?? ??? ?2 ?1 ? Unknown to verifier! ?1?2?3

37. Eliminating Depth Restriction Idea: Convert computation to low-depth circuit! ??? ?? 1 ... ? ?1 ?? ??? ?2 ?1 ? Prover commits to ?,?1, ,??,??? Using a cryptographic commitment ?1?2?3

39. Classical proofs (Zero-knowledge) Interactive proofs multi-prover interactive proofs Probabilistically checkable proofs Interactive PCP/ Interactive Oracle Proofs