[SUSTCSC '25] Rust in HPC

In this challenge, you will get hands-on experience using Rust for high-performance computing (HPC) tasks, especially in a narrow domain of numerical computing. As I only have knowledge about security and cryptography, this challenge will only focus on acclerating an encrypted numerical computation, or boosting encryption itself task using Rust - most ubiquitous libraries of cryptography are written in Rust.

TL;DR

The basic challenge is to boost a encrypted numerical computation task: Conway's Game of Life (2D version) computed on a fully homomorphic encryption (FHE) scheme (empowered by tfhe-rs). The scheme is implemented with LWE (Learning With Errors, in case you don't know what it is, it's a post-quantum cryptography that is very complicated in computation, so very slow). Though the task seems tricky (but you don't need to know about the encryption), you just need to focus on the parallelization, compilation and SIMD optimization of the code - simple as that. FHE is being developed to be used in real-world secure HPC applications, and demanded by the enterprises.

Once you done the basic one, I've prepared a bonus challenge for you: boost the attack on the LWE scheme, by recovering the secret vector. This is a very hard one as I don't know the solution neither. But the point is that you explore an unknown area of the problem space and potentially discover new techniques or optimizations, which can be shown by your report. I'm expecting you to implement an attack purely in Rust, which I'm sure that no one has done before.

What's in this website?

You will find the following contents in this website:

Setting up Environment will guide you through the preparation for the challenge.
Crash Course on Rust will get you started with Rust and how it's used in HPC.
Introduction to LWE will introduce the details of LWE and how it works.

You know what Conway's Game of Life is, so I won't bother to explain it here.

Environment Setup

This challenge only focuses on optimization on CPU so that saves you a lot of time learning CUDA or OpenCL. This chapter assumes you have a basic knowledge of computer and programming (e.g., if you learned some languages), and you don't know anything about Rust. We will get you started with Rust on local bare-metal machine or container.

If you'd rather not spend too much time on setting up the environment, a Linux/macOS machine will be the best choice. Otherwise, you could use a Docker container but it may take a while to install Docker and set up the network. Don't worry, we will provide a Dockerfile for you and guideline to resolve the issues. The worst choice is to use Windows, but if you have to, you can enable WSL2 or install Docker Desktop.

We run your code in a Docker container after the submission and we may resolve some issues that is not regarding to your code. However, if we decide it's a bug in your code, we will not fix that and will consider it as a failure. For performance issues, we will ensure that your code is running in a native CPU environment, and for the worst case, we might turn to a grading scheme by comparing all of submissions (i.e., relative performance).

A tip about Rust that it's associated with a package manager called Cargo and online repository called crates.io. You can find documents of crates on docs.rs.

Overview of Benchmarking Environment

