Recreating a Secret Santa App in Rust with WASM (Part 1)

I'm trying to learn Rust and WASM together and this seemed like an interesting project to pursue. This part covers the Rust portion of the project.

I've always been annoyed by how SecretSanta apps make you sign up and give them your email and other details. They do make it simple in some ways but more complex in others. Then I found this very cool example. Which uses an encrypted hash to hide details from a human observer but which can then be decrypted to give a person their SecretSanta. Obviously this isn't how encryption was intended to be used because the private key needs to be available to online application to decrypt the hash, but it serves its purpose and means the App doesn't need to know someone's email address or even store their name.

Perfect for a static website like this!

The full code for the Rust implementation is available in this repository.

Scoping

The JS implementation I wanted to emulate for this project had taken an approach of serving JS in HTML alongside styling. The codebase was compact but required a little deciphering to pull out the secret santa bits. The core of JS included three main parts; the instruction parser, the secret santa algorithm and the encryption/decryption of matches.

An important step in the scoping was choosing where to put the boundary between the Rust/WASM and the DOM rendering/styling. Given the objectives of learning Rust, I wanted to try and put as much of the secret santa logic into Rust as possible but decided to avoid DOM manipulations. As a side effect, the Rust implementation can also be used as a standalone library by other code.

Instruction Parser

Instructions for the Secret Santa are provided by the user as ASCII text. Each participant is labelled and then given a set of restrictions or an enforced pairing. For example, if Ben has no restrictions then the line is

Ben

Labels can also be complex

Ben (the older one)

If Tom cannot get Ben for secret santa then the blocked pairing label is prefixed by a ! and the instruction is

Tom !Ben

It is possible to give multiple blocked pairings as well

Tom !Ben !Ben (the older one)

And we can force a match for one person to another using a = prefix.

Tom =Jerry

Finally all text after a # is ignored as a comment.

struct Participant

Each instruction about a participant represents the minimal amount of information needed by the secret santa algorithm. To capture each instruction I implemented a struct capturing the Participant name or label, the pairing as an option and the blocklist as an optional HashSet.

participant.rs

#[derive(Default, Debug, Eq, Clone)]
pub struct Participant {
    pub name: String,
    pub paired_with: Option<String>,
    pub blocklist: Option<HashSet<String>>,
}

If an enforced pairing (the = prefix) or a blocked pairing (the ! prefix) are not supplied with an instruction then we cannot set these values in the struct, hence they are kept as options. The HastSet is useful, because if a blocked name is supplied twice it will only be added to the list once. HashSets enforce uniqueness of values in the set.

There will be some traits required for Participant to support the secret santa algorithm but these will be introduced in that section. For now, Participant just needs a constructor.

participant.rs

impl Participant {
    pub fn new(name: String) -> Self {
        Participant {
            name,
            blocklist: None,   // Default to None
            paired_with: None, // Default to None
        }
    }
}

Instruction parsing

Instruction parsing can be broken down into a number of sequential steps.

1. Remote comments from and white space around each line.
2. Get the participant label.
3. Get any blocked labels for 2.
4. Get and enforced match for 2.
5. Return a Participant with parsed values.

I approached this problem in a functional way using a mixture of Options and Results in Rust to handle errors. Line components are extracted or removed using the regex crate. The primary method I used to extract text from each line utilised the capture method for a compiled regex. I found the regex crate somewhat more difficult to use then similar libraries in other languages. A Regex instance has many methods that might be used for extraction and they all return different structs. The key seemed to be to understand what traits the structs implemented so that the captured text could be extracted.

The function get_instruction which trims comments and whitespace is an example of this. re.captures returns an iterable struct over the groups identified by the Regex. The iterable, which can only be of length one still needs to be post-processed through the map and extract operations to get the necessary data.

fn get_instruction(instruction: &str) -> Option<&str> {
    let re = Regex::new(r"(^[^#]+)").unwrap();
    let Some((_, [inst])) = re.captures(&instruction).map(|cap| cap.extract()) else {
        return None;
    };
    Some(inst.trim())
}

The same process is repeated in subsequent regex extraction functions to get the participant name and rules.

Secret Santa algorithm

Algorithm

There are a few considerations when building the secret santa algorithm.

1. We want people to be assigned randomly to other people.
2. We need to observe the rules for all participants.
3. Sometimes the rules might be too restrictive in that there aren't enough participants who a person can be matched with.

My approach to this can be broken down into the following steps.

1. Create two sets of all names. set_a for givers and set_b for receivers.
2. Check for any forced pairings and remove the giver from set_a and the receiver from set_b.
3. Recursively generate one giver and receiver pair by:
   1. Sort set_a by the number of possible matches remaining in set_b accounting for rules.
   2. If set_a is empty everyone has been assigned, return OK.
   3. If the first participant has no possible matches, return error.
   4. If the first participant in set_a only has 1 possible match, make them a pair and update set_a and set_b then recurse.
   5. If the first participant has two or more possible matches, choose one at random, update set_a and set_b then recurse.

