This documentation is about the BFV version of our compiler; for our new FHE compiler based on the TFHE scheme, see our TFHE Compiler documentation.

Introduction to FHE and our compiler

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 do anything with this encrypted data, apart from decrypting it. That's where FHE comes in!

Using FHE, anyone can perform computations directly on private (i.e. encrypted) data—no need to decrypt.

We recommend starting with this article if you're new to FHE.

Why should I care about FHE?

FHE has applications to a variety of fields. We'll briefly consider two applications of FHE in the blockchain and machine learning space.

In blockchain, FHE enables privacy-preserving smart contracts. 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.

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!).

Why haven't I already used FHE?

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).

As magical as FHE is, it's actually very hard 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 huge performance overhead, expected the user to know quite a bit about how FHE works, or were poorly designed for the target applications.

For FHE to see widespread adoption, we need usability and great performance.

Preliminary knowledge

To effectively use our library, we assume some basic knowledge of public key cryptography as well as Rust.

Cryptography and math

• Plaintext vs. ciphertext: Plaintext refers to unencrypted data (i.e. data in the clear) whereas ciphertext refers to encrypted data.
• Public key vs. private key: In public key cryptography, there are two types of keys. The public key (aka the encryption key) can be shared with others. Using the public key, people can send encrypted messages. The private key (aka the decryption key) should not 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.
• "Homomorphic": We use this term to denote computations performed directly on encrypted data. For example, if we say "homomorphic addition," we are referring to addition of two ciphertexts.
• Modulus: We use this term in the context of discussing modular arithmetic (aka clock arithmetic). Under modular arithmetic, values "wrap around" when they exceed the modulus. In the example 7 mod 4 = 3, 4 is the modulus.

Rust and programming

• Rust basics (e.g. rust types, traits, .unwrap() and other error handling techniques)
• Generic types
• Generic functions

Why is a compiler needed for FHE?

Why is it so hard to write FHE programs?

Note: The following is not a precise description 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.

FHE makes use of some pretty fancy math—namely, lattices. In fact, all known FHE schemes use lattice-based cryptography. Something special about lattice-based cryptography is that it's post-quantum.

You're likely familiar with matrices and vectors. Imagine that instead of having numbers as the entries in a matrix or vector, we replace them with polynomials (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 many numbers (as coefficients) in a single matrix entry, thus leading to better efficiency/performance. Recall that polynomials consist of coefficients (these would be 8, 5, 1, 13 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.

Let's take a brief detour and discuss modular arithmetic (aka clock arithmetic). Modular arithmetic is just integer arithmetic that "wraps" around. Alternatively, you can think of it as division with remainder. For example, 13 mod 12 = 1.

The polynomials in FHE make use of modular arithmetic. The degree is actually mod some value; we'll say degree mod N. The coefficients are also mod some value; we'll say coefficient mod P.

So if I tell you to take the degree mod 3 and the coefficients mod 7, \(8x^5+5x^2+x+13\) becomes \(1x^2+5x^2+x+6\).

To get good performance in FHE, you need to know how to set these parameters (N, P) just right. 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.

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)?

Our compiler handles picking all parameters and the appropriate keys for you. We abstract away the polynomials and circuits too.

Sunscreen's compiler

Our goal is to make it easy for any engineer 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 Rust. In addition to having a powerful and expressive type system, Rust is very well suited to cryptography. It's highly performant (like C/C++) and safe by design (unlike C/C++).

Our compiler relies on Microsoft's SEAL 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.

What features does our compiler offer?

This list isn't comprehensive. These are just the main features we'd like to call attention to:

• Type support for fractions, rationals, and signed integers (even 64-bit integers!)
• Ability to perform computations on combinations of plaintexts and ciphertexts (e.g. you can multiply a ciphertext and plaintext together)
• Can run computations without FHE (useful for testing purposes)
• Private computation with literals
• Automated parameter and key selection
• Ciphertext maintenance operations inserted automatically (these operations need to be done for optimal performance)
• Compiler generates FHE programs for you (no need to work with circuits)
• Compiler automatically parallelizes program (i.e. circuit) execution for you
• Support for WASM
• Support for serialization
• Can compile natively to Apple's M1

Note: 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.

Who should use our compiler?

You're building an application that operates on user data but you want to ensure all user data remains private.

You're a web3 engineer.

Our compiler was primarily designed with your web3 needs in mind!

You likely need all of the following features:

• Exact computation (since you're working with account balances and currency transfer)
• Compatibility with efficient ZKP schemes for trustless decentralized applications (we plan to provide the appropriate libraries for this)
• Program chaining (helpful for smart contract composability)
• Support for fractions/rationals/big integers
• Fast arithmetic
• Exceptional performance overall

You may notice that FHE ciphertexts can sometimes be quite large. In the future, we'll help you manage this issue.

You're a web2 engineer.

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.

Our compiler is great for many web2 applications (e.g. 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.

You're a researcher.

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).

We also provide advanced features that allow you to fine tune the plaintext modulus choice and noise margin if desired.

Compiler performance

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 this SoK paper on FHE compilers.

Time includes key generation + encryption + (homomorphic) computation + decryption.

Experiments were performed on an Intel Xeon @ 3.00 GHz with 8 cores and 16 GB RAM.

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.

Getting started

This chapter walks through installation. We also provide an overview of Sunscreen through a simple example of multiplying two encrypted numbers.

If you'd like to try out the compiler before installing it, check out our playground.

Installation

Using Sunscreen in your app no different than any other Rust crate.

Simply add

sunscreen = "*"

to your application's Cargo.toml [dependencies] section.

You also need cmake, clang, and a C++ compiler toolchain installed on your machine and visible in your $PATH. If you have ever built any other crate that wraps a C++ library, you may already be done.

Linux

Using Yum (e.g. CentOS)

In your terminal, run

sudo yum install cmake3 clang git

Use gcc10-g++ as your compiler

In some distros (e.g Amazon Linux), the default compiler (i.e. gcc7 from the gcc-c++ package), crashes when building SEAL. If g++ --version yields version 7, you need to install and use gcc10.

Run

sudo yum install gcc10 gcc10-c++

then

export CC=/usr/bin/gcc10-gcc
export CXX=/usr/bin/gcc10-g++

before building your application with Cargo. You may wish to add these exports to your shell's rc file (e.g. ~/.bash_profile).

Using Apt (e.g. Debian)

sudo apt install build-essential cmake3 clang git

On some distros (e.g. Ubuntu), the cmake package is already version 3 and you can just use it directly.

Alias cmake3 as cmake

Then, make cmake3 appear in your $PATH as cmake. A simple way to do this is run

sudo ln /usr/bin/cmake3 /usr/bin/cmake

However, this globally creates a hard link for all users and may conflict with also installing the cmake (CMake 2.x) package. As an alternative, you can simply create the hard link or symlink somewhere under your $PATH with higher search precedence than /usr/bin.

MacOS

Using Brew

brew install cmake git

When you first attempt to build your application, MacOS will prompt you to install the command-line developer tools. Do this.

Windows

Install Rust toolchain

Install the MSVC C++ toolchain

When prompted for what to install, ensure you additionally check the Windows 10 SDK. You'll need to rerun the tool and modify your installation if you forget to do this.

Install Rustup. Run the executable and hit return a bunch of times to accept the default options.

Cmake

Install cmake 3.

When prompted, add cmake to either the system or user path. You can also do this later by editing your system's environment variables.

Clang

Install llvm+clang. In the installer, select the option to add LLVM to your %PATH%. If you forget to do check this option, add C:\Program Files\LLVM\bin to your %PATH%.

git

Install git. Defaults are fine.

Crate features

Sunscreen supports the following crate features:

• hexl — Speeds up FHE operations with HEXL on x86_64 processors supporting AVX-512 IMFA instructions. Disabled by default.

My first FHE program

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.

In this example, we'll just multiply two encrypted integers.

use sunscreen::{
    fhe_program,
    types::{bfv::Signed, Cipher},
    Compiler, Error, FheRuntime,
};

#[fhe_program(scheme = "bfv")]
fn simple_multiply(a: Cipher<Signed>, b: Cipher<Signed>) -> Cipher<Signed> {
    a * b
}

fn main() {
}

Notice that the simple_multiply function is like any other function in Rust, except for the #[fhe_program(...)] attribute. This is where the magic happens— it declares your function as an FHE program that can be compiled. The scheme argument should always be "bfv", though we may support additional FHE schemes in the future.

simple_multiply's signature specifies that it takes in two Cipher<Signed> values and returns one. Cipher<T> indicates the contained type T is encrypted (i.e. a ciphertext) and Signed is Sunscreen's signed integer type; thus, Cipher<Signed> indicates that we have an encrypted signed integer. The body of simple_multiply multiplies the ciphertexts a and b together. As with any function in Rust, omitting a ; returns an expression's value from the current scope.

Having specified our program, let's compile it.

use sunscreen::{
    fhe_program,
    types::{bfv::Signed, Cipher},
    Compiler, Error, FheRuntime,
};

#[fhe_program(scheme = "bfv")]
fn simple_multiply(a: Cipher<Signed>, b: Cipher<Signed>) -> Cipher<Signed> {
    a * b
}

fn main() -> Result<(), Error> {
    let app = Compiler::new()
        .fhe_program(simple_multiply)
        .compile()?;

    Ok(())
}

We invoke the compiler to build our simple_multiply FHE program. Compilation translates our program into a runnable format, performs optimizations and fills in implementation details, including figuring out FHE scheme parameters and inserting special operations.

What's the ? after at the end of .compile()? For the uninitiated, the ? operator propagates errors. Fallible expressions in Rust emit Results, which can contain either a value or an error. Using ? 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.

On success, the compiler emits an Application bundle containing the compiled form of each .fhe_program() argument. In our case, app will contain a single compiled FHE program named simple_multiply.

Next, we need a public and private key pair. In order to generate keys, we'll first construct an FheRuntime with the parameters we got from compilation. This allows us to encrypt/decrypt data and run FHE programs.

use sunscreen::{
    fhe_program,
    types::{bfv::Signed, Cipher},
    Compiler, Error, FheRuntime,
};

#[fhe_program(scheme = "bfv")]
fn simple_multiply(a: Cipher<Signed>, b: Cipher<Signed>) -> Cipher<Signed> {
    a * b
}

fn main() -> Result<(), Error> {
    let app = Compiler::new()
        .fhe_program(simple_multiply)
        .compile()?;

    let runtime = FheRuntime::new(app.params())?;

    let (public_key, private_key) = runtime.generate_keys()?;

    let a = runtime.encrypt(Signed::from(15), &public_key)?;
    let b = runtime.encrypt(Signed::from(5), &public_key)?;

    Ok(())
}

After constructing our runtime, we generate a public and private key pair by calling runtime.generate_keys().

Next, we call Signed::from(15) to make an unencrypted Signed integer equal to 15. Rust doesn't allow implicit type conversion as some languages do, so we use the From trait to explicitly convert a Rust i64 into a Sunscreen Signed.

Once we have our plaintext value 15, we encrypt it by calling runtime.encrypt(...), passing in the value and our public key. We repeat this process for b with the value 5. Now that we have the two ciphertexts a and b to give to simple_multiply, we're ready to run our FHE program!

use sunscreen::{
    fhe_program,
    types::{bfv::Signed, Cipher},
    Compiler, Error, FheRuntime,
};

#[fhe_program(scheme = "bfv")]
fn simple_multiply(a: Cipher<Signed>, b: Cipher<Signed>) -> Cipher<Signed> {
    a * b
}

fn main() -> Result<(), Error> {
    let app = Compiler::new()
        .fhe_program(simple_multiply)
        .compile()?;

    let runtime = FheRuntime::new(app.params())?;

    let (public_key, private_key) = runtime.generate_keys()?;

    let a = runtime.encrypt(Signed::from(15), &public_key)?;
    let b = runtime.encrypt(Signed::from(5), &public_key)?;

    let results = runtime.run(app.get_fhe_program(simple_multiply).unwrap(), vec![a, b], &public_key)?;

    let c: Signed = runtime.decrypt(&results[0], &private_key)?;
    assert_eq!(c, 75.into());

    Ok(())
}

We call runtime.run(...) to execute our FHE program. For the first argument, we pass in our previously compiled program. We retrieve this program by calling app.get_fhe_program() and unwrapping the result. The second argument is always a Vec containing the arguments to the FHE program. In this case, we pass in the encrypted a and b values. You'll need to pass in the public_key as well.

What would happen if we forgot to encrypt one of our values or gave an encrypted Fractional value where the program wanted an encrypted Signed value? Fortunately, the run 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 run method returns an error Result. The ? propagates this error, but our program exits because this is the main() method!

Next, we call runtime.decrypt(...) with the first result and our private key. Programs can return more than one value; hence, results is a Vec. Since our FHE program only returns one value, we decrypt the value at index 0. The left hand side of the assignment denotes the decrypted data is a Signed whereas runtime.decrypt(...) ensures this type matches the ciphertext's encrypted value before decryption. If we had assigned a different type to c, say Fractional, then decrypt would return an error.

Finally, we verify the result equals 75 (i.e. 15 * 5) as expected.

What's in an FHE program?

This section describes the anatomy of an FHE program, what you can and can't do, and the different data types FHE programs support.

Types

Sunscreen supports a number of data types for different scenarios. Each of these data types is located in the sunscreen::types::bfv module.

All types T support +, -, * operations on plaintext, ciphertext, and literals. Note that at least one of the operands must be a ciphertext.

• Use Signed if you need to work with integers.
• Use Fractional if you need to work with decimals (but don't anticipate needing to divide by ciphertexts).
• UseRational if ciphertext division is absolutely necessary to your application. This type incurs more overhead than Fractional.

Cipher

The Cipher type is special in that you don't directly create Cipher values. Cipher<T> should only appear in an FHE program's call signature and denotes that an argument or return value is an encrypted T. The absence of this wrapper indicates that T is unencrypted.

While arguments may be unencrypted (i.e. of type T), return values must always be encrypted (i.e. of type Cipher<T>).

For example:

#![allow(unused)]
fn main() {
use sunscreen::{
    fhe_program,
    types::{bfv::Signed, Cipher},
};

#[fhe_program(scheme = "bfv")]
fn my_program(a: Cipher<Signed>, b: Signed) -> (Cipher<Signed>, Cipher<Signed>) {
    // Do things
    (a, a + b)
}
}

• Argument a is an encrypted Signed value.
• Argument b is an unencrypted Signed value.
• my_program returns 2 encrypted Signed values via a tuple.

Arrays

Sunscreen supports fixed-length arrays¹ that behave as you'd expect. You declare and use them as any other fixed-length array in Rust:

#![allow(unused)]
fn main() {
use sunscreen::{
    fhe_program,
    types::{bfv::Fractional, Cipher},
};

#[fhe_program(scheme = "bfv")]
fn matrix_vector_multiply(a: [[Cipher<Fractional<64>>; 10]; 10], b: [Cipher<Fractional<64>>; 10]) -> [Cipher<Fractional<64>>; 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
}
}

You can make arrays of encrypted or unencrypted data types. In the former case, the Cipher must go inside the array; you can't declare a Cipher<[T; 2]>.

Working with literals

Sometimes, you simply want to double a value or add 15. Fortunately, most FHE types and operations support literal operands.

For example, Signed values work with i64 values

#![allow(unused)]
fn main() {
use sunscreen::{
    fhe_program,
    types::{bfv::Signed, Cipher},
};

#[fhe_program(scheme = "bfv")]
fn answer(a: Cipher<Signed>) -> Cipher<Signed> {
    a + 42
}
}

while Fractional and Rational values support f64 values

#![allow(unused)]
fn main() {
use sunscreen::{
    fhe_program,
    types::{bfv::Fractional, Cipher},
};

#[fhe_program(scheme = "bfv")]
fn answer_2(a: Cipher<Fractional<64>>) -> Cipher<Fractional<64>> {
    42.0 * a
}
}

Signed

Signed values allow you to perform integer arithmetic as follows (recall that at least one operand must be a ciphertext):

Additionally, you can perform unary negation on encrypted Signed values.

Representation

Signed values contain thousands of binary digits of precision, easily enough to store any i64 value.

Fractional

Fractional values allow you to perform decimal arithmetic. You can think of Fractional as being similar to a fixed-point representation.

Sunscreen represents Fractional values as an integer and fractional part. The INT_BITS type argument specifies how many binary digits store the integer part. Setting INT_BITS to 64 should be more than sufficient for most applications since Fractional<64> values can exactly represent every i64 with thousands (!!) of binary digits for the decimal portion.

You can perform operations on Fractional values as follows (recall at least one operand must be a ciphertext):

Additionally, you perform unary negation on Fractional ciphertexts.

While division by only literals may seem limiting, this is one of the more common use cases. For example, you can average 3 values:

#![allow(unused)]
fn main() {
use sunscreen::{
    fhe_program,
    types::{bfv::Fractional, Cipher},
    Compiler, Runtime, PublicKey
};

#[fhe_program(scheme = "bfv")]
fn avg(
    a: Cipher<Fractional<64>>,
    b: Cipher<Fractional<64>>,
    c: Cipher<Fractional<64>>
) -> Cipher<Fractional<64>> {
    (a + b + c) / 3.0
}
}

Additionally, division by literals is sufficient to compute many transcendental functions (e.g. sin, cos, exp) via a power series.

Representation

A scheme parameter lattice_dimension (chosen by the Sunscreen compiler) determines the number of decimal places such that INT_BITS + DECIMAL_BITS = lattice_dimension. This scheme parameter is always at least 1024. You can find the compiler's chosen value with my_compiled_program.metadata.params.lattice_dimension.

Fractional values use exact arithmetic and don't suffer from roundoff errors as floating point values do. In fact, if INT_BITS=1024 and lattice_dimension >= 2048 they can exactly store every double precision value with a fixed decimal point!

Efficiency

Unlike the Rational type, storing and computing Fractional values is as efficient as Signed values.

Rational

The Rational type allows you to perform all decimal arithmetic:

Additionally, you can perform unary negation on Rational ciphertexts (i.e., given a, compute -a).

Representation

Rational encodes a numerator and denominator as two independent Signed values. This results in ciphertexts twice as large as when using the Fractional type.

Efficiency

In addition to the increased size, each Rational operation (except negation) requires multiple FHE operations. Thus, even addition can quickly increase FHE program complexity. Using Rational ciphertexts in prolonged computation may require larger scheme parameters (hence resulting in slower computations).

Writing an FHE program

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!

The #[fhe_program(...)] attribute

To indicate that a function is an FHE program, simply add the #[fhe_program()] attribute to an fn function:

#![allow(unused)]
fn main() {
use sunscreen::{
   fhe_program,
};

#[fhe_program(scheme = "bfv")]
fn my_fhe_program() {
}
}

This attribute takes a single scheme argument. Currently, this argument value should always be "bfv", our supported FHE scheme.

FHE program interface requirements

FHE programs implement their logic in the fn function beneath the #[fhe_program()] attribute. The function you write must satisfy some conditions:

• Your fn function must be non-generic and stand-alone (i.e. not a struct method, closure, trait method, etc).
• Your fn function may take any number of arguments.
• Each argument must be of either type T (i.e. plaintext) or Cipher<T> (i.e. ciphertext), where T is a type supported in FHE programs. Every argument need not be the same T.
• Your fn function must return either a Cipher<T> or a tuple of (Cipher<T1>, Cipher<T2>, ...) values (i.e. return values are always encrypted). As with arguments, types must be supported in FHE programs.

Here's an example of an FHE program that returns a tuple containing two encrypted values: a * b and a + c.

#![allow(unused)]
fn main() {
use sunscreen::{
    fhe_program,
    types::{bfv::Signed, Cipher},
};

#[fhe_program(scheme = "bfv")]
fn multiple_returns(a: Cipher<Signed>, b: Cipher<Signed>, c: Signed) -> (Cipher<Signed>, Cipher<Signed>) {
    (a * b, a + c)
}
}

Operations

In FHE programs, you can:

• Perform basic operations (+, -, *, /, <<, >>). The supported set of operations vary from type to type. Note that at least one of the operands must be a ciphertext.
• Call functions.
• Use any Rust construct (e.g. match, for i in ..., if...else) on data not derived from any argument. We walk through a number of examples in the limitations chapter.

Factoring FHE programs

In this section we'll show you how to factor your programs in a specific way that allows for

• Reusing algorithms with different data types.
• Running your algorithm without FHE. This allows you to debug the algorithm without encryption getting in your way and measure FHE's performance overhead.

Let's begin by rewriting our simple_multiply example with a common implementation (simple_multiply_impl):

#![allow(unused)]
fn main() {
use sunscreen::{
    fhe_program,
    types::{bfv::{Signed, Fractional}, Cipher},
};
use std::ops::Mul;

fn simple_multiply_impl<T, U>(a: T, b: U) -> T
where T: Mul<U, Output=T> + Copy
{
    a * b
}

#[fhe_program(scheme = "bfv")]
fn simple_multiply_signed(a: Cipher<Signed>, b: Cipher<Signed>) -> Cipher<Signed> {
    simple_multiply_impl(a, b)
}


#[fhe_program(scheme = "bfv")]
fn simple_multiply_fractional(a: Cipher<Fractional<64>>, b: Fractional<64>) -> Cipher<Fractional<64>> {
    simple_multiply_impl(a, b)
}
}

The first FHE program multiplies encrypted Signed values. In the second, a is an encrypted Fractional value while b is an unencrypted Fractional value. We can run both of these programs using runtime.run() as normal.

Running your implementation without FHE

If we inspect the trait bounds on simple_multiply_impl, we'll notice there is no mention of anything Sunscreen related. This means we can directly run our implementation with Rust i64 values by simply calling:

use std::ops::Mul;

fn simple_multiply_impl<T, U>(a: T, b: U) -> T
where T: Mul<U, Output=T> + Copy
{
    a * b
}

fn main() {
    simple_multiply_impl(7, 5);
}

It's worth explicitly pointing out that T and U may be of the same or different types; the trait bounds merely require that you can multiply T and U values.

Limitations

FHE programs have some limitations you'll need to keep in mind.

Comparisons not supported

Performing comparisons on encrypted data is complex. Thus, we do not currently support comparisons.

The following is not allowed:

#![allow(unused)]
fn main() {
use sunscreen::types::{bfv::Signed, Cipher};

#[fhe_program(scheme = "bfv")]
fn invalid(a: Cipher<Signed>) -> Cipher<Signed> {
    // Return value mismatch aside, comparisons
    // are not supported
    a == 42
}
}

Branching restricted to constant expressions

Branches (i.e. for, if/else, match) cannot depend on function arguments, encrypted¹ or otherwise.

For example, you cannot do the following:

#![allow(unused)]
fn main() {
use sunscreen::types::{bfv::Signed, Cipher};

#[fhe_program(scheme = "bfv")]
fn invalid(a: Cipher<Signed>, b: Signed) -> Cipher<Signed> {
    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
}
}

You can, however, use loops and if statements so long as their conditions don't depend on FHE program arguments. The examples below show allowed loop and if statements:

#![allow(unused)]
fn main() {
use sunscreen::{
   types::{bfv::{Fractional, Signed}, Cipher},
   fhe_program
};

#[fhe_program(scheme = "bfv")]
fn loopy(x: Cipher<Fractional<64>>) -> Cipher<Fractional<64>> {
    let mut y = x;

    for _ in 0..5 {
        y = y + x;
    }

    y
}

#[fhe_program(scheme = "bfv")]
fn iffy(x: Cipher<Signed>) -> Cipher<Signed> {
    let mut ans = x;

    for i in 1..5 {
        if i % 2 == 0 {
            ans = ans + i * x;
        } else {
            ans = ans - i * x;
        }
    }

    ans
}
}

Notice that their conditions don't depend on their argument x, so they're legal.

Bounded computation

You currently cannot perform computations indefinitely on ciphertexts. See here for a more in-depth discussion of this.

Avoid "transparent" ciphertexts

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 run() to fail to prevent data from leaking. Fortunately, such operations are not particularly useful in the first place.

Avoid doing the following:

• Subtracting a ciphertext from itself. However, it's fine to subtract 2 different ciphertexts that happen to contain the same value (i.e. the ciphertexts encrypt the same data but using different randomness).
• Multiplying a ciphertext by the plaintext or literal value 0. However, if a ciphertext encrypts 0, that's totally fine.

Troubleshooting

How do I debug my algorithm?

You can write your algorithm in a generic way, run it without FHE, and single step through it. You can also compare results executing with and without FHE.

Another technique that can be helpful is to call the render() method on your compiled FheProgram. This returns a String containing the compiled execution graph in DOT format. You can write this to a file and render it with Graphviz, a standard graph rendering library.

My FHE program yields the wrong answer. I'm certain the algorithm is correct.

Your issue might be one of 2 things:

1. You exceeded the noise budget. You can check the noise budget remaining on a ciphertext (this requires the private key) by calling (runtime.measure_noise_budget(&ciphertext, &private_key)). If this value is 0, you exceeded the noise budget and your value is corrupted. The most common scenario where you will encounter this issue is when chaining multiple FHE program executions.
2. Overflow. Try increasing the plaintext modulus. Due to carryless arithmetic, 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.

I need to use the output of one FHE program as the input to another (i.e. chain program executions).

We will likely improve the experience in the future, but you can do this today as follows:

1. Compile all your FHE programs with an increased noise_margin and look at their metadata.params.lattice_dimension values.
2. Change your application so the that the program with the largest lattice dimension (program x) compiles as it does in step 1, while the remaining programs call .with_params(&x.metadata.params) during compilation. This causes the remaining programs to use the same parameters verbatim.

The noise_margin you chose in step 1 determines how many times you can chain together program executions.

What the heck is an FheProgramNode?

It's a type wrapper needed to compile your FHE program. Internally, the #[fhe_program] macro turns all your program inputs and outputs into graph nodes — i.e. FheProgramNodes. Operator inputs and outputs are actually FheProgramNodes, which build up the execution graph during compilation. Unfortunately, they tend to be a leaky abstraction that wind up in error messages.

Usually, these errors tell you an FheProgramNode'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 Signed values:

error[E0369]: cannot divide `FheProgramNode<Cipher<Signed>>` by `FheProgramNode<Cipher<Signed>>`
  --> examples/simple_multiply/src/main.rs:22:7
   |
22 |     a / b
   |     - ^ - FheProgramNode<Cipher<Signed>>
   |     |
   |     FheProgramNode<Cipher<Signed>>

For more information about this error, try `rustc --explain E0369`.

This can also crop up when using explicit annotations. For example, the following will fail to compile:

#![allow(unused)]
fn main() {
#[fhe_program(scheme = "bfv")]
fn simple_multiply(a: Cipher<Signed>, b: Cipher<Signed>) -> Cipher<Signed> {
    // This assignment will fail because a * b results in an
    // `FheProgramNode<Cipher<Signed>>`, not a Cipher<Signed>
    let c: Cipher<Signed>  = a * b;

    c
}
}

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 sunscreen::types::intern::FheProgramNode.

Runtime

To create a runtime, you simply call FheRuntime::new, passing a Params object. You get a params object from compiling an FHE program as we did in our example.

use sunscreen::{
    fhe_program,
    types::{bfv::Signed, Cipher},
    Compiler, FheRuntime, PublicKey
};

#[fhe_program(scheme = "bfv")]
fn noop() {
}

fn main() {
   let app = Compiler::new()
       .fhe_program(noop)
       .compile()
       .unwrap();

    let runtime = FheRuntime::new(app.params()).unwrap();
}

Once you're created a runtime, you can:

• generate public/private keys
• encrypt plaintexts
• run FHE programs
• decrypt ciphertexts

Parameter compatibility

Note that to use artifacts produced by a runtime (e.g. ciphertexts, keys), they must have been produced under a runtime using exactly the same parameters. This situation may have ramifications if you're attempting to re-use ciphertexts across multiple FHE programs; those programs must be compiled with the same set of parameters.

Key Generation

Once you've created a runtime, generating keys is simple:

use sunscreen::{
    fhe_program,
    types::{bfv::Signed, Cipher},
    Compiler, FheRuntime, PublicKey
};

#[fhe_program(scheme = "bfv")]
fn noop() {
}

fn main() {
   let app = Compiler::new()
       .fhe_program(noop)
       .compile()
       .unwrap();

   let runtime = FheRuntime::new(app.params()).unwrap();

    let (public_key, private_key) = runtime.generate_keys().unwrap();
}

This produces a public key (which allows you to encrypt data and run FHE programs) and a private key (which allows you to decrypt).

Encryption

To encrypt data, simply call encrypt() on FheRuntime:

use sunscreen::{
    fhe_program,
    types::{bfv::Signed, Cipher},
    Compiler, FheRuntime, PublicKey
};

#[fhe_program(scheme = "bfv")]
fn noop() {
}

fn main() {
   let app = Compiler::new()
       .fhe_program(noop)
       .compile()
       .unwrap();

   let runtime = FheRuntime::new(app.params()).unwrap();
   let (public_key, private_key) = runtime.generate_keys().unwrap();

    let val = Signed::from(15);
    let val_enc = runtime.encrypt(val, &public_key).unwrap();
}

This produces a Ciphertext value suitable for use in run(). Be careful not to confuse the Ciphertext type, which represents an actual encrypted value, with Cipher, which is a marker type to indicate a value in an FHE program is encrypted! Sunscreen can encrypt any of its provided types or fixed-length arrays¹ of them. Note that arrays encrypt as multiple values in a single large Ciphertext.

Cleartext metadata

Sunscreen attaches scheme parameters and the underlying datatype metadata to each Ciphertext. The former aids in serialization, while the latter prevents honest mistakes and improves the developer experience. When you serialize Ciphertext 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).

Running FHE Programs

In our simple example, we called runtime.run to execute our FHE program

use sunscreen::{*, types::{{bfv::Signed}, Cipher}};

fn main() {
  #[fhe_program(scheme = "bfv")]
  fn multiply(a: Cipher<Signed>, b: Cipher<Signed>) -> Cipher<Signed> {
  a * b
  }

  let app = Compiler::new()
      .fhe_program(multiply)
      .plain_modulus_constraint(PlainModulusConstraint::Raw(64))
      .compile()
      .unwrap();

  let runtime = FheRuntime::new(app.params()).unwrap();
  let (public_key, _) = runtime.generate_keys().unwrap();
    let a_enc = runtime.encrypt(Signed::from(5), &public_key).unwrap();
    let b_enc = runtime.encrypt(Signed::from(15), &public_key).unwrap();

    let results = runtime.run(app.get_fhe_program(multiply).unwrap(), vec![a_enc, b_enc], &public_key).unwrap();
}

Let's break down the arguments to runtime.run:

1. The first app.get_fhe_program(multiply).unwrap() argument is the compiled multiply program you wish to run.
2. The second vec![a, b] argument contains the input arguments to the program in a Vec.
3. The final public_key argument is the public key used to generate the encrypted program inputs (i.e. a_enc and b_enc).

FHE program inputs

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!

Our FheProgramInput wrapper enum solves this problem; it wraps values so they can exist in a homogeneous collection. The run function's second argument is a Vec<T> where T readily converts into an FheProgramInput (i.e. T impl Into<FheProgramInput>¹). Ciphertext and all types under sunscreen::bfv::types::* do this.

If your FHE program only accepts ciphertexts (a common scenario), it's sufficient to simply pass a Vec<Ciphertext> as we did in the above example. However, if you want to mix Ciphertext and unencrypted values, you'll need to make a Vec<FheProgramInput> manually, converting each argument yourself:

use sunscreen::{*, types::{{bfv::Signed}, Cipher}};

fn main() {
    // Note the lack of the `Cipher` type on b. This declares
    // it as a unencrypted.
    #[fhe_program(scheme = "bfv")]
    fn multiply(a: Cipher<Signed>, b: Signed) -> Cipher<Signed> {
        a * b
    }

    let app = Compiler::new()
        .fhe_program(multiply)
        .compile()
        .unwrap();

    let runtime = FheRuntime::new(app.params()).unwrap();
    let (public_key, _) = runtime.generate_keys().unwrap();

    let a_enc = runtime.encrypt(Signed::from(5), &public_key).unwrap();

    // a is encrypted, but the second argument, b, is not.
    // We make a Vec<FheProgramInput> by calling `.into()`
    // on each value.
    let args: Vec<FheProgramInput> = vec![a_enc.into(), Signed::from(15).into()];
    let results = runtime.run(app.get_fhe_program(multiply).unwrap(), args, &public_key).unwrap();
}

Validation

When you compile your FHE program, the compiler marks down the call signature (argument and return types). The run function validates that the inputs you gave are appropriately encrypted/unencrypted and are of the correct type.

Return value

On success, the run method returns a Vec<Ciphertext> containing each output of the FHE program.

• If the underlying FHE program returns a tuple, the entries of the Vec are each of the tuple's entries.
• If the underlying FHE program returns a single value, the Vec contains a single entry.
• If the underlying FHE program doesn't return anything, you should write more useful programs. The Vec will be empty.

Decryption

To decrypt, simply call decrypt() using your private key and the data you want to decrypt

use sunscreen::{
    fhe_program,
    types::{bfv::Signed, Cipher},
    Compiler, FheRuntime, PublicKey, PlainModulusConstraint
};

#[fhe_program(scheme = "bfv")]
fn noop() {
}

fn main() {
   let app = Compiler::new()
       .fhe_program(noop)
       .plain_modulus_constraint(PlainModulusConstraint::Raw(5))
       .compile()
       .unwrap();

   let runtime = FheRuntime::new(app.params()).unwrap();
   let (public_key, private_key) = runtime.generate_keys().unwrap();

   let val = Signed::from(15);
   let val_enc = runtime.encrypt(val, &public_key).unwrap();

    // val_enc is an encrypted `Signed` value coming from an FHE program
    // or just directly encrypted.
    let a: Signed = runtime.decrypt(&val_enc, &private_key).unwrap();
}

Validation

Unlike with encrypt, you must specify the unencrypted data type (either on the left-hand side as above or using turbofish). The encrypted value's type must match the assigned type; if the specified data type doesn't match that on the ciphertext, decrypt will return an error. In the above example, decrypt will fail if the encrypted value is not a Signed type.

Serialization

While most examples compute everything in one place, in practice, data will be split amongst multiple machines. You can serialize many things in Sunscreen:

• Ciphertexts
• Keys
• Scheme parameters
• FHE programs

Sunscreen uses serde 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 bincode since it reduces storage and network requirements by efficiently packing byte arrays.

The process to serialize and deserialize any type is the same, but this example shows how to do it with a ciphertext:

use sunscreen::{
    fhe_program,
    types::{bfv::Signed, Cipher},
    Compiler, FheRuntime, PublicKey, Ciphertext
};

#[fhe_program(scheme = "bfv")]
fn noop() {
}

fn main() {
   let app = Compiler::new()
       .fhe_program(noop)
       .compile()
       .unwrap();

   let runtime = FheRuntime::new(app.params()).unwrap();
   let (public_key, _) = runtime.generate_keys().unwrap();
    let c = runtime
        .encrypt(Signed::from(20), &public_key)
        .unwrap();

    // ser is now a Vec<u8> that can be written to disk, socket, etc.
    let ser = bincode::serialize(&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(&ser).unwrap();
}

As with any dependency, you'll need to add bincode as a dependency in your Cargo.toml.

From toy programs to real life

So far, we’ve seen how to write a single FHE program that can be run once on an encrypted data set. However, such a situation is often not representative of real life applications of FHE. What if we’d like to run different programs on the same encrypted data set? What if we want to feed the outputs of one FHE program as the inputs to another FHE program?

In this chapter, we’ll look at how to use unified parameters and chaining to address the above scenarios.

Unified Parameters

In many real life scenarios, we want to run different programs on an encrypted data set.

Let's imagine we have a private version of 23andMe run by Service Provider. Service Provider (SP) sets up the protocol and thus is responsible for choosing the appropriate FHE scheme parameters with which the user will generate keys and then encrypt her data. SP chooses parameter set α based on wanting to run test_a on the user's data. They'd like to run the more complex test_b as well on the user's data. However, it turns out that parameter set α is not adequate for running test_b. One solution would be for the SP to figure out the appropriate parameter set for test_b—let's say this is parameter set β—and then ask the user to generate new keys and encrypt her data with respect to this new parameter set. A pretty bad solution right?

In this section, we'll see how to encrypt data in such a way that we can run multiple FHE programs on it; supporting this requires choosing scheme parameters that work for a set of pre-determined FHE programs.

Some other scenarios where you might want unified parameters include:

• training on a private data set where you'd like to experiment with various algorithms
• private inference where you may want to make various predictions using the same user-provided data set

Specifying multiple FHE programs

Let's assume we want to run function1, function2, and function3 on an encrypted data set.

#![allow(unused)]
fn main() {
use sunscreen::fhe_program;

#[fhe_program(scheme = "bfv")]
fn function1() {
}

#[fhe_program(scheme = "bfv")]
fn function2() {
}

#[fhe_program(scheme = "bfv")]
fn function3() {
}
}

As usual, we declare each of our functions as an FHE program with the appropriate attribute (#[fhe_program(scheme = "bfv")])).

use sunscreen::{fhe_program, Compiler, Error};

#[fhe_program(scheme = "bfv")]
fn function1() {
}

#[fhe_program(scheme = "bfv")]
fn function2() {
}

#[fhe_program(scheme = "bfv")]
fn function3() {
}

fn main() -> Result<(), Error> {
   let app = Compiler::new()
       .fhe_program(function1)
       .fhe_program(function2)
       .fhe_program(function3)
       .compile()?;

   Ok(())
}

When we invoke the compiler to build our programs, we pass in each of the programs individually. Behind the scenes, our compiler then chooses FHE scheme parameters that work for running any of the programs!

Chaining

Chaining is an essential feature when moving from toy applications to real life; maybe we'd like to update an ML model based on new training data that came in or maybe we'd like to compose smart contracts together. Regardless of the particular application, we need some way to use the encrypted output of one FHE program as an input to another FHE program.

We have yet to see another FHE compiler support this feature so we'll briefly explain the different chaining scenarios.

Chaining with the same program

Let's look at a special case of chaining where we want to use the encrypted output of Program A as one of the inputs to a new run of Program A.

We'll consider a very simple application so we can focus on how to use this feature. Suppose we have a private account balance that we periodically need to update with incoming private transactions. We express this with the following FHE program:

#![allow(unused)]
fn main() {
use sunscreen::{fhe_program, types::{Cipher, bfv::Signed}};

#[fhe_program(scheme = "bfv")]
fn accumulate_balance(balance: Cipher<Signed>, tx_amount: Cipher<Signed>) -> Cipher<Signed> {
    balance + tx_amount
}
}

When we compile the above FHE program, the compiler chooses scheme parameters that guarantee we can run it with freshly encrypted¹ ciphertexts. As written, the compiler guarantees nothing if the ciphertexts aren't "fresh." As we'll see below, with one simple change to the code, we can chain executions together and fix this limitation.

#![allow(unused)]
fn main() {
use sunscreen::{fhe_program, types::{Cipher, bfv::Signed}};

#[fhe_program(scheme = "bfv", chain_count = 10)]
fn accumulate_balance(balance: Cipher<Signed>, tx_amount: Cipher<Signed>) -> Cipher<Signed> {
    balance + tx_amount
}
}

chain_count = 10 tells the compiler to choose FHE scheme parameters that allow us to chain the program up to 10 times. That is, we can use accumulate_balance's returned ciphertext as the input to another run of accumulate_balance and we can repeat this process up to 10 times. After the final run, the resulting ciphertext can still be decrypted successfully.

Chaining with different programs (stay tuned!)

More generally, we may want to use the encrypted output of one FHE program as the input to a different FHE program.

As this feature is currently in progress, attempting to compile more than one FHE program with any of them declaring a chain_count will result in a compilation error.

Applications

In this section, we'll look at some (hopefully) interesting applications of FHE to web2 and web3.

Private token swap (via automated market makers)

We'll now walk through a less trivial computation that can be done with FHE. Our program is inspired by computations used in automated market makers (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.

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 front-running her order.

To swap her tokens, she interacts with a "pool" 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 changes based on the pool's reserves of the two tokens.

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 encrypted ETH Alice should receive in exchange for her encrypted amount of NU tokens via FHE.

An intro to AMMs for the uninitiated

If you're not familiar with AMMs, we suggest starting here.

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 "pool" 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.

The exchange rate between the two tokens evolves automatically based on a known mathematical formula.

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 "manipulate" 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.

Privacy (specifically hiding trade values) is one solution to this front-running problem.

Program walkthrough

Let's look at how to implement this now.

Setup

#![allow(unused)]
fn main() {
use sunscreen::{
    fhe_program,
    types::{bfv::Rational, Cipher},
    Ciphertext, CompiledFheProgram, Compiler, Params, PrivateKey, PublicKey,
    FheRuntime,
};

#[fhe_program(scheme = "bfv")]
/// This program swaps NU tokens for ETH.
fn swap_nu(
    nu_tokens_to_trade: Cipher<Rational>,
) -> Cipher<Rational> {
    let total_eth = 100.0;
    let total_nu = 1_000.0;

    -(total_eth * total_nu / (total_nu + nu_tokens_to_trade) - total_eth)
}
}

We begin by importing the stuff we're going to use.

We declare our swap_nu function as an FHE program with the appropriate attribute (#[fhe_program(scheme = "bfv")]).

swap_nu computes how much encrypted ETH a user will receive in exchange for nu_tokens_to_trade some amount of encrypted NU . Since we'll need to divide by a ciphertext, we'll have to use the Rational type here. Thus, notice that swap_nu takes in a Cipher<Rational> and returns a Cipher<Rational>. If you're wondering where the formula for swap_nu came from, it's from the constant product formula used by some automated market makers.

Notice that the other values in swap_nu (i.e. the pool reserves for ETH total_eth and NU total_nu) are in the clear.

Alice

#![allow(unused)]
fn main() {
use sunscreen::{
    fhe_program,
    types::{bfv::Rational, Cipher},
    Ciphertext, CompiledFheProgram, Compiler, Params, PrivateKey,
    Error,
    PublicKey,
    FheRuntime
};

/// 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: FheRuntime,
}
}

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).

#![allow(unused)]
fn main() {
use sunscreen::{
    fhe_program,
    types::{bfv::Rational, Cipher},
    Ciphertext, CompiledFheProgram, Compiler, Params, PrivateKey,
    Error,
    PublicKey,
    FheRuntime
};

/// 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: FheRuntime,
}

impl Alice {
    pub fn setup(params: &Params) -> Result<Alice, Error> {
        let runtime = FheRuntime::new(params)?;

        let (public_key, private_key) = runtime.generate_keys()?;

        Ok(Alice {
            public_key,
            private_key,
            runtime,
        })
    }

    pub fn create_transaction(&self, amount: f64) -> Result<Ciphertext, Error> {
        Ok(self.runtime
            .encrypt(Rational::try_from(amount)?, &self.public_key)?
        )
    }

    pub fn check_received_eth(&self, received_eth: Ciphertext) -> Result<(), Error> {
        let received_eth: Rational = self
            .runtime
            .decrypt(&received_eth, &self.private_key)?;

        let received_eth: f64 = received_eth.into();

        println!("Alice received {}ETH", received_eth);

        Ok(())
    }
}
}

Alice first constructs a runtime and then can generate her public/private key pair.

To encrypt her order amount, she'll call create_transaction passing in the amount of NU she wants to trade and herpublic_key. We need try_from here to help us perform the appropriate type conversion.

We won't use this until the very end but check_received_eth 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 check_received_eth Alice will decrypt this value by passing in her private_key and received_eth the encrypted amount of ETH she received.

Miner

Let's look at the miner next.

#![allow(unused)]
fn main() {
use sunscreen::{
    fhe_program,
    types::{bfv::Rational, Cipher},
    Ciphertext, CompiledFheProgram, Compiler, Params, PrivateKey,
    Error,
    PublicKey,
    FheRuntime,
};
/// 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: FheRuntime,
}
}

