PageSourceSearch

https://zkjargon.github.io/intro_to_zk/interactive_proofs.html

html zkjargon.github.io collected 2026-10-03 10:15:11 UTC 21,988 bytes, 282 lines download raw bytes

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.