The sorting step is important because it gives the algorithm the best chance of finding a match for all people. We want to ensure that participants with the fewest match options are prioritised when assigning the matches.

Participant Traits

The development of the algorithm in Rust got slightly tricky when trying to cover different functionality. There are strong limitations around certain structs (like HashSet) which needed some trial and error to understand. The HashSet type is important in the algorithm because it allows the easy adding and removal of names from set_a and set_b. I also use a HashSet<Participant> in a SecretSanta struct to hold the participants created during the parsing of the Instructions and while generating pairings.

Firstly, there are a few traits that can be implemented on Participant to make referencing them in a HashSet easier. This requires creating methods that facilitate comparisons between String types and Participants. The trait needed is PartialEq for String. This directly compares a String to the name value of the Participant struct.

participant.rs

impl PartialEq<Participant> for String {
    fn eq(&self, other: &Participant) -> bool {
        self == &other.name
    }
}

The reciprocal can also be implemented allowing bidirectional comparisons.

participant.rs

impl PartialEq<String> for Participant {
    fn eq(&self, other: &String) -> bool {
        &self.name == other
    }
}

To make Participant hashable, the Hash trait should also be implemented. Here, the name is the important value in the struct and will form the sole basis of the hash - ignoring the other values.

participant.rs

impl Hash for Participant {
    // Only need name in hash as it is the unique bit
    fn hash<H: Hasher>(&self, state: &mut H) {
        self.name.hash(state);
    }
}

The String comparisons and the Hash trait facilitate methods in SecretSanta like get_name and contains where Participant instances in a HashSet can be referenced with just a Participant instance that has the name only.

secretsanta.rs

pub struct SecretSanta {
    participants: HashSet<Participant>,
}

impl SecretSanta {
    /// SecretSanta contains recipient with name
    pub fn contains(&self, name: &str) -> bool {
        self.participants
            .contains(&Participant::new(name.to_string()))
    }

    /// SecretSanta get participant by name
    pub fn get_name(&self, name: &str) -> Option<&Participant> {
        let p = Participant::new(name.to_string());
        let part = self.participants.get(&p)?;
        Some(part)
    }
}

HashSet limitations

After some experimentation in the algorithm it became clear that HashSet have issues around ordering. Specifically, the Rust implementation does not guarantee the set order under iteration which means sorting and indexing into the set are not possible.

The sorting issue was overcome by using a BTreeMap, an alternative to HashMap. The BTreeMap does support ordering, so it was used when calculating the number of possible matches for givers in set_a. find_matches is a method of Participant that looks for valid matches in the argument given the blocklist rules. The insertion into the tree_a instance automatically sorts based on the key.

snippet

 let mut tree_a = BTreeMap::new();

for p in set_a.iter() {
    let Some(part) = self.get_name(p) else {
        return Err(SecretSantaError::new("Instructions issue".to_string()));
    };
    let n_matches = part.find_matches(&set_b).len();
    tree_a.insert(n_matches, part);
}

Indexing into the HashSet for selecting a random name in cases where more than one recipient are possible choices also requires an ordered collection. The simplest solution was to transform the matches HashSet into a Vec<&String> which contains ordered pointers to the names in matches. Then a random index can be chosen.

snippet

let matches = part.find_matches(&set_b);
let vec_matches: Vec<&String> = matches.iter().collect();
let pairing = vec_matches
    .choose(&mut thread_rng())
    .cloned()
    .expect("Something went wrong!");

The full algorithm is available in secretsanta.rs.

Encryption / Decryption

I used the RustCrypto crate collection for encryption in Rust. The documentation is a little patchy and the broad use of traits can make understanding how the libraries fit together a little difficult. There are some limited examples for some of the crates but they aren't always direct copy and paste.

Similar to the original implementation I went for AES (aes-gcm-siv) and 256 byte key. AES is a symmetric encryption algorithm which means the same key is used on decryption. Although other security measures are needed like verification of inputs in typical encryption processes, the objective here is only to obfuscate the paired name for use in a URL query string.

Encryption

The encryption needs three arguments, the message, a suitable key and a nonce or initialisation vector. Usually the key would be kept secret but we will provide all the information necessary to decrypt the message to the user.

The key and nonce are generated with the generate_nonce and generate_key functions. Note that Key, OsRng and others come from a common aead crate while Aes256GcmSiv is implementations of traits associated with these base structs.

crypto.rs

use aes_gcm_siv::{
    aead::{generic_array::GenericArray, Aead, Key, KeyInit, OsRng},
    Aes256GcmSiv, // Or `Aes128GcmSiv`
    Nonce,
};
use rand::RngCore;

/// Generate a random nonce with 96bit fixed size.
pub fn generate_nonce() -> Nonce {
    let mut rand = [0u8; 12];
    OsRng.fill_bytes(&mut rand);
    let nonce = Nonce::from_iter(rand);
    nonce
}

// Generate a 256bit key
pub fn generate_key() -> Key<Aes256GcmSiv> {
    let key = Aes256GcmSiv::generate_key(&mut OsRng);
    key
}

A message can then be encrypted using the key and nonce.