Recall that the miner is responsible for processing Alice's order; thus, he'll have to run the compiled swap_nu program (compiled_swap_nu).

#![allow(unused)]
fn main() {
use sunscreen::{
    fhe_program,
    types::{bfv::Rational, Cipher},
    Ciphertext, CompiledFheProgram, Compiler, Params, PrivateKey,
    Error,
    PublicKey,
    FheRuntime,
};

#[fhe_program(scheme = "bfv")]
/// This program swaps NU tokens for ETH.
fn swap_nu(
    nu_tokens_to_trade: Cipher<Rational>,
) -> Cipher<Rational> {
    let total_eth = 100.0;
    let total_nu = 1_000.0;

    -(total_eth * total_nu / (total_nu + nu_tokens_to_trade) - total_eth)
}

/// Imagine this is a miner in a blockchain application. They're responsible
/// for processing transactions
struct Miner {
    /// The compiled FHE swap program
    pub compiled_swap_nu: CompiledFheProgram,

    /// The Miner's runtime
    runtime: FheRuntime,
}

impl Miner {
    pub fn setup() -> Result<Miner, Error> {
        let app = Compiler::new()
            .fhe_program(swap_nu)
            .compile()?;

        let runtime = FheRuntime::new(app.params())?;

        Ok(Miner {
            compiled_swap_nu: app.get_fhe_program(swap_nu).unwrap().clone(),
            runtime,
        })
    }

    pub fn run_contract(
        &self,
        nu_tokens_to_trade: Ciphertext,
        public_key: &PublicKey,
    ) -> Result<Ciphertext, Error> {
        let results = self.runtime.run(&self.compiled_swap_nu, vec![nu_tokens_to_trade], public_key)?;

        Ok(results[0].clone())
    }
}
}

In setup, we compile swap_nu and save the runnable program as compiled_swap_nu. We also construct and save an FheRuntime for our miner to allow him to run it.

The miner can run the token swap contract (see run_contract) by calling runtime.run with the compiled_swap_nu program, Alice's encrypted order amount (nu_tokens_to_trade), and Alice's public_key. Recall that we must pass in arguments to an FHE program (such as compiled_swap_nu) via a Vec.

Swapping the tokens privately

use sunscreen::{
    fhe_program,
    types::{bfv::Rational, Cipher},
    Ciphertext, CompiledFheProgram, Compiler, Params, PrivateKey,
    Error,
    PublicKey,
    FheRuntime,
};

 #[fhe_program(scheme = "bfv")]
/// This program swaps NU tokens to receive ETH.
fn swap_nu(
    nu_tokens_to_trade: Cipher<Rational>,
) -> Cipher<Rational> {
    let total_eth = 100.0;
    let total_nu = 1_000.0;

    -(total_eth * total_nu / (total_nu + nu_tokens_to_trade) - total_eth)
}

/// 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: FheRuntime,
}

impl Miner {
    pub fn setup() -> Result<Miner, Error> {
        let app = Compiler::new()
            .fhe_program(swap_nu)
            .compile()?;

        let runtime = FheRuntime::new(app.params())?;

        Ok(Miner {
            compiled_swap_nu: app.get_fhe_program(swap_nu).unwrap().clone(),
            runtime,
        })
    }

    pub fn run_contract(
        &self,
        nu_tokens_to_trade: Ciphertext,
        public_key: &PublicKey,
    ) -> Result<Ciphertext, Error> {
        let results = self.runtime.run(&self.compiled_swap_nu, vec![nu_tokens_to_trade], public_key)?;

        Ok(results[0].clone())
    }
}

/// 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: FheRuntime,
}

impl Alice {
    pub fn setup(params: &Params) -> Result<Alice, Error> {
        let runtime = FheRuntime::new(params)?;

        let (public_key, private_key) = runtime.generate_keys()?;

        Ok(Alice {
            public_key,
            private_key,
            runtime,
        })
    }

    pub fn create_transaction(&self, amount: f64) -> Result<Ciphertext, Error> {
        Ok(self.runtime
            .encrypt(Rational::try_from(amount)?, &self.public_key)?
        )
    }

    pub fn check_received_eth(&self, received_eth: Ciphertext) -> Result<(), Error> {
        let received_eth: Rational = self
            .runtime
            .decrypt(&received_eth, &self.private_key)?;

        let received_eth: f64 = received_eth.into();

        println!("Alice received {}ETH", received_eth);

        Ok(())
    }
}

fn main() -> Result<(), Error> {
    // 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(&miner.compiled_swap_nu.metadata.params)?;

    let transaction = alice.create_transaction(20.0)?;

    let encrypted_received_eth =
        miner.run_contract(transaction, &alice.public_key)?;

    alice.check_received_eth(encrypted_received_eth)?;

    Ok(())
}

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.

Alice calls create_transaction to encrypt her trade amount of 20.0 NU tokens.

The miner calls run_contract to calculate how much encrypted ETH Alice will receive for her encrypted NU (based on the formula from swap_nu). The miner passes in Alice's encrypted trade amount (the result of alice.create_transaction(20.0) which is a ciphertext) along with Alice's public key (alice.public_key).

Finally, Alice can determine how much ETH she actually received from the swap via check_received_eth.

Performance

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.

What's missing?

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).

If you're curious about the answers:

• we've omitted account balances for simplicity (but such account balances would be encrypted as well)
• to ensure Alice is behaving honestly, we would need additional cryptographic tools such as zero-knowledge proofs
• the primary goal of private token swaps would be to prevent front-running, thus there would be some additional step to "reveal" the new reserve values

Private information retrieval

With private information retrieval (PIR), a user can retrieve an item from a database without revealing 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 help detect harmful images in end-to-end encrypted messaging. For private cryptocurrencies, PIR can help light clients retrieve relevant transactions.

To make this section easy to understand, we'll implement two simple PIR algorithms with our compiler.

The first algorithm 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.

The second algorithm does 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.

Warm up: a very simple PIR algorithm

We'll start with a very simple algorithm that uses a dot product to return an item privately.

How will our algorithm work?

Everything in the database will be unencrypted. We'll represent our database as a vector of n items.

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 n as well.

Information retrieval (without privacy)

Every element of this query vector, except 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:

[item₁, item₂, item₃, ... , item_n] · [0, 1, 0, ... , 0]^t

= item₁ · 0 + item₂ · 1 + item₃ · 0 + ... + item_n · 0

= item₂

Of course, the server can observe that Alice is interested in retrieving the 2nd item. How do we make this query private?

Making the query private

For simplicity, let Enc(x) denote that we encrypt x.¹

Since Alice doesn't want to reveal to the server which 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:

[item₁, item₂, item₃, ... , item_n] · [Enc(0), Enc(1), Enc(0), ... , Enc(0)]^t

= item₁ · Enc(0) + item₂ · Enc(1) + item₃ · Enc(0) + ... + item_n · Enc(0)

= Enc(item₂)

Program walkthrough

Our database will have 100 items in it. We'll represent the vectors from earlier as arrays, one of Sunscreen's supported types.

Setup

#![allow(unused)]
fn main() {
use sunscreen::{
    fhe_program,
    types::{bfv::Signed, Cipher},
};

const DATABASE_SIZE: usize = 100;

#[fhe_program(scheme = "bfv")]
/// 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<Signed>; DATABASE_SIZE], database: [Signed; DATABASE_SIZE]) -> Cipher<Signed> {
    let mut sum = query[0] * database[0];

    for i in 1..DATABASE_SIZE {
        sum = sum + query[i] * database[i]
    }

    sum
}
}

We begin by importing the stuff we're going to use.

We declare our lookup function as an FHE program with the appropriate attribute (#[fhe_program(scheme = "bfv")]).

lookup implements the dot product formula discussed above. It takes in the unencrypted database and the encrypted query from the user to retrieve an item privately. The database is an array of length DATABASE_SIZE where each item in the database is a signed integer (Signed). Hence, the user's query is an array of length DATABASE_SIZE as well, where each entry is of type Cipher<Signed>.

Alice

#![allow(unused)]
fn main() {
use sunscreen::{
    fhe_program,
    types::{bfv::Signed, Cipher},
    Ciphertext, CompiledFheProgram, Compiler, Error, FheProgramInput, FheRuntime,
    Params, PrivateKey, PublicKey,
};

/// 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: FheRuntime,
}
}

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).

#![allow(unused)]
fn main() {
use sunscreen::{
    fhe_program,
    types::{bfv::Signed, Cipher},
    Ciphertext, CompiledFheProgram, Compiler, Error, FheProgramInput, FheRuntime,
    Params, PrivateKey, PublicKey,
};

const DATABASE_SIZE: usize = 100;

/// 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: FheRuntime,
}

impl Alice {
    pub fn setup(params: &Params) -> Result<Alice, Error> {
        let runtime = FheRuntime::new(params)?;

        let (public_key, private_key) = runtime.generate_keys()?;

        Ok(Alice {
            public_key,
            private_key,
            runtime,
        })
    }

    pub fn create_query(&self, index: usize) -> Result<Ciphertext, Error> {
        let mut query = [Signed::from(0); DATABASE_SIZE];
        query[index] = Signed::from(1);

        Ok(self.runtime.encrypt(query, &self.public_key)?)
    }

    pub fn check_response(&self, value: Ciphertext) -> Result<(), Error> {
        let value: Signed = self.runtime.decrypt(&value, &self.private_key)?;

        let value: i64 = value.into();

        println!("Alice received {}", value);

        Ok(())
    }
}
}

Alice will need to construct a runtime. Once that's done, she can generate her public/private key pair.

Alice can create her unencrypted query "vector" (actually an array) of 0's and 1's by calling create_query. 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 encrypt her query, passing in her public_key as necessary.

We won't use this until the very end but check_response allows Alice to decrypt the server's response by passing in the ciphertext she received (value) along with her private_key.

Server

Let's look at the server next.

#![allow(unused)]
fn main() {
use sunscreen::{
    fhe_program,
    types::{bfv::Signed, Cipher},
    Ciphertext, CompiledFheProgram, Compiler, Error, FheProgramInput, FheRuntime,
    Params, PrivateKey, PublicKey,
};
/// 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: FheRuntime,
}
}

Recall that the server is responsible for retrieving Alice's item from the database; thus, it will have to run the compiled lookup program (compiled_lookup).

#![allow(unused)]
fn main() {
use sunscreen::{
    fhe_program,
    types::{bfv::Signed, Cipher},
    Ciphertext, CompiledFheProgram, Compiler, Error, FheProgramInput, FheRuntime,
    Params, PrivateKey, PublicKey,
};

const DATABASE_SIZE: usize = 100;

#[fhe_program(scheme = "bfv")]
/// 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<Signed>; DATABASE_SIZE], database: [Signed; DATABASE_SIZE]) -> Cipher<Signed> {
    let mut sum = query[0] * database[0];

    for i in 1..DATABASE_SIZE {
        sum = sum + query[i] * database[i]
    }

    sum
}

/// 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: FheRuntime,
}

impl Server {
    pub fn setup() -> Result<Server, Error> {
        let app = Compiler::new()
            .fhe_program(lookup)
            .compile()?;

        let runtime = FheRuntime::new(app.params())?;

        Ok(Server {
            compiled_lookup: app.get_fhe_program(lookup).unwrap().clone(),
            runtime,
        })
    }

    pub fn run_query(
        &self,
        query: Ciphertext,
        public_key: &PublicKey,
    ) -> Result<Ciphertext, Error> {
        // 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::<Vec<Signed>>()
            .try_into()
            .unwrap();

        let args: Vec<FheProgramInput> = vec![query.into(), database.into()];

        let results = self.runtime.run(&self.compiled_lookup, args, public_key)?;

        Ok(results[0].clone())
    }
}
}

