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>What does it mean to prove? - 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" class="active">What does it mean to prove?</a></li><li class="chapter-item expanded "><a href="../intro_to_zk/interactive_proofs.html">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/what_is_proving.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-1-what-does-it-mean-to-prove"><a class="header" href="#part-1-what-does-it-mean-to-prove">Part 1: What does it mean to <em>prove</em>?</a></h2> 186<p>This article aims to be a gentle introduction to the notions of <strong>decision problems</strong>, <strong>relations</strong>, <strong>languages</strong> and the <strong><span class="katex"><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.6944em;"></span><span class="mord"><span class="mord mathsf">NP</span></span></span></span></span> complexity class</strong>. 187We follow a running example and rephrase it each time we cover a new term.</p> 188<h3 id="decision-problems"><a class="header" href="#decision-problems">Decision Problems</a></h3> 189<p>In mathematics, a statement is either <code>TRUE</code> or <code>FALSE</code>. 190However, deciding whether a statement is true or false is not always easy. 191Consider for example the following statements:</p> 192<ul> 193<li><strong>Statement 1</strong>: the number <span class="katex"><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.6444em;"></span><span class="mord">54</span></span></span></span> is even.</li> 194<li><strong>Statement 2</strong>: the number <span class="katex"><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.6444em;"></span><span class="mord">25890323</span></span></span></span> can be factored.</li> 195</ul> 196<!-- 5669 x 4567 = 25890323 --> 197<p>We can quickly check that Statement 1 is <code>TRUE</code>, but what about Statement 2? 198To our knowledge, the best way to decide Statement 2 is just to try factoring <span class="katex"><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.6444em;"></span><span class="mord">25890323</span></span></span></span>. 199If we succeed, the statement is <code>TRUE</code>, but we might be trying for a long time, with no guarantee of ever succeeding!</p> 200<p>What if we are given additional information? 201Letâs say we were magically handed (or by luck stumbled upon) the numbers <span class="katex"><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.6444em;"></span><span class="mord">5669</span></span></span></span> and <span class="katex"><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.6444em;"></span><span class="mord">4567</span></span></span></span>. 202We can try to multiply them together and find that indeed <span class="katex"><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.7278em;vertical-align:-0.0833em;"></span><span class="mord">5669</span><span class="mspace" style="margin-right:0.2222em;"></span><span class="mbin">Ã</span><span class="mspace" style="margin-right:0.2222em;"></span></span><span class="base"><span class="strut" style="height:0.6444em;"></span><span class="mord">4567</span><span class="mspace" style="margin-right:0.2778em;"></span><span class="mrel">=</span><span class="mspace" style="margin-right:0.2778em;"></span></span><span class="base"><span class="strut" style="height:0.6444em;"></span><span class="mord">25890323</span></span></span></span>. 203We can now decide Statement 2 â .</p> 204<p>Notice that with the additional information, we only needed to perform one multiplication; much less work than trying out all the potential factorizations. 205In a way, this additional information was in fact a <strong>proof</strong> that Statement 2 is <code>TRUE</code>.</p> 206<p><strong>Answer #1 (informal): proving means giving auxiliary information about a statement to decide that it is true.</strong></p> 207<p>We can also rephrase this answer in the form of a condition: a provable statement is one that can be easily decided <em>provided the right information</em>. 208In <a href="https://en.wikipedia.org/wiki/Computational_complexity_theory">complexity theory</a>, this corresponds to the <a href="https://en.wikipedia.org/wiki/NP_(complexity)">class <span class="katex"><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.6944em;"></span><span class="mord"><span class="mord mathsf">NP</span></span></span></span></span></a>.</p> 209<h3 id="relations"><a class="header" href="#relations">Relations</a></h3> 210<p>The discussion above is formalised by the notions of relations and languages:</p> 211<ul> 212<li>A <strong>relation</strong> <span class="katex"><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.6833em;"></span><span class="mord mathcal">R</span></span></span></span> is a set of ordered pairs <span class="katex"><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mopen">(</span><span class="mord mathnormal">x</span><span class="mpunct">,</span><span class="mspace" style="margin-right:0.1667em;"></span><span class="mord mathnormal" style="margin-right:0.02691em;">w</span><span class="mclose">)</span></span></span></span>. 213When talking about <span class="katex"><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.6944em;"></span><span class="mord"><span class="mord mathsf">NP</span></span></span></span></span> relations (provable statements) we refer to the first item, <span class="katex"><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.4306em;"></span><span class="mord mathnormal">x</span></span></span></span>, as an <strong>instance</strong>
213, and the second, <span class="katex"><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.4306em;"></span><span class="mord mathnormal" style="margin-right:0.02691em;">w</span></span></span></span>, as a <strong>witness</strong>.</li> 214</ul> 215<blockquote> 216<p><strong>Example: factors.</strong> 217Letâs define a relation that we will call <span class="katex"><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.8333em;vertical-align:-0.15em;"></span><span class="mord"><span class="mord mathcal">R</span><span class="msupsub"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:0.3361em;"><span style="top:-2.55em;margin-left:0em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord text mtight"><span class="mord mtight">factors</span></span></span></span></span><span class="vlist-s">â</span></span><span class="vlist-r"><span class="vlist" style="height:0.15em;"><span></span></span></span></span></span></span></span></span></span>. 218An instance of this relation is an integer, and a witness is an unordered list of integers greater than 1. 219We will say that the pair <span class="katex"><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mopen">(</span><span class="mord mathnormal">x</span><span class="mpunct">,</span><span class="mspace" style="margin-right:0.1667em;"></span><span class="mord mathnormal" style="margin-right:0.02691em;">w</span><span class="mclose">)</span></span></span></span> is in <span class="katex"><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.8333em;vertical-align:-0.15em;"></span><span class="mord"><span class="mord mathcal">R</span><span class="msupsub"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:0.3361em;"><span style="top:-2.55em;margin-left:0em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord text mtight"><span class="mord mtight">factors</span></span></span></span></span><span class="vlist-s">â</span></span><span class="vlist-r"><span class="vlist" style="height:0.15em;"><span></span></span></span></span></span></span></span></span></span> if and only if <span class="katex"><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.4306em;"></span><span class="mord mathnormal" style="margin-right:0.02691em;">w</span></span></span></span> contains more than one element and the product of all the elements in <span class="katex"><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.4306em;"></span><span class="mord mathnormal" style="margin-right:0.02691em;">w</span></span></span></span> is equal to <span class="katex"><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.4306em;"></span><span class="mord mathnormal">x</span></span></span></span>.</p> 220<p>For example, the instance <span class="katex"><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.6444em;"></span><span class="mord">6</span></span></span></span> has the witness <span class="katex"><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mopen">[</span><span class="mord">2</span><span class="mpunct">,</span><span class="mspace" style="margin-right:0.1667em;"></span><span class="mord">3</span><span class="mclose">]</span></span></span></span>. 221The instance <span class="katex"><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.6444em;"></span><span class="mord">16</span></span></span></span> has multiple witnesses: including <span class="katex"><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mopen">[</span><span class="mord">
2214</span><span class="mpunct">,</span><span class="mspace" style="margin-right:0.1667em;"></span><span class="mord">4</span><span class="mclose">]</span></span></span></span>, <span class="katex"><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mopen">[</span><span class="mord">2</span><span class="mpunct">,</span><span class="mspace" style="margin-right:0.1667em;"></span><span class="mord">8</span><span class="mclose">]</span></span></span></span> and <span class="katex"><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mopen">[</span><span class="mord">2</span><span class="mpunct">,</span><span class="mspace" style="margin-right:0.1667em;"></span><span class="mord">2</span><span class="mpunct">,</span><span class="mspace" style="margin-right:0.1667em;"></span><span class="mord">4</span><span class="mclose">]</span></span></span></span>.</p> 222<p>We can now recast Statement 2 in terms of <span class="katex"><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.8333em;vertical-align:-0.15em;"></span><span class="mord"><span class="mord mathcal">R</span><span class="msupsub"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:0.3361em;"><span style="top:-2.55em;margin-left:0em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord text mtight"><span class="mord mtight">factors</span></span></span></span></span><span class="vlist-s">â</span></span><span class="vlist-r"><span class="vlist" style="height:0.15em;"><span></span></span></span></span></span></span></span></span></span>:</p> 223<ul> 224<li><strong>Statement 2</strong> (with jargon, part 1): there exists a witness <span class="katex"><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.4306em;"></span><span class="mord mathnormal" style="margin-right:0.02691em;">w</span></span></span></span> such that <span class="katex"><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mopen">(</span><span class="mord">25890323</span><span class="mpunct">,</span><span class="mspace" style="margin-right:0.1667em;"></span><span class="mord mathnormal" style="margin-right:0.02691em;">w</span><span class="mclose">)</span></span></span></span> is in <span class="katex"><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.8333em;vertical-align:-0.15em;"></span><span class="mord"><span class="mord mathcal">R</span><span class="msupsub"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:0.3361em;"><span style="top:-2.55em;margin-left:0em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord text mtight"><span class="mord mtight">factors</span></span></span></span></span><span class="vlist-s">â</span></span><span class="vlist-r"><span class="vlist" style="height:0.15em;"><span></span></span></span></span></span></span></span></span></span>.</li> 225</ul> 226<p>As we saw above, finding such a witness ourselves is a lot of work. 227However, given the candidate witness <span class="katex"><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mopen">[</span><span class="mord">5669</span><span class="mpunct">,</span><span class="mspace" style="margin-right:0.1667em;"></span><span class="mord">4567</span><span class="mclose">]</span></span></span></span>, we can quickly check that the pair <span class="katex"><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mopen">(</span><span class="mord">25890323</span><span class="mpunct">,</span><span class="mspace" style="margin-right:0.1667em;"></span><span class="mopen">[</span><span class="mord">5669</span><span class="mpunct">,</span><span class="mspace" style="margin-right:0.1667em;"></span><span class="mord">4567</span><span class="mclose">])</span></span></span></span> is in <span class="katex"><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.8333em;vertical-align:-0.15em;"></span><span class="mord"><span class="mord mathcal">R</span><span class="msupsub"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:0.3361em;"><span style="top:-2.55em;margin-left:0em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord text mtight"><span class="mord mtight">factors</span></span></span></span></span><span class="vlist-s">â</span></span><span class="vlist-r"><span class="vlist" style="height:0.15em;"><span></span></span></span></span></span></span></span></span></span>.</p> 228</blockquote> 229<h3 id="languages"><a class="header" href="#languages">Languages</a></h3> 230<p>Rather than always having to say âthe instance <span class="katex"><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.5806em;vertical-align:-0.15em;"></span><span class="mord"><span class="mord mathnormal">x</span><span class="msupsub"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:0.3011em;"><span style="top:-2.55em;margin-left:0em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight">1</span></span></span></span><span class="vlist-s">â</span></span><span class="vlist-r"><span class="vlist" style="height:0.15em;"><span></span></span></span></span></span></span></span></span></span> has a witness <span class="katex"><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.5806em;vertical-align:-0.15em;"></span><span class="mord"><span class="mord mathnormal" style="margin-right:0.02691em;">w</span><span class="msupsub"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:0.3011em;"><span style="top:-2.55em;margin-left:-0.0269em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight">1</span></span></span></span><span class="vlist-s">â</span></span><span class="vlist-r"><span class="vlist" style="height:0.15em;"><span></span></span></span></span></span></span></span></span></span> such that <span class="katex"><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mopen">(</span><span class="mord"><span class="mord mathnormal">x</span><span class="msupsub"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:0.3011em;"><span style="top:-2.55em;margin-left:0em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight">1</span></span></span></span><span class="vlist-s">â</span></span><span class="vlist-r"><span class="vlist" style="height:0.15em;"><span></span></span></span></span></span></span><span class="mpunct">,</span><span class="mspace" style="margin-right:0.1667em;"></span><span class="mord"><span class="mord mathnormal" style="margin-right:0.02691em;">w</span><span class="msupsub"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:0.3011em;"><span style="top:-2.55em;margin-left:-0.0269em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight">1</span></span></span></span><span class="vlist-s">â</span></span><span class="vlist-r"><span class="vlist" style="height:0.15em;"><span></span></span></span></span></span></span><span class="mclose">)</span><span class="mspace" style="margin-right:0.2778em;"></span><span class="mrel">â</span><span class="mspace" style="margin-right:0.2778em;"></span></span><span class="base"><span class="strut" style="height:0.6833em;"></span><span class="mord mathcal">R</span></span></span></span>â, we use the shorter form âthe instance <span class="katex"><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.5806em;vertical-align:-0.15em;"></span><span class="mord"><span class="mord mathnormal">x</span><span class="msupsub"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:0.3011em;"><span style="top:-2.55em;margin-left:0em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight">1</span></span></span></span><span class="vlist-s">â</span></span><span class="vlist-r"><span class="vlist" style="height:0.15em;"><span></span></span></span></span></span></span></span></span></span> is <strong>satisfiable</strong>â. 231Note that the relation which <span class="katex"><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.5806em;vertical-align:-0.15em;"></span><span class="mord"><span class="mord mathnormal">x</span><span class="msupsub"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:0.3011em;"><span style="top:-2.55em;margin-left:0em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight">1</span></span></span></span><span class="vlist-s">â</span></span><span class="vlist-r"><span class="vlist" style="height:0.15em;"><span></span></span></span></span></span></span></span></span></span> satisfies isnât explicitly stated and must be made clear from the context.</p> 232<p>We can collect all the satisfiable instances of a relation in a set:</p> 233<ul> 234<li>the <strong>language</strong> defined by a relation <span class="katex"><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.6833em;"></span><span class="mord mathcal">R</span></span></span></span> is the set of all satisfiable instances for <span class="katex"><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.6833em;"></span><span class="mord mathcal">R</span></span></span></span>. 235We often write <span class="katex"><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathcal">L</span><span class="mopen">(</span><span class="mord mathcal">R</span><span class="mclose">)</span></span></span></span> or <span class="katex"><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.8333em;vertical-align:-0.15em;"></span><span class="mord"><span class="mord mathcal">L</span><span class="msupsub"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:0.3283em;"><span style="top:-2.55em;margin-left:0em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mathcal mtight">R</span></span></span></span><span class="vlist-s">â</span></span><span class="vlist-r"><span class="vlist" style="height:0.15em;"><span></span></span></span></span></span></span></span></span></span>.</li> 236</ul> 237<blockquote> 238<p><strong>Example: factors.</strong>
239As we have seen, <span class="katex"><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.6444em;"></span><span class="mord">6</span></span></span></span> and <span class="katex"><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.6444em;"></span><span class="mord">16</span></span></span></span> are in <span class="katex"><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathcal">L</span><span class="mopen">(</span><span class="mord"><span class="mord mathcal">R</span><span class="msupsub"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:0.3361em;"><span style="top:-2.55em;margin-left:0em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord text mtight"><span class="mord mtight">factors</span></span></span></span></span><span class="vlist-s">â</span></span><span class="vlist-r"><span class="vlist" style="height:0.15em;"><span></span></span></span></span></span></span><span class="mclose">)</span></span></span></span>. 240On the other hand, prime numbers such as <span class="katex"><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.6444em;"></span><span class="mord">5</span></span></span></span> or <span class="katex"><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.6444em;"></span><span class="mord">7</span></span></span></span> cannot be expressed as a product of integers. 241Therefore, they are not in <span class="katex"><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathcal">L</span><span class="mopen">(</span><span class="mord"><span class="mord mathcal">R</span><span class="msupsub"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:0.3361em;"><span style="top:-2.55em;margin-left:0em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord text mtight"><span class="mord mtight">factors</span></span></span></span></span><span class="vlist-s">â</span></span><span class="vlist-r"><span class="vlist" style="height:0.15em;"><span></span></span></span></span></span></span><span class="mclose">)</span></span></span></span>.</p> 242<p>Once again we can rephrase Statement 2 in terms of the language defined by <span class="katex"><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.8333em;vertical-align:-0.15em;"></span><span class="mord"><span class="mord mathcal">R</span><span class="msupsub"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:0.3361em;"><span style="top:-2.55em;margin-left:0em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord text mtight"><span class="mord mtight">factors</span></span></span></span></span><span class="vlist-s">â</span></span><span class="vlist-r"><span class="vlist" style="height:0.15em;"><span></span></span></span></span></span></span></span></span></span>:</p> 243<ul> 244<li><strong>Statement 2</strong> (with jargon, part 2): <span class="katex"><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.6444em;"></span><span class="mord">25890323</span></span></span></span> is in <span class="katex"><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathcal">L</span><span class="mopen">(</span><span class="mord"><span class="mord mathcal">R</span><span class="msupsub"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:0.3361em;"><span style="top:-2.55em;margin-left:0em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord text mtight"><span class="mord mtight">factors</span></span></span></span></span><span class="vlist-s">â</span></span><span class="vlist-r"><span class="vlist" style="height:0.15em;"><span></span></span></span></span></span></span><span class="mclose">)</span></span></span></span>.</li> 245</ul> 246</blockquote> 247<p><strong>Answer #2 (same as before, in jargon): proving means giving evidence that an instance is indeed in the language defined by some relation <span class="katex"><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.6833em;"></span><span class="mord mathcal">R</span></span></span></span>.</strong></p> 248<p><strong>More examples.</strong> 249As an exercise, try to cast a Sudoku as a relation and identify the instance, witness and language. 250What about the relation <span class="katex"><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.9694em;vertical-align:-0.2861em;"></span><span class="mord"><span class="mord mathcal">R</span><span class="msupsub"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:0.3361em;"><span style="top:-2.55em;margin-left:0em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mathnormal mtight" style="margin-right:0.10764em;">f</span></span></span></span><span class="vlist-s">â</span></span><span class="vlist-r"><span class="vlist" style="height:0.2861em;"><span></span></span></span></span></span></span></span></span></span>, defined for some function <span class="katex"><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.8889em;vertical-align:-0.1944em;"></span><span class="mord mathnormal" style="margin-right:0.10764em;">f</span></span></span></span> as all pairs <span class="katex"><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mopen">(</span><span class="mord mathnormal">x</span><span class="mpunct">,</span><span class="mspace" style="margin-right:0.1667em;"></span><span class="mord mathnormal" style="margin-right:0.02691em;">w</span><span class="mclose">)</span></span></span></span> such that <span class="katex"><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.4306em;"></span><span class="mord mathnormal">x</span><span class="mspace" style="margin-right:0.2778em;"></span><span class="mrel">=</span><span class="mspace" style="margin-right:0.2778em;"></span></span><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathnormal" style="margin-right:0.10764em;">f</span><span class="mopen">(</span><span class="mord mathnormal" style="margin-right:0.02691em;">w</span><span class="mclose">)</span></span></span></span>? 251What happens when we pick <span class="katex"><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.8889em;vertical-align:-0.1944em;"></span><span class="mord mathnormal" style="margin-right:0.10764em;">f</span></span></span></span> to be <em>(i)</em> a polynomial or <em>(ii)</em> a hash function?</p> 252<hr /> 253<h2 id="up-next-probabilistic-and-interactive-proofs"><a class="header" href="#up-next-probabilistic-and-interactive-proofs">Up next: probabilistic and interactive proofs</a></h2> 254<p>So far we have only considered the trivial proof system: sending the witness.</p> 255<p>In some cases, this is not desirable. 256Sometimes the witness is private and should remain so. 257Other times, the witness is just too big to be sent or for the verifier to process. 258These cases motivate the need for more elaborate (and powerful) proof systems. 259We discuss these systems more formally in the next article.</p> 260 261 </main> 262 263 <nav class="nav-wrapper" aria-label="Page navigation"> 264 <!-- Mobile navigation buttons --> 265 <a rel="prev" href="../foreword.html" class="mobile-nav-chapter
265s previous" title="Previous chapter" aria-label="Previous chapter" aria-keyshortcuts="Left"> 266 <i class="fa fa-angle-left"></i> 267 </a> 268 269 <a rel="next prefetch" href="../intro_to_zk/interactive_proofs.html" class="mobile-nav-chapters next" title="Next chapter" aria-label="Next chapter" aria-keyshortcuts="Right"> 270 <i class="fa fa-angle-right"></i> 271 </a> 272 273 <div style="clear: both"></div> 274 </nav> 275 </div> 276 </div> 277 278 <nav class="nav-wide-wrapper" aria-label="Page navigation"> 279 <a rel="prev" href="../foreword.html" class="nav-chapters previous" title="Previous chapter" aria-label="Previous chapter" aria-keyshortcuts="Left"> 280 <i class="fa fa-angle-left"></i> 281 </a> 282 283 <a rel="next prefetch" href="../intro_to_zk/interactive_proofs.html" class="nav-chapters next" title="Next chapter" aria-label="Next chapter" aria-keyshortcuts="Right"> 284 <i class="fa fa-angle-right"></i> 285 </a> 286 </nav> 287 288 </div> 289 290 291 292 293
293<script> 294 window.playground_copyable = true; 295 </script>
295 296 297 298
298<script src="../elasticlunr.min.js"></script>
298 299
299<script src="../mark.min.js"></script>
299 300
300<script src="../searcher.js"></script>
300 301 302
302<script src="../clipboard.min.js"></script>
302 303
303<script src="../highlight.js"></script>
303 304
304<script src="../book.js"></script>
304 305 306 <!-- Custom JS scripts --> 307 308 309 </div> 310 </body> 311</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.