github/Sunscreen
1
1
Fork 0
mirror of https://github.com/Sunscreen-tech/Sunscreen.git synced 2026-01-14 08:07:56 -05:00
Code Issues Packages Projects Releases Wiki Activity
Files
sunscreen
Sunscreen/sunscreen_docs/book/print.html
Rick Weber a323229243 WIP
2022-05-02 12:05:08 -07:00

2621 lines
191 KiB
HTML
Raw Permalink Blame History

This file contains ambiguous Unicode characters
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>Sunscreen Documentation</title>
<meta name="robots" content="noindex" />
<!-- Custom HTML head -->
<meta content="text/html; charset=utf-8" http-equiv="Content-Type">
<meta name="description" content="">
<meta name="viewport" content="width=device-width, initial-scale=1">
<meta name="theme-color" content="#ffffff" />
<link rel="icon" href="favicon.svg">
<link rel="shortcut icon" href="favicon.png">
<link rel="stylesheet" href="css/variables.css">
<link rel="stylesheet" href="css/general.css">
<link rel="stylesheet" href="css/chrome.css">
<link rel="stylesheet" href="css/print.css" media="print">
<!-- Fonts -->
<link rel="stylesheet" href="FontAwesome/css/font-awesome.css">
<link rel="stylesheet" href="fonts/fonts.css">
<!-- Highlight.js Stylesheets -->
<link rel="stylesheet" href="highlight.css">
<link rel="stylesheet" href="tomorrow-night.css">
<link rel="stylesheet" href="ayu-highlight.css">
<!-- Custom theme stylesheets -->
<!-- MathJax -->
<script async type="text/javascript" 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 type="text/javascript">
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 type="text/javascript">
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 type="text/javascript">
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 type="text/javascript">
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="intro/intro.html"><strong aria-hidden="true">1.</strong> Introduction</a></li><li><ol class="section"><li class="chapter-item expanded "><a href="intro/prelim.html"><strong aria-hidden="true">1.1.</strong> Prerequisites</a></li><li class="chapter-item expanded "><a href="intro/why.html"><strong aria-hidden="true">1.2.</strong> Why is a compiler needed for FHE?</a></li><li class="chapter-item expanded "><a href="intro/compiler.html"><strong aria-hidden="true">1.3.</strong> Sunscreen's compiler</a></li></ol></li><li class="chapter-item expanded "><a href="getting_started/getting_started.html"><strong aria-hidden="true">2.</strong> Getting started</a></li><li><ol class="section"><li class="chapter-item expanded "><a href="getting_started/installation.html"><strong aria-hidden="true">2.1.</strong> Installation</a></li><li class="chapter-item expanded "><a href="getting_started/example.html"><strong aria-hidden="true">2.2.</strong> My first FHE program</a></li></ol></li><li class="chapter-item expanded "><a href="fhe_programs/fhe_programs.html"><strong aria-hidden="true">3.</strong> What's in an FHE program?</a></li><li><ol class="section"><li class="chapter-item expanded "><a href="fhe_programs/types/types.html"><strong aria-hidden="true">3.1.</strong> Types</a></li><li><ol class="section"><li class="chapter-item expanded "><a href="fhe_programs/types/signed.html"><strong aria-hidden="true">3.1.1.</strong> Signed</a></li><li class="chapter-item expanded "><a href="fhe_programs/types/fractional.html"><strong aria-hidden="true">3.1.2.</strong> Fractional</a></li><li class="chapter-item expanded "><a href="fhe_programs/types/rational.html"><strong aria-hidden="true">3.1.3.</strong> Rational</a></li></ol></li><li class="chapter-item expanded "><a href="fhe_programs/writing_an_fhe_program/writing_an_fhe_program.html"><strong aria-hidden="true">3.2.</strong> How to write an FHE program</a></li><li><ol class="section"><li class="chapter-item expanded "><a href="fhe_programs/factoring_fhe_programs.html"><strong aria-hidden="true">3.2.1.</strong> Factoring FHE programs</a></li><li class="chapter-item expanded "><a href="fhe_programs/writing_an_fhe_program/limitations.html"><strong aria-hidden="true">3.2.2.</strong> Limitations</a></li></ol></li><li class="chapter-item expanded "><a href="troubleshooting.html"><strong aria-hidden="true">3.3.</strong> Troubleshooting</a></li></ol></li><li class="chapter-item expanded "><a href="fhe_programs/runtime/runtime.html"><strong aria-hidden="true">4.</strong> Runtime</a></li><li><ol class="section"><li class="chapter-item expanded "><a href="fhe_programs/runtime/key_generation.html"><strong aria-hidden="true">4.1.</strong> Key generation</a></li><li class="chapter-item expanded "><a href="fhe_programs/runtime/encryption.html"><strong aria-hidden="true">4.2.</strong> Encryption</a></li><li class="chapter-item expanded "><a href="fhe_programs/runtime/running_fhe_programs.html"><strong aria-hidden="true">4.3.</strong> Running FHE programs</a></li><li class="chapter-item expanded "><a href="fhe_programs/runtime/decryption.html"><strong aria-hidden="true">4.4.</strong> Decryption</a></li><li class="chapter-item expanded "><a href="fhe_programs/runtime/serialization.html"><strong aria-hidden="true">4.5.</strong> Serialization</a></li></ol></li><li class="chapter-item expanded "><a href="fhe_programs/apps.html"><strong aria-hidden="true">5.</strong> Applications</a></li><li><ol class="section"><li class="chapter-item expanded "><a href="fhe_programs/example.html"><strong aria-hidden="true">5.1.</strong> AMMs &amp; private token swaps</a></li><li class="chapter-item expanded "><a href="fhe_programs/pir_intro.html"><strong aria-hidden="true">5.2.</strong> Private information retrieval</a></li><li><ol class="section"><li class="chapter-item expanded "><a href="fhe_programs/pir_simple.html"><strong aria-hidden="true">5.2.1.</strong> Take 1</a></li><li class="chapter-item expanded "><a href="fhe_programs/pir_matrix.html"><strong aria-hidden="true">5.2.2.</strong> Take 2</a></li></ol></li><li class="chapter-item expanded "><div><strong aria-hidden="true">5.3.</strong> Genomics &amp; private tests</div></li></ol></li><li class="chapter-item expanded "><a href="advanced/faq.html"><strong aria-hidden="true">6.</strong> FAQ</a></li><li class="chapter-item expanded "><a href="advanced/advanced.html"><strong aria-hidden="true">7.</strong> Advanced topics</a></li><li><ol class="section"><li class="chapter-item expanded "><a href="advanced/bfv.html"><strong aria-hidden="true">7.1.</strong> Why the BFV scheme?</a></li><li class="chapter-item expanded "><a href="advanced/good_fhe_programs.html"><strong aria-hidden="true">7.2.</strong> Writing even better FHE programs</a></li><li><ol class="section"><li class="chapter-item expanded "><a href="advanced/plain_modulus/plain_modulus.html"><strong aria-hidden="true">7.2.1.</strong> Plaintext modulus</a></li><li class="chapter-item expanded "><a href="advanced/noise_margin.html"><strong aria-hidden="true">7.2.2.</strong> Noise</a></li><li class="chapter-item expanded "><a href="advanced/pruning_keys.html"><strong aria-hidden="true">7.2.3.</strong> Pruning public keys</a></li></ol></li><li class="chapter-item expanded "><a href="advanced/wasm.html"><strong aria-hidden="true">7.3.</strong> WASM support</a></li><li class="chapter-item expanded "><a href="advanced/carryless_arithmetic.html"><strong aria-hidden="true">7.4.</strong> Funky math: carryless arithmetic</a></li><li class="chapter-item expanded "><div><strong aria-hidden="true">7.5.</strong> Batching</div></li></ol></li></ol>
</div>
<div id="sidebar-resize-handle" class="sidebar-resize-handle"></div>
</nav>
<div id="page-wrapper" class="page-wrapper">
<div class="page">
<div id="menu-bar-hover-placeholder"></div>
<div id="menu-bar" class="menu-bar sticky bordered">
<div class="left-buttons">
<button id="sidebar-toggle" class="icon-button" type="button" title="Toggle Table of Contents" aria-label="Toggle Table of Contents" aria-controls="sidebar">
<i class="fa fa-bars"></i>
</button>
<button id="theme-toggle" class="icon-button" type="button" title="Change theme" aria-label="Change theme" aria-haspopup="true" aria-expanded="false" aria-controls="theme-list">
<i class="fa fa-paint-brush"></i>
</button>
<ul id="theme-list" class="theme-popup" aria-label="Themes" role="menu">
<li role="none"><button role="menuitem" class="theme" id="light">Light (default)</button></li>
<li role="none"><button role="menuitem" class="theme" id="rust">Rust</button></li>
<li role="none"><button role="menuitem" class="theme" id="coal">Coal</button></li>
<li role="none"><button role="menuitem" class="theme" id="navy">Navy</button></li>
<li role="none"><button role="menuitem" class="theme" id="ayu">Ayu</button></li>
</ul>
<button id="search-toggle" class="icon-button" type="button" title="Search. (Shortkey: s)" aria-label="Toggle Searchbar" aria-expanded="false" aria-keyshortcuts="S" aria-controls="searchbar">
<i class="fa fa-search"></i>
</button>
</div>
<h1 class="menu-title">Sunscreen Documentation</h1>
<div class="right-buttons">
<a href="print.html" title="Print this book" aria-label="Print this book">
<i id="print-button" class="fa fa-print"></i>
</a>
</div>
</div>
<div id="search-wrapper" class="hidden">
<form id="searchbar-outer" class="searchbar-outer">
<input type="search" id="searchbar" name="searchbar" placeholder="Search this book ..." aria-controls="searchresults-outer" aria-describedby="searchresults-header">
</form>
<div id="searchresults-outer" class="searchresults-outer hidden">
<div id="searchresults-header" class="searchresults-header"></div>
<ul id="searchresults">
</ul>
</div>
</div>
<!-- Apply ARIA attributes after the sidebar and the sidebar toggle button are added to the DOM -->
<script type="text/javascript">
document.getElementById('sidebar-toggle').setAttribute('aria-expanded', sidebar === 'visible');
document.getElementById('sidebar').setAttribute('aria-hidden', sidebar !== 'visible');
Array.from(document.querySelectorAll('#sidebar a')).forEach(function(link) {
link.setAttribute('tabIndex', sidebar === 'visible' ? 0 : -1);
});
</script>
<div id="content" class="content">
<main>
<h1 id="introduction-to-fhe-and-our-compiler"><a class="header" href="#introduction-to-fhe-and-our-compiler">Introduction to FHE and our compiler</a></h1>
<p>Fully homomorphic encryption (FHE) is the next generation of public key encryption schemes. Standard public key encryption allows anyone to share data in a secure way. However, you can't really <em>do</em> anything with this encrypted data, apart from decrypting it. That's where FHE comes in! </p>
<p>Using FHE, anyone can perform computations directly on private (i.e. encrypted) data—no need to decrypt.</p>
<p>We recommend starting with <a href="https://blog.nucypher.com/an-engineers-guide-to-fully-homomorphic-encryption/">this article</a> if you're new to FHE.</p>
<h3 id="why-should-i-care-about-fhe"><a class="header" href="#why-should-i-care-about-fhe">Why should I care about FHE?</a></h3>
<p>FHE has applications to a variety of fields. We'll briefly consider two applications of FHE in the blockchain and machine learning space.</p>
<p>In blockchain, FHE enables <a href="https://eprint.iacr.org/2021/727">privacy-preserving smart contracts</a>. We have two parties in this setting: users and miners. Users can share their private data to the chain in the form of transactions. Miners can then run computations (encoded as smart contracts) directly on users' private data.</p>
<p>In machine learning, FHE allows for private inference. We have two parties in this setting: the user (who owns the data) and the server (who owns the trained machine learning model). The user can share her private data with the server. The server can then run the model on the user's encrypted data to give her a private prediction (which only she knows!). </p>
<h3 id="why-havent-i-already-used-fhe"><a class="header" href="#why-havent-i-already-used-fhe">Why haven't I already used FHE?</a></h3>
<p>FHE used to be incredibly slow. Performance has come a long way in the past few years; operations that used to take seconds (or even minutes) now take milliseconds (if not microseconds). </p>
<p>As magical as FHE is, it's actually <a href="intro/./why.html">very hard</a> to write FHE programs unless you're a cryptography expert (even then it's pretty hard).
Researchers built various FHE compilers in an attempt to improve usability. Unfortunately, these compilers failed for one of the following reasons: they introduced a <a href="intro/./compiler.html#compiler-performance">huge performance overhead</a>, expected the user to know quite a bit about how FHE works, or were poorly designed for the target applications.</p>
<p>For FHE to see widespread adoption, we need usability <em>and</em> great performance.</p>
<div style="break-before: page; page-break-before: always;"></div><h1 id="preliminary-knowledge"><a class="header" href="#preliminary-knowledge">Preliminary knowledge</a></h1>
<p>To effectively use our library, we assume some basic knowledge of public key cryptography as well as Rust.</p>
<h2 id="cryptography-and-math"><a class="header" href="#cryptography-and-math">Cryptography and math</a></h2>
<ul>
<li><strong>Plaintext vs. ciphertext</strong>: Plaintext refers to <em>un</em>encrypted data (i.e. data in the clear) whereas ciphertext refers to <em>encrypted</em> data.</li>
<li><strong>Public key vs. private key</strong>: In <a href="intro/">public key cryptography</a>, there are two types of keys. The <em>public</em> key (aka the encryption key) can be shared with others. Using the public key, people can send encrypted messages. The <em>private</em> key (aka the decryption key) should <em>not</em> be shared. Whoever holds the private key can decrypt the messages addressed to them (which are encrypted under the corresponding public key). Usually, each person has their own public/private key pair. </li>
<li><strong>&quot;Homomorphic&quot;</strong>: We use this term to denote computations performed directly on encrypted data. For example, if we say &quot;homomorphic addition,&quot; we are referring to addition of two <em>ciphertexts</em>. </li>
<li><strong>Modulus</strong>: We use this term in the context of discussing modular arithmetic (aka clock arithmetic). Under modular arithmetic, values &quot;wrap around&quot; when they exceed the <em>modulus</em>. In the example <code>7 mod 4 = 3</code>, <code>4</code> is the modulus. </li>
</ul>
<h2 id="rust-and-programming"><a class="header" href="#rust-and-programming">Rust and programming</a></h2>
<ul>
<li>Rust basics (e.g. <a href="https://doc.rust-lang.org/book/ch03-02-data-types.html">rust types</a>, <a href="https://doc.rust-lang.org/book/ch10-02-traits.html">traits</a>, <a href="https://doc.rust-lang.org/book/ch09-03-to-panic-or-not-to-panic.html"><code>.unwrap()</code></a> and other error handling techniques)</li>
<li><a href="https://doc.rust-lang.org/book/ch10-01-syntax.html">Generic types</a></li>
<li><a href="https://doc.rust-lang.org/book/ch10-00-generics.html">Generic functions</a></li>
</ul>
<div style="break-before: page; page-break-before: always;"></div><h1 id="why-is-a-compiler-needed-for-fhe"><a class="header" href="#why-is-a-compiler-needed-for-fhe">Why is a compiler needed for FHE?</a></h1>
<blockquote>
<p>Why is it so hard to write FHE programs?</p>
</blockquote>
<p><em>Note:</em> The following is not a <em>precise description</em> of the math behind FHE. Our goal is to give you a high level overview as to why it's hard to work with FHE directly. </p>
<p>FHE makes use of some pretty fancy math—namely, <a href="https://en.wikipedia.org/wiki/Lattice_(group)">lattices</a>. In fact, all known FHE schemes use lattice-based cryptography. Something special about lattice-based cryptography is that it's <a href="https://en.wikipedia.org/wiki/Post-quantum_cryptography">post-quantum</a>.</p>
<p>You're likely familiar with matrices and vectors. Imagine that instead of having <em>numbers</em> as the entries in a matrix or vector, we replace them with <em>polynomials</em> (e.g. \(8x^5+5x^2+x+13\)). You might wonder: why would we want to have polynomials instead of numbers as entries? Well, replacing a number with a polynomial allows us to embed <em>many</em> numbers (as coefficients) in a single matrix entry, thus leading to better efficiency/performance. Recall that polynomials consist of coefficients (these would be <code>8</code>, <code>5</code>, <code>1</code>, <code>13</code> in our example) and a degree/order (this is 5 in our example). However, these polynomials behave a bit differently than what you've seen in grade school. </p>
<p>Let's take a brief detour and discuss modular arithmetic (aka clock arithmetic). Modular arithmetic is just integer arithmetic that &quot;wraps&quot; around. Alternatively, you can think of it as division with remainder. For example, <code>13 mod 12 = 1</code>.</p>
<p>The polynomials in FHE make use of modular arithmetic. The degree is actually mod some value; we'll say degree mod <code>N</code>. The coefficients are also mod some value; we'll say coefficient mod <code>P</code>. </p>
<p>So if I tell you to take the degree <code>mod 3</code> and the coefficients <code>mod 7</code>, \(8x^5+5x^2+x+13\) becomes \(1x^2+5x^2+x+6\). </p>
<p>To get good performance in FHE, you need to know how to set these parameters (N, P) <em>just right</em>. If the parameters are too small, you'll be very limited in terms of the computations you can do. Alternatively, if you make the parameters too big, you'll end with poor performance and large ciphertext sizes. Even worse, you need to base your parameter choices off the maximum sequence of multiplications you plan on doing along with the desired security level.</p>
<p>Finally, I've neglected to mention how FHE programs actually work. Under the hood, FHE uses circuits. For the BFV scheme, we have arithmetic circuits (some other FHE schemes use binary circuits). When was the last time you tried to work directly with circuits (if ever)? </p>
<p>Our compiler handles picking all parameters and the appropriate keys for you. We abstract away the polynomials and circuits too.</p>
<div style="break-before: page; page-break-before: always;"></div><h1 id="sunscreens-compiler"><a class="header" href="#sunscreens-compiler">Sunscreen's compiler</a></h1>
<p>Our goal is to make it easy for <em>any engineer</em> to write an FHE program. To accomplish this, we've been working to get the API just right (we're always excited to hear feedback from users!). A large part of this was choosing the right language for our compiler— we chose <a href="https://www.rust-lang.org/">Rust</a>. In addition to having a powerful and expressive type system, Rust is very well suited to cryptography. It's highly performant (like C/C++) <em>and</em> safe by design (unlike C/C++). </p>
<p>Our compiler relies on Microsoft's <a href="https://github.com/microsoft/SEAL">SEAL</a> library. There are many different types of FHE schemes out there; we've chosen to use the BFV fully homomorphic encryption scheme—named for the authors (Brakerski-Fan-Vercauteren) who came up with the scheme.</p>
<h2 id="what-features-does-our-compiler-offer"><a class="header" href="#what-features-does-our-compiler-offer">What features does our compiler offer?</a></h2>
<p>This list isn't comprehensive. These are just the main features we'd like to call attention to:</p>
<ul>
<li>Type support for fractions, rationals, and signed integers (even 64-bit integers!)</li>
<li>Ability to perform computations on combinations of plaintexts and ciphertexts (e.g. you can multiply a ciphertext and plaintext together)</li>
<li>Can run computations without FHE (useful for testing purposes)</li>
<li>Private computation with literals</li>
<li>Automated parameter and key selection</li>
<li>Ciphertext maintenance operations inserted automatically (these operations need to be done for optimal performance)</li>
<li>Compiler generates FHE programs for you (no need to work with circuits)</li>
<li>Compiler automatically parallelizes program (i.e. circuit) execution for you</li>
<li>Support for WASM</li>
<li>Support for serialization</li>
<li>Can compile natively to Apple's M1 </li>
</ul>
<p><em>Note:</em> Although we have performed a number of optimizations, we don't take advantage of all possible compiler transforms (yet!). Additionally, we do not currently allow users to author their own types.</p>
<h2 id="who-should-use-our-compiler"><a class="header" href="#who-should-use-our-compiler">Who should use our compiler?</a></h2>
<p>You're building an application that operates on user data <em>but</em> you want to ensure all user data remains private.</p>
<h3 id="youre-a-web3-engineer"><a class="header" href="#youre-a-web3-engineer">You're a web3 engineer.</a></h3>
<p>Our compiler was primarily designed with your web3 needs in mind!</p>
<p>You likely need all of the following features:</p>
<ul>
<li>Exact computation (since you're working with account balances and currency transfer)</li>
<li>Compatibility with efficient ZKP schemes for trustless decentralized applications (we plan to provide the appropriate libraries for this)</li>
<li>Support for fractions/rationals/big integers</li>
<li>Fast arithmetic</li>
<li>Exceptional performance overall</li>
</ul>
<p>You may notice that FHE ciphertexts can sometimes be quite large. In the future, we'll help you manage this issue. </p>
<h3 id="youre-a-web2-engineer"><a class="header" href="#youre-a-web2-engineer">You're a web2 engineer.</a></h3>
<p>Performance is very important to you; more importantly, the code needs to be easy to understand and write since you don't have the time to learn the intricacies of FHE or (god forbid) an entirely new language. You may need to perform 32 or even 64 bit computation.</p>
<p>Our compiler is great for many web2 applications (e.gg data analysis on private data). Comparisons on encrypted data are not currently supported; please keep this in mind when deciding if our compiler is best suited to your application. We will likely expand support to other FHE schemes in the future. The CKKS scheme, for example, is often better suited to privacy-preserving machine learning applications than the BFV scheme.</p>
<h3 id="youre-a-researcher"><a class="header" href="#youre-a-researcher">You're a researcher.</a></h3>
<p>You want to quickly prototype FHE applications without fussing over the optimal parameter choice. However, performance is very important and you don't want to introduce a significant slowdown by working with an FHE compiler (over the FHE scheme directly).</p>
<p>We also provide advanced features that allow you to fine tune the <a href="intro/./../advanced/plain_modulus/plain_modulus.html">plaintext modulus</a> choice and <a href="intro/./../advanced/noise_margin.html">noise margin</a> if desired.</p>
<h2 id="compiler-performance"><a class="header" href="#compiler-performance">Compiler performance</a></h2>
<p>We've benchmarked Sunscreen's compiler against existing FHE compilers (that support exact computation). We run a chi-squared test according to the criteria set out in <a href="https://arxiv.org/pdf/2101.07078.pdf">this</a> SoK paper on FHE compilers.</p>
<p>Time includes key generation + encryption + (homomorphic) computation + decryption.</p>
<p>Experiments were performed on an Intel Xeon @ 3.00 GHz with 8 cores and 16 GB RAM.</p>
<table><thead><tr><th>Compiler</th><th>Time (seconds)</th></tr></thead><tbody>
<tr><td>Sunscreen</td><td>0.072</td></tr>
<tr><td>Microsoft EVA</td><td>0.328</td></tr>
<tr><td>Cingulata-BFV</td><td>492.109</td></tr>
<tr><td>Cingulata-TFHE</td><td>62.118</td></tr>
<tr><td>E<sup>3</sup>-BFV</td><td>11.319</td></tr>
<tr><td>E<sup>3</sup>-TFHE</td><td>1934.663</td></tr>
<tr><td>Concrete Numpy</td><td>N/A<sup class="footnote-reference"><a href="#1">1</a></sup></td></tr>
</tbody></table>
<div class="footnote-definition" id="1"><sup class="footnote-definition-label">1</sup>
<p>This compiler could not support the program. Concrete Numpy only allows for 256 unique values (e.g. can only represent integer values in the range [0, 255]).</p>
</div>
<p>Our compiler is built on SEAL's implementation of the BFV scheme. For reference, if coded directly in SEAL and optimized manually by an expert, the chi-squared test can run in 0.053 s.</p>
<div style="break-before: page; page-break-before: always;"></div><h1 id="getting-started"><a class="header" href="#getting-started">Getting started</a></h1>
<p>This chapter walks through installation. We also provide an overview of Sunscreen through a simple example of multiplying two encrypted numbers.</p>
<div style="break-before: page; page-break-before: always;"></div><h1 id="installation"><a class="header" href="#installation">Installation</a></h1>
<p>Using Sunscreen in your app no different than any other Rust crate. However, while in private release, you must use Sunscreen's private registry. </p>
<p>In your repository, add/edit <code>.cargo/config.toml</code> and add the following line</p>
<pre><code class="language-toml">sunscreen = { index = &quot;https://crates.sunscreen.tech/git/index&quot; }
</code></pre>
<p>under the <code>[registries]</code> section (or create one if not present).</p>
<p>In your <code>Cargo.toml</code> simply add</p>
<pre><code class="language-toml">sunscreen = { version=&quot;0.4.0&quot;, registry=&quot;sunscreen&quot; }
</code></pre>
<p>to your application's Cargo.toml <code>[dependencies]</code> section.</p>
<p>You also need cmake, clang, and a C++ compiler toolchain installed on your machine and visible in your <code>$PATH</code>. If you have ever built any other crate that wraps a C++ library, you may already be done.</p>
<h2 id="linux"><a class="header" href="#linux">Linux</a></h2>
<h3 id="using-yum-eg-centos"><a class="header" href="#using-yum-eg-centos">Using Yum (e.g. CentOS)</a></h3>
<p>In your terminal, run</p>
<pre><code class="language-sh">sudo yum install cmake3 clang git
</code></pre>
<h4 id="use-gcc10-g-as-your-compiler"><a class="header" href="#use-gcc10-g-as-your-compiler">Use <code>gcc10-g++</code> as your compiler</a></h4>
<p>In some distros (e.g Amazon Linux), the default compiler (i.e. gcc7 from the <code>gcc-c++</code> package), crashes when building SEAL. If <code>g++ --version</code> yields version 7, you need to install and use gcc10.</p>
<p>Run</p>
<pre><code class="language-sh">sudo yum install gcc10 gcc10-c++
</code></pre>
<p>then</p>
<pre><code class="language-sh">export CC=/usr/bin/gcc10-gcc
export CXX=/usr/bin/gcc10-g++
</code></pre>
<p>before building your application with Cargo. You may wish to add these <code>exports</code> to your shell's rc file (e.g. <code>~/.bash_profile</code>).</p>
<h3 id="using-apt-eg-debian"><a class="header" href="#using-apt-eg-debian">Using Apt (e.g. Debian)</a></h3>
<pre><code class="language-sh">sudo apt install build-essential cmake3 clang git
</code></pre>
<p>On some distros (e.g. Ubuntu), the cmake package is already version 3 and you can just use it directly.</p>
<h3 id="alias-cmake3-as-cmake"><a class="header" href="#alias-cmake3-as-cmake">Alias <code>cmake3</code> as cmake</a></h3>
<p>Then, make <code>cmake3</code> appear in your <code>$PATH</code> as <code>cmake</code>. A simple way to do this is run</p>
<pre><code class="language-sh">sudo ln /usr/bin/cmake3 /usr/bin/cmake
</code></pre>
<p>However, this globally creates a hard link for all users and may conflict with also installing the <code>cmake</code> (CMake 2.x) package. As an alternative, you can simply create the hard link or symlink somewhere under your <code>$PATH</code> with higher search precedence than <code>/usr/bin</code>.</p>
<h2 id="macos"><a class="header" href="#macos">MacOS</a></h2>
<h3 id="using-brew"><a class="header" href="#using-brew">Using Brew</a></h3>
<pre><code class="language-sh">brew install cmake git
</code></pre>
<p>When you first attempt to build your application, MacOS will prompt you to install the command-line developer tools. Do this.</p>
<h2 id="windows"><a class="header" href="#windows">Windows</a></h2>
<h3 id="install-rust-toolchain"><a class="header" href="#install-rust-toolchain">Install Rust toolchain</a></h3>
<p>Install the <a href="https://aka.ms/vs/17/release/vs_BuildTools.exe">MSVC C++ toolchain</a></p>
<p>When prompted for what to install, ensure you additionally check the <em>Windows 10 SDK</em>. You'll need to rerun the tool and modify your installation if you forget to do this.</p>
<p>Install <a href="https://win.rustup.rs/x86_64">Rustup</a>. Run the executable and hit return a bunch of times to accept the default options.</p>
<h3 id="cmake"><a class="header" href="#cmake">Cmake</a></h3>
<p>Install <a href="https://github.com/Kitware/CMake/releases/download/v3.23.0-rc2/cmake-3.23.0-rc2-windows-x86_64.msi">cmake 3</a>.</p>
<p>When prompted, add cmake to either the system or user path. You can also do this later by editing your system's environment variables.</p>
<h3 id="clang"><a class="header" href="#clang">Clang</a></h3>
<p>Install <a href="https://github.com/llvm/llvm-project/releases/download/llvmorg-13.0.0/LLVM-13.0.0-win64.exe">llvm+clang</a>. In the installer, select the option to add LLVM to your <code>%PATH%</code>. If you forget to do check this option, add <code>C:\Program Files\LLVM\bin</code> to your <code>%PATH%</code>.</p>
<h3 id="git"><a class="header" href="#git">git</a></h3>
<p>Install <a href="https://git-scm.com/download/win">git</a>. Defaults are fine.</p>
<div style="break-before: page; page-break-before: always;"></div><h1 id="my-first-fhe-program"><a class="header" href="#my-first-fhe-program">My first FHE program</a></h1>
<p>Now that we have installed the Sunscreen crate as a dependency, let's get started writing our first private app using FHE! Writing our program will be a gradual process and we'll add more code as we progress through this section. </p>
<p>In this example, we'll just multiply two encrypted integers.</p>
<pre><pre class="playground"><code class="language-rust no_run edition2021">use sunscreen::{
fhe_program,
types::{bfv::Signed, Cipher},
Compiler, Error, Runtime,
};
#[fhe_program(scheme = &quot;bfv&quot;)]
fn simple_multiply(a: Cipher&lt;Signed&gt;, b: Cipher&lt;Signed&gt;) -&gt; Cipher&lt;Signed&gt; {
a * b
}
fn main() {
}
</code></pre></pre>
<p>Notice that the <code>simple_multiply</code> function is like any other function in Rust, except for the <code>#[fhe_program(...)]</code> attribute. This is where the magic happens— it declares your function as an FHE program that can be compiled. The <code>scheme</code> argument should always be <code>&quot;bfv&quot;</code>, though we may support additional FHE schemes in the future.</p>
<p><code>simple_multiply</code>'s signature specifies that it takes in two <code>Cipher&lt;Signed&gt;</code> values and returns one. <code>Cipher&lt;T&gt;</code> indicates the contained type <code>T</code> is encrypted (i.e. a ciphertext) and <code>Signed</code> is Sunscreen's signed integer type; thus, <code>Cipher&lt;Signed&gt;</code> indicates that we have an encrypted signed integer. The body of <code>simple_multiply</code> multiplies the ciphertexts <code>a</code> and <code>b</code> together. As with any function in Rust, omitting a <code>;</code> returns an expression's value from the current scope.</p>
<p>Having specified our program, let's compile it.</p>
<pre><pre class="playground"><code class="language-rust no_run edition2021">use sunscreen::{
fhe_program,
types::{bfv::Signed, Cipher},
Compiler, Error, Runtime,
};
#[fhe_program(scheme = &quot;bfv&quot;)]
fn simple_multiply(a: Cipher&lt;Signed&gt;, b: Cipher&lt;Signed&gt;) -&gt; Cipher&lt;Signed&gt; {
a * b
}
fn main() -&gt; Result&lt;(), Error&gt; {
let fhe_program = Compiler::with_fhe_program(simple_multiply)
.compile()?;
Ok(())
}
</code></pre></pre>
<p>The <code>Compiler::with_fhe_program(simple_multiply)</code> line creates a compiler and <code>.compile()</code>, tells it to compile our FHE program. Compilation performs optimization and fills in implementation details, including figuring out FHE scheme parameters and inserting special operations. </p>
<p>What's the <code>?</code> after at the end of <code>.compile()</code>? For the uninitiated, the <a href="https://doc.rust-lang.org/book/ch09-02-recoverable-errors-with-result.html"><code>?</code></a> operator propagates errors. Fallible expressions in Rust emit <a href="https://doc.rust-lang.org/std/result/enum.Result.html"><code>Results</code></a>, which can contain either a value or an error. Using <code>?</code> unwraps the value in a successful result or immediately returns the error from a failed one, letting the caller of the current function deal with it. We should see the former after compilation, as our program is well-formed.</p>
<p>Next, we need a public and private key pair. In order to generate keys, we'll first construct a <code>Runtime</code> with the parameters we got from compilation. This allows us to encrypt/decrypt data and run FHE programs.</p>
<pre><pre class="playground"><code class="language-rust no_run edition2021">use sunscreen::{
fhe_program,
types::{bfv::Signed, Cipher},
Compiler, Error, Runtime,
};
#[fhe_program(scheme = &quot;bfv&quot;)]
fn simple_multiply(a: Cipher&lt;Signed&gt;, b: Cipher&lt;Signed&gt;) -&gt; Cipher&lt;Signed&gt; {
a * b
}
fn main() -&gt; Result&lt;(), Error&gt; {
let fhe_program = Compiler::with_fhe_program(simple_multiply)
.compile()?;
let runtime = Runtime::new(&amp;fhe_program.metadata.params)?;
let (public_key, private_key) = runtime.generate_keys()?;
let a = runtime.encrypt(Signed::from(15), &amp;public_key)?;
let b = runtime.encrypt(Signed::from(5), &amp;public_key)?;
Ok(())
}
</code></pre></pre>
<p>After constructing our runtime, we generate a public and private key pair by calling <code>runtime.generate_keys()</code>.</p>
<p>Next, we call <code>Signed::from(15)</code> to make an unencrypted <code>Signed</code> integer equal to <code>15</code>. Rust doesn't allow implicit type conversion as some languages do, so we use the <code>From</code> trait to explicitly convert a Rust <code>i64</code> into a Sunscreen <code>Signed</code>.</p>
<p>Once we have our plaintext value 15, we encrypt it by calling <code>runtime.encrypt(...)</code>, passing in the value and our public key. We repeat this process for <code>b</code> with the value <code>5</code>. Now that we have the two ciphertexts <code>a</code> and <code>b</code> to give to <code>simple_multiply</code>, we're ready to run our FHE program!</p>
<pre><pre class="playground"><code class="language-rust no_run edition2021">use sunscreen::{
fhe_program,
types::{bfv::Signed, Cipher},
Compiler, Error, Runtime,
};
#[fhe_program(scheme = &quot;bfv&quot;)]
fn simple_multiply(a: Cipher&lt;Signed&gt;, b: Cipher&lt;Signed&gt;) -&gt; Cipher&lt;Signed&gt; {
a * b
}
fn main() -&gt; Result&lt;(), Error&gt; {
let fhe_program = Compiler::with_fhe_program(simple_multiply)
.compile()?;
let runtime = Runtime::new(&amp;fhe_program.metadata.params)?;
let (public_key, private_key) = runtime.generate_keys()?;
let a = runtime.encrypt(Signed::from(15), &amp;public_key)?;
let b = runtime.encrypt(Signed::from(5), &amp;public_key)?;
let results = runtime.run(&amp;fhe_program, vec![a, b], &amp;public_key)?;
let c: Signed = runtime.decrypt(&amp;results[0], &amp;private_key)?;
assert_eq!(c, 75.into());
Ok(())
}
</code></pre></pre>
<p>We call <code>runtime.run(...)</code> to execute our FHE program. For the first argument, we pass in our previously compiled program <code>fhe_program</code>. The second argument is always a <a href="https://doc.rust-lang.org/std/vec/struct.Vec.html">Vec</a> containing the arguments to the FHE program. In this case, we pass in the encrypted <code>a</code> and <code>b</code> values. You'll need to pass in the <code>public_key</code> as well.</p>
<p>What would happen if we forgot to encrypt one of our values or gave an encrypted <code>Fractional</code> value where the program wanted an encrypted <code>Signed</code> value? Fortunately, the <code>run</code> method first performs some sanity checks to ensure the arguments match the call signature. If the types of the values we pass in don't match the signature, the <code>run</code> method returns an error <code>Result</code>. The <code>?</code> propagates this error, but our program exits because this is the <code>main()</code> method!</p>
<p>Next, we call <code>runtime.decrypt(...)</code> with the first result and our private key. Programs <em>can</em> return more than one value; hence, <code>results</code> is a <code>Vec</code>. Since our FHE program only returns one value, we decrypt the value at index <code>0</code>. The left hand side of the assignment denotes the decrypted data is a <code>Signed</code> whereas <code>runtime.decrypt(...)</code> ensures this type matches the ciphertext's encrypted value before decryption. If we had assigned a different type to <code>c</code>, say <code>Fractional</code>, then decrypt would return an error.</p>
<p>Finally, we verify the result equals 75 (i.e. 15 * 5) as expected. </p>
<div style="break-before: page; page-break-before: always;"></div><h1 id="whats-in-an-fhe-program"><a class="header" href="#whats-in-an-fhe-program">What's in an FHE program?</a></h1>
<p>This section describes the anatomy of an FHE program, what you can and can't do, and the different data types FHE programs support.</p>
<div style="break-before: page; page-break-before: always;"></div><h1 id="types"><a class="header" href="#types">Types</a></h1>
<p>Sunscreen supports a number of data types for different scenarios. Each of these data types is located in the <code>sunscreen_compiler::types::bfv</code> module.</p>
<p>All types <code>T</code> support <code>+</code>, <code>-</code>, <code>*</code> operations on plaintext, ciphertext, and literals. Note that at least one of the operands must be a ciphertext.</p>
<ul>
<li>Use <code>Signed</code> if you need to work with integers. </li>
<li>Use <code>Fractional</code> if you need to work with decimals (but <em>don't</em> anticipate needing to divide by ciphertexts).</li>
<li>Use<code>Rational</code> if ciphertext division is <em>absolutely necessary</em> to your application. This type incurs more overhead than <code>Fractional</code>. </li>
</ul>
<table><thead><tr><th>type</th><th>division</th></tr></thead><tbody>
<tr><td>Signed</td><td>unsupported</td></tr>
<tr><td>Fractional</td><td>divide by literal only</td></tr>
<tr><td>Rational</td><td>fully supported</td></tr>
</tbody></table>
<h2 id="cipher"><a class="header" href="#cipher">Cipher</a></h2>
<p>The <code>Cipher</code> type is special in that you don't directly create <code>Cipher</code> values. <code>Cipher&lt;T&gt;</code> should only appear in an FHE program's call signature and denotes that an argument or return value is an encrypted <code>T</code>. The absence of this wrapper indicates that <code>T</code> is unencrypted. </p>
<p>While arguments may be unencrypted (i.e. of type <code>T</code>), return values must always be encrypted (i.e. of type <code>Cipher&lt;T&gt;</code>).</p>
<p>For example:</p>
<pre><pre class="playground"><code class="language-rust no_run edition2021">
<span class="boring">#![allow(unused)]
</span><span class="boring">fn main() {
</span><span class="boring">use sunscreen::{
</span><span class="boring"> fhe_program,
</span><span class="boring"> types::{bfv::Signed, Cipher},
</span><span class="boring">};
</span><span class="boring">
</span>#[fhe_program(scheme = &quot;bfv&quot;)]
fn my_program(a: Cipher&lt;Signed&gt;, b: Signed) -&gt; (Cipher&lt;Signed&gt;, Cipher&lt;Signed&gt;) {
// Do things
<span class="boring"> (a, a + b)
</span>}
<span class="boring">}
</span></code></pre></pre>
<ul>
<li>Argument <code>a</code> is an encrypted <code>Signed</code> value.</li>
<li>Argument <code>b</code> is an <em>un</em>encrypted <code>Signed</code> value.</li>
<li><code>my_program</code> returns 2 encrypted <code>Signed</code> values via a tuple.</li>
</ul>
<h2 id="arrays"><a class="header" href="#arrays">Arrays</a></h2>
<p>Sunscreen supports fixed-length arrays<sup class="footnote-reference"><a href="#1">1</a></sup> that behave as you'd expect. You declare and use them as any other fixed-length array in Rust:</p>
<pre><pre class="playground"><code class="language-rust no_run edition2021">
<span class="boring">#![allow(unused)]
</span><span class="boring">fn main() {
</span><span class="boring">use sunscreen::{
</span><span class="boring"> fhe_program,
</span><span class="boring"> types::{bfv::Fractional, Cipher},
</span><span class="boring">};
</span><span class="boring">
</span>#[fhe_program(scheme = &quot;bfv&quot;)]
fn matrix_vector_multiply(a: [[Cipher&lt;Fractional&lt;64&gt;&gt;; 10]; 10], b: [Cipher&lt;Fractional&lt;64&gt;&gt;; 10]) -&gt; [Cipher&lt;Fractional&lt;64&gt;&gt;; 10] {
// Clone b just so we get an initialized object of the right
// type in col.
let mut col = b.clone();
// Perform matrix-vector multiplication with col_query to extract
// Alice's desired column
for i in 0..10 {
for j in 0..10 {
if j == 0 {
col[i] = a[i][j] * b[j];
} else {
col[i] = col[i] + a[i][j] * b[j];
}
}
}
col
}
<span class="boring">}
</span></code></pre></pre>
<p>You can make arrays of encrypted or unencrypted data types. In the former case, the <code>Cipher</code> must go inside the array; you can't declare a <code>Cipher&lt;[T; 2]&gt;</code>.</p>
<p><em>TODO: add discussion on using arrays as inputs to FHE programs (readable vs writeable). having to initialize writeable arrays. cannot return arrays from FHE programs.</em></p>
<div class="footnote-definition" id="1"><sup class="footnote-definition-label">1</sup>
<p>Don't confuse these with <code>Vec</code>, which Sunscreen does <em>not</em> support!</p>
</div>
<h2 id="working-with-literals"><a class="header" href="#working-with-literals">Working with literals</a></h2>
<p>Sometimes, you simply want to double a value or add <code>15</code>. Fortunately, most FHE types and operations support literal operands.</p>
<p>For example, <code>Signed</code> values work with <code>i64</code> values</p>
<pre><pre class="playground"><code class="language-rust no_run edition2021">
<span class="boring">#![allow(unused)]
</span><span class="boring">fn main() {
</span><span class="boring">use sunscreen::{
</span><span class="boring"> fhe_program,
</span><span class="boring"> types::{bfv::Signed, Cipher},
</span><span class="boring">};
</span><span class="boring">
</span>#[fhe_program(scheme = &quot;bfv&quot;)]
fn answer(a: Cipher&lt;Signed&gt;) -&gt; Cipher&lt;Signed&gt; {
a + 42
}
<span class="boring">}
</span></code></pre></pre>
<p>while <code>Fractional</code> and <code>Rational</code> values support <code>f64</code> values</p>
<pre><pre class="playground"><code class="language-rust no_run edition2021">
<span class="boring">#![allow(unused)]
</span><span class="boring">fn main() {
</span><span class="boring">use sunscreen::{
</span><span class="boring"> fhe_program,
</span><span class="boring"> types::{bfv::Fractional, Cipher},
</span><span class="boring">};
</span><span class="boring">
</span>#[fhe_program(scheme = &quot;bfv&quot;)]
fn answer_2(a: Cipher&lt;Fractional&lt;64&gt;&gt;) -&gt; Cipher&lt;Fractional&lt;64&gt;&gt; {
42.0 * a
}
<span class="boring">}
</span></code></pre></pre>
<div style="break-before: page; page-break-before: always;"></div><h1 id="signed"><a class="header" href="#signed">Signed</a></h1>
<p><code>Signed</code> values allow you to perform integer arithmetic as follows (recall that at least one operand must be a ciphertext):</p>
<table><thead><tr><th>operation</th><th>operand</th></tr></thead><tbody>
<tr><td>add</td><td>ciphertext, plaintext, <code>i64</code> literal</td></tr>
<tr><td>sub</td><td>ciphertext, plaintext, <code>i64</code> literal</td></tr>
<tr><td>mul</td><td>ciphertext, plaintext, <code>i64</code> literal</td></tr>
</tbody></table>
<p>Additionally, you can perform unary negation on encrypted <code>Signed</code> values.</p>
<h2 id="representation"><a class="header" href="#representation">Representation</a></h2>
<p><code>Signed</code> values contain thousands of binary digits of precision, easily enough to store any <code>i64</code> value.</p>
<div style="break-before: page; page-break-before: always;"></div><h1 id="fractional"><a class="header" href="#fractional">Fractional</a></h1>
<p><code>Fractional</code> values allow you to perform decimal arithmetic. You can think of <code>Fractional</code> as being similar to a fixed-point representation.</p>
<p>Sunscreen represents <code>Fractional</code> values as an integer and fractional part. The <code>INT_BITS</code> type argument specifies how many binary digits store the integer part. Setting <code>INT_BITS</code> to <code>64</code> should be more than sufficient for most applications since <code>Fractional&lt;64&gt;</code> values can exactly represent every <code>i64</code> with thousands (!!) of binary digits for the decimal portion. </p>
<p>You can perform operations on <code>Fractional</code> values as follows (recall at least one operand must be a ciphertext):</p>
<table><thead><tr><th>operation</th><th>operand</th></tr></thead><tbody>
<tr><td>add</td><td>ciphertext, plaintext, literal</td></tr>
<tr><td>sub</td><td>ciphertext, plaintext, literal</td></tr>
<tr><td>mul</td><td>ciphertext, plaintext, literal</td></tr>
<tr><td>div</td><td>ciphertext numerator + literal divisor</td></tr>
</tbody></table>
<p>Additionally, you perform unary negation on <code>Fractional</code> ciphertexts.</p>
<p>While division by only literals may seem limiting, this is one of the more common use cases. For example, you can average 3 values:</p>
<pre><pre class="playground"><code class="language-rust no_run edition2021">
<span class="boring">#![allow(unused)]
</span><span class="boring">fn main() {
</span><span class="boring">use sunscreen::{
</span><span class="boring"> fhe_program,
</span><span class="boring"> types::{bfv::Fractional, Cipher},
</span><span class="boring"> Compiler, Runtime, PublicKey
</span><span class="boring">};
</span>
#[fhe_program(scheme = &quot;bfv&quot;)]
fn avg(
a: Cipher&lt;Fractional&lt;64&gt;&gt;,
b: Cipher&lt;Fractional&lt;64&gt;&gt;,
c: Cipher&lt;Fractional&lt;64&gt;&gt;
) -&gt; Cipher&lt;Fractional&lt;64&gt;&gt; {
(a + b + c) / 3.0
}
<span class="boring">}
</span></code></pre></pre>
<p>Additionally, division by literals is sufficient to compute many transcendental functions (e.g. <code>sin</code>, <code>cos</code>, <code>exp</code>) via a power series.</p>
<h2 id="representation-1"><a class="header" href="#representation-1">Representation</a></h2>
<p>A scheme parameter <code>lattice_dimension</code> (chosen by the Sunscreen compiler) determines the number of decimal places such that <code>INT_BITS + DECIMAL_BITS = lattice_dimension</code>. This scheme parameter is always at least <code>1024</code>. You can find the compiler's chosen value with <code>my_compiled_program.metadata.params.lattice_dimension</code>.</p>
<p><code>Fractional</code> values use exact arithmetic and don't suffer from roundoff errors as floating point values do. In fact, if <code>INT_BITS=1024</code> and <code>lattice_dimension &gt;= 2048</code> they can <em>exactly</em> store every double precision value with a fixed decimal point!</p>
<h2 id="efficiency"><a class="header" href="#efficiency">Efficiency</a></h2>
<p>Unlike the <a href="fhe_programs/types/./rational.html"><code>Rational</code></a> type, storing and computing <code>Fractional</code> values is as efficient as <a href="fhe_programs/types/./signed.html"><code>Signed</code></a> values.</p>
<div style="break-before: page; page-break-before: always;"></div><h1 id="rational"><a class="header" href="#rational">Rational</a></h1>
<p>The <code>Rational</code> type allows you to perform all decimal arithmetic:</p>
<table><thead><tr><th>operation</th><th>operand</th></tr></thead><tbody>
<tr><td>add</td><td>ciphertext, plaintext, literal</td></tr>
<tr><td>sub</td><td>ciphertext, plaintext, literal</td></tr>
<tr><td>mul</td><td>ciphertext, plaintext, literal</td></tr>
<tr><td>div</td><td>ciphertext, plaintext, literal</td></tr>
</tbody></table>
<p>Additionally, you can perform unary negation on <code>Rational</code> ciphertexts (i.e., given <code>a</code>, compute <code>-a</code>).</p>
<h2 id="representation-2"><a class="header" href="#representation-2">Representation</a></h2>
<p><code>Rational</code> encodes a numerator and denominator as two independent <code>Signed</code> values. This results in ciphertexts <strong>twice</strong> as large as when using the <a href="fhe_programs/types/./fractional.html"><code>Fractional</code></a> type.</p>
<h2 id="efficiency-1"><a class="header" href="#efficiency-1">Efficiency</a></h2>
<p>In addition to the increased size, each <code>Rational</code> operation (except negation) requires multiple FHE operations. Thus, even addition can quickly increase FHE <a href="fhe_programs/types//advanced/noise_margin.html#what-is-noise">program complexity</a>. Using <code>Rational</code> ciphertexts in prolonged computation may require larger scheme parameters (hence resulting in slower computations).</p>
<div style="break-before: page; page-break-before: always;"></div><h1 id="writing-an-fhe-program"><a class="header" href="#writing-an-fhe-program">Writing an FHE program</a></h1>
<p>An FHE program is simply a Rust function with an annotation and a few restrictions. However, unlike standard Rust functions, FHE programs work with encrypted data!</p>
<h2 id="the-fhe_program-attribute"><a class="header" href="#the-fhe_program-attribute">The <code>#[fhe_program(...)]</code> attribute</a></h2>
<p>To indicate that a function is an FHE program, simply add the <code>#[fhe_program()]</code> attribute to an <code>fn</code> function:</p>
<pre><pre class="playground"><code class="language-rust no_run edition2021">
<span class="boring">#![allow(unused)]
</span><span class="boring">fn main() {
</span><span class="boring">use sunscreen::{
</span><span class="boring"> fhe_program,
</span><span class="boring">};
</span>
#[fhe_program(scheme = &quot;bfv&quot;)]
fn my_fhe_program() {
}
<span class="boring">}
</span></code></pre></pre>
<p>This attribute takes a single <code>scheme</code> argument. Currently, this argument value should always be <code>&quot;bfv&quot;</code>, our supported FHE scheme.</p>
<h2 id="fhe-program-interface-requirements"><a class="header" href="#fhe-program-interface-requirements">FHE program interface requirements</a></h2>
<p>FHE programs implement their logic in the <code>fn</code> function beneath the <code>#[fhe_program()]</code> attribute. The function you write must satisfy some conditions:</p>
<ul>
<li>Your <code>fn</code> function must be non-generic and stand-alone (i.e. not a <code>struct</code> method, closure, <code>trait</code> method, etc).</li>
<li>Your <code>fn</code> function may take any number of arguments.</li>
<li>Each argument must be of either type <code>T</code> (i.e. plaintext) or <code>Cipher&lt;T&gt;</code> (i.e. ciphertext), where <code>T</code> is a type <a href="fhe_programs/writing_an_fhe_program//fhe_programs/types/types.html">supported</a> in FHE programs. Every argument need not be the same <code>T</code>.</li>
<li>Your <code>fn</code> function must return either a <code>Cipher&lt;T&gt;</code> or a tuple of <code>(Cipher&lt;T1&gt;, Cipher&lt;T2&gt;, ...)</code> values (i.e. return values are always encrypted). As with arguments, types must be supported in FHE programs.</li>
</ul>
<p>Here's an example of an FHE program that returns a tuple containing two encrypted values: <code>a * b</code> and <code>a + c</code>.</p>
<pre><pre class="playground"><code class="language-rust no_run edition2021">
<span class="boring">#![allow(unused)]
</span><span class="boring">fn main() {
</span><span class="boring">use sunscreen::{
</span><span class="boring"> fhe_program,
</span><span class="boring"> types::{bfv::Signed, Cipher},
</span><span class="boring">};
</span><span class="boring">
</span>#[fhe_program(scheme = &quot;bfv&quot;)]
fn multiple_returns(a: Cipher&lt;Signed&gt;, b: Cipher&lt;Signed&gt;, c: Signed) -&gt; (Cipher&lt;Signed&gt;, Cipher&lt;Signed&gt;) {
(a * b, a + c)
}
<span class="boring">}
</span></code></pre></pre>
<h2 id="operations"><a class="header" href="#operations">Operations</a></h2>
<p>In FHE programs, you can:</p>
<ul>
<li>Perform basic operations (<code>+</code>, <code>-</code>, <code>*</code>, <code>/</code>, <code>&lt;&lt;</code>, <code>&gt;&gt;</code>). The supported set of operations vary from type to <a href="fhe_programs/writing_an_fhe_program//fhe_programs/types/types.html">type</a>. Note that at least one of the operands must be a ciphertext.</li>
<li>Call functions.</li>
<li>Use any Rust construct (e.g. <code>match</code>, <code>for i in ...</code>, <code>if...else</code>) on data <em>not</em> derived from any argument. We walk through a number of examples in the <a href="fhe_programs/writing_an_fhe_program//fhe_programs/writing_an_fhe_program/limitations.html#branching-restricted-to-constant-expressions">limitations</a> chapter.</li>
</ul>
<div style="break-before: page; page-break-before: always;"></div><h1 id="factoring-fhe-programs"><a class="header" href="#factoring-fhe-programs">Factoring FHE programs</a></h1>
<p>In this section we'll show you how to factor your programs in a specific way that allows for</p>
<ul>
<li>Reusing algorithms with different data types.</li>
<li>Running your algorithm without FHE. This allows you to debug the algorithm without encryption getting in your way and measure FHE's performance overhead.</li>
</ul>
<p>Let's begin by rewriting our <code>simple_multiply</code> example with a common implementation (<code>simple_multiply_impl</code>):</p>
<pre><pre class="playground"><code class="language-rust no_run edition2021">
<span class="boring">#![allow(unused)]
</span><span class="boring">fn main() {
</span>use sunscreen::{
fhe_program,
types::{bfv::{Signed, Fractional}, Cipher},
};
use std::ops::Mul;
fn simple_multiply_impl&lt;T, U&gt;(a: T, b: U) -&gt; T
where T: Mul&lt;U, Output=T&gt; + Copy
{
a * b
}
#[fhe_program(scheme = &quot;bfv&quot;)]
fn simple_multiply_signed(a: Cipher&lt;Signed&gt;, b: Cipher&lt;Signed&gt;) -&gt; Cipher&lt;Signed&gt; {
simple_multiply_impl(a, b)
}
#[fhe_program(scheme = &quot;bfv&quot;)]
fn simple_multiply_fractional(a: Cipher&lt;Fractional&lt;64&gt;&gt;, b: Fractional&lt;64&gt;) -&gt; Cipher&lt;Fractional&lt;64&gt;&gt; {
simple_multiply_impl(a, b)
}
<span class="boring">}
</span></code></pre></pre>
<p>The first FHE program multiplies encrypted <code>Signed</code> values. In the second, <code>a</code> is an encrypted <code>Fractional</code> value while <code>b</code> is an unencrypted <code>Fractional</code> value. We can run both of these programs using <code>runtime.run()</code> as normal. </p>
<h2 id="running-your-implementation-without-fhe"><a class="header" href="#running-your-implementation-without-fhe">Running your implementation without FHE</a></h2>
<p>If we inspect the <a href="https://doc.rust-lang.org/rust-by-example/generics/where.html">trait bounds</a> on <code>simple_multiply_impl</code>, we'll notice there is no mention of anything Sunscreen related. This means we can directly run our implementation with Rust <code>i64</code> values by simply calling:</p>
<pre><pre class="playground"><code class="language-rust no_run edition2021"><span class="boring">use std::ops::Mul;
</span><span class="boring">
</span><span class="boring">fn simple_multiply_impl&lt;T, U&gt;(a: T, b: U) -&gt; T
</span><span class="boring">where T: Mul&lt;U, Output=T&gt; + Copy
</span><span class="boring">{
</span><span class="boring"> a * b
</span><span class="boring">}
</span><span class="boring">
</span><span class="boring">fn main() {
</span> simple_multiply_impl(7, 5);
<span class="boring">}
</span></code></pre></pre>
<p>It's worth explicitly pointing out that <code>T</code> and <code>U</code> may be of the same or different types; the trait bounds merely require that you can multiply <code>T</code> and <code>U</code> values.</p>
<div style="break-before: page; page-break-before: always;"></div><h1 id="limitations"><a class="header" href="#limitations">Limitations</a></h1>
<p>FHE programs have some limitations you'll need to keep in mind.</p>
<h2 id="comparisons-not-supported"><a class="header" href="#comparisons-not-supported">Comparisons not supported</a></h2>
<p>Performing comparisons on encrypted data is complex. Thus, we do not currently support comparisons. </p>
<p>The following is <em>not</em> allowed:</p>
<pre><pre class="playground"><code class="language-rust no_run compile_fail edition2021">
<span class="boring">#![allow(unused)]
</span><span class="boring">fn main() {
</span><span class="boring">use sunscreen::types::{bfv::Signed, Cipher};
</span>
#[fhe_program(scheme = &quot;bfv&quot;)]
fn invalid(a: Cipher&lt;Signed&gt;) -&gt; Cipher&lt;Signed&gt; {
// Return value mismatch aside, comparisons
// are not supported
a == 42
}
<span class="boring">}
</span></code></pre></pre>
<h2 id="branching-restricted-to-constant-expressions"><a class="header" href="#branching-restricted-to-constant-expressions">Branching restricted to constant expressions</a></h2>
<p>Branches (i.e. <code>for</code>, <code>if/else</code>, <code>match</code>) cannot depend on function arguments, encrypted<sup class="footnote-reference"><a href="#1">1</a></sup> or otherwise.</p>
<p>For example, you <em>cannot</em> do the following:</p>
<pre><pre class="playground"><code class="language-rust no_run compile_fail edition2021">
<span class="boring">#![allow(unused)]
</span><span class="boring">fn main() {
</span><span class="boring">use sunscreen::types::{bfv::Signed, Cipher};
</span>
#[fhe_program(scheme = &quot;bfv&quot;)]
fn invalid(a: Cipher&lt;Signed&gt;, b: Signed) -&gt; Cipher&lt;Signed&gt; {
let mut c = a;
// For loop runs during compilation, but b isn't known until
// you call `run`.
for i in 0..b {
c = c + a;
}
c
}
<span class="boring">}
</span></code></pre></pre>
<p>You <em>can</em>, however, use loops and if statements so long as their conditions don't depend on FHE program arguments. The examples below show <strong>allowed loop and if statements</strong>:</p>
<pre><pre class="playground"><code class="language-rust no_run edition2021">
<span class="boring">#![allow(unused)]
</span><span class="boring">fn main() {
</span><span class="boring">use sunscreen::{
</span><span class="boring"> types::{bfv::{Fractional, Signed}, Cipher},
</span><span class="boring"> fhe_program
</span><span class="boring">};
</span>
#[fhe_program(scheme = &quot;bfv&quot;)]
fn loopy(x: Cipher&lt;Fractional&lt;64&gt;&gt;) -&gt; Cipher&lt;Fractional&lt;64&gt;&gt; {
let mut y = x;
for _ in 0..5 {
y = y + x;
}
y
}
#[fhe_program(scheme = &quot;bfv&quot;)]
fn iffy(x: Cipher&lt;Signed&gt;) -&gt; Cipher&lt;Signed&gt; {
let mut ans = x;
for i in 1..5 {
if i % 2 == 0 {
ans = ans + i * x;
} else {
ans = ans - i * x;
}
}
ans
}
<span class="boring">}
</span></code></pre></pre>
<p>Notice that their conditions don't depend on their argument <code>x</code>, so they're legal.</p>
<div class="footnote-definition" id="1"><sup class="footnote-definition-label">1</sup>
<p>This is not merely a Sunscreen limitation; if an FHE scheme supported traditional branching, it would be fundamentally insecure.</p>
</div>
<h2 id="bounded-computation"><a class="header" href="#bounded-computation">Bounded computation</a></h2>
<p>You currently cannot perform computations <em>indefinitely</em> on ciphertexts. See <a href="fhe_programs/writing_an_fhe_program/./advanced/noise_margin.html">here</a> for a more in-depth discussion of this.</p>
<h2 id="avoid-transparent-ciphertexts"><a class="header" href="#avoid-transparent-ciphertexts">Avoid &quot;transparent&quot; ciphertexts</a></h2>
<p>Some trivial operations destroy the randomness essential to the security of the resultant ciphertext — an outside observer can trivially decode them! Sunscreen will detect this and cause <code>run()</code> to fail to prevent data from leaking. Fortunately, such operations are not particularly useful in the first place. </p>
<p>Avoid doing the following:</p>
<ul>
<li>Subtracting a ciphertext from itself. However, it's fine to subtract 2 <em>different</em> ciphertexts that happen to contain the same value (i.e. the ciphertexts encrypt the same data but using <em>different randomness</em>).</li>
<li>Multiplying a ciphertext by the plaintext or literal value 0. However, if a <em>ciphertext</em> encrypts 0, that's totally fine.</li>
</ul>
<div style="break-before: page; page-break-before: always;"></div><h1 id="troubleshooting"><a class="header" href="#troubleshooting">Troubleshooting</a></h1>
<h2 id="how-do-i-debug-my-algorithm"><a class="header" href="#how-do-i-debug-my-algorithm">How do I debug my algorithm?</a></h2>
<p>You can write your algorithm <a href="/fhe_programs/plaintext_execution.html">in a generic way</a>, run it without FHE, and single step through it.
You can also compare results executing with and without FHE.</p>
<p>Another technique that can be helpful is to call the <code>render()</code> method on your compiled <code>FheProgram</code>. This returns a <code>String</code> containing the compiled execution graph in <a href="https://www.graphviz.org/doc/info/lang.html">DOT</a> format. You can write this to a file and render it with <a href="https://graphviz.org/">Graphviz</a>, a standard graph rendering library.</p>
<h2 id="my-fhe-program-yields-the-wrong-answer-im-certain-the-algorithm-is-correct"><a class="header" href="#my-fhe-program-yields-the-wrong-answer-im-certain-the-algorithm-is-correct">My FHE program yields the wrong answer. I'm certain the algorithm is correct.</a></h2>
<p>Your issue might be one of 2 things:</p>
<ol>
<li>You exceeded the <a href="/advanced/noise_margin.html">noise budget</a>. You can check the noise budget remaining on a ciphertext (this requires the private key) by calling (<code>runtime.measure_noise_budget(&amp;ciphertext, &amp;private_key)</code>). If this value is <code>0</code>, you exceeded the noise budget and your value is corrupted. The most common scenario where you will encounter this issue is when <a href="troubleshooting.html#i-need-to-use-the-output-of-one-fhe-program-as-the-input-to-another-ie-chain-program-executions">chaining</a> multiple FHE program executions.</li>
<li>Overflow. <a href="/advanced/plain_modulus/choosing_plain_modulus.html">Try increasing the plaintext modulus</a>. Due to <a href="/advanced/carryless_arithmetic.html">carryless arithmetic</a>, understanding overflow can be a bit tricky. Usually, overflow occurs when your plaintext modulus is too small and a digit wraps. Values can also overflow during multiplication due to running out of digits. However, this is very rare in FHE.</li>
</ol>
<h2 id="i-need-to-use-the-output-of-one-fhe-program-as-the-input-to-another-ie-chain-program-executions"><a class="header" href="#i-need-to-use-the-output-of-one-fhe-program-as-the-input-to-another-ie-chain-program-executions">I need to use the output of one FHE program as the input to another (i.e. chain program executions).</a></h2>
<p>We will likely improve the experience in the future, but you can do this today as follows:</p>
<ol>
<li>Compile all your FHE programs with an increased <a href="/advanced/noise_margin.html#changing-the-noise-margin"><code>noise_margin</code></a> and look at their <code>metadata.params.lattice_dimension</code> values.</li>
<li>Change your application so the that the program with the largest lattice dimension (program <code>x</code>) compiles as it does in step 1, while the remaining programs call <code>.with_params(&amp;x.metadata.params)</code> during compilation. This causes the remaining programs to use the same parameters verbatim.</li>
</ol>
<p>The <code>noise_margin</code> you chose in step 1 determines how many times you can chain together program executions.</p>
<h2 id="what-the-heck-is-an-fheprogramnode"><a class="header" href="#what-the-heck-is-an-fheprogramnode">What the heck is an <code>FheProgramNode</code>?</a></h2>
<p>It's a type wrapper needed to compile your FHE program. Internally, the <code>#[fhe_program]</code> macro turns all your program inputs and outputs into graph nodes — i.e. <code>FheProgramNodes</code>. Operator inputs and outputs are actually <code>FheProgramNodes</code>, which build up the execution graph during compilation. Unfortunately, they tend to be a leaky abstraction that wind up in error messages.</p>
<p>Usually, these errors tell you an <code>FheProgramNode</code>'s inner type doesn't
support an operation you're trying to perform. In the example below, the compiler is saying you can't divide <code>Signed</code> values:</p>
<pre><code class="language-ignore">error[E0369]: cannot divide `FheProgramNode&lt;Cipher&lt;Signed&gt;&gt;` by `FheProgramNode&lt;Cipher&lt;Signed&gt;&gt;`
--&gt; examples/simple_multiply/src/main.rs:22:7
|
22 | a / b
| - ^ - FheProgramNode&lt;Cipher&lt;Signed&gt;&gt;
| |
| FheProgramNode&lt;Cipher&lt;Signed&gt;&gt;
For more information about this error, try `rustc --explain E0369`.
</code></pre>
<p>This can also crop up when using explicit annotations. For example, the following will fail to compile:</p>
<pre><pre class="playground"><code class="language-rust no_run compile_fail edition2021">
<span class="boring">#![allow(unused)]
</span><span class="boring">fn main() {
</span>#[fhe_program(scheme = &quot;bfv&quot;)]
fn simple_multiply(a: Cipher&lt;Signed&gt;, b: Cipher&lt;Signed&gt;) -&gt; Cipher&lt;Signed&gt; {
// This assignment will fail because a * b results in an
// `FheProgramNode&lt;Cipher&lt;Signed&gt;&gt;`, not a Cipher&lt;Signed&gt;
let c: Cipher&lt;Signed&gt; = a * b;
c
}
<span class="boring">}
</span></code></pre></pre>
<p>Unnecessary type annotations are unidiomatic and thus we advise against them. Usually, type inference is sufficient, but if you really need one you can import and use <code>sunscreen::types::intern::FheProgramNode</code>.</p>
<div style="break-before: page; page-break-before: always;"></div><h1 id="runtime"><a class="header" href="#runtime">Runtime</a></h1>
<p>To create a runtime, you simply call <code>Runtime::new</code>, passing a <code>Params</code> object. You get a params object from compiling an FHE program as we did in our example.</p>
<pre><pre class="playground"><code class="language-rust no_run edition2021"><span class="boring">use sunscreen::{
</span><span class="boring"> fhe_program,
</span><span class="boring"> types::{bfv::Signed, Cipher},
</span><span class="boring"> Compiler, Runtime, PublicKey
</span><span class="boring">};
</span><span class="boring">
</span><span class="boring">#[fhe_program(scheme = &quot;bfv&quot;)]
</span><span class="boring">fn noop() {
</span><span class="boring">}
</span><span class="boring">
</span><span class="boring">fn main() {
</span><span class="boring"> let fhe_program = Compiler::with_fhe_program(noop)
</span><span class="boring"> .compile()
</span><span class="boring"> .unwrap();
</span><span class="boring">
</span> let runtime = Runtime::new(&amp;fhe_program.metadata.params).unwrap();
<span class="boring">}
</span></code></pre></pre>
<p>Once you're created a runtime, you can:</p>
<ul>
<li><a href="fhe_programs/runtime/./key_generation.html">generate public/private keys</a></li>
<li><a href="fhe_programs/runtime/./encryption.html">encrypt plaintexts</a></li>
<li><a href="fhe_programs/runtime/./running_fhe_programs.html">run FHE programs</a></li>
<li><a href="fhe_programs/runtime/./decryption.html">decrypt ciphertexts</a></li>
</ul>
<h2 id="parameter-compatibility"><a class="header" href="#parameter-compatibility">Parameter compatibility</a></h2>
<p>Note that to use artifacts produced by a runtime (e.g. ciphertexts, keys), they must have been produced under a runtime using <em>exactly the same parameters</em>. This situation may have ramifications if you're attempting to re-use ciphertexts across multiple FHE programs; those programs must be compiled with the <em>same</em> set of parameters.</p>
<div style="break-before: page; page-break-before: always;"></div><h1 id="key-generation"><a class="header" href="#key-generation">Key Generation</a></h1>
<p>Once you've created a runtime, generating keys is simple:</p>
<pre><pre class="playground"><code class="language-rust no_run edition2021"><span class="boring">use sunscreen::{
</span><span class="boring"> fhe_program,
</span><span class="boring"> types::{bfv::Signed, Cipher},
</span><span class="boring"> Compiler, Runtime, PublicKey
</span><span class="boring">};
</span><span class="boring">
</span><span class="boring">#[fhe_program(scheme = &quot;bfv&quot;)]
</span><span class="boring">fn noop() {
</span><span class="boring">}
</span><span class="boring">
</span><span class="boring">fn main() {
</span><span class="boring"> let fhe_program = Compiler::with_fhe_program(noop)
</span><span class="boring"> .compile()
</span><span class="boring"> .unwrap();
</span><span class="boring">
</span><span class="boring"> let runtime = Runtime::new(&amp;fhe_program.metadata.params).unwrap();
</span><span class="boring">
</span> let (public_key, private_key) = runtime.generate_keys().unwrap();
<span class="boring">}
</span></code></pre></pre>
<p>This produces a public key (which allows you to encrypt data and run FHE programs) and a private key (which allows you to decrypt).</p>
<div style="break-before: page; page-break-before: always;"></div><h1 id="encryption"><a class="header" href="#encryption">Encryption</a></h1>
<p>To encrypt data, simply call <code>encrypt()</code> on <code>Runtime</code>:</p>
<pre><pre class="playground"><code class="language-rust no_run edition2021"><span class="boring">use sunscreen::{
</span><span class="boring"> fhe_program,
</span><span class="boring"> types::{bfv::Signed, Cipher},
</span><span class="boring"> Compiler, Runtime, PublicKey
</span><span class="boring">};
</span><span class="boring">
</span><span class="boring">#[fhe_program(scheme = &quot;bfv&quot;)]
</span><span class="boring">fn noop() {
</span><span class="boring">}
</span><span class="boring">
</span><span class="boring">fn main() {
</span><span class="boring"> let fhe_program = Compiler::with_fhe_program(noop)
</span><span class="boring"> .compile()
</span><span class="boring"> .unwrap();
</span><span class="boring">
</span><span class="boring"> let runtime = Runtime::new(&amp;fhe_program.metadata.params).unwrap();
</span><span class="boring"> let (public_key, private_key) = runtime.generate_keys().unwrap();
</span><span class="boring">
</span> let val = Signed::from(15);
let val_enc = runtime.encrypt(val, &amp;public_key).unwrap();
<span class="boring">}
</span></code></pre></pre>
<p>This produces a <code>Ciphertext</code> value suitable for use in <code>run()</code>. Be careful not to confuse the <code>Ciphertext</code> type, which represents an actual encrypted value, with <a href="fhe_programs/runtime//fhe_programs/types/cipher.html"><code>Cipher</code></a>, which is a marker type to indicate a value in an FHE program is encrypted! Sunscreen can encrypt any of its provided <a href="fhe_programs/runtime/./fhe_programs/types/types.html">types</a> or fixed-length arrays<sup class="footnote-reference"><a href="#1">1</a></sup> of them. Note that arrays encrypt as multiple values in a single large <code>Ciphertext</code>.</p>
<p><em>[DW: if the user is sending many ciphertexts (e.g., a vector of ciphertexts) under the same scheme, wouldn't it make sense to only communicate the scheme parameters once for all of the ciphertexts rather than attaching them on each one? That would help save some space.]</em></p>
<div class="footnote-definition" id="1"><sup class="footnote-definition-label">1</sup>
<p>Fixed-length arrays have the type <code>[T; N]</code> where <code>N</code> is a the number <code>T</code>s. Don't confuse these with <code>Vec&lt;T&gt;</code>, which does not encode the length in its type! Sunscreen does not support <code>Vecs</code>.</p>
</div>
<h2 id="cleartext-metadata"><a class="header" href="#cleartext-metadata">Cleartext metadata</a></h2>
<p>Sunscreen attaches scheme parameters and the underlying datatype metadata to each <code>Ciphertext</code>. The former aids in serialization, while the latter <a href="fhe_programs/runtime//fhe_programs/runtime/running_fhe_programs.html#validation">prevents honest mistakes</a> and improves the developer experience. When you serialize <code>Ciphertext</code> values to send over the network, this metadata appears in the clear. For most applications, this will be public information and part of the protocol. If, for some reason, you need the data type or scheme parameters to also be encrypted, you should encrypt the serialized ciphertext (e.g. use TLS for communication).</p>
<div style="break-before: page; page-break-before: always;"></div><h1 id="running-fhe-programs"><a class="header" href="#running-fhe-programs">Running FHE Programs</a></h1>
<p>In our simple example, we called <code>runtime.run</code> to execute our FHE program</p>
<pre><pre class="playground"><code class="language-rust no_run edition2021"><span class="boring">use sunscreen::{*, types::{{bfv::Signed}, Cipher}};
</span><span class="boring">
</span><span class="boring">fn main() {
</span><span class="boring"> #[fhe_program(scheme = &quot;bfv&quot;)]
</span><span class="boring"> fn multiply(a: Cipher&lt;Signed&gt;, b: Cipher&lt;Signed&gt;) -&gt; Cipher&lt;Signed&gt; {
</span><span class="boring"> a * b
</span><span class="boring"> }
</span><span class="boring">
</span><span class="boring"> let fhe_program = Compiler::with_fhe_program(multiply)
</span><span class="boring"> .plain_modulus_constraint(PlainModulusConstraint::Raw(64))
</span><span class="boring"> .compile()
</span><span class="boring"> .unwrap();
</span><span class="boring">
</span><span class="boring"> let runtime = Runtime::new(&amp;fhe_program.metadata.params).unwrap();
</span><span class="boring"> let (public_key, _) = runtime.generate_keys().unwrap();
</span> let a_enc = runtime.encrypt(Signed::from(5), &amp;public_key).unwrap();
let b_enc = runtime.encrypt(Signed::from(15), &amp;public_key).unwrap();
let results = runtime.run(&amp;fhe_program, vec![a_enc, b_enc], &amp;public_key).unwrap();
<span class="boring">}
</span></code></pre></pre>
<p>Let's break down the arguments to <code>runtime.run</code>:</p>
<ol>
<li>The first <code>fhe_program</code> argument is the compiled program you wish to run.</li>
<li>The second <code>vec![a, b]</code> argument contains the input arguments to the program in a <a href="https://doc.rust-lang.org/std/vec/struct.Vec.html"><code>Vec</code></a>.</li>
<li>The final <code>public_key</code> argument is the public key used to generate the encrypted program inputs (i.e. <code>a_enc</code> and <code>b_enc</code>).</li>
</ol>
<h2 id="fhe-program-inputs"><a class="header" href="#fhe-program-inputs">FHE program inputs</a></h2>
<p>Rust requires collections be homogenous (i.e. each item is the same type). However, program arguments may not be always be of the same type! </p>
<p>Our <code>FheProgramInput</code> wrapper enum solves this problem; it wraps values so they can exist in a homogeneous collection. The run function's second argument is a <code>Vec&lt;T&gt;</code> where <code>T</code> readily converts into an <code>FheProgramInput</code> (i.e. <code>T impl</code> <a href="https://doc.rust-lang.org/std/convert/trait.Into.html"><code>Into&lt;FheProgramInput&gt;</code></a><sup class="footnote-reference"><a href="#1">1</a></sup>). <code>Ciphertext</code> and all types under <code>sunscreen::bfv::types::*</code> do this.</p>
<p>If your FHE program only accepts ciphertexts (a common scenario), it's sufficient to simply pass a <code>Vec&lt;Ciphertext&gt;</code> as we did in the above example. However, if you want to mix <code>Ciphertext</code> and unencrypted values, you'll need to make a <code>Vec&lt;FheProgramInput&gt;</code> manually, converting each argument yourself:</p>
<pre><pre class="playground"><code class="language-rust no_run edition2021"><span class="boring">use sunscreen::{*, types::{{bfv::Signed}, Cipher}};
</span><span class="boring">
</span><span class="boring">fn main() {
</span><span class="boring"> // Note the lack of the `Cipher` type on b. This declares
</span><span class="boring"> // it as a unencrypted.
</span><span class="boring"> #[fhe_program(scheme = &quot;bfv&quot;)]
</span><span class="boring"> fn multiply(a: Cipher&lt;Signed&gt;, b: Signed) -&gt; Cipher&lt;Signed&gt; {
</span><span class="boring"> a * b
</span><span class="boring"> }
</span><span class="boring">
</span><span class="boring"> let fhe_program = Compiler::with_fhe_program(multiply)
</span><span class="boring"> .compile()
</span><span class="boring"> .unwrap();
</span><span class="boring">
</span><span class="boring"> let runtime = Runtime::new(&amp;fhe_program.metadata.params).unwrap();
</span><span class="boring"> let (public_key, _) = runtime.generate_keys().unwrap();
</span>
let a_enc = runtime.encrypt(Signed::from(5), &amp;public_key).unwrap();
// a is encrypted, but the second argument, b, is not.
// We make a Vec&lt;FheProgramInput&gt; by calling `.into()`
// on each value.
let args: Vec&lt;FheProgramInput&gt; = vec![a_enc.into(), Signed::from(15).into()];
let results = runtime.run(&amp;fhe_program, args, &amp;public_key).unwrap();
<span class="boring">}
</span></code></pre></pre>
<div class="footnote-definition" id="1"><sup class="footnote-definition-label">1</sup>
<p><code>FheProgramInput</code> itself meets this requirement because every type in Rust is reflexive.</p>
</div>
<h3 id="validation"><a class="header" href="#validation">Validation</a></h3>
<p>When you compile your FHE program, the compiler marks down the call signature (argument and return types). The <code>run</code> function validates that the inputs you gave are appropriately encrypted/unencrypted and are of the correct type.</p>
<h2 id="return-value"><a class="header" href="#return-value">Return value</a></h2>
<p>On success, the <code>run</code> method returns a <code>Vec&lt;Ciphertext&gt;</code> containing each output of the FHE program.</p>
<ul>
<li>If the underlying FHE program returns a tuple, the entries of the <code>Vec</code> are each of the tuple's entries.</li>
<li>If the underlying FHE program returns a single value, the <code>Vec</code> contains a single entry.</li>
<li>If the underlying FHE program doesn't return anything, you should write more useful programs. The <code>Vec</code> will be empty.</li>
</ul>
<div style="break-before: page; page-break-before: always;"></div><h1 id="decryption"><a class="header" href="#decryption">Decryption</a></h1>
<p>To decrypt, simply call <code>decrypt()</code> using your private key and the data you want to decrypt</p>
<pre><pre class="playground"><code class="language-rust no_run edition2021"><span class="boring">use sunscreen::{
</span><span class="boring"> fhe_program,
</span><span class="boring"> types::{bfv::Signed, Cipher},
</span><span class="boring"> Compiler, Runtime, PublicKey, PlainModulusConstraint
</span><span class="boring">};
</span><span class="boring">
</span><span class="boring">#[fhe_program(scheme = &quot;bfv&quot;)]
</span><span class="boring">fn noop() {
</span><span class="boring">}
</span><span class="boring">
</span><span class="boring">fn main() {
</span><span class="boring"> let fhe_program = Compiler::with_fhe_program(noop)
</span><span class="boring"> .plain_modulus_constraint(PlainModulusConstraint::Raw(5))
</span><span class="boring"> .compile()
</span><span class="boring"> .unwrap();
</span><span class="boring">
</span><span class="boring"> let runtime = Runtime::new(&amp;fhe_program.metadata.params).unwrap();
</span><span class="boring"> let (public_key, private_key) = runtime.generate_keys().unwrap();
</span><span class="boring">
</span><span class="boring"> let val = Signed::from(15);
</span><span class="boring"> let val_enc = runtime.encrypt(val, &amp;public_key).unwrap();
</span><span class="boring">
</span> // val_enc is an encrypted `Signed` value coming from an FHE program
// or just directly encrypted.
let a: Signed = runtime.decrypt(&amp;val_enc, &amp;private_key).unwrap();
<span class="boring">}
</span></code></pre></pre>
<h2 id="validation-1"><a class="header" href="#validation-1">Validation</a></h2>
<p>Unlike with <code>encrypt</code>, you must specify the unencrypted data type (either on the left-hand side as above or using <a href="https://techblog.tonsser.com/posts/what-is-rusts-turbofish">turbofish</a>). The encrypted value's type must match the assigned type; if the specified data type doesn't match that on the <a href="fhe_programs/runtime/./encryption.html#type-annotation">ciphertext</a>, <code>decrypt</code> will return an error. In the above example, decrypt will fail if the encrypted value is not a <code>Signed</code> type.</p>
<div style="break-before: page; page-break-before: always;"></div><h1 id="serialization"><a class="header" href="#serialization">Serialization</a></h1>
<p>While most examples compute everything in one place, in practice, data will be split amongst multiple machines. You can serialize many things in Sunscreen:</p>
<ul>
<li>Ciphertexts</li>
<li>Keys</li>
<li>Scheme parameters</li>
<li>FHE programs</li>
</ul>
<p>Sunscreen uses <a href="https://serde.rs/"><code>serde</code></a> for serialization and can serialize data in a number of formats including JSON and bincode. Since most data in Sunscreen is high entropy byte arrays, we recommend using <a href="https://docs.rs/bincode/1.3.3/bincode/">bincode</a> since it reduces storage and network requirements by efficiently packing byte arrays.</p>
<p>The process to serialize and deserialize any type is the same, but this example shows how to do it with a ciphertext:</p>
<pre><pre class="playground"><code class="language-rust no_run edition2021"><span class="boring">use sunscreen::{
</span><span class="boring"> fhe_program,
</span><span class="boring"> types::{bfv::Signed, Cipher},
</span><span class="boring"> Compiler, Runtime, PublicKey, Ciphertext
</span><span class="boring">};
</span><span class="boring">
</span><span class="boring">#[fhe_program(scheme = &quot;bfv&quot;)]
</span><span class="boring">fn noop() {
</span><span class="boring">}
</span><span class="boring">
</span><span class="boring">fn main() {
</span><span class="boring"> let fhe_program = Compiler::with_fhe_program(noop)
</span><span class="boring"> .compile()
</span><span class="boring"> .unwrap();
</span><span class="boring">
</span><span class="boring"> let runtime = Runtime::new(&amp;fhe_program.metadata.params).unwrap();
</span><span class="boring"> let (public_key, _) = runtime.generate_keys().unwrap();
</span> let c = runtime
.encrypt(Signed::from(20), &amp;public_key)
.unwrap();
// ser is now a Vec&lt;u8&gt; that can be written to disk, socket, etc.
let ser = bincode::serialize(&amp;c).unwrap();
// Upon receiving a serialized byte array, deserialize it
// back into a Ciphertext. You may now use it normally.
let c: Ciphertext = bincode::deserialize(&amp;ser).unwrap();
<span class="boring">}
</span></code></pre></pre>
<p>As with any dependency, you'll need to add <code>bincode</code> as a dependency in your <code>Cargo.toml</code>.</p>
<div style="break-before: page; page-break-before: always;"></div><h1 id="applications"><a class="header" href="#applications">Applications</a></h1>
<p>In this section, we'll look at some (hopefully) interesting applications of FHE to web2 and web3.</p>
<div style="break-before: page; page-break-before: always;"></div><h1 id="private-token-swap-via-automated-market-makers"><a class="header" href="#private-token-swap-via-automated-market-makers">Private token swap (via automated market makers)</a></h1>
<p>We'll now walk through a less trivial computation that can be done with FHE. Our program is inspired by computations used in <a href="https://docs.uniswap.org/protocol/V2/concepts/protocol-overview/how-uniswap-works">automated market makers</a> (AMMs).
While some of the code and ideas presented here could be useful for constructing an automated market maker with swap privacy, many details have been omitted.</p>
<p>Alice would like to swap some NU tokens for some ETH tokens. She'd like to perform this token swap without revealing to anyone her order amount. This might be done to prevent malicious actors from <a href="https://arxiv.org/pdf/1902.05164.pdf">front-running</a> her order.</p>
<p>To swap her tokens, she interacts with a &quot;pool&quot; that has reserves of both NU and ETH (implemented as a smart contract). For this example, we'll say the pool contains 100 ETH tokens and 1000 NU tokens. The reserve values here are public information. The exchange rate for NU ⇔ ETH <a href="https://docs.uniswap.org/protocol/V2/concepts/core-concepts/swaps">changes</a> based on the pool's reserves of the two tokens. </p>
<p>Alice will encrypt her order (i.e. the amount of NU tokens she wants to swap) and then submit it to the blockchain miner. The miner can then calculate how much <em>encrypted</em> ETH Alice should receive in exchange for her encrypted amount of NU tokens via FHE.</p>
<h2 id="an-intro-to-amms-for-the-uninitiated"><a class="header" href="#an-intro-to-amms-for-the-uninitiated">An intro to AMMs for the uninitiated</a></h2>
<p>If you're not familiar with AMMs, we suggest starting <a href="https://www.coindesk.com/learn/2021/08/20/what-is-an-automated-market-maker/">here</a>.</p>
<p>AMMs can be a great alternative to centralized exchanges since they allow you to exchange one type of a token for another with (generally) lower fees. Each token pair (in our example, we have NU and ETH) has its own &quot;pool&quot; which users interact with when performing a trade between those two particular tokens. You can also earn passive income from your tokens by providing liquidity (i.e. depositing two tokens) to a specific pool.</p>
<p>The exchange rate between the two tokens evolves automatically based on a known mathematical formula.</p>
<p>Unfortunately, the open and public nature of AMMs combined with the predictable behavior of the exchange rate allows for front-running attacks. Bad actors observe pending trades and then submit their own trades to &quot;manipulate&quot; the exchange rate in a way favorable to themselves. What does this mean for you as a potential AMM user? You may end up with a worse price than expected when your trade executes as these front-running attacks are fairly common and widespread. </p>
<p>Privacy (specifically hiding trade values) is one solution to this front-running problem. </p>
<h2 id="program-walkthrough"><a class="header" href="#program-walkthrough">Program walkthrough</a></h2>
<p>Let's look at how to implement this now.</p>
<h3 id="setup"><a class="header" href="#setup">Setup</a></h3>
<pre><pre class="playground"><code class="language-rust no_run edition2021">
<span class="boring">#![allow(unused)]
</span><span class="boring">fn main() {
</span>use sunscreen::{
fhe_program,
types::{bfv::Rational, Cipher},
Ciphertext, CompiledFheProgram, Compiler, Params, PrivateKey, PublicKey,
Runtime,
};
#[fhe_program(scheme = &quot;bfv&quot;)]
/// This program swaps NU tokens for ETH.
fn swap_nu(
nu_tokens_to_trade: Cipher&lt;Rational&gt;,
) -&gt; Cipher&lt;Rational&gt; {
let total_eth = 100.0;
let total_nu = 1_000.0;
-(total_eth * total_nu / (total_nu + nu_tokens_to_trade) - total_eth)
}
<span class="boring">}
</span></code></pre></pre>
<p>We begin by importing the stuff we're going to use.</p>
<p>We declare our <code>swap_nu</code> function as an FHE program with the appropriate attribute (<code>#[fhe_program(scheme = &quot;bfv&quot;)]</code>).</p>
<p><code>swap_nu</code> computes how much encrypted ETH a user will receive in exchange for <code>nu_tokens_to_trade</code> some amount of encrypted NU . Since we'll need to divide by a ciphertext, we'll have to use the <code>Rational</code> type here. Thus, notice that <code>swap_nu</code> takes in a <code>Cipher&lt;Rational&gt;</code> and returns a <code>Cipher&lt;Rational&gt;</code>. If you're wondering where the formula for <code>swap_nu</code> came from, it's from the constant product formula used by some automated market makers.</p>
<p>Notice that the other values in <code>swap_nu</code> (i.e. the pool reserves for ETH <code>total_eth</code> and NU <code>total_nu</code>) are in the clear.</p>
<h3 id="alice"><a class="header" href="#alice">Alice</a></h3>
<pre><pre class="playground"><code class="language-rust no_run edition2021">
<span class="boring">#![allow(unused)]
</span><span class="boring">fn main() {
</span><span class="boring">use sunscreen::{
</span><span class="boring"> fhe_program,
</span><span class="boring"> types::{bfv::Rational, Cipher},
</span><span class="boring"> Ciphertext, CompiledFheProgram, Compiler, Params, PrivateKey,
</span><span class="boring"> Error,
</span><span class="boring"> PublicKey,
</span><span class="boring"> Runtime,
</span><span class="boring">};
</span><span class="boring">
</span>/// Alice is a party that would like to trade some NU for ETH.
struct Alice {
/// Alice's public key
pub public_key: PublicKey,
/// Alice's private key
private_key: PrivateKey,
/// Alice's runtime
runtime: Runtime,
}
<span class="boring">}
</span></code></pre></pre>
<p>Alice wants to swap some encrypted (i.e. hidden) amount of NU for an encrypted (i.e. hidden) amount of ETH. She'll need a public/private key pair to do this (since she needs to encrypt her order with respect to her public key).</p>
<pre><pre class="playground"><code class="language-rust no_run edition2021">
<span class="boring">#![allow(unused)]
</span><span class="boring">fn main() {
</span><span class="boring">use sunscreen::{
</span><span class="boring"> fhe_program,
</span><span class="boring"> types::{bfv::Rational, Cipher},
</span><span class="boring"> Ciphertext, CompiledFheProgram, Compiler, Params, PrivateKey,
</span><span class="boring"> Error,
</span><span class="boring"> PublicKey,
</span><span class="boring"> Runtime,
</span><span class="boring">};
</span><span class="boring">
</span><span class="boring">/// Alice is a party that would like to trade some NU for ETH.
</span><span class="boring">struct Alice {
</span><span class="boring"> /// Alice's public key
</span><span class="boring"> pub public_key: PublicKey,
</span><span class="boring">
</span><span class="boring"> /// Alice's private key
</span><span class="boring"> private_key: PrivateKey,
</span><span class="boring">
</span><span class="boring"> /// Alice's runtime
</span><span class="boring"> runtime: Runtime,
</span><span class="boring">}
</span><span class="boring">
</span>impl Alice {
pub fn setup(params: &amp;Params) -&gt; Result&lt;Alice, Error&gt; {
let runtime = Runtime::new(params)?;
let (public_key, private_key) = runtime.generate_keys()?;
Ok(Alice {
public_key,
private_key,
runtime,
})
}
pub fn create_transaction(&amp;self, amount: f64) -&gt; Result&lt;Ciphertext, Error&gt; {
Ok(self.runtime
.encrypt(Rational::try_from(amount)?, &amp;self.public_key)?
)
}
pub fn check_received_eth(&amp;self, received_eth: Ciphertext) -&gt; Result&lt;(), Error&gt; {
let received_eth: Rational = self
.runtime
.decrypt(&amp;received_eth, &amp;self.private_key)?;
let received_eth: f64 = received_eth.into();
println!(&quot;Alice received {}ETH&quot;, received_eth);
Ok(())
}
}
<span class="boring">}
</span></code></pre></pre>
<p>Alice first constructs a runtime and then can generate her public/private key pair.</p>
<p>To encrypt her order amount, she'll call <code>create_transaction</code> passing in the <code>amount</code> of NU she wants to trade and her<code>public_key</code>. We need <code>try_from</code> here to help us perform the appropriate type conversion.</p>
<p>We won't use this until the very end but <code>check_received_eth</code> will allow Alice to see how many ETH tokens she's received after performing the swap. Recall that Alice will receive an encrypted amount of ETH tokens, so in <code>check_received_eth</code> Alice will decrypt this value by passing in her <code>private_key</code> and <code>received_eth</code> the encrypted amount of ETH she received.</p>
<h3 id="miner"><a class="header" href="#miner">Miner</a></h3>
<p>Let's look at the miner next.</p>
<pre><pre class="playground"><code class="language-rust no_run edition2021">
<span class="boring">#![allow(unused)]
</span><span class="boring">fn main() {
</span><span class="boring">use sunscreen::{
</span><span class="boring"> fhe_program,
</span><span class="boring"> types::{bfv::Rational, Cipher},
</span><span class="boring"> Ciphertext, CompiledFheProgram, Compiler, Params, PrivateKey,
</span><span class="boring"> Error,
</span><span class="boring"> PublicKey,
</span><span class="boring"> Runtime,
</span><span class="boring">};
</span>/// Imagine this is a miner in a blockchain application. They're responsible
/// for processing transactions
struct Miner {
/// The compiled swap_nu program
pub compiled_swap_nu: CompiledFheProgram,
/// The Miner's runtime
runtime: Runtime,
}
<span class="boring">}
</span></code></pre></pre>
<p>Recall that the miner is responsible for processing Alice's order; thus, he'll have to run the compiled <code>swap_nu</code> program (<code>compiled_swap_nu</code>).</p>
<pre><pre class="playground"><code class="language-rust no_run edition2021">
<span class="boring">#![allow(unused)]
</span><span class="boring">fn main() {
</span><span class="boring">use sunscreen::{
</span><span class="boring"> fhe_program,
</span><span class="boring"> types::{bfv::Rational, Cipher},
</span><span class="boring"> Ciphertext, CompiledFheProgram, Compiler, Params, PrivateKey,
</span><span class="boring"> Error,
</span><span class="boring"> PublicKey,
</span><span class="boring"> Runtime,
</span><span class="boring">};
</span><span class="boring">
</span><span class="boring">#[fhe_program(scheme = &quot;bfv&quot;)]
</span><span class="boring">/// This program swaps NU tokens for ETH.
</span><span class="boring">fn swap_nu(
</span><span class="boring"> nu_tokens_to_trade: Cipher&lt;Rational&gt;,
</span><span class="boring">) -&gt; Cipher&lt;Rational&gt; {
</span><span class="boring"> let total_eth = 100.0;
</span><span class="boring"> let total_nu = 1_000.0;
</span><span class="boring">
</span><span class="boring"> -(total_eth * total_nu / (total_nu + nu_tokens_to_trade) - total_eth)
</span><span class="boring">}
</span><span class="boring">
</span><span class="boring">/// Imagine this is a miner in a blockchain application. They're responsible
</span><span class="boring">/// for processing transactions
</span><span class="boring">struct Miner {
</span><span class="boring"> /// The compiled FHE swap program
</span><span class="boring"> pub compiled_swap_nu: CompiledFheProgram,
</span><span class="boring">
</span><span class="boring"> /// The Miner's runtime
</span><span class="boring"> runtime: Runtime,
</span><span class="boring">}
</span><span class="boring">
</span>impl Miner {
pub fn setup() -&gt; Result&lt;Miner, Error&gt; {
let compiled_swap_nu = Compiler::with_fhe_program(swap_nu).compile()?;
let runtime = Runtime::new(&amp;compiled_swap_nu.metadata.params)?;
Ok(Miner {
compiled_swap_nu,
runtime,
})
}
pub fn run_contract(
&amp;self,
nu_tokens_to_trade: Ciphertext,
public_key: &amp;PublicKey,
) -&gt; Result&lt;Ciphertext, Error&gt; {
let results = self.runtime.run(&amp;self.compiled_swap_nu, vec![nu_tokens_to_trade], public_key)?;
Ok(results[0].clone())
}
}
<span class="boring">}
</span></code></pre></pre>
<p>In <code>setup</code>, we compile <code>swap_nu</code> and save the runnable program as <code>compiled_swap_nu</code>.
We also construct and save a <code>Runtime</code> for our miner to allow him to run it.</p>
<p>The miner can run the token swap contract (see <code>run_contract</code>) by calling <code>runtime.run</code> with the <code>compiled_swap_nu</code> program, Alice's encrypted order amount (<code>nu_tokens_to_trade</code>), and Alice's <code>public_key</code>. Recall that we must pass in arguments to an FHE program (such as <code>compiled_swap_nu</code>) via a <code>Vec</code>.</p>
<h3 id="swapping-the-tokens-privately"><a class="header" href="#swapping-the-tokens-privately">Swapping the tokens privately</a></h3>
<pre><pre class="playground"><code class="language-rust no_run edition2021"><span class="boring">use sunscreen::{
</span><span class="boring"> fhe_program,
</span><span class="boring"> types::{bfv::Rational, Cipher},
</span><span class="boring"> Ciphertext, CompiledFheProgram, Compiler, Params, PrivateKey,
</span><span class="boring"> Error,
</span><span class="boring"> PublicKey,
</span><span class="boring"> Runtime,
</span><span class="boring">};
</span><span class="boring">
</span><span class="boring"> #[fhe_program(scheme = &quot;bfv&quot;)]
</span><span class="boring">/// This program swaps NU tokens to receive ETH.
</span><span class="boring">fn swap_nu(
</span><span class="boring"> nu_tokens_to_trade: Cipher&lt;Rational&gt;,
</span><span class="boring">) -&gt; Cipher&lt;Rational&gt; {
</span><span class="boring"> let total_eth = 100.0;
</span><span class="boring"> let total_nu = 1_000.0;
</span><span class="boring">
</span><span class="boring"> -(total_eth * total_nu / (total_nu + nu_tokens_to_trade) - total_eth)
</span><span class="boring">}
</span><span class="boring">
</span><span class="boring">/// Imagine this is a miner in a blockchain application. They're responsible
</span><span class="boring">/// for processing transactions
</span><span class="boring">struct Miner {
</span><span class="boring"> /// The compiled swap_nu program
</span><span class="boring"> pub compiled_swap_nu: CompiledFheProgram,
</span><span class="boring">
</span><span class="boring"> /// The Miner's runtime
</span><span class="boring"> runtime: Runtime,
</span><span class="boring">}
</span><span class="boring">
</span><span class="boring">impl Miner {
</span><span class="boring"> pub fn setup() -&gt; Result&lt;Miner, Error&gt; {
</span><span class="boring"> let compiled_swap_nu = Compiler::with_fhe_program(swap_nu).compile()?;
</span><span class="boring">
</span><span class="boring"> let runtime = Runtime::new(&amp;compiled_swap_nu.metadata.params)?;
</span><span class="boring">
</span><span class="boring"> Ok(Miner {
</span><span class="boring"> compiled_swap_nu,
</span><span class="boring"> runtime,
</span><span class="boring"> })
</span><span class="boring"> }
</span><span class="boring">
</span><span class="boring"> pub fn run_contract(
</span><span class="boring"> &amp;self,
</span><span class="boring"> nu_tokens_to_trade: Ciphertext,
</span><span class="boring"> public_key: &amp;PublicKey,
</span><span class="boring"> ) -&gt; Result&lt;Ciphertext, Error&gt; {
</span><span class="boring"> let results = self.runtime.run(&amp;self.compiled_swap_nu, vec![nu_tokens_to_trade], public_key)?;
</span><span class="boring">
</span><span class="boring"> Ok(results[0].clone())
</span><span class="boring"> }
</span><span class="boring">}
</span><span class="boring">
</span><span class="boring">/// Alice is a party that would like to trade some NU for ETH.
</span><span class="boring">struct Alice {
</span><span class="boring"> /// Alice's public key
</span><span class="boring"> pub public_key: PublicKey,
</span><span class="boring">
</span><span class="boring"> /// Alice's private key
</span><span class="boring"> private_key: PrivateKey,
</span><span class="boring">
</span><span class="boring"> /// Alice's runtime
</span><span class="boring"> runtime: Runtime,
</span><span class="boring">}
</span><span class="boring">
</span><span class="boring">impl Alice {
</span><span class="boring"> pub fn setup(params: &amp;Params) -&gt; Result&lt;Alice, Error&gt; {
</span><span class="boring"> let runtime = Runtime::new(params)?;
</span><span class="boring">
</span><span class="boring"> let (public_key, private_key) = runtime.generate_keys()?;
</span><span class="boring">
</span><span class="boring"> Ok(Alice {
</span><span class="boring"> public_key,
</span><span class="boring"> private_key,
</span><span class="boring"> runtime,
</span><span class="boring"> })
</span><span class="boring"> }
</span><span class="boring">
</span><span class="boring"> pub fn create_transaction(&amp;self, amount: f64) -&gt; Result&lt;Ciphertext, Error&gt; {
</span><span class="boring"> Ok(self.runtime
</span><span class="boring"> .encrypt(Rational::try_from(amount)?, &amp;self.public_key)?
</span><span class="boring"> )
</span><span class="boring"> }
</span><span class="boring">
</span><span class="boring"> pub fn check_received_eth(&amp;self, received_eth: Ciphertext) -&gt; Result&lt;(), Error&gt; {
</span><span class="boring"> let received_eth: Rational = self
</span><span class="boring"> .runtime
</span><span class="boring"> .decrypt(&amp;received_eth, &amp;self.private_key)?;
</span><span class="boring">
</span><span class="boring"> let received_eth: f64 = received_eth.into();
</span><span class="boring">
</span><span class="boring"> println!(&quot;Alice received {}ETH&quot;, received_eth);
</span><span class="boring">
</span><span class="boring"> Ok(())
</span><span class="boring"> }
</span><span class="boring">}
</span><span class="boring">
</span>fn main() -&gt; Result&lt;(), Error&gt; {
// Set up the miner with some NU and ETH tokens.
let miner = Miner::setup()?;
// Alice sets herself up. The FHE scheme parameters are public to the
// protocol, so Alice has them.
let alice = Alice::setup(&amp;miner.compiled_swap_nu.metadata.params)?;
let transaction = alice.create_transaction(20.0)?;
let encrypted_received_eth =
miner.run_contract(transaction, &amp;alice.public_key)?;
alice.check_received_eth(encrypted_received_eth)?;
Ok(())
}
</code></pre></pre>
<p>We set up the miner and then Alice (notice that Alice relies on parameters generated from the Miner's setup). Both of them must use the same set of FHE scheme parameters for compatibility. In deployment, these values would likely be fixed at the protocol level.</p>
<p>Alice calls <code>create_transaction</code> to encrypt her trade amount of <code>20.0</code> NU tokens.</p>
<p>The miner calls <code>run_contract</code> to calculate how much encrypted ETH Alice will receive for her encrypted NU (based on the formula from <code>swap_nu</code>). The miner passes in Alice's encrypted trade amount (the result of <code>alice.create_transaction(20.0)</code> which is a ciphertext) along with Alice's public key (<code>alice.public_key</code>).</p>
<p>Finally, Alice can determine how much ETH she actually received from the swap via <code>check_received_eth</code>.</p>
<h3 id="performance"><a class="header" href="#performance">Performance</a></h3>
<p>The entire program (not including compilation time) takes ~25 ms on an Intel Xeon @ 3.0 GHz (with 8 cores and 16 GB RAM) and ~100 ms on a Macbook Air M1.</p>
<h2 id="whats-missing"><a class="header" href="#whats-missing">What's missing?</a></h2>
<p>For simplicity, we've omitted many details that are needed to actually execute a private token swap in real life. You may have noticed we mentioned nothing about Alice's account balance (deducting the amount of NU she wants to swap or adding the amount of ETH she receives), ensuring that Alice is behaving honestly (e.g. she actually has enough NU in her account to make the swap, she isn't creating tokens out of thin air), or how to determine the new reserve values of the pool (i.e. how much NU and ETH are in the pool after Alice has made her swap).</p>
<p>If you're curious about the answers:</p>
<ul>
<li>we've omitted account balances for simplicity (but such account balances would be encrypted as well)</li>
<li>to ensure Alice is behaving honestly, we would need additional cryptographic tools such as zero-knowledge proofs</li>
<li>the primary goal of private token swaps would be to prevent <a href="https://ethereum.org/en/developers/docs/mev/#mev-examples-sandwich-trading">front-running</a>, thus there would be some additional step to &quot;reveal&quot; the new reserve values </li>
</ul>
<div style="break-before: page; page-break-before: always;"></div><h1 id="private-information-retrieval"><a class="header" href="#private-information-retrieval">Private information retrieval</a></h1>
<p>With private information retrieval (PIR), a user can retrieve an item from a database without <em>revealing</em> to the server which item she's interested in. PIR is useful for both web2 and web3 applications. In web2, for example, PIR can be used to <a href="https://www.usenix.org/system/files/sec21summer_kulshrestha.pdf">help detect harmful images</a> in end-to-end encrypted messaging. For private cryptocurrencies, PIR can help light clients <a href="https://eprint.iacr.org/2021/1256.pdf">retrieve relevant transactions</a>.</p>
<p>To make this section easy to understand, we'll implement two simple PIR algorithms with our compiler.</p>
<p>The <a href="fhe_programs/./pir_simple.html">first algorithm</a> does not require the full power of FHE since we only perform ciphertext-plaintext multiplication via a vector dot product; thus, an additively homomorphic encryption scheme would actually suffice.</p>
<p>The <a href="fhe_programs/./pir_matrix.html">second algorithm</a> <em>does</em> require the full power of FHE as we'll perform both ciphertext-ciphertext multiplication and ciphertext-plaintext multiplication via a matrix-vector product and vector dot product.</p>
<div style="break-before: page; page-break-before: always;"></div><h1 id="warm-up-a-very-simple-pir-algorithm"><a class="header" href="#warm-up-a-very-simple-pir-algorithm">Warm up: a very simple PIR algorithm</a></h1>
<p>We'll start with a very simple algorithm that uses a dot product to return an item privately. </p>
<h2 id="how-will-our-algorithm-work"><a class="header" href="#how-will-our-algorithm-work">How will our algorithm work?</a></h2>
<p>Everything in the database will be <em>un</em>encrypted. We'll represent our database as a <a href="https://en.wikipedia.org/wiki/Euclidean_vector">vector</a> of <code>n</code> items.</p>
<p>Let's say that Alice wants to retrieve the 2nd item from the database. Alice will send a query to the server; we'll represent this query as a vector of length <code>n</code> as well.</p>
<h3 id="information-retrieval-without-privacy"><a class="header" href="#information-retrieval-without-privacy">Information retrieval (<strong>without privacy</strong>)</a></h3>
<p>Every element of this query vector, <em>except</em> the one Alice is interested in, will have a 0 in its place. Alice will place a 1 in the 2nd entry (since she's interested in the 2nd item). When the server take the dot product of these two vectors, Alice will get back the item she wanted to retrieve:</p>
<p>[item<sub>1</sub>, item<sub>2</sub>, item<sub>3</sub>, ... , item<sub>n</sub>] · [0, 1, 0, ... , 0]<sup>t</sup> </p>
<p>= item<sub>1</sub> · 0 + item<sub>2</sub> · 1 + item<sub>3</sub> · 0 + ... + item<sub>n</sub> · 0 </p>
<p>= item<sub>2</sub></p>
<p>Of course, the server can observe that Alice is interested in retrieving the 2nd item. How do we make this query private?</p>
<h3 id="making-the-query-private"><a class="header" href="#making-the-query-private">Making the query private</a></h3>
<p>For simplicity, let Enc(x) denote that we encrypt x.<sup class="footnote-reference"><a href="#1">1</a></sup></p>
<p>Since Alice doesn't want to reveal to the server <em>which</em> item she's interested in, she encrypts each of the elements in her query vector with respect to her FHE public key. Voila! We can now retrieve the information privately:</p>
<p>[item<sub>1</sub>, item<sub>2</sub>, item<sub>3</sub>, ... , item<sub>n</sub>] · [Enc(0), Enc(1), Enc(0), ... , Enc(0)]<sup>t</sup> </p>
<p>= item<sub>1</sub> · Enc(0) + item<sub>2</sub> · Enc(1) + item<sub>3</sub> · Enc(0) + ... + item<sub>n</sub> · Enc(0) </p>
<p>= Enc(item<sub>2</sub>)</p>
<div class="footnote-definition" id="1"><sup class="footnote-definition-label">1</sup>
<p>The encryption scheme must be <a href="https://en.wikipedia.org/wiki/Probabilistic_encryption">probabilistic</a> (such that different randomness is used for encrypting each element in the query vector). Otherwise, the server <em>would</em> be able to tell apart Enc(1) from Enc(0) and deduce what Alice wants to retrieve. You don't have to worry about this issue when using Sunscreen's compiler.</p>
</div>
<h2 id="program-walkthrough-1"><a class="header" href="#program-walkthrough-1">Program walkthrough</a></h2>
<p>Our database will have 100 items in it. We'll represent the vectors from earlier as <a href="fhe_programs/./types/types.html">arrays</a>, one of Sunscreen's supported types.</p>
<h3 id="setup-1"><a class="header" href="#setup-1">Setup</a></h3>
<pre><pre class="playground"><code class="language-rust no_run edition2021">
<span class="boring">#![allow(unused)]
</span><span class="boring">fn main() {
</span>use sunscreen::{
fhe_program,
types::{bfv::Signed, Cipher},
};
const DATABASE_SIZE: usize = 100;
#[fhe_program(scheme = &quot;bfv&quot;)]
/// This program takes a user's query and looks up the entry in the database.
/// Queries are arrays containing a single 1 element at the
/// desired item's index and 0s elsewhere.
fn lookup(query: [Cipher&lt;Signed&gt;; DATABASE_SIZE], database: [Signed; DATABASE_SIZE]) -&gt; Cipher&lt;Signed&gt; {
let mut sum = query[0] * database[0];
for i in 1..DATABASE_SIZE {
sum = sum + query[i] * database[i]
}
sum
}
<span class="boring">}
</span></code></pre></pre>
<p>We begin by importing the stuff we're going to use.</p>
<p>We declare our <code>lookup</code> function as an FHE program with the appropriate attribute (<code>#[fhe_program(scheme = &quot;bfv&quot;)]</code>).</p>
<p><code>lookup</code> implements the dot product formula discussed above. It takes in the unencrypted <code>database</code> and the encrypted <code>query</code> from the user to retrieve an item privately. The database is an array of length <code>DATABASE_SIZE</code> where each item in the database is a signed integer (<code>Signed</code>). Hence, the user's <code>query</code> is an array of length <code>DATABASE_SIZE</code> as well, where each entry is of type <code>Cipher&lt;Signed&gt;</code>.</p>
<h3 id="alice-1"><a class="header" href="#alice-1">Alice</a></h3>
<pre><pre class="playground"><code class="language-rust no_run edition2021">
<span class="boring">#![allow(unused)]
</span><span class="boring">fn main() {
</span><span class="boring">use sunscreen::{
</span><span class="boring"> fhe_program,
</span><span class="boring"> types::{bfv::Signed, Cipher},
</span><span class="boring"> Ciphertext, CompiledFheProgram, Compiler, Error, FheProgramInput, Params, PrivateKey,
</span><span class="boring"> PublicKey, Runtime,
</span><span class="boring">};
</span><span class="boring">
</span>/// Alice is a party that wants to look up a value in the database without
/// revealing what she looked up.
struct Alice {
/// Alice's public key
pub public_key: PublicKey,
/// Alice's private key
private_key: PrivateKey,
/// Alice's runtime
runtime: Runtime,
}
<span class="boring">}
</span></code></pre></pre>
<p>Alice wants to retrieve an item from the database privately. She'll need a public/private key pair to do this (since she needs to encrypt her query with respect to her public key).</p>
<pre><pre class="playground"><code class="language-rust no_run edition2021">
<span class="boring">#![allow(unused)]
</span><span class="boring">fn main() {
</span><span class="boring">use sunscreen::{
</span><span class="boring"> fhe_program,
</span><span class="boring"> types::{bfv::Signed, Cipher},
</span><span class="boring"> Ciphertext, CompiledFheProgram, Compiler, Error, FheProgramInput, Params, PrivateKey,
</span><span class="boring"> PublicKey, Runtime,
</span><span class="boring">};
</span><span class="boring">
</span><span class="boring">const DATABASE_SIZE: usize = 100;
</span><span class="boring">
</span><span class="boring">/// Alice is a party that wants to look up a value in the database without
</span><span class="boring">/// revealing what she looked up.
</span><span class="boring">struct Alice {
</span><span class="boring"> /// Alice's public key
</span><span class="boring"> pub public_key: PublicKey,
</span><span class="boring">
</span><span class="boring"> /// Alice's private key
</span><span class="boring"> private_key: PrivateKey,
</span><span class="boring">
</span><span class="boring"> /// Alice's runtime
</span><span class="boring"> runtime: Runtime,
</span><span class="boring">}
</span><span class="boring">
</span>impl Alice {
pub fn setup(params: &amp;Params) -&gt; Result&lt;Alice, Error&gt; {
let runtime = Runtime::new(params)?;
let (public_key, private_key) = runtime.generate_keys()?;
Ok(Alice {
public_key,
private_key,
runtime,
})
}
pub fn create_query(&amp;self, index: usize) -&gt; Result&lt;Ciphertext, Error&gt; {
let mut query = [Signed::from(0); DATABASE_SIZE];
query[index] = Signed::from(1);
Ok(self.runtime.encrypt(query, &amp;self.public_key)?)
}
pub fn check_response(&amp;self, value: Ciphertext) -&gt; Result&lt;(), Error&gt; {
let value: Signed = self.runtime.decrypt(&amp;value, &amp;self.private_key)?;
let value: i64 = value.into();
println!(&quot;Alice received {}&quot;, value);
Ok(())
}
}
<span class="boring">}
</span></code></pre></pre>
<p>Alice will need to construct a runtime. Once that's done, she can generate her public/private key pair. </p>
<p>Alice can create her unencrypted query &quot;vector&quot; (actually an <a href="fhe_programs/./types/types.html">array</a>) of 0's and 1's by calling <code>create_query</code>. Recall that the we'll have a 1 in the place of her desired item's index and a 0 elsewhere. Since she wants her query to be private, she'll <code>encrypt</code> her <code>query</code>, passing in her <code>public_key</code> as necessary.</p>
<p>We won't use this until the very end but <code>check_response</code> allows Alice to decrypt the server's response by passing in the ciphertext she received (<code>value</code>) along with her <code>private_key</code>.</p>
<h3 id="server"><a class="header" href="#server">Server</a></h3>
<p>Let's look at the server next.</p>
<pre><pre class="playground"><code class="language-rust no_run edition2021">
<span class="boring">#![allow(unused)]
</span><span class="boring">fn main() {
</span><span class="boring">use sunscreen::{
</span><span class="boring"> fhe_program,
</span><span class="boring"> types::{bfv::Signed, Cipher},
</span><span class="boring"> Ciphertext, CompiledFheProgram, Compiler, Error, FheProgramInput, Params, PrivateKey,
</span><span class="boring"> PublicKey, Runtime,
</span><span class="boring">};
</span>/// This is the server that processes Alice's query.
struct Server {
/// The compiled database lookup program
pub compiled_lookup: CompiledFheProgram,
/// The server's runtime
runtime: Runtime,
}
<span class="boring">}
</span></code></pre></pre>
<p>Recall that the server is responsible for retrieving Alice's item from the database; thus, it will have to run the compiled <code>lookup</code> program (<code>compiled_lookup</code>).</p>
<pre><pre class="playground"><code class="language-rust no_run edition2021">
<span class="boring">#![allow(unused)]
</span><span class="boring">fn main() {
</span><span class="boring">use sunscreen::{
</span><span class="boring"> fhe_program,
</span><span class="boring"> types::{bfv::Signed, Cipher},
</span><span class="boring"> Ciphertext, CompiledFheProgram, Compiler, Error, FheProgramInput, Params, PrivateKey,
</span><span class="boring"> PublicKey, Runtime,
</span><span class="boring">};
</span><span class="boring">
</span><span class="boring">const DATABASE_SIZE: usize = 100;
</span><span class="boring">
</span><span class="boring">#[fhe_program(scheme = &quot;bfv&quot;)]
</span><span class="boring">/// This program takes a user's query and looks up the entry in the database.
</span><span class="boring">/// Queries are arrays containing a single 1 element at the
</span><span class="boring">/// desired item's index and 0s elsewhere.
</span><span class="boring">fn lookup(query: [Cipher&lt;Signed&gt;; DATABASE_SIZE], database: [Signed; DATABASE_SIZE]) -&gt; Cipher&lt;Signed&gt; {
</span><span class="boring"> let mut sum = query[0] * database[0];
</span><span class="boring">
</span><span class="boring"> for i in 1..DATABASE_SIZE {
</span><span class="boring"> sum = sum + query[i] * database[i]
</span><span class="boring"> }
</span><span class="boring">
</span><span class="boring"> sum
</span><span class="boring">}
</span><span class="boring">
</span><span class="boring">/// This is the server that processes Alice's query.
</span><span class="boring">struct Server {
</span><span class="boring"> /// The compiled database lookup program
</span><span class="boring"> pub compiled_lookup: CompiledFheProgram,
</span><span class="boring">
</span><span class="boring"> /// The server's runtime
</span><span class="boring"> runtime: Runtime,
</span><span class="boring">}
</span><span class="boring">
</span>impl Server {
pub fn setup() -&gt; Result&lt;Server, Error&gt; {
let compiled_lookup = Compiler::with_fhe_program(lookup).compile()?;
let runtime = Runtime::new(&amp;compiled_lookup.metadata.params)?;
Ok(Server {
compiled_lookup,
runtime,
})
}
pub fn run_query(
&amp;self,
query: Ciphertext,
public_key: &amp;PublicKey,
) -&gt; Result&lt;Ciphertext, Error&gt; {
// Our database will consist of values between 400 and 500.
let database: [Signed; DATABASE_SIZE] = (400..(400 + DATABASE_SIZE))
.map(|x| Signed::from(x as i64))
.collect::&lt;Vec&lt;Signed&gt;&gt;()
.try_into()
.unwrap();
let args: Vec&lt;FheProgramInput&gt; = vec![query.into(), database.into()];
let results = self.runtime.run(&amp;self.compiled_lookup, args, public_key)?;
Ok(results[0].clone())
}
}
<span class="boring">}
</span></code></pre></pre>
<p>The server constructs a runtime so that it can run the compiled FHE program <code>compiled_lookup</code>.</p>
<p>Using <code>run_query</code>, the server can return an (encrypted) response to Alice's query.</p>
<p>The items in the database will be the integers from 400 to 499, stored in ascending order. Recall that <code>lookup</code> takes in two arguments---the encrypted query and the unencrypted database. Unfortunately, we'll need to do some type conversion for the <code>database</code> as Sunscreen's compiler needs the <code>Signed</code> type <em>not</em> <code>i64</code> for its programs.</p>
<p>Additionally, to <code>run</code> FHE programs, we need to pass in arguments as a <code>vec</code>. Thus, we create a <code>vec</code> called <code>args</code> that contains our encrypted <code>query</code> and unencrypted <code>database</code> (which now has <code>Signed</code> entries rather than <code>i64</code> entries in it). </p>
<p>Once all that's done, the server can <code>run</code> the FHE program by passing in the <code>compiled_lookup</code> program, the arguments to the program <code>args</code> (now contained in a <code>vec</code>), and Alice's <code>public_key</code>. </p>
<h3 id="retrieving-the-item-privately"><a class="header" href="#retrieving-the-item-privately">Retrieving the item privately</a></h3>
<pre><pre class="playground"><code class="language-rust no_run edition2021"><span class="boring">use sunscreen::{
</span><span class="boring"> fhe_program,
</span><span class="boring"> types::{bfv::Signed, Cipher},
</span><span class="boring"> Ciphertext, CompiledFheProgram, Compiler, Error, FheProgramInput, Params, PrivateKey,
</span><span class="boring"> PublicKey, Runtime,
</span><span class="boring">};
</span><span class="boring">
</span><span class="boring">const DATABASE_SIZE: usize = 100;
</span><span class="boring">
</span><span class="boring">#[fhe_program(scheme = &quot;bfv&quot;)]
</span><span class="boring">/// This program takes a user's query and looks up the entry in the database.
</span><span class="boring">/// Queries are arrays containing a single 1 element at the
</span><span class="boring">/// desired item's index and 0s elsewhere.
</span><span class="boring">fn lookup(query: [Cipher&lt;Signed&gt;; DATABASE_SIZE], database: [Signed; DATABASE_SIZE]) -&gt; Cipher&lt;Signed&gt; {
</span><span class="boring"> let mut sum = query[0] * database[0];
</span><span class="boring">
</span><span class="boring"> for i in 1..DATABASE_SIZE {
</span><span class="boring"> sum = sum + query[i] * database[i]
</span><span class="boring"> }
</span><span class="boring">
</span><span class="boring"> sum
</span><span class="boring">}
</span><span class="boring">
</span><span class="boring">/// Alice is a party that wants to look up a value in the database without
</span><span class="boring">/// revealing what she looked up.
</span><span class="boring">struct Alice {
</span><span class="boring"> /// Alice's public key
</span><span class="boring"> pub public_key: PublicKey,
</span><span class="boring">
</span><span class="boring"> /// Alice's private key
</span><span class="boring"> private_key: PrivateKey,
</span><span class="boring">
</span><span class="boring"> /// Alice's runtime
</span><span class="boring"> runtime: Runtime,
</span><span class="boring">}
</span><span class="boring">
</span><span class="boring">impl Alice {
</span><span class="boring"> pub fn setup(params: &amp;Params) -&gt; Result&lt;Alice, Error&gt; {
</span><span class="boring"> let runtime = Runtime::new(params)?;
</span><span class="boring">
</span><span class="boring"> let (public_key, private_key) = runtime.generate_keys()?;
</span><span class="boring">
</span><span class="boring"> Ok(Alice {
</span><span class="boring"> public_key,
</span><span class="boring"> private_key,
</span><span class="boring"> runtime,
</span><span class="boring"> })
</span><span class="boring"> }
</span><span class="boring">
</span><span class="boring"> pub fn create_query(&amp;self, index: usize) -&gt; Result&lt;Ciphertext, Error&gt; {
</span><span class="boring"> let mut query = [Signed::from(0); DATABASE_SIZE];
</span><span class="boring"> query[index] = Signed::from(1);
</span><span class="boring">
</span><span class="boring"> Ok(self.runtime.encrypt(query, &amp;self.public_key)?)
</span><span class="boring"> }
</span><span class="boring">
</span><span class="boring"> pub fn check_response(&amp;self, value: Ciphertext) -&gt; Result&lt;(), Error&gt; {
</span><span class="boring"> let value: Signed = self.runtime.decrypt(&amp;value, &amp;self.private_key)?;
</span><span class="boring">
</span><span class="boring"> let value: i64 = value.into();
</span><span class="boring">
</span><span class="boring"> println!(&quot;Alice received {}&quot;, value);
</span><span class="boring">
</span><span class="boring"> Ok(())
</span><span class="boring"> }
</span><span class="boring">}
</span><span class="boring">
</span><span class="boring">/// This is the server that processes Alice's query.
</span><span class="boring">struct Server {
</span><span class="boring"> /// The compiled database lookup program
</span><span class="boring"> pub compiled_lookup: CompiledFheProgram,
</span><span class="boring">
</span><span class="boring"> /// The server's runtime
</span><span class="boring"> runtime: Runtime,
</span><span class="boring">}
</span><span class="boring">
</span><span class="boring">impl Server {
</span><span class="boring"> pub fn setup() -&gt; Result&lt;Server, Error&gt; {
</span><span class="boring"> let compiled_lookup = Compiler::with_fhe_program(lookup).compile()?;
</span><span class="boring">
</span><span class="boring"> let runtime = Runtime::new(&amp;compiled_lookup.metadata.params)?;
</span><span class="boring">
</span><span class="boring"> Ok(Server {
</span><span class="boring"> compiled_lookup,
</span><span class="boring"> runtime,
</span><span class="boring"> })
</span><span class="boring"> }
</span><span class="boring">
</span><span class="boring"> pub fn run_query(
</span><span class="boring"> &amp;self,
</span><span class="boring"> query: Ciphertext,
</span><span class="boring"> public_key: &amp;PublicKey,
</span><span class="boring"> ) -&gt; Result&lt;Ciphertext, Error&gt; {
</span><span class="boring"> // Our database will consist of values between 400 and 500.
</span><span class="boring"> let database: [Signed; DATABASE_SIZE] = (400..(400 + DATABASE_SIZE))
</span><span class="boring"> .map(|x| Signed::from(x as i64))
</span><span class="boring"> .collect::&lt;Vec&lt;Signed&gt;&gt;()
</span><span class="boring"> .try_into()
</span><span class="boring"> .unwrap();
</span><span class="boring">
</span><span class="boring"> let args: Vec&lt;FheProgramInput&gt; = vec![query.into(), database.into()];
</span><span class="boring">
</span><span class="boring"> let results = self.runtime.run(&amp;self.compiled_lookup, args, public_key)?;
</span><span class="boring">
</span><span class="boring"> Ok(results[0].clone())
</span><span class="boring"> }
</span><span class="boring">}
</span><span class="boring">
</span>fn main() -&gt; Result&lt;(), Error&gt; {
// Set up the database
let server = Server::setup()?;
// Alice sets herself up. The FHE scheme parameters are public to the
// protocol, so Alice has them.
let alice = Alice::setup(&amp;server.compiled_lookup.metadata.params)?;
let query = alice.create_query(94)?;
let response = server.run_query(query, &amp;alice.public_key)?;
alice.check_response(response)?;
Ok(())
}
</code></pre></pre>
<p>We set up the server first and then Alice (notice that Alice relies on parameters generated from the server's setup). Both of them must use the same set of FHE scheme parameters for compatibility. In deployment, these values would likely be fixed at the protocol level.</p>
<p>Alice would like to privately retrieve the item at the 94th position from the database so she calls <code>create_query</code> which encrypts her query value of <code>94</code> (i.e. we get an array that has encryptions of <code>0</code> in all positions except the 94th position which contains an encryption of <code>1</code>).</p>
<p>The server calls <code>run_query</code> to privately retrieve Alice's desired item to her. It passes in Alice's encrypted <code>query</code> along with Alice's public key (<code>alice.public_key</code>).</p>
<p>Finally, Alice can decrypt to check what item she received via <code>check_response</code>.</p>
<h3 id="performance-1"><a class="header" href="#performance-1">Performance</a></h3>
<p>The entire program (not including compilation time) takes ~5 ms on an Intel Xeon @ 3.0 GHz (with 8 cores and 16 GB RAM) and ~42 ms on a Macbook Air M1.</p>
<div style="break-before: page; page-break-before: always;"></div><h1 id="a-better-pir-algorithm"><a class="header" href="#a-better-pir-algorithm">A better PIR algorithm</a></h1>
<p>In the previous PIR algorithm, the user had to send a query vector of the same size as the database itself. Can we do better than that? Yes!</p>
<p>Let's look at how to reduce the user's query size by making use of matrix-vector product <em>and</em> dot prodct.</p>
<h2 id="how-will-our-improved-algorithm-work"><a class="header" href="#how-will-our-improved-algorithm-work">How will our improved algorithm work?</a></h2>
<p>Instead of representing the database as a vector of length n, we'll represent it as a <a href="https://en.wikipedia.org/wiki/Matrix_(mathematics)">matrix</a> of dimension sqrt(n) by sqrt(n). As prior, everything in the database is <em>un</em>encrypted.</p>
<p>Let's say Alice wants to retrieve item<sub>1,2</sub> from the database. This time, Alice will send <em>two</em> query vectors to the server; each query vector is of length sqrt(n) so Alice's communication cost will be reduced from n to 2 · sqrt(n).</p>
<h3 id="information-retrieval-without-privacy-1"><a class="header" href="#information-retrieval-without-privacy-1">Information retrieval (without privacy)</a></h3>
<p>What goes in the query vectors?</p>
<ul>
<li>Query Vector #1: Used in the matrix-vector product. The query vector will have a 0 in every place, except for the column number Alice is interested in. Since Alice wants the 2nd column, the vector takes the following form: [0, 1, 0, ..., 0].</li>
<li>Query Vector #2: Used in the dot product. This query vector will have a 0 in every place, except for the row number Alice is interested in. Since Alice wants the 1st row, the vector takes the following form: [1, 0, ..., 0].</li>
</ul>
<p>When we take the matrix-vector product of the database with query vector #1, we get a vector back. What's in this vector?</p>
<p>[item<sub>1,2</sub>, item<sub>2,2</sub>, item<sub>3,2</sub>, ..., item<sub>sqrt(n),2</sub>]</p>
<p>When we take the dot product of the previous result with query vector #2, we get the item Alice is interested in. Why? Well:</p>
<p>[item<sub>1,2</sub>, item<sub>2,2</sub>, item<sub>3,2</sub>, ..., item<sub>sqrt(n),2</sub>] · [1, 0, ..., 0]<sup>t</sup> = item<sub>1,2</sub></p>
<h3 id="making-the-query-private-1"><a class="header" href="#making-the-query-private-1">Making the query private</a></h3>
<p>Since Alice doesn't want to reveal to the server which item she's interested in, she encrypts her two query vectors with respect to her FHE public key.</p>
<ul>
<li>Query Vector #1: [Enc(0), Enc(1), Enc(0), ..., Enc(0)]</li>
<li>Query Vector #2: [Enc(1), Enc(0), ..., Enc(0)]</li>
</ul>
<p>When the server takes the matrix-vector product of the database with encrypted query vector #1, we get:</p>
<p>[Enc(item<sub>1,2</sub>), Enc(item<sub>2,2</sub>), Enc(item<sub>3,2</sub>), ..., Enc(item<sub>sqrt(n),2</sub>)]</p>
<p>When the server takes the dot product of the above vector with encrypted query vector #2, voila, we get Alice's desired item:</p>
<p>[Enc(item<sub>1,2</sub>), Enc(item<sub>2,2</sub>), Enc(item<sub>3,2</sub>), ..., Enc(item<sub>sqrt(n),2</sub>)] · [Enc(1), Enc(0), ..., Enc(0)]<sup>t</sup> = Enc(item<sub>1,2</sub>)</p>
<h2 id="program-walkthrough-2"><a class="header" href="#program-walkthrough-2">Program walkthrough</a></h2>
<p>Our database will have 100 items in it. We'll use an <a href="fhe_programs/./types/types.html">array</a> to represent our database.</p>
<h3 id="setup-2"><a class="header" href="#setup-2">Setup</a></h3>
<pre><pre class="playground"><code class="language-rust no_run edition2021">
<span class="boring">#![allow(unused)]
</span><span class="boring">fn main() {
</span>use sunscreen::{
fhe_program,
types::{bfv::Signed, Cipher},
};
const SQRT_DATABASE_SIZE: usize = 10;
#[fhe_program(scheme = &quot;bfv&quot;)]
/// This program takes a user's query and looks up the entry in the database.
/// Queries are arrays containing a single 1 element at the
/// desired item's index and 0s elsewhere.
fn lookup(
col_query: [Cipher&lt;Signed&gt;; SQRT_DATABASE_SIZE],
row_query: [Cipher&lt;Signed&gt;; SQRT_DATABASE_SIZE],
database: [[Signed; SQRT_DATABASE_SIZE]; SQRT_DATABASE_SIZE],
) -&gt; Cipher&lt;Signed&gt; {
// Copy col_query just so we get an initialized object of the right
// type in col.
let mut col = [col_query[0]; SQRT_DATABASE_SIZE];
// Perform matrix-vector multiplication with col_query to extract
// Alice's desired column
for i in 0..SQRT_DATABASE_SIZE {
for j in 0..SQRT_DATABASE_SIZE {
if j == 0 {
col[i] = database[i][j] * col_query[j];
} else {
col[i] = col[i] + database[i][j] * col_query[j];
}
}
}
let mut sum = col[0] * row_query[0];
// Dot product the result with the row query to get the result
for i in 1..SQRT_DATABASE_SIZE {
sum = sum + col[i] * row_query[i];
}
sum
}
<span class="boring">}
</span></code></pre></pre>
<p>We begin by importing the stuff we're going to use.</p>
<p>We declare our <code>lookup</code> function as an FHE program with the appropriate attribute <code>(#[fhe_program(scheme = &quot;bfv&quot;)])</code>. </p>
<p>We'll represent our database as an array of length <code>SQRT_DATABASE_SIZE</code> (in this case = 10) with entries that are arrays of length <code>SQRT_DATABASE_SIZE</code> (also = 10). Since we want to write into the database, we'll need to initialize the array in the FHE program's function body.</p>
<p><code>lookup</code> implements the matrix-vector and dot product formulas explained above to retrieve Alice's item privately. It takes in an unencrypted <code>database</code> along with Alice's encrypted query &quot;vectors&quot; (actually arrays). Recall that we have two queries— <code>col_query</code> will be used to select the appropriate column of the database whereas <code>row_query</code> will be used to select the appropriate row of the database. </p>
<h3 id="alice-2"><a class="header" href="#alice-2">Alice</a></h3>
<pre><pre class="playground"><code class="language-rust no_run edition2021">
<span class="boring">#![allow(unused)]
</span><span class="boring">fn main() {
</span><span class="boring">use sunscreen::{
</span><span class="boring"> PrivateKey, PublicKey, Runtime,
</span><span class="boring">};
</span>
/// Alice is a party that wants to look up a value in the database without
/// revealing what she looked up.
struct Alice {
/// Alice's public key
pub public_key: PublicKey,
/// Alice's private key
private_key: PrivateKey,
/// Alice's runtime
runtime: Runtime,
}
<span class="boring">}
</span></code></pre></pre>
<p>Alice wants to retrieve an item from the database privately. She'll need a public/private key pair to do this (since she needs to encrypt her query with respect to her public key).</p>
<pre><pre class="playground"><code class="language-rust no_run edition2021">
<span class="boring">#![allow(unused)]
</span><span class="boring">fn main() {
</span><span class="boring">use sunscreen::{
</span><span class="boring"> fhe_program,
</span><span class="boring"> types::{bfv::Signed, Cipher},
</span><span class="boring"> Ciphertext, CompiledFheProgram, Compiler, Error, FheProgramInput, Params, PrivateKey,
</span><span class="boring"> PublicKey, Runtime,
</span><span class="boring">};
</span><span class="boring">
</span><span class="boring">const SQRT_DATABASE_SIZE: usize = 10;
</span><span class="boring">
</span><span class="boring">/// Alice is a party that wants to look up a value in the database without
</span><span class="boring">/// revealing what she looked up.
</span><span class="boring">struct Alice {
</span><span class="boring"> /// Alice's public key
</span><span class="boring"> pub public_key: PublicKey,
</span><span class="boring">
</span><span class="boring"> /// Alice's private key
</span><span class="boring"> private_key: PrivateKey,
</span><span class="boring">
</span><span class="boring"> /// Alice's runtime
</span><span class="boring"> runtime: Runtime,
</span><span class="boring">}
</span><span class="boring">
</span>impl Alice {
pub fn setup(params: &amp;Params) -&gt; Result&lt;Alice, Error&gt; {
let runtime = Runtime::new(params)?;
let (public_key, private_key) = runtime.generate_keys()?;
Ok(Alice {
public_key,
private_key,
runtime,
})
}
pub fn create_query(&amp;self, index: usize) -&gt; Result&lt;(Ciphertext, Ciphertext), Error&gt; {
let col = index % SQRT_DATABASE_SIZE;
let row = index / SQRT_DATABASE_SIZE;
let mut col_query = [Signed::from(0); SQRT_DATABASE_SIZE];
let mut row_query = [Signed::from(0); SQRT_DATABASE_SIZE];
col_query[col] = Signed::from(1);
row_query[row] = Signed::from(1);
Ok((
self.runtime.encrypt(col_query, &amp;self.public_key)?,
self.runtime.encrypt(row_query, &amp;self.public_key)?,
))
}
pub fn check_response(&amp;self, value: Ciphertext) -&gt; Result&lt;(), Error&gt; {
let value: Signed = self.runtime.decrypt(&amp;value, &amp;self.private_key)?;
let value: i64 = value.into();
println!(&quot;Alice received {}&quot;, value);
Ok(())
}
}
<span class="boring">}
</span></code></pre></pre>
<p>Alice will need to construct a runtime. Once that's done, she can generate her public/private key pair.</p>
<p><code>create_query</code> will allow Alice to create and encrypt her two query &quot;vectors&quot; (i.e. arrays). Alice will pass in an <code>index</code> which contains her desired column and row indices. Notice the 1's place of the <code>index</code> will allow Alice to select her desired column #, whereas the 10's place will allow Alice to select her desired row # (e.g. if <code>index</code> is 85, this denotes Alice is interested in entry located in the 5th column, 8th row). </p>
<p>We won't use this until the very end but <code>check_response</code> allows Alice to decrypt the server's response by passing in the ciphertext she received (<code>value</code>) along with her <code>private_key</code>.</p>
<h3 id="server-1"><a class="header" href="#server-1">Server</a></h3>
<p>Let's look at the server next.</p>
<pre><pre class="playground"><code class="language-rust no_run edition2021">
<span class="boring">#![allow(unused)]
</span><span class="boring">fn main() {
</span><span class="boring">use sunscreen::{
</span><span class="boring"> fhe_program,
</span><span class="boring"> types::{bfv::Signed, Cipher},
</span><span class="boring"> Ciphertext, CompiledFheProgram, Compiler, Error, FheProgramInput, Params, PrivateKey,
</span><span class="boring"> PublicKey, Runtime,
</span><span class="boring">};
</span><span class="boring">
</span>/// This is the server that processes Alice's query.
struct Server {
/// The compiled database query program
pub compiled_lookup: CompiledFheProgram,
/// The server's runtime
runtime: Runtime,
}
<span class="boring">}
</span></code></pre></pre>
<p>Recall that the server is responsible for retrieving Alice's item from the database; thus, it will have to run the compiled lookup program (<code>compiled_lookup</code>).</p>
<pre><pre class="playground"><code class="language-rust no_run edition2021">
<span class="boring">#![allow(unused)]
</span><span class="boring">fn main() {
</span><span class="boring">use sunscreen::{
</span><span class="boring"> fhe_program,
</span><span class="boring"> types::{bfv::Signed, Cipher},
</span><span class="boring"> Ciphertext, CompiledFheProgram, Compiler, Error, FheProgramInput, Params, PrivateKey,
</span><span class="boring"> PublicKey, Runtime,
</span><span class="boring">};
</span><span class="boring">
</span><span class="boring">#[fhe_program(scheme = &quot;bfv&quot;)]
</span><span class="boring">/// This program takes a user's query and looks up the entry in the database.
</span><span class="boring">/// Queries are arrays containing a single 1 element at the
</span><span class="boring">/// desired item's index and 0s elsewhere.
</span><span class="boring">fn lookup(
</span><span class="boring"> col_query: [Cipher&lt;Signed&gt;; SQRT_DATABASE_SIZE],
</span><span class="boring"> row_query: [Cipher&lt;Signed&gt;; SQRT_DATABASE_SIZE],
</span><span class="boring"> database: [[Signed; SQRT_DATABASE_SIZE]; SQRT_DATABASE_SIZE],
</span><span class="boring">) -&gt; Cipher&lt;Signed&gt; {
</span><span class="boring"> // Copy col_query just so we get an initialized object of the right
</span><span class="boring"> // type in col.
</span><span class="boring"> let mut col = [col_query[0]; SQRT_DATABASE_SIZE];
</span><span class="boring">
</span><span class="boring"> // Perform matrix-vector multiplication with col_query to extract
</span><span class="boring"> // Alice's desired column
</span><span class="boring"> for i in 0..SQRT_DATABASE_SIZE {
</span><span class="boring"> for j in 0..SQRT_DATABASE_SIZE {
</span><span class="boring"> if j == 0 {
</span><span class="boring"> col[i] = database[i][j] * col_query[j];
</span><span class="boring"> } else {
</span><span class="boring"> col[i] = col[i] + database[i][j] * col_query[j];
</span><span class="boring"> }
</span><span class="boring"> }
</span><span class="boring"> }
</span><span class="boring">
</span><span class="boring"> let mut sum = col[0] * row_query[0];
</span><span class="boring">
</span><span class="boring"> // Dot product the result with the row query to get the result
</span><span class="boring"> for i in 1..SQRT_DATABASE_SIZE {
</span><span class="boring"> sum = sum + col[i] * row_query[i];
</span><span class="boring"> }
</span><span class="boring">
</span><span class="boring"> sum
</span><span class="boring">}
</span><span class="boring">
</span><span class="boring">const SQRT_DATABASE_SIZE: usize = 10;
</span><span class="boring">
</span><span class="boring">/// This is the server that processes Alice's query.
</span><span class="boring">struct Server {
</span><span class="boring"> /// The compiled database query program
</span><span class="boring"> pub compiled_lookup: CompiledFheProgram,
</span><span class="boring">
</span><span class="boring"> /// The server's runtime
</span><span class="boring"> runtime: Runtime,
</span><span class="boring">}
</span><span class="boring">
</span>impl Server {
pub fn setup() -&gt; Result&lt;Server, Error&gt; {
let compiled_lookup = Compiler::with_fhe_program(lookup).compile()?;
let runtime = Runtime::new(&amp;compiled_lookup.metadata.params)?;
Ok(Server {
compiled_lookup,
runtime,
})
}
pub fn run_query(
&amp;self,
col_query: Ciphertext,
row_query: Ciphertext,
public_key: &amp;PublicKey,
) -&gt; Result&lt;Ciphertext, Error&gt; {
// Our database will consist of values between 400 and 500.
let mut database = [[Signed::from(0); SQRT_DATABASE_SIZE]; SQRT_DATABASE_SIZE];
let mut val = Signed::from(400);
for i in 0..SQRT_DATABASE_SIZE {
for j in 0..SQRT_DATABASE_SIZE {
database[i][j] = val;
val = val + 1;
}
}
let args: Vec&lt;FheProgramInput&gt; = vec![col_query.into(), row_query.into(), database.into()];
let results = self.runtime.run(&amp;self.compiled_lookup, args, public_key)?;
Ok(results[0].clone())
}
}
<span class="boring">}
</span></code></pre></pre>
<p>The server constructs a runtime so that it can run the compiled FHE program <code>compiled_lookup</code>.</p>
<p>Using <code>run_query</code>, the server can return an (encrypted) response to Alice's query.</p>
<p>The items in the database will be the integers from 400 to 499, stored in ascending order. Recall that <code>lookup</code> takes in three arguments---the encrypted query for the column index (<code>col_query</code>), the encrypted query for the row index (<code>row_query</code>), and the unencrypted database. Unfortunately, we'll need to do some type conversion for the database as Sunscreen's compiler needs entries of the <code>Signed</code> type not <code>i64</code> for its programs.</p>
<p>Additionally, to run FHE programs, we need to pass in arguments as a <code>vec</code>. Thus, we create a <code>vec</code> called <code>args</code> that contains our encrypted queries and unencrypted database (which now has <code>Signed</code> entries rather than <code>i64</code> entries in it).</p>
<p>Once all that's done, the server can <code>run</code> the FHE program by passing in the <code>compiled_lookup</code> program, the arguments to the program <code>args</code> (now contained in a <code>vec</code>), and Alice's <code>public_key</code>.</p>
<h3 id="retrieving-the-item-privately-1"><a class="header" href="#retrieving-the-item-privately-1">Retrieving the item privately</a></h3>
<pre><pre class="playground"><code class="language-rust no_run edition2021"><span class="boring">use sunscreen::{
</span><span class="boring"> fhe_program,
</span><span class="boring"> types::{bfv::Signed, Cipher},
</span><span class="boring"> Ciphertext, CompiledFheProgram, Compiler, Error, FheProgramInput, Params, PrivateKey,
</span><span class="boring"> PublicKey, Runtime,
</span><span class="boring">};
</span><span class="boring">
</span><span class="boring">const SQRT_DATABASE_SIZE: usize = 10;
</span><span class="boring">
</span><span class="boring">#[fhe_program(scheme = &quot;bfv&quot;)]
</span><span class="boring">/// This program takes a user's query and looks up the entry in the database.
</span><span class="boring">/// Queries are arrays containing a single 1 element at the
</span><span class="boring">/// desired item's index and 0s elsewhere.
</span><span class="boring">fn lookup(
</span><span class="boring"> col_query: [Cipher&lt;Signed&gt;; SQRT_DATABASE_SIZE],
</span><span class="boring"> row_query: [Cipher&lt;Signed&gt;; SQRT_DATABASE_SIZE],
</span><span class="boring"> database: [[Signed; SQRT_DATABASE_SIZE]; SQRT_DATABASE_SIZE],
</span><span class="boring">) -&gt; Cipher&lt;Signed&gt; {
</span><span class="boring"> // Copy col_query just so we get an initialized object of the right
</span><span class="boring"> // type in col.
</span><span class="boring"> let mut col = [col_query[0]; SQRT_DATABASE_SIZE];
</span><span class="boring">
</span><span class="boring"> // Perform matrix-vector multiplication with col_query to extract
</span><span class="boring"> // Alice's desired column
</span><span class="boring"> for i in 0..SQRT_DATABASE_SIZE {
</span><span class="boring"> for j in 0..SQRT_DATABASE_SIZE {
</span><span class="boring"> if j == 0 {
</span><span class="boring"> col[i] = database[i][j] * col_query[j];
</span><span class="boring"> } else {
</span><span class="boring"> col[i] = col[i] + database[i][j] * col_query[j];
</span><span class="boring"> }
</span><span class="boring"> }
</span><span class="boring"> }
</span><span class="boring">
</span><span class="boring"> let mut sum = col[0] * row_query[0];
</span><span class="boring">
</span><span class="boring"> // Dot product the result with the row query to get the result
</span><span class="boring"> for i in 1..SQRT_DATABASE_SIZE {
</span><span class="boring"> sum = sum + col[i] * row_query[i];
</span><span class="boring"> }
</span><span class="boring">
</span><span class="boring"> sum
</span><span class="boring">}
</span><span class="boring">
</span><span class="boring">/// Alice is a party that wants to look up a value in the database without
</span><span class="boring">/// revealing what she looked up.
</span><span class="boring">struct Alice {
</span><span class="boring"> /// Alice's public key
</span><span class="boring"> pub public_key: PublicKey,
</span><span class="boring">
</span><span class="boring"> /// Alice's private key
</span><span class="boring"> private_key: PrivateKey,
</span><span class="boring">
</span><span class="boring"> /// Alice's runtime
</span><span class="boring"> runtime: Runtime,
</span><span class="boring">}
</span><span class="boring">
</span><span class="boring">impl Alice {
</span><span class="boring"> pub fn setup(params: &amp;Params) -&gt; Result&lt;Alice, Error&gt; {
</span><span class="boring"> let runtime = Runtime::new(params)?;
</span><span class="boring">
</span><span class="boring"> let (public_key, private_key) = runtime.generate_keys()?;
</span><span class="boring">
</span><span class="boring"> Ok(Alice {
</span><span class="boring"> public_key,
</span><span class="boring"> private_key,
</span><span class="boring"> runtime,
</span><span class="boring"> })
</span><span class="boring"> }
</span><span class="boring">
</span><span class="boring"> pub fn create_query(&amp;self, index: usize) -&gt; Result&lt;(Ciphertext, Ciphertext), Error&gt; {
</span><span class="boring"> let col = index % SQRT_DATABASE_SIZE;
</span><span class="boring"> let row = index / SQRT_DATABASE_SIZE;
</span><span class="boring">
</span><span class="boring"> let mut col_query = [Signed::from(0); SQRT_DATABASE_SIZE];
</span><span class="boring"> let mut row_query = [Signed::from(0); SQRT_DATABASE_SIZE];
</span><span class="boring"> col_query[col] = Signed::from(1);
</span><span class="boring"> row_query[row] = Signed::from(1);
</span><span class="boring">
</span><span class="boring"> Ok((
</span><span class="boring"> self.runtime.encrypt(col_query, &amp;self.public_key)?,
</span><span class="boring"> self.runtime.encrypt(row_query, &amp;self.public_key)?,
</span><span class="boring"> ))
</span><span class="boring"> }
</span><span class="boring">
</span><span class="boring"> pub fn check_response(&amp;self, value: Ciphertext) -&gt; Result&lt;(), Error&gt; {
</span><span class="boring"> let value: Signed = self.runtime.decrypt(&amp;value, &amp;self.private_key)?;
</span><span class="boring">
</span><span class="boring"> let value: i64 = value.into();
</span><span class="boring">
</span><span class="boring"> println!(&quot;Alice received {}&quot;, value);
</span><span class="boring">
</span><span class="boring"> Ok(())
</span><span class="boring"> }
</span><span class="boring">}
</span><span class="boring">
</span><span class="boring">/// This is the server that processes Alice's query.
</span><span class="boring">struct Server {
</span><span class="boring"> /// The compiled database query program
</span><span class="boring"> pub compiled_lookup: CompiledFheProgram,
</span><span class="boring">
</span><span class="boring"> /// The server's runtime
</span><span class="boring"> runtime: Runtime,
</span><span class="boring">}
</span><span class="boring">
</span><span class="boring">impl Server {
</span><span class="boring"> pub fn setup() -&gt; Result&lt;Server, Error&gt; {
</span><span class="boring"> let compiled_lookup = Compiler::with_fhe_program(lookup).compile()?;
</span><span class="boring">
</span><span class="boring"> let runtime = Runtime::new(&amp;compiled_lookup.metadata.params)?;
</span><span class="boring">
</span><span class="boring"> Ok(Server {
</span><span class="boring"> compiled_lookup,
</span><span class="boring"> runtime,
</span><span class="boring"> })
</span><span class="boring"> }
</span><span class="boring">
</span><span class="boring"> pub fn run_query(
</span><span class="boring"> &amp;self,
</span><span class="boring"> col_query: Ciphertext,
</span><span class="boring"> row_query: Ciphertext,
</span><span class="boring"> public_key: &amp;PublicKey,
</span><span class="boring"> ) -&gt; Result&lt;Ciphertext, Error&gt; {
</span><span class="boring"> // Our database will consist of values between 400 and 500.
</span><span class="boring"> let mut database = [[Signed::from(0); SQRT_DATABASE_SIZE]; SQRT_DATABASE_SIZE];
</span><span class="boring"> let mut val = Signed::from(400);
</span><span class="boring">
</span><span class="boring"> for i in 0..SQRT_DATABASE_SIZE {
</span><span class="boring"> for j in 0..SQRT_DATABASE_SIZE {
</span><span class="boring"> database[i][j] = val;
</span><span class="boring"> val = val + 1;
</span><span class="boring"> }
</span><span class="boring"> }
</span><span class="boring">
</span><span class="boring"> let args: Vec&lt;FheProgramInput&gt; = vec![col_query.into(), row_query.into(), database.into()];
</span><span class="boring">
</span><span class="boring"> let results = self.runtime.run(&amp;self.compiled_lookup, args, public_key)?;
</span><span class="boring">
</span><span class="boring"> Ok(results[0].clone())
</span><span class="boring"> }
</span><span class="boring">}
</span>fn main() -&gt; Result&lt;(), Error&gt; {
// Set up the database
let server = Server::setup()?;
// Alice sets herself up. The FHE scheme parameters are public to the
// protocol, so Alice has them.
let alice = Alice::setup(&amp;server.compiled_lookup.metadata.params)?;
let (col_query, row_query) = alice.create_query(94)?;
let response = server.run_query(col_query, row_query, &amp;alice.public_key)?;
alice.check_response(response)?;
Ok(())
}
</code></pre></pre>
<p>We set up the server first and then Alice (notice that Alice relies on parameters generated from the server's setup). Both of them must use the same set of FHE scheme parameters for compatibility. In deployment, these values would likely be fixed at the protocol level.</p>
<p>Alice would like to privately retrieve the item at the 94th &quot;position&quot; (this will mean the entry located in the 4th row, 9th column) from the database so she calls <code>create_query</code>. <code>create_query</code> encrypts her query value of 94 properly (i.e. creates <code>col_query</code> and <code>row_query</code> which has encryptions of 0s and 1s in the appropriate places).</p>
<p>The server calls <code>run_query</code> to privately retrieve Alice's desired item to her. It passes in Alice's encrypted queries along with Alice's public key (<code>alice.public_key</code>).</p>
<p>Finally, Alice can decrypt to check what item she received via <code>check_response</code>.</p>
<h3 id="performance-2"><a class="header" href="#performance-2">Performance</a></h3>
<p>The entire program (not including compilation time) takes ~376 ms on an Intel Xeon @ 3.0 GHz (with 8 cores and 16 GB RAM) and ~716 ms on a Macbook Air M1.</p>
<h1 id="whats-missing-1"><a class="header" href="#whats-missing-1">What's missing?</a></h1>
<p>If you're interested in using PIR in a real application, there are much better PIR algorithms out there (e.g. <a href="https://eprint.iacr.org/2017/1142.pdf">SealPIR</a>, <a href="https://eprint.iacr.org/2022/368.pdf">Spiral</a>) that are faster and compress the query vector further. </p>
<p>Additionally, in PIR, we assume that the user knows the index of the item she wants to retrieve. For many applications though, this might not be the case. <a href="https://eprint.iacr.org/2021/1256.pdf">Oblivious message detection</a> allows the user to detect <em>which</em> item she's interested in and can be combined with PIR.</p>
<div style="break-before: page; page-break-before: always;"></div><h1 id="faq"><a class="header" href="#faq">FAQ</a></h1>
<h3 id="ive-worked-with-fhe-libraries-before-what-does-your-compiler-actually-do"><a class="header" href="#ive-worked-with-fhe-libraries-before-what-does-your-compiler-actually-do">I've worked with FHE libraries before. What does your compiler actually <em>do</em>?</a></h3>
<p>A challenge in working with the BFV scheme is having to set polynomial modulus degree, coefficient modulus, as well as the plaintext modulus for your specific application to ensure good performance. Additionally, bootstrapping is not supported so you need to be careful in choosing the correct parameters for your application so that you don't run out of noise budget before you finish your computation. Our compiler chooses the best polynomial modulus degree and coefficient modulus for your particular program, ensuring you’ll have enough noise budget to perform the entire computation. We do not yet choose the best plaintext modulus for your specific program (this will likely be implemented in the next release). Right now, we simply hard code a value for the plaintext modulus that works for almost any computation you'd likely do. Advanced users can go in and <a href="advanced/./plain_modulus/plain_modulus.html">change this value</a> manually if they'd like though.</p>
<p>You’ll also notice there’s no encoding process to do before encryption (we’ve abstracted that away). You also don’t have to worry about inserting relinearizations in manually (done for ciphertext maintenance purposes).</p>
<h3 id="can-i-perform-computations-on-private-data-belonging-to-different-parties"><a class="header" href="#can-i-perform-computations-on-private-data-belonging-to-different-parties">Can I perform computations on private data belonging to <em>different</em> parties?</a></h3>
<p>Our compiler currently only supports a single-key FHE scheme, meaning that all data needs to be encrypted with respect to the same key if you want to perform computations on it. There <em>are</em> certainly <a href="https://eprint.iacr.org/2021/133">ways</a> to get around the single key limitation to enable computation on private data belonging to different parties. However, it's highly application dependent and often requires the use of additional tools (e.g. zero-knowledge proofs).</p>
<p>There are also variants of FHE—multi-party FHE and multi-key FHE— that support computation on private data belonging to different parties out of the box.</p>
<h3 id="what-are-your-future-plans"><a class="header" href="#what-are-your-future-plans">What are your future plans?</a></h3>
<p>In terms of plans for our compiler specifically, we'd like to add support for:</p>
<ul>
<li>batching</li>
<li>choosing scheme parameters based on multiple FHE programs as inputs</li>
<li>using the outputs of one FHE program as the inputs to another FHE program</li>
</ul>
<p>In terms of broader plans for Sunscreen, some of our next milestones include:</p>
<ul>
<li>helping users manage large FHE ciphertexts</li>
<li>providing a complementary zero-knowledge proof library for our FHE compiler </li>
</ul>
<div style="break-before: page; page-break-before: always;"></div><h1 id="advanced"><a class="header" href="#advanced">Advanced</a></h1>
<p>Now that you've gotten the basics down, let's dive into some more complex topics.</p>
<div style="break-before: page; page-break-before: always;"></div><h1 id="bfv-scheme"><a class="header" href="#bfv-scheme">BFV scheme</a></h1>
<p>There are many different FHE schemes out there. Our compiler uses the <a href="http://homomorphicencryption.org/wp-content/uploads/2018/11/HomomorphicEncryptionStandardv1.1.pdf">BFV scheme</a>.</p>
<h3 id="why-did-we-choose-the-bfv-scheme"><a class="header" href="#why-did-we-choose-the-bfv-scheme">Why did we choose the BFV scheme?</a></h3>
<p>The BFV scheme provides the following nice features:</p>
<ul>
<li>Exact integer arithmetic (it may surprise you but some FHE schemes can't support exact integer arithmetic)</li>
<li>&quot;Fast&quot; integer arithmetic<sup class="footnote-reference"><a href="#1">1</a></sup></li>
<li>&quot;Small&quot; public key sizes<sup class="footnote-reference"><a href="#1">1</a></sup></li>
<li>Potential for &quot;batching&quot; (aka &quot;SIMD&quot;-like) operation for improved performance</li>
<li>Compatibility with fairly efficient <a href="https://www.wired.com/story/zero-knowledge-proofs/">zero-knowledge proof</a> systems</li>
</ul>
<div class="footnote-definition" id="1"><sup class="footnote-definition-label">1</sup>
<p>in comparison to other FHE schemes (e.g. TFHE)</p>
</div>
<h3 id="what-are-some-of-the-drawbacks-to-the-bfv-scheme"><a class="header" href="#what-are-some-of-the-drawbacks-to-the-bfv-scheme">What are some of the drawbacks to the BFV scheme?</a></h3>
<p>No FHE scheme is perfect. Some drawbacks to working with BFV include:</p>
<ul>
<li>Certain operations are difficult (i.e. more expensive) to perform. This notably includes comparisons of two private values.</li>
<li>You can't perform private computations <em>indefinitely</em> on data. What that means for you is that you'll need to choose an upper bound (ahead of time) for how many private computations you'd like to perform. There is an advanced technique called bootstrapping to get around this issue but we do not currently support it.</li>
</ul>
<div style="break-before: page; page-break-before: always;"></div><h1 id="writing-even-better-fhe-programs"><a class="header" href="#writing-even-better-fhe-programs">Writing even better FHE programs</a></h1>
<p>In this section, we're going to cover a few techniques to get the most out of your FHE applications. </p>
<p>Specifically, we'll look at:</p>
<ul>
<li>Manually changing the plaintext modulus to better suit your data and computation</li>
<li>Manually changing the noise margin to allow for more efficient computations</li>
<li>Manually pruning unused public keys for space savings</li>
</ul>
<div style="break-before: page; page-break-before: always;"></div><h1 id="plaintext-modulus"><a class="header" href="#plaintext-modulus">Plaintext modulus</a></h1>
<p>FHE uses some <a href="advanced/plain_modulus//intro/why.html">funky math</a>. At the lowest level, plaintexts are polynomials where the coefficient of each term is an integer modulo the <em>plaintext modulus</em>. The plaintext modulus parameter impacts <a href="advanced/plain_modulus//advanced/carryless_arithmetic.html#overflow">correctness</a> and performance — overflow occurs when the plaintext modulus is too small, but increasing it can negatively impact performance. Sunscreen balances these two considerations by setting a default plaintext modulus that prevents overflow in most applications while maintaining good performance.<sup class="footnote-reference"><a href="#1">1</a></sup> However, you may at times wish to change it.</p>
<div class="footnote-definition" id="1"><sup class="footnote-definition-label">1</sup>
<p>The default is <code>64^3 = 262,144</code>, which allows multiplying any 4 canonical (i.e. all 1s and 0s) 64-bit input values without overflow.</p>
</div>
<h2 id="why-you-might-want-to-change-the-default-plaintext-modulus"><a class="header" href="#why-you-might-want-to-change-the-default-plaintext-modulus">Why you might want to change the default plaintext modulus</a></h2>
<p>A few reasons you would change the plain modulus include:</p>
<ul>
<li>If the default is too conservative, decreasing the plaintext modulus can improve performance.</li>
<li>Very very rarely, the default can cause overflow in some FHE programs. Increasing the plaintext modulus solves this issue at the expense of performance.</li>
<li>You wish to use <a href="advanced/plain_modulus//advanced/batching/batching.html">batching</a>, which requires very specific values.</li>
</ul>
<p>When setting the plaintext modulus, you call <code>compiler.plain_modulus_constraint()</code> and pass a <code>PlainModulusConstraint</code>, which comes in two forms:</p>
<ul>
<li><code>Raw(x)</code> sets the plaintext modulus to <code>x</code>.</li>
<li><code>BatchingMinimum(x)</code> chooses a value suitable for use with batching with at least <code>x</code> bits of precision. As noted in the name, this modulus should be used with batching.</li>
</ul>
<h2 id="how-to-change-the-plaintext-modulus"><a class="header" href="#how-to-change-the-plaintext-modulus">How to change the plaintext modulus</a></h2>
<p>You can manually set the <code>PlainModulusConstraint</code> when compiling your program like so:</p>
<pre><pre class="playground"><code class="language-rust no_run edition2021"><span class="boring">use sunscreen::{
</span><span class="boring"> fhe_program,
</span><span class="boring"> types::{bfv::Signed, Cipher},
</span><span class="boring"> Compiler, Runtime, PublicKey, PlainModulusConstraint
</span><span class="boring">};
</span><span class="boring">
</span><span class="boring">#[fhe_program(scheme = &quot;bfv&quot;)]
</span><span class="boring">fn my_program() {
</span><span class="boring">}
</span><span class="boring">
</span><span class="boring">fn main() {
</span> let fhe_program = Compiler::with_fhe_program(my_program)
.plain_modulus_constraint(PlainModulusConstraint::Raw(1_000_000))
.compile()
.unwrap();
<span class="boring">}
</span></code></pre></pre>
<div style="break-before: page; page-break-before: always;"></div><h1 id="noise"><a class="header" href="#noise">Noise</a></h1>
<p>Every FHE operation introduces <em>noise</em> into ciphertexts.<sup class="footnote-reference"><a href="#1">1</a></sup> If too much noise accrues, then the message becomes garbled and cannot be decrypted. The total amount of allowed noise before this problem occurs is referred to as the <em>noise budget</em>.</p>
<p>Fortunately, our compiler handles this noise issue for you. It uses a value known as the <code>noise_margin</code> that influences how conservative it needs to be in parameter selection. So long as <code>noise_budget &gt;= noise_margin</code>, we're good to go. Sunscreen's default noise margin prevents garbled ciphertexts coming from a <em>single</em> FHE program.</p>
<div class="footnote-definition" id="1"><sup class="footnote-definition-label">1</sup>
<p>Multiplying ciphertexts is one of the largest contributors to noise growth.</p>
</div>
<h2 id="why-you-might-want-to-change-the-default-noise-margin"><a class="header" href="#why-you-might-want-to-change-the-default-noise-margin">Why you might want to change the default noise margin</a></h2>
<p>There are a few reasons you may wish to change the noise margin:</p>
<ul>
<li>If you wish to use an output of one FHE program as an input to another FHE program, you need to allow for additional noise growth in subsequent programs. See our <a href="https://github.com/Sunscreen-tech/Sunscreen/blob/main/examples/calculator_rational/src/main.rs#L221">calculator</a> for a complete example of this scenario.</li>
<li>Decreasing the noise margin can result in improved performance if your application can tolerate a higher rate of faults.</li>
</ul>
<h2 id="how-to-change-the-noise-margin"><a class="header" href="#how-to-change-the-noise-margin">How to change the noise margin</a></h2>
<p>To change the noise margin, simply call <code>.additional_noise_budget()</code> when compiling your program. For example:</p>
<pre><pre class="playground"><code class="language-rust no_run edition2021"><span class="boring">use sunscreen::{
</span><span class="boring"> fhe_program,
</span><span class="boring"> types::{bfv::Signed, Cipher},
</span><span class="boring"> Compiler, Runtime, PublicKey
</span><span class="boring">};
</span><span class="boring">
</span><span class="boring">#[fhe_program(scheme = &quot;bfv&quot;)]
</span><span class="boring">fn my_program() {
</span><span class="boring">}
</span><span class="boring">
</span><span class="boring">fn main() {
</span> let fhe_program = Compiler::with_fhe_program(my_program)
.additional_noise_budget(60)
.compile()
.unwrap();
<span class="boring">}
</span></code></pre></pre>
<div style="break-before: page; page-break-before: always;"></div><h1 id="pruning-public-keys"><a class="header" href="#pruning-public-keys">Pruning public keys</a></h1>
<p>For convenience, the <code>generate_keys</code> function creates several keys in the returned <code>PublicKey</code> object. </p>
<h2 id="why-you-might-want-to-prune-publickey"><a class="header" href="#why-you-might-want-to-prune-publickey">Why you might want to prune <code>PublicKey</code></a></h2>
<p>Some of these keys can be fairly large, the size of which is determined by scheme parameters. However, they may or may not be needed in your application:</p>
<ul>
<li>Galois keys (<code>galois_key</code>) are needed to run FHE programs that perform batching rotations or row swapping.</li>
<li>Relinearization keys (<code>relin_key</code>) are needed to run FHE programs that multiply ciphertexts.</li>
</ul>
<h2 id="how-to-prune-publickey"><a class="header" href="#how-to-prune-publickey">How to prune <code>PublicKey</code></a></h2>
<p>You can <code>compile()</code> an FHE program and look at <code>fhe_program.metadata.required_keys</code> to get a list of required keys for your specific program.</p>
<p>You can then remove unneeded keys. For example:</p>
<pre><pre class="playground"><code class="language-rust no_run edition2021"><span class="boring">use sunscreen::{
</span><span class="boring"> fhe_program,
</span><span class="boring"> types::{bfv::Signed, Cipher},
</span><span class="boring"> Compiler, Runtime, PublicKey
</span><span class="boring">};
</span><span class="boring">
</span><span class="boring">#[fhe_program(scheme = &quot;bfv&quot;)]
</span><span class="boring">fn noop() {
</span><span class="boring">}
</span><span class="boring">
</span><span class="boring">fn main() {
</span><span class="boring"> let fhe_program = Compiler::with_fhe_program(noop)
</span><span class="boring"> .compile()
</span><span class="boring"> .unwrap();
</span><span class="boring">
</span><span class="boring"> let runtime = Runtime::new(&amp;fhe_program.metadata.params).unwrap();
</span>let (public_key, private_key) = runtime.generate_keys().unwrap();
// Shadow and overwrite the public_key, removing the galois_key and relin_key
let public_key = PublicKey {
galois_key: None, // only do this if not using batching
relin_key: None, // only do this if your FHE program never multiplies ciphertexts
..public_key
};
<span class="boring">}
</span></code></pre></pre>
<div style="break-before: page; page-break-before: always;"></div><h1 id="wasm-support"><a class="header" href="#wasm-support">WASM support</a></h1>
<p>Need to run Sunscreen in your browser or NodeJS app? Simply build your app targeting WebAssembly (WASM).</p>
<p>WASM is an instruction set for a sandboxed virtual machine that allows you to safely run Rust and C++ code in your browser more efficiently than Javascript. This includes your Sunscreen app!</p>
<p>Rust features multiple targets for building WASM binaries, but Sunscreen currently only supports <code>wasm32-unknown-emscripten</code>. As the target's name suggests, this leverages <a href="https://emscripten.org/">emscripten</a>, which SEAL needs during compilation and runtime.</p>
<h2 id="setup-3"><a class="header" href="#setup-3">Setup</a></h2>
<h3 id="install-emscripten"><a class="header" href="#install-emscripten">Install emscripten</a></h3>
<pre><code class="language-sh">git clone https://github.com/emscripten-core/emsdk.git
emsdk/emsdk install 3.1.3
emsdk/emsdk activate
</code></pre>
<p>You can try installing other toolchain versions if you wish, but we've seen the compiler seg fault and other strange errors when building our examples 🙃.</p>
<h3 id="load-the-emscripten-environment"><a class="header" href="#load-the-emscripten-environment">Load the emscripten environment</a></h3>
<pre><code class="language-sh">source emsdk/emsdk_env.sh
</code></pre>
<p>Put this command in your shell's .rc file so you don't need to rerun it each time you launch a shell.</p>
<h3 id="add-the-wasm32-unknown-emscripten-target-to-rust"><a class="header" href="#add-the-wasm32-unknown-emscripten-target-to-rust">Add the <code>wasm32-unknown-emscripten</code> target to Rust</a></h3>
<pre><code class="language-sh">rustup target add wasm32-unknown-emscripten
</code></pre>
<h2 id="building"><a class="header" href="#building">Building</a></h2>
<p>To compile your program with Rust+emscripten, you'll need to do a few extra things.</p>
<h3 id="required-emscripten-features"><a class="header" href="#required-emscripten-features">Required emscripten features</a></h3>
<p>Add the following lines to your <code>.cargo/config.toml</code><sup class="footnote-reference"><a href="#1">1</a></sup>:</p>
<pre><code class="language-toml">[env]
EMCC_CFLAGS = &quot;-sERROR_ON_UNDEFINED_SYMBOLS=0 -sDISABLE_EXCEPTION_CATCHING=0 -sALLOW_MEMORY_GROWTH&quot;
</code></pre>
<p><code>ERROR_ON_UNDEFINED_SYMBOLS=0</code> works around a <a href="https://github.com/rust-lang/rust/pull/95950">known issue</a> when Rust's panic handling is set to <code>unwind</code> (the default). Alternatively, you can <a href="https://doc.rust-lang.org/rustc/codegen-options/index.html#panic">set the handling mode to <code>abort</code></a> when building for WASM.</p>
<p><code>DISABLE_EXCEPTION_CATCHING=0</code> allows C++ code to catch exceptions. Without this, you'll get an error complaining that Rust can't catch foreign exceptions and your application will terminate via <code>abort()</code>.</p>
<p>Finally, <code>ALLOW_MEMORY_GROWTH</code> allows the heap to resize. Without this, your app will quickly run out of memory and seg fault.</p>
<div class="footnote-definition" id="1"><sup class="footnote-definition-label">1</sup>
<p>This is <em>not</em> your <code>Cargo.toml</code> file! Put the <code>.cargo</code> directory at the root of your git repository and commit it.</p>
</div>
<h2 id="building-your-app"><a class="header" href="#building-your-app">Building your app</a></h2>
<p>Simply run:</p>
<pre><code class="language-sh">cargo build --bin myapp --release --target wasm32-unknown-emscripten
</code></pre>
<p>where <code>myapp</code> is the name of your executable.</p>
<p>On success, you should see the following files:</p>
<pre><code class="language-ignore">target/wasm32-unknown-emscripten/release/myapp.js
target/wasm32-unknown-emscripten/release/myapp.wasm
</code></pre>
<h3 id="running-with-node"><a class="header" href="#running-with-node">Running with node</a></h3>
<pre><code class="language-sh">node target/wasm32-unknown-emscripten/release/myapp.js
</code></pre>
<h3 id="running-in-browser"><a class="header" href="#running-in-browser">Running in browser</a></h3>
<p>Put <code>myapp.js</code> in a script tag in an <code>index.html</code> file:</p>
<pre><code class="language-html">&lt;!DOCTYPE html&gt;
&lt;html&gt;
&lt;head&gt;
&lt;script src=&quot;myapp.js&quot;&gt;&lt;/script&gt;
&lt;/head&gt;
&lt;body&gt;&lt;/body&gt;
&lt;/html&gt;
</code></pre>
<p>and serve the <code>index.html</code>, <code>myapp.js</code>, and <code>myapp.wasm</code> files on a web server. Your app will run when the user loads the page in their browser.</p>
<p>Alternatively, you can bundle your <code>.js</code> and <code>.wasm</code> into a larger application with <code>webpack</code>.</p>
<h3 id="running-with-wasmerwasmtime"><a class="header" href="#running-with-wasmerwasmtime">Running with wasmer/wasmtime</a></h3>
<p>Unfortunately, these scenarios are currently unsupported 😞.</p>
<h2 id="running-tests"><a class="header" href="#running-tests">Running tests</a></h2>
<p>Build your tests with:</p>
<pre><code class="language-sh">cargo test --no-run --release --target wasm32-unknown-emscripten
</code></pre>
<p>You'll find your tests' entry points in <code>target/wasm32-unknown-emscripten/release/deps/*.js</code>. Simply select the desired test and run:</p>
<pre><code class="language-sh">node target/wasm32-unknown-emscripten/release/mytest-xxxx.js
</code></pre>
<h2 id="debugging"><a class="header" href="#debugging">Debugging</a></h2>
<p>Debugging WASM is challenging. If possible, you should debug issues running your app natively. For debugging WASM-specific issues, emscripten can emit both DWARF symbols and traditional source maps. While DWARF symbols are more useful, browser support at this stage is terrible.</p>
<h3 id="build-in-debug-mode"><a class="header" href="#build-in-debug-mode">Build in debug mode</a></h3>
<p>To use source maps, simply build in debug mode<sup class="footnote-reference"><a href="#2">2</a></sup>:</p>
<pre><code class="language-sh">cargo build --bin myapp --target wasm32-unknown-emscripten
</code></pre>
<p>where <code>myapp</code> is the name of your executable.</p>
<div class="footnote-definition" id="2"><sup class="footnote-definition-label">2</sup>
<p>You may wish to add <code>-O3</code> to <code>EMCC_CFLAGS</code> to speed up your app.</p>
</div>
<h3 id="make-a-webpage"><a class="header" href="#make-a-webpage">Make a webpage</a></h3>
<p>In our experiments debugging with <code>node --inspect-brk</code>, the Chrome debugger failed to find the source maps. Debugging raw WASM is unpleasant, so we recommend an alternative — make a simple webpage that hosts your app.</p>
<p>Make an <code>index.html</code> with the following contents in the root of your git repository:</p>
<pre><code class="language-html">&lt;!DOCTYPE html&gt;
&lt;html&gt;
&lt;head&gt;
&lt;script src=&quot;./target/wasm32-unknown-emscripten/debug/myapp.js&quot;&gt;&lt;/script&gt;
&lt;/head&gt;
&lt;body&gt;&lt;/body&gt;
&lt;/html&gt;
</code></pre>
<h3 id="serve-your-page"><a class="header" href="#serve-your-page">Serve your page</a></h3>
<p>In another terminal, run:</p>
<pre><code class="language-sh">npm install -g http-server
node http-server /git/repo/root/dir
</code></pre>
<h3 id="debug-your-program-on-the-website"><a class="header" href="#debug-your-program-on-the-website">Debug your program on the website</a></h3>
<p>Open Chrome and navigate to <code>http://localhost:8080/index.html</code>. Hit F12 to open the debugger. Chrome should find your source maps allowing you to navigate the stack, set breakpoints, step, continue, etc. all with real source code. Unfortunately, you can't see variables.</p>
<p>You can also use the <code>log</code> crate to print information to the debug console. If you go this route, use <code>simple-logger</code> as the logger backend; don't use a WASM-specific crate (e.g. <code>wasm-logger</code>) for this because emscripten already routes stdout and stderr to the console.</p>
<div style="break-before: page; page-break-before: always;"></div><h1 id="carryless-arithmetic"><a class="header" href="#carryless-arithmetic">Carryless arithmetic</a></h1>
<p>When learning arithmetic in grade school, you learned the base 10 system where digits range from 0-9. Whenever adding digits exceeds 9, you have to carry the 1. However, this is not the only way to do arithmetic; we can instead omit the carry and allow digits to exceed 9!</p>
<p>Why would we want to do this? FHE operations actually add and multiply <a href="advanced//intro/why.html">polynomials</a> under the hood. If we treat each coefficient of the polynomial as a digit and use carryless arithmetic, we can trick them into behaving like numbers. This results in more efficient data types.</p>
<h2 id="addition"><a class="header" href="#addition">Addition</a></h2>
<p>Let's start with a simple carryless addition example. Adding 99 + 43 without propagating carries gives us:</p>
<pre><code class="language-ignore"> 9 9
+ 4 3
------
13 12
</code></pre>
<p>That is <code>13</code> in the 10s place and <code>12</code> in the 1s place which is <code>13 * 10 + 12 * 1 = 142</code>. This is the same value as if we had propagated carries (<code>1 * 100 + 4 * 10 + 2 * 1 = 142</code>). Under carryless arithmetic, <em>both</em> are valid ways to represent the value 142; representations are no longer unique!</p>
<p>Furthermore, we can represent negative values by negating each digit. For example, <code>-123</code> is <code>-1 * 100 + -2 * 10 + -3 * 1</code>. Mechanically, we simply treat each polynomial coefficient as <code>p</code>'s complement<sup class="footnote-reference"><a href="#1">1</a></sup> value to allow negative numbers.</p>
<p>We can easily extend this reasoning to base 2 (binary). Under carryless arithmetic, base 2 simply means that each digit is a multiple of a power of 2. For example, we can compute <code>3 + 2 + (-4)</code> as follows:</p>
<pre><code class="language-ignore">3 + 2 =
1 1 = 3
+ 1 0 = 2
-----
2 1 = 2*2^1 + 1*2^0 = 5
5 + (-4) =
0 2 1 = 5
+ -1 0 0 = -4
--------
-1 2 1 = -1*2^2 + 2*2^1 + 1*2^0 = 1
</code></pre>
<p>Again <code>-1 2 1</code> equals <code>1</code>, as does <code>0 0 1</code>; the representation is not unique.</p>
<div class="footnote-definition" id="1"><sup class="footnote-definition-label">1</sup>
<p><code>p</code> is the <a href="advanced//advanced/plain_modulus/plain_modulus.html">plain modulus</a></p>
</div>
<h3 id="adding-polynomials"><a class="header" href="#adding-polynomials">Adding polynomials</a></h3>
<p>To see why carryless arithmetic is useful, let's take the values of our previous example (<code>3</code>, <code>2</code>, <code>-4</code>) and map their digits onto polynomials like so: </p>
<p>\[3 = 0\times 2^2 + 1\times 2^1 + 1\times 2^0 \rightarrow 0x^2 + 1x + 1\]</p>
<p>\[2 = 0\times 2^2 + 1\times 2^1 + 0\times 2^0 \rightarrow 0x^2 + 1x + 0\]</p>
<p>\[-4 = -1\times 2^2 + 0\times 2^1 + 0\times 2^0 \rightarrow -1x^2 + 0x + 0\]</p>
<p>To add polynomials, recall that you simply collect the terms:</p>
<p>\[3 + 2 \rightarrow (0x^2 + 1x + 1) + (0x^2 + 1x + 0) = 0x^2 + 2x + 1\]</p>
<p>Now, let's subtract 4:</p>
<p>\[5 + (-4) \rightarrow (0x^2 + 2x + 1) + (-1x^2 + 0x + 0) = -1x^2 + 2x + 1 \]</p>
<p>Note that the coefficients are the same as the digits in our carryless arithmetic result. We can convert the polynomial back into an integer by evaluating it at <code>x = 2</code>, yielding <code>1</code>!</p>
<h2 id="multiplication"><a class="header" href="#multiplication">Multiplication</a></h2>
<p>Now, lets go through a multiplication example with binary carryless arithmetic. Here, we multiply <code>7 * 13 = 91</code>:</p>
<pre><code class="language-ignore"> 0 1 1 1 = 7
* 1 1 0 1 = 13
---------------
0 1 1 1
+ 0 0 0 0
+ 0 1 1 1
+ 0 1 1 1
---------------
0 1 2 2 2 1 1 = 1*2^5 + 2*2^4 + 2*2^3 + 2*2^2 + 1*2^1 + 1*2^0 = 91
</code></pre>
<p>Notice that when we collected each place, we didn't propagate carries when values exceeded <code>1</code>.</p>
<p>As another example, when we square <code>1 0 0 0 0 = 16</code>, we get <code>1 0 0 0 0 0 0 0 0 = 256</code>. Compared to the previous example, the operands are larger (<code>16 * 16</code> vs. <code>7 * 13</code>), but the result's largest digit is smaller — <code>1</code> in <code>1 0 0 0 0 0 0 0 0</code> vs. <code>2</code> in <code>0 1 2 2 2 1 1</code>. This will come up again when we talk about overflow.</p>
<h3 id="multiplying-polynomials"><a class="header" href="#multiplying-polynomials">Multiplying polynomials</a></h3>
<p>As with addition, we'll now show how carryless multiplication directly maps to polynomial multiplication. Let's encode <code>7</code> and <code>13</code> as polynomials:</p>
<p>\[7 = 0\times 2^3 + 1\times 2^2 + 1\times 2^1 + 1\times 2^0 \rightarrow 0x^3 + 1x^2 + 1x^1 + 1\]</p>
<p>\[13 = 1\times 2^3 + 1\times 2^2 + 0\times 2^1 + 1\times 2^0 \rightarrow 1x^3 + 1x^2 + 0x^1 + 1\]</p>
<p>Let's multiply these polynomials:</p>
<p>\[7 \times 13 \rightarrow (0x^3 + 1x^2 + 1x^1 + 1)(1x^3 + 1x^2 + 0x^1 + 1) \]
\[= 1x^3(0x^3 + 1x^2 + 1x^1 + 1) + 1x^2(0x^3 + 1x^2 + 1x^1 + 1)\]
\[ + 0x^1(0x^3 + 1x^2 + 1x^1 + 1) + 1(0x^3 + 1x^2 + 1x^1 + 1) \]</p>
<p>\[=(0x^6 + 1x^5 + 1x^4 + 1x^3) + (0x^5 + 1x^4 + 1x^3 + 1x^2)\]
\[+(0x^4 + 0x^3 + 0x^2 + 0x^1) + (0x^3 + 1x^2 + 1x^1 + 1) \]</p>
<p>\[=0x^6 + 1x^5 + 2x^4 + 2x^3 + 2x^2 + 1x^1 + 1\]</p>
<p>Again, the coefficients of this polynomial exactly match our carryless addition result, so we can trivially map our polynomial back into a number to recover our answer!</p>
<p>You might be wondering: &quot;can polynomial coefficients grow indefinitely?&quot; </p>
<p>Unfortunately, they can't.</p>
<h2 id="overflow"><a class="header" href="#overflow">Overflow</a></h2>
<p>As with normal computer arithmetic, values in FHE can <em>overflow</em>. In Sunscreen, plaintext polynomials have <a href="https://en.wikipedia.org/wiki/Method_of_complements"><code>p</code>'s complement</a> coefficients, where <code>p</code> is the <a href="advanced/./plain_modulus/plain_modulus.html">plaintext modulus</a>. Assuming <code>p</code> is odd, this means each coefficient must be in the range \([\frac{-p}{2}, \frac{p}{2}] \) <sup class="footnote-reference"><a href="#2">2</a></sup>. The result of any operation that falls outside this range will wrap around — it overflows.</p>
<p>Suppose <code>p = 7</code> and we try to add <code>3 + 1</code>. Values should be within the range \([-3,3]\), but <code>3 + 1 = 4</code> is not and thus wraps around to <code>-3</code>! This example looks at a single value, but polynomials feature many coefficients, each of which has the same range restriction.</p>
<div class="footnote-definition" id="2"><sup class="footnote-definition-label">2</sup>
<p>When <code>p</code> is odd, \(\frac{p}{2}\) rounds down. If <code>p</code> is even, the interval is \([\frac{-p}{2}, \frac{p}{2})\), i.e. the upper bound opens.</p>
</div>
<h3 id="addition-1"><a class="header" href="#addition-1">Addition</a></h3>
<p>Let's look at an addition example, treating the coefficients as carryless arithmetic binary digits. Take <code>p = 9</code> (meaning digits are in the interval \([-4,4]\)) and add <code>15 = 4 0 -1</code><sup class="footnote-reference"><a href="#3">3</a></sup> with <code>8 = 2 2 -4</code>.</p>
<pre><code class="language-ignore"> 4 0 -1 = 15
+ 2 2 -4 = 8
--------
-3 2 4 = -3*2^2 + 2*2^1 + 4*2^0 = -4
</code></pre>
<p>From this example, we have two observations:</p>
<ul>
<li>We expected <code>6 2 -5 = 23</code>, but both the 4s and 1s places overflowed, giving us a very strange <code>-4</code>!</li>
<li>Operands' digits only contribute to their respective place in the result (i.e. the 4s place contributes only to the 4s place, the 2s place to only the 2s place, etc).</li>
</ul>
<p>If we increase <code>p</code> to <code>13</code> and repeat the example, we do get the correct answer because <code>6</code> and <code>-5</code> are within \([-6,6]\).</p>
<div class="footnote-definition" id="3"><sup class="footnote-definition-label">3</sup>
<p>Recall that values have many representations under carryless arithmetic — this example is typical after performing a few operations!</p>
</div>
<h3 id="multiplication-1"><a class="header" href="#multiplication-1">Multiplication</a></h3>
<p>Next, let's consider canonical representations of <code>31 = 1 1 1 1 1</code> and <code>15 = 0 1 1 1 1</code> when <code>p = 7</code> (i.e. digits in interval \([-3, 3]\)). Adding these numbers doesn't lead to overflow, but what about multiplication? Let's find out:</p>
<pre><code class="language-ignore"> 1 1 1 1 1 = 31
* 0 1 1 1 1 = 15
--------------------------
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
0 0 0 0 0
--------------------------
0 1 2 3 -1 -1 3 2 1
= 0*256 + 1*128 + 2*64 + 3*32 + -1*16 + -1*8 + 3*4 + 2*2 + 1
= 345
</code></pre>
<p>We draw 2 observations from this example:</p>
<ul>
<li>We expected <code>465 = 0 1 2 3 4 4 3 2 1</code>, but got <code>345</code> because the 16s and 8s places overflowed.</li>
<li>The number of non-zero digits in each operand contributes to the result digits' magnitudes.</li>
</ul>
<p>Increasing <code>p</code> to <code>9</code> eliminates the overflow since <code>4</code> is in the interval \([-4, 4]\).</p>
<p>If we multiply canonical representations of <code>32 = 1 0 0 0 0 0</code> and <code>16 = 0 1 0 0 0 0</code> when <code>p = 7</code>, surely this will overflow as well, right? After all, they're bigger numbers than in our previous example! As it turns out, this gives exactly the right answer: <code>512 = 1 0 0 0 0 0 0 0 0 0</code>. The operands feature far fewer non-zero digits, and thus are less impacted by our second observation.</p>
<p>We chose operand digits with value 1 in this example to reveal the second observation, but larger values further compound digit growth! You can see this by redoing the example with 4's: <code>124 = 4 4 4 4 4</code> times <code>60 = 0 4 4 4 4</code> equals <code>7440 = 0 16 32 48 64 64 48 32 16</code>.</p>
<h3 id="preventing-overflow"><a class="header" href="#preventing-overflow">Preventing overflow</a></h3>
<p>Overflow is a bit counterintuitive under carryless arithmetic, but you can prevent it — simply increase the <a href="advanced/./plain_modulus/plain_modulus.html">plaintext modulus</a>. Understanding your computation and knowing the range of your inputs can help you choose the appropriate value.</p>
</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>
<!-- Livereload script (if served using the cli tool) -->
<script type="text/javascript">
var socket = new WebSocket("ws://localhost:3000/__livereload");
socket.onmessage = function (event) {
if (event.data === "reload") {
socket.close();
location.reload();
}
};
window.onbeforeunload = function() {
socket.close();
}
</script>
<script type="text/javascript">
window.playground_copyable = true;
</script>
<script src="elasticlunr.min.js" type="text/javascript" charset="utf-8"></script>
<script src="mark.min.js" type="text/javascript" charset="utf-8"></script>
<script src="searcher.js" type="text/javascript" charset="utf-8"></script>
<script src="clipboard.min.js" type="text/javascript" charset="utf-8"></script>
<script src="highlight.js" type="text/javascript" charset="utf-8"></script>
<script src="book.js" type="text/javascript" charset="utf-8"></script>
<!-- Custom JS scripts -->
<script type="text/javascript">
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