<!DOCTYPE HTML>
<html lang="en" class="sidebar-visible no-js light">
<head>
<!-- Book generated using mdBook -->
<meta charset="UTF-8">
<title>Polynomial Commitment - Zero Network Documentation</title>
<!-- Custom HTML head -->
<meta content="text/html; charset=utf-8" http-equiv="Content-Type">
<meta name="description" content="">
<meta name="viewport" content="width=device-width, initial-scale=1">
<meta name="theme-color" content="#ffffff" />
<link rel="icon" href="favicon.svg">
<link rel="shortcut icon" href="favicon.png">
<link rel="stylesheet" href="css/variables.css">
<link rel="stylesheet" href="css/general.css">
<link rel="stylesheet" href="css/chrome.css">
<link rel="stylesheet" href="css/print.css" media="print">
<!-- Fonts -->
<link rel="stylesheet" href="FontAwesome/css/font-awesome.css">
<link rel="stylesheet" href="fonts/fonts.css">
<!-- Highlight.js Stylesheets -->
<link rel="stylesheet" href="highlight.css">
<link rel="stylesheet" href="tomorrow-night.css">
<link rel="stylesheet" href="ayu-highlight.css">
<!-- Custom theme stylesheets -->
<!-- MathJax -->
<script async src="https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.1/MathJax.js?config=TeX-AMS-MML_HTMLorMML"></script>
</head>
<body>
<!-- Provide site root to javascript -->
<script>
var path_to_root = "";
var default_theme = window.matchMedia("(prefers-color-scheme: dark)").matches ? "navy" : "light";
</script>
<!-- Work around some values being stored in localStorage wrapped in quotes -->
<script>
try {
var theme = localStorage.getItem('mdbook-theme');
var sidebar = localStorage.getItem('mdbook-sidebar');
if (theme.startsWith('"') && theme.endsWith('"')) {
localStorage.setItem('mdbook-theme', theme.slice(1, theme.length - 1));
}
if (sidebar.startsWith('"') && sidebar.endsWith('"')) {
localStorage.setItem('mdbook-sidebar', sidebar.slice(1, sidebar.length - 1));
}
} catch (e) { }
</script>
<!-- Set the theme before any content is loaded, prevents flash -->
<script>
var theme;
try { theme = localStorage.getItem('mdbook-theme'); } catch(e) { }
if (theme === null || theme === undefined) { theme = default_theme; }
var html = document.querySelector('html');
html.classList.remove('no-js')
html.classList.remove('light')
html.classList.add(theme);
html.classList.add('js');
</script>
<!-- Hide / unhide sidebar before it is displayed -->
<script>
var html = document.querySelector('html');
var sidebar = 'hidden';
if (document.body.clientWidth >= 1080) {
try { sidebar = localStorage.getItem('mdbook-sidebar'); } catch(e) { }
sidebar = sidebar || 'visible';
}
html.classList.remove('sidebar-visible');
html.classList.add("sidebar-" + sidebar);
</script>
<nav id="sidebar" class="sidebar" aria-label="Table of contents">
<div class="sidebar-scrollbox">
<ol class="chapter"><li class="chapter-item expanded "><a href="0_0_zero_network.html"><strong aria-hidden="true">1.</strong> Zero Network</a></li><li class="chapter-item expanded "><a href="1_0_overview.html"><strong aria-hidden="true">2.</strong> Overview</a></li><li><ol class="section"><li class="chapter-item expanded "><a href="1_1_what_is_privacy.html"><strong aria-hidden="true">2.1.</strong> What is Privacy</a></li><li class="chapter-item expanded "><a href="1_2_hide_transfer_amount.html"><strong aria-hidden="true">2.2.</strong> Hide Transfer Amount</a></li><li class="chapter-item expanded "><a href="1_3_gas_limit.html"><strong aria-hidden="true">2.3.</strong> Gas Limit</a></li><li class="chapter-item expanded "><a href="1_4_zero_knowledge_scheme.html"><strong aria-hidden="true">2.4.</strong> Zero Knowledge Scheme</a></li><li class="chapter-item expanded "><a href="1_5_transaction_constraints.html"><strong aria-hidden="true">2.5.</strong> Transaction Constraints</a></li></ol></li><li class="chapter-item expanded "><a href="2_0_transaction_constraints.html"><strong aria-hidden="true">3.</strong> Transaction Constraints</a></li><li><ol class="section"><li class="chapter-item expanded "><a href="2_1_confidential_transfer.html"><strong aria-hidden="true">3.1.</strong> Confidential Transfer</a></li><li class="chapter-item expanded "><a href="2_2_confidential_smart_contract.html"><strong aria-hidden="true">3.2.</strong> Confidential Smart Contract</a></li></ol></li><li class="chapter-item expanded "><a href="3_0_primitive.html"><strong aria-hidden="true">4.</strong> Primitive</a></li><li><ol class="section"><li class="chapter-item expanded "><a href="3_1_crypto.html"><strong aria-hidden="true">4.1.</strong> Crypto</a></li><li class="chapter-item expanded "><a href="3_2_jubjub.html"><strong aria-hidden="true">4.2.</strong> Jubjub</a></li><li class="chapter-item expanded "><a href="3_3_bls12_381.html"><strong aria-hidden="true">4.3.</strong> Bls12 381</a></li><li class="chapter-item expanded "><a href="3_4_elgamal.html"><strong aria-hidden="true">4.4.</strong> ElGamal</a></li><li class="chapter-item expanded "><a href="3_5_pairing.html"><strong aria-hidden="true">4.5.</strong> Pairing</a></li></ol></li><li class="chapter-item expanded "><a href="4_0_pallet.html"><strong aria-hidden="true">5.</strong> Pallet</a></li><li><ol class="section"><li class="chapter-item expanded "><a href="4_1_plonk.html"><strong aria-hidden="true">5.1.</strong> Plonk</a></li><li class="chapter-item expanded "><a href="4_2_encrypted_balance.html"><strong aria-hidden="true">5.2.</strong> Encrypted Balance</a></li><li class="chapter-item expanded "><a href="4_3_confidential_transfer.html"><strong aria-hidden="true">5.3.</strong> Confidential Transfer</a></li></ol></li><li class="chapter-item expanded "><a href="5_0_related_tools.html"><strong aria-hidden="true">6.</strong> Related Tools</a></li><li><ol class="section"><li class="chapter-item expanded "><a href="5_1_stealth_address.html"><strong aria-hidden="true">6.1.</strong> Stealth Address</a></li><li class="chapter-item expanded "><a href="5_2_pedersen_commitment.html"><strong aria-hidden="true">6.2.</strong> Pedersen Commitment</a></li><li class="chapter-item expanded "><a href="5_3_non_interactive_zero_knowlege_proof.html"><strong aria-hidden="true">6.3.</strong> Non Interactive Zero Knowledge Proof</a></li><li><ol class="section"><li class="chapter-item expanded "><a href="5_3_1_qap.html"><strong aria-hidden="true">6.3.1.</strong> QAP</a></li><li class="chapter-item expanded "><a href="5_3_2_polynomial_commitment.html" class="active"><strong aria-hidden="true">6.3.2.</strong> Polynomial Commitment</a></li><li class="chapter-item expanded "><a href="5_3_3_homomorphic_encryption.html"><strong aria-hidden="true">6.3.3.</strong> Homomorphic Encryption</a></li></ol></li></ol></li><li class="chapter-item expanded "><a href="6_0_tutorial.html"><strong aria-hidden="true">7.</strong> Tutorial</a></li><li><ol class="section"><li class="chapter-item expanded "><a href="6_1_plonk_pallet.html"><strong aria-hidden="true">7.1.</strong> pallet-plonk</a></li><li class="chapter-item expanded "><a href="6_2_confidential_transfer.html"><strong aria-hidden="true">7.2.</strong> confidential_transfer</a></li></ol></li><li class="chapter-item expanded "><a href="7_0_frequent_errors.html"><strong aria-hidden="true">8.</strong> Frequent Errors</a></li></ol>
</div>
<div id="sidebar-resize-handle" class="sidebar-resize-handle"></div>
</nav>
<div id="page-wrapper" class="page-wrapper">
<div class="page">
<div id="menu-bar-hover-placeholder"></div>
<div id="menu-bar" class="menu-bar sticky bordered">
<div class="left-buttons">
<button id="sidebar-toggle" class="icon-button" type="button" title="Toggle Table of Contents" aria-label="Toggle Table of Contents" aria-controls="sidebar">
<i class="fa fa-bars"></i>
</button>
<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">
<i class="fa fa-paint-brush"></i>
</button>
<ul id="theme-list" class="theme-popup" aria-label="Themes" role="menu">
<li role="none"><button role="menuitem" class="theme" id="light">Light (default)</button></li>
<li role="none"><button role="menuitem" class="theme" id="rust">Rust</button></li>
<li role="none"><button role="menuitem" class="theme" id="coal">Coal</button></li>
<li role="none"><button role="menuitem" class="theme" id="navy">Navy</button></li>
<li role="none"><button role="menuitem" class="theme" id="ayu">Ayu</button></li>
</ul>
<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">
<i class="fa fa-search"></i>
</button>
</div>
<h1 class="menu-title">Zero Network Documentation</h1>
<div class="right-buttons">
<a href="print.html" title="Print this book" aria-label="Print this book">
<i id="print-button" class="fa fa-print"></i>
</a>
</div>
</div>
<div id="search-wrapper" class="hidden">
<form id="searchbar-outer" class="searchbar-outer">
<input type="search" id="searchbar" name="searchbar" placeholder="Search this book ..." aria-controls="searchresults-outer" aria-describedby="searchresults-header">
</form>
<div id="searchresults-outer" class="searchresults-outer hidden">
<div id="searchresults-header" class="searchresults-header"></div>
<ul id="searchresults">
</ul>
</div>
</div>
<!-- Apply ARIA attributes after the sidebar and the sidebar toggle button are added to the DOM -->
<script>
document.getElementById('sidebar-toggle').setAttribute('aria-expanded', sidebar === 'visible');
document.getElementById('sidebar').setAttribute('aria-hidden', sidebar !== 'visible');
Array.from(document.querySelectorAll('#sidebar a')).forEach(function(link) {
link.setAttribute('tabIndex', sidebar === 'visible' ? 0 : -1);
});
</script>
<div id="content" class="content">
<main>
<h1 id="polynomial-commitment"><a class="header" href="#polynomial-commitment">Polynomial Commitment</a></h1>
<p>In previous <a href="3_1_qap.html">section</a>, we enable to check whether <code>computation</code> was done correctly by the knowledge of polynomial which can be devided by minimal polynomial <code>Z(x)</code> as following.</p>
<p>$$ L(x) * R(x) - O(x) = Z(x) * T(x) $$</p>
<p>However, we can create equation easily because <code>Z(x)</code> is public information. Then we need to verify whether <code>L(x), R(x), O(x)</code> are created by using valid input. To do so, we are going to use <code>Polynomial Commitment</code>.</p>
<h2 id="abstract"><a class="header" href="#abstract">Abstract</a></h2>
<p>The <code>Polynomial Commitment</code> check whether the prover know polynomials <code>L(x), R(x), O(x)</code> and these comes from valid input.</p>
<h2 id="details"><a class="header" href="#details">Details</a></h2>
<p>To know polynomials <code>L(x), R(x), O(x)</code> means having knowledge of coefficients of them.</p>
<h2 id="combination"><a class="header" href="#combination">Combination</a></h2>
<p>First of all, we combine these polynomials to one in order to make check process easier. Let's say degree of polynomials <code>L(x), R(x), O(x)</code> as <code>d</code>, we can combine them into one as following and let combined polynomial as <code>F(x)</code>.</p>
<p>$$ L(x) + R(x) * X^{d+1} + O(x) * X^{2d+1} = F(x) $$</p>
<p>In polynomial <code>F(x)</code>, the coefficients of <code>0~d</code> degree expresses <code>L(x)</code> coefficients, <code>d+1~2d</code> is <code>R(x)</code> and <code>2d+1~3d</code> is <code>O(x)</code> as well. The polynomial <code>F(x)</code> degree is <code>3d</code> and when we denote coefficients as k, it would be following.</p>
<p>$$ F(x) = k_0 + k_1X + k_2X^2 + ... + k_{3d}X^{3d} $$</p>
<h2 id="verification"><a class="header" href="#verification">Verification</a></h2>
<p>The verification processes are following.</p>
<ol>
<li>Bob choses random <code>α, (a_0,...,a_{3d}) ∈ F</code> and compute <code>(b_0,...,b_{3d}) = α(a_0,...,a_{3d})</code>.</li>
<li>Bob sends Alice to <code>(a_0,...,a_{3d})</code> and <code>(b_0,...,b_{3d})</code>.</li>
<li>Alice computes following.
$$ (\acute a_0,...,\acute a_{3d}, \acute b_0,...,\acute b_{3d}) = (a_0 * k_0,...,a_{3d} * k_{3d}, b_0 * k_0,...,b_{3d} * k_{3d}) $$</li>
<li>Bob checks following.
$$ (\acute a_0,...,\acute a_{3d}) = α(\acute b_0,...,\acute b_{3d}) $$</li>
</ol>
<p>If Alice don't know the coefficients, she couldn't do step <code>3</code>. With using this step, we can know that the prover know polynomials <code>L(x), R(x), O(x)</code> and these comes from valid input.</p>
<h2 id="next"><a class="header" href="#next">Next</a></h2>
<p>In this section, we understood how to check the prover polynomials comming from valid input but these information would be known by verifier. To hide these information from verifier, we are using homomorphic encryption.</p>
</main>
<nav class="nav-wrapper" aria-label="Page navigation">
<!-- Mobile navigation buttons -->
<a rel="prev" href="5_3_1_qap.html" class="mobile-nav-chapters previous" title="Previous chapter" aria-label="Previous chapter" aria-keyshortcuts="Left">
<i class="fa fa-angle-left"></i>
</a>
<a rel="next" href="5_3_3_homomorphic_encryption.html" class="mobile-nav-chapters next" title="Next chapter" aria-label="Next chapter" aria-keyshortcuts="Right">
<i class="fa fa-angle-right"></i>
</a>
<div style="clear: both"></div>
</nav>
</div>
</div>
<nav class="nav-wide-wrapper" aria-label="Page navigation">
<a rel="prev" href="5_3_1_qap.html" class="nav-chapters previous" title="Previous chapter" aria-label="Previous chapter" aria-keyshortcuts="Left">
<i class="fa fa-angle-left"></i>
</a>
<a rel="next" href="5_3_3_homomorphic_encryption.html" class="nav-chapters next" title="Next chapter" aria-label="Next chapter" aria-keyshortcuts="Right">
<i class="fa fa-angle-right"></i>
</a>
</nav>
</div>
<script>
window.playground_copyable = true;
</script>
<script src="elasticlunr.min.js" charset="utf-8"></script>
<script src="mark.min.js" charset="utf-8"></script>
<script src="searcher.js" charset="utf-8"></script>
<script src="clipboard.min.js" charset="utf-8"></script>
<script src="highlight.js" charset="utf-8"></script>
<script src="book.js" charset="utf-8"></script>
<!-- Custom JS scripts -->
</body>
</html>
