mirror of
https://github.com/geometryxyz/semacaulk.git
synced 2026-01-15 00:08:17 -05:00
431 lines
26 KiB
HTML
431 lines
26 KiB
HTML
<!DOCTYPE HTML>
|
|
<html lang="en" class="sidebar-visible no-js light">
|
|
<head>
|
|
<!-- Book generated using mdBook -->
|
|
<meta charset="UTF-8">
|
|
<title>Cryptographic Specification - Semacaulk</title>
|
|
|
|
|
|
<!-- Custom HTML head -->
|
|
|
|
<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="overview.html"><strong aria-hidden="true">1.</strong> Overview</a></li><li class="chapter-item expanded "><a href="quick_start.html"><strong aria-hidden="true">2.</strong> Quick start</a></li><li class="chapter-item expanded "><a href="trusted_setup.html"><strong aria-hidden="true">3.</strong> Trusted Setup</a></li><li class="chapter-item expanded "><a href="cryptographic_specification.html" class="active"><strong aria-hidden="true">4.</strong> Cryptographic Specification</a></li><li><ol class="section"><li class="chapter-item expanded "><a href="system_invariants.html"><strong aria-hidden="true">4.1.</strong> System invariants</a></li><li class="chapter-item expanded "><a href="insertion.html"><strong aria-hidden="true">4.2.</strong> Insertion</a></li><li class="chapter-item expanded "><a href="circuit_and_gates.html"><strong aria-hidden="true">4.3.</strong> The Circuit and Gates</a></li><li class="chapter-item expanded "><a href="precomputation_and_updates.html"><strong aria-hidden="true">4.4.</strong> Precomputation and updates</a></li><li class="chapter-item expanded "><a href="fiat_shamir_transcript.html"><strong aria-hidden="true">4.5.</strong> The Fiat-Shamir Transcript</a></li><li class="chapter-item expanded "><a href="proof_generation.html"><strong aria-hidden="true">4.6.</strong> Proof generation</a></li><li class="chapter-item expanded "><a href="verification.html"><strong aria-hidden="true">4.7.</strong> Proof verification</a></li></ol></li><li class="chapter-item expanded "><a href="lagrange_basis_polynomial_commitment_tree.html"><strong aria-hidden="true">5.</strong> The Lagrange Basis Polynomial Commitment Tree</a></li><li class="chapter-item expanded "><a href="mechanism_of_operation.html"><strong aria-hidden="true">6.</strong> Mechanism of Operation</a></li><li class="chapter-item expanded "><a href="ethereum_contracts.html"><strong aria-hidden="true">7.</strong> Ethereum contracts</a></li><li><ol class="section"><li class="chapter-item expanded "><a href="gas_costs.html"><strong aria-hidden="true">7.1.</strong> Gas costs</a></li></ol></li><li class="chapter-item expanded "><a href="performance_benchmarks.html"><strong aria-hidden="true">8.</strong> Performance and Benchmarks</a></li><li class="chapter-item expanded "><a href="credits.html"><strong aria-hidden="true">9.</strong> Credits</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</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">Semacaulk</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>
|
|
<link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/katex@0.12.0/dist/katex.min.css" integrity="sha384-AfEj0r4/OFrOo5t7NnNe46zW/tFgW6x/bCJG8FqQCEo3+Aro6EYUG4+cU+KJWu/X" crossorigin="anonymous">
|
|
<h1 id="cryptographic-specification"><a class="header" href="#cryptographic-specification">Cryptographic Specification</a></h1>
|
|
<p>Some of the terminology, symbols, and language has been borrowed from and
|
|
inspired by the <a href="https://zcash.github.io/halo2">Halo2 Book</a> and the <a href="https://hackmd.io/AP6zPSgtThWxx6pjXY7R8A">MACI 1.0
|
|
Audit Specification</a>.</p>
|
|
<h2 id="notation"><a class="header" href="#notation">Notation</a></h2>
|
|
<ul>
|
|
<li>Accumulator: an elliptic curve point which is a commitment to \(t\) field
|
|
elements.</li>
|
|
<li>\(t\): the maximum capacity of the accumulator.</li>
|
|
<li>Zero value: the nothing-up-my-sleeve value (see 2).</li>
|
|
<li>Elliptic curve multiplication: in this specification, we use the dot operator
|
|
\(\cdot\) to denote scalar multiplication of an elliptic curve point.</li>
|
|
</ul>
|
|
<h2 id="cryptographic-primitives"><a class="header" href="#cryptographic-primitives">Cryptographic primitives</a></h2>
|
|
<h3 id="1-the-bn254-curve"><a class="header" href="#1-the-bn254-curve">1. The BN254 curve</a></h3>
|
|
<p>The current implementation of Semacaulk uses the BN254 curve which Ethereum
|
|
supports in its elliptic curve addition, scalar multiplication, and
|
|
pairing-check precompiles as defined in
|
|
<a href="https://eips.ethereum.org/EIPS/eip-196">EIP-196</a> and
|
|
<a href="https://eips.ethereum.org/EIPS/eip-197">EIP-197</a>. </p>
|
|
<h4 id="11-the-bn254-scalar-field"><a class="header" href="#11-the-bn254-scalar-field">1.1. The BN254 scalar field</a></h4>
|
|
<p>The BN254 scalar field \(\mathbb{F}_r\) is:</p>
|
|
<pre><code>21888242871839275222246405745257275088548364400416034343698204186575808495617
|
|
</code></pre>
|
|
<h4 id="12-the-bn254-scalar-field"><a class="header" href="#12-the-bn254-scalar-field">1.2. The BN254 scalar field</a></h4>
|
|
<p>The BN254 prime field \(\mathbb{F}_q\) is:</p>
|
|
<pre><code>21888242871839275222246405745257275088696311157297823662689037894645226208583
|
|
</code></pre>
|
|
<h4 id="13-the-mathbbg_1-group"><a class="header" href="#13-the-mathbbg_1-group">1.3. The \(\mathbb{G}_1\) group</a></h4>
|
|
<p>The group \(\mathbb{G}_1\) defined on BN254 has the generator point \(g_1 =
|
|
(1, 2)\).</p>
|
|
<h4 id="14-the-mathbbg_2-point"><a class="header" href="#14-the-mathbbg_2-point">1.4. The \(\mathbb{G}_2\) point</a></h4>
|
|
<p>The group \(\mathbb{G}_2\) defined on BN254 has the generator point \(g_2 =
|
|
(x_0 * i + x_1, y_0 * i + y_1)\) where:</p>
|
|
<ul>
|
|
<li>\(x_0\) equals <code>11559732032986387107991004021392285783925812861821192530917403151452391805634</code></li>
|
|
<li>\(x_1\) equals <code>10857046999023057135944570762232829481370756359578518086990519993285655852781</code></li>
|
|
<li>\(y_0\) equals <code>4082367875863433681332203403145435568316851327593401208105741076214120093531</code></li>
|
|
<li>\(y_1\) equals <code>8495653923123431417604973247489272438418190587263600148770280649306958101930</code></li>
|
|
</ul>
|
|
<h3 id="2-the-nothing-up-my-sleeve-value"><a class="header" href="#2-the-nothing-up-my-sleeve-value">2. The nothing-up-my-sleeve value</a></h3>
|
|
<p>The nothing-up-my-sleeve (NUMS) value is:</p>
|
|
<pre><code class="language-bash">14233191614411629788649003849761857673160358990904722769695641636673172216357
|
|
</code></pre>
|
|
<p>It is the Keccak256 hash of the bytestring <code>Semacaulk</code>, modulo
|
|
\(\mathbb{F}_r\). To compute it, run the following in a NodeJS console where
|
|
<code>e</code> is an instance of Ethers.js 5.0:</p>
|
|
<pre><code class="language-js">(
|
|
BigInt(e.utils.solidityKeccak256(['string'], ['Semacaulk'])) %
|
|
BigInt('21888242871839275222246405745257275088548364400416034343698204186575808495617')
|
|
).toString(10)
|
|
</code></pre>
|
|
<p>Due to the second-image resistance property of the Keccak256 hash function,
|
|
anyone can be assured that no-one knows any other preimage to the NUMS value.
|
|
It follows that no-one knows the MiMC7 preimage to the NUMS value.</p>
|
|
<h3 id="3-the-structured-reference-string-srs"><a class="header" href="#3-the-structured-reference-string-srs">3. The structured reference string (SRS)</a></h3>
|
|
<p>Semacaulk's structured reference string (SRS) consists of an ordered list of
|
|
\(2^n + 1\) \(\mathbb{G}_1\) points and \(2^n\) \(\mathbb{G}_2\)
|
|
points, where the maximum capacity of the accumulator is \(2^n = t\).</p>
|
|
<p>We assume the existence of a secret and unknown value \(\tau\) which can be
|
|
generated using a <a href="https://eprint.iacr.org/2017/1050.pdf">securely run trusted
|
|
setup</a>.</p>
|
|
<p>These points are defined as such:</p>
|
|
<ul>
|
|
<li>\(\mathsf{srs\_g1}\): \([g_1, g_1 \cdot {\tau}, \ldots, g_1 \cdot {\tau \cdot {t + 1}}]\)</li>
|
|
<li>\(\mathsf{srs\_g2}\): \([g_2, g_2 \cdot {\tau}, \ldots, g_2 \cdot {\tau \cdot {t + 1}}]\)</li>
|
|
</ul>
|
|
<p>Where \(g_1\) is defined in 1.3 and \(g_2\) is defined in 1.4.</p>
|
|
<h3 id="4-the-mimc7-hash-function"><a class="header" href="#4-the-mimc7-hash-function">4. The MiMC7 hash function</a></h3>
|
|
<p>Semacaulk currently uses the MiMC7 hash function to compute identity
|
|
commitments and nullifier hashes. While other possibly more secure hash
|
|
functions like Poseidon are possible, we chose MiMC7 only because of its
|
|
simplicity of implementation for our purposes of delivering a proof-of-concept.</p>
|
|
<p>The MiMC7 has function is defined
|
|
<a href="https://iden3-docs.readthedocs.io/en/latest/_downloads/a04267077fb3fdbf2b608e014706e004/Ed-DSA.pdf">here</a>.</p>
|
|
<p>Our instantiation of the MiMC7 hash function for the BN254 curve uses the
|
|
following constants:</p>
|
|
<ul>
|
|
<li>\(n = 91\)</li>
|
|
<li>\(\mathsf{MIMC\_SEED} =\) <code>mimc</code> (the hexidecimal array <code>[0x6d, 0x69, 0x6d, 0x63]</code>)</li>
|
|
</ul>
|
|
<h4 id="41-the-mimc7-round-constants"><a class="header" href="#41-the-mimc7-round-constants">4.1. The MiMC7 round constants</a></h4>
|
|
<p>Given the BN254 scalar field \(\mathbb{F}_r\), we first define 91 round
|
|
constants (denoted as \(\mathsf{cts}\)) using the algorithm implemented in
|
|
<a href="https://github.com/iden3/circomlibjs/blob/ee8ec2fca2ca7f16dec9d0f39d57dbe80dd18870/src/mimc7.js#L29"><code>circomlibjs/src/mimc7.js</code></a>
|
|
and
|
|
<a href="https://github.com/geometryresearch/semacaulk/blob/main/src/mimc7.rs#L65"><code>semacaulk/src/mimc7.rs</code></a>.</p>
|
|
<p>The algorithm is as such:</p>
|
|
<ul>
|
|
<li>The first round constant is \(0\).</li>
|
|
<li>The next round constant is the Keccak256 hash of \(\mathsf{MIMC\_SEED} =\),
|
|
modulo the field order of \(\mathbb{F}_r\).</li>
|
|
<li>Each subsequent round constant is the Keccak256 hash of the previous one,
|
|
modulo the field order of \(\mathbb{F}_r\).</li>
|
|
</ul>
|
|
<h4 id="42-the-mimc7-hash-algorithm"><a class="header" href="#42-the-mimc7-hash-algorithm">4.2. The MiMC7 <code>hash</code> algorithm</a></h4>
|
|
<p>To hash a single field element \(x\), we use the <code>hash()</code> algorithm. The inputs to
|
|
<code>hash()</code> are \(x\) and a key \(k\).</p>
|
|
<ol>
|
|
<li>Compute the first round digest \(\mathsf{rd[0]} = (x + k) ^ 7\).</li>
|
|
<li>Compute the next \(n - 1\) round digests such that
|
|
\(\mathsf{rd}[i] = (\mathsf{rd}[i - 1] + \mathsf{cts}[i] + k) ^ 7\)</li>
|
|
<li>Return \(\mathsf{rd}[n - 1] + k\).</li>
|
|
</ol>
|
|
<h4 id="43-the-mimc7-multi_hash-algorithm"><a class="header" href="#43-the-mimc7-multi_hash-algorithm">4.3. The MiMC7 <code>multi_hash</code> algorithm</a></h4>
|
|
<p>To hash multiple field elements \(x_0, \ldots, x_n\), we use the <code>multi_hash()</code>
|
|
algorithm. The inputs to <code>multi_hash()</code> are the array of said field elements
|
|
and a key \(k\).</p>
|
|
<ol>
|
|
<li>
|
|
<p>Initialise \(r\) to equal \(k\).</p>
|
|
</li>
|
|
<li>
|
|
<p>For each \(x_i\):</p>
|
|
<p>a. Set \(h_i = \mathsf{hash}(x_i, r)\).</p>
|
|
<p>b. Set \(r = x_i + h_i\).</p>
|
|
</li>
|
|
<li>
|
|
<p>Return \(r\).</p>
|
|
</li>
|
|
</ol>
|
|
<h5 id="431-multi_hash-with-two-field-elements"><a class="header" href="#431-multi_hash-with-two-field-elements">4.3.1 <code>multi_hash</code> with two field elements</a></h5>
|
|
<p>It is useful to describe the <code>multi_hash</code> algorithm for two input elements in
|
|
individual steps because the Semacaulk circuit construction (see <a href="./circuit_and_gates.html">The Circuit
|
|
and Gates</a>) makes use of its intermediate states.</p>
|
|
<p>Given inputs \(a\) and \(b\):</p>
|
|
<ol>
|
|
<li>Set \(r\) as 0.</li>
|
|
<li>Set \(h_0 = \mathsf{hash}(a, r)\).</li>
|
|
<li>Set \(r = r + a + h_0\).</li>
|
|
<li>Set \(h_1 = \mathsf{hash}(b, r)\).</li>
|
|
<li>Return \(r + b + h_1\).</li>
|
|
</ol>
|
|
<p>Note that in step 4, the key is \(a + h_0 = \mathsf{hash}(a, 0)\). This fact
|
|
is crucial to understanding how the circuit construction works.</p>
|
|
<h3 id="5-kzg-commitments"><a class="header" href="#5-kzg-commitments">5. KZG commitments</a></h3>
|
|
<p>Semcaulk uses the KZG commitment scheme described in
|
|
<a href="https://www.iacr.org/archive/asiacrypt2010/6477178/6477178.pdf">KZG10</a>.</p>
|
|
<p>Given an array of \(t\) values \([m_0, \ldots, m_t]\), we interpolate to
|
|
derive the polynomial \(\phi\) such that \(\phi(i) = m_i\).</p>
|
|
<p>Knowing \(\phi\) with \(l\) coefficients \([\phi_0, \ldots, \phi_{l -
|
|
1}]\), one can use \(\mathsf{srs\_g1}\) to produce a commitment in the form
|
|
of a \(\mathbb{G}_1\) point, or \(\mathsf{srs\_g2}\) to produce a
|
|
commitment in the form of a \(\mathbb{G}_2\) point.</p>
|
|
<p>\(\mathsf{commit}(\phi, \mathsf{srs}) = \sum_{i=1}^{l} \mathsf{srs}[i] \cdot \phi_i \)</p>
|
|
<p>An alternative notation for \(\mathsf{commit}\) is:</p>
|
|
<ul>
|
|
<li>\([\phi]_1\) where the commitment is a \(\mathbb{G}_1\) point or</li>
|
|
<li>\([\phi]_2\) where the commitment is a \(\mathbb{G}_2\) point.</li>
|
|
</ul>
|
|
<p>A KZG opening proof is denoted as:</p>
|
|
<p>\(\mathsf{open}(\mathsf{srs}, [\phi], \phi(i))\)</p>
|
|
<h3 id="6-lagrange-basis-polynomials"><a class="header" href="#6-lagrange-basis-polynomials">6. Lagrange basis polynomials</a></h3>
|
|
<p>Lagrange basis polynomials are an important concept and are used in several
|
|
parts of the protocol. To understand them, we must first define roots of unity
|
|
of a finite field.</p>
|
|
<h4 id="61-roots-of-unity-of-a-finite-field"><a class="header" href="#61-roots-of-unity-of-a-finite-field">6.1. Roots of unity of a finite field</a></h4>
|
|
<p>The \(n\)th roots of unity of a finite field \(\mathbb{F}_p\) with prime
|
|
order \(p\) are field elements where for each element \(x\), \(x^n = 1\).</p>
|
|
<p>For example, the 4th roots of unity of the BN254 scalar field (see 1.1) are:</p>
|
|
<pre><code>0x0000000000000000000000000000000000000000000000000000000000000001
|
|
0x30644E72E131A029048B6E193FD841045CEA24F6FD736BEC231204708F703636
|
|
0x30644E72E131A029B85045B68181585D2833E84879B9709143E1F593F0000000
|
|
0x0000000000000000B3C4D79D41A91758CB49C3517C4604A520CFF123608FC9CB
|
|
</code></pre>
|
|
<p>Another name for the \(n\) roots of unity is the evaluation domain of size \(n\)
|
|
for a given finite field. They are commonly denoted as \(\{1, \omega, \ldots,
|
|
\omega^{n-1}\}\).</p>
|
|
<h4 id="62-lagrange-basis-polynomials"><a class="header" href="#62-lagrange-basis-polynomials">6.2. Lagrange basis polynomials</a></h4>
|
|
<p>Given an evaluation domain of size \(n\), the Lagrange basis polynomials of
|
|
this domain are the \(n\) polynomials \([L_0, \ldots, L_n]\) such that
|
|
\(L_i(\omega^{i - 1} = 1)\) and \(L_i(\omega^{j} = 0)\) for all
|
|
\(j \neq i - 1\). For example:</p>
|
|
<ul>
|
|
<li>the Lagrange basis polynomial \(L_0\) evaluates to 1 given the input
|
|
\(\omega^0\).</li>
|
|
<li>the Lagrange basis polynomial \(L_0\) evaluates to 0 given the input
|
|
\(\omega^1\).</li>
|
|
<li>the Lagrange basis polynomial \(L_1\) evaluates to 0 given the input
|
|
\(\omega^0\).</li>
|
|
<li>the Lagrange basis polynomial \(L_1\) evaluates to 1 given the input
|
|
\(\omega^1\).</li>
|
|
</ul>
|
|
<h4 id="63-efficient-generation-of-commitments-to-lagrange-basis-polynomials"><a class="header" href="#63-efficient-generation-of-commitments-to-lagrange-basis-polynomials">6.3. Efficient generation of commitments to Lagrange basis polynomials</a></h4>
|
|
<p>To support \(t\) insertions, Semacaulk requires the KZG commitments to the
|
|
Lagrange basis polynomials over the evaluation domain of size \(t\). These
|
|
KZG commitments are efficiently generated using an implementation of the
|
|
<a href="https://alinush.github.io/2021/06/17/Feist-Khovratovich-technique-for-computing-KZG-proofs-fast.html">Feist-Khovratovich
|
|
technique</a>.</p>
|
|
<h3 id="7-the-accumulator"><a class="header" href="#7-the-accumulator">7. The accumulator</a></h3>
|
|
<p>The <em>accumulator</em> is a single \(\mathbb{G}_1\) point that is a commitment to
|
|
a vector of \(t\) \(\mathbb{F}_r\) elements where \(t\) is the maximum
|
|
capacity of the instance of Semacaulk in question. These elements are ordered
|
|
with the users' identity commitments followed by nothing-up-my-sleeve values.</p>
|
|
<p>An <em>empty accumulator</em> is simply a commitment to \(t\) nothing-up-my-sleeve
|
|
values.</p>
|
|
<p>Given the vector of values \([v_0, \ldots, v_t]\), the accumulator \(C\) is computed
|
|
as such:</p>
|
|
<p>\(\sum_{i=1}^{t} \mathsf{commit}(L_i, \mathsf{srs\_g1}) \cdot v_i\)</p>
|
|
<h4 id="71-updating-the-accumulator"><a class="header" href="#71-updating-the-accumulator">7.1 Updating the accumulator</a></h4>
|
|
<p>To replace a value at \(w_i\) with \(v_i\) at index \(i\):</p>
|
|
<p>\(C_{\mathsf{new}} = C - L \cdot w_i + L \cdot v_i\)</p>
|
|
<p>\(= C + L \cdot (v_i - w_i)\)</p>
|
|
<p>where \(L = \mathsf{commit}(L_i, \mathsf{srs\_g1})\)</p>
|
|
<p>This can be done on-chain at a low cost because the only expensive operations
|
|
required are an elliptic curve scalar multiplication and a elliptic curve
|
|
addition.</p>
|
|
<h3 id="8-the-keccak256-hash"><a class="header" href="#8-the-keccak256-hash">8. The Keccak256 hash</a></h3>
|
|
<p>The Keccak256 hash function is defined in <a href="https://keccak.team/files/Keccak-submission-3.pdf"><em>The Keccak SHA-3
|
|
submission</em></a> by Bertoni et
|
|
al with the output length of 256 bits. We rely on implementations from the
|
|
following sources:</p>
|
|
<ul>
|
|
<li>The EVM's <a href="https://ethereum.org/en/developers/docs/evm/opcodes/"><code>KECCAK256</code>
|
|
opcode</a> denoted as
|
|
<code>0x20</code>.</li>
|
|
<li>The Javascript <a href="https://docs.ethers.org/v5/api/utils/hashing/#utils-keccak256">Ethers.js library's
|
|
<code>ethers.utils.solidityKeccak256</code></a>
|
|
function.</li>
|
|
<li>The Rust <a href="https://docs.rs/tiny-keccak/latest/tiny_keccak/struct.Keccak.html"><code>tiny-keccak</code> library's
|
|
<code>v256</code></a>
|
|
function.</li>
|
|
</ul>
|
|
<h3 id="9-evaluation-domains"><a class="header" href="#9-evaluation-domains">9. Evaluation domains</a></h3>
|
|
<h4 id="91-the-subgroup-domain"><a class="header" href="#91-the-subgroup-domain">9.1. The subgroup domain</a></h4>
|
|
<p>An evaluation domain with size 128. We denote this constant as
|
|
\(\mathsf{SUBGROUP\_SIZE}\).</p>
|
|
<h4 id="92-the-extended-coset-domain"><a class="header" href="#92-the-extended-coset-domain">9.2. The extended coset domain</a></h4>
|
|
<p>An evaluation domain with size 8 * 128. We denote this as
|
|
\(\mathsf{EXTENDED\_DOMAIN\_FACTOR} * \mathsf{SUBGROUP\_SIZE} = 1024\).</p>
|
|
<h4 id="93-the-table-domain"><a class="header" href="#93-the-table-domain">9.3. The table domain</a></h4>
|
|
<p>An evaluation domain with a size of at least 1024. This is the upper limit on
|
|
the number of elements that the accumulator can hold.</p>
|
|
|
|
</main>
|
|
|
|
<nav class="nav-wrapper" aria-label="Page navigation">
|
|
<!-- Mobile navigation buttons -->
|
|
<a rel="prev" href="trusted_setup.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="system_invariants.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="trusted_setup.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="system_invariants.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"></script>
|
|
<script src="mark.min.js"></script>
|
|
<script src="searcher.js"></script>
|
|
|
|
<script src="clipboard.min.js"></script>
|
|
<script src="highlight.js"></script>
|
|
<script src="book.js"></script>
|
|
|
|
<!-- Custom JS scripts -->
|
|
|
|
|
|
</body>
|
|
</html>
|