The server constructs a runtime so that it can run the compiled FHE program compiled_lookup.

Using run_query, the server can return an (encrypted) response to Alice's query.

The items in the database will be the integers from 400 to 499, stored in ascending order. Recall that lookup takes in two arguments---the encrypted query and the unencrypted database. Unfortunately, we'll need to do some type conversion for the database as Sunscreen's compiler needs the Signed type not i64 for its programs.

Additionally, to run FHE programs, we need to pass in arguments as a vec. Thus, we create a vec called args that contains our encrypted query and unencrypted database (which now has Signed entries rather than i64 entries in it).

Once all that's done, the server can run the FHE program by passing in the compiled_lookup program, the arguments to the program args (now contained in a vec), and Alice's public_key.

Retrieving the item privately

use sunscreen::{
    fhe_program,
    types::{bfv::Signed, Cipher},
    Ciphertext, CompiledFheProgram, Compiler, Error, FheProgramInput, FheRuntime,
    Params, PrivateKey, PublicKey,
};

const DATABASE_SIZE: usize = 100;

#[fhe_program(scheme = "bfv")]
/// 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<Signed>; DATABASE_SIZE], database: [Signed; DATABASE_SIZE]) -> Cipher<Signed> {
    let mut sum = query[0] * database[0];

    for i in 1..DATABASE_SIZE {
        sum = sum + query[i] * database[i]
    }

    sum
}

/// 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: FheRuntime,
}

impl Alice {
    pub fn setup(params: &Params) -> Result<Alice, Error> {
        let runtime = FheRuntime::new(params)?;

        let (public_key, private_key) = runtime.generate_keys()?;

        Ok(Alice {
            public_key,
            private_key,
            runtime,
        })
    }

    pub fn create_query(&self, index: usize) -> Result<Ciphertext, Error> {
        let mut query = [Signed::from(0); DATABASE_SIZE];
        query[index] = Signed::from(1);

        Ok(self.runtime.encrypt(query, &self.public_key)?)
    }

    pub fn check_response(&self, value: Ciphertext) -> Result<(), Error> {
        let value: Signed = self.runtime.decrypt(&value, &self.private_key)?;

        let value: i64 = value.into();

        println!("Alice received {}", value);

        Ok(())
    }
}

/// 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: FheRuntime,
}

impl Server {
    pub fn setup() -> Result<Server, Error> {
        let app = Compiler::new()
            .fhe_program(lookup)
            .compile()?;

        let runtime = FheRuntime::new(app.params())?;

        Ok(Server {
            compiled_lookup: app.get_fhe_program(lookup).unwrap().clone(),
            runtime,
        })
    }

    pub fn run_query(
        &self,
        query: Ciphertext,
        public_key: &PublicKey,
    ) -> Result<Ciphertext, Error> {
        // 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::<Vec<Signed>>()
            .try_into()
            .unwrap();

        let args: Vec<FheProgramInput> = vec![query.into(), database.into()];

        let results = self.runtime.run(&self.compiled_lookup, args, public_key)?;

        Ok(results[0].clone())
    }
}

fn main() -> Result<(), Error> {
    // 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(&server.compiled_lookup.metadata.params)?;

    let query = alice.create_query(94)?;

    let response = server.run_query(query, &alice.public_key)?;

    alice.check_response(response)?;

    Ok(())
}

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.

Alice would like to privately retrieve the item at the 94th position from the database so she calls create_query which encrypts her query value of 94 (i.e. we get an array that has encryptions of 0 in all positions except the 94th position which contains an encryption of 1).

The server calls run_query to privately retrieve Alice's desired item to her. It passes in Alice's encrypted query along with Alice's public key (alice.public_key).

Finally, Alice can decrypt to check what item she received via check_response.

Performance

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.

A better PIR algorithm

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!

Let's look at how to reduce the user's query size by making use of matrix-vector product and dot product.

How will our improved algorithm work?

Instead of representing the database as a vector of length n, we'll represent it as a matrix of dimension sqrt(n) by sqrt(n). As prior, everything in the database is unencrypted.

Let's say Alice wants to retrieve item_1,2 from the database. This time, Alice will send two 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).

Information retrieval (without privacy)

What goes in the query vectors?

• 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].
• 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].

When we take the matrix-vector product of the database with query vector #1, we get a vector back. What's in this vector?

[item_1,2, item_2,2, item_3,2, ..., item_sqrt(n),2]

When we take the dot product of the previous result with query vector #2, we get the item Alice is interested in. Why? Well:

[item_1,2, item_2,2, item_3,2, ..., item_sqrt(n),2] · [1, 0, ..., 0]^t = item_1,2

Making the query private

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.

• Query Vector #1: [Enc(0), Enc(1), Enc(0), ..., Enc(0)]
• Query Vector #2: [Enc(1), Enc(0), ..., Enc(0)]

When the server takes the matrix-vector product of the database with encrypted query vector #1, we get:

[Enc(item_1,2), Enc(item_2,2), Enc(item_3,2), ..., Enc(item_sqrt(n),2)]

When the server takes the dot product of the above vector with encrypted query vector #2, voila, we get Alice's desired item:

[Enc(item_1,2), Enc(item_2,2), Enc(item_3,2), ..., Enc(item_sqrt(n),2)] · [Enc(1), Enc(0), ..., Enc(0)]^t = Enc(item_1,2)

Program walkthrough

Our database will have 100 items in it. We'll use an array to represent our database.

Setup

#![allow(unused)]
fn main() {
use sunscreen::{
    fhe_program,
    types::{bfv::Signed, Cipher},
};

const SQRT_DATABASE_SIZE: usize = 10;

#[fhe_program(scheme = "bfv")]
/// 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<Signed>; SQRT_DATABASE_SIZE],
    row_query: [Cipher<Signed>; SQRT_DATABASE_SIZE],
    database: [[Signed; SQRT_DATABASE_SIZE]; SQRT_DATABASE_SIZE],
) -> Cipher<Signed> {
    // 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
}
}

We begin by importing the stuff we're going to use.

We declare our lookup function as an FHE program with the appropriate attribute (#[fhe_program(scheme = "bfv")]).

We'll represent our database as an array of length SQRT_DATABASE_SIZE (in this case = 10) with entries that are arrays of length SQRT_DATABASE_SIZE (also = 10). Since we want to write into the database, we'll need to initialize the array in the FHE program's function body.

lookup implements the matrix-vector and dot product formulas explained above to retrieve Alice's item privately. It takes in an unencrypted database along with Alice's encrypted query "vectors" (actually arrays). Recall that we have two queries— col_query will be used to select the appropriate column of the database whereas row_query will be used to select the appropriate row of the database.

Alice

#![allow(unused)]
fn main() {
use sunscreen::{
    FheRuntime, PrivateKey, PublicKey,
};

/// 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: FheRuntime,
}
}

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).

#![allow(unused)]
fn main() {
use sunscreen::{
    fhe_program,
    types::{bfv::Signed, Cipher},
    Ciphertext, CompiledFheProgram, Compiler, Error, FheProgramInput, FheRuntime,
    Params, PrivateKey, PublicKey,
};

const SQRT_DATABASE_SIZE: usize = 10;

/// 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: FheRuntime,
}

impl Alice {
    pub fn setup(params: &Params) -> Result<Alice, Error> {
        let runtime = FheRuntime::new(params)?;

        let (public_key, private_key) = runtime.generate_keys()?;

        Ok(Alice {
            public_key,
            private_key,
            runtime,
        })
    }

    pub fn create_query(&self, index: usize) -> Result<(Ciphertext, Ciphertext), Error> {
        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, &self.public_key)?,
            self.runtime.encrypt(row_query, &self.public_key)?,
        ))
    }

    pub fn check_response(&self, value: Ciphertext) -> Result<(), Error> {
        let value: Signed = self.runtime.decrypt(&value, &self.private_key)?;

        let value: i64 = value.into();

        println!("Alice received {}", value);

        Ok(())
    }
}
}

Alice will need to construct a runtime. Once that's done, she can generate her public/private key pair.

create_query will allow Alice to create and encrypt her two query "vectors" (i.e. arrays). Alice will pass in an index which contains her desired column and row indices. Notice the 1's place of the index will allow Alice to select her desired column #, whereas the 10's place will allow Alice to select her desired row # (e.g. if index is 85, this denotes Alice is interested in entry located in the 5th column, 8th row).

We won't use this until the very end but check_response allows Alice to decrypt the server's response by passing in the ciphertext she received (value) along with her private_key.

Server

Let's look at the server next.

#![allow(unused)]
fn main() {
use sunscreen::{
    fhe_program,
    types::{bfv::Signed, Cipher},
    Ciphertext, CompiledFheProgram, Compiler, Error, FheProgramInput, FheRuntime,
    Params, PrivateKey, PublicKey,
};

/// 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: FheRuntime,
}
}

Recall that the server is responsible for retrieving Alice's item from the database; thus, it will have to run the compiled lookup program (compiled_lookup).

#![allow(unused)]
fn main() {
use sunscreen::{
    fhe_program,
    types::{bfv::Signed, Cipher},
    Ciphertext, CompiledFheProgram, Compiler, Error, FheProgramInput, FheRuntime,
    Params, PrivateKey, PublicKey,
};

#[fhe_program(scheme = "bfv")]
/// 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<Signed>; SQRT_DATABASE_SIZE],
    row_query: [Cipher<Signed>; SQRT_DATABASE_SIZE],
    database: [[Signed; SQRT_DATABASE_SIZE]; SQRT_DATABASE_SIZE],
) -> Cipher<Signed> {
    // 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
}

const SQRT_DATABASE_SIZE: usize = 10;

/// 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: FheRuntime,
}

impl Server {
    pub fn setup() -> Result<Server, Error> {
        let app = Compiler::new()
            .fhe_program(lookup)
            .compile()?;

        let runtime = FheRuntime::new(app.params())?;

        Ok(Server {
            compiled_lookup: app.get_fhe_program(lookup).unwrap().clone(),
            runtime,
        })
    }

    pub fn run_query(
        &self,
        col_query: Ciphertext,
        row_query: Ciphertext,
        public_key: &PublicKey,
    ) -> Result<Ciphertext, Error> {
        // 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<FheProgramInput> = vec![col_query.into(), row_query.into(), database.into()];

        let results = self.runtime.run(&self.compiled_lookup, args, public_key)?;

        Ok(results[0].clone())
    }
}
}

The server constructs a runtime so that it can run the compiled FHE program compiled_lookup.

Using run_query, the server can return an (encrypted) response to Alice's query.

The items in the database will be the integers from 400 to 499, stored in ascending order. Recall that lookup takes in three arguments---the encrypted query for the column index (col_query), the encrypted query for the row index (row_query), and the unencrypted database. Unfortunately, we'll need to do some type conversion for the database as Sunscreen's compiler needs entries of the Signed type not i64 for its programs.

Additionally, to run FHE programs, we need to pass in arguments as a vec. Thus, we create a vec called args that contains our encrypted queries and unencrypted database (which now has Signed entries rather than i64 entries in it).

Once all that's done, the server can run the FHE program by passing in the compiled_lookup program, the arguments to the program args (now contained in a vec), and Alice's public_key.

Retrieving the item privately

use sunscreen::{
    fhe_program,
    types::{bfv::Signed, Cipher},
    Ciphertext, CompiledFheProgram, Compiler, Error, FheProgramInput, FheRuntime,
    Params, PrivateKey, PublicKey,
};

const SQRT_DATABASE_SIZE: usize = 10;

#[fhe_program(scheme = "bfv")]
/// 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<Signed>; SQRT_DATABASE_SIZE],
    row_query: [Cipher<Signed>; SQRT_DATABASE_SIZE],
    database: [[Signed; SQRT_DATABASE_SIZE]; SQRT_DATABASE_SIZE],
) -> Cipher<Signed> {
    // 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
}

/// 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: FheRuntime,
}

impl Alice {
    pub fn setup(params: &Params) -> Result<Alice, Error> {
        let runtime = FheRuntime::new(params)?;

        let (public_key, private_key) = runtime.generate_keys()?;

        Ok(Alice {
            public_key,
            private_key,
            runtime,
        })
    }

    pub fn create_query(&self, index: usize) -> Result<(Ciphertext, Ciphertext), Error> {
        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, &self.public_key)?,
            self.runtime.encrypt(row_query, &self.public_key)?,
        ))
    }

    pub fn check_response(&self, value: Ciphertext) -> Result<(), Error> {
        let value: Signed = self.runtime.decrypt(&value, &self.private_key)?;

        let value: i64 = value.into();

        println!("Alice received {}", value);

        Ok(())
    }
}

/// 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: FheRuntime,
}

impl Server {
    pub fn setup() -> Result<Server, Error> {
        let app = Compiler::new()
            .fhe_program(lookup)
            .compile()?;

        let runtime = FheRuntime::new(app.params())?;

        Ok(Server {
            compiled_lookup: app.get_fhe_program(lookup).unwrap().clone(),
            runtime,
        })
    }

    pub fn run_query(
        &self,
        col_query: Ciphertext,
        row_query: Ciphertext,
        public_key: &PublicKey,
    ) -> Result<Ciphertext, Error> {
        // 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<FheProgramInput> = vec![col_query.into(), row_query.into(), database.into()];

        let results = self.runtime.run(&self.compiled_lookup, args, public_key)?;

        Ok(results[0].clone())
    }
}
fn main() -> Result<(), Error> {
    // 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(&server.compiled_lookup.metadata.params)?;

    let (col_query, row_query) = alice.create_query(94)?;

    let response = server.run_query(col_query, row_query, &alice.public_key)?;

    alice.check_response(response)?;

    Ok(())
}

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.

Alice would like to privately retrieve the item at the 94th "position" (this will mean the entry located in the 4th row, 9th column) from the database so she calls create_query. create_query encrypts her query value of 94 properly (i.e. creates col_query and row_query which has encryptions of 0s and 1s in the appropriate places).

The server calls run_query to privately retrieve Alice's desired item to her. It passes in Alice's encrypted queries along with Alice's public key (alice.public_key).

Finally, Alice can decrypt to check what item she received via check_response.

Performance

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.

What's missing?

If you're interested in using PIR in a real application, there are much better PIR algorithms out there (e.g. SealPIR, Spiral) that are faster and compress the query vector further.

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. Oblivious message detection allows the user to detect which item she's interested in and can be combined with PIR.

Statistics on encrypted data

Let's look at how to compute various statistics over an encrypted data set. You can imagine more exciting applications such as a private version of 23andMe where the testing provider runs various tests on your encrypted genetic data so that only you know the results!

For this example, we'll demonstrate some basic statistical computations (mean and variance) over a small encrypted data set. The computations presented here are so trivial that the user is better off calculating the results themselves on their own plaintext data; FHE isn't really needed. A more realistic scenario would involve computations that are too intensive for the user to compute herself (i.e. you need a lot of computational power) and/or the test provider holding proprietary tests that they don't wish to share directly with the user.

Program Walkthrough

Our data set will consist of 15 points.

We'll take advantage of unified parameters as well as see how to factor FHE programs and use serialization.

Setup

#![allow(unused)]
fn main() {
use bincode::Error as BincodeError;
use std::ops::{Add, Div, Mul, Sub};
use sunscreen::{
    fhe_program,
    types::{bfv::Fractional, Cipher},
    Ciphertext, CompiledFheProgram, Compiler, Error as SunscreenError,
    FheRuntime, Params, PrivateKey, PublicKey, RuntimeError,
};

const DATA_POINTS: usize = 15;

fn mean<T, const COUNT: usize>(data: &[T; COUNT]) -> T
where
    T: Add<Output = T> + Div<f64, Output = T> + Copy,
{
    let mut sum = data[0];

    for i in 1..data.len() {
        sum = sum + data[i];
    }

    sum / (data.len() as f64)
}

fn variance<T, const COUNT: usize>(data: &[T; COUNT]) -> T
where
    T: Add<Output = T> + Sub<Output = T> + Mul<Output = T> + Div<f64, Output = T> + Copy,
{
    let mean_data = mean(data);
    let mut variance = data.clone();

    for i in 0..data.len() {
        let tmp = mean_data - data[i];

        variance[i] = tmp * tmp;
    }

    mean(&variance)
}

#[derive(Debug)]
pub enum Error {
    SunscreenError(SunscreenError),
    BincodeError(BincodeError),
}

impl From<SunscreenError> for Error {
    fn from(e: SunscreenError) -> Self {
        Self::SunscreenError(e)
    }
}

impl From<RuntimeError> for Error {
    fn from(e: RuntimeError) -> Self {
        Self::SunscreenError(SunscreenError::RuntimeError(e))
    }
}

impl From<BincodeError> for Error {
    fn from(e: BincodeError) -> Self {
        Self::BincodeError(e)
    }
}
}

We begin by importing the stuff we're going to use. For this example, we'll need to use the Fractional type since we'll have to divide a ciphertext by plaintext (as a sanity check, you should convince yourself why).

We factor our programs—namely the mean function and variance function. Recall that factoring allows us to run these programs without FHE if desired.

Testing Provider

#![allow(unused)]
fn main() {
use sunscreen::{
    fhe_program,
    types::{bfv::Fractional, Cipher},
    Ciphertext, CompiledFheProgram, Compiler, Error as SunscreenError,
    FheRuntime, Params, PrivateKey, PublicKey, RuntimeError,
};

pub struct Bob {
    params: Params,
    mean_fhe: CompiledFheProgram,
    variance_fhe: CompiledFheProgram,
    runtime: FheRuntime,
}
}

The testing provider (Bob) will compute the mean and variance of a user's encrypted data set; thus, he'll have to run the compiled versions of these FHE programs.

#![allow(unused)]
fn main() {
use bincode::Error as BincodeError;
use std::ops::{Add, Div, Mul, Sub};
use sunscreen::{
    fhe_program,
    types::{bfv::Fractional, Cipher},
    Ciphertext, CompiledFheProgram, Compiler, Error as SunscreenError,
    FheRuntime, Params, PrivateKey, PublicKey, RuntimeError,
};

const DATA_POINTS: usize = 15;

fn mean<T, const COUNT: usize>(data: &[T; COUNT]) -> T
where
    T: Add<Output = T> + Div<f64, Output = T> + Copy,
{
    let mut sum = data[0];

    for i in 1..data.len() {
        sum = sum + data[i];
    }

    sum / (data.len() as f64)
}

fn variance<T, const COUNT: usize>(data: &[T; COUNT]) -> T
where
    T: Add<Output = T> + Sub<Output = T> + Mul<Output = T> + Div<f64, Output = T> + Copy,
{
    let mean_data = mean(data);
    let mut variance = data.clone();

    for i in 0..data.len() {
        let tmp = mean_data - data[i];

        variance[i] = tmp * tmp;
    }

    mean(&variance)
}

#[derive(Debug)]
pub enum Error {
    SunscreenError(SunscreenError),
    BincodeError(BincodeError),
}

impl From<SunscreenError> for Error {
    fn from(e: SunscreenError) -> Self {
        Self::SunscreenError(e)
    }
}

impl From<RuntimeError> for Error {
    fn from(e: RuntimeError) -> Self {
        Self::SunscreenError(SunscreenError::RuntimeError(e))
    }
}

impl From<BincodeError> for Error {
    fn from(e: BincodeError) -> Self {
        Self::BincodeError(e)
    }
}

pub struct Bob {
   params: Params,
   mean_fhe: CompiledFheProgram,
   variance_fhe: CompiledFheProgram,
   runtime: FheRuntime,
}

impl Bob {
    pub fn new() -> Result<Self, Error> {
        #[fhe_program(scheme = "bfv")]
        fn mean_fhe(data: [Cipher<Fractional<64>>; DATA_POINTS]) -> Cipher<Fractional<64>> {
            mean(&data)
        }

        #[fhe_program(scheme = "bfv")]
        fn variance_fhe(data: [Cipher<Fractional<64>>; DATA_POINTS]) -> Cipher<Fractional<64>> {
            variance(&data)
        }

        let app = Compiler::new()
            .fhe_program(mean_fhe)
            .fhe_program(variance_fhe)
            .compile()?;

        let mean_program = app.get_fhe_program(mean_fhe).unwrap();
        let variance_program = app.get_fhe_program(variance_fhe).unwrap();

        let runtime = FheRuntime::new(app.params())?;

        Ok(Self {
            params: app.params().to_owned(),
            mean_fhe: mean_program.to_owned(),
            variance_fhe: variance_program.to_owned(),
            runtime,
        })
    }

    pub fn compute_and_serialize_mean_variance(
        &self,
        serialized_ciphertext: &[u8],
        serialized_public_key: &[u8],
    ) -> Result<(Vec<u8>, Vec<u8>), Error> {
        let data: Ciphertext = bincode::deserialize(serialized_ciphertext)?;
        let public_key = bincode::deserialize(serialized_public_key)?;

        let mean_result = self
            .runtime
            .run(&self.mean_fhe, vec![data.clone()], &public_key)?;

        let variance_result = self
            .runtime
            .run(&self.variance_fhe, vec![data], &public_key)?;

        Ok((
            bincode::serialize(&mean_result[0])?,
            bincode::serialize(&variance_result[0])?,
        ))
    }

    pub fn serialized_scheme_params(&self) -> Result<Vec<u8>, Error> {
        Ok(bincode::serialize(&self.params)?)
    }
}
}

He declares mean_fhe and variance_fhe as FHE programs with the appropriate attribute (#[fhe_program(scheme = "bfv")]). Asmean_fhe and variance_fhe compute the mean and variance over an encrypted data set, they both take in Cipher<Fractional<64>>s and return a Cipher<Fractional<64>>.

Since Bob is responsible for computing the mean and variance, he'll have to run the compiled mean_fhe and variance_fhe programs. Thus, in new, he compiles mean_fhe and variance_fhe and saves them as runnable programs. Finally, he constructs and saves a runtime so that he can later run these programs.

In compute_and_serialize_mean_variance, Bob computes the mean and variance of a user's encrypted data and then serializes the results of these computations. He calls runtime.run, passing in the respective FHE program (either mean_fhe or variance_fhe), the user's encrypted data (data), and the user's public_key. Recall that we must pass in arguments to an FHE program via a vec. The results of the computations are stored as mean_result and variance_result and then serialized.

We also have serialized_scheme_parameters which will allow Bob to share the appropriate FHE scheme parameters with the user. Doing this ensures that the user encrypts her data with the correct parameter set.

Alice

Let's look at the user (Alice) next.

#![allow(unused)]
fn main() {
use sunscreen::{
    fhe_program,
    types::{bfv::Fractional, Cipher},
    Ciphertext, CompiledFheProgram, Compiler, Error as SunscreenError,
    FheRuntime, Params, PrivateKey, PublicKey, RuntimeError,
};

pub struct Alice {
    runtime: FheRuntime,
    public_key: PublicKey,
    private_key: PrivateKey,
}
}

Alice will need to generate a public/private key pair to encrypt her data with.

#![allow(unused)]
fn main() {
use bincode::Error as BincodeError;
use std::ops::{Add, Div, Mul, Sub};
use sunscreen::{
    fhe_program,
    types::{bfv::Fractional, Cipher},
    Ciphertext, CompiledFheProgram, Compiler, Error as SunscreenError,
    FheRuntime, Params, PrivateKey, PublicKey, RuntimeError,
};

const DATA_POINTS: usize = 15;

#[derive(Debug)]
pub enum Error {
    SunscreenError(SunscreenError),
    BincodeError(BincodeError),
}

impl From<SunscreenError> for Error {
    fn from(e: SunscreenError) -> Self {
        Self::SunscreenError(e)
    }
}

impl From<RuntimeError> for Error {
    fn from(e: RuntimeError) -> Self {
        Self::SunscreenError(SunscreenError::RuntimeError(e))
    }
}

impl From<BincodeError> for Error {
    fn from(e: BincodeError) -> Self {
        Self::BincodeError(e)
    }
}
pub struct Alice {
   runtime: FheRuntime,
   public_key: PublicKey,
   private_key: PrivateKey,
}

impl Alice {
    pub fn new(serialized_params: &[u8]) -> Result<Self, Error> {
        let params = bincode::deserialize(serialized_params)?;
        let runtime = FheRuntime::new(&params)?;

        let (public_key, private_key) = runtime.generate_keys()?;

        Ok(Self {
            runtime,
            public_key,
            private_key,
        })
    }

    pub fn encrypt_and_serialize_input(&self) -> Result<Vec<u8>, Error> {
        fn create_dataset() -> [Fractional<64>; DATA_POINTS] {
            (0..DATA_POINTS)
                .map(|x| Fractional::try_from(x as f64).unwrap())
                .collect::<Vec<Fractional<64>>>()
                .try_into()
                .unwrap()
        }

        let data = create_dataset();

        let ciphertext = self.runtime.encrypt(data, &self.public_key)?;

        Ok(bincode::serialize(&ciphertext)?)
    }

    pub fn serialized_public_key(&self) -> Result<Vec<u8>, Error> {
        Ok(bincode::serialize(&self.public_key)?)
    }

    pub fn deserialize_decrypt_and_print_results(
        &self,
        serialized_mean: &[u8],
        serialized_variance: &[u8],
    ) -> Result<(), Error> {
        let mean = bincode::deserialize(serialized_mean)?;
        let variance = bincode::deserialize(serialized_variance)?;

        let mean: Fractional<64> = self.runtime.decrypt(&mean, &self.private_key)?;
        let mean: f64 = mean.into();

        let variance: Fractional<64> = self.runtime.decrypt(&variance, &self.private_key)?;
        let variance: f64 = variance.into();

        println!("Mean={}, Variance={}", mean, variance);

        Ok(())
    }
}
}

In new, Alice retrieves the scheme parameters and creates a key pair for herself. She obtains the serialized scheme parameters (serialized_params), deserializes them, and uses them to construct a runtime. Once Alice has constructed a runtime, she's ready to generate her public_key and private_key.

Alice then creates her data set (via create_dataset); we need try_from here to help us perform the appropriate type conversion. Now she's ready to encrypt her data using her public_key. She saves the encrypted version as ciphertext and finally serializes it.

serialized_public_key will allow Alice to share her serialized public key with Bob when he performs the computations.

We won't use this until the very end but deserialize_decrypt_and_print_results allows Alice to find out what the results were of Bob's computations. She receives the encrypted serialized_mean and serialized_variance from Bob, deserializes them, and finally can decrypt the values.

Computing various statistics over private data

use bincode::Error as BincodeError;
use std::ops::{Add, Div, Mul, Sub};
use sunscreen::{
    fhe_program,
    types::{bfv::Fractional, Cipher},
    Ciphertext, CompiledFheProgram, Compiler, Error as SunscreenError,
    FheRuntime, Params, PrivateKey, PublicKey, RuntimeError,
};

const DATA_POINTS: usize = 15;

fn mean<T, const COUNT: usize>(data: &[T; COUNT]) -> T
where
    T: Add<Output = T> + Div<f64, Output = T> + Copy,
{
    let mut sum = data[0];

    for i in 1..data.len() {
        sum = sum + data[i];
    }

    sum / (data.len() as f64)
}

fn variance<T, const COUNT: usize>(data: &[T; COUNT]) -> T
where
    T: Add<Output = T> + Sub<Output = T> + Mul<Output = T> + Div<f64, Output = T> + Copy,
{
    let mean_data = mean(data);
    let mut variance = data.clone();

    for i in 0..data.len() {
        let tmp = mean_data - data[i];

        variance[i] = tmp * tmp;
    }

    mean(&variance)
}

#[derive(Debug)]
pub enum Error {
    SunscreenError(SunscreenError),
    BincodeError(BincodeError),
}

impl From<SunscreenError> for Error {
    fn from(e: SunscreenError) -> Self {
        Self::SunscreenError(e)
    }
}

impl From<RuntimeError> for Error {
    fn from(e: RuntimeError) -> Self {
        Self::SunscreenError(SunscreenError::RuntimeError(e))
    }
}

impl From<BincodeError> for Error {
    fn from(e: BincodeError) -> Self {
        Self::BincodeError(e)
    }
}

pub struct Bob {
    params: Params,
    mean_fhe: CompiledFheProgram,
    variance_fhe: CompiledFheProgram,
    runtime: FheRuntime,
}

impl Bob {
    pub fn new() -> Result<Self, Error> {
        #[fhe_program(scheme = "bfv")]
        fn mean_fhe(data: [Cipher<Fractional<64>>; DATA_POINTS]) -> Cipher<Fractional<64>> {
            mean(&data)
        }

        #[fhe_program(scheme = "bfv")]
        fn variance_fhe(data: [Cipher<Fractional<64>>; DATA_POINTS]) -> Cipher<Fractional<64>> {
            variance(&data)
        }

        let app = Compiler::new()
            .fhe_program(mean_fhe)
            .fhe_program(variance_fhe)
            .compile()?;

        let mean_program = app.get_fhe_program(mean_fhe).unwrap();
        let variance_program = app.get_fhe_program(variance_fhe).unwrap();

        let runtime = FheRuntime::new(app.params())?;

        Ok(Self {
            params: app.params().to_owned(),
            mean_fhe: mean_program.to_owned(),
            variance_fhe: variance_program.to_owned(),
            runtime,
        })
    }

    pub fn compute_and_serialize_mean_variance(
        &self,
        serialized_ciphertext: &[u8],
        serialized_public_key: &[u8],
    ) -> Result<(Vec<u8>, Vec<u8>), Error> {
        let data: Ciphertext = bincode::deserialize(serialized_ciphertext)?;
        let public_key = bincode::deserialize(serialized_public_key)?;

        let mean_result = self
            .runtime
            .run(&self.mean_fhe, vec![data.clone()], &public_key)?;

        let variance_result = self
            .runtime
            .run(&self.variance_fhe, vec![data], &public_key)?;

        Ok((
            bincode::serialize(&mean_result[0])?,
            bincode::serialize(&variance_result[0])?,
        ))
    }

    pub fn serialized_scheme_params(&self) -> Result<Vec<u8>, Error> {
        Ok(bincode::serialize(&self.params)?)
    }
}

pub struct Alice {
    runtime: FheRuntime,
    public_key: PublicKey,
    private_key: PrivateKey,
}

impl Alice {
    pub fn new(serialized_params: &[u8]) -> Result<Self, Error> {
        let params = bincode::deserialize(serialized_params)?;
        let runtime = FheRuntime::new(&params)?;

        let (public_key, private_key) = runtime.generate_keys()?;

        Ok(Self {
            runtime,
            public_key,
            private_key,
        })
    }

    pub fn encrypt_and_serialize_input(&self) -> Result<Vec<u8>, Error> {
        fn create_dataset() -> [Fractional<64>; DATA_POINTS] {
            (0..DATA_POINTS)
                .map(|x| Fractional::try_from(x as f64).unwrap())
                .collect::<Vec<Fractional<64>>>()
                .try_into()
                .unwrap()
        }

        let data = create_dataset();

        let ciphertext = self.runtime.encrypt(data, &self.public_key)?;

        Ok(bincode::serialize(&ciphertext)?)
    }

    pub fn serialized_public_key(&self) -> Result<Vec<u8>, Error> {
        Ok(bincode::serialize(&self.public_key)?)
    }

    pub fn deserialize_decrypt_and_print_results(
        &self,
        serialized_mean: &[u8],
        serialized_variance: &[u8],
    ) -> Result<(), Error> {
        let mean = bincode::deserialize(serialized_mean)?;
        let variance = bincode::deserialize(serialized_variance)?;

        let mean: Fractional<64> = self.runtime.decrypt(&mean, &self.private_key)?;
        let mean: f64 = mean.into();

        let variance: Fractional<64> = self.runtime.decrypt(&variance, &self.private_key)?;
        let variance: f64 = variance.into();

        println!("Mean={}, Variance={}", mean, variance);

        Ok(())
    }
}

fn main() -> Result<(), Error> {
    // This application performs serialization to simulate messages
    // going over a network.
    let bob = Bob::new()?;

    let alice = Alice::new(&bob.serialized_scheme_params()?)?;
    let serialized_input = alice.encrypt_and_serialize_input()?;

    let (serialized_mean, serialized_variance) = bob
        .compute_and_serialize_mean_variance(&serialized_input, &alice.serialized_public_key()?)?;

    alice.deserialize_decrypt_and_print_results(&serialized_mean, &serialized_variance)?;

    Ok(())
}

We set up Bob first (since Alice relies on parameters generated from Bob's setup).

Alice retrieves the serialized scheme parameters from Bob which she then uses to set up her runtime and generate a key pair (via new). Once that's done, she encrypts her data and serializes the result using encrypt_and_serialize_input.

Bob retrieves Alice's serialized data (serialized_input) along with Alice's serialized public key (alice.serialized_public_key()). He then computes the mean and variance over Alice's private data set and serializes the results, saving them as serialized_mean and serialized_variance.

Finally, Alice can determine the mean and variance over her data set via deserialize_decrypt_and_prints_results.

Performance

The entire program (not including compilation time) takes ~2.54 s on an Intel Xeon @ 3.0 GHz (with 8 cores and 16 GB RAM) and ~8.71 s on a MacBook Air M1.

What's missing?

For more interesting examples (i.e. larger data sets and more complex statistical computations), you'll likely need to go in and change the default plaintext modulus value to be larger.

FAQ

I've worked with FHE libraries before. What does your compiler actually do?

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 change this value manually if they'd like though.

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).

Can I perform computations on private data belonging to different parties?

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 are certainly ways 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).

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.

