1<!DOCTYPE HTML> 2<html lang="en" class="light" dir="ltr"> 3 <head> 4 <!-- Book generated using mdBook --> 5 <meta charset="UTF-8"> 6 <title>Probabilistic and Interactive proofs - ZK Jargon Decoder</title> 7 8 9 <!-- Custom HTML head --> 10 11 <meta name="description" content=""> 12 <meta name="viewport" content="width=device-width, initial-scale=1"> 13 <meta name="theme-color" content="#ffffff"> 14 15 <link rel="icon" href="../favicon.svg"> 16 <link rel="shortcut icon" href="../favicon.png"> 17 <link rel="stylesheet" href="../css/variables.css"> 18 <link rel="stylesheet" href="../css/general.css"> 19 <link rel="stylesheet" href="../css/chrome.css"> 20 <link rel="stylesheet" href="../css/print.css" media="print"> 21 22 <!-- Fonts --> 23 <link rel="stylesheet" href="../FontAwesome/css/font-awesome.css"> 24 <link rel="stylesheet" href="../fonts/fonts.css"> 25 26 <!-- Highlight.js Stylesheets --> 27 <link rel="stylesheet" href="../highlight.css"> 28 <link rel="stylesheet" href="../tomorrow-night.css"> 29 <link rel="stylesheet" href="../ayu-highlight.css"> 30 31 <!-- Custom theme stylesheets --> 32 33 </head> 34 <body class="sidebar-visible no-js"> 35 <div id="body-container"> 36 <!-- Provide site root to javascript --> 37
37<script> 38 var path_to_root = "../"; 39 var default_theme = window.matchMedia("(prefers-color-scheme: dark)").matches ? "navy" : "light"; 40 </script>
40 41 42 <!-- Work around some values being stored in localStorage wrapped in quotes --> 43
43<script> 44 try { 45 var theme = localStorage.getItem('mdbook-theme'); 46 var sidebar = localStorage.getItem('mdbook-sidebar'); 47 48 if (theme.startsWith('"') && theme.endsWith('"')) { 49 localStorage.setItem('mdbook-theme', theme.slice(1, theme.length - 1)); 50 } 51 52 if (sidebar.startsWith('"') && sidebar.endsWith('"')) { 53 localStorage.setItem('mdbook-sidebar', sidebar.slice(1, sidebar.length - 1)); 54 } 55 } catch (e) { } 56 </script>
56 57 58 <!-- Set the theme before any content is loaded, prevents flash --> 59
59<script> 60 var theme; 61 try { theme = localStorage.getItem('mdbook-theme'); } catch(e) { } 62 if (theme === null || theme === undefined) { theme = default_theme; } 63 var html = document.querySelector('html'); 64 html.classList.remove('light') 65 html.classList.add(theme); 66 var body = document.querySelector('body'); 67 body.classList.remove('no-js') 68 body.classList.add('js'); 69 </script>
69 70 71 <input type="checkbox" id="sidebar-toggle-anchor" class="hidden"> 72 73 <!-- Hide / unhide sidebar before it is displayed --> 74
74<script> 75 var body = document.querySelector('body'); 76 var sidebar = null; 77 var sidebar_toggle = document.getElementById("sidebar-toggle-anchor"); 78 if (document.body.clientWidth >= 1080) { 79 try { sidebar = localStorage.getItem('mdbook-sidebar'); } catch(e) { } 80 sidebar = sidebar || 'visible'; 81 } else { 82 sidebar = 'hidden'; 83 } 84 sidebar_toggle.checked = sidebar === 'visible'; 85 body.classList.remove('sidebar-visible'); 86 body.classList.add("sidebar-" + sidebar); 87 </script>
87 88 89 <nav id="sidebar" class="sidebar" aria-label="Table of contents"> 90 <div class="sidebar-scrollbox"> 91 <ol class="chapter"><li class="chapter-item expanded affix "><a href="../foreword.html">Welcome</a></li><li class="chapter-item expanded affix "><li class="part-title">Introduction to ZK Jargon</li><li class="chapter-item expanded "><a href="../intro_to_zk/what_is_proving.html">What does it mean to prove?</a></li><li class="chapter-item expanded "><a href="../intro_to_zk/interactive_proofs.html" class="active">Probabilistic and Interactive proofs</a></li><li class="chapter-item expanded affix "><li class="part-title">Acronyms</li><li class="chapter-item expanded "><a href="../acronyms.html">List of Common Acronyms</a></li><li class="chapter-item expanded affix "><li class="part-title">Definitions</li><li class="chapter-item expanded "><a href="../definitions/algebraic_holographic_proof.html">Algebraic Holographic Proof (AHP)</a></li><li class="chapter-item expanded "><a href="../definitions/arithmetization.html">Arithmetization</a></li><li class="chapter-item expanded "><a href="../definitions/base_field.html">Base Field</a></li><li class="chapter-item expanded "><a href="../definitions/circuit.html">Circuit</a></li><li class="chapter-item expanded "><a href="../definitions/coefficient_form.html">Coefficient Form</a></li><li class="chapter-item expanded "><a href="../definitions/common_reference_string.html">Common Reference String</a></li><li class="chapter-item expanded "><a href="../definitions/completeness.html">Completeness</a></li><li class="chapter-item expanded "><a href="../definitions/constraints.html">Constraints</a></li><li class="chapter-item expanded "><a href="../definitions/elliptic_curve.html">Elliptic Curve</a></li><li class="chapter-item expanded "><a href="../definitions/evaluation_form.html">Evaluation Form</a></li><li class="chapter-item expanded "><a href="../definitions/fast_fourier_transform.html">Fast Fourier Transform</a></li><li class="chapter-item expanded "><a href="../definitions/fiat_shamir.html">Fiat-Shamir Transform</a></li><li class="chapter-item expanded "><a href="../definitions/fhe.html">Fully Homomorphic Encryption (FHE)</a></li><li class="chapter-item expanded "><a href="../definitions/instance.html">Instance</a></li><li class="chapter-item expanded "><a href="../definitions/lagrange_interpolation.html">Lagrange Interpolation</a></li><li class="chapter-item expanded "><a href="../definitions/language.html">Language</a></li><li class="chapter-item expanded "><a href="../definitions/mpc.html">Multi-party Computation (MPC)</a></li><li class="chapter-item expanded "><a href="../definitions/nullifier.html">Nullifier</a></li><li class="chapter-item expanded "><a href="../definitions/oracle.html">Oracle</a></li><li class="chapter-item expanded "><a href="../definitions/plonkish_arithmetization.html">PLONKish Arithmetization</a></li><li class="chapter-item expanded "><a href="../definitions/polynomial_commitment.html">Polynomial Commitment Scheme</a></li><li class="chapter-item expanded "><a href="../definitions/polynomial_interactive_oracle_proof.html">Polynomial Interactive Oracle Proof</a></li><li class="chapter-item expanded "><a href="../definitions/preprocessing_snark.html">Preprocessing SNARK</a></li><li class="chapter-item expanded "><a href="../definitions/public-coin.html">Public-coin</a></li><li class="chapter-item expanded "><a href="../definitions/quadratic_arithmetic_program.html">Quadratic Arithmetic Program</a></li><li class="chapter-item expanded "><a href="../definitions/r1cs.html">R1CS</a></li><li class="chapter-item expanded "><a href="../definitions/random_oracle.html">Random Oracle</a></li><li class="chapter-item expanded "><a href="../definitions/relation.html">Relation</a></li><li class="chapter-item expanded "><a href="../definitions/roots_of_unity.html">Roots of Unity</a></li><li class="chapter-item expanded "><a href="../definitions/scalable.html">Scalable</a></li><li class="chapter-item expanded "><a href="../definitions/scalar_field.html">Scalar Field</a></li><li class="chapter-item expanded "><a href="../definitions/schwartz_zippel.html">Schwartz-Zippel Lemma</a></li><li class="chapter-item expanded "><a href="../definitions/snark.html">SNARK</a></li><li class="chapter-item expanded "><a href="../definitions/soundness.html">Soundness</a></li><li class="chapter-item expanded "><a href="../definitions/stark.html">STARK</a></li><li class="chapter-item expanded "><a href="../definitions/structured_reference_string.html">Structured Reference String</a></li><li class="chapter-item expanded "><a href="../definitions/succinct.html">Succinct</a></li><li class="chapter-item expanded "><a href="../definitions/threshold_encryption.html">Threshold Encryption</a></li><li class="chapter-item expanded "><a href="../definitions/transparent_setup.html">Transparent Setup</a></li><li class="chapter-item expanded "><a href="../definitions/trusted_setup.html">Trusted Setup</a></li><li class="chapter-item expanded "><a href="../definitions/vanishing_polynomial.html">Vanishing Polynomial</a></li><li class="chapter-item expanded "><a href="../definitions/witness.html">Witness</a></li><li class="chapter-item expanded "><a href="../definitions/witness_encryption.html">Witness Encryption</a></li><li class="chapter-item expanded "><a href="../definitions/zero_knowledge_proof.html">Zero-Knowledge Proof</a></li><li class="chapter-item expanded "><a href="../definitions/zkvm.html">zkVM</a></li></ol> 92 </div> 93 <div id="sidebar-resize-handle" class="sidebar-resize-handle"> 94 <div class="sidebar-resize-indicator"></div> 95 </div> 96 </nav> 97 98 <!-- Track and set sidebar scroll position --> 99
99<script> 100 var sidebarScrollbox = document.querySelector('#sidebar .sidebar-scrollbox'); 101 sidebarScrollbox.addEventListener('click', function(e) { 102 if (e.target.tagName === 'A') { 103 sessionStorage.setItem('sidebar-scroll', sidebarScrollbox.scrollTop); 104 } 105 }, { passive: true }); 106 var sidebarScrollTop = sessionStorage.getItem('sidebar-scroll'); 107 sessionStorage.removeItem('sidebar-scroll'); 108 if (sidebarScrollTop) { 109 // preserve sidebar scroll position when navigating via links within sidebar 110 sidebarScrollbox.scrollTop = sidebarScrollTop; 111 } else { 112 // scroll sidebar to current active section when navigating via "next/previous chapter" buttons 113 var activeSection = document.querySelector('#sidebar .active'); 114 if (activeSection) { 115 activeSection.scrollIntoView({ block: 'center' }); 116 } 117 } 118 </script>
118 119 120 <div id="page-wrapper" class="page-wrapper"> 121 122 <div class="page"> 123 <div id="menu-bar-hover-placeholder"></div> 124 <div id="menu-bar" class="menu-bar sticky"> 125 <div class="left-buttons"> 126 <label id="sidebar-toggle" class="icon-button" for="sidebar-toggle-anchor" title="Toggle Table of Contents" aria-label="Toggle Table of Contents" aria-controls="sidebar"> 127 <i class="fa fa-bars"></i> 128 </label> 129 <button id="theme-toggle" class="icon-button" type="button" title="Change theme" aria-label="Change theme" aria-haspopup="true" aria-expanded="false" aria-controls="theme-list"> 130 <i class="fa fa-paint-brush"></i> 131 </button> 132 <ul id="theme-list" class="theme-popup" aria-label="Themes" role="menu"> 133 <li role="none"><button role="menuitem" class="theme" id="light">Light</button></li> 134 <li role="none"><button role="menuitem" class="theme" id="rust">Rust</button></li> 135 <li role="none"><button role="menuitem" class="theme" id="coal">Coal</button></li> 136 <li role="none"><button role="menuitem" class="theme" id="navy">Navy</button></li> 137 <li role="none"><button role="menuitem" class="theme" id="ayu">Ayu</button></li> 138 </ul> 139 <button id="search-toggle" class="icon-button" type="button" title="Search. (Shortkey: s)" aria-label="Toggle Searchbar" aria-expanded="false" aria-keyshortcuts="S" aria-controls="searchbar"> 140 <i class="fa fa-search"></i> 141 </button> 142 </div> 143 144 <h1 class="menu-title">ZK Jargon Decoder</h1> 145 146 <div class="right-buttons"> 147 <a href="../print.html" title="Print this book" aria-label="Print this book"> 148 <i id="print-button" class="fa fa-print"></i> 149 </a> 150 <a href="https://github.com/zkjargon/zkjargon.github.io/" title="Git repository" aria-label="Git repository"> 151 <i id="git-repository-button" class="fa fa-github"></i> 152 </a> 153 <a href="https://github.com/zkjargon/zkjargon.github.io/edit/main/src/intro_to_zk/interactive_proofs.md" title="Suggest an edit" aria-label="Suggest an edit"> 154 <i id="git-edit-button" class="fa fa-edit"></i> 155 </a> 156 157 </div> 158 </div> 159 160 <div id="search-wrapper" class="hidden"> 161 <form id="searchbar-outer" class="searchbar-outer"> 162 <input type="search" id="searchbar" name="searchbar" placeholder="Search this book ..." aria-controls="searchresults-outer" aria-describedby="searchresults-header"> 163 </form> 164 <div id="searchresults-outer" class="searchresults-outer hidden"> 165 <div id="searchresults-header" class="searchresults-header"></div> 166 <ul id="searchresults"> 167 </ul> 168 </div> 169 </div> 170 171 <!-- Apply ARIA attributes after the sidebar and the sidebar toggle button are added to the DOM --> 172
172<script> 173 document.getElementById('sidebar-toggle').setAttribute('aria-expanded', sidebar === 'visible'); 174 document.getElementById('sidebar').setAttribute('aria-hidden', sidebar !== 'visible'); 175 Array.from(document.querySelectorAll('#sidebar a')).forEach(function(link) { 176 link.setAttribute('tabIndex', sidebar === 'visible' ? 0 : -1); 177 }); 178 </script>
178 179 180 <div id="content" class="content"> 181 <main> 182 <link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/[email protected]/dist/katex.min.css"> 183<h1 id="introduction-to-zk-jargon"><a class="header" href="#introduction-to-zk-jargon">Introduction to ZK Jargon</a></h1> 184<hr /> 185<h2 id="part-2-probabilistic-and-interactive-proofs"><a class="header" href="#part-2-probabilistic-and-interactive-proofs">Part 2: Probabilistic and Interactive Proofs</a></h2> 186<p>In the <a href="./what_is_proving.html">previous article</a>, we covered what âprovingâ means, established some necessary vocabulary and finally discussed the trivial proof system: sending the <a href="./what_is_proving.html#relations">witness</a>. 187As discussed, this is not always desirable. 188Sometimes the witness is private and should remain so. 189Other times, the witness is just too big to be sent or for the Verifier to process.</p> 190<p>In this article, we look at two techniques to build more elaborate proof systems:</p> 191<ul> 192<li>the first is to allow the Verifier to âask multiple questionsâ, i.e. to <strong>interact with the Prover</strong>;</li> 193<li>the second is to allow the Verifier to <strong>not read the whole proof</strong>.</li> 194</ul> 195<p>Naturally, if the proof is shorter than the witness or it is some randomized version of it, the Verifier might sometimes accept proofs for <code>FALSE</code> statements. 196This is acceptable (!), as long as it only happens with a small probability. 197We call this probability the <strong>soundness error</strong> (see <a href="../definitions/soundness.html">Soundness</a>).</p> 198<h3 id="1-asking-multiple-questions"><a class="header" href="#1-asking-multiple-questions">1. Asking multiple questions</a></h3> 199<p>The first technique can be understood as âasking multiple questionsâ. 200Rather than sending the witness as a single message, the Prover and Verifier can <strong>interact</strong> over multiple rounds. 201This forces the Prover to stay consistent: once something is said, it cannot be unsaid; and any contradiction between the Proverâs messages can be used against him.</p> 202<p>Proof systems that use this paradigm are known as <strong>interactive proofs (IP)</strong>.</p> 203<p><img src="../images/cartoon_ip.png" alt="Interactive proof" /></p> 204<p>In practice, we much prefer non-interactive proofs. 205Luckily, if an IP is such that the Verifierâs messages are all sampled at random from a uniform distribution, <strong>there are techniques to transform the IP into a non-interactive proof</strong> (e.g., the <a href="../definitions/fiat_shamir.html">Fiat-Shamir Transform</a>).</p> 206<h3 id="2-not-reading-the-full-proof"><a class="header" href="#2-not-reading-the-full-proof">2. Not reading the full proof</a></h3> 207<p>The second technique is to not read the full proof. 208Instead, the Verifier will <strong>query the proof</strong> at location of her choice. 209The locations are usually chosen at random after the Prover sent his message.</p> 210<p>Proof systems that use this paradigm are known as <strong>probabilistically checkable proofs (PCP)</strong>.</p> 211<p><img src="../images/cartoon_pcp.png" alt="Probabilistic proof" /></p> 212<p>Note that for PCPs to make sense, we need a way for the Prover to send his message, without requiring the Verifier to read it in full. 213When working on theoretical systems, we allow the Prover to send an <a href="../definitions/oracle.html">oracle</a> for his proof. 214In this context, an oracle is a black-box that stores the proof string and can be queried at any index. 215<strong>To turn these into real-world systems, we implement the oracle with a commitment scheme.</strong></p> 216<h3 id="3-combining-both"><a class="header" href="#3-combining-both">3. Combining both</a></h3> 217<p>Of course, we can combine the two above techniques. 218The resulting proof systems are known as <strong>interactive oracle proofs (IOP)</strong>.</p> 219<p><img src="../images/cartoon_iop.png" alt="Interactive oracle proof" /></p> 220<p>Interestingly, IOPs are not more powerful than PCPs. 221Everything that can be proven by an IOP can also be proven by a PCP. 222However, they yield more efficient protocols in practice.</p> 223<h2 id="how-is-this-related-to-my-snarks"><a class="header" href="#how-is-this-related-to-my-snarks">How is this related to my SNARKs?</a></h2> 224<p>Our favorite recipe to build a SNARK is as follows: <strong>we start with an IOP, replace the theoretical oracles with commitments, and then remove interaction by using the Fiat-Shamir transform</strong>. 225The SNARK âproofâ is a collection of commitments to the Proverâs messages, the values of the IOP messages at the locations queried by the Verifier, and some extra information to convince the Verifier that the values do correspond to the committed strings.</p> 226<p>For a formal treatment of these techniques, please see the <em>excellent</em> free online book <a href="https://snargsbook.org"><em>Building Cryptographic Proofs from Hash Functions</em></a> by Chiesa and Yogev.</p> 227<h2 id="references"><a class="header" href="#references">References</a></h2> 228<p>See ââBibliographic Notesâ in Chiesa and Yogevâs <a href="https://snargsbook.org"><em>Building Cryptographic Proofs from Hash Functions</em></a>.</p> 229<hr /> 230<p><em>Cartoons created in <a href="https://plus.excalidraw.com">Excalidraw</a> by Nicolas Mohnblatt, using the Stick Figures collection by <a href="https://github.com/youritjang">Youri Tjang</a> and the Speech Bubbles collection by <a href="https://www.grepper.com/app/profile.php?id=44392">Oscar Capraro</a>.</em></p> 231 232 </main> 233 234 <nav class="nav-wrapper" aria-label="Page navigation"> 235 <!-- Mobile navigation buttons --> 236 <a rel="prev" href="../intro_to_zk/what_is_proving.html" class="mobile-nav-chapter
236s previous" title="Previous chapter" aria-label="Previous chapter" aria-keyshortcuts="Left"> 237 <i class="fa fa-angle-left"></i> 238 </a> 239 240 <a rel="next prefetch" href="../acronyms.html" class="mobile-nav-chapters next" title="Next chapter" aria-label="Next chapter" aria-keyshortcuts="Right"> 241 <i class="fa fa-angle-right"></i> 242 </a> 243 244 <div style="clear: both"></div> 245 </nav> 246 </div> 247 </div> 248 249 <nav class="nav-wide-wrapper" aria-label="Page navigation"> 250 <a rel="prev" href="../intro_to_zk/what_is_proving.html" class="nav-chapters previous" title="Previous chapter" aria-label="Previous chapter" aria-keyshortcuts="Left"> 251 <i class="fa fa-angle-left"></i> 252 </a> 253 254 <a rel="next prefetch" href="../acronyms.html" class="nav-chapters next" title="Next chapter" aria-label="Next chapter" aria-keyshortcuts="Right"> 255 <i class="fa fa-angle-right"></i> 256 </a> 257 </nav> 258 259 </div> 260 261 262 263 264
264<script> 265 window.playground_copyable = true; 266 </script>
266 267 268 269
269<script src="../elasticlunr.min.js"></script>
269 270
270<script src="../mark.min.js"></script>
270 271
271<script src="../searcher.js"></script>
271 272 273
273<script src="../clipboard.min.js"></script>
273 274
274<script src="../highlight.js"></script>
274 275
275<script src="../book.js"></script>
275 276 277 <!-- Custom JS scripts --> 278 279 280 </div> 281 </body> 282</html>
Line numbers count LF bytes from the start of the resource, as the search results do. Vendor segments are library code the classifier recognised; they are stored but not indexed. Bytes are shown as Latin1 characters, one per byte.