CPU: Intel Xeon Platinum 8350C (2.40GHz * 20 core * 2 sockets)
Rust: stable, possibly 1.87.0¹
GPU: N/A (we won't use GPU in this challenge)
Host OS: Linux 4.18.0-372.32.1.el8_6.x86_64, all mitigation disabled
Network: N/A²
Docker: Singularity 3.7.1

Signal us if you'd like to use a nightly version anywhere in the submission. However, you have to be responsible for the nightly version since it may break or slow down your code.

We ignore all compilation cost, including the cost of downloading dependencies, and we will not run your code in a container with network access.

Running Rust on Linux

Well, if you're using Linux, you know how to do it.

But if you don't, here's a quick guide to get you started.

Preparing the System packages

Linux is just a kernel and there're various distributions of Linux, which means that you may need to find out what you got because they have different package managers, by executing

uname -a
# will output something like:
# Linux your-hostname 6.14.6-arch1-1 #1 SMP PREEMPT_DYNAMIC Fri, 09 May 2025 17:36:18 +0000 x86_64 GNU/Linux
cat /etc/os-release
# NAME="Arch Linux"
# PRETTY_NAME="Arch Linux"
# ID=arch
# BUILD_ID=rolling
# ANSI_COLOR="38;2;23;147;209"
# HOME_URL="https://archlinux.org/"
# DOCUMENTATION_URL="https://wiki.archlinux.org/"
# SUPPORT_URL="https://bbs.archlinux.org/"
# BUG_REPORT_URL="https://gitlab.archlinux.org/groups/archlinux/-/issues"
# PRIVACY_POLICY_URL="https://terms.archlinux.org/docs/privacy-policy/"
# LOGO=archlinux-logo

In this example, we are using Arch Linux. Once you know what distribution you're using, go on

Debian/Ubuntu

sudo apt-get update && \
sudo apt-get install -y build-essential \
    ca-certificates curl \
    pkg-config unzip util-linux wget \

Fedora

sudo dnf makecache --refresh && \
sudo dnf group install c-development && \
sudo dnf install ca-certificates curl \
    pkg-config unzip util-linux wget

RHEL

sudo dnf makecache --refresh && \
sudo dnf groupinstall "Devlopment tools" && \
sudo dnf install epel-release && \
sudo /usr/bin/crb enable && \
sudo dnf makecache --refresh && \
sudo dnf install ca-certificates curl \
    pkg-config unzip util-linux wget

Arch

sudo pacman -Syyu && \
sudo pacman -S base-devel ca-certificates curl  \
    pkg-config unzip util-linux wget

openSUSE

sudo zypper ref && \
sudo zypper in -t pattern devel_C_C++ && \
sudo zypper in ca-certificates curl \
    pkg-config unzip util-linux wget

Installing Rust

curl --proto '=https' --tlsv1.2 -sSf https://sh.rustup.rs | sh && \
. "$HOME/.cargo/env" && \
rustup default stable # or nightly

Verify the installation by running

rustc --version

You're all set to go!

Running Rust on macOS

macOS is a Unix-like operating system, so it's similar to Linux in many ways.

Package Manager: Homebrew

Though macOS has fantatstic GUI, developers will always need a package manager in CLI to help them install and manage software - Homebrew is the most choice. ¹

xcode-select --install
# This will install the Xcode Command Line Tools, which includes the necessary tools
# Type in your password if prompted
/bin/bash -c "$(curl -fsSL https://raw.githubusercontent.com/Homebrew/install/HEAD/install.sh)"

Installing Rust

Getting libraries and Rust toolchain is easy with Homebrew.

brew install rustup curl pkgconf unzip util-linux wget && \
. "$HOME/.cargo/env" && \
rustup default stable # or nightly

Verify the installation by running:

rustc --version

We highly recommend you to have a VS Code and install the rust-analyzer extension.

If you prefer to use MacPorts or Nix, skip this section plz.

Running Rust on Windows

Nobody wants to develop Rust on Windows, but if you have to, we're only able to offer you alternative solutions

Using WSL/WSL2

Refer to the official WSL documentation.

Go to Linux section for more info.

Using Docker Desktop

Refer to the official Docker documentation.

Go to Docker section for more info.

Running Rust inside Docker

If you come from Windows, go to bootup section directly.

Installing Docker

See Docker installation guide if you're using Linux.

If you are facing network issues, don't worry, we all have been there. You can try using a proxy or a VPN, or you can use the following commands to install Docker without network access:

echo "
{
    "registry-mirrors": [
        "https://docker-proxy.benx.dev"
    ]
}
" > /etc/docker/daemon.json
sudo systemctl daemon-reload
sudo systemctl restart docker

macOS users can install Docker Desktop from Docker Hub, simply with a few clicks.

Bootup Rust

Once you have Docker installed, you can execute the provided Docker compose file to start the Rust environment

git clone https://github.com/chanbengz/sustcsc-rs
cd sustcsc-rs
docker-compose up -d dev # or stable/nightly for running only

dev is an interactive development environment, where you can write you code outside and run the code (and execute any command) inside the container.

First Look at Rust

Welcome to the world of Rust. The following chapters will lead you to write code in Rust for computing. Nevertheless, I shall note that Rust is a little bie more complicated than other languages.

In this page, you can run the code snippets by clicking the "Run" button on the top right corner of the code block.

Hello World

If you follow the installation guidelines, you should see cargo and rustc on your machine. Now, create your first Rust project by

$ cargo new hello-world --bin

Here, --bin means that you want to create a standalone project (i.e. runs on its own), so if you'd like to create a library, you can use --lib instead. The project will be created in the hello-world directory.

$ cd hello_world
$ tree .
.
├── Cargo.toml
└── src
    └── main.rs

Cargo.toml is the configuration file for your project, and you don't need to edit it yourself. The src directory contains the source code of your project. The main.rs file is the entry point of your program, and it contains the main function, which is the first function that is called when your program runs, just like in C/C++.

fn main() {
    println!("Hello world!");
}

Here're somethign to take away

fn is used to define a function. We will talk about functions in Functions section.
println! is a macro that prints the string to the standard output. The ! indicates that it is a macro, not a function. The reason for print being a macro is complicated, but you can find clues in this website.
unlike C/C++, you don't need to return 0; at the end of the main function. Rust has a better way.

Variables

Rust has a type inference for declaring variables, so you don't need to specify the type of the variable when you declare it. For example,

fn main() {
    let x = 5;
    let s = "Hello world!";
    let v = vec![1, 2, 3]; // dynamic array

    println!("x = {}", x);
    println!("s = {}", s);
    println!("v = {:?}", v);
}

Hinted about the type

Rust is a statically typed language and it offers a strong type inference system. You would probably notice that let doesn't require you to specify the type of the variable as in Java or C. But type inference is not always possible and so you should hint the compiler about the type of the variable.

#![allow(unused)]
fn main() {
let x: i32 = 5; // explicitly hint the type of x
let y = 10u32;  // hint by constants
let arr = vec![0.0; 4] // we'll get to vector later
}

Oops! Inference breaks

There're cases where the compiler cannot know the type of a variable at compile time. For example, if you declare a variable without initializing it, the compiler will not be able to infer its type:

#![allow(unused)]
fn main() {
let x;
let v = Vec::new(); // or
let v = vec![];
}

You can see the error by clicking the "Run" button above.

To address this, you need to specify the type of the variable explicitly:

#![allow(unused)]
fn main() {
let x: i32;
let v: Vec<i32> = Vec::new(); // or
let v: Vec<i32> = vec![]; // or
let v = Vec::<i32>::new(); // generic
}

First glance on ownership

Rust has a unique ownership system that enforces you to manage memory safely and efficiently. When we say define a variable, we actually mean to "bind" a name to a value in Rust. For example, if you try to use a variable after it has been moved, the compiler will throw an error:

fn main() {
    let s1 = String::from("Hello");
    let s2 = s1; // move ownership from s1 to s2
    println!("{}", s1); // this will not compile, as s1 is no longer valid
}

because s1 is no longer valid after the ownership has been moved to s2. To address this, you can use either cloning or borrowing (reference) to avoid take ownership of the variable.

fn main() {
    let s1 = String::from("Hello");
    let s2 = s1.clone(); // clone the value of s1 to s2
    let s3 = &s1; // borrow a reference to s1
    println!("{}", s1); // this will compile, as s1 is still valid
}

Printing

Rust formatting is similar to other languages. If you have some experience with other languages, you would probably know that not all the types can be printed directly. For example, if you try to print a self-defined struct, you will get a weird output in Python:

class Point:
    def __init__(self, x, y):
        self.x = x
        self.y = y

if __name__ == "__main__":
    p = Point(1, 2)
    print(p)

This will print something like <__main__.Point object at 0x7f8c2c3e4d90>, which is not very useful. Python has a special method __str__ and __repr__ to address this, and Java has toString(), etc. In Rust, you can use the Debug trait to print the struct. You need to derive the Debug trait for your struct, and then you can use the {:?} format specifier to print it. For example:

#[derive(Debug)]
struct Point {
    x: i32,
    y: i32,
}

fn main() {
    let p = Point { x: 1, y: 2 };
    println!("{:?}", p);
}

Or if you want to print it in a more human-readable format, you can use the {} format specifier and implement the Display trait for your struct. For example:

#![allow(unused)]
fn main() {
use std::fmt;

impl fmt::Display for Point {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        write!(f, "({}, {})", self.x, self.y) // just like a write syscall
    }
}
}

Then you can use the {} format specifier to print it:

fn main() {
    let p = Point { x: 1, y: 2 };
    println!("{}", p); // (1, 2)
    // or
    let p = Point { x: 1, y: 2 };
    println!("{p}"); // (1, 2)
}

and a more complex formatting:

fn main() {
    println!("x = {x}, y = {y}, sum = {sum}", x=1, y=2, sum=1+2);
}

Variables and Numbers

This chapter tells about how you can compute with numbers in Rust.

Mutable and Immutable Variables

In Rust, variables are immutable by default. This means that once a variable is bound to a value, it cannot be changed. For example:

fn main() {
    let x = 5;
    println!("x = {}", x);
    x = 6; // error: cannot assign twice to immutable variable `x`
}

If you want to make a variable mutable, you can use the mut keyword:

fn main() {
    let mut x = 5;
    println!("x = {}", x);
    x = 6;
    println!("x = {}", x);
}

In this case, x is mutable, so you can change its value.

Constants

Constants are similar to immutable variables, but they must be explicitly typed and cannot be changed. You can define a constant using the const keyword:

#![allow(unused)]
fn main() {
const PI: f64 = 3.141592653589793;
}

Constants are always immutable and must have a type annotation. They can be defined in any scope, including inside functions.

fn main() {
    const PI: f64 = 3.141592653589793;
    println!("PI = {}", PI);
}

Numbers

Rust has a intuitive name for the number types, like i32 for 32-bit signed integers, u32 for 32-bit unsigned integers, and f64 for 64-bit floating-point numbers. You can use the following types:

fn main() {
    let x = 5i32;
    let y = 10u32;
    let z = 3.14f64;

    println!("x = {}", x);
    println!("y = {}", y);
    println!("z = {}", z);
}

Struct

You can also define your own types using struct. A struct is a custom data type that lets you package together related data. Here's an example of a simple struct:

#![allow(unused)]
fn main() {
struct Point {
    x: f64,
    y: f64,
    pub metadata: String, 
    // `pub` makes this field accessible outside the module
}
}

to create an instance of a struct, you can use the following syntax:

fn main() {
    let p = Point {
        x: 1.0,
        y: 2.0,
        metadata: String::from("A point in 2D space"),
    };
    println!("Point: ({}, {}), Metadata: {}", p.x, p.y, p.metadata);
    //                                        ^^^ not accessible outside the module
}

Tuple

Tuple is a fixed-size collection of values of different types. You can create a tuple using parentheses:

fn main() {
    let tuple: (i32, f64, char) = (42, 3.14, 'a');
    println!("Tuple: ({}, {}, {})", tuple.0, tuple.1, tuple.2);
}

Tuples are the same typed if all their elements have the same type.

Enum

Enums are a way to define a type that can be one of several different variants. You can define an enum using the enum keyword:

#![allow(unused)]
fn main() {
enum Direction {
    Up,
    Down,
    Left,
    Right,
}
}

You can wrap data in an enum variant:

#![allow(unused)]
fn main() {
enum Card {
    Clubs(u8), // Clubs with a value
    Diamonds(u8), // Diamonds with a value
    Hearts(u8), // Hearts with a value
    Spades(u8), // Spades with a value
}

let card = Card::Hearts(10);
match card {
    Card::Clubs(value) => println!("Clubs with value: {}", value),
    Card::Diamonds(value) => println!("Diamonds with value: {}", value),
    Card::Hearts(value) => println!("Hearts with value: {}", value),
    Card::Spades(value) => println!("Spades with value: {}", value),
}
}

Loops and Arrays

Loops and arrays are fundamental concepts in all programming languages. So we will assume that you've already written loops and arrays in other languages. This section will tell you how to write loops and arrays in Rust and at the last, we will introduce the ndarray crate, which is a powerful library for numerical computing in Rust.

Loop and while

Rust does not define a for loop like in C/C++ or Java. Instead, it's like Python's. For example, to iterate over a range of numbers, you can use the for loop like this:

#![allow(unused)]
fn main() {
for i in 0..10 {
    println!("i = {i}");
}
}

which will print numbers from 0 to 9. If you'd include the tail number, you can use 0..=10:

#![allow(unused)]
fn main() {
for i in 0..=10 {
    println!("i = {i}");
}
}

It's an iterator-like syntax because .. gives a range iterator just like range() in Python. So similarly, Rust also has

x.. to create a slice like [x:] in Python, without a right bound.
..y to create a slice like [:y] in Python, without a left bound.

Infinite loops can be created using loop:

#![allow(unused)]
fn main() {
loop {
    println!("This will run forever!");
    // break;
}
}

Iterators

The concept of iterators originates from functional programming languages, which will be discussed in the next chapter. But for now, we just focus on how to use iterators in Rust. To use an iterator, the stuff you'd iterate over must implement the Iterator and IntoIterator trait. We don't need to worry about this here.

The point of having a Iterator is that it implements the next() method, which is the core of the iterator concept. FYI, an iterator is a stateful object that returns a sequence of values by next(). You don't need to care about the internal state of the iterator, just call next() to get the next value.
The IntoIterator trait is used to convert a collection into an iterator. It provides the into_iter() method, which returns an iterator over the collection. This is similar to Python's iter() function.

For example, the for loop we mentioned above can be rewritten using an iterator:

#![allow(unused)]
fn main() {
let mut iter = (0..10).into_iter();
while let Some(i) = iter.next() { // Some<T> is exlained in the next chapter
    println!("i = {i}");
}
}

and using iterators can give you more flexibility, such as filtering

#![allow(unused)]
fn main() {
let mut iter = (0..10).into_iter().filter(|&x| x % 2 == 0)
while let Some(i) = iter.next() {
    println!("i = {i}"); // i is even
}
}

or stepping through the range:

#![allow(unused)]
fn main() {
for i in (0..10).into_iter().step_by(2) {
    println!("i = {i}"); // i is even
}
}

Why do we need iterators? Because they are lazy! They don't compute the values until you actually need them. Second, they can be easily composed together to create complex data processing pipelines. We will see a more advanced example in the next chapter when we talk about functional programming.

Array (Slice and Vec)