What are your future plans?

In terms of plans for our compiler specifically, we'd like to add support for:

• batching
• choosing scheme parameters based on multiple FHE programs as inputs (multi-program parameter sharing)
• using the outputs of one FHE program as the inputs to another FHE program (chaining)
• providing rigorous analysis of noise growth

In terms of broader plans for Sunscreen, some of our next milestones include:

• helping users manage large FHE ciphertexts
• providing a complementary zero-knowledge proof library for our FHE compiler

Advanced

Now that you've gotten the basics down, let's dive into some more complex topics.

BFV scheme

There are many different FHE schemes out there. Our compiler uses the BFV scheme.

Why did we choose the BFV scheme?

The BFV scheme provides the following nice features:

• Exact integer arithmetic (it may surprise you but some FHE schemes can't support exact integer arithmetic)
• "Fast" integer arithmetic¹
• "Small" public key sizes¹
• Potential for "batching" (aka "SIMD"-like) operation for improved performance
• Compatibility with fairly efficient zero-knowledge proof systems

What are some of the drawbacks to the BFV scheme?

No FHE scheme is perfect. Some drawbacks to working with BFV include:

• Certain operations are difficult (i.e. more expensive) to perform. This notably includes comparisons of two private values.
• You can't perform private computations indefinitely 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.

Writing even better FHE programs

In this section, we're going to cover a few techniques to get the most out of your FHE applications.

Specifically, we'll look at:

• Manually changing the plaintext modulus to better suit your data and computation
• Manually changing the noise margin to allow for more efficient computations
• Manually pruning unused public keys for space savings

Plaintext modulus

FHE uses some funky math. At the lowest level, plaintexts are polynomials where the coefficient of each term is an integer modulo the plaintext modulus. The plaintext modulus parameter impacts correctness 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.¹ However, you may at times wish to change it.

Why you might want to change the default plaintext modulus

A few reasons you would change the plain modulus include:

• If the default is too conservative, decreasing the plaintext modulus can improve performance.
• Very very rarely, the default can cause overflow in some FHE programs. Increasing the plaintext modulus solves this issue at the expense of performance.
• You wish to use batching, which requires very specific values.

When setting the plaintext modulus, you call compiler.plain_modulus_constraint() and pass a PlainModulusConstraint, which comes in two forms:

• Raw(x) sets the plaintext modulus to x.
• BatchingMinimum(x) chooses a value suitable for use with batching with at least x bits of precision. As noted in the name, this modulus should be used with batching.

How to change the plaintext modulus

You can manually set the PlainModulusConstraint when compiling your program like so:

use sunscreen::{
    fhe_program,
    types::{bfv::Signed, Cipher},
    Compiler, Runtime, PublicKey, PlainModulusConstraint
};

#[fhe_program(scheme = "bfv")]
fn my_program() {
}

fn main() {
    let app = Compiler::new()
        .fhe_program(my_program)
        .plain_modulus_constraint(PlainModulusConstraint::Raw(1_000_000))
        .compile()
        .unwrap();
}

Noise

Every FHE operation introduces noise into ciphertexts.¹ 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 noise budget.

Fortunately, our compiler handles this noise issue for you. It uses a value known as the noise_margin that influences how conservative it needs to be in parameter selection. So long as noise_budget >= noise_margin, we're good to go. Sunscreen's default noise margin prevents garbled ciphertexts coming from a single FHE program.

Why you might want to change the default noise margin

There are a few reasons you may wish to change the noise margin:

• 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 calculator for a complete example of this scenario.
• Decreasing the noise margin can result in improved performance if your application can tolerate a higher rate of faults.

How to change the noise margin

To change the noise margin, simply call .additional_noise_budget() when compiling your program. For example:

use sunscreen::{
    fhe_program,
    types::{bfv::Signed, Cipher},
    Compiler, Runtime, PublicKey
};

#[fhe_program(scheme = "bfv")]
fn my_program() {
}

fn main() {
    let app = Compiler::new()
        .fhe_program(my_program)
        .additional_noise_budget(60)
        .compile()
        .unwrap();
}

Pruning public keys

For convenience, the generate_keys function creates several keys in the returned PublicKey object.

Why you might want to prune PublicKey

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:

• Galois keys (galois_key) are needed to run FHE programs that perform batching rotations or row swapping.
• Relinearization keys (relin_key) are needed to run FHE programs that multiply ciphertexts.

How to prune PublicKey

Each compiled FHE program contains a list the keys it needs at runtime in fhe_program.metadata.required_keys. You can then remove unneeded keys. For example:

use sunscreen::{
    fhe_program,
    types::{bfv::Signed, Cipher},
    Compiler, FheRuntime, PublicKey
};

#[fhe_program(scheme = "bfv")]
fn noop() {
}

fn main() {
   let app = Compiler::new()
       .fhe_program(noop)
       .compile()
       .unwrap();

   let runtime = FheRuntime::new(app.params()).unwrap();
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
};
}

WASM support

Need to run Sunscreen in your browser or NodeJS app? Simply build your app targeting WebAssembly (WASM).

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!

Rust features multiple targets for building WASM binaries, but Sunscreen currently only supports wasm32-unknown-emscripten. As the target's name suggests, this leverages emscripten, which SEAL needs during compilation and runtime.

Setup

Install emscripten

git clone https://github.com/emscripten-core/emsdk.git
emsdk/emsdk install 3.1.3
emsdk/emsdk activate 3.1.3

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 🙃.

Load the emscripten environment

source emsdk/emsdk_env.sh

Put this command in your shell's .rc file so you don't need to rerun it each time you launch a shell.

Add the wasm32-unknown-emscripten target to Rust

rustup target add wasm32-unknown-emscripten

Building

To compile your program with Rust+emscripten, you'll need to do a few extra things.

Required emscripten features

Add the following lines to your .cargo/config.toml¹:

[env]
EMCC_CFLAGS = "-sERROR_ON_UNDEFINED_SYMBOLS=0 -sDISABLE_EXCEPTION_CATCHING=0 -sALLOW_MEMORY_GROWTH"

ERROR_ON_UNDEFINED_SYMBOLS=0 works around a known issue when Rust's panic handling is set to unwind (the default). Alternatively, you can set the handling mode to abort when building for WASM.

DISABLE_EXCEPTION_CATCHING=0 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 abort().

Finally, ALLOW_MEMORY_GROWTH allows the heap to resize. Without this, your app will quickly run out of memory and seg fault.

Building your app

Simply run:

cargo build --bin myapp --release --target wasm32-unknown-emscripten

where myapp is the name of your executable.

On success, you should see the following files:

target/wasm32-unknown-emscripten/release/myapp.js
target/wasm32-unknown-emscripten/release/myapp.wasm

Running with node

node target/wasm32-unknown-emscripten/release/myapp.js

Running in browser

Put myapp.js in a script tag in an index.html file:

<!DOCTYPE html>
<html>
    <head>
        <script src="myapp.js"></script>
    </head>
    <body></body>
</html>

and serve the index.html, myapp.js, and myapp.wasm files on a web server. Your app will run when the user loads the page in their browser.

Alternatively, you can bundle your .js and .wasm into a larger application with webpack.

Running with wasmer/wasmtime

Unfortunately, these scenarios are currently unsupported 😞.

Running tests

Build your tests with:

cargo test --no-run --release --target wasm32-unknown-emscripten

