github/semacaulk
1
1
Fork 0
mirror of https://github.com/geometryxyz/semacaulk.git synced 2026-01-15 00:08:17 -05:00
Code Issues Packages Projects Releases Wiki Activity
Files
gh-pages
semacaulk/print.html
weijiekoh cb3efe4d31 deploy: 859c638cb1
2023-02-13 17:00:56 +00:00

1356 lines
95 KiB
HTML
Raw Permalink Blame History

This file contains invisible Unicode characters
This file contains invisible Unicode characters that are indistinguishable to humans but may be processed differently by a computer. If you think that this is intentional, you can safely ignore this warning. Use the Escape button to reveal them.
This file contains Unicode characters that might be confused with other characters. If you think that this is intentional, you can safely ignore this warning. Use the Escape button to reveal them.
<!DOCTYPE HTML>
<html lang="en" class="sidebar-visible no-js light">
<head>
<!-- Book generated using mdBook -->
<meta charset="UTF-8">
<title>Semacaulk</title>
<meta name="robots" content="noindex" />
<!-- 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"><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="overview"><a class="header" href="#overview">Overview</a></h1>
<p>Semacaulk is a zero-knowledge set membership protocol that works on Ethereum.</p>
<p>Semacaulk allows a user to <em>commit</em> to an identity, represented by two secret
values: an identity nullifier and an identity trapdoor. Next, any user who
knows their secret values can generate a proof that they had previously
committed to said identity, without revealing which member of the set they
were. Moreover, when they submit such a proof, they can broadcast an arbitrary
<em>signal</em> against an <em>external nullifier</em>, but only do so once per external
nullifier. This enables applications like mixers, whistleblowing, and simple
private voting systems. This is the same basic functionality as the <a href="https://github.com/semaphore-protocol/semaphore">Semaphore
Protocol</a>.</p>
<p>The source code for Semacaulk can be found
<a href="https://github.com/geometryresearch/semacaulk">here</a>.</p>
<h2 id="differences-from-semaphore"><a class="header" href="#differences-from-semaphore">Differences from Semaphore</a></h2>
<p>Semacaulk differs from Semaphore in two key ways. First, instead of
accumulating identity commitments in a Merkle tree, it updates a KZG
commitment. This operations involves BN254 point multiplication and addition,
rather than expensive zk-friendly hash operations. Secondly, the underlying
proof system is a polynomial interactive oracle proof that combines <a href="https://eprint.iacr.org/2022/957">Caulk+
lookups</a> and a <a href="https://zcash.github.io/halo2/design/proving-system/multipoint-opening.html">multipoint opening
argument</a>.</p>
<p>Thanks to these techniques, on-chain insertions are far cheaper in Semacaulk
(around 68k gas) while the gas cost of verification (356k gas) is comparable to
that of Semaphore. Moreover, proof generation comes in two phases - a
<a href="precomputation_and_updates.html">precomputation stage</a> and a proof generation
stage. The total time taken is comparable to Groth16 proof generation for a
Semaphore circuit that supports the same number of insertions, but more
imporantly, precomputation can be performed long in advance and efficiently
updated, which imparts more flexibility which may lead to higher
user-friendliness.</p>
<h2 id="motivation"><a class="header" href="#motivation">Motivation</a></h2>
<p>We intend Semacaulk to demonstrate the use of Caulk+ techniques for membership
proofs in a gas-efficient manner to enable privacy-related applications. We
believe these techniques, as are other new proving systems and lookup
arguments, can be highly useful, and we hope that Semacaulk shows how to
practically use them.</p>
<p>We highly welcome and strongly encourage collaboration with projects who wish
to build upon Semacaulk.</p>
<p>Note that the techniques used in Semacaulk do not have to involve an end-to-end
custom prover such as used here. We have done this only because we wanted to
experiment with improving prover efficiency further. With only small changes,
the same gas-efficient membership proof construction can be used with more
generic and expressive SNARK-based programs.</p>
<h2 id="security"><a class="header" href="#security">Security</a></h2>
<p>The code base has not been audited. We do not recommend its use in production
until a thorough audit has been performed.</p>
<div style="break-before: page; page-break-before: always;"></div><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="quick-start"><a class="header" href="#quick-start">Quick start</a></h1>
<ol>
<li>
<p>Install Rust using <a href="https://www.rust-lang.org/learn/get-started">these
instructions</a>.</p>
</li>
<li>
<p>Install Foundry using <a href="https://github.com/foundry-rs/foundry#installation">these
instructions</a>.</p>
</li>
<li>
<p>Clone this repository.</p>
</li>
</ol>
<pre><code class="language-bash">git clone https://github.com/geometryresearch/semacaulk.git &amp;&amp; \
cd semacaulk
</code></pre>
<ol start="4">
<li>Build the contracts</li>
</ol>
<pre><code class="language-bash">./build_contracts.sh
</code></pre>
<ol start="5">
<li>Run tests</li>
</ol>
<pre><code class="language-bash">cargo test
</code></pre>
<ol start="6">
<li>Build and run the demo:</li>
</ol>
<pre><code class="language-bash">cargo build --release &amp;&amp; \
./target/release/demo 11 11.hex lagrangeComms_11
</code></pre>
<p>Note that the files <code>11.hex</code> and <code>lagrangeComms_11</code> support up to 2048 leaf
insertions. To support a larger capacity, see the <a href="./trusted_setup.html#processing-the-points">Trusted Setup - Processing
the points</a> section for
instructions on how to do so.</p>
<div style="break-before: page; page-break-before: always;"></div><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="trusted-setup"><a class="header" href="#trusted-setup">Trusted Setup</a></h1>
<p>Semacaulk requires a <a href="https://eprint.iacr.org/2017/1050.pdf">securely run trusted
setup</a>. Specifically, for a capacity of
\(2^n\) elements, it requires \(2^n + 1\) \({g_1}^{\tau}\) points and
\(2^n\) \({g_2}^{\tau}\) points where \(\tau\) is highly unlikely to be
known but \({g_1}^{\tau}\) and \({g_2}^{\tau}\) can be generated via a
multi-party ceremony. As long as one participant does not reveal and destroys
the secret so-called toxic waste that they use, the entire ceremony is secure.</p>
<p>For compatibility with Ethereum, Semacaulk is built on the BN254 curve. As
such, the output of the <a href="https://github.com/privacy-scaling-explorations/perpetualpowersoftau">Perpetual Powers of
Tau</a>
ceremony can be used. The outputs of this ceremony include up to \(2^{28}\)
\({g_1}^{\tau}\) and \({g_2}^{\tau}\) points. If Semacaulk is to be used on
a different elliptic curve, a different trusted setup must be used.</p>
<p>For the sake of convenience, we recommend the trusted setup output from Hermez
Network, which consist of the 54th contribution of Perpetual Powers of Tau (PPOT) with
a random beacon. These files can be downloaded from <a href="https://github.com/iden3/snarkjs#7-prepare-phase-2">this
page</a>. (You may also use
the latest contribution to PPOT, but at the time of writing, a tool to parse
and convert it has not yet been written.)</p>
<p>Note that the <a href="https://github.com/AztecProtocol/ignition-verification/blob/master/Transcript_spec.md">Aztec Ignition ceremony
output</a>
is not sufficient for Semacaulk as only provides 1 <code>tauG2</code> point, while
Semacaulk requires as many <code>tauG2</code> points as the maximum desired capacity of
the accumulator. </p>
<h2 id="processing-the-points"><a class="header" href="#processing-the-points">Processing the points</a></h2>
<p>Semacaulk's <code>demo</code> binary requires two inputs: a <code>.hex</code> file containing the
trusted setup outputs, and another file containing the KZG commitments to the
Lagrange basis polynomials generated using said trusted setup outputs.</p>
<p>To produce the former, use the
<a href="https://github.com/geometryresearch/export-ptau-points">export-ptau-points</a>
tool. First, download Hermez Network <code>.ptau</code> file with at least \(2^{11}\)
points. In this example, we choose \(2^{11}\) for a maximum capacity of 2048:</p>
<pre><code class="language-bash">wget https://hermez.s3-eu-west-1.amazonaws.com/powersOfTau28_hez_final_11.ptau
</code></pre>
<p>In <code>export-ptau-points</code>, run:</p>
<pre><code>npm i &amp;&amp; npm run build &amp;&amp; \
node build/index.js -p powersOfTau28_hez_final_11.ptau -o ./11.hex --num-g1 2049 --num-g2 2048
</code></pre>
<p>Build and run the <code>setup</code> binary from the Semacaulk repository:</p>
<pre><code class="language-bash">cargo build --release
</code></pre>
<p>To produce the latter, run the <code>setup</code> binary:</p>
<pre><code class="language-bash">./target/release/setup 11 ./path/to/11.hex lagrangeComms_11
</code></pre>
<p>You are now ready to run the demo according to the instructions in <a href="./quick_start.html">the quick start
page</a>.</p>
<div style="break-before: page; page-break-before: always;"></div><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>
<div style="break-before: page; page-break-before: always;"></div><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="system-invariants"><a class="header" href="#system-invariants">System invariants</a></h1>
<p>An <a href="https://mathworld.wolfram.com/Invariant.html">invariant</a> is a property of a
system which remains unmodified even after operations or transformations are
applied to it. The authors of Semacaulk intend the following to be the
invariants of Semacaulk:</p>
<ol>
<li>
<p><strong>Privacy</strong>: No-one but the user who knows the value of the identity
nullifier and identity trapdoor behind an identity commitment may generate a
valid proof of set membership of the identity commitment in the accumulator.</p>
</li>
<li>
<p><strong>Safe NUMS value</strong>: No-one should be able to produce a valid proof of set
membership for the default nothing-up-my-sleeve value.</p>
</li>
<li>
<p><strong>Proof non-malleability</strong>: Proofs are visible once submitted to the mempool,
but no-one should be able to modify an existing proof, change it such that
it is associated with a different signal, and remain valid.</p>
</li>
<li>
<p><strong>Zero-knowledge</strong>: given a valid proof, no-one should be able to determine
the index of the identity commitment the identity nullifier, or the identity
trapdor associated with the proof.</p>
</li>
</ol>
<p>Other invariants which have to do with the internal consistency and correctness
of the system are:</p>
<ol start="5">
<li>
<p>All identity commitments must be less than the BN254 scalar field size.</p>
</li>
<li>
<p>Every identity commitment in the accumulator must have been added at some
point in the past, except for the NUMS values.</p>
</li>
<li>
<p>Any identity commitment besides the NUMS value may be added to the
accumulator, unless it is full.</p>
</li>
<li>
<p>The NUMS value cannot be added to the accumulator.</p>
</li>
<li>
<p>There can be no valid proof associated with a NUMS value as the identity
commitment.</p>
</li>
<li>
<p>All nullifier hashes must be less than the BN254 scalar field size.</p>
</li>
<li>
<p>It should only be possible to generate a proof for a valid user, and
impossible to generate a proof for an invalid user.</p>
</li>
</ol>
<div style="break-before: page; page-break-before: always;"></div><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="insertion"><a class="header" href="#insertion">Insertion</a></h1>
<p>As described in the <a href="./cryptographic_specification.html#7-the-accumulator">Cryptographic
Specification</a>,
insertions to the accumulator are easily achieved via an elliptic curve point
multiplication and addition.</p>
<p>To replace a value (originally <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.3117em;"><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 mathnormal mtight">i</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>) at index \(i\) with <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.03588em;">v</span><span class="msupsub"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:0.3117em;"><span style="top:-2.55em;margin-left:-0.0359em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mathnormal mtight">i</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>
<p><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 mathnormal" style="margin-right:0.07153em;">C</span><span class="msupsub"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:0.1611em;"><span style="top:-2.55em;margin-left:-0.0715em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight"><span class="mord mtight"><span class="mord mathsf mtight" style="margin-right:0.01389em;">new</span></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="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.7667em;vertical-align:-0.0833em;"></span><span class="mord mathnormal" style="margin-right:0.07153em;">C</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.6833em;"></span><span class="mord mathnormal">L</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:1em;vertical-align:-0.25em;"></span><span class="mopen">(</span><span class="mord"><span class="mord mathnormal" style="margin-right:0.03588em;">v</span><span class="msupsub"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:0.3117em;"><span style="top:-2.55em;margin-left:-0.0359em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mathnormal mtight">i</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="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:1em;vertical-align:-0.25em;"></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.3117em;"><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 mathnormal mtight">i</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>
<p>where <span class="katex"><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.6833em;"></span><span class="mord mathnormal">L</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:1.0361em;vertical-align:-0.2861em;"></span><span class="mord"><span class="mord mathsf">commit</span></span><span class="mopen">(</span><span class="mord"><span class="mord mathnormal">L</span><span class="msupsub"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:0.3117em;"><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">i</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 mathsf">srs</span><span class="mord"><span class="mspace newline"></span><span class="msupsub"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:0.1611em;"><span style="top:-2.55em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mathsf mtight" style="margin-right:0.01389em;">g</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 class="mord mathsf">1</span></span><span class="mclose">)</span></span></span></span></p>
<p>If only insertions are allowed, <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.3117em;"><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 mathnormal mtight">i</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 by definition the <a href="./cryptographic_specification.html#2-the-nothing-up-my-sleeve-value">nothing-up-my-sleeve
value</a>.</p>
<div style="break-before: page; page-break-before: always;"></div><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="the-circuit-and-gates"><a class="header" href="#the-circuit-and-gates">The Circuit and Gates</a></h1>
<p>Semacaulk uses a custom Plonk-style proof system where a prover must convince a
verifier that it knows of some private <em>witness</em> values which are the result of
the correct execution of predefined logical operations upon public inputs and
fixed data. In other terms, there is a <em>circuit</em> which represents some program.
In proof systems like Groth16, circuits are represented in the form of a Rank-1
Constraint System (R1CS), and compilers like <a href="https://iden3.io/circom">circom</a>
can be used to easily compile circuits to this format. Semacaulk, by contrast,
uses a set of custom gates on a set of data columns to represent its
logic.</p>
<h2 id="private-inputs-witness"><a class="header" href="#private-inputs-witness">Private inputs (witness)</a></h2>
<ul>
<li>\(\mathsf{id\_nul}\): the identity nullifier.</li>
<li>\(\mathsf{id\_trap}\): the identity trapdoor.</li>
<li>\(i\): the index of the prover's identity commitment in the accumulator.</li>
</ul>
<h2 id="public-inputs"><a class="header" href="#public-inputs">Public inputs</a></h2>
<ul>
<li>\(\mathsf{ext\_nul}\): the extenal nullifier.</li>
<li>\(\mathsf{id\_comm}\): the identity commitment, which is the MiMC7
<code>multi_hash</code> of \([\mathsf{id\_nul}, \mathsf{id\_trap}]\).</li>
<li>\(\mathsf{nul\_hash}\): the nullifier hash, which is the MiMC7
<code>multi_hash</code> of \([\mathsf{id\_nul}, \mathsf{ext\_nul}]\).</li>
</ul>
<h2 id="columns"><a class="header" href="#columns">Columns</a></h2>
<div class="table-wrapper"><table><thead><tr><th>Row</th><th>\(\mathsf{w}_0\)</th><th>\(\mathsf{w}_1\)</th><th>\(\mathsf{w}_2\)</th><th>\(\mathsf{key}\)</th><th>\(\mathsf{c}\)</th><th>\(\mathsf{q\_mimc}\)</th></tr></thead><tbody>
<tr><td>0</td><td>\(\mathsf{id\_nul}\)</td><td>\(\mathsf{id\_trap}\)</td><td>\(\mathsf{ext\_nul}\)</td><td>\(\mathsf{w}_0[n] + \mathsf{w}_0[0] \)</td><td>\(\mathsf{cts}[0]\)</td><td>1</td></tr>
<tr><td>1</td><td>\((\mathsf{w}_0[0] + \mathsf{c}[0]) ^ 7\)</td><td>\((\mathsf{w}_1[0] + \mathsf{key}[0] + \mathsf{c}[0]) ^ 7\)</td><td>\((\mathsf{w}_2[0] + \mathsf{key}[0] + \mathsf{c}[0]) ^ 7\)</td><td>\(\mathsf{w}_0[n] + \mathsf{w}_0[0] \)</td><td>\(\mathsf{cts}[1]\)</td><td>1</td></tr>
<tr><td>\ldots</td><td>\ldots</td><td>\ldots</td><td>\ldots</td><td>\ldots</td><td>\ldots</td><td>\ldots</td></tr>
<tr><td>\(n\)</td><td>\((\mathsf{w}_0[n - 1] + \mathsf{c}[n - 1]) ^ 7\)</td><td>\((\mathsf{w}_1[n - 1] + \mathsf{key}[n - 1] + \mathsf{c}[n - 1]) ^ 7\)</td><td>\((\mathsf{w}_2[n - 1] + \mathsf{key}[n - 1] + \mathsf{c}[n - 1]) ^ 7\)</td><td>\(\mathsf{w}_0[n] + \mathsf{w}_0[0] \)</td><td>\(\mathsf{dummy}\)</td><td>0</td></tr>
<tr><td>128</td><td>\(b\)</td><td>\(b\)</td><td>\(b\)</td><td>\(b\)</td><td>\(b\)</td><td>\(b\)</td></tr>
</tbody></table>
</div>
<p>Notes:</p>
<ul>
<li>The 0th row contains the \(\mathsf{id\_nul}\), \(\mathsf{id\_trap}\), etc
values. They are not table headers.</li>
<li>\(n\) is the constant (91) defined in
<a href="./cryptographic_specification.html#4-the-mimc7-hash-function">4</a>.</li>
<li>\(\mathsf{dummy}\) can be any value as it will not be used by any of the gates.</li>
<li>\(\mathsf{q\_mimc}\) is a selector column. It is a vector starting with
\(n\) 1 values followed by zeros.</li>
<li>\(\mathsf{c}\) is a fixed column starting with \(n\) MiMC7 round constants.</li>
<li>\(b\) are random values used to blind the columns, in order to
make it computationally infeasible to brute-force their polynomial commitments.</li>
</ul>
<h2 id="gates"><a class="header" href="#gates">Gates</a></h2>
<p>To understand how the logic of the circuit is encoded, consider each row of the
table as inputs to the linear combination of the following gates, which must
evaluate to 0 for a valid proof to be generated. In effect:</p>
<p>\(\mathsf{gate}_0(r) + \ldots + \mathsf{gate}_n(r) = 0\) must be true.</p>
<p>Each and every gate must evaluate to 0. It is not possible for the prover to
cheat by having some gates evaluate to some value such that the total evaluates
to 0, since the prover will be forced to separate each gate with a challenge
that they cannot control. Internally, the equation is actually:</p>
<p>\(\mathsf{gate}_0(r) \cdot v_0 + \ldots + \mathsf{gate}_n(r) \cdot v_n = 0\) must be true.</p>
<p>where the \(v\) values are successive powers of the hash of the public
inputs. The prover would have to break a strong hash function to choose the
public inputs and \(v\) values in order to cheat.</p>
<h3 id="0-mimc7roundgate"><a class="header" href="#0-mimc7roundgate">0. <code>Mimc7RoundGate</code></a></h3>
<p>The equation is:</p>
<p>\(\mathsf{q\_mimc}[i] \cdot (\mathsf{w}_0[i] + 0 + \mathsf{c}[i]) ^ 7\)</p>
<p>This makes each row from 1 to \(n\) contain the successive outputs of the
MiMC7 round function over \(\mathsf{id\_nul}\). </p>
<p>The key is set to 0 for all rows.</p>
<h3 id="1-mimc7roundgate-for-the-identity-commitment"><a class="header" href="#1-mimc7roundgate-for-the-identity-commitment">1. <code>Mimc7RoundGate</code> for the identity commitment</a></h3>
<p>The equation is:</p>
<p>\(\mathsf{q\_mimc}[i] \cdot (\mathsf{w}_1[i] + \mathsf{key}[i] + \mathsf{c}[i]) ^ 7\)</p>
<p>To understand this, first note that gate 4 (<code>KeyCopyGate</code>) and gate 3
(<code>KeyEqualityGate</code>) ensure that the \(\mathsf{key}\) values are all the MiMC7
<code>hash</code> of \(\mathsf{id\_nul}\) plus \(\mathsf{id\_nul}\).</p>
<p>As described in
<a href="./cryptographic_specification.html#431-multi_hash-with-two-field-elements">4.3.1</a>,
this means that the key for step 4 of the <code>multi_hash</code> function on two inputs
is the value in any row of \(key\) from 0 to \(n\). As such, this gate
represents the circuit logic for step 4 of <code>multi_hash</code>, which brings it us
closer to computing the identity commitment.</p>
<p>Recall from <a href="./mechanism_of_operation.html#51-user-identities">5.1</a>:</p>
<p>\(\mathsf{id\_comm} = \mathsf{multi\_hash}([\mathsf{id\_nul}, \mathsf{id\_trap}])\)</p>
<h3 id="2-mimc7roundgate-for-the-nullifier-hash"><a class="header" href="#2-mimc7roundgate-for-the-nullifier-hash">2. <code>Mimc7RoundGate</code> for the nullifier hash</a></h3>
<p>The equation is:</p>
<p>\(\mathsf{q\_mimc}[i] \cdot (\mathsf{w}_2[i] + \mathsf{key}[i] + \mathsf{c}[i]) ^ 7\)</p>
<p>Recall that:</p>
<p>\(\mathsf{nul\_hash} = \mathsf{multi\_hash}([\mathsf{id\_nul}, \mathsf{ext\_nul}])\)</p>
<p>By the same logic behind the <code>Mimc7RoundGate</code> for the identity commitment, this
gate brings us closer to compuing the nullifier hash.</p>
<h3 id="3-keyequalitygate"><a class="header" href="#3-keyequalitygate">3. <code>KeyEqualityGate</code></a></h3>
<p>The equation is:</p>
<p>\(\mathsf{q\_mimc}[i] \cdot (\mathsf{key}[i] + \mathsf{key}[n])\) </p>
<p>This gate ensures that every row of \(\mathsf{key}\) from 0 to \(n\) contains the
same value.</p>
<h3 id="4-keycopygate"><a class="header" href="#4-keycopygate">4. <code>KeyCopyGate</code></a></h3>
<p>The equation is:</p>
<p>\(L_0(\omega_i) \cdot (\mathsf{key}[i] - \mathsf{w}_0[i] - \mathsf{w}_0[n])\)</p>
<p>This gate ensures that the first row in the \(\mathsf{key}\) column is equal
to \(\mathsf{id\_nul}\) plus the \(n\)th iteration of the MiMC7 round
function on \(\mathsf{id\_nul}\).</p>
<p>\(L_0\) is a precomputed polynomial in the multiplicative subgroup which
evaluates to 1 at \(\omega_i\), and 0 at all other roots of unity.
Effectively, it acts as a selector without the overhead of a selector column.</p>
<h3 id="5-nullifierhashgate"><a class="header" href="#5-nullifierhashgate">5. <code>NullifierHashGate</code></a></h3>
<p>The equation is:</p>
<p>\(L_0(\omega_i) \cdot (\mathsf{nul\_hash} - \mathsf{w}_2[n] - (2 \cdot \mathsf{key}[i]) - \mathsf{w}_2[i])\)</p>
<p>This gate ensures that the \(\mathsf{nul\_hash}\) public input is equal to:</p>
<p>\(\mathsf{w}_2[n] + (2 \cdot \mathsf{key}[0]) + \mathsf{w}_2[0])\)</p>
<p>To understand why, let us trace the computation of \(\mathsf{nul\_hash}\):</p>
<p>Given inputs \(\mathsf{id\_nul}\) and \(\mathsf{ext\_nul}\):</p>
<ol>
<li>Set \(r\) as 0.</li>
<li>Set \(h_0 = \mathsf{hash}(\mathsf{id\_nul}, r)\).</li>
<li>Set \(r = r + \mathsf{id\_nul} + h_0\).</li>
<li>Set \(h_1 = \mathsf{hash}(\mathsf{ext\_nul}, r)\).</li>
<li>Return \(r + \mathsf{ext\_nul} + h_1\).</li>
</ol>
<p>Hence, \(\mathsf{nul\_hash}\) equals:</p>
<p>\(r + \mathsf{ext\_nul} + h_1 =\)</p>
<p>\(\mathsf{id\_nul} + h_0 + \mathsf{ext\_nul} + h_1 =\)</p>
<p>\(\mathsf{id\_nul} + \mathsf{hash}(\mathsf{id\_nul}, 0) + \mathsf{ext\_nul} + \mathsf{hash}(\mathsf{ext\_nul}, \mathsf{id\_nul} + \mathsf{hash}(\mathsf{id\_nul}, 0))\)</p>
<p>Since the value \(r\) from step 3 is used as the key in step 4, the above is
equal to:</p>
<p>\(\mathsf{key}[0] + \mathsf{ext\_nul} + \mathsf{hash}(\mathsf{ext\_nul}, \mathsf{key}[0])\)</p>
<p>Since \(\mathsf{hash}(x, k)\) equals \(n\) round digests of \(x\) plus
\(k\), the above equals:</p>
<p>\(\mathsf{key}[0] + \mathsf{w}_2[0] + \mathsf{w}_2[n] + \mathsf{key}[0] =\)</p>
<p>\(\mathsf{w}_2[n] + (2 \cdot \mathsf{key}[0]) + \mathsf{w}_2[0])\)</p>
<h3 id="6-externalnullifiergate"><a class="header" href="#6-externalnullifiergate">6. <code>ExternalNullifierGate</code></a></h3>
<p>The equation is:</p>
<p>\(L_0(\omega_i) \cdot (\mathsf{w}_2[i] - \mathsf{ext\_nul})\)</p>
<p>This gate ensures that the \(\mathsf{ext\_nul}\) public input is equal to
\(\mathsf{w}_2[0]\).</p>
<div style="break-before: page; page-break-before: always;"></div><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="precomputation-and-updates"><a class="header" href="#precomputation-and-updates">Precomputation and updates</a></h1>
<p>Caulk employs a precomputation step in order to make the use of it sublinear in
the group size. This allows neatly separating the membership proof part of
Semacaulk from the nullifier computation, while allowing to blind the
precomputed membership proof differently at each use.</p>
<p>When a group is updated, precomputation is needed again, so there are a few
options as to how to avoid many precomputations in frequently updated groups.
These include storing a history of valid group commitments or batching
insertions and updating the precomputation after some predefined time slot.
This also opens the possibility to use a centralised, but verifiable, service
to compute these for them, since a unique feature of the precomputation in
Caulk is that a batch can be computed even more cheaply. There are, of course,
privacy implications when using a service, but these can also be mitigated
using several techniques and trade-offs.</p>
<p>Additionally, the precomputation done in Caulk is amenable to efficient updates
when the group changes, justifying a higher cost for the initial
precomputation.</p>
<h2 id="precomputed-data"><a class="header" href="#precomputed-data">Precomputed data</a></h2>
<p>Precomputed data consists of the following:</p>
<ol>
<li>\(\mathsf{mimc\_cts}\)</li>
<li>\(\mathsf{mimc\_cts\_coset\_evals}\)</li>
<li>\(\mathsf{zh\_inverse\_coset\_evals}\)</li>
<li>\(\mathsf{q\_mimc}\) </li>
<li>\(\mathsf{q\_mimc\_coset\_evals}\) </li>
<li>\(\mathsf{l0\_coset\_evals}\) </li>
<li>\(\mathsf{w_1\_mapping}\) </li>
<li>\([{\mathsf{W}_1}^{(i)}]_2\) for all indices \(i \in I\)</li>
<li>\([{\mathsf{W}_2}^{(i)}]_2\) for all indices \(i \in I\)</li>
</ol>
<p>The only parts of the precomputed data which rely on the secret index \(i\),
which denotes the secret position of the prover's identity commitment in the
accumulator, are \([{\mathsf{W}_1}^{(i)}]_2\) and \([{\mathsf{W}_2}^{(i)}]_2\).</p>
<p>The Caulk+ paper defines:</p>
<ul>
<li>\({\mathsf{W}_1}^{(i)} = (C(X) - v_i) / (X - \omega^i)\)</li>
<li>\({\mathsf{W}_2}^{(i)} = Z_H(X) / (X - \omega^i)\)</li>
</ul>
<h2 id="updating-commitments-to-mathsfw_1i"><a class="header" href="#updating-commitments-to-mathsfw_1i">Updating commitments to \(\mathsf{W}_1^{(i)}\)</a></h2>
<p>For many of Semacaulk's use cases, users insert new items into the accumulator,
and do not update existing items. As such, this section will only discuss
how to update commitments to \(\mathsf{W}_1^{(i)}\) when the accumulator
changes at an index \(j\) which is different from that of the user's entry
\(i\).</p>
<p>We can efficiently update \([{\mathsf{W}_1}^{(i)}]_2\) using the technique
described in <a href="https://eprint.iacr.org/2020/527.pdf">TADBFK20, section 3.4.2</a>,
where \(i \neq j\).</p>
<p>When an element at \(j\) is updated and \(i \neq j\), and the new element
is \(v_j = v_\mathsf{zero} + \delta\), the new accumulator is:</p>
<p>\(C(X) - L_j(X) \cdot v_\mathsf{zero} + L_j \cdot v_j\)</p>
<p>\(= C(X) - L_j(X) \cdot (v_\mathsf{zero} + v_j)\)</p>
<p>\(= C(X) + \delta \cdot L_j(X)\)</p>
<p>\({\mathsf{W{new}}_1}^{(i)}\) is therefore:</p>
<p>\(\frac{C(X) - v_i + \delta \cdot L_j(X)}{X - \omega^i}\)
\( = {\mathsf{W}_1}^{(i)} + \delta \cdot \frac{L_j(X)}{X - \omega^i}\)</p>
<p>To use the homomorphic properties of KZG commitments, we need to
compute \([\frac{L_j(X)}{X - \omega^i}]_2\), multiply it by \(\delta\), and
add it to \([{\mathsf{W}_1}^{(i)}]_2\). Yet we must do this with lower than
the \(O(n)\) cost of a full KZG \(\mathsf{commit}\) operation.</p>
<p>TADBFK20 section 3.4.2 describes how to do so without performing
\(\mathsf{commit}\) at all. This document will be updated to elaborate on the
method.</p>
<!--
1. Compute \\(a_j = g \cdot (A(\tau) / (\tau / \omega^j))\\) for each \\(j \in [0
\ldots t]\\) during the setup.
Since \\(\tau\\) is unknown but we have access to \\(g \cdot \tau\\), we can
rewrite this formula as:
\\(a_j = g \cdot ((\tau^t - 1) / (\tau / \omega^j))\\)
\\(= g \cdot (\frac{\tau^t}{\tau - \omega^j} - \frac{1}{\tau - \omega^j})\\)
\\(= (g \cdot \frac{\tau^t}{\tau - \omega^j}) / (g \cdot \frac{1}{\tau - \omega^j})\\)
\\(= (g \cdot \frac{\tau^t}{\tau - \omega^j}) \cdot (g \cdot (\tau - \omega^j))\\)
2. Compute \\(w_{i,j} = {a_i} \cdot {v_i} {a_j} \cdot {v_j}\\)
3. Compute \\(u = {w_{i,j}} \cdot {\frac{1}{t\omega^{-j}}}\\).
4. Compute \\([{\mathsf{W{new}}_1}^{(i)}]_2 =\\)
\\([{\mathsf{W}_1}^{(i)}]_2 \cdot u \cdot \delta\\)
TODO: test this in code!
-->
<h2 id="updating-commitments-to-mathsfw_2i"><a class="header" href="#updating-commitments-to-mathsfw_2i">Updating commitments to \(\mathsf{W}_2^{(i)}\)</a></h2>
<p>For use cases where users do not update their own entries (i.e. \(i \neq j\)),
there is no need to update the precomputed commitments to
\(\mathsf{W}_2^{(i)}\).</p>
<!--
### \\(\mathsf{mimc\\_cts}\\)
A polynomial over the multiplicative subgroup which evaluates to the MiMC7
round constants at each root of unity. The subgroup size is the number of MiMC7
rounds defined in
[4](./cryptographic_specification.html#4-the-mimc7-hash-function).
### \\(\mathsf{mimc\\_cts\\_coset\\_evals}\\)
We first compute a polynomial which evaluates, at each root of unity in the
subgroup domain, to a vector (of the size of the subgroup) consisting of the
evaluations of the MiMC7 round constants, padded by dummy values. Next, we
perform an FFT over the coset of the extended domain on the coefficients of
this polynomial to obtain \\(\mathsf{mimc\\_cts\\_coset\\_evals}\\).
### \\(\mathsf{zh\\_inverse\\_coset\\_evals}\\)
A vector of \\(\mathbb{F}_r\\) elements that are the field inversions of the
(coefficients of the vanishing polynomial over the coset??? TODO)
### \\(\mathsf{q\\_mimc}\\)
A polynomial whose evaluations at the roots of unity over the subgroup domain
of size 128 are \\(n = 91\\) `1` values, followed by zeroes. It represents the
\\(\mathsf{q\\_mimc}\\) [selector column](./circuit_and_gates.html).
### \\(\mathsf{q\\_mimc\\_coset\\_evals}\\)
A vector of \\(\mathbb{F}_r\\) elements that are the evaluations of the
\\(\\mathsf{q\\_mimc}\\) polynomial coefficients over the coset?? (TODO)
### \\(\mathsf{l0\\_coset\\_evals}\\)
Where \\(L_0\\) is the 0th Lagrange basis polynomial over the subgroup
evaluation domain, this is a vector of its evaluations over the coset (?? TODO)
### \\({\mathsf{W}_1}^{i}\\)
As defined in the [Caulk+ paper, section 3](https://eprint.iacr.org/2022/957.pdf).
### \\({\mathsf{W}_2}^{i}\\)
As defined in the [Caulk+ paper, section 3](https://eprint.iacr.org/2022/957.pdf).
-->
<div style="break-before: page; page-break-before: always;"></div><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="the-fiat-shamir-transcript"><a class="header" href="#the-fiat-shamir-transcript">The Fiat-Shamir Transcript</a></h1>
<p>A transcript is an abstraction over the <a href="https://en.wikipedia.org/wiki/Fiat%E2%80%93Shamir_heuristic">Fiat-Shamir
heuristic</a>. Both
the prover and verifier use the transcript to deterministically generate
<em>challenge variables</em> based on the public inputs and proof data.</p>
<p>Another way to think about the transcript is as a state machine where the state
is a single data buffer. Every time a challenge is requested, it hashes the
buffer replaces the contents of the buffer with the hash, and returns a value
derived from the hash. The transcript can also be updated with abitrary data by
appending the update to the buffer.</p>
<p>Our transcript implements this concept with the following functions:</p>
<ul>
<li><code>new_transcript</code>: returns a new transcript whose buffer is 32 bytes of <code>0</code>
values.</li>
<li><code>update_with_f</code>: accepts a single \(\mathbb{F}_r\) value, converts it to a
big-endian byte array, and appends it to the buffer.</li>
<li><code>update_with_g1</code>: accepts a single \(\mathbb{G}_1\) point, converts its
\(x\) and \(y\) points to big-endian byte arrays, and appends them to the
buffer in the aforementioned order.</li>
<li><code>update_with_g2</code>: accepts a single \(\mathbb{G}_2\) point, converts its
\(x_0\), \(x_1\), \(y_0\), and \(y_1\) points into big-endian byte
arrays, and appends them to the buffer in the aforementioned order.</li>
<li><code>get_challenge</code>: hashes the buffer with Keccak256, replaces the buffer with
the hash, converts the hash into a \(\mathbb{F}_r\) element (treating it
as a big-endian buffer), and returns the \(\mathbb{F}_r\) element.</li>
</ul>
<div style="break-before: page; page-break-before: always;"></div><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="proof-generation"><a class="header" href="#proof-generation">Proof generation</a></h1>
<h2 id="461-assignment-round"><a class="header" href="#461-assignment-round">4.6.1. Assignment Round</a></h2>
<p>Given the public and private inputs, the prover generates the assignment table
(see <a href="./circuit_and_gates.html">4.3</a>). Each column is represented as a
polynomial over the multiplicative subgroup.</p>
<ul>
<li>\(\mathsf{w}_0\)</li>
<li>\(\mathsf{w}_1\)</li>
<li>\(\mathsf{w}_2\)</li>
<li>\(\mathsf{key}\)</li>
</ul>
<p>The prover then computes KZG commitments to each of the above polynomials:</p>
<ul>
<li>\([\mathsf{w}_0]_1\)</li>
<li>\([\mathsf{w}_1]_1\)</li>
<li>\([\mathsf{w}_2]_1\)</li>
<li>\([\mathsf{key}]_1\)</li>
</ul>
<p>The prover also computes:</p>
<p>\(A = \mathsf{w}_1 + \mathsf{w}_1(\gamma^{91}X) + 2 \cdot \mathsf{key}\)</p>
<p>where \(\mathsf{w}_1(\gamma^{91}X)\) is \(\mathsf{w}_1\) shifted by the
\(n\)th root of unity in the subgroup domain
(<a href="cryptographic_specification.html#91-the-subgroup-domain">9.1</a>).</p>
<p>Next, the prover adds the public inputs to the transcript in this order:</p>
<ol>
<li>\(\mathsf{ext\_nul}\)</li>
<li>\(\mathsf{nul\_hash}\)</li>
<li>\(\mathsf{sig\_hash}\)</li>
</ol>
<p>The prover then extracts the challenge \(v\), which is used in the next
round.</p>
<h2 id="462-quotient-round"><a class="header" href="#462-quotient-round">4.6.2. Quotient round</a></h2>
<p>The prover generates a quotient polynomial \(q\) by dividing
a numerator — a powers-of-\(v\)-separated linear combination of gate
polynomials — with the vanishing polynomial \(Z_H\).</p>
<p>\(q(X) = \mathsf{numerator} / Z_H\) where</p>
<p>\(\mathsf{numerator} =\)</p>
<p>\(\mathsf{q\_mimc}((\mathsf{w}_0 + \mathsf{cts})^7 - \mathsf{w}_0(\gamma X)) + \)</p>
<p>\(v \cdot \mathsf{q\_mimc}((w_1 + \mathsf{key} + \mathsf{cts})^7 - w_1(\gamma X)) +\)</p>
<p>\(v^2 \cdot \mathsf{q\_mimc}((\mathsf{w}_2 + \mathsf{key} + \mathsf{cts})^7 - \mathsf{w}_2(\gamma X)) +\)</p>
<p>\(v^3 \cdot \mathsf{q\_mimc}(\mathsf{key} - \mathsf{key}(\gamma X)) +\)</p>
<p>\(v^4 \cdot L_0(\mathsf{key} - \mathsf{w}_0 - \mathsf{w}_0(\gamma ^{91}X)) +\)</p>
<p>\(v^5 \cdot L_0(\mathsf{nul\_hash} - \mathsf{w}_2 - \mathsf{w}_2(\gamma ^{91}X) - 2 \cdot \mathsf{key}) +\)</p>
<p>\(v^6 \cdot L_0 \cdot (\mathsf{w}_2 - \mathsf{ext\_nul})\)</p>
<p>These equations correspond to the gates defined in
<a href="circuit_and_gates.html#gates">4.3</a>.</p>
<p>\(\mathsf{w}_0(\gamma X)\) refers to \(\mathsf{w}_0\) shifted (or
&quot;rotated&quot;) forward by one.</p>
<p>\(\mathsf{w}_0(\gamma ^{91}X)\) refers to \(\mathsf{w}_0\) shifted forward
by 91, which is the number of MiMC7 rounds defined in
<a href="./cryptographic_specification.html#41-the-mimc7-round-constants">4.1</a>.</p>
<p>The prover then commits to \(q\) to obtain \([q]_1\).</p>
<h2 id="463-first-caulk-round"><a class="header" href="#463-first-caulk-round">4.6.3. First Caulk+ round</a></h2>
<p>The prover computes:</p>
<ul>
<li>\(\mathsf{z}_i\)</li>
<li>\(\mathsf{c}_i\)</li>
<li>\(u'\)</li>
</ul>
<p>and their commitments:</p>
<ul>
<li>\([\mathsf{z}_i]_1\)</li>
<li>\([\mathsf{c}_i]_1\)</li>
<li>\([u']_1\)</li>
</ul>
<p>according to <a href="https://eprint.iacr.org/2022/957.pdf">page 6 of the Caulk+
paper</a>.</p>
<p>The prover then updates the transcript with \([q]_1\) and the above values,
and extracts the challenge values \(\chi_1\) and \(\chi_2\), which are
used in the next round. \(\chi_1\) is also used in the opening round.</p>
<h2 id="464-second-caulk-round"><a class="header" href="#464-second-caulk-round">4.6.4. Second Caulk+ round</a></h2>
<p>The prover computes:</p>
<ul>
<li>\(\mathsf{h}\)</li>
<li>\(\mathsf{w}\)</li>
</ul>
<p>according to the Round 2 steps from <a href="https://eprint.iacr.org/2022/957.pdf">page 6 of the Caulk+
paper</a>, and commits to them:</p>
<ul>
<li>\([\mathsf{h}]_1\)</li>
<li>\([\mathsf{w}]_2\)</li>
</ul>
<p>The prover then extracts the challenge \(\alpha\), which is used in the next
round.</p>
<h2 id="465-opening-round"><a class="header" href="#465-opening-round">4.6.5. Opening round</a></h2>
<p>This section is a work in progress; in the meantime, see <a href="https://hackmd.io/D-bL6-oNSbSej7Ao_-9PLA">this
document</a> for the multiopen argument.
Also see <a href="https://hackmd.io/D-bL6-oNSbSej7Ao_-9PLA">this document</a> which
describes the argument adapted for Semacaulk.</p>
<p>The prover computes:</p>
<ul>
<li>\(\omega\): the root of unity with index 1 (starting from zero) of the
subgroup domain
((9.1)[./cryptographic_specification.html#91-the-subgroup-domain]).</li>
<li>\(\omega^n\): the root of unity with index \(n\) (starting from 0) of the
subgroup domain.</li>
</ul>
<p>The prover computes the polynomials:</p>
<!--\\(\mathsf{p}_1 = \mathsf{zi} + \mathsf{ci} \cdot \chi_1\\)-->
<!--\\(\mathsf{p}_2 = \mathsf{zi} \cdot \mathsf{u'}(\alpha) + \chi_1 \cdot \mathsf{ci}(\mathsf{u'}(\alpha))\\)-->
<ul>
<li>\(\mathsf{p}_1\)</li>
<li>\(\mathsf{p}_2\)</li>
</ul>
<p>The commitments:</p>
<ul>
<li>\([\mathsf{p}_1]_1\)</li>
<li>\([\mathsf{p}_2]_1\)</li>
</ul>
<p>The openings:</p>
<ul>
<li>\(\mathsf{w}_0(\alpha)\)</li>
<li>\(\mathsf{w}_0(\omega\alpha)\)</li>
<li>\(\mathsf{w}_0(\omega^n \alpha)\)</li>
<li>\(\mathsf{w}_1(\alpha)\)</li>
<li>\(\mathsf{w}_1(\omega\alpha)\)</li>
<li>\(\mathsf{w}_1(\omega^n \alpha)\)</li>
<li>\(\mathsf{w}_2(\alpha)\)</li>
<li>\(\mathsf{w}_2(\omega\alpha)\)</li>
<li>\(\mathsf{w}_2(\omega^n \alpha)\)</li>
<li>\(\mathsf{key}(\alpha)\)</li>
<li>\(\mathsf{key}(\omega\alpha)\)</li>
<li>\(\mathsf{q\_mimc}(\alpha)\)</li>
<li>\(\mathsf{mimc\_cts}(\alpha)\)</li>
<li>\(\mathsf{q}(\alpha)\)</li>
<li>\(\mathsf{u'}_1(\alpha)\)</li>
<li>\(\mathsf{p}_1(\mathsf{u'}_1(\alpha))\)</li>
<li>\(\mathsf{p}_2(\alpha)\)</li>
</ul>
<p>The prover adds the above openings to the transcript in the stated order.</p>
<h2 id="466-multiopen-argument-round"><a class="header" href="#466-multiopen-argument-round">4.6.6. Multiopen argument round</a></h2>
<p>The steps in this are based on the Halo2 <a href="https://zcash.github.io/halo2/design/proving-system/multipoint-opening.html">multipoint opening
argument</a>.</p>
<p>The prover computes the vanishing polynomials:</p>
<ul>
<li>\(\mathsf{z}_1 = x - \mathsf{u'}_1(\alpha)\)</li>
<li>\(\mathsf{z}_2 = x - \alpha\)</li>
<li>\(\mathsf{z}_3 = \mathsf{z}_2 \cdot (x - \omega\alpha)\)</li>
<li>\(\mathsf{z}_4 = \mathsf{z}_3 \cdot (x - \omega^n \alpha)\)</li>
</ul>
<p>The prover extracts the challenge values \(x_1\), \(x_2\), \(x_3\), and
\(x_4\).</p>
<p>The prover computes the polynomials:</p>
<ul>
<li>\(\mathsf{q}_1 = \mathsf{p}_1\)</li>
<li>\(\mathsf{q}_2 = \mathsf{q\_mimc} +
\mathsf{mimc\_cts} \cdot x_1 +
\mathsf{q} \cdot {x_1}^{2} +
\mathsf{u'} * {x_1}^{3} +
\mathsf{p}_2 \cdot {x_1}^{4}\)</li>
<li>\(\mathsf{q}_3 = \mathsf{key}\)</li>
<li>\(\mathsf{q}_4 = \mathsf{w}_0 + \mathsf{w}_1 \cdot x_1 + \mathsf{w}_2 \cdot {x_1} ^ 2\)</li>
<li>\(\mathsf{f}_1 = \mathsf{q}_1 / \mathsf{z}_1\)</li>
<li>\(\mathsf{f}_2 = \mathsf{q}_2 / \mathsf{z}_2\)</li>
<li>\(\mathsf{f}_3 = \mathsf{q}_3 / \mathsf{z}_3\)</li>
<li>\(\mathsf{f}_4 = \mathsf{q}_4 / \mathsf{z}_4\)</li>
<li>\(\mathsf{f} = \mathsf{f}_1 +
\mathsf{f}_2 \cdot x_2 +
\mathsf{f}_3 \cdot {x_2}^2 +
\mathsf{f}_4 \cdot {x_2}^3\)</li>
<li>\(\mathsf{final} = \mathsf{f} +
\mathsf{q}_1 \cdot x_4 +
\mathsf{q}_2 \cdot {x_4}^2 +
\mathsf{q}_3 \cdot {x_4}^3 +
\mathsf{q}_4 \cdot {x_4}^4\)</li>
</ul>
<p>The prover computes the openings:</p>
<ul>
<li>\(\mathsf{q}_1(x_3)\)</li>
<li>\(\mathsf{q}_2(x_3)\)</li>
<li>\(\mathsf{q}_3(x_3)\)</li>
<li>\(\mathsf{q}_4(x_3)\)</li>
</ul>
<p>The prover computes the commitments:</p>
<ul>
<li>\([\mathsf{f}]_1\)</li>
</ul>
<p>Finally, the prover computes a KZG opening proof:</p>
<ul>
<li>\(\pi_\mathsf{final} = \mathsf{open}(\mathsf{srs\_g1}, \mathsf{final},
x_3)\)</li>
</ul>
<h2 id="467-the-proof"><a class="header" href="#467-the-proof">4.6.7. The proof</a></h2>
<p>The final proof consists of:</p>
<ul>
<li>The multiopen proof
<ul>
<li>\(\mathsf{q1\_opening}\)</li>
<li>\(\mathsf{q2\_opening}\)</li>
<li>\(\mathsf{q3\_opening}\)</li>
<li>\(\mathsf{q4\_opening}\)</li>
<li>\(\mathsf{f\_cm}\)</li>
<li>\(\mathsf{final\_\pi}\)</li>
</ul>
</li>
<li>The openings
<ul>
<li>\(\mathsf{q\_mimc}\)</li>
<li>\(\mathsf{mimc\_cts}\)</li>
<li>\(\mathsf{quotient}\)</li>
<li>\(\mathsf{u\_prime}\)</li>
<li>\(\mathsf{p1}\)</li>
<li>\(\mathsf{p2}\)</li>
<li>\(\mathsf{w0}_0\)</li>
<li>\(\mathsf{w0}_1\)</li>
<li>\(\mathsf{w0}_2\)</li>
<li>\(\mathsf{w1}_0\)</li>
<li>\(\mathsf{w1}_1\)</li>
<li>\(\mathsf{w1}_2\)</li>
<li>\(\mathsf{w2}_0\)</li>
<li>\(\mathsf{w2}_1\)</li>
<li>\(\mathsf{w2}_2\)</li>
<li>\(\mathsf{key}_0\)</li>
<li>\(\mathsf{key}_1\)</li>
</ul>
</li>
<li>The commitments
<ul>
<li>\([\mathsf{w}_0]_1\)</li>
<li>\([\mathsf{w}_1]_1\)</li>
<li>\([\mathsf{w}_2]_1\)</li>
<li>\([\mathsf{key}]_1\)</li>
<li>\([\mathsf{mimc\_cts}]_1\)</li>
<li>\([\mathsf{quotient}]_1\)</li>
<li>\([\mathsf{u\_prime}]_1\)</li>
<li>\([\mathsf{zi}]_1\)</li>
<li>\([\mathsf{ci}]_1\)</li>
<li>\([\mathsf{p1}]_1\)</li>
<li>\([\mathsf{p2}]_1\)</li>
<li>\([\mathsf{q\_mimc}]_1\)</li>
<li>\([\mathsf{h}]_1\)</li>
<li>\([\mathsf{w}]_2\)</li>
</ul>
</li>
</ul>
<div style="break-before: page; page-break-before: always;"></div><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="proof-verification"><a class="header" href="#proof-verification">Proof verification</a></h1>
<p>At a high level, the verifier does three main steps to verify a proof
(<a href="proof_generation.html#466-the-proof">4.6.6</a>):</p>
<h2 id="471-check-the-gate-openings"><a class="header" href="#471-check-the-gate-openings">4.7.1. Check the gate openings</a></h2>
<p>Given the opening values which the prover claims to be evaluations of the
column polynomials which correspond to the circuit, the verifier computes the
linear combination of the evaluation of the openings based on each gate
equations separated by the \(v\) challenge values. This linear combination
must equal the product of the quotient opening and the evaluation of the
vanishing polynomial, or the verifier will return false.</p>
<h2 id="472-compute-the-multiopen-arguments-final_poly-and-final_poly_eval-values"><a class="header" href="#472-compute-the-multiopen-arguments-final_poly-and-final_poly_eval-values">4.7.2. Compute the multiopen argument's <code>final_poly</code> and <code>final_poly_eval</code> values</a></h2>
<p>Leveraging the homomorphic properties of KZG commitments, the verifier
reconstructs a commitment to the \(\mathsf{final}_\pi\) polynomial generated
in the
<a href="./proof_generation.html#466-multiopen-argument-round">prover's multiopen argument round</a>.</p>
<p>The verifier also
reconstructs \(\mathsf{final\_poly\_eval}\) which is the evaluation of
\(\mathsf{final}\) at the \(x_3\) challenge.</p>
<h2 id="473-perform-pairing-checks"><a class="header" href="#473-perform-pairing-checks">4.7.3. Perform pairing checks</a></h2>
<p>A three-part pairing product is performed and the verifier returns true only if
the result is 1.</p>
<p>\(A * B * C == 1\)</p>
<p>where:</p>
<p>\(A = e(\mathsf{a}_1 + \mathsf{a}_2 + \mathsf{a}_3, [1]_2)\)</p>
<p>\(\mathsf{a}_1 = C - [\mathsf{ci}]_1\)</p>
<p>\(\mathsf{a}_2 = \chi_2(\mathsf{srs\_g1}[t] - [1]_1)\)</p>
<p><span class="katex"><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.5944em;vertical-align:-0.15em;"></span><span class="mord"><span class="mord mathsf">a</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">3</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="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="mopen">(</span><span class="mord"><span class="mord mathnormal" style="margin-right:0.03588em;">π</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:-0.0359em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight"><span class="mord mathsf mtight">final</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="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.7333em;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">3</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="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:1.0444em;vertical-align:-0.35em;"></span><span class="mord"><span class="mord mathsf">final_poly_eval</span></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:1em;vertical-align:-0.25em;"></span><span class="mopen">[</span><span class="mord"><span class="mord mathsf">final</span></span><span class="mclose"><span class="mclose">]</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="mclose">)</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.4306em;"></span><span class="mord mathnormal">s</span></span></span></span></p>
<p>\(B = e(-[\mathsf{zi}]_1, [\mathsf{w}]_2)\)</p>
<p>\(C = e(-[\mathsf{final}_\pi]_1 \cdot s, [1]_2 \cdot \tau)\)</p>
<p>and \(s\) is a separator challenge extracted from the transcript.</p>
<div style="break-before: page; page-break-before: always;"></div><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="the-lagrange-basis-polynomial-commitment-tree"><a class="header" href="#the-lagrange-basis-polynomial-commitment-tree">The Lagrange Basis Polynomial Commitment Tree</a></h1>
<p>The Semacaulk contract's <code>insertIdentity</code> function requires access to a valid
commitment to the Lagrange basis polynomial at the index at which an insertion
is made. This commitment is prohibitively expensive to compute on-chain, so
we instead have a Merkle root to the hashes of all of these commitments be set
as an immutable storage variable at deployment time. The user only has to
provide a Merkle path to said commitment, which the contract can cheaply
verify. These commitments are deterministic and anyone can verify that the
Merkle root to these values is valid.</p>
<h2 id="code"><a class="header" href="#code">Code</a></h2>
<p>The Rust function to compute the Lagrange basis polynomial commitments is
<code>commit_to_lagrange_bases</code> located in <code>src/accumulator.rs</code>. The code to compute
the Merkle tree of the hashes of these commitments is also located in the same
file.</p>
<div style="break-before: page; page-break-before: always;"></div><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="mechanism-of-operation"><a class="header" href="#mechanism-of-operation">Mechanism of Operation</a></h1>
<p>The goal of Semacaulk is to enable users to:</p>
<ol>
<li>Register their identity;</li>
<li>Prove in zero-knowledge that they are a member of the set of registered users;</li>
<li>Broadcast an arbitrary signal towards an external nullifier, without the
possibility of double-signalling.</li>
</ol>
<h2 id="61-user-identities"><a class="header" href="#61-user-identities">6.1. User identities</a></h2>
<p>A user's identity consists of an <em>identity nullifier</em> \(\mathsf{id\_nul}\)
and an <em>identity trapdoor</em> \(\mathsf{id\_trap}\). These are secret values
and are elements of \(\mathbb{F}_r\) (see <a href="./cryptographic_specification.html#11-the-bn254-scalar-field">1.1</a>).</p>
<p>An <em>identity commitment</em> \(\mathsf{id\_comm}\) is the MiMC7 <code>multi_hash</code> (see <a href="./cryptographic_specification.html#43-the-mimc7-multi_hash-algorithm">4.3</a>)
of \(\mathsf{id\_nul}\) and \(\mathsf{id\_trap}\):</p>
<p>\(\mathsf{id\_comm} = \mathsf{multi\_hash}([\mathsf{id\_nul}, \mathsf{id\_trap}])\)</p>
<h2 id="62-external-nullifiers"><a class="header" href="#62-external-nullifiers">6.2. External nullifiers</a></h2>
<p>An <em>external nullifier</em> \(\mathsf{ext\_nul}\) is a \(\mathbb{F}_r\) field
element which represents a topic. A signal can only be broadcast towards each
external nullifier once and only once.</p>
<h2 id="63-nullifier-hashes"><a class="header" href="#63-nullifier-hashes">6.3. Nullifier hashes</a></h2>
<p>A nullifier hash is the MiMC7 <code>multi_hash</code> of
\(\mathsf{id\_nul}\) and \(\mathsf{ext\_nul}\):</p>
<p>\(\mathsf{nul\_hash} = \mathsf{multi\_hash}([\mathsf{id\_nul}, \mathsf{ext\_nul}])\)</p>
<h2 id="64-insertions"><a class="header" href="#64-insertions">6.4. Insertions</a></h2>
<p>An <em>insertion</em> is the act of updating the on-chain accumulator with a user's
identity commitment. This is done by invoking the <code>insertIdentity()</code> function
of the Semacaulk smart contract.</p>
<h2 id="65-broadcasting-a-signal"><a class="header" href="#65-broadcasting-a-signal">6.5. Broadcasting a signal</a></h2>
<p>When a user <em>broadcasts a signal</em>, they generate a proof that they know the
secret identity nullifier and identity trapdoor behind their identity
commitment, and then submit said proof to the Semacaulk smart contract's
<code>broadcastSignal()</code> function.</p>
<p>Tied to this proof is the hash of a <em>signal</em> and the user's desired external
nullifier. The contract (not the user) hashes the user-provided signal using
Keccak256 and right-shifts the result by 8 bits to derive
\(\mathsf{sig\_hash}\), which is used as one of the public inputs to the
verifier.</p>
<h3 id="66-preventing-double-signalling"><a class="header" href="#66-preventing-double-signalling">6.6. Preventing double-signalling</a></h3>
<p>The Semacaulk smart contract maintains a mapping of nullifier hashes. Each
nullifier hash is unique to the user and an external nullifier. If the
<code>broadcastSignal()</code> function finds that a nullifier hash has already been seen,
it rejects the transaction, thus preventing double-signalling.</p>
<div style="break-before: page; page-break-before: always;"></div><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="ethereum-contracts"><a class="header" href="#ethereum-contracts">Ethereum contracts</a></h1>
<h2 id="semacaulksol"><a class="header" href="#semacaulksol"><code>Semacaulk.sol</code></a></h2>
<p>The main Semacaulk contract which client applications should interact with or
inherit. The key functions it exposes are:</p>
<h3 id="insertidentity"><a class="header" href="#insertidentity"><code>insertIdentity</code></a></h3>
<p>Functions signature: <code>insertIdentity(uint256 _identityCommitment, uint256 _lagrangeLeafX, uint256 _lagrangeLeafY, bytes32[] memory _lagrangeMerkleProof</code>)</p>
<p><code>_identityCommitment</code> is the user-generated value defined in
<a href="./mechanism_of_operation.html#61-user-identities">6.1</a>.</p>
<p><code>_lagrangeLeafX</code> and <code>_lagrangeLeafY</code> are the respective X and Y coordinates of
the commitment to the Lagrange basis polynomial of the index at which the user
wishes to insert their identity commitment.</p>
<p><code>_lagrangeMerkleProof</code> is the Merkle proof from the Keccak256 hash of
<code>_lagrangeLeafX</code> and <code>_lagrangeLeafY</code> to the root of the <a href="./lagrange_basis_polynomial_commitment_tree.html">Lagrange Basis
Polynomial Commitment Tree</a>.</p>
<p>This function first verifies the Merkle proof to ensure that <code>_lagrangeLeafX</code>
and <code>_lagrangeLeafY</code> are valid. Next, it performs field and elliptic curve
operations to perform an <a href="./insertion.html">insertion</a> to update the
accumulator.</p>
<h3 id="broadcastsignal"><a class="header" href="#broadcastsignal"><code>broadcastSignal</code></a></h3>
<p>Function signature: <code>broadcastSignal(bytes memory _signal, Types.Proof memory proof, uint256 _nullifierHash, uint256 _externalNullifier)</code></p>
<p>This function performs the following steps:</p>
<ol>
<li>Revert if <code>_nullifierHash</code> has already been seen. This prevents double-signalling.</li>
<li>Compute the <span class="katex"><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1.0444em;vertical-align:-0.35em;"></span><span class="mord"><span class="mord mathsf">sig_hash</span></span></span></span></span> public input by hashing <code>_signal</code> with
Keccak256 and right-shifting the result by 8 bits.</li>
<li>Verify the proof and revert if it is invalid.</li>
<li>Store the nullifier hash.</li>
</ol>
<h2 id="verifiersol"><a class="header" href="#verifiersol"><code>Verifier.sol</code></a></h2>
<p>This contract exposes a <code>verify()</code> function for the Semacaulk contract's
<code>broadcastSignal</code> function to use. It performs the steps described in
<a href="./verification.html">4.7</a>.</p>
<h2 id="transcriptsol"><a class="header" href="#transcriptsol"><code>Transcript.sol</code></a></h2>
<p>This contract abstracts over the Fiat-Shamir Heuristic by providing helper
functions to the verifier to add data to the transcript and extract the
challenge values it needs.</p>
<h2 id="typessol"><a class="header" href="#typessol"><code>Types.sol</code></a></h2>
<p>A helper library that defines complex Solidity types that comprise the proof.</p>
<h2 id="bn254sol"><a class="header" href="#bn254sol"><code>BN254.sol</code></a></h2>
<p>Provides functions that encapsulate elliptic curve operations over the BN254
curve.</p>
<h2 id="keccakmtsol"><a class="header" href="#keccakmtsol"><code>KeccakMT.sol</code></a></h2>
<p>Provides a helper function for the Semacaulk contract's <code>insertIdentity</code>
function to verify a Merkle proof.</p>
<h2 id="lagrangesol"><a class="header" href="#lagrangesol"><code>Lagrange.sol</code></a></h2>
<p>Provides a helper function for the verifier contract to compute the evaluation
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 mathnormal">L</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">0</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> at a given point <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.0037em;">α</span></span></span></span>, and the evaluation of the vanishing
polynomial at <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.0037em;">α</span></span></span></span>.</p>
<h2 id="constantssol"><a class="header" href="#constantssol"><code>Constants.sol</code></a></h2>
<p>Contains crucial constant values:</p>
<ul>
<li><code>PRIME_Q</code>: the order of the BN254 base field.</li>
<li><code>PRIME_R</code>: the order of the BN254 scalar field.</li>
<li><code>DOMAIN_SIZE_INV</code>: the inverse of the domain size (128) over the BN254 scalar field.</li>
<li><code>LOG2_DOMAIN_SIZE</code>: the binary logarithm of the domain size such that <code>2 ^ LOG2_DOMAIN_SIZE = 128</code>.</li>
<li><code>OMEGA</code>: the 1st root of unity (counting from 0) of the subgroup domain.</li>
<li><code>OMEGA_N</code>: the <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">n</span></span></span></span>th root of unity (counting from 0) of the subgroup domain.</li>
</ul>
<p>The following constants depend on the maximum size of the accumulator, and
should be changed depending on how many elements the client application wishes
to support.</p>
<ul>
<li><code>SRS_G1_T_X</code>: The X coordinate of <span class="katex"><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1.1em;vertical-align:-0.35em;"></span><span class="mord"><span class="mord mathsf">srs_g1</span></span><span class="mopen">[</span><span class="mord mathnormal">t</span><span class="mclose">]</span></span></span></span></li>
<li><code>SRS_G1_T_Y</code>: The Y coordinate of <span class="katex"><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1.1em;vertical-align:-0.35em;"></span><span class="mord"><span class="mord mathsf">srs_g1</span></span><span class="mopen">[</span><span class="mord mathnormal">t</span><span class="mclose">]</span></span></span></span></li>
<li><code>SRS_G2_1_X_0</code>: The X0 coordinate of <span class="katex"><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1.1em;vertical-align:-0.35em;"></span><span class="mord"><span class="mord mathsf">srs_g2</span></span><span class="mopen">[</span><span class="mord">1</span><span class="mclose">]</span></span></span></span></li>
<li><code>SRS_G2_1_X_1</code>: The X1 coordinate of <span class="katex"><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1.1em;vertical-align:-0.35em;"></span><span class="mord"><span class="mord mathsf">srs_g2</span></span><span class="mopen">[</span><span class="mord">1</span><span class="mclose">]</span></span></span></span></li>
<li><code>SRS_G2_1_Y_0</code>: The Y0 coordinate of <span class="katex"><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1.1em;vertical-align:-0.35em;"></span><span class="mord"><span class="mord mathsf">srs_g2</span></span><span class="mopen">[</span><span class="mord">1</span><span class="mclose">]</span></span></span></span></li>
<li><code>SRS_G2_1_Y_1</code>: The Y1 coordinate of <span class="katex"><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1.1em;vertical-align:-0.35em;"></span><span class="mord"><span class="mord mathsf">srs_g2</span></span><span class="mopen">[</span><span class="mord">1</span><span class="mclose">]</span></span></span></span></li>
</ul>
<div style="break-before: page; page-break-before: always;"></div><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="gas-costs"><a class="header" href="#gas-costs">Gas costs</a></h1>
<p>An insertion (via <code>insertIdentity()</code> costs around 68k gas.</p>
<p><code>broadcastSignal()</code>, which includes proof verification, costs around 355k gas.</p>
<p>By contrast, a Tornado Cash deposit (which involves inserting a leaf to a
Merkle tree) costs <a href="https://etherscan.io/tx/0x6f60a4aa7058dab153a859adfb139362d4bc395145528371ed90b127e528c7e7">907787
gas</a>
and a withdrawal (which involves a Groth16 verification step) costs <a href="https://etherscan.io/tx/0xf2eb3005bf1d1866b4778d6b3686aaed64f8c6b015d2e998855598226223b613">327188
gas</a>.</p>
<div style="break-before: page; page-break-before: always;"></div><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="performance-and-benchmarks"><a class="header" href="#performance-and-benchmarks">Performance and Benchmarks</a></h1>
<p>These benchmarks were performed on an Intel(R) Core(TM) i7-8565U CPU @ 1.80GHz
machine with 24 GB RAM. They represent the time taken for a native Rust binary
(built for <code>release</code>) to perform the precomputation and proof generation steps.</p>
<p>To reproduce these benchamarks, run the <code>demo</code> binary following <a href="./quick_start.html">these instructions</a>.</p>
<h2 id="benchmarks"><a class="header" href="#benchmarks">Benchmarks</a></h2>
<div class="table-wrapper"><table><thead><tr><th>Maximum capacity</th><th>Precomputation (ms)</th><th>Proof generation (ms)</th><th>Precomputation + proving</th><th>SRS size (uncompressed hex) (MB)</th></tr></thead><tbody>
<tr><td><code>2 ** 11 = 2048</code></td><td><code>103</code></td><td><code>63</code></td><td><code>166</code></td><td><code>0.78</code></td></tr>
<tr><td><code>2 ** 12 = 4096</code></td><td><code>183</code></td><td><code>51</code></td><td><code>234</code></td><td><code>1.6</code></td></tr>
<tr><td><code>2 ** 14 = 16384</code></td><td><code>668</code></td><td><code>53</code></td><td><code>721</code></td><td><code>6.1</code></td></tr>
<tr><td><code>2 ** 16 = 65536</code></td><td><code>2126</code></td><td><code>50</code></td><td><code>2176</code></td><td><code>25</code></td></tr>
<tr><td><code>2 ** 20 = 1048576</code></td><td><code>24333</code></td><td><code>42</code></td><td><code>24375</code></td><td><code>387</code></td></tr>
</tbody></table>
</div><div style="break-before: page; page-break-before: always;"></div><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="credits"><a class="header" href="#credits">Credits</a></h1>
<p>Semacaulk was written by:</p>
<ul>
<li>Andrija Novakovic (<a href="mailto:andrija@geometry.xyz">andrija@geometry.xyz</a>)</li>
<li>Koh Wei Jie (<a href="wj@geometry.xyz">wj@geometry.xyz</a>)</li>
<li>Kobi Gurkan (<a href="kobi@geometry.xyz">kobi@geometry.xyz</a>)</li>
</ul>
<p>Special thanks to these contributors for their feedback and support:</p>
<ul>
<li>Nicolas Mohnblatt (<a href="mailto:nico@geometry.xyz">nico@geometry.xyz </a>)</li>
<li>Tom Walton-Pocock (<a href="mailto:tom@geometry.xyz">tom@geometry.xyz</a>)</li>
<li>Lai Ying Tong (<a href="mailto:yingtong@geometry.xyz">yingtong@geometry.xyz</a>)</li>
</ul>
<p>Last but not least, we would also like to thank:</p>
<ul>
<li>Jon Stephens from <a href="https://veridise.com/">Veridise</a> and Andy Guzman from
<a href="https://semaphore.appliedzkp.org/">Sempahore</a> for sharing
information about Semaphore's invariants used in their formal audit.</li>
</ul>
</main>
<nav class="nav-wrapper" aria-label="Page navigation">
<!-- Mobile navigation buttons -->
<div style="clear: both"></div>
</nav>
</div>
</div>
<nav class="nav-wide-wrapper" aria-label="Page navigation">
</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 -->
<script>
window.addEventListener('load', function() {
MathJax.Hub.Register.StartupHook('End', function() {
window.setTimeout(window.print, 100);
});
});
</script>
</body>
</html>
Reference in New Issue View Git Blame Copy Permalink