Array in Rust is a fixed-size collection of elements of the same type. It is similar to arrays in C/C++ or Java but it comes with a formal definition: [T; N], where T is the type of the elements and N is the size of the array (it's a generic). So array with different sizes are also different types. Use array as you want

#![allow(unused)]
fn main() {
let mut arr: [i32; 5] = [0; 5]; // an array of 5 i32 initialized to 0
//  ^^^ mut is important
let arr2 = [1, 2, 3, 4, 5];

arr[0] = 1; // set the first element to 1
println!("{:?}", arr); // print the array
}

To iterate over an array, you can use a for loop:

#![allow(unused)]
fn main() {
for i in &arr { // note the reference
    println!("i = {i}");
}
}

Slicing is a way to create a view into a part of an array. It has the annotation &[T], which is a reference to a slice of type T and looks like Python's.

#![allow(unused)]
fn main() {
let a = [1, 2, 3, 4, 5];
let s = &a[1..4]; // slice from index 1 to 3 (4 is excluded)
assert_eq!(s, [2, 3, 4]);
}

You may notice the reference & in the slice. This is because Rust is strict about ownership and borrowing, which will be discussed in the next chapter. For now, just remember that slices are references to parts of arrays.

To create a dynamic array, Rust provides the Vec type, which is a growable array. Here's how you can use it:

#![allow(unused)]
fn main() {
let mut v: Vec<i32> = Vec::new(); // create an empty vector
v.push(1); // add an element to the vector
v.push(2);
v.push(3); // add more elements
println!("{:?}", v); // print the vector

let mut v = vec![1, 2, 3]; // create a vector with initial elements
v.push(4); // add an element to the vector
println!("{:?}", v); // print the vector

let mut v = vec![0; 5]; // create a vector of 5 elements initialized to 0
v[0] = 1; // set the first element to 1
println!("{:?}", v); // print the vector
}

And to play vector with iterator, you can

#![allow(unused)]
fn main() {
let v: Vec<_> = (114..514).into_iter().collect();
// or a generic way
let v = (114..514).into_iter().collect::<Vec<_>>();
}

As in other vectors (C++/Java/Python), the dynamic array is costly to resize because of remalloc and moving data, so it will be better to preallocate the size of the vector if you know it in advance:

#![allow(unused)]
fn main() {
let mut v: Vec<i32> = Vec::with_capacity(100); // create a vector with capacity 100
for i in 0..100 {
    v.push(i); // add elements to the vector
}
}

ndarray

It's good to have the native Array and Vec types in Rust, but they are not enough for numerical computing. For example, creating a 2D array (matrix) is not straightforward and not efficient with the native types

#![allow(unused)]
fn main() {
let mut mat = vec![vec![0; 3]; 4]; // a 4x3 matrix initialized to 0
mat[0][0] = 1; // set the first element to 1
println!("{:?}", mat); // print the matrix
}

Too much vector nesting, and the performance is not good because of the memory layout. A intuitive way to create a 2D array is flatten it into a 1D array and wrap it in a struct with metadata

#![allow(unused)]
fn main() {
struct Matrix {
    data: Vec<i32>, // the data of the matrix
    rows: usize,   // the number of rows
    cols: usize,   // the number of columns
}

impl Matrix {
    fn new(rows: usize, cols: usize) -> Self {
        Matrix {
            data: vec![0; rows * cols], // initialize the data to 0
            rows,
            cols,
        }
    }
    // yeah I hate the getter and setter
    // we can write in a better way but it's not the point here
    fn get(&self, row: usize, col: usize) -> i32 {
        self.data[row * self.cols + col] // access the element at (row, col)
    }

    fn set(&mut self, row: usize, col: usize, value: i32) {
        self.data[row * self.cols + col] = value; // set the element at (row, col)
    }
}
}

and that's what ndarray crate does for you. To equip with it, execute in the terminal

cargo add ndarray

then, you can use it like this:

#![allow(unused)]
fn main() {
use ndarray::{array, Array2};

let a = Array2::zeros((4, 3)); // create a 4x3 matrix filled with zeros
println!("{:?}", a);

let b = array![[1, 2, 3], [4, 5, 6]]; // create a 2D array (matrix) with initial values
println!("{:?}", b);
}

index the matrix is also straightforward:

#![allow(unused)]
fn main() {
let a = array![[1, 2, 3], [4, 5, 6]];
println!("a[0, 0] = {}", a[[0, 0]]);
}

For slicing and iterating, ndarray provides a lot of methods to manipulate the array easily:

#![allow(unused)]
fn main() {
use ndarray::{array, s};

let a = array![[1, 2, 3], [4, 5, 6]];
let b = a.slice(s![.., 0..1, ..]);
}

more about slicing and iterating can be found in the ndarray documentation.

Moreover, ndarray provides lots of optimizations! View it next chapter.

String

String is complicated in Rust so we won't talk about it in detail here. Refer to this.

Functions and Functional Programming

This section may take longer than the others, as we have lots of examples to go through. It also contains plenty of concepts regarding functional programming, which you may not be familiar with. And this section isn't just about functions, despite its title, it also covers functional programming in Rust. So take your time to read through it, and don't hesitate to ask questions if you have any.

Functions, `Option` and `Result`

Let's assume you know what functions are, and how to define and use them. In Java, it has alias method. Rust defines functions like this:

#![allow(unused)]
fn main() {
fn function_name(parameter1: Type1, parameter2: Type2) -> ReturnType {
    // function body
    // ...
    return value; // or just `value` if the return type is not `()`
}
}

If you don't want to return a value, you can omit the return type, or use (), which is the unit type in Rust, similar to void in C/C++ or Java.

Yet, where Rust is special is that its grammar allows you to omit the return keyword when returning a value, as long as the last expression does not end with a semicolon.

#![allow(unused)]
fn main() {
fn sum(a: i32, b: i32) -> i32 {
    // ...
    a + b // no semicolon, so this is the return value
}
}

This kind of syntax can also be seen in if statements and match expressions, which we will see later.

There're special types in Rust that define how Rust code looks like, the most classic ones are Option and Result.

If you know functional programming, you may have heard of Maybe and Either types, and Option is one of them - it's a monad. But I guess you're less likely to have heard of monad so you can just forget about monad. Simply speaking, Option is a type that can either be Some(value) or None.

#![allow(unused)]
fn main() {
fn get_value() -> Option<i32> {
    // ...
    if some_condition {
        Some(42) // return a value wrapped in `Some`
    } else {
        None // return `None` if the condition is not met
    }
}
}

It's often a placeholder for a value that may not exist, or a value that may fail to be computed, but since Rust is statically typed, you must return the same type every time, so you cannot return i32 and None at the same time ¹. Also, to use the value inside an Option, you must unwrap it

#![allow(unused)]
fn main() {
let a = Option::Some(114);
let b = Option::Some(514);
let c = a + b; // this will not compile, as `Option` does not implement `Add` trait
let c = a.unwrap() + b.unwrap(); // this will compile, but it may panic if `a` or `b` is `None`
}

Otherwise you would have to expicitly define a error value like -1 or 0, but sometimes they have special meanings other than "error", so it's not a good idea to use them as error values.

As for Result, it's a type that can either be Ok(value) or Err(error), and it's used to represent the result of an execution that may fail. It's useful if you don't like the panic mechanism in Rust because it aborts the program. Yes, it's Rust way to deal with try-catch in other languages, but it does not have try-catch at all.

#![allow(unused)]
fn main() {
fn divide(a: i32, b: i32) -> Result<i32, String> {
    if b == 0 {
        Err("Cannot divide by zero".to_string()) // return an error if b is zero
    } else {
        Ok(a / b) // return the result wrapped in `Ok`
    }
}

let result = divide(10, 2);
println!("{:?}", result); // prints `Ok(5)`
let result = divide(10, 0);
println!("{:?}", result); // prints `Err("Cannot divide by zero")`
}

to handle Err or None, we suggest you use unwrap_or or unwrap_or_else methods, which will return a default value if the value is None or Err.

#![allow(unused)]
fn main() {
let a = Option::None;
let b = a.unwrap_or(0); // if `a` is `None`, return `0` instead of panicking
}

A special case when using Result is that if you have nested function calls that share the same error type, for example:

#![allow(unused)]
fn main() {
fn foo() -> Result<i32, String> {
    let a = bar()?; // `bar` returns `Result<i32, String>`
    //           ^ this `?` operator will automatically propagate the error if `bar` returns `Err`
}

fn bar() -> Result<i32, String> {
    // ...
    Err("An error occurred".to_string())
}
}

? can be abbreviated as unwrap_or_else(|e| Err(e)), which will return the error if it exists and abort the function execution.

`if let` and `match`

Before match, we should bring up enum because it's a powerful feature in Rust that allows you to define a wrapped type.

#![allow(unused)]
fn main() {
enum Number {
    Integer(i32),
    Float(f64),
    Complex(f64, f64),
    Rational(i32, i32),
    Zero,
    Nothing
}

fn print_number(num: Number) {
    match num {
        Number::Integer(i) => println!("Integer: {}", i),
        Number::Float(f) => println!("Float: {}", f),
        Number::Complex(r, i) => println!("Complex: {} + {}i", r, i),
        Number::Rational(n, d) => println!("Rational: {}/{}", n, d),
        Number::Zero => println!("0"),
        Number::Nothing => println!("Nothing"),
    }
}
}

sometimes you're tired of exhausting all the variants of an enum, Rust provides a convenient way to match _ as a don't-care pattern,

#![allow(unused)]
fn main() {
fn foo(num: Number) -> i32 {
    match num {
        Number::Integer(i) => i * 2,
        Number::Float(f) => f as i32 * 2,
        Number::Complex(r, i) => (r + i) as i32 * 2,
        _ => 0, // catch-all pattern
    }
}
}

match can almost match anything, and more flexible than you can imagine, but we don't elaborate on it here. Refer to Rust 圣经

When you only have one specific variant to match, you can use if let to simplify the code:

#![allow(unused)]
fn main() {
fn print_number(num: Number) {
    if let Number::Integer(i) = num { // if let Variant::Value(v) = expression
        println!("Integer: {}", i);
    }
}

print_number(Number::Integer(42)); // prints "Integer: 42"
print_number(Number::Float(3.14)); // does nothing, as the pattern does not match
}

this snippet only matches Number::Integer, so it will not print anything else. Similarly, we have while-let to match patterns in a loop, which you've seen in the previous section.

#![allow(unused)]
fn main() {
let mut numbers = vec![Number::Integer(1), Number::Float(2.0), Number::Complex(3.0, 4.0)];
while let Some(num) = numbers.pop() {
    if let Number::Integer(i) = num {
        println!("Integer: {}", i);
    }
}
}

Iterators

Rust's developers are experienced in OCaml (a functional programming language, opposed to imperative languages like C or Java), and they have brought some of the functional programming features to Rust. One of them is iterators. This section elaborates on aforementioned Iterator trait, beyond next, filter and collect methods. If you know functional programming, you may have heard of map, sum, fold, zip and other higher-order functions, which are also available in Rust's iterators.

#![allow(unused)]
fn main() {
let numbers = vec![1, 2, 3, 4, 5];
let doubled: Vec<i32> = numbers.iter().map(|x| x * 2).collect();
println!("{:?}", doubled); // prints [2, 4, 6, 8, 10]
}

map takes a lambda function (or called closure in FP, we'll get to that soon) as an argument and applies it to each element of the iterator, returning a new iterator. The collect method is used to convert the iterator back to a collection, in this case, a Vec<i32>. Also, we have sum which is common when computing a vector's norm

#![allow(unused)]
fn main() {
let arr = vec![1, 2, 3, 4, 5];
let norm: f64 = arr.iter().map(|x| x * x).sum().sqrt();
println!("Norm: {}", norm);
}

You can also use fold or reduce to accumulate values to extend sum's functionality, which is a more general form of sum.

#![allow(unused)]
fn main() {
let sum: i32 = arr.iter().fold(0, |acc, x| acc + x); // 0 is the initial value, `acc` is the accumulator
println!("Sum: {}", sum);
let sum: i32 = arr.iter().reduce(|acc, x| acc + x); // `reduce` is similar to `fold`, but it does not take an initial value
}

When you need to iterate over two or more iterators at the same time, you can use zip to combine them into a single iterator. For example, computing a dot product of two vectors:

#![allow(unused)]
fn main() {
let vec1 = vec![1, 2, 3];
let vec2 = vec![4, 5, 6];
let dot_product: i32 = vec1.iter().zip(vec2.iter()).map(|(x, y)| x * y).sum();
println!("Dot product: {}", dot_product);
}

Lambda and Closure

Rust is neither a purely functional programming language nor an imperative one. It supports both paradigms, and as a FP language, it has first-class functions. A typical example is the lambda, a.k.a. anonymous function, which does not have a name and can capture variables from its surrounding scope (note that Rust is hard to define global variables, so closures are extremely useful).

#![allow(unused)]
fn main() {
let add = |x: i32, y: i32| x + y; // define a lambda that adds two numbers
let result = add(2, 3);
println!("Result: {}", result); // prints "Result: 5"
}

As previously mentioned, like in map, || is embraces the parameters of the lambda, and the body is defined after the |s. You can define a more complicated lambda body

#![allow(unused)]
fn main() {
let multiply = |x: i32, y: i32| {
    let result = x * y;
    result // return the result
};
let result = multiply(2, 3);
println!("Result: {}", result);
}

When you try to capture variables from the surrounding scope, it's called a closure, for example:

#![allow(unused)]
fn main() {
let factor = 2;
let multiply = |x: i32| x * factor; // capture `factor` from
println!("Result: {}", multiply(3)); // prints "Result: 6"
}

However, sometimes you may want to take the ownership of the captured variables, for example, you access something that cannot be referenced

#![allow(unused)]
fn main() {
let s = String::from("Hello");
let closure = || println!("{}", s); // this will not compile, as println will take ownership of `s`
}

move keyword is here to help you, it will take the ownership of the captured variables (i.e. the variables that are used inside the closure).

#![allow(unused)]
fn main() {
let s = String::from("Hello");
let closure = move || println!("{}", s); // now `s` is moved into the closure
closure(); // prints "Hello"
// println!("{}", s); 
}

Higher-Order Functions

In Rust, functions have types and traits, and you can pass functions as arguments to other functions, or return functions from functions. Traits of functions are defined as Fn, FnMut, and FnOnce, which are similar to the function types in other languages. They're advanced topics so we won't cover them here, but you can read the Rust documentation for more information.

Types of functions are defined by the types of their parameters and return values only. You can define different names for the same function type, and they're the same function type as long as their signatures match. Here's a simple example of a higher-order function that takes a function as an argument:

fn apply<F>(f: F, x: i32) -> i32
where
    F: Fn(i32) -> i32, // F is a function that takes an i32 and returns an i32
{
    f(x)
}

fn add_one(x: i32) -> i32 {
    x + 1
}

fn multiply_by_two(x: i32) -> i32 {
    x * 2
}

fn main() {
    let result1 = apply(add_one, 5); // applies `add_one` to 5
    let result2 = apply(multiply_by_two, 5); // applies `multiply_by_two` to 5
    let result3 = apply(|x| x + 3, 5); // applies an anonymous function to 5
    println!("Result1: {}, Result2: {}, Result3: {}", result1, result2, result3); // prints "Result1: 6, Result2: 10, Result3: 8"
}

Ownership and Lifetime

I must admit that ownership and lifetime are very sucky features in Rust, and yet it only does when you learn it for the first time. Once you get used to it, it is actually quite powerful and useful, in a good way because it can enforce you to check something that you might forget. Let's jump into it!

Ownership

We suppose that you know something about stack, heap and memory. You're aware that when writing a program, you have to think about how to manage memory, like requesting memory, using it, and then releasing it. The last step is the most important one, while most of us will neglect it.

Bob: Why would I release memory? We got OS to do that for us, right?

Alice: Nah, Bob. OS recycles your shit only when you stop it.

You have to be programming in a memory-aware way, but it sucks. Your mind might be blown if you're not experienced with it or you're writing complex code bases. So here's some ways to omit the pain:

Garbarge Collection (GC): compiler inserts GC code into yours to keep track of the variables while your program is running.
- Pros: user friendly
- Cons: performance loss, incomplete (in some corner cases, it breaks)
Ownership: compiler checks the usage and ownership of memory and releases it automatically when it's no longer needed.
- Pros: performance (as it's only in compile time), completely memory safe
- Cons: steep learning curve

Rust takes the ownership model and strictly adhere to it. An example to show how it solves the problem. Suppose we have a C program that you would probably do

int* foo() {
    int a = 100;
    return &a;
}

You allocate a variable a and return its pointer, nothing wrong? No! This is a "dangling pointer" because a is allocated on the stack, and when the function returns, a is no longer valid. Nobody can use it after that. So how Rust solves this problem? It doesn't allow you to do that at all. If you try to write the same code in Rust:

#![allow(unused)]
fn main() {
fn foo() -> &i32 {
    let a = 100;
    &a // error: cannot return reference to local variable `a`
}
}

You will get a compile-time error saying that you cannot return a reference to a local variable. When foo returns, a is dropped and so the reference to a is no longer valid. Rust prevents this by enforcing ownership rules at compile time. Bare in mind that Rust enforces

A memory region (variable/arrays) can only have one owner at a time. Others must borrow it, i.e., request a reference to it.
For mutable references, there can only be one mutable reference to a memory region at a time and during the lifetime of that reference, no other references can be made to that memory region.
When the owner goes out of scope, the memory region is automatically released (or called dropped in Rust).

When you rewrite it in Rust, you would do

#![allow(unused)]
fn main() {
fn foo() -> i32 {
    let a = 100;
    a
}
}

It works but it looks like C. Did Rust compiler check it? Yes, the blind spot is that i32 as a primitive type is implicitly copied when you return it.

Transfer, Clone and Borrow

Why does this pass the compilation

#![allow(unused)]
fn main() {
let a = 100;
let b = a;
println!("{}", a); // `a` is still valid
}

while this doesn't

#![allow(unused)]
fn main() {
let a = String::from("Hello");
let b = a;
println!("{}", a); // error: value borrowed here after move
}

Did they all transfer ownership? Yes or no. The first one implements a Copy trait (will get to that soon), and therefore it is implicitly copied when you assign it to b. Though a and b are both 100, they are different ones. It's like Java's objects. Whereas, the String type does not implement Copy, so when you assign a to b, the ownership of the memory region is transferred. When you reuse a, it will throw an error because a is no longer holding the ownership of the memory region.

What if a and b holds the same memory region? Imagine that a and b are in the same scope and they go out of scope at the same time. Boom! You have a double free error, and in C/C++, it's like

int* a = malloc(sizeof(int));
int* b = a;
// end of scope
free(a);
free(b); // error: double free

It would be critical if the memory of a (or b) is assigned to another variable, and then you free it, since you're not aware of that. You could be debugging for hours to find the root cause.

Yes, Copy/Clone can solve this problem. Yet, it's expensive when you copy a large memory region, like a vector or a struct, not to mention that copying variables will make them independent, so changes to one will not affect the other. If you miss that, you might end up with unexpected results: why this variable is not updated?

We suggest that you use borrowing for most of the time. Borrowing means that you request a reference to the memory region without taking ownership of it. It's similar to pointers in C/C++ and references in Java/Python. You can borrow a memory region by using the & operator and after that, dereference it with the * operator.

#![allow(unused)]
fn main() {
let a = 114514;
let b = &a; // borrow `a`

assert_eq!(*b, 114514); // dereference `b` to get the value of `a`
assert_eq!(b, 114514);  // don't do this, it will not compile
}

Be aware of the immutablility when you'd change the value of a!

#![allow(unused)]
fn main() {
let mut a = 114;

fn change_value(b: &mut i32) {
    *b = 514; // dereference `b` to change the value of `a`
}

fn change_value_wrong(b: &i32) {
    *b = 514; // error: cannot assign to `*b`, as `b` is an immutable reference
}

change_value(&mut a); // borrow `a` mutably
}

Remember that you can only have one mutable reference?

#![allow(unused)]
fn main() {
let mut a = 114;
let b = &mut a; // borrow `a` mutably
let c = &mut a; // error: cannot borrow `a` as mutable more than
let d = &a; // error: cannot borrow `a` as immutable while it is also borrowed as mutable
}

If you know data race, this is exactly what Rust prevents. You cannot have multiple mutable references to the same memory region at the same time, and you cannot have a mutable reference while there are immutable references to the same memory region. This enforces thread safety. But it's anoying when you do multi-threading. We will talk about it later.

Lifetime

From now on, forget about the delete keyword.

As we said, when the owner goes out of scope, the memory region is automatically released. We have an extended example from above

#![allow(unused)]
fn main() {
let a;
{
    let b = String::from("Hello");
    a = &b;
}
println!("{}", a); // error: value borrowed here after move
}

this is because the lifetime of them disagree

#![allow(unused)]
fn main() {
let a;                             // --------+- 'a
{                                  // --+- 'b |
    let b = String::from("Hello"); //   |     |
    a = &b;                        // --+     |
}                                  //         |
a                                  // --------+
}

But ofter, nothing is perfect.

#![allow(unused)]
fn main() {
fn longest_string(s1: &str, s2: &str) -> &str {
    if s1.len() > s2.len() {
        s1
    } else {
        s2
    }
}

let s1 = String::from("Hello World!");
let s2 = String::from("World");
println!("The longest string is: {}", longest_string(&s1, &s2));
}

Oops! Compiler complains that it cannot infer the lifetime of the returned reference. Because the lifetime of s1 and s2 may be different, and it's runtime dependent. You have to console compiler that you know what you're doing. You can do that by annotating the lifetime of the references in the function signature.

#![allow(unused)]
fn main() {
fn longest_string<'a>(s1: &'a str, s2: &'a str) -> &'a str {
    if s1.len() > s2.len() {
        s1
    } else {
        s2
    }
}

let s1 = String::from("Hello World!");
let s2 = String::from("World");
println!("The longest string is: {}", longest_string(&s1, &s2));
}

By doing this, you tell the compiler that you're pretty sure s1 will live at least as long as s2 (or the opposite).

For more advanced lifetime usage, refer to the Rust Course.

Tuning Rust Code for Performance

Since most of you guys know little about OS, we won't talk much about low-level threading concepts, like synchronization, memory barriers and so on. We will only focus on embarrassingly parallel problems, leveraging Rust's thread safety. Next, we will have a simple look at SIMD, and yet this does not require you to handwrite SIMD code, as Rust provides a good abstraction for it. Finally, we will talk about some ad-hoc optimizations for this challenge.

Parallelism

Everything we talked so far is single-threaded, which is not enough for modern computing. We need to leverage multiple cores to speed up our code. Rust provides a simple way to do this, using the std::thread module. But this is not intuitive at first, so will use another one called rayon. This one provides easy-to-use parallel iterators.

Before we start, you need to add rayon to your Cargo.toml:

cargo add rayon

Then you can use it like this:

use rayon::prelude::*;

fn main() {
    let data = vec![1, 2, 3, 4, 5];
    let doubled: Vec<_> = data.par_iter().map(|&x| x * 2).collect();
}

This snippet will run map in parallel, as the elements in data are independent of each other. This is called embarrassingly parallel, which means that the problem can be easily divided into smaller independent tasks. If you need to create independent tasks other than the iterators, you can use rayon::spawn:

use rayon::prelude::*;

fn main() {
    let data = vec![5, 1, 8, 22, 0, 44];
    rayon::join(
        || println!("Sum: {}", foo(&data)),
        || println!("Double Sum: {}", bar(&data)),
    );
}

fn foo(arr: &Vec<i32>) -> i32 {
    arr.iter().sum()
}

fn bar(arr: &Vec<i32>) -> i32 {
    arr.map(|x| x * 2).iter().sum()
}

To further optimize rayon, we have to understand where the bottleneck is. One problem is that the workload above is trivial and rayon just simply splits them into separate threads. If context switching pops out in your mind, you are right. The overhead is largely due to the uncessary threads and their costs. To avoid this, we can use par_chunks to split the data into chunks in one thread each to keep cores busy

use rayon::prelude::*;

fn main() {
    let data = vec![1, 2, 3, 4, 5];
    let doubled: Vec<_> = data.par_chunks(1024).flat_map(|chunk| {
        chunk.iter().map(|&x| x * 2)
    }).collect();
}

SIMD

Single Instruction Multiple Data (SIMD) is a low-level technique in CPU. Since most of you are not familiar with computer architecture, we won't go that deep. To explain it in a few sentences, SIMD unrolls the loop and executes the same operation on multiple data at once. It's pretty like rayon, but at a lower level. This is a powerful technique to speed up numerical computing, but unfortunately, Rust has not fully supported it yet. To turn on SIMD, you need to switch to the nightly version of Rust and enable features flags.

rustup default nightly

The simplest way to use SIMD in Rust is to hint compiler to use SIMD instructions but for now, compiler isn't smart enough to do this automatically. Also, SIMD has its limitations, like it works at maximum speed only when the data is aligned and independent.

The current simplest way to use SIMD in Rust is portable-simd. Let's take sum again as the example

#![allow(unused)]
#![feature(portable_simd)]  // Release the nightly compiler kraken
fn main() {
use multiversion::{multiversion, target::selected_target};
use std::simd::prelude::*;

#[multiversion(targets("x86_64+avx2+fma", "x86_64+avx", "x86_64+sse2"))]
fn simd_sum(x: &Vec<f32>) -> f32 {
    const SIMD_WIDTH: usize = const { 
        selected_target!().suggested_simd_width::<f32>().unwrap_or(1)
    };

    let (peel, body, tail) = x.as_simd::<SIMD_WIDTH>();
    let simd_sum = body.into_iter().sum::<Simd<f32, SIMD_WIDTH>>();
    let scalar_sum = peel.into_iter().chain(tail).sum::<f32>();
    simd_sum.reduce_sum() + scalar_sum
}
}

The worst way but the most compatible way to use SIMD in Rust is to use std::arch module. And you need to handwrite assembly code. Well, you don't need to do this in this challenge, but it's good to know that you can do it if you want.

Compilation

The last thing we need to talk about is the compilation. Rust has a powerful optimization system, and you can enable it by setting the release profile in your Cargo.toml:

[profile.release]
opt-level = 3
lto = "fat"

opt-level controls the optimization level made automatically by the comiler, and lto enables link-time optimization, which allows the compiler to optimize across crate boundaries, i.e., by thinking about the program as a whole. Meanwhile, you can enable feature flags to optimize the code further. For example, you can enable simd feature flag to use SIMD instructions in your code. You can also use multiversion to enable multiple versions of the same function for different targets, which can be useful for performance optimization.

When compiling, use the --release flag to enable the release profile:

cargo build --release

Trait and Generics

This chapter will backtrack to Rust's type system and explain some of the common hazards and pitfalls when working with traits and generics. Though the type system seems flexible, it's still quite static and needs your attention - that's why Rust is charming.

Generics

You might've learnt it from C++ or Java. It's pretty similar in Rust.

#![allow(unused)]
fn main() {
fn add<T>(a: T, b: T) -> T {
    a + b // T must implement the `Add` trait
}
}

Here, T is a generic type parameter, as the template parameter in C++. Rust can infer the type of T most of the time,

fn main() {
    let a = 1;
    let b = 2;
    let c = add(a, b); // T is inferred as i32
    println!("{} + {} = {}", a, b, c);
}

but you can also specify it explicitly:

#![allow(unused)]
fn main() {
add::<i32>(a, b); // T is explicitly specified as i32
}

but not every type implements the Add trait, so you need to specify a bound for T:

#![allow(unused)]
fn main() {
use std::ops::Add;

fn add<T: Add<Output = T>>(a: T, b: T) -> T {
    a + b // T must implement the `Add` trait
}
}

Generics can also be used with structs and enums, allowing you to define types that can work with any data type.

#![allow(unused)]
fn main() {
struct Point<T> {
    x: T,
    y: T,
}
}

Trait and `impl`

Traits are a way to define shared behavior in Rust. You can think of them as interfaces in other languages. Here's how you can define a trait:

#![allow(unused)]
fn main() {
trait Shape {
    fn area(&self) -> f64;
}
}

Then, you can implement this trait for different types:

impl Shape for Point<f64> {
    fn area(&self) -> f64 {
        0.0 // Points don't have an area
    }
}

fn main() {
    let p = Point { x: 1.0, y: 2.0 };
    println!("Area of point: {}", p.area()); // Calls the area method
}

As you may notice, p.area() looks like a OOP-styled. Rust is not an OOP language but it supports defining functions for a stuct or enum, which is called impl block. You can define methods for a struct or enum in an impl block, and you can also implement traits for them.

#![allow(unused)]
fn main() {
impl Point<f64> {
    fn new(x: f64, y: f64) -> Self {
        Point { x, y }
    }
}
}

Besides explicitly implementing traits, Rust also provides a way to implement traits with default methods, using macros.

#![allow(unused)]
fn main() {
#[derive(Debug, Clone, Copy)]
struct Point<T> {
    x: T,
    y: T,
}
}

Now you have Copy, Clone, and Debug traits implemented for Point<T>. These dirty works are long gone!

We have to mention another useful trait, Display where you can define how a type should be formatted when printed.

use std::fmt;

impl<T: fmt::Display> fmt::Display for Point<T> {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        write!(f, "Point({}, {})", self.x, self.y)
    }
}

fn main() {
    let p = Point { x: 1.0, y: 2.0 };
    println!("Point: {}", p); // Calls the Display trait
}

Const Generics

Const generics is a feature in Rust that allows you to define a generic type with a constant value. You can't imagine that before it, Rust actually had a stupid problem

fn main() {
    let v1 = [1u32; 32];
    let v2 = [1u32; 33];

    println!("{:?}", v1);
    println!("{:?}", v2);
    //               ^^ `[u32; 33]` cannot be formatted using `{:?}` because it doesn't implement `std::fmt::Debug`
}

because Rust's libcore implemented std::fmt::Debug for all arrays with size from 0 to 32 but not for 33, by expanding macro. This seems pretty weird, so Rust introduced a new feature called const generics. And we could imagine that fmt becomes simple

#![allow(unused)]
fn main() {
impl<T: fmt::Debug, const N: usize> fmt::Debug for [T; N] {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        fmt::Debug::fmt(&&self[..], f)
    }
}
}

As you see, similar to array, const generics can be used to define a generic type with a constant value, like matrix and vector, which is quite useful in numerical computing. An example from https://github.com/getong/rust_example/blob/main/const_workspace_example/const_generics_example/src/main.rs

use std::{
    fmt::Debug,
    ops::{Add, Mul},
};

#[derive(Copy, Clone, Debug)]
struct Matrix<T: Copy + Debug, const N: usize, const M: usize>([[T; M]; N]);

impl<T: Copy + Debug, const N: usize, const M: usize> Matrix<T, N, M> {
    pub fn new(v: [[T; M]; N]) -> Self {
        Self(v)
    }

    pub fn with_all(v: T) -> Self {
        Self([[v; M]; N])
    }
}

impl<T: Copy + Default + Debug, const N: usize, const M: usize> Default for Matrix<T, N, M> {
    fn default() -> Self {
        Self::with_all(Default::default())
    }
}

impl<T, const N: usize, const M: usize, const L: usize> Mul<Matrix<T, M, L>> for Matrix<T, N, M>
where
    T: Copy + Default + Add<T, Output = T> + Mul<T, Output = T> + Debug,
{
    type Output = Matrix<T, N, L>;

    fn mul(self, rhs: Matrix<T, M, L>) -> Self::Output {
        let mut out: Self::Output = Default::default();

        for r in 0..N {
            for c in 0..M {
                for l in 0..L {
                    out.0[r][l] = out.0[r][l] + self.0[r][c] * rhs.0[c][l];
                }
            }
        }

        out
    }
}

type Vector<T, const N: usize> = Matrix<T, N, 1usize>;

fn main() {
    let m = Matrix::new([[1f64, 0f64, 0f64], [1f64, 2f64, 0f64], [1f64, 2f64, 3f64]]);
    let v = Vector::new([[10f64], [20f64], [40f64]]);

    println!("{:?} * {:?} = {:?}", m, v, m * v);
}

Challenge Overview

In the burgeoning era of quantum computing, traditional cryptographic methods are under threat. Visionary scientists have developed new 'post-quantum' cryptosystems, one of which is based on the Learning With Errors (LWE) problem. LWE's security relies on the presumed difficulty of solving certain mathematical problems involving lattices. -- Google Gemini

Learning With Errors (LWE)

Learning with Errors (LWE) is a foundational problem in lattice-based cryptography. SUSTech students should alreadly take the linear algebra course, so we won't bother repeating the basics of linear algebra here.

Integer Lattice is a group of basis vectors spanning a discrete grid in n-dimensional space. All of the vectors in the lattice are expressed as integer linear combinations of the basis vectors. However, if we constuct a vector using

$$ \mathbf{v} = \mathbf{A} \cdot \mathbf{x} + \mathbf{e} $$

where A is a matrix (lattice), x is a vector of secret values, and e is a small error vector. It's hard to find x given v, A, and e, because all you can do is to guess or go through every combination of x, which is computationally infeasible for large dimensions.

One may argue that: well, we could use guassian elimination to solve the linear system, but the error vector e accumulates the error in the system, making it impossible to find the exact solution. The error vector is small, but it is a disaster for the system.

That gives security to the LWE problem.

Fully Homomorphic Encryption (FHE)

Acknowledgements: pictures are all from tfhe-rs and its blog post.

When applying LWE to cryptography, we can either put our secret in the vector x, and we can do an addition on the ciphertext because suppose

$$ b_1 = A \cdot x_1 + e_1 $$

$$ b_2 = A \cdot x_2 + e_2 $$

if we add them together, we get

$$ b_1 + b_2 = A \cdot (x_1 + x_2) + (e_1 + e_2) = A \cdot (x_1 + x_2) + e^{\prime} $$

but it's weird that we have e as the secret key and we have to add the secret keys to recover the original secret. How can we know what the operations done on the ciphertexts? So it's not applicable. The most common way is to use the vector x as the secret key and put the plaintext in the error vector e

$$ b = A \cdot x + e + m * \Delta $$

so that we have (A, b) as the public key and x as the secret key. The real implementation will be more complicated, for example

It's tfhe-rs's choice of GLWE, and for decryption, it's straightforward

The ciphertext may look like

adding them up is like

in math, we have

$$ b_1 + b_2 = A \cdot x + (e_1 + e_2) + (m_1 + m_2) * \Delta $$

the error is trivial as long as it's less than the delta. The additive property of the ciphertext is called homomorphic addition. If we extend the computational property beyond addition, like with multiplication, comparison and etc, it becomes fully homomorphic encryption (FHE).

With that, we can confidentially handle the computation task to the untrusted server, and the server can compute the result without knowing the plaintext. Isn't it cool?

Playing it with a Game of Life

In this challenge, we will implement a simple Game of Life using LWE. The Game of Life is a cellular automaton devised by the British mathematician John Horton Conway in 1970. It consists of a grid of cells that can be either alive or dead, and the state of each cell changes based on the states of its neighbors.

However, the FHE is more expensive than expected due to the encryption/decryption/homomorphic operations, so we need to optimize the Game of Life to make it efficient. Thankfully, the game of life is naturally parallelizable.

Cracking LWE (Bonus)

After finishing Fhe Game of Life, we can now try to crack the LWE problem. It's not that hard as we scale down the parameters a little bit. The point of this challenge is to understand how to accelerate a problem that you probably don't know a bit. When we say optimize it, we are saying

you need to understand the problem and research about the algorithms that can solve it
you need to implement the algorithm in a way that is efficient and scalable, and in Rust
you need to optimize the implementation using parallel, SIMD, and other techniques

To crack the LWE problem, we will find the secret vector x given the public key (A, b).

An intuitive way to crack LWE is to reduce it to a Closest Vector Problem (CVP). CVP defines a problem of finding the closest vector to some vector in lattice. It's formulated as follows: given a vector w that is not in the lattice, find a vector v in the lattice such that the distance between w and v is minimized. The distance is usually measured by the Euclidean norm.

Normally, when the dimension is small, Babai's nearest plane algorithm can solve the problem

Find a basis that is sufficiently orthogonal with LLL (Lenstra–Lenstra–Lovász lattice basis reduction)
let b = t (t is the encrypted vector)
for j from n to 1, run b = b - B[j] * c[j] where c = round(b * hat(B[j] / (hat(B[j]) * hat(B[j]))) (hat(B[j]) means the gram schmidt of B[j], and B[j] is the j-th basis vector after LLL reduction)
return t - b

However, under a module q, we need to do some tricks to make it work. Since

$$ b = A \cdot x + e \mod q $$

we have

$$ A x + q I_m k = b - e $$

so that to find x, we can construct a new basis with

$$ [A | q I_m] \begin{bmatrix} x \ k \end{bmatrix} = b - e = b^{\prime} $$

we don't need to care about the k at the solution. The final step is to do guassian elimination on the

$$ A x = b^{\prime} \mod q $$

which is trivial.

Hints

Something to help you get started with the exercises in this section. First of all, you should already know what this challenge requires you to do, and download the starter code from the repos.

Parallelization

Everything in the starter code except the main.rs is parallelizable and modifiable. For example, the encryption and decryption simply iterate the grid and encrypt/decrypt each cell, so you can use par_iter to parallelize the process. The same goes for the update_grid function, which updates the grid based on the rules of the Game of Life.

Simple SIMD

You don't need to handwrite the SIMD code, since the tfhe-rs library already provides a SIMD implementation for the LWE encryption scheme. Search for how to enable this.

Compilation

You know what to do.

Ad-hoc optimizations

One of the most effective optimizations I can think of is to clone the tfhe-rs and optimize it, but it's not really necessary for this challenge. The second best way would be to benchmark why the starter code is slow, like the computation cost for the FHE types like FheUInt8.

Meanwhile, there're something unnecessary or written in a dumb way, such as unnecessary cloning. You should remove it.

(Bonus) Switching to different algorithms

The Babai's nearest plane algorithm is not the best algorithm for the LWE decryption. I've noticed that we have other algorithms that might work better, including but not limited to:

BKZ algorithm
pnj-bkz
Sieve (G6k)
You tell me.

I'm pretty excited to see what you can come up with. Surprise me!

SUSTCSC 2025 RUST