You'll find your tests' entry points in target/wasm32-unknown-emscripten/release/deps/*.js. Simply select the desired test and run:

node target/wasm32-unknown-emscripten/release/mytest-xxxx.js

Debugging

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.

Build in debug mode

To use source maps, simply build in debug mode²:

cargo build --bin myapp --target wasm32-unknown-emscripten

where myapp is the name of your executable.

Make a webpage

In our experiments debugging with node --inspect-brk, 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.

Make an index.html with the following contents in the root of your git repository:

<!DOCTYPE html>
<html>
    <head>
        <script src="./target/wasm32-unknown-emscripten/debug/myapp.js"></script>
    </head>
    <body></body>
</html>

Serve your page

In another terminal, run:

npm install -g http-server
node http-server /git/repo/root/dir

Debug your program on the website

Open Chrome and navigate to http://localhost:8080/index.html. 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.

You can also use the log crate to print information to the debug console. If you go this route, use simple-logger as the logger backend; don't use a WASM-specific crate (e.g. wasm-logger) for this because emscripten already routes stdout and stderr to the console.

Carryless arithmetic

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!

Why would we want to do this? FHE operations actually add and multiply polynomials 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.

Addition

Let's start with a simple carryless addition example. Adding 99 + 43 without propagating carries gives us:

  9  9
+ 4  3
------
 13 12

That is 13 in the 10s place and 12 in the 1s place which is 13 * 10 + 12 * 1 = 142. This is the same value as if we had propagated carries (1 * 100 + 4 * 10 + 2 * 1 = 142). Under carryless arithmetic, both are valid ways to represent the value 142; representations are no longer unique!

Furthermore, we can represent negative values by negating each digit. For example, -123 is -1 * 100 + -2 * 10 + -3 * 1. Mechanically, we simply treat each polynomial coefficient as p's complement¹ value to allow negative numbers.

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 3 + 2 + (-4) as follows:

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 

Again -1 2 1 equals 1, as does 0 0 1; the representation is not unique.

Adding polynomials

To see why carryless arithmetic is useful, let's take the values of our previous example (3, 2, -4) and map their digits onto polynomials like so:

\[3 = 0\times 2^2 + 1\times 2^1 + 1\times 2^0 \rightarrow 0x^2 + 1x + 1\]

\[2 = 0\times 2^2 + 1\times 2^1 + 0\times 2^0 \rightarrow 0x^2 + 1x + 0\]

\[-4 = -1\times 2^2 + 0\times 2^1 + 0\times 2^0 \rightarrow -1x^2 + 0x + 0\]

To add polynomials, recall that you simply collect the terms:

\[3 + 2 \rightarrow (0x^2 + 1x + 1) + (0x^2 + 1x + 0) = 0x^2 + 2x + 1\]

Now, let's subtract 4:

\[5 + (-4) \rightarrow (0x^2 + 2x + 1) + (-1x^2 + 0x + 0) = -1x^2 + 2x + 1 \]

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 x = 2, yielding 1!

Multiplication

Now, lets go through a multiplication example with binary carryless arithmetic. Here, we multiply 7 * 13 = 91:

        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

Notice that when we collected each place, we didn't propagate carries when values exceeded 1.

As another example, when we square 1 0 0 0 0 = 16, we get 1 0 0 0 0 0 0 0 0 = 256. Compared to the previous example, the operands are larger (16 * 16 vs. 7 * 13), but the result's largest digit is smaller — 1 in 1 0 0 0 0 0 0 0 0 vs. 2 in 0 1 2 2 2 1 1. This will come up again when we talk about overflow.

Multiplying polynomials

As with addition, we'll now show how carryless multiplication directly maps to polynomial multiplication. Let's encode 7 and 13 as polynomials:

\[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\]

\[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\]

Let's multiply these polynomials:

\[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) \]

\[=(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) \]

\[=0x^6 + 1x^5 + 2x^4 + 2x^3 + 2x^2 + 1x^1 + 1\]

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!

You might be wondering: "can polynomial coefficients grow indefinitely?"

Unfortunately, they can't.

Overflow

As with normal computer arithmetic, values in FHE can overflow. In Sunscreen, plaintext polynomials have p's complement coefficients, where p is the plaintext modulus. Assuming p is odd, this means each coefficient must be in the range \([\frac{-p}{2}, \frac{p}{2}] \) ². The result of any operation that falls outside this range will wrap around — it overflows.

Suppose p = 7 and we try to add 3 + 1. Values should be within the range \([-3,3]\), but 3 + 1 = 4 is not and thus wraps around to -3! This example looks at a single value, but polynomials feature many coefficients, each of which has the same range restriction.

Addition

Let's look at an addition example, treating the coefficients as carryless arithmetic binary digits. Take p = 9 (meaning digits are in the interval \([-4,4]\)) and add 15 = 4 0 -1³ with 8 = 2 2 -4.

  4 0 -1 = 15
+ 2 2 -4 = 8
--------
 -3 2  4 = -3*2^2 + 2*2^1 + 4*2^0 = -4

From this example, we have two observations:

• We expected 6 2 -5 = 23, but both the 4s and 1s places overflowed, giving us a very strange -4!
• 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).

If we increase p to 13 and repeat the example, we do get the correct answer because 6 and -5 are within \([-6,6]\).

Multiplication

Next, let's consider canonical representations of 31 = 1 1 1 1 1 and 15 = 0 1 1 1 1 when p = 7 (i.e. digits in interval \([-3, 3]\)). Adding these numbers doesn't lead to overflow, but what about multiplication? Let's find out:

             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

We draw 2 observations from this example:

• We expected 465 = 0 1 2 3 4 4 3 2 1, but got 345 because the 16s and 8s places overflowed.
• The number of non-zero digits in each operand contributes to the result digits' magnitudes.

Increasing p to 9 eliminates the overflow since 4 is in the interval \([-4, 4]\).

If we multiply canonical representations of 32 = 1 0 0 0 0 0 and 16 = 0 1 0 0 0 0 when p = 7, 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: 512 = 1 0 0 0 0 0 0 0 0 0. The operands feature far fewer non-zero digits, and thus are less impacted by our second observation.

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: 124 = 4 4 4 4 4 times 60 = 0 4 4 4 4 equals 7440 = 0 16 32 48 64 64 48 32 16.

Preventing overflow

Overflow is a bit counterintuitive under carryless arithmetic, but you can prevent it — simply increase the plaintext modulus. Understanding your computation and knowing the range of your inputs can help you choose the appropriate value.

Introduction to ZKPs and our compiler

ZKPs allow one to prove that a statement is correct without revealing any information, other than the correctness of the statement.

A simple real world example might involve Alice trying to convince Bob the bartender she's over 21 without revealing exactly how old she is.

Why should I care about ZKPs?

At first, ZKPs may seem paradoxical or totally unrealistic but they are already out in the wild and have become increasingly popular, particularly for their ability to provide privacy in transparent systems.

For example, in Ethereum, every transaction is recorded on a public blockchain. With ZKPs, users can conduct private transactions (in which the transaction amount and their balance are hidden to outside parties) while only publishing proof of the validity of the transaction (e.g. user shows the hidden amount is less than their hidden balance, the hidden amount is greater than 0). An example of private transactions deployed in practice is Zcash. ZKPs also enable other use cases in the web3 setting, such as decentralized identity and EVM scalability (via "zk-rollups").

While the above ZKP applications relate to the web3 space, there are interesting applications in web2 as well (e.g. Cloudflare's attestation of personhood).

A light introduction to ZKPs

In a zero knowledge proof (ZKP), we have two parties—a prover and a verifier. The prover is trying to convince the verifier of some fact without revealing to the verifier why it's true.

In the introduction, we mentioned that a simple real world example might involve Alice trying to convince Bob the bartender she's over 21 without revealing exactly how old she is (she's 27). In the language of ZKPs, Alice would be the "prover" and Bob would be the "verifier." The statement Alice is trying to show she satisfies is that she is over 21 and her "witness" (think of this as a private piece of information that the prover Alice will use to show she satisfies the statement) might be her ID stating she is 27. Alice will keep the witness hidden from Bob.

How a ZKP works

There are a few steps in an (interactive) ZKP. Don't worry too much about technical details here—we just want to give you a feel for how ZKPs work at a high level.¹

1. The prover first creates a commitment (this will prevent her from cheating later on) which she sends to the verifier.

2. The verifier then sends a challenge to the prover to test her knowledge of what she has claimed.

3. The prover sends a response to the verifier's challenge (which the verifier will check). You can think of the response as the "proof".

ZKP properties

The three properties a ZKP must satify are completeness, soundness, and zero-knowledge.

• Completeness: if the statement is true, the verifier will be convinced by the proof.
• Soundness: if the statement is false, the prover cannot cheat (i.e. convince the verifier to accept the proof) except with some tiny, tiny probability.
• Zero-knowledge: the verifier learns nothing other than the fact that the statement is true.

For most applications, we'd like our proof to be non-interactive. Rather than having a back and forth interaction between the prover and verifier, wouldn't it be nice if we could reduce the protocol to a single round? This can be done using the Fiat-Shamir transformation to make the proof "non-interactive."

In modern day applications of ZKPs, we'd generally like our proof to be succinct as well. There's some debate around what exactly succinct means but generally we'd like for the proof size to be logarithmic (ideally constant) in the size of the computation.

Why do we need a ZKP compiler?

While all of the above sounds simple enough (hopefully), how do we actually start translating programs (written in some higher level programming language) into ZKPs?

Let's look at an overview of the process.²

1. "Idea" : The developer has an idea for an application or program he wants to create that requires proving some relations over private data.
2. "Program" : The developer translates his application idea into a program (potentially written in some high level programming language like Python or Rust).
3. "R1CS" : The developer needs to translate his program into a format that can be used in a ZKP. This requires thinking about the program—specifically the parts involving the relations over private data—in terms of circuits and constraints (conditions we want to impose on our inputs) instead. As part of this, the developer will need to choose a particular arithmetization scheme (such as R1CS).
4. "Params" : Once the developer has translated the relevant part of his program into circuits and constraints, he can feed that into the setup process of a ZKP to generate parameters needed in the proving and verifying algorithms.
5. "ZKP" : Finally, the developer has a ZKP ready to go that others can interact with.

So where does a compiler comes in?

Well, it helps automate the process of translating your program into a format that can then be used in a ZKP (setting up the circuits and constraints for you behind the scenes according to the chosen arithmetization!). The developer will write his program in a high level programming language, letting the compiler know what info he wants to be public vs. private and specifying constraints in a high level way (expressing what relations need to be satisfied on the inputs in terms of =, >, <, >=, <=).

In the future, you'll be able to use Sunscreen's FHE and ZKP compilers in conjunction, adding the #[fhe_program(...)] and #[zkp_program] attributes as needed to various parts of your code to let the compiler know which parts of your code you'd like transformed.

Further reading

If you'd like to learn more about how ZKPs work, we recommend the following resources:

• Vitalik's blog post on zkSNARKs
• ZK Whiteboard sessions, particularly the first 3 videos
• Berkeley's ZKP MOOC, particularly the first 3 videos

Prerequisites

To effectively use our library, we assume some basic knowledge of cryptography as well as Rust.

Cryptography

• Curve: An elliptic curve is a type of mathematical object that forms the basis of most modern-day cryptographic systems. There are many different types of elliptic curves with various properties (e.g. pairing friendly curves, curves that offer very fast operations). The ZKP system we use as the proof backend in our compiler relies on elliptic curve-based cryptography, so we must specify the elliptic curve we want to work with.
• Field: When working with elliptic curves, we also need to specify a field where the points on the curve come from. Fields are a type of mathematical structure that support addition, subtraction, multiplication, and division. The set of real numbers is a common example of a field. However, you can also have finite fields (via modular/clock arithmetic). Finite fields are what we'll be interested in when we're looking at ZKPs.
• Circuits: When we mention circuits in our ZKP compiler docs, we're referring to arithmetic circuits that break everything down into addition and multiplication gates. Programs for ZKP systems are actually circuits; however, you can imagine that writing circuits directly can be tedious and unpleasant.
• Constraints: You can think of constraints as the lower level language of ZKPs, essentially a way to allow the developer to specify the program/computation they're interested in via some mathematical relations. We rely on Rank 1 Constraint Systems, a particular way of translating a program into a set of mathematical relations. In terms of our compiler, you'll be able to work with equality and comparisons (i.e. greater than/less than).
• Witness: A witness is the "secret" that the prover wants to conceal from the verifier. Say for example Alice wants to convince Bob the bartender she's over 21 without revealing to Bob what exactly her age is (she's 27). The witness in this case would be Alice's age (27). When working with our compiler, witnesses will be denoted with the #[private] attribute.

Rust

• Rust basics (e.g. rust types, traits, .unwrap() and other error handling techniques)
• Generic types
• Generic functions

Sunscreen's ZKP compiler

Our goal is to make it easier for engineers to write ZKP programs.

One aspect of this was deciding whether we should develop an entirely new language (with its own syntax and grammar) or create a DSL embedded within an existing programming language. We've chosen to go with a Rust-based DSL. In addition to having a powerful and expressive type system, Rust is very well suited to cryptography. It's highly performant and safe by design. Another important aspect was ensuring compatibility with our FHE compiler (i.e. ability to prove things about FHE-encrypted inputs and providing a consistent experience in terms of API with our FHE compiler).

In ZKP land, the engineer needs to translate their higher level program into a format that ZKPs can understand (arithmetic circuits/constraint systems). This process is called arithmetization and there are a few different ways to specify constraints. Our compiler currently uses R1CS (Rank 1 Constraint System) and helps automate this process for you.

We currently support Bulletproofs as the proof backend though we will add support for other proof backends in the future. Bulletproofs allow you to prove general relations (using arithmetic circuits) and does not require a trusted setup. The main reason for targetting Bulletproofs was speed to launch (as Bulletproofs will most easily link with FHE even though it's by no means the most efficient proof system).

WARNING: Our FHE and ZKP compilers are not yet linked together! Specifically, our current API does not allow you to prove facts about FHE ciphertexts.

What features does our compiler offer?

This list isn't comprehensive (and may not mean much to you unless you've worked with ZKPs previously). These are just the main features we'd like to call attention to:

• Support for other proof backends!
• Basic field operations (specifically, access to +, -, * when creating zkp_programs)
• Support for equality and comparison constraints
• Public, private, and constant inputs (to easily specify the role of program arguments within ZKPs)
• Create gadgets (e.g. to perform additional operations such as division, re-use across programs)
• User definable types

How do ZKPs and FHE fit together?

ZKPs are useful (and often necessary) when building general purpose FHE-enabled applications in a trustless environment. By trustless, we mean an environment in which we either (1) can't fully trust the user encrypting their data or (2) can't fully trust the party responsible for performing the computation on the encrypted data.

What are some examples of the former situation? Let's suppose you've used our FHE compiler to implement private transactions. If a user wants to withdraw some encrypted amount enc(amt) from their encrypted balance enc(bal), how can the implementation enforce that amt <= bal while allowing amt and bal to stay private? Enter ZKPs! Additionally, validating that the user-provided ciphertext is "well-formed" (and not just some random garbage) might be important. In this scenario, the user can send a ZKP along with their ciphertexts, proving the ciphertexts' validity without revealing the underlying values.

With regards to the latter situation, let's take a step back and think about how things work in web2. Maybe you've used AWS to run a benchmark or you've experimented with ChatGPT. How do we know that Amazon has actually run the computation you asked them to? How do we know that OpenAI has actually used their most advanced learning model? The answer is we don't. We're trusting these organizations to have done what we asked them to based on their reputation. If we ask AWS to run an FHE computation for us, we likely trust that they've run it correctly. However, in web3, random parties may be tasked with running FHE computations. If we're assuming a large number of parties are all running the same FHE computation, it may be sufficient to assume there is an honest majority of them (no ZKP required). On the other hand, if a single party is taked with running an FHE computation (say a rollup provider), that party will need to prove that they've run the computation correctly.

Getting started

This chapter walks through installation. We also provide an overview of Sunscreen's ZKP compiler through a simple example of proving set inclusion (i.e. our number is on a given list of numbers without revealing which one it is).

If you'd like to try out our ZKP compiler before installing it, check out our playground.

Installation

Using Sunscreen in your app no different than any other Rust crate.

Simply add

sunscreen = { version = "*", features = ["bulletproofs"] }

to your application's Cargo.toml [dependencies] section. The bulletproofs feature enables the ZKP backend that will be used in the following examples.

You also need cmake, clang, and a C++ compiler toolchain installed on your machine and visible in your $PATH. If you have ever built any other crate that wraps a C++ library, you may already be done.

Linux

Using Yum (e.g. CentOS)

In your terminal, run

sudo yum install cmake3 clang git

Use gcc10-g++ as your compiler

In some distros (e.g Amazon Linux), the default compiler (i.e. gcc7 from the gcc-c++ package), crashes when building SEAL. If g++ --version yields version 7, you need to install and use gcc10.

Run

sudo yum install gcc10 gcc10-c++

then

export CC=/usr/bin/gcc10-gcc
export CXX=/usr/bin/gcc10-g++

before building your application with Cargo. You may wish to add these exports to your shell's rc file (e.g. ~/.bash_profile).

Using Apt (e.g. Debian)

sudo apt install build-essential cmake3 clang git

On some distros (e.g. Ubuntu), the cmake package is already version 3 and you can just use it directly.

Alias cmake3 as cmake

Then, make cmake3 appear in your $PATH as cmake. A simple way to do this is run

sudo ln /usr/bin/cmake3 /usr/bin/cmake

However, this globally creates a hard link for all users and may conflict with also installing the cmake (CMake 2.x) package. As an alternative, you can simply create the hard link or symlink somewhere under your $PATH with higher search precedence than /usr/bin.

MacOS

Using Brew

brew install cmake git

When you first attempt to build your application, MacOS will prompt you to install the command-line developer tools. Do this.

Windows

Install Rust toolchain

Install the MSVC C++ toolchain

When prompted for what to install, ensure you additionally check the Windows 10 SDK. You'll need to rerun the tool and modify your installation if you forget to do this.

Install Rustup. Run the executable and hit return a bunch of times to accept the default options.

Cmake

Install cmake 3.

When prompted, add cmake to either the system or user path. You can also do this later by editing your system's environment variables.

Clang

Install llvm+clang. In the installer, select the option to add LLVM to your %PATH%. If you forget to do check this option, add C:\Program Files\LLVM\bin to your %PATH%.

git

Install git. Defaults are fine.

My first ZKP program

Now that we have installed the Sunscreen crate as a dependency, let's get started writing our first ZKP! Writing our program will be a gradual process and we'll add more code as we progress through this section.

In this example, we'll prove that one private number is equal to one of two public numbers (i.e. we want to show our number is on a given list without revealing which number it is). Specifically, the Prover's private number will be 64 and the public list will contain the numbers 64 and 1000.

A brief overview of the process

Before diving into the code, let's briefly outline how we'll use Sunscreen's ZKP compiler.

1. Create a ZKP program (via the #[zkp_program] attribute).
   • Specify what inputs will be public vs. private (using #[public] and #[private] attributes respectively).
   • Specify the relation that the prover is trying to show/the verifier will need to check. As part of this process, you'll have access to two types of constraints: equality (.constrain_eq) and comparisons (.constrain_gt_bounded, .constrain_ge_bounded, .constrain_lt_bounded, .constrain_le_bounded for >, >=, <, <= respectively).
2. Compile the ZKP program (via .compile). You'll specify the proof backend (e.g. Bulletproofs) as part of this.
3. We can create a runtime now! Using the runtime, a prover and verifier can interact with and use the compiled ZKP program.
4. Prover and verifier will need to agree on the public inputs. How this is done in practice is application-dependent (e.g. data comes from a previous block in the chain, system parameters).
5. Prover creates a proof using the compiled ZKP program, passing in public inputs, along with their private inputs (i.e. witness).
6. Verifier can check a given proof.

Defining a ZKP program

#![allow(unused)]
fn main() {
use sunscreen::{
    bulletproofs::BulletproofsBackend,
    types::zkp::{BulletproofsField, Field, FieldSpec},
    zkp_program, zkp_var, Error, ZkpProgramFnExt
};

#[zkp_program]
fn either<F: FieldSpec>(
    #[private] x: Field<F>, // witness in ZKP terminology
    #[public] y: Field<F>,
    #[public] z: Field<F>,
) {
    let zero = zkp_var!(0);
    let poly = (y - x) * (z - x);
    poly.constrain_eq(zero); 
}
}

There are many different proof systems out there with various tradeoffs in terms of efficiency. How might we write our program generically so that we can compile it to various backend proof systems? We'll do this with the generic type parameter F:FieldSpec (which should be present on all ZKP programs).

There's a few things to explain from the above code but, first, notice that the function either looks just like any other Rust function, except for a few extra attributes:

• #[zkp_program]: This top level attribute is where the magic happens — this declares your function as a ZKP program that can be compiled.
• Argument attributes: Each argument is either private or public:
  • #[private]: This indicates that the argument is private or hidden from the verifier (you can think of this as the witness if you are familiar with that terminology). As we'll see below, it is only specified by the prover when generating a proof. Note that this is the default behavior for program arguments so omitting an attribute is the same as specifying #[private].
  • #[public]: Some public information may be needed as part of proof generation and verification. This attribute indicates that the argument is public to both the prover and verifier. As we'll see below, both parties must specify these inputs when proving and verifying.

To show that a private number is equal to one of two other numbers, we can translate it into the following simple mathematical relation \(0 = (y - x) \cdot (z - x)\) where \(x\) is our private number (i.e. witness) and \(y, z\) are the given public numbers. However, since we're in ZKP land, we're working with a special mathematical object called fields so \(x, y, z,\) and \(0\) are actually field elements. Specifically, they are integers modulo some prime number.

To specify that the program variables x, y, and z are field elements we use the type Field<F>. If we want to create field elements within a ZKP program function (here we want the number 0 as a field element), we need to use the zkp_var macro.

Finally, how do we specify that poly (i.e. (y - x) * (z - x)) is required to be equal to zero in our ZKP program for the provided arguments? We need to use an equality constraint (constrain_eq). You can think of constraints as a kind of mathematically verifiable assertion.

All of these things are explained in much greater detail in the What's in a ZKP program section.

Compiling a ZKP program

Having specified our program, let's compile it.

use sunscreen::{
    bulletproofs::BulletproofsBackend,
    types::zkp::{BulletproofsField, Field, FieldSpec},
    zkp_program, zkp_var, Error, ZkpProgramFnExt
};
#[zkp_program]
fn either<F: FieldSpec>(
    #[private] x: Field<F>,
    #[public] y: Field<F>,
    #[public] z: Field<F>,
) {
    let zero = zkp_var!(0);
    let poly = (y - x) * (z - x);
    poly.constrain_eq(zero);
}
fn main() -> Result<(), Error> {
    let either_zkp = either.compile::<BulletproofsBackend>()?;
    Ok(())
}

This is pretty straightforward; we invoke the .compile() method that exists on our ZKP program and specify the bulletproofs backend proof system (more about this later).

What's the ? after at the end of .compile()? For the uninitiated, the ? operator propagates errors. Fallible expressions in Rust emit Results, which can contain either a value or an error. Using ? 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.

If you need to compile more than one program, you can also invoke a new Compiler and specify multiple ZKP programs. We'll see how to do this later on.

Constructing a runtime

We'll need a ZkpRuntime to interact with compiled ZKP programs.

use sunscreen::{
    bulletproofs::BulletproofsBackend,
    types::zkp::{BulletproofsField, Field, FieldSpec},
    zkp_program, zkp_var, Error, ZkpProgramFnExt
};
#[zkp_program]
fn either<F: FieldSpec>(
    #[private] x: Field<F>,
    #[public] y: Field<F>,
    #[public] z: Field<F>,
) {
    let zero = zkp_var!(0);
    let poly = (y - x) * (z - x);
    poly.constrain_eq(zero);
}
fn main() -> Result<(), Error> {
    let either_zkp = either.compile::<BulletproofsBackend>()?;
    let runtime = either.runtime::<BulletproofsBackend>()?;

    let x = BulletproofsField::from(64);
    let y = BulletproofsField::from(64); 
    let z = BulletproofsField::from(1000); 

    Ok(())
}

To construct a ZkpRuntime, we need to specify which proof system we're interested in using. Currently, the only supported backend is the Bulletproofs proof system so we use BulletproofsBackend.

As mentioned earlier, in ZKP land, we're working with field elements (specifically whatever field we've chosen to use in the corresponding ZKP system). For this example, we're using BulletproofsBackend so we'll want to specify that x, y, and z need to be field elements from whatever field is being utilized there. We do this via BulletproofsField::from.

BulletproofsField is the scalar field of the group used in our curve (Curve25519). Specifically, this will be integers mod 2^252 + 27742317777372353535851937790883648493.

Proving and verifying

Finally, let's see the runtime in action.

use sunscreen::{
    bulletproofs::BulletproofsBackend,
    types::zkp::{BulletproofsField, Field, FieldSpec},
    zkp_program, zkp_var, Error, ZkpProgramFnExt
};
#[zkp_program]
fn either<F: FieldSpec>(
    #[private] x: Field<F>,
    #[public] y: Field<F>,
    #[public] z: Field<F>,
) {
    let zero = zkp_var!(0);
    let poly = (y - x) * (z - x);
    poly.constrain_eq(zero);
}
fn main() -> Result<(), Error> {
    let either_zkp = either.compile::<BulletproofsBackend>()?;
    let runtime = either.runtime::<BulletproofsBackend>()?;

    let x = BulletproofsField::from(64);
    let y = BulletproofsField::from(64);
    let z = BulletproofsField::from(1000);

    // Generate a proof that x is equal to either y or z
    let proof = runtime
        .proof_builder(&either_zkp) // compiled ZKP program
        .private_input(x)           // private inputs
        .public_input(y)            // public inputs
        .public_input(z)
        .prove()?;

    // Verify the proof
    runtime
        .verification_builder(&either_zkp) // compiled ZKP program
        .proof(&proof)                     // proof created by prover
        .public_input(y)                   // public inputs
        .public_input(z)
        .verify()?;

    Ok(())
}

As you can see, for both proving and verifying, the first thing we do is specify the compiled ZKP program. The proof_builder method returns a builder which takes the public and private inputs to produce a proof that will then be passed to the verifier. Accordingly, the verification_builder method returns a builder which takes in the proof and public inputs.

Notice that both proof generation and verification are fallible operations. If you try to construct an invalid proof, the runtime will return an error. This prevents you the prover from trying to send an invalid proof to a verifier, only to be rejected later. Lastly, verification will return an error if the proof is invalid. Also notice that because we are propagating errors with ?, as long as this program exits with code 0, then proof generation and verification have succeeded!

In practice, the prover and verifier are separate entities so ZkpRuntime::prove and ZkpRuntime::verify will happen on different machines but both must have access to the ZKP program either_zkp. They can import it from a common Rust library. Finally, the proof is serializable and can be sent from the prover to the verifier. A realistic example of this multi-machine setting can be found in Applications.

What's in a ZKP program?

If you've already read through our FHE compiler documentation, you'll find that ZKPs are, in many ways, much simpler. This is perhaps unsurprising; whereas FHE enables general purpose private computation, ZKPs have a narrower purpose. For example, ZKP programs don't even have return values!

This section describes the anatomy of a ZKP program, what you can and can't do, and the different types involved in ZKP programs.

ZKP program interface requirements

ZKP programs implement their logic in the fn function beneath the #[zkp_program] attribute.

The fn function you write has to satisfy the following conditions:

• Must be stand-alone (i.e. not a struct method, closure, trait method, etc).
• Must take one generic param F: FieldSpec.
• May take any number of arguments, but each type must be supported.
• May not have any return values.

Operations

Some aspects of writing ZKP programs may be surprising to you if you're not familiar with R1CS constraints at a high level. Not to worry, we'll explain how this plays into the operations available to you.

In ZKP programs, you can:

• Perform basic arithmetic operations (+, -, *)—specially only those native to R1CS. Integer division (with remainder) and field inversion are not directly possible since these operations are not native to R1CS, but can be implemented via a gadget.
• Add constraints to enforce that certain mathematical statements hold in the proof.
• Call other functions.
• Use any Rust construct (e.g. match, for i in ..., if...else) on data not derived from any argument. We walk through a number of examples in the limitations chapter.

Types

All of the types relevant to a ZKP program live in sunscreen::types::zkp.

Native field elements

The ZKPs we're looking at operate over mathematical objects called fields. Thus, we're actually specifying field elements in our ZKP programs.

As we saw in my first ZKP program, the atomic type used in all ZKP programs is Field<F>, which represents a native field element in the backend proof system. For most users, this is the only type you need to be aware of!

The Field type supports the following basic field arithmetic: +, -, *.¹

#![allow(unused)]
fn main() {
use sunscreen::{
    types::zkp::{ConstrainEq, Field, FieldSpec}, zkp_program
};

#[zkp_program]
fn distribution<F: FieldSpec>(a: Field<F>, b: Field<F>, c: Field<F>) {
    let left = a * (b + c);
    let right = a * b + a * c;
    left.constrain_eq(right);
}
}

The constrain_eq introduces a constraint into the proof. We'll talk more about this in Constraints.

Arrays

Sunscreen supports fixed-length arrays² that behave as you'd expect. You declare and use them like any other fixed-length array in Rust:

#![allow(unused)]
fn main() {
use sunscreen::{
    types::zkp::{ConstrainEq, Field, FieldSpec}, zkp_program
};

#[zkp_program]
fn my_program<F: FieldSpec>(a: [[Field<F>; 10]; 10], b: [Field<F>; 10]) {
    // Assert that each array in `a` is equal to the `b` array
    for i in 0..10 {
        for j in 0..10 {
            a[i][j].constrain_eq(b[j]);
        }
    }
}
}

Working with literals

Sometimes, you simply want to double a value or add 15. The easiest way to do this is to use the sunscreen::zkp_var! macro:

#![allow(unused)]
fn main() {
use sunscreen::{
    types::zkp::{ConstrainEq, Field, FieldSpec}, zkp_program, zkp_var
};

#[zkp_program]
fn double_and_add<F: FieldSpec>(a: Field<F>) {
    let two = zkp_var!(2);
    let x = two * a + zkp_var!(15);
    x.constrain_eq(zkp_var!(42));
}
}

You can also create arrays:

#![allow(unused)]
fn main() {
use sunscreen::{
    types::zkp::{ConstrainEq, Field, FieldSpec}, zkp_program, zkp_var
};

#[zkp_program]
fn my_program<F: FieldSpec>(a: [Field<F>; 10]) {
    // Assert a is all zeroes.
    let arr = zkp_var![0; 5];
    for i in 0..5 {
        arr[i].constrain_eq(a[i]);
    }

    // You can also specify varying values, like normal array syntax:
    let arr = zkp_var![11, 1, 2, 42];
    for i in 0..5 {
        arr[i].constrain_eq(a[i + 5]);
    }
}
}

Attributes

We've already discussed the #[zkp_program] attribute. However, there are also attributes on program arguments.

#![allow(unused)]
fn main() {
use sunscreen::{
    types::zkp::{ConstrainEq, Field, FieldSpec}, zkp_program, zkp_var
};

#[zkp_program]
fn all_kinds<F: FieldSpec>(
    #[private] x: Field<F>,
    #[public] p: Field<F>,
) {
    // prove that our secret value x is equal to either p or 1
    let poly = (x - p) * (x - zkp_var!(1));
    poly.constrain_eq(zkp_var!(0));
}
}

Note that zkp_program arguments should appear in the order private, public, and finally constant to match prove call.

Private

The #[private] attribute is used for any arguments that are private to the prover (i.e. shouldn't be seen by anyone else). In more formal terminology, these arguments are the witnesses. For example, this might be a private key in an encryption scheme or something application specific like an account balance that you (as the prover) wish to keep hidden.

This is the default argument type; omitting an attribute is the same as specifying #[private].

Public

The #[public] attribute is used for any arguments that are public to both the prover and verifier. For example, this could be the public generator of a group in some encryption scheme or something application specific like a minimum balance threshold for issuing transactions.

Constant

We do not discuss these in the main docs; please see the advanced section if you're interested in working with constant arguments.

Constraints

So far we've discussed how to create native field elements and perform arithmetic on them. But performing arithmetic on its own doesn't allow us to prove anything. We'll need constraints to create proofs.

You can think of constraints as a set of conditions we claim our hidden values (i.e. private witness) must satify. These constraints are then encoded as a circuit, taking in any public values along with the hidden values. But not to worry, our compiler does this translation for you!

At your disposal, you'll have two types of constraints—equality and comparison.

Equality

The most basic constraint we can introduce is an equality constraint. At first this might not seem very useful; if we prove our private value is equal to something else, isn't that going to reveal too much information? It turns out this equality constraint is very useful, particularly when constrained against a polynomial!

#![allow(unused)]
fn main() {
use sunscreen::{
    types::zkp::{ConstrainEq, Field, FieldSpec}, zkp_program, zkp_var,
};

#[zkp_program]
fn one_of<F: FieldSpec>(
    #[private] x: Field<F>,
    #[public] ys: [Field<F>; 100],
) {
    // prove that our secret is one of 100 possible values
    let zero = zkp_var!(0);
    let one = zkp_var!(1);
    let mut poly = one;
    for y in ys {
        poly = poly * (y - x);
    }
    poly.constrain_eq(zero);
}
}

As constrain_eq is native to R1CS, it is very fast for native fields.

Ordering/Comparisons

The other constraint available in our compiler is an ordering constraint. This one is slightly more complicated to use since the user is required to bound the maximum difference between the numbers being compared.

While the example below involves comparing a private value with a public value, you are free to compare any combination of private and public values in practice!

#![allow(unused)]
fn main() {
use sunscreen::{
    types::zkp::{ConstrainCmp, Field, FieldSpec}, zkp_program, zkp_var,
};

#[zkp_program]
fn exceeds<F: FieldSpec>(
    #[private] balance: Field<F>,
    #[public] threshold: Field<F>,
) {
    // prove that balance > threshold
    balance.constrain_gt_bounded(threshold, 64);
}
}

When we call balance.constrain_gt_bounded(threshold, 64), the second argument is the maximum number of bits required to represent the absolute difference |balance - threshold|. In this example, if we suppose that balance and threshold values are represented in our application as u64, we know that the difference can be represented in 64 bits.

We also offer constrain_ge_bounded, constrain_lt_bounded, and constrain_le_bounded, which constrain >=, <, <= respectively.

Please note that comparison constraints are not native to R1CS (and are actually making use of gadgets we've created for you under the hood). Thus, a larger number of bits will result in slower proofs.

Limitations

ZKP programs have some limitations you'll need to keep in mind. Some of these restrictions apply more generally to ZKPs while others have to do with the design of our compiler (e.g. our specific choice of arithmetization).

Comparisons not directly supported

It's important to keep in mind that the values we're working with are native field elements within R1CS, and not typical integral types.

One of the many differences is that comparisons like == or > are not supported on native field elements:

#![allow(unused)]
fn main() {
#[zkp_program]
fn invalid<F: FieldSpec>(a: Field<F>) {
    // The following lines won't compile!
    let b1 = a == 42;
    let b2 = a > 42;
    let b3 = a <= 42;
}
}

However, you can specify comparisons as constraints.

Division not directly supported

Division (whether it's integer division with remainder or computing the inverse) is not native to R1CS so it must be specified via a "gadget".

Branching restricted to constant expressions

Branches (i.e. for, if/else, match) cannot depend on native field elements, whether they are from function arguments or created by zkp_var!.

For example, you cannot do the following:

#![allow(unused)]
fn main() {
#[zkp_program]
fn invalid<F: FieldSpec>(a: Field<F>, b: Field<F>) {
    let mut c = zkp_var!(0);

    // Can't use native field element b as a loop parameter!
    for i in 0..b {
        c = c + a;
    }

    c.constrain_eq(a * b);
}
}

You can, however, use loops and if statements so long as their conditions don't depend on program inputs. Programs can take things that aren't field elements in so long as they impl ZkpType.

The examples below show allowed loop and if statements:

#![allow(unused)]
fn main() {
use sunscreen::{
    types::zkp::{Field, FieldSpec}, zkp_program, zkp_var,
};
#[zkp_program]
fn loopy<F: FieldSpec>(
    a: Field<F>,
    b: Field<F>,
) {
    let mut c = zkp_var!(0);

    for _i in 0..5 {
        c = c + a;
    }

    c.constrain_eq(b);
}

#[zkp_program]
fn iffy<F: FieldSpec>(
    a: Field<F>,
    b: Field<F>,
) {
    let mut c = zkp_var!(0);

    for i in 1..5 {
        if i % 2 == 0 {
            c = c + zkp_var!(i) * a;
        } else {
            c = c - zkp_var!(i) * a;
        }
    }

    c.constrain_eq(b);
}
}

Notice that their conditions don't depend on any native field elements, so they're legal.

Encoding cost

Currently, each time you call runtime.prove and runtime.verify, we "construct" (i.e. encode) the proof statement for you. Unfortunately, this encoding process often takes a non-trivial amount of time.

In the future, we'll provide a way to compile the proof statement into a format that can be reused across proofs.

Troubleshooting

How do I debug my program?

Debugging ZKP programs is currently quite difficult. We recommend you follow standard best coding practices for now. We will soon offer a debugger that should make this process easier.

What the heck is a ProgramNode?

It's a type wrapper needed to compile your ZKP program. Internally, the #[zkp_program] macro turns all your program inputs and outputs into graph nodes — i.e. ProgramNodes. Operator inputs and outputs are actually ProgramNodes, which build up the circuit during compilation. Unfortunately, they tend to be a leaky abstraction that wind up in error messages.

Usually, these errors tell you a ProgramNode doesn't support an operation you're trying to perform. In the example below, the compiler is saying you can't compare values:

error[E0369]: binary operation `>` cannot be applied to type `ProgramNode<Field<F>>`
  --> examples/ordering_zkp/src/main.rs:13:15
   |
13 |     let b = x > y;
   |             - ^ - ProgramNode<Field<F>>
   |             |
   |             ProgramNode<Field<F>>

This can also crop up when using explicit annotations. For example, the following will fail to compile:

#![allow(unused)]
fn main() {
use sunscreen::{zkp_program, zkp_var, types::zkp::{Field, FieldSpec}};
#[zkp_program]
fn either<F: FieldSpec>(
    x: Field<F>,
    y: Field<F>,
) {
    let diff: Field<F> = x - y;     // This type annotation isn't correct!
    diff.constrain_eq(zkp_var!(0));
}
}

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 sunscreen::types::zkp::ProgramNode.

#![allow(unused)]
fn main() {
use sunscreen::{zkp_program, zkp_var, types::zkp::{Field, FieldSpec, ProgramNode}};
#[zkp_program]
fn either<F: FieldSpec>(
    x: Field<F>,
    y: Field<F>,
) {
    let diff: ProgramNode<Field<F>> = x - y;     // Fixed!
    diff.constrain_eq(zkp_var!(0));
}
}

Compiling

After you've defined a ZKP program, you'll need to compile it. The simplest way, as we saw in the first example, is to just call .compile() on the program:

use sunscreen::{
    bulletproofs::BulletproofsBackend,
    types::zkp::{Field, FieldSpec},
    zkp_program, Error, ZkpProgramFnExt
};

#[zkp_program]
fn tautology<F: FieldSpec>(x: Field<F>) {
    x.constrain_eq(x);
}

fn main() -> Result<(), Error> {
    let tautology_compiled = tautology.compile::<BulletproofsBackend>()?;
    Ok(())
}

Remember that you'll need to specify the proof system being used in the backend (e.g. BulletproofsBackend).

However, if you have multiple ZKP programs to compile, you may find it easier to invoke a full Compiler and get back an Application holding multiple programs.

use sunscreen::{
    bulletproofs::BulletproofsBackend,
    types::zkp::{Field, FieldSpec},
    zkp_program, zkp_var, Error, Compiler
};

#[zkp_program]
fn tautology<F: FieldSpec>(x: Field<F>) {
    x.constrain_eq(x);
}

#[zkp_program]
fn contradiction<F: FieldSpec>(x: Field<F>) {
    x.constrain_eq(x + zkp_var!(1));
}

fn main() -> Result<(), Error> {
    let app = Compiler::new()
        .zkp_backend::<BulletproofsBackend>()
        .zkp_program(tautology)
        .zkp_program(contradiction)
        .compile()?;

    let tautology_compiled = app.get_zkp_program(tautology);
    let contradiction_compiled = app.get_zkp_program(contradiction);
    Ok(())
}

To actually run your compiled ZKP programs, you'll need a runtime! This is covered in the next chapter.

Runtime

To create a runtime, you simply call ZkpRuntime::new, passing a ZkpBackend reference. Currently, we support Bulletproofs as the only proof backend.

use sunscreen::{
    bulletproofs::BulletproofsBackend,
    types::zkp::{BulletproofsField, Field, FieldSpec},
    zkp_program, zkp_var, Compiler, Error, ZkpRuntime,
};
fn main() -> Result<(), Error> {
let runtime = ZkpRuntime::new(BulletproofsBackend::new())?;
    Ok(())
}

Once you're created a runtime, you can:

• make a proof
• verify a proof

Proving

To make a proof, you must supply all of the arguments defined in your ZKP program function.

use sunscreen::{
    bulletproofs::BulletproofsBackend,
    types::zkp::{BulletproofsField, Field, FieldSpec},
    zkp_program, zkp_var, Compiler, Error, ZkpRuntime,
};
#[zkp_program]
fn either<F: FieldSpec>(
    #[private] x: Field<F>,
    #[public] y: Field<F>,
    #[public] z: Field<F>,
) {
    let zero = zkp_var!(0);
    let poly = (y - x) * (z - x);
    poly.constrain_eq(zero);
}
fn main() -> Result<(), Error> {
    let app = Compiler::new()
        .zkp_backend::<BulletproofsBackend>()
        .zkp_program(either)
        .compile()?;

    let either_zkp = app.get_zkp_program(either).unwrap();


// ...

let runtime = ZkpRuntime::new(BulletproofsBackend::new())?;
 
let x = BulletproofsField::from(64);
let y = BulletproofsField::from(64);
let z = BulletproofsField::from(1000);

let proof = runtime.prove(
    either_zkp, // compiled ZKP program
    vec![x],    // private inputs
    vec![y, z], // public inputs
    vec![],     // constant inputs
)?;

    Ok(())
}

Recall that zkp_program arguments should appear in order private, public, constant to match the prove call.

Excluding the compiled ZKP program, all other arguments must be passed in via a Vec.

Let's break down the arguments to runtime.prove:

1. The first argument must be the compiled ZKP program
2. The second argument must be private inputs (only viewable by the prover)
3. The third argument must be be any public inputs (which are viewable by both the prover and verifier)
4. The fourth argument must be any constant inputs (constant inputs are an advanced feature so this will often be empty!)

Notice that proof generation is a fallible operation. If you try to construct an invalid proof, the runtime will return an error, so that you don't end up trying to send an invalid proof to a verifier, only to be rejected later. This is for developer convenience; please note that security does not rely on this API decision.

ZKP proof builder

One issue you may run into is that prove accepts vectors of type I: Into<ZkpProgramInput>. In Rust, elements in a Vec must all have the same type. Consequently, if you have arguments with varying types, you'd have to convert them all to ZkpProgramInput.

However, we offer a convenient builder method for precisely this reason:

use sunscreen::{
    bulletproofs::BulletproofsBackend,
    types::zkp::{BulletproofsField, Field, FieldSpec},
    zkp_program, zkp_var, Compiler, Error, ZkpRuntime,
    ZkpProgramInput,
};
#[zkp_program]
fn eval<F: FieldSpec>(
    #[private] x: Field<F>,
    #[private] z: Field<F>,
    #[public] ys: [Field<F>; 2],
) {
    let poly = (ys[0] - x) * (ys[1] - x);
    poly.constrain_eq(z);
}
fn main() -> Result<(), Error> {
    let app = Compiler::new()
        .zkp_backend::<BulletproofsBackend>()
        .zkp_program(eval)
        .compile()?;

    let eval_zkp = app.get_zkp_program(eval).unwrap();

    let runtime = ZkpRuntime::new(BulletproofsBackend::new())?;



// ...

let x = BulletproofsField::from(64);
let z = BulletproofsField::from(0);
let ys = [BulletproofsField::from(64), BulletproofsField::from(1000)];

let proof = runtime.proof_builder(eval_zkp)
    .private_input(x)
    .private_input(z)
    .public_input(ys)
    .prove()?;

    Ok(())
}

Verifying

Once we receive a proof, we can verify it!

use sunscreen::{
    bulletproofs::BulletproofsBackend,
    types::zkp::{BulletproofsField, Field, FieldSpec},
    zkp_program, zkp_var, Compiler, Error, ZkpRuntime,
};
#[zkp_program]
fn either<F: FieldSpec>(
    #[private] x: Field<F>,
    #[public] y: Field<F>,
    #[public] z: Field<F>,
) {
    let zero = zkp_var!(0);
    let poly = (y - x) * (z - x);
    poly.constrain_eq(zero);
}
fn main() -> Result<(), Error> {
    let app = Compiler::new()
        .zkp_backend::<BulletproofsBackend>()
        .zkp_program(either)
        .compile()?;

    let either_zkp = app.get_zkp_program(either).unwrap();


// ...

let runtime = ZkpRuntime::new(BulletproofsBackend::new())?;
 
let x = BulletproofsField::from(64);
let y = BulletproofsField::from(64);
let z = BulletproofsField::from(1000);

let proof = runtime.prove(
    either_zkp, // compiled ZKP program
    vec![x],    // private inputs
    vec![y, z], // public inputs
    vec![],     // constant inputs
)?;

// Verify the proof
runtime.verify(
    either_zkp, // compiled ZKP program
    &proof,     // the proof to verify
    vec![y, z],  // public inputs
    vec![],     // constant inputs
)?;

Ok(())
}

Excluding the compiled ZKP program and proof, the remaining arguments must be passed in via a Vec.

Let's break down the arguments to runtime.verify:

1. The first argument will be the compiled ZKP program
2. The second argument is the proof that we receive from the prover
3. The third argument is any public inputs (viewable to both the prover and verifier)
4. The fourth argument is any constant inputs (constant inputs are an advanced feature so this will often be empty)

Notice that, like proof generation, verification is also a fallible operation. An Err result indicates that verification of the proof failed and the verifier should not trust the proof they were given.

ZKP verification builder

The same limitations discussed in the last chapter apply to the verify method. If you have arguments of varying types, you will find the verification builder much more convenient to use:

use sunscreen::{
    bulletproofs::BulletproofsBackend,
    types::zkp::{BulletproofsField, Field, FieldSpec},
    zkp_program, zkp_var, Compiler, Error, ZkpRuntime,
    ZkpProgramInput,
};
#[zkp_program]
fn eval<F: FieldSpec>(
    #[private] x: Field<F>,
    #[public] z: Field<F>,
    #[public] ys: [Field<F>; 2],
) {
    let poly = (ys[0] - x) * (ys[1] - x);
    poly.constrain_eq(z);
}
fn main() -> Result<(), Error> {
    let app = Compiler::new()
        .zkp_backend::<BulletproofsBackend>()
        .zkp_program(eval)
        .compile()?;

    let eval_zkp = app.get_zkp_program(eval).unwrap();

    let runtime = ZkpRuntime::new(BulletproofsBackend::new())?;



// ...

let x = BulletproofsField::from(64);
let z = BulletproofsField::from(0);
let ys = [BulletproofsField::from(64), BulletproofsField::from(1000)];

let proof = runtime.proof_builder(eval_zkp)
    .public_input(z)
    .public_input(ys)
    .private_input(x)
    .prove()?;

runtime.verification_builder(eval_zkp)
    .proof(&proof)
    .public_input(z)
    .public_input(ys)
    .verify()?;
    Ok(())
}

Serialization

So far, our examples have computed everything in one place. In practice, writing a ZKP program, proving, and verifying are often split among multiple machines.

In Sunscreen, you can serialize proofs.

Sunscreen uses serde 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 bincode since it reduces storage and network requirements by efficiently packing byte arrays.

Below is an example of serialization and deserialization of a proof:

use std::io;

use sunscreen::{
    bulletproofs::BulletproofsBackend, types::zkp::{BulletproofsField, Field, FieldSpec},
    Compiler, ZkpProgramInput, ZkpRuntime, Proof, zkp_var, zkp_program
};

#[zkp_program]
fn zkp<F: FieldSpec>(x: Field<F>, #[public] y: Field<F>) {
    x.constrain_eq(y + zkp_var!(1));
}

fn main() -> Result<(), Box<dyn std::error::Error>> {
    let app = Compiler::new()
        .zkp_backend::<BulletproofsBackend>()
        .zkp_program(zkp)
        .compile()?;
    let prog = app.get_zkp_program(zkp).unwrap();
    let runtime = ZkpRuntime::new(BulletproofsBackend::new())?;

    let x: BulletproofsField = BulletproofsField::from(1);
    let y: BulletproofsField = BulletproofsField::from(2);
let proof: Proof = runtime.prove(prog, vec![y], vec![x], vec![])?;
let serialized_proof = bincode::serialize(&proof)?;
let deserialized_proof: Proof = bincode::deserialize(&serialized_proof)?;
    Ok(())
}

As with any dependency, you'll need to add bincode as a dependency in your Cargo.toml.

To see how serialization works in practice, check out our set inclusion application.

Applications

In this section, we'll look at some less trivial ZKP programs.

Private set inclusion

Let's look at how to prove that we have a number on a given list without revealing to anyone what our number is (aka private set inclusion).

Such a program might be interesting when thinking more generally about allowlists (e.g. proving you're on a given list without revealing your identity to others). While allowlists are beyond the scope of this document, there's plenty of applications of this idea in both web2 and web3.

In this example, we'll also see how proof serialization works.

A brief diversion on file structure with serialization

In Sunscreen, you can serialize proofs. Usually, we'll define a ZKP program in one place, and share that code between both the prover and verifier. This is easily accomplished with a Cargo package with multiple binaries, or Cargo workspace if you need more flexibility. For example, the workspace might have a file structure like this:

.
├── Cargo.lock
├── Cargo.toml
├── prover
│   ├── Cargo.toml
│   └── src
│       └── main.rs
├── README.md
├── verifier
│   ├── Cargo.toml
│   └── src
│       └── main.rs
└── zkp
    ├── Cargo.toml
    └── src
        └── lib.rs

How will our algorithm work?

We'll build off ideas from My first ZKP program (where we wanted to prove that our number was on a list with 2 public numbers) for this example.

Let's say we have the following list: [element₀, element₁, ... , element_n]. If s is on the list, then that means there exists some element_i such that s = element_i. Then the equation (s - element₀)(s - element₁)...(s - element_n) must equal 0 since one of these factors (s - element_i) is 0.

Program Walkthrough

Examining our ZKP program

The ZKP program is exported from zkp/src/lib.rs:

#![allow(unused)]
fn main() {
use std::array;
use sunscreen::{types::zkp::{Field, FieldSpec}, zkp_program, zkp_var};

/// A ZKP proving a private entry is equal to one of the values in a list
#[zkp_program]
pub fn allowlist<F: FieldSpec>(
    entry: Field<F>,
    #[public] list: [Field<F>; 100],
) {
    let zero = zkp_var!(0);
    let one = zkp_var!(1);
    let mut poly = one;
    for x in list {
        poly = poly * (x - entry);
    }
    poly.constrain_eq(zero);
}

/// A default list for the prover and verifier to use: [100, 199]
pub fn default_list<F: FieldSpec>() -> [Field<F>; 100] {
    array::from_fn(|i| Field::from(100 + i as u32))
}
}

Let's briefly walk though the ZKP program allowlist now. The prover will want to show that they have some entry on a given list without revealing what exactly their entry is. Accordingly, entry is private whereas the values on the list are public. We'll need to create two native field elements within allowlist (specifically 0 and 1) so we use zkp_var to get zero and one. Our program builds off ideas from My first ZKP program so we recommend reading that section first before proceeding. Recall that to require poly to be equal to zero, we'll need to use an equality constraint (constrain_eq).

In terms of the specific list we'll be looking at, this will be default_list, where we do the appropriate conversion to get native field elements.

Prover

Let's look at how the prover would go about creating their proof and then serializing it.

The prover crate defines a binary that accepts a number on the command line and prints the serialized proof to stdout:

// Just squashed the zkp module above
mod zkp { use std::array; use sunscreen::{types::zkp::{Field, FieldSpec}, zkp_program, zkp_var}; #[zkp_program] pub fn allowlist<F: FieldSpec>( entry: Field<F>, #[public] list: [Field<F>; 100],) { let zero = zkp_var!(0); let one = zkp_var!(1); let mut poly = one; for x in list { poly = poly * (x - entry); } poly.constrain_eq(zero); } pub fn default_list<F: FieldSpec>() -> [Field<F>; 100] { array::from_fn(|i| Field::from(100 + i as u32)) } }
use std::io;
use std::error::Error;

use sunscreen::{
    bulletproofs::BulletproofsBackend, types::zkp::BulletproofsField, 
    ZkpProgramFnExt,
};

use zkp::{default_list, allowlist};

fn main() -> Result<(), Box<dyn Error>> {
    let allowlist_zkp = allowlist.compile::<BulletproofsBackend>()?;
    let runtime = allowlist.runtime::<BulletproofsBackend>()?;

    // prover's witness is the value 101
    let entry: BulletproofsField = get_first_arg()?.unwrap_or(101).into();
    let list: [BulletproofsField; 100] = default_list();

    let proof = runtime.proof_builder(&allowlist_zkp)
        .private_input(entry)
        .public_input(list)
        .prove()?;

    bincode::serialize_into(io::stdout(), &proof)?;
    Ok(())
}

fn get_first_arg() -> Result<Option<u32>, Box<dyn Error>> {
    let arg = std::env::args().nth(1).map(|s| s.parse()).transpose()?;
    Ok(arg)
}

The Prover begins by importing the stuff they're going to use.

Next, the Prover compiles the ZKP program, specifying that they'll be using Bulletproofs as the backend proof system.

To prove things, they construct a runtime, again specifying Bulletproofs as the backend proof system. Now, they're ready to create the proof!

As usual, elements need to be in the correct format (field elements—specifically we're working over whatever field Bulletproofs uses).

Then, the Prover calls runtime.proof_builder(), passing in the compiled ZKP program, their private inputs (just entry here) and any public inputs (just list here) to create a proof (using prove). Finally, the proof is serialized and printed to stdout.

Verifier

Lastly, the verifier crate defines a binary that reads a proof from stdin and exits with code 0 on success and 1 on error:

// Just squashed the zkp module above
mod zkp { use std::array; use sunscreen::{types::zkp::{Field, FieldSpec}, zkp_program, zkp_var}; #[zkp_program] pub fn allowlist<F: FieldSpec>( entry: Field<F>, #[public] list: [Field<F>; 100],) { let zero = zkp_var!(0); let one = zkp_var!(1); let mut poly = one; for x in list { poly = poly * (x - entry); } poly.constrain_eq(zero); } pub fn default_list<F: FieldSpec>() -> [Field<F>; 100] { array::from_fn(|i| Field::from(100 + i as u32)) } }
use std::io;
use std::error::Error;

use sunscreen::{
    bulletproofs::BulletproofsBackend, types::zkp::BulletproofsField,
    Proof, ZkpProgramFnExt, 
};

use zkp::{default_list, allowlist};

fn main() -> Result<(), Box<dyn Error>> {
    let allowlist_zkp = allowlist.compile::<BulletproofsBackend>()?;
    let runtime = allowlist.runtime::<BulletproofsBackend>()?;

    let proof: Proof = bincode::deserialize_from(io::stdin())?;

    let list: [BulletproofsField; 100] = default_list();
    runtime.verification_builder(&allowlist_zkp)
        .proof(&proof)
        .public_input(list)
        .verify()?;

    println!("Verified proof successfully!");
    Ok(())
}

Recall that the Verifier will have to compile the allowlist program and construct a runtime with the same backend proof system before verifying the proof.

The Verifier retrieves the serialized proof and deserializes it. They can then call runtime.verification_builder(), passing in the compiled ZKP program (allowlist_zkp), the proof received from the Prover (proof), and the public input (list) to verify the proof (using verify).

Execution

With these pieces in place, we can see serialization and deserialization in action! From the root directory:

$ cargo run -p prover 150 | cargo run -p verifier

Verified proof successfully!

The full example is on GitHub for reference.

Sudoku

We'll now walk through a less trivial proof in which we prove that we have a valid Sudoku solution, without revealing what the solution is.

Recall Sudoku is a 9x9 grid in which:

• Each of the 9 rows must contain the numbers \(1, \ldots, 9\).
• Each of the 9 columns must contain the numbers \(1, \ldots, 9\).
• Each of the 3x3 sub-squares must contain the numbers \(1, \ldots, 9\).

The user will be given a starting grid with some numbers filled in and those numbers must remain the same in their solution.

How will our algorithm work?

This example is a bit more complicated in terms of translating conditions the private inputs need to satisfy into constraints. As we'll make extensive use of polynomials and polynomial evaluation, we recommend making sure you're comfortable with the previous example before diving into this section.

At a high level, we need to take a set \(S\) of 9 squares and prove that the set is precisely the numbers 1 through 9.

For each of these sets \(S\), our strategy will be as follows: for each of the numbers \(i \in \{1, \ldots, 9\}\), construct a polynomial \( p = \prod_{s \in S} (i - s) \) and constrain \( p = 0 \). This proves that each \(i \in S\), and since \(S\) is a set of size 9, it proves that \(S = \{1, \ldots, 9 \}\).

Program walkthrough

Let's look at how to implement this.

Setup

We'll start with the necessary imports.

#![allow(unused)]
fn main() {
use sunscreen::{
    bulletproofs::BulletproofsBackend,
    types::zkp::{BulletproofsField, Field, FieldSpec},
    zkp_program, zkp_var, Error, ZkpProgramFnExt
};
}

Arguments

Next, we need to choose how to represent the board and the solution. Arrays are a natural choice.

#![allow(unused)]
fn main() {
use sunscreen::{
    bulletproofs::BulletproofsBackend,
    types::zkp::{BulletproofsField, Field, FieldSpec},
    zkp_program, zkp_var, Error, ZkpProgramFnExt
};
#[zkp_program]
fn sudoku_proof<F: FieldSpec>(
    solution: [[Field<F>; 9]; 9], // no attribute specified so this is private by default
    #[public] board: [[Field<F>; 9]; 9],
) { }
}

We'll let a zero in the starting board represent an empty square that the solution has to fill in.

We declare sudoku_proof as a ZKP program with the appropriate attribute (#[zkp_program]). Under the hood, we're actually working over a field in our ZKP program so we need to specify that the given board and provided solution contain fields elements (using Field).

The board will need to be viewable to both the prover and verifier (which is why we use #[public]) whereas the solution will be kept private to the prover.

Set equality constraints

Notice we have a common constraint that a set of nine numbers is precisely the set \(\{1, \ldots, 9\}\). Since our ZKP programs are just normal Rust functions, we have the full power of the Rust programming language at our disposal! So, let's make a function to reuse for each set of numbers that needs to satisfy this constraint.

#![allow(unused)]
fn main() {
use sunscreen::{
    bulletproofs::BulletproofsBackend,
    types::zkp::{BulletproofsField, Field, FieldSpec},
    zkp_program, zkp_var, Error, ZkpProgramFnExt
};
#[zkp_program]
fn sudoku_proof<F: FieldSpec>(
    solution: [[Field<F>; 9]; 9],
    #[public] board: [[Field<F>; 9]; 9],
) {
    let zero = zkp_var!(0);

    let assert_unique_numbers = |squares| {
        for i in 1..=9 {
            let mut circuit = zkp_var!(1);
            for s in squares {
                circuit = circuit * (zkp_var!(i) - s);
            }
            circuit.constrain_eq(zero);
        }
    };
// N.B. below is just here for constraining type of closure above
    for row in solution {
        assert_unique_numbers(row);
    }
}
}

For each number in \(1, \ldots, 9\), we'll need to verify that number is indeed on the list of squares. If squares is an array of length nine, this shows set equality!

Since we need to create field elements within our ZKP program sudoku_proof, we make use of zkp_var for 0 and 1...9.

To require circuit to be equal to zero, we need to specify an equality constraint (done using constrain_eq). Again, we see that constraining a polynomial to equal zero is a very useful pattern.

All that's left now is to make sure our function satisfies the bulletpoints mentioned in the intro.

#![allow(unused)]
fn main() {
use sunscreen::{
    bulletproofs::BulletproofsBackend,
    types::zkp::{BulletproofsField, Field, FieldSpec},
    zkp_program, zkp_var, Error, ZkpProgramFnExt
};
#[zkp_program]
fn sudoku_proof<F: FieldSpec>(
    solution: [[Field<F>; 9]; 9],
    #[public] board: [[Field<F>; 9]; 9],
) {
    let zero = zkp_var!(0);

    let assert_unique_numbers = |squares| {
        for i in 1..=9 {
            let mut circuit = zkp_var!(1);
            for s in squares {
                circuit = circuit * (zkp_var!(i) - s);
            }
            circuit.constrain_eq(zero);
        }
    };

    // Checks rows contain every number from 1 to 9
    for row in solution {
        assert_unique_numbers(row);
    }

    // Checks columns contain each number from 1 to 9
    for col in 0..9 {
        let column = solution.map(|r| r[col]);
        assert_unique_numbers(column);
    }

    // Checks squares contain each number from 1 to 9
    for i in 0..3 {
        for j in 0..3 {
            let rows = &solution[(i * 3)..(i * 3 + 3)];

            let square = rows.iter().map(|s| &s[(j * 3)..(j * 3 + 3)]);

            let flattened_sq = square
                .flatten()
                .copied()
                .collect::<Vec<_>>()
                .try_into()
                .unwrap_or([zero; 9]);

            assert_unique_numbers(flattened_sq);
        }
    }
}
}

Starting board constraints

The final part of proving we have a valid Sudoku solution is making sure that the solution sticks to the starting board constraints.

#![allow(unused)]
fn main() {
use sunscreen::{
    bulletproofs::BulletproofsBackend,
    types::zkp::{BulletproofsField, Field, FieldSpec},
    zkp_program, zkp_var, Error, ZkpProgramFnExt
};
#[zkp_program]
fn sudoku_proof<F: FieldSpec>(
    solution: [[Field<F>; 9]; 9],
    #[public] board: [[Field<F>; 9]; 9],
) {
    let zero = zkp_var!(0);
// Proves that the solution matches up with the puzzle where applicable
for i in 0..9 {
    for j in 0..9 {
        let square = solution[i][j];
        let constraint = board[i][j];
        (constraint * (constraint - square)).constrain_eq(zero);
    }
}
}
}

Here, we're using the fact that \(a \cdot b = 0\) implies \(a = 0\) or \(b = 0\). This implies that each square in the starting board was either filled in or remains the same in the solution.

Prove and verify

Let's see this in action!

use sunscreen::{
    bulletproofs::BulletproofsBackend,
    types::zkp::{BulletproofsField, Field, FieldSpec},
    zkp_program, zkp_var, Error, ZkpProgramFnExt
};

#[zkp_program]
fn sudoku_proof<F: FieldSpec>(
    solution: [[Field<F>; 9]; 9],
    #[public] board: [[Field<F>; 9]; 9],
) {
    let zero = zkp_var!(0);

    let assert_unique_numbers = |squares| {
        for i in 1..=9 {
            let mut circuit = zkp_var!(1);
            for s in squares {
                circuit = circuit * (zkp_var!(i) - s);
            }
            circuit.constrain_eq(zero);
        }
    };

    // Checks rows contain every number from 1 to 9
    for row in solution {
        assert_unique_numbers(row);
    }

    // Checks columns contain each number from 1 to 9
    for col in 0..9 {
        let column = solution.map(|r| r[col]);
        assert_unique_numbers(column);
    }

    // Checks squares contain each number from 1 to 9
    for i in 0..3 {
        for j in 0..3 {
            let rows = &solution[(i * 3)..(i * 3 + 3)];

            let square = rows.iter().map(|s| &s[(j * 3)..(j * 3 + 3)]);

            let flattened_sq = square
                .flatten()
                .copied()
                .collect::<Vec<_>>()
                .try_into()
                .unwrap_or([zero; 9]);

            assert_unique_numbers(flattened_sq);
        }
    }

    // Proves that the solution matches up with the puzzle where applicable
    for i in 0..9 {
        for j in 0..9 {
            let square = solution[i][j];
            let constraint = board[i][j];
            (constraint * (constraint - square)).constrain_eq(zero);
        }
    }
}

fn main() -> Result<(), Error> {
    let compiled_sudoku_proof = sudoku_proof.compile::<BulletproofsBackend>()?;
    let runtime = sudoku_proof.runtime::<BulletproofsBackend>()?;

    let ex_board = [
        [0, 7, 0, 0, 2, 0, 0, 4, 6],
        [0, 6, 0, 0, 0, 0, 8, 9, 0],
        [2, 0, 0, 8, 0, 0, 7, 1, 5],
        [0, 8, 4, 0, 9, 7, 0, 0, 0],
        [7, 1, 0, 0, 0, 0, 0, 5, 9],
        [0, 0, 0, 1, 3, 0, 4, 8, 0],
        [6, 9, 7, 0, 0, 2, 0, 0, 8],
        [0, 5, 8, 0, 0, 0, 0, 6, 0],
        [4, 3, 0, 0, 8, 0, 0, 7, 0],
    ];

    let ex_sol = [
        [8, 7, 5, 9, 2, 1, 3, 4, 6],
        [3, 6, 1, 7, 5, 4, 8, 9, 2],
        [2, 4, 9, 8, 6, 3, 7, 1, 5],
        [5, 8, 4, 6, 9, 7, 1, 2, 3],
        [7, 1, 3, 2, 4, 8, 6, 5, 9],
        [9, 2, 6, 1, 3, 5, 4, 8, 7],
        [6, 9, 7, 4, 1, 2, 5, 3, 8],
        [1, 5, 8, 3, 7, 9, 2, 6, 4],
        [4, 3, 2, 5, 8, 6, 9, 7, 1],
    ];

    let solution = ex_sol.map(|a| a.map(BulletproofsField::from)); // recall we need field elements here

    let board = ex_board.map(|a| a.map(BulletproofsField::from)); //  recall we need field elements here

    let proof = runtime.proof_builder(&compiled_sudoku_proof)
        .private_input(solution)
        .public_input(board)
        .prove()?;

    runtime.verification_builder(&compiled_sudoku_proof)
        .proof(&proof)
        .public_input(board)
        .verify()?;

    Ok(())
}

After specifying the backend proof system (BulletproofsBackend), we compile our sudoku_proof program and save the runnable program as compiled_sudoku_proof. We then construct a runtime so we can go on to proving and verifying things.

We define a starting Sudoku board as a public input (ex_board) and a valid solution (ex_sol) as a private input. Since ZKP programs operate on field elements, we use map to get board and solution which are now in the correct format.

Once that's done, we're ready to create our proof! We call runtime.proof_builder, passing in our compiled ZKP program, our private inputs (just solution), any public inputs (just board) to create a proof (via prove).

To verify the proof, we call runtime.verification_builder, passing in the compiled ZKP program, the proof received, and any public inputs (just the board) to verify if the proof is valid (via verify).

We see that verification was successful (as expected)!

FAQ

Why did you create your own ZKP compiler?

We created our own ZKP compiler mainly to ensure compatibility with our FHE compiler—existing ZKP compilers were not designed with FHE's needs in mind.

How will this fit in with Sunscreen's FHE compiler?

Our ZKP compiler is currently offered as a standalone product.

In the future, Sunscreen's FHE compiler and ZKP compiler will be linked together so that you can prove statements about FHE-encrypted inputs! This is especially important in trustless settings like web3. You will still be able to use either of these offerings independently if desired.

As part of linking together our FHE and ZKP compiler, we're working on an implementation of a proof system that allows us to (somewhat efficiently) show that FHE ciphertexts are well-formed. This proof system is called Short Discrete Log Proofs for FHE and Ring-LWE Ciphertexts (SDLP). Once we have linked our FHE compiler with SDLP and SDLP with our ZKP compiler, you'll be able to use our FHE and ZKP compilers together.

Why Bulletproofs as the proof backend? Aren't there more performant proof systems?

As mentioned earlier, our ZKP compiler was designed with the end goal of it being used in conjunction with our FHE compiler.

Before we can prove arbitrary statements about our FHE-encrypted inputs, we need to prove our FHE ciphertext is well-formed. The proof system we use for this is Short Discrete Log Proofs for FHE and Ring-LWE Ciphertexts (SDLP); you can track our implementation progress here. Both Bulletproofs and SDLP use Pedersen commitments constructed of Ristretto group elements, which allows us to prove secret inputs to both proofs are the same. For this reason, we decided to first start with support of Bulletproofs in our ZKP compiler as it meant we could release something sooner for developers to try out. Additionally, while Bulletproofs is far from being the most performant SNARK, SDLP prover and verifier times dwarf that of Bulletproofs so we have chosen to focus our initial efforts on optimizations for SDLP.

What are your future plans?

Beyond integration with our FHE compiler, we're considering adding support for other proof backends and arithmetizations.

Advanced

Now that you've gotten the basics down, let's dive into some more complex topics.

Writing even better ZKP programs

In this section, we're going to cover a few techniques that allow you to get the most out of your ZKP programs.

Specifically, we'll look at:

• Creating gadgets to improve performance and be re-used across programs (gadgets also allow you to do stuff like division which isn't native to R1CS!)
• Using constant (instead of public) inputs to improve performance where possible
• Creating your own types for certain use cases

Gadgets

Gadgets in ZKPs are analogous to functions in programming languages. Like functions, they can be invoked from within a ZKP, take inputs, and compute outputs. Gadgets can also call other gadgets.

We refer to the inputs of the gadget as "gadget inputs". With these inputs, the gadget then computes "hidden inputs" which will likely (but not always) be the gadget outputs. They're "hidden" in the sense that they're not directly passed into prove or verify but instead snuck into the R1CS constraints outside of the argument list; they're "inputs" in the sense that they will be viewed as private values that will be fed into your ZKP program. It is up to the gadget implementation to prove that the hidden inputs are calculated correctly.

Why you might want to create a gadget

There a few reasons you might be interested in creating a gadget:

• To fine-tune/improve performance
• To re-use them across different ZKP programs
• To accomplish things not native to R1CS like division

How to create a gadget

You can create your own gadgets by implementing the Gadget trait:¹

#![allow(unused)]
fn main() {
use sunscreen::{Result, types::zkp::{BigInt, NodeIndex}};
use std::any::Any;
pub trait Gadget: Any + Send + Sync {
    /// Generate the circuit that proves the hidden inputs are calculated correctly
    /// and return the gadget outputs.
    fn gen_circuit(
        &self,
        gadget_inputs: &[NodeIndex],
        hidden_inputs: &[NodeIndex],
    ) -> Vec<NodeIndex>;

    /// Compute the ZKP hidden inputs from the gadget inputs
    fn compute_hidden_inputs(&self, gadget_inputs: &[BigInt]) -> Result<Vec<BigInt>>;

    /// Expected # of gadget inputs (this should be constant for a given implementation)
    fn gadget_input_count(&self) -> usize;

    /// Expected # of ZKP hidden inputs/gadget outputs (this should be constant for a given implementation)
    fn hidden_input_count(&self) -> usize;
}
}

You may have noticed that the Field<F> type does not occur in the gadget definition. This is mostly an implementation detail, as we need to package up various gadgets as dynamic trait objects. Instead, you work with BigInts which are the internal representation of a native field. If your gadget relies on any context specific to the ZKP backend, you'll have to provide that context to the gadget. This is demonstrated in the example below.

Warning: Even though we're working with BigInt values, the gadget must return values less than the field modulus otherwise proof generation will fail. You can pass the field modulus as an argument to the gadget's constructor and provide this value via FieldSpec::FIELD_MODULUS. See example.

Example

Let's walk through an example of a gadget that computes the multiplicative inverse of a native field element. Here, the gadget input will be some native field element \(x\) and the calculated hidden input will be \(x^{-1}\). The gadget output is just the hidden input in this case.²

Definition

The inverse calculation is dependent on the field modulus, so we'll parameterize the gadget with this context:

#![allow(unused)]
fn main() {
use sunscreen::types::zkp::BigInt;

pub struct Inverse {
    field_modulus: BigInt,
}
}

Counting inputs

Let's get the easy stuff out of the way. To calculate an inverse, we take in one native field element (this will be the value to be inverted) and return one native field element (this will be the inverse). Thus:

#![allow(unused)]
fn main() {
use sunscreen::{
    types::zkp::{BigInt, Gadget, NodeIndex},
    ZkpResult,
};
pub struct Inverse {
    field_modulus: BigInt,
}
impl Gadget for Inverse {

    fn gadget_input_count(&self) -> usize {
        1
    }

    fn hidden_input_count(&self) -> usize {
        1
    }

    fn compute_hidden_inputs(&self, gadget_inputs: &[BigInt]) -> ZkpResult<Vec<BigInt>> {
        todo!()
    }

    fn gen_circuit(
        &self,
        gadget_inputs: &[NodeIndex],
        hidden_inputs: &[NodeIndex],
    ) -> Vec<NodeIndex> {
        todo!()
    }
}
}

Computing inputs

Next, we compute the hidden input, which in this case is the inverse of the single gadget input. There's one very important detail to keep in mind when computing hidden inputs—to prevent timing (side channel) attacks, your implementation must run in constant time!

#![allow(unused)]
fn main() {
use sunscreen::{
    types::zkp::{BigInt, Gadget, NodeIndex},
    ZkpError, ZkpResult,
};
pub struct Inverse {
    field_modulus: BigInt,
}
impl Gadget for Inverse {

    fn gadget_input_count(&self) -> usize {
        1
    }

    fn hidden_input_count(&self) -> usize {
        1
    }

fn compute_hidden_inputs(&self, gadget_inputs: &[BigInt]) -> ZkpResult<Vec<BigInt>> {
    let x = gadget_inputs[0];

    if x == BigInt::ZERO {
        return Err(ZkpError::gadget_error("Cannot take inverse of zero."));
    }
    if self.field_modulus == BigInt::ZERO {
        return Err(ZkpError::gadget_error(
            "Cannot have a finite field of zero size.",
        ));
    }

    // Note: BigInt::inverse_fp runs in constant time
    let x_inv = x.inverse_fp(&self.field_modulus);

    Ok(vec![x_inv])
}

    fn gen_circuit(
        &self,
        gadget_inputs: &[NodeIndex],
        hidden_inputs: &[NodeIndex],
    ) -> Vec<NodeIndex> {
        todo!()
    }
}
}

Generating the circuit

Finally, we need to produce the circuit proving that the hidden inputs were calculated correctly.

#![allow(unused)]
fn main() {
use sunscreen::{
    types::zkp::{BigInt, Gadget, NodeIndex},
    zkp::{ZkpContextOps, with_zkp_ctx},
    ZkpError, ZkpResult,
};
pub struct Inverse {
    field_modulus: BigInt,
}
impl Gadget for Inverse {

    fn gadget_input_count(&self) -> usize {
        1
    }

    fn hidden_input_count(&self) -> usize {
        1
    }

    fn compute_hidden_inputs(&self, gadget_inputs: &[BigInt]) -> ZkpResult<Vec<BigInt>> {
        todo!()
    }

fn gen_circuit(
    &self,
    gadget_inputs: &[NodeIndex],
    hidden_inputs: &[NodeIndex],
) -> Vec<NodeIndex> {
   let x = gadget_inputs[0];
   let x_inv = hidden_inputs[0];

   with_zkp_ctx(|ctx| {
       // Assert x * x^-1 == 1
       let prod = ctx.add_multiplication(x, x_inv);
       ctx.add_constraint(prod, &BigInt::ONE);
   });

   vec![x_inv]
}
}
}

The proof that the inverse was calculated properly is quite simple in this case; we just need to constrain that the product of the gadget input and its inverse is equal to one. The with_zkp_ctx call is how we insert these constraints into the graph context. Finally, we return the inverse as the gadget output.

Invoking the gadget

To use our gadget, we use the sunscreen::invoke_gadget function. This function returns raw graph node indices, so library authors are encouraged to write a wrapper function for use in ZKP program functions.

#![allow(unused)]
fn main() {
use sunscreen::{
    invoke_gadget,
    types::zkp::{BigInt, Gadget, Field, FieldSpec, NodeIndex, ProgramNode},
    zkp::{ZkpContextOps, with_zkp_ctx},
    zkp_program, zkp_var, ZkpError, ZkpResult,
};
pub struct Inverse {
    field_modulus: BigInt,
}
impl Gadget for Inverse {
    fn gadget_input_count(&self) -> usize {
        1
    }
    fn hidden_input_count(&self) -> usize {
        1
    }
    fn compute_hidden_inputs(&self, gadget_inputs: &[BigInt]) -> ZkpResult<Vec<BigInt>> {
        let x = gadget_inputs[0];
    
        if x == BigInt::ZERO {
            return Err(ZkpError::gadget_error("Cannot take inverse of zero."));
        }
        if self.field_modulus == BigInt::ZERO {
            return Err(ZkpError::gadget_error(
                "Cannot have a finite field of zero size.",
            ));
        }
    
        // Note: BigInt::inverse_fp runs in constant time
        let x_inv = x.inverse_fp(&self.field_modulus);
    
        Ok(vec![x_inv])
    }
    fn gen_circuit(
        &self,
        gadget_inputs: &[NodeIndex],
        hidden_inputs: &[NodeIndex],
    ) -> Vec<NodeIndex> {
       let x = gadget_inputs[0];
       let x_inv = hidden_inputs[0];
    
       with_zkp_ctx(|ctx| {
           // Assert x * x^-1 == 1
           let prod = ctx.add_multiplication(x, x_inv);
           ctx.add_constraint(prod, &BigInt::ONE);
       });
    
       vec![x_inv]
    }
}
pub fn inverse<F: FieldSpec>(
    x: ProgramNode<Field<F>>
) -> ProgramNode<Field<F>> {
    let gadget = Inverse { field_modulus: F::FIELD_MODULUS };
    let x_inv_ids = invoke_gadget(gadget, x.ids);
    ProgramNode::new(&x_inv_ids)
}

#[zkp_program]
fn use_inverse<F: FieldSpec>(a: Field<F>) {
    let a_inv = inverse(a);
    let one = zkp_var!(1);
    (a * a_inv).constrain_eq(one);
}
}

Gadgets are a very useful tool for building up functionality to be reused across ZKPs. However, because hidden input calculations need to be constant time, gadgets need to be written very carefully.

If you'd like to see a real example of the utility of gadgets, check out the source of how Field::constrain_ge_bounded is implemented.

Constant inputs

In general, we recommend sticking with #[private] and #[public] argument types.

Why you might want to use constant inputs

However, if you find that you're using a fixed public value as a ZKP program input, you might want to consider using the #[constant] argument type instead of #[public]. Often times, this will give you a performance boost (you'll see why below).

However, there is a trade-off in that constant inputs must always be encoded. Currently, our ZkpRuntime only offers prove() and verify() methods, but in the future we may offer a jit() method, with all public inputs already encoded. In this scenario, constant inputs would still have to be encoded on every jitted.verify() call.

Furthermore, constant inputs are fundamentally incompatible with any proof system requiring a trusted setup (as in you would have to re-run the trusted setup process).

How to use constant inputs

It's pretty straightforward to use constant inputs, simply use the #[constant] attribute for the relevant arguments you want to be treated as constants.

An example

For example, let's say you've written the following ZKP to evaluate a polynomial on private/secret coefficients:

#![allow(unused)]
fn main() {
use sunscreen::{
    bulletproofs::BulletproofsBackend,
    types::zkp::{BulletproofsField, Field, FieldSpec},
    zkp_program, zkp_var, Compiler, Error, ZkpProgramInput, ZkpRuntime,
};
#[zkp_program]
fn evaluate_polynomial<F: FieldSpec>(
    coefficients: [Field<F>; 100], // private
    #[public] point: Field<F>,
    #[public] expected: Field<F>,
) {
    let mut evaluation = zkp_var!(0);
    let mut power = zkp_var!(1);
    for coeff in coefficients {
        evaluation = evaluation + coeff * power;
        power = power * point;
    }

    evaluation.constrain_eq(expected);
}
}

Tracing

Let's further suppose that your program works correctly but that you are not happy with the performance. The first thing you can do to troubleshoot your ZKP performance is to enable tracing¹.

If you run this ZKP program on the polynomial with coefficients 1,...,100 evaluated at the point 2, you'll see a trace like the following:

[TRACE sunscreen_runtime::runtime] Starting JIT (prover)...
[TRACE sunscreen_runtime::runtime] Prover JIT time 0.002542035s
[TRACE sunscreen_runtime::runtime] Starting backend prove...
[TRACE sunscreen_zkp_backend::bulletproofs] Bulletproofs encode time 0.002508913s
[TRACE sunscreen_zkp_backend::bulletproofs] Metrics {
        multipliers: 249,
        constraints: 399,
        phase_one_constraints: 399,
        phase_two_constraints: 0,
    }
[TRACE sunscreen_zkp_backend::bulletproofs] Bulletproofs prover time 0.254062677s
[TRACE sunscreen_runtime::runtime] Starting JIT (verifier)
[TRACE sunscreen_runtime::runtime] Verifier JIT time 0.001074441s
[TRACE sunscreen_runtime::runtime] Starting backend verify...
[TRACE sunscreen_zkp_backend::bulletproofs] Starting backend verify...
[TRACE sunscreen_zkp_backend::bulletproofs] Bulletproofs encode time 0.001557964s
[TRACE sunscreen_zkp_backend::bulletproofs] Bulletproofs verify time 0.022426849s

That's weird; we only have one constrain_eq call, but there are 399 constraints in the proof. What's up with that?

Constant inputs

When we arithmetize your program, there's actually a lot of extra constraints that get added to the low level R1CS representation.

Normally, the number of constraints \(n\) increase linearly with the number of multiplication operations, as multiplication is essentially represented as a dot product where the vectors contain the inputs to all multiplication gates in the constraint system.

Constant inputs are instead placed directly into a weights matrix, and these factors can be applied directly to variables, rather than requiring additional multiplication gates that increase the factor \(n\).

If we change the argument types from #[public] to #[constant] and rerun the trace, we'll see a big improvement:

[TRACE sunscreen_runtime::runtime] Starting JIT (prover)...
[TRACE sunscreen_runtime::runtime] Prover JIT time 0.002529488s
[TRACE sunscreen_runtime::runtime] Starting backend prove...
[TRACE sunscreen_zkp_backend::bulletproofs] Bulletproofs encode time 0.001372845s
[TRACE sunscreen_zkp_backend::bulletproofs] Metrics {
        multipliers: 50,
        constraints: 1,
        phase_one_constraints: 1,
        phase_two_constraints: 0,
    }
[TRACE sunscreen_zkp_backend::bulletproofs] Bulletproofs prover time 0.057199442s
[TRACE sunscreen_runtime::runtime] Starting JIT (verifier)
[TRACE sunscreen_runtime::runtime] Verifier JIT time 0.001072157s
[TRACE sunscreen_runtime::runtime] Starting backend verify...
[TRACE sunscreen_zkp_backend::bulletproofs] Starting backend verify...
[TRACE sunscreen_zkp_backend::bulletproofs] Bulletproofs encode time 0.001272397s
[TRACE sunscreen_zkp_backend::bulletproofs] Bulletproofs verify time 0.007118962s

Because the only multiplications happen with constants, the only constraint in the R1CS circuit is the constrain_eq call. Also notice both the prover and verifier times have gone down dramatically.

Custom ZKP types

So far, all of our ZKP program arguments have had type Field<F>. However, this doesn't have to be the case! You can use other argument types, as long as they implement the ZkpType trait.

We've seen throughout the documentation that polynomials are incredibly useful for expressing constraints. So let's make a custom ZKP type that makes polynomials easier to use!

Motivating the need for custom ZKP types

In this section we'll see how to define a polynomial type.

Our polynomials will exist in the quotient ring \(\mathbb{Z}[x]/(x^N + 1) \). Polynomial quotient rings are very common in lattice cryptography (and thus FHE¹), so this is a structure we're particularly interested in as we think about linking together our FHE and ZKP compilers.²

In our polynomial quotient ring, we're able to add and multiply polynomials together. However, arithmetic behaves slightly differently here. Namely, the degree of the polynomial will wrap around N (the coefficients won't wrap however). Let's explain this in a bit more detail.

Polynomials \(p(x) \in \mathbb{Z}/(x^N + 1)\) behave just like they do in \(\mathbb{Z}[x]\), but they are reduced modulo \(x^N + 1\). This is similar to modular/clock arithmetic, where numbers in \(\mathbb{Z}_q\) behave just like those in \(\mathbb{Z}\) but you reduce numbers \(\mod q\). For example, 7 in \(\mathbb{Z}_3\) wraps around to become 1.

The only difference is here is that you take the remainder of \(p(x)\) divided by \(x^N + 1\). Long division with polynomials is typically rather tedious, but lucky for us, the divisor polynomial \(x^N + 1\) has a really nice property. All you have to do is replace every factor of \(x^N\) with \(-1\) in \(p(x)\)! That is, for every term with an exponent \(m > N\), reduce the exponent to \(m \mod N\) and stick a minus sign in front of the coefficient.

For example, suppose \(p(x) = (x^4 - 4)\) and \(q(x) = (x^2 - 3)\) are polynomials in \(\mathbb{Z}[x]/(x^5 + 1)\). Then

\[ \begin{align*} p(x) * q(x) &= (x^4 - 4) * (x^2 - 3) \\ &= x^6 - 3x^4 - 4x^2 + 12 \\ &= -x - 3x^4 - 4x^2 + 12 \\ &= -3x^4 - 4x^2 - x + 12 \\ \end{align*} \]

Type definition

Let's get our imports out of the way; there are quite a few for implementing a custom ZKP type!

#![allow(unused)]
fn main() {
use sunscreen::{
    bulletproofs::BulletproofsBackend,
    types::zkp::{
        AddVar, BigInt, BulletproofsField, Coerce, MulVar, Field, FieldSpec,
        NumFieldElements, ProgramNode, SubVar, ToNativeFields,
    },
    zkp::{with_zkp_ctx, ZkpContextOps},
    zkp_program, zkp_var, Compiler, Error,
    TypeName, ZkpBackend, ZkpRuntime,
};
}

Next, we'll define the polynomial type. Our polynomial will actually exist in the quotient ring \(\mathbb{Z}[x]/(x^N + 1) \).

We represent the polynomial here as an array of coefficients, ordered from least significant (smallest degree) to most significant (largest degree).

use sunscreen::{ bulletproofs::BulletproofsBackend, types::zkp::{ AddVar, BigInt, BulletproofsField, Coerce, MulVar, Field, FieldSpec, NumFieldElements, ProgramNode, SubVar, ToNativeFields, }, zkp::{with_zkp_ctx, ZkpContextOps}, zkp_program, zkp_var, Compiler, Error, TypeName, ZkpBackend, ZkpRuntime, };

#[derive(Debug, Copy, Clone, TypeName)]
pub struct Polynomial<F: FieldSpec, const N: usize> {
    coefficients: [Field<F>; N],
}

Implementing ZkpType

To use our Polynomial in ZKP programs, we have to satisfy the Polynomial: ZkpType constraint. This is equivalent to providing impls for TypeName, NumFieldElements, and ToNativeFields.

The first we were able to derive on the type definition. The second one is trivial; our polynomial has N field elements, so NUM_NATIVE_FIELD_ELEMENTS is simply N:

#![allow(unused)]
fn main() {
use sunscreen::{ bulletproofs::BulletproofsBackend, types::zkp::{ AddVar, BigInt, BulletproofsField, Coerce, MulVar, Field, FieldSpec, NumFieldElements, ProgramNode, SubVar, ToNativeFields, }, zkp::{with_zkp_ctx, ZkpContextOps}, zkp_program, zkp_var, Compiler, Error, TypeName, ZkpBackend, ZkpRuntime, };
#[derive(Debug, Copy, Clone)] pub struct Polynomial<F: FieldSpec, const N: usize> { coefficients: [Field<F>; N], }
impl<F: FieldSpec, const N: usize> sunscreen::types::TypeName for Polynomial<F, N> { fn type_name() -> sunscreen::types::Type { sunscreen::types::Type { name: String::from("Polynomial"), ..Field::<F>::type_name() } } }

impl<F: FieldSpec, const N: usize> NumFieldElements for Polynomial<F, N> {
    const NUM_NATIVE_FIELD_ELEMENTS: usize = N;
}
}

The last one is also fairly trivial! We just need to package up our representation into an ordered list of the BigInts underlying the Field<F>.

#![allow(unused)]
fn main() {
use sunscreen::{ bulletproofs::BulletproofsBackend, types::zkp::{ AddVar, BigInt, BulletproofsField, Coerce, MulVar, Field, FieldSpec, NumFieldElements, ProgramNode, SubVar, ToNativeFields, }, zkp::{with_zkp_ctx, ZkpContextOps}, zkp_program, zkp_var, Compiler, Error, TypeName, ZkpBackend, ZkpRuntime, };
#[derive(Debug, Copy, Clone)] pub struct Polynomial<F: FieldSpec, const N: usize> { coefficients: [Field<F>; N], }
impl<F: FieldSpec, const N: usize> sunscreen::types::TypeName for Polynomial<F, N> { fn type_name() -> sunscreen::types::Type { sunscreen::types::Type { name: String::from("Polynomial"), ..Field::<F>::type_name() } } }

impl<F: FieldSpec, const N: usize> ToNativeFields for Polynomial<F, N> {
    fn to_native_fields(&self) -> Vec<BigInt> {
        self.coefficients.map(|x| x.val).into_iter().collect()
    }
}
}

These returned values must be less than F::FIELD_MODULUS, or users will get an out of range error.

Implementing arithmetic

If you try to use the polynomial now, you'll find it is not particularly useful. We need to implement some arithmetic traits to be able to add, subtract, and multiply elements of this type together. To be specific, we need to implement types::zkp{AddVar, SubVar, MulVar} respectively.³

But first, we need to briefly touch on some implementation details of our compiler. We represent your compiled ZKP program as a graph of program nodes. A ProgramNode<T> holds type information in T, but otherwise contains a single ids: &[NodeIndex] field, which contains graph node indices. These ids are how we refer to nodes in the arithmetic circuit underlying the ZKP program. While native field elements will always have just one node index, others may contain more. In fact, this is precisely what we specified above when implementing NumFieldElements! Namely, that our polynomial variables will contain N node indices.

Also, recall from the previous section that with_zkp_ctx is the function we use to add operations to the graph context. The graph ctx variable contains the arithmetic circuit being constructed as we compile a user's program, and with it we can add operations like addition, subtraction, and multiplication. Note that you cannot nest calls to with_zkp_ctx, or you'll get a panic!

Addition is straightforward as we just add the corresponding coefficients together:

#![allow(unused)]
fn main() {
use sunscreen::{ bulletproofs::BulletproofsBackend, types::zkp::{ AddVar, BigInt, BulletproofsField, Coerce, MulVar, Field, FieldSpec, NumFieldElements, ProgramNode, SubVar, ToNativeFields, }, zkp::{with_zkp_ctx, ZkpContextOps}, zkp_program, zkp_var, Compiler, Error, TypeName, ZkpBackend, ZkpRuntime, };
#[derive(Debug, Copy, Clone)] pub struct Polynomial<F: FieldSpec, const N: usize> { coefficients: [Field<F>; N], }
impl<F: FieldSpec, const N: usize> sunscreen::types::TypeName for Polynomial<F, N> { fn type_name() -> sunscreen::types::Type { sunscreen::types::Type { name: String::from("Polynomial"), ..Field::<F>::type_name() } } }
impl<F: FieldSpec, const N: usize> NumFieldElements for Polynomial<F, N> { const NUM_NATIVE_FIELD_ELEMENTS: usize = N; }
impl<F: FieldSpec, const N: usize> ToNativeFields for Polynomial<F, N> { fn to_native_fields(&self) -> Vec<BigInt> { self.coefficients.map(|x| x.val).into_iter().collect() } }

impl<F: FieldSpec, const N: usize> AddVar for Polynomial<F, N> {
    fn add(lhs: ProgramNode<Self>, rhs: ProgramNode<Self>) -> ProgramNode<Self> {
        let mut coeff_node_indices = vec![];

        with_zkp_ctx(|ctx| {
            for (left, right) in lhs.ids.iter().zip(rhs.ids) {
                coeff_node_indices.push(ctx.add_addition(*left, *right));
            }
        });

        Self::coerce(&coeff_node_indices)
    }
}
}

Similarly, for subtraction:

#![allow(unused)]
fn main() {
use sunscreen::{ bulletproofs::BulletproofsBackend, types::zkp::{ AddVar, BigInt, BulletproofsField, Coerce, MulVar, Field, FieldSpec, NumFieldElements, ProgramNode, SubVar, ToNativeFields, }, zkp::{with_zkp_ctx, ZkpContextOps}, zkp_program, zkp_var, Compiler, Error, TypeName, ZkpBackend, ZkpRuntime, };
#[derive(Debug, Copy, Clone)] pub struct Polynomial<F: FieldSpec, const N: usize> { coefficients: [Field<F>; N], }
impl<F: FieldSpec, const N: usize> sunscreen::types::TypeName for Polynomial<F, N> { fn type_name() -> sunscreen::types::Type { sunscreen::types::Type { name: String::from("Polynomial"), ..Field::<F>::type_name() } } }
impl<F: FieldSpec, const N: usize> NumFieldElements for Polynomial<F, N> { const NUM_NATIVE_FIELD_ELEMENTS: usize = N; }
impl<F: FieldSpec, const N: usize> ToNativeFields for Polynomial<F, N> { fn to_native_fields(&self) -> Vec<BigInt> { self.coefficients.map(|x| x.val).into_iter().collect() } }

impl<F: FieldSpec, const N: usize> SubVar for Polynomial<F, N> {
    fn sub(lhs: ProgramNode<Self>, rhs: ProgramNode<Self>) -> ProgramNode<Self> {
        let mut coeff_node_indices = vec![];

        with_zkp_ctx(|ctx| {
            for (left, right) in lhs.ids.iter().zip(rhs.ids) {
                coeff_node_indices.push(ctx.add_subtraction(*left, *right));
            }
        });

        Self::coerce(&coeff_node_indices)
    }
}
}

Multiplication is a little more involved⁴, but generally we just follow the logic described in the quotient ring description above.

#![allow(unused)]
fn main() {
use sunscreen::{ bulletproofs::BulletproofsBackend, types::zkp::{ AddVar, BigInt, BulletproofsField, Coerce, MulVar, Field, FieldSpec, NumFieldElements, ProgramNode, SubVar, ToNativeFields, }, zkp::{with_zkp_ctx, ZkpContextOps}, zkp_program, zkp_var, Compiler, Error, TypeName, ZkpBackend, ZkpRuntime, };
#[derive(Debug, Copy, Clone)] pub struct Polynomial<F: FieldSpec, const N: usize> { coefficients: [Field<F>; N], }
impl<F: FieldSpec, const N: usize> sunscreen::types::TypeName for Polynomial<F, N> { fn type_name() -> sunscreen::types::Type { sunscreen::types::Type { name: String::from("Polynomial"), ..Field::<F>::type_name() } } }
impl<F: FieldSpec, const N: usize> NumFieldElements for Polynomial<F, N> { const NUM_NATIVE_FIELD_ELEMENTS: usize = N; }
impl<F: FieldSpec, const N: usize> ToNativeFields for Polynomial<F, N> { fn to_native_fields(&self) -> Vec<BigInt> { self.coefficients.map(|x| x.val).into_iter().collect() } }

impl<F: FieldSpec, const N: usize> MulVar for Polynomial<F, N> {
    fn mul(lhs: ProgramNode<Self>, rhs: ProgramNode<Self>) -> ProgramNode<Self> {
        let mut output_coeffs = vec![];

        with_zkp_ctx(|ctx| {
            // We'll start with the zero polynomial, and add to each coefficient
            // as we go
            output_coeffs = vec![ctx.add_constant(&BigInt::ZERO); N];

            // When multiplying (a_i x^i) * (b_j x^j), we get a (a_i * b_j) addend
            // for the `x^{i+j}` coefficient
            for i in 0..N {
                for j in 0..N {
                    // But! Recall we reduce any x^{i+j} to x^{(i+j) % N}
                    // in the quotient ring
                    let coeff_index = (i + j) % N;

                    // Next let's multiply (a_i * b_j)
                    let coeffs_mul = ctx.add_multiplication(lhs.ids[i], rhs.ids[j]);

                    // If (i + j) >= N, we have to add the -1 factor
                    let coeff_addend = if i + j >= N {
                        ctx.add_negate(coeffs_mul)
                    } else {
                        coeffs_mul
                    };

                    // Finally, let's add it to our running total for that coefficient
                    output_coeffs[coeff_index] =
                        ctx.add_addition(output_coeffs[coeff_index], coeff_addend);
                }
            }
        });

        Self::coerce(&output_coeffs)
    }
}
}

Implementing evaluation

We want to define the evaluate function not on the Polynomial itself, but rather the ProgramNode—this way we can evaluate polynomial variables within ZKP programs.

#![allow(unused)]
fn main() {
use sunscreen::{ bulletproofs::BulletproofsBackend, types::zkp::{ AddVar, BigInt, BulletproofsField, Coerce, MulVar, Field, FieldSpec, NumFieldElements, ProgramNode, SubVar, ToNativeFields, }, zkp::{with_zkp_ctx, ZkpContextOps}, zkp_program, zkp_var, Compiler, Error, TypeName, ZkpBackend, ZkpRuntime, };
#[derive(Debug, Copy, Clone)] pub struct Polynomial<F: FieldSpec, const N: usize> { coefficients: [Field<F>; N], }
impl<F: FieldSpec, const N: usize> sunscreen::types::TypeName for Polynomial<F, N> { fn type_name() -> sunscreen::types::Type { sunscreen::types::Type { name: String::from("Polynomial"), ..Field::<F>::type_name() } } }
impl<F: FieldSpec, const N: usize> NumFieldElements for Polynomial<F, N> { const NUM_NATIVE_FIELD_ELEMENTS: usize = N; }
impl<F: FieldSpec, const N: usize> ToNativeFields for Polynomial<F, N> { fn to_native_fields(&self) -> Vec<BigInt> { self.coefficients.map(|x| x.val).into_iter().collect() } }

pub trait Evaluate<F: FieldSpec> {
    fn evaluate<S>(&self, point: S) -> ProgramNode<Field<F>>
    where
        S: Into<ProgramNode<Field<F>>>;
}

impl<F: FieldSpec, const N: usize> Evaluate<F> for ProgramNode<Polynomial<F, N>> {
    /// Evaluate the polynomial at `point`
    fn evaluate<S>(&self, point: S) -> ProgramNode<Field<F>>
    where
        S: Into<ProgramNode<Field<F>>>,
    {
        let point = point.into().ids[0];
        let node_index = with_zkp_ctx(|ctx| {
            let mut result = ctx.add_constant(&BigInt::ZERO);
            let mut pow = ctx.add_constant(&BigInt::ONE);
            for coeff in self.ids {
                let addend = ctx.add_multiplication(pow, *coeff);
                result = ctx.add_addition(result, addend);
                pow = ctx.add_multiplication(pow, point);
            }
            result
        });

        ProgramNode::new(&[node_index])
    }
}
}

Implementing helpers

Next, we'll add a few convenient methods for constructing polynomials within ZKP programs:

#![allow(unused)]
fn main() {
use sunscreen::{ bulletproofs::BulletproofsBackend, types::zkp::{ AddVar, BigInt, BulletproofsField, Coerce, MulVar, Field, FieldSpec, NumFieldElements, ProgramNode, SubVar, ToNativeFields, }, zkp::{with_zkp_ctx, ZkpContextOps}, zkp_program, zkp_var, Compiler, Error, TypeName, ZkpBackend, ZkpRuntime, };
#[derive(Debug, Copy, Clone)] pub struct Polynomial<F: FieldSpec, const N: usize> { coefficients: [Field<F>; N], }
impl<F: FieldSpec, const N: usize> sunscreen::types::TypeName for Polynomial<F, N> { fn type_name() -> sunscreen::types::Type { sunscreen::types::Type { name: String::from("Polynomial"), ..Field::<F>::type_name() } } }
impl<F: FieldSpec, const N: usize> NumFieldElements for Polynomial<F, N> { const NUM_NATIVE_FIELD_ELEMENTS: usize = N; }
impl<F: FieldSpec, const N: usize> ToNativeFields for Polynomial<F, N> { fn to_native_fields(&self) -> Vec<BigInt> { self.coefficients.map(|x| x.val).into_iter().collect() } }
impl<F: FieldSpec, const N: usize> SubVar for Polynomial<F, N> { fn sub(lhs: ProgramNode<Self>, rhs: ProgramNode<Self>) -> ProgramNode<Self> { let mut coeff_node_indices = vec![]; with_zkp_ctx(|ctx| { for (left, right) in lhs.ids.iter().zip(rhs.ids) { coeff_node_indices.push(ctx.add_subtraction(*left, *right)); } }); Self::coerce(&coeff_node_indices) } }

impl<F: FieldSpec, const N: usize> Polynomial<F, N> {
    /// Create the zero polynomial.
    pub fn zero() -> ProgramNode<Self> {
        let zero = with_zkp_ctx(|ctx| ctx.add_constant(&BigInt::ZERO));
        ProgramNode::new(&[zero; N])
    }

    /// Create the polynomial `1`, i.e. the polynomial with zero coefficients
    /// everywhere except for the coefficient `1` at `x^0`.
    pub fn one() -> ProgramNode<Self> {
        let mut poly_ids: [_; N] = Self::zero().ids.try_into().unwrap();
        let one = with_zkp_ctx(|ctx| ctx.add_constant(&BigInt::ONE));
        poly_ids[0] = one;
        ProgramNode::new(&poly_ids)
    }

    /// Create the polynomial `x`, i.e. the polynomial with zero coefficients
    /// everywhere except for the coefficient `1` at `x^1`.
    pub fn x() -> ProgramNode<Self> {
        let mut poly_ids: [_; N] = Self::zero().ids.try_into().unwrap();
        let one = with_zkp_ctx(|ctx| ctx.add_constant(&BigInt::ONE));
        poly_ids[1] = one;
        ProgramNode::new(&poly_ids)
    }

    /// Make a scalar polynomial, i.e. the polynomial with zero coefficients
    /// everywhere except for the coefficient `scalar` at `x^0`.
    pub fn scalar<S>(scalar: S) -> ProgramNode<Self>
    where
        S: Into<ProgramNode<Field<F>>>,
    {
        let mut poly_ids: [_; N] = Self::zero().ids.try_into().unwrap();
        poly_ids[0] = scalar.into().ids[0];
        ProgramNode::new(&poly_ids)
    }

    /// Make a root polynomial `(x - root)`
    pub fn root<S>(root: S) -> ProgramNode<Self>
    where
        S: Into<ProgramNode<Field<F>>>,
    {
        let x = Self::x();
        let r = Self::scalar(root);
        x - r
    }
}
}

One last thing that will be nice for users is an easy way to construct Polynomial inputs to ZKP programs:

#![allow(unused)]
fn main() {
use sunscreen::{ bulletproofs::BulletproofsBackend, types::zkp::{ AddVar, BigInt, BulletproofsField, Coerce, MulVar, Field, FieldSpec, NumFieldElements, ProgramNode, SubVar, ToNativeFields, }, zkp::{with_zkp_ctx, ZkpContextOps}, zkp_program, zkp_var, Compiler, Error, TypeName, ZkpBackend, ZkpRuntime, };
#[derive(Debug, Copy, Clone)] pub struct Polynomial<F: FieldSpec, const N: usize> { coefficients: [Field<F>; N], }
pub fn from_coefficients<B: ZkpBackend, const N: usize, I>(
    coeffs: [I; N],
) -> Polynomial<B::Field, N>
where
    Field<B::Field>: From<I>,
{
    Polynomial {
        coefficients: coeffs.map(Field::from),
    }
}
}

In action!

Finally, let's actually use our polynomial type. Since we wrote all that code, let's use it in two different ZKP programs.

#![allow(unused)]
fn main() {
use sunscreen::{ bulletproofs::BulletproofsBackend, types::zkp::{ AddVar, BigInt, BulletproofsField, Coerce, MulVar, Field, FieldSpec, NumFieldElements, ProgramNode, SubVar, ToNativeFields, }, zkp::{with_zkp_ctx, ZkpContextOps}, zkp_program, zkp_var, Compiler, Error, TypeName, ZkpBackend, ZkpRuntime, };
#[derive(Debug, Copy, Clone)] pub struct Polynomial<F: FieldSpec, const N: usize> { coefficients: [Field<F>; N], }
impl<F: FieldSpec, const N: usize> sunscreen::types::TypeName for Polynomial<F, N> { fn type_name() -> sunscreen::types::Type { sunscreen::types::Type { name: String::from("Polynomial"), ..Field::<F>::type_name() } } }
impl<F: FieldSpec, const N: usize> NumFieldElements for Polynomial<F, N> { const NUM_NATIVE_FIELD_ELEMENTS: usize = N; }
impl<F: FieldSpec, const N: usize> ToNativeFields for Polynomial<F, N> { fn to_native_fields(&self) -> Vec<BigInt> { self.coefficients.map(|x| x.val).into_iter().collect() } }
impl<F: FieldSpec, const N: usize> MulVar for Polynomial<F, N> { fn mul(lhs: ProgramNode<Self>, rhs: ProgramNode<Self>) -> ProgramNode<Self> { let mut output_coeffs = vec![]; with_zkp_ctx(|ctx| { output_coeffs = vec![ctx.add_constant(&BigInt::ZERO); N]; for i in 0..N { for j in 0..N { let coeff_index = (i + j) % N; let coeffs_mul = ctx.add_multiplication(lhs.ids[i], rhs.ids[j]); let coeff_addend = if i + j >= N { ctx.add_negate(coeffs_mul) } else { coeffs_mul }; output_coeffs[coeff_index] = ctx.add_addition(output_coeffs[coeff_index], coeff_addend); } } }); Self::coerce(&output_coeffs) } }
impl<F: FieldSpec, const N: usize> Polynomial<F, N> { pub fn zero() -> ProgramNode<Self> { let zero = with_zkp_ctx(|ctx| ctx.add_constant(&BigInt::ZERO)); ProgramNode::new(&[zero; N]) } pub fn one() -> ProgramNode<Self> { let mut poly_ids: [_; N] = Self::zero().ids.try_into().unwrap(); let one = with_zkp_ctx(|ctx| ctx.add_constant(&BigInt::ONE)); poly_ids[0] = one; ProgramNode::new(&poly_ids) } pub fn x() -> ProgramNode<Self> { let mut poly_ids: [_; N] = Self::zero().ids.try_into().unwrap(); let one = with_zkp_ctx(|ctx| ctx.add_constant(&BigInt::ONE)); poly_ids[1] = one; ProgramNode::new(&poly_ids) } pub fn scalar<S>(scalar: S) -> ProgramNode<Self> where S: Into<ProgramNode<Field<F>>>, { let mut poly_ids: [_; N] = Self::zero().ids.try_into().unwrap(); poly_ids[0] = scalar.into().ids[0]; ProgramNode::new(&poly_ids) } pub fn root<S>(root: S) -> ProgramNode<Self> where S: Into<ProgramNode<Field<F>>>, { let x = Self::x(); let r = Self::scalar(root); x - r } }
impl<F: FieldSpec, const N: usize> SubVar for Polynomial<F, N> { fn sub(lhs: ProgramNode<Self>, rhs: ProgramNode<Self>) -> ProgramNode<Self> { let mut coeff_node_indices = vec![]; with_zkp_ctx(|ctx| { for (left, right) in lhs.ids.iter().zip(rhs.ids) { coeff_node_indices.push(ctx.add_subtraction(*left, *right)); } }); Self::coerce(&coeff_node_indices) } }
pub trait Evaluate<F: FieldSpec> { fn evaluate<S>(&self, point: S) -> ProgramNode<Field<F>> where S: Into<ProgramNode<Field<F>>>; }
impl<F: FieldSpec, const N: usize> Evaluate<F> for ProgramNode<Polynomial<F, N>> { fn evaluate<S>(&self, point: S) -> ProgramNode<Field<F>> where S: Into<ProgramNode<Field<F>>>, { let point = point.into().ids[0]; let node_index = with_zkp_ctx(|ctx| { let mut result = ctx.add_constant(&BigInt::ZERO); let mut pow = ctx.add_constant(&BigInt::ONE); for coeff in self.ids { let addend = ctx.add_multiplication(pow, *coeff); result = ctx.add_addition(result, addend); pow = ctx.add_multiplication(pow, point); } result }); ProgramNode::new(&[node_index]) } }

#[zkp_program]
pub fn one_of<F: FieldSpec>(x: Field<F>, #[public] list: [Field<F>; 5]) {
    // Let's build up a polynomial by roots
    // Note we want to allow degree 5, so we want a ring modulo x^{6}
    let mut poly = Polynomial::<F, 6>::one();
    for elem in list {
        poly = poly * Polynomial::root(elem);
    }

    // If x is in the list, then it is a root of the polynomial
    poly.evaluate(x).constrain_eq(zkp_var!(0));
}
}

We can also use polynomials as arguments!

#![allow(unused)]
fn main() {
use sunscreen::{ bulletproofs::BulletproofsBackend, types::zkp::{ AddVar, BigInt, BulletproofsField, Coerce, MulVar, Field, FieldSpec, NumFieldElements, ProgramNode, SubVar, ToNativeFields, }, zkp::{with_zkp_ctx, ZkpContextOps}, zkp_program, zkp_var, Compiler, Error, TypeName, ZkpBackend, ZkpRuntime, };
#[derive(Debug, Copy, Clone)] pub struct Polynomial<F: FieldSpec, const N: usize> { coefficients: [Field<F>; N], }
impl<F: FieldSpec, const N: usize> sunscreen::types::TypeName for Polynomial<F, N> { fn type_name() -> sunscreen::types::Type { sunscreen::types::Type { name: String::from("Polynomial"), ..Field::<F>::type_name() } } }
impl<F: FieldSpec, const N: usize> NumFieldElements for Polynomial<F, N> { const NUM_NATIVE_FIELD_ELEMENTS: usize = N; }
impl<F: FieldSpec, const N: usize> ToNativeFields for Polynomial<F, N> { fn to_native_fields(&self) -> Vec<BigInt> { self.coefficients.map(|x| x.val).into_iter().collect() } }
impl<F: FieldSpec, const N: usize> MulVar for Polynomial<F, N> { fn mul(lhs: ProgramNode<Self>, rhs: ProgramNode<Self>) -> ProgramNode<Self> { let mut output_coeffs = vec![]; with_zkp_ctx(|ctx| { output_coeffs = vec![ctx.add_constant(&BigInt::ZERO); N]; for i in 0..N { for j in 0..N { let coeff_index = (i + j) % N; let coeffs_mul = ctx.add_multiplication(lhs.ids[i], rhs.ids[j]); let coeff_addend = if i + j >= N { ctx.add_negate(coeffs_mul) } else { coeffs_mul }; output_coeffs[coeff_index] = ctx.add_addition(output_coeffs[coeff_index], coeff_addend); } } }); Self::coerce(&output_coeffs) } }
impl<F: FieldSpec, const N: usize> Polynomial<F, N> { pub fn zero() -> ProgramNode<Self> { let zero = with_zkp_ctx(|ctx| ctx.add_constant(&BigInt::ZERO)); ProgramNode::new(&[zero; N]) } pub fn one() -> ProgramNode<Self> { let mut poly_ids: [_; N] = Self::zero().ids.try_into().unwrap(); let one = with_zkp_ctx(|ctx| ctx.add_constant(&BigInt::ONE)); poly_ids[0] = one; ProgramNode::new(&poly_ids) } pub fn x() -> ProgramNode<Self> { let mut poly_ids: [_; N] = Self::zero().ids.try_into().unwrap(); let one = with_zkp_ctx(|ctx| ctx.add_constant(&BigInt::ONE)); poly_ids[1] = one; ProgramNode::new(&poly_ids) } pub fn scalar<S>(scalar: S) -> ProgramNode<Self> where S: Into<ProgramNode<Field<F>>>, { let mut poly_ids: [_; N] = Self::zero().ids.try_into().unwrap(); poly_ids[0] = scalar.into().ids[0]; ProgramNode::new(&poly_ids) } pub fn root<S>(root: S) -> ProgramNode<Self> where S: Into<ProgramNode<Field<F>>>, { let x = Self::x(); let r = Self::scalar(root); x - r } }
impl<F: FieldSpec, const N: usize> SubVar for Polynomial<F, N> { fn sub(lhs: ProgramNode<Self>, rhs: ProgramNode<Self>) -> ProgramNode<Self> { let mut coeff_node_indices = vec![]; with_zkp_ctx(|ctx| { for (left, right) in lhs.ids.iter().zip(rhs.ids) { coeff_node_indices.push(ctx.add_subtraction(*left, *right)); } }); Self::coerce(&coeff_node_indices) } }
pub trait Evaluate<F: FieldSpec> { fn evaluate<S>(&self, point: S) -> ProgramNode<Field<F>> where S: Into<ProgramNode<Field<F>>>; }
impl<F: FieldSpec, const N: usize> Evaluate<F> for ProgramNode<Polynomial<F, N>> { fn evaluate<S>(&self, point: S) -> ProgramNode<Field<F>> where S: Into<ProgramNode<Field<F>>>, { let point = point.into().ids[0]; let node_index = with_zkp_ctx(|ctx| { let mut result = ctx.add_constant(&BigInt::ZERO); let mut pow = ctx.add_constant(&BigInt::ONE); for coeff in self.ids { let addend = ctx.add_multiplication(pow, *coeff); result = ctx.add_addition(result, addend); pow = ctx.add_multiplication(pow, point); } result }); ProgramNode::new(&[node_index]) } }
#[zkp_program]
pub fn private_eval<F: FieldSpec>(
    eval: Field<F>,
    point: Field<F>,
    #[public] poly: Polynomial<F, 10>,
) {
    poly.evaluate(point).constrain_eq(eval);
}
}

For completeness, here's an example of proving and verifying these ZKPs:

use sunscreen::{ bulletproofs::BulletproofsBackend, types::zkp::{ AddVar, BigInt, BulletproofsField, Coerce, MulVar, Field, FieldSpec, NumFieldElements, ProgramNode, SubVar, ToNativeFields, }, zkp::{with_zkp_ctx, ZkpContextOps}, zkp_program, zkp_var, Compiler, Error, TypeName, ZkpBackend, ZkpRuntime, };
#[derive(Debug, Copy, Clone)] pub struct Polynomial<F: FieldSpec, const N: usize> { coefficients: [Field<F>; N], }
impl<F: FieldSpec, const N: usize> sunscreen::types::TypeName for Polynomial<F, N> { fn type_name() -> sunscreen::types::Type { sunscreen::types::Type { name: String::from("Polynomial"), ..<Field::<F> as sunscreen::types::TypeName>::type_name() } } }
impl<F: FieldSpec, const N: usize> sunscreen::types::TypeNameInstance for Polynomial<F, N> { fn type_name_instance(&self) -> sunscreen::types::Type { sunscreen::types::Type { name: String::from("Polynomial"), ..<Field::<F> as sunscreen::types::TypeName>::type_name() } } }
impl<F: FieldSpec, const N: usize> NumFieldElements for Polynomial<F, N> { const NUM_NATIVE_FIELD_ELEMENTS: usize = N; }
impl<F: FieldSpec, const N: usize> ToNativeFields for Polynomial<F, N> { fn to_native_fields(&self) -> Vec<BigInt> { self.coefficients.map(|x| x.val).into_iter().collect() } }
impl<F: FieldSpec, const N: usize> MulVar for Polynomial<F, N> { fn mul(lhs: ProgramNode<Self>, rhs: ProgramNode<Self>) -> ProgramNode<Self> { let mut output_coeffs = vec![]; with_zkp_ctx(|ctx| { output_coeffs = vec![ctx.add_constant(&BigInt::ZERO); N]; for i in 0..N { for j in 0..N { let coeff_index = (i + j) % N; let coeffs_mul = ctx.add_multiplication(lhs.ids[i], rhs.ids[j]); let coeff_addend = if i + j >= N { ctx.add_negate(coeffs_mul) } else { coeffs_mul }; output_coeffs[coeff_index] = ctx.add_addition(output_coeffs[coeff_index], coeff_addend); } } }); Self::coerce(&output_coeffs) } }
impl<F: FieldSpec, const N: usize> Polynomial<F, N> { pub fn zero() -> ProgramNode<Self> { let zero = with_zkp_ctx(|ctx| ctx.add_constant(&BigInt::ZERO)); ProgramNode::new(&[zero; N]) } pub fn one() -> ProgramNode<Self> { let mut poly_ids: [_; N] = Self::zero().ids.try_into().unwrap(); let one = with_zkp_ctx(|ctx| ctx.add_constant(&BigInt::ONE)); poly_ids[0] = one; ProgramNode::new(&poly_ids) } pub fn x() -> ProgramNode<Self> { let mut poly_ids: [_; N] = Self::zero().ids.try_into().unwrap(); let one = with_zkp_ctx(|ctx| ctx.add_constant(&BigInt::ONE)); poly_ids[1] = one; ProgramNode::new(&poly_ids) } pub fn scalar<S>(scalar: S) -> ProgramNode<Self> where S: Into<ProgramNode<Field<F>>>, { let mut poly_ids: [_; N] = Self::zero().ids.try_into().unwrap(); poly_ids[0] = scalar.into().ids[0]; ProgramNode::new(&poly_ids) } pub fn root<S>(root: S) -> ProgramNode<Self> where S: Into<ProgramNode<Field<F>>>, { let x = Self::x(); let r = Self::scalar(root); x - r } }
impl<F: FieldSpec, const N: usize> SubVar for Polynomial<F, N> { fn sub(lhs: ProgramNode<Self>, rhs: ProgramNode<Self>) -> ProgramNode<Self> { let mut coeff_node_indices = vec![]; with_zkp_ctx(|ctx| { for (left, right) in lhs.ids.iter().zip(rhs.ids) { coeff_node_indices.push(ctx.add_subtraction(*left, *right)); } }); Self::coerce(&coeff_node_indices) } }
pub trait Evaluate<F: FieldSpec> { fn evaluate<S>(&self, point: S) -> ProgramNode<Field<F>> where S: Into<ProgramNode<Field<F>>>; }
impl<F: FieldSpec, const N: usize> Evaluate<F> for ProgramNode<Polynomial<F, N>> { fn evaluate<S>(&self, point: S) -> ProgramNode<Field<F>> where S: Into<ProgramNode<Field<F>>>, { let point = point.into().ids[0]; let node_index = with_zkp_ctx(|ctx| { let mut result = ctx.add_constant(&BigInt::ZERO); let mut pow = ctx.add_constant(&BigInt::ONE); for coeff in self.ids { let addend = ctx.add_multiplication(pow, *coeff); result = ctx.add_addition(result, addend); pow = ctx.add_multiplication(pow, point); } result }); ProgramNode::new(&[node_index]) } }
pub fn from_coefficients<B: ZkpBackend, const N: usize, I>( coeffs: [I; N],) -> Polynomial<B::Field, N> where Field<B::Field>: From<I>, { Polynomial { coefficients: coeffs.map(Field::from), } }
#[zkp_program] pub fn one_of<F: FieldSpec>(x: Field<F>, #[public] list: [Field<F>; 5]) { let mut poly = Polynomial::<F, 6>::one(); for elem in list { poly = poly * Polynomial::root(elem); } poly.evaluate(x).constrain_eq(zkp_var!(0)); }
#[zkp_program] pub fn private_eval<F: FieldSpec>( eval: Field<F>, point: Field<F>, #[public] poly: Polynomial<F, 10>,) { poly.evaluate(point).constrain_eq(eval); }
fn main() -> Result<(), Error> {
    let app = Compiler::new()
        .zkp_backend::<BulletproofsBackend>()
        .zkp_program(one_of)
        .zkp_program(private_eval)
        .compile()?;
    let runtime = ZkpRuntime::new(BulletproofsBackend::new())?;

    // Let's test our `one_of` ZKP works as expected

    let one_of_zkp = app.get_zkp_program(one_of).unwrap();

    let x = BulletproofsField::from(12345);
    let list: [_; 5] = std::array::from_fn(|i| BulletproofsField::from(12343 + i as u32));

    let proof = runtime
        .proof_builder(one_of_zkp)
        .private_input(x)
        .public_input(list)
        .prove()?;
    runtime
        .verification_builder(one_of_zkp)
        .proof(&proof)
        .public_input(list)
        .verify()?;

    // Next let's try out `private_eval`

    let private_eval_zkp = app.get_zkp_program(private_eval).unwrap();

    let poly = from_coefficients::<BulletproofsBackend, 10, _>(
        [1, 42, 0, 0, 0, 3, 0, 0, 0, 0]
    );
    let point = BulletproofsField::from(2);
    // At point 2, the poly should be equal to 1 + 42 * 2 + 3 * 32 = 181
    let eval = BulletproofsField::from(1 + 42 * 2 + 3 * 32);

    let proof = runtime
        .proof_builder(private_eval_zkp)
        .private_input(eval)
        .private_input(point)
        .public_input(poly)
        .prove()?;
    runtime
        .verification_builder(private_eval_zkp)
        .proof(&proof)
        .public_input(poly)
        .verify()?;

    Ok(())
}

Final note

Expressing the one_of constraint in terms of these polynomials is incredibly inefficient; you can see this if you change the program to use more than a 5-degree list. If you already know the point c, it is much more efficient to compute (c - a_1) * ... * (c - a_k) directly, as this is only k * (k - 1) arithmetic operations. Whereas, using the polynomial approach above, the polynomial multiplication will happen first, which requires a ton of multiplication and addition of coefficients.

WASM support

Need to run Sunscreen in your browser or NodeJS app? Simply build your app targeting WebAssembly (WASM).

WASM is an instruction set for a sandboxed virtual machine that allows you to safely run Rust code in your browser more efficiently than Javascript. This includes your Sunscreen app!

Rust features multiple targets for building WASM binaries, but Sunscreen currently only supports wasm32-unknown-emscripten. As the name suggests, this leverages emscripten.¹

Setup

Install emscripten

git clone https://github.com/emscripten-core/emsdk.git
emsdk/emsdk install 3.1.3
emsdk/emsdk activate 3.1.3

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 🙃.

Load the emscripten environment

source emsdk/emsdk_env.sh

Put this command in your shell's .rc file so you don't need to rerun it each time you launch a shell.

Add the wasm32-unknown-emscripten target to Rust

rustup target add wasm32-unknown-emscripten

Building

To compile your program with Rust+emscripten, you'll need to do a few extra things.

Required emscripten features

Add the following lines to your .cargo/config.toml²:

[env]
EMCC_CFLAGS = "-sERROR_ON_UNDEFINED_SYMBOLS=0 -sDISABLE_EXCEPTION_CATCHING=0 -sALLOW_MEMORY_GROWTH"

ERROR_ON_UNDEFINED_SYMBOLS=0 works around a known issue when Rust's panic handling is set to unwind (the default). Alternatively, you can set the handling mode to abort when building for WASM.

DISABLE_EXCEPTION_CATCHING=0 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 abort().

Finally, ALLOW_MEMORY_GROWTH allows the heap to resize. Without this, your app will quickly run out of memory and seg fault.

Building your app

Simply run:

cargo build --bin myapp --release --target wasm32-unknown-emscripten

where myapp is the name of your executable.

On success, you should see the following files:

target/wasm32-unknown-emscripten/release/myapp.js
target/wasm32-unknown-emscripten/release/myapp.wasm

Running with node

node target/wasm32-unknown-emscripten/release/myapp.js

Running in browser

Put myapp.js in a script tag in an index.html file:

<!DOCTYPE html>
<html>
    <head>
        <script src="myapp.js"></script>
    </head>
    <body></body>
</html>

and serve the index.html, myapp.js, and myapp.wasm files on a web server. Your app will run when the user loads the page in their browser.

Alternatively, you can bundle your .js and .wasm into a larger application with webpack.

Running with wasmer/wasmtime

Unfortunately, these scenarios are currently unsupported 😞.

Running tests

Build your tests with:

cargo test --no-run --release --target wasm32-unknown-emscripten

You'll find your tests' entry points in target/wasm32-unknown-emscripten/release/deps/*.js. Simply select the desired test and run:

node target/wasm32-unknown-emscripten/release/mytest-xxxx.js

Debugging

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.

Build in debug mode

To use source maps, simply build in debug mode³:

cargo build --bin myapp --target wasm32-unknown-emscripten

where myapp is the name of your executable.

Make a webpage

In our experiments debugging with node --inspect-brk, 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.

Make an index.html with the following contents in the root of your git repository:

<!DOCTYPE html>
<html>
    <head>
        <script src="./target/wasm32-unknown-emscripten/debug/myapp.js"></script>
    </head>
    <body></body>
</html>

Serve your page

In another terminal, run:

npm install -g http-server
node http-server /git/repo/root/dir

Debug your program on the website

Open Chrome and navigate to http://localhost:8080/index.html. 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.

You can also use the log crate to print information to the debug console. If you go this route, use simple-logger as the logger backend; don't use a WASM-specific crate (e.g. wasm-logger) for this because emscripten already routes stdout and stderr to the console.