pub fn encrypt(msg: &str, key: &Key<Aes256GcmSiv>, nonce: &Nonce) -> Vec<u8> {
    let cipher = Aes256GcmSiv::new(key);
    let ciphertext = cipher.encrypt(nonce, msg.as_bytes()).unwrap();
    ciphertext
}

The returned key, nonce and ciphertext are bit representations that are not compatible with ASCII or UTF-8 characters. This means it isn't directly usable in a URL query which we will need for the frontend. Instead, the bits must be encoded into text. This can be done using the base64ct crate. Other bases are also available. The URL safe encoding used here is helpful because it does not require an alphabet to be supplied.

lib.rs

fn encrypt_secret_santa(paired_with: &str) -> EncryptedSecretSanta {
    let key = crypto::generate_key();
    let nonce = crypto::generate_nonce();
    let ciphertext = crypto::encrypt(paired_with, &key, &nonce);
    let enc_ss = EncryptedSecretSanta {
        key: Base64Url::encode_string(&key),
        nonce: Base64Url::encode_string(&nonce),
        pairing: Base64Url::encode_string(&ciphertext),
    };
    enc_ss
}

Decryption

Decryption occurs in the reverse order. First the encoded strings provided by the user are decoded. the #[wasm_bindgen(catch)] is needed because this function will be exposed to the frontend.

lib.rs

fn decode_vec(input: &str) -> Result<Vec<u8>, SecretSantaError> {
    match Base64Url::decode_vec(input) {
        Ok(v) => Ok(v),
        Err(_) => Err(SecretSantaError::new(
            "Could not decode secrets".to_string(),
        )),
    }
}

#[wasm_bindgen(catch)]
pub fn decrypt_secret_santa(
    key: &str,
    nonce: &str,
    ciphertext: &str,
) -> Result<String, SecretSantaError> {
    let dc_key = decode_vec(key)?;
    let dc_nonce = decode_vec(nonce)?;
    let dc_ct = decode_vec(ciphertext)?;
    let name = crypto::decrypt(&dc_ct, &dc_key, &dc_nonce);
    Ok(name)
}

Examples of decryption from previously created keys were difficult to find, but the bit representations of the key and nonce supplied by the user can be used to decrypt the ciphertext.

crypto.rs

pub fn decrypt(ciphertext: &Vec<u8>, key: &Vec<u8>, nonce: &Vec<u8>) -> String {
    let cipher = Aes256GcmSiv::new_from_slice(&key).expect("Key was incorrect");
    let nonce_ga: GenericArray<u8, _> = GenericArray::clone_from_slice(nonce);
    // let cipher = Aes256GcmSiv::new(key);
    let msg = cipher.decrypt(&nonce_ga, ciphertext.as_ref()).unwrap();
    String::from_utf8(msg).unwrap()
}

Generate secrets

The final step was to combine the parsing of the instructions, the pairing and the encryption into an accessible interface for the frontend. A little trickery was needed with serde to serialise the HashMap used for the secrets into a JS compatible type - an Object of nested Objects in this case.

The catch property for wasm_bindgen allows for gracious handling of the Result with errors catchable within JS.

lib.rs

#[wasm_bindgen(catch)]
pub fn get_secret_santas(instructions: String) -> Result<JsValue, SecretSantaError> {
    let mut secret_santa = SecretSanta::new();

    // loop all lines
    for i in instructions.trim().split('\n') {
        secret_santa.add_instruction(&i)?;
    }
    secret_santa.generate_pairings()?;

    let pairings = secret_santa.get_pairings();
    let enc_pairings: HashMap<String, EncryptedSecretSanta> = pairings
        .iter()
        .map(|(k, v)| (k.clone(), encrypt_secret_santa(v)))
        .collect();

    match serde_wasm_bindgen::to_value(&enc_pairings) {
        Ok(v) => return Ok(v),
        Err(_) => return Err(SecretSantaError::new("Serialisation error".to_string())),
    }
}

Notes & Issues

Rust crates

Rust has a pretty small standard library which means there has been a lot of crate proliferation over the years. When searching for a crate or set of crates to use it can be difficult to know what exactly to use. Often you'll be guided by examples or when some crates have good documentation. Some crates or sets of crates seem to becoming the standard like RustCrypto but there is no firm endorsements either way from core Rust.

Rust and WASM

Initially I had worked from the Rust WASM tutorial which was structured in a way that it exported most of its functions to JS. I found that complex Rust structs/types didn't play nicely with WASM. Introducing non-standard structs and types to JS requires a lot of overhead to manage serialisation and deserialisation using serde.

Instead I opted to limit the interface between Rust and WASM/JS by keeping much of the internals Rust only. I then offered a limited interface to JS through a couple of key functions. This meant moving everything into Rust (apart from frontend) into Rust and it worked out in the end.

rstest crate

I discovered the rstest crate which was a good attempt to create Pytest like functionality in Rust testing. I wouldn't say its as convenient but it makes things a bit easier. Especially repetitive fixture set up.

Links

• Rust repository
• Working Frontend