Use Case: Stable Matching

Every year in the United States, ~50,000 graduating medical students (doctors, for short) are placed into the residencies where they will begin their careers by the National Resident Matching Program (or The Match). To do so, the program finds a stable matching: an assignment of doctors to medical programs (hospitals, for short) such that there is no pair of doctor and hospital that would prefer to be assigned each other over the match(es) they ended up with. Each candidate doctor ranks their preferred hospitals and each hospital ranks their preferences in candidates, and the matching proceeds algorithmically.

One of the original problems in the field of algorithmic mechanism design, the matching program uses the Roth-Peranson algorithm (1999), a modification of the earlier Gale-Shapley algorithm (1962). These contributions in large part earned Roth & Shapley the 2012 Nobel Prize in Economics.

The Match is a classic example of a computation whose transparency and accountability can benefit from private verifiable computation: at present, doctors receive no direct assurance that an algorithmic decision that will shape their careers (and their career earnings) is being executed correctly. However, The Match cannot simply publish a transcript of the matching, as it would harm the privacy of the doctors in particular (“Alice said she wanted to come back home for residency, but she didn’t rank any local hospitals” or “when we interviewed Bob he said fifteen years ago he ranked us highly in The Match, but he only had us seventh”). Anonymizing the doctors can only accomplish so much as it offers only the illusion of privacy; modern re-identification techniques routinely pierce de-identified data. As a result, anonymization fails to actually anonymize. Our goal is to create a system that provides complete transparency about the correctness of the matching algorithm while preserving the privacy of all preference rankings.

Specifically, we want to generate a cryptographic proof that demonstrates the Gale-Shapley algorithm was executed correctly and produced a stable matching, without revealing any individual’s private preferences. The Nexus zkVM enables us to achieve exactly this balance between accountability and privacy.

---

1

Implementation — initialize host and guest programs

Follow the SDK Quick Start. After installing the zkVM, to initialize the host and guest programs, run:

Initialize host and guest

$ cargo nexus host matching

2

Guest Program

This guest program is the program to be proven; it implements the matching itself using the Gale-Shapley approach.

matching/src/guest/src/main.rs

stable_matching implementation

#![cfg_attr(target_arch = "riscv32", no_std, no_main)]

extern crate alloc;
use alloc::collections::BTreeSet;
use alloc::{vec, vec::Vec};

fn stable_matching(
    n: usize,
    mut employers: BTreeSet<usize>,
    mut candidates: BTreeSet<usize>,
    employer_prefs: Vec<Vec<usize>>,
    candidate_prefs: Vec<Vec<usize>>,
) -> Vec<Option<usize>> {
    let mut hires: Vec<Option<usize>> = vec![None; n];
    while !employers.is_empty() {
        let next = employers.pop_first().unwrap();
        let prefs = &employer_prefs[next];

        for c in prefs {
            if candidates.contains(c) {
                hires[next] = Some(*c);
                assert!(candidates.remove(c));
                break;
            } else {
                let current = hires
                    .iter()
                    .position(|&x| x.is_some() && *c == x.unwrap())
                    .unwrap();
                if candidate_prefs[*c].iter().position(|&x| next == x)
                    < candidate_prefs[*c].iter().position(|&x| current == x)
                {
                    assert!(employers.insert(current));
                    hires[next] = Some(*c);
                    hires[current] = None;
                    break;
                }
            }
        }
    }

    hires
}

The function takes:

• a set of candidates (doctors),

• a set of employers (hospitals),

• preference rankings in matrix form (row i of employer_prefs encodes the ranking for the i-th employer),

• a parameter n = employers.len().

It returns a vector hires of length n, where hires[j] = i means the j-th hospital hires the i-th doctor.

You also need a main to handle zkVM inputs/outputs and declare which inputs are public/private.

matching/src/guest/src/main.rs

guest main

#[nexus_rt::main]
#[nexus_rt::private_input(prefs)]
#[nexus_rt::public_input(lists)]
fn main(
    prefs: (Vec<Vec<usize>>, Vec<Vec<usize>>),
    lists: (BTreeSet<usize>, BTreeSet<usize>),
) -> Vec<Option<usize>> {
    let (mut employer_prefs, mut candidate_prefs) = prefs;
    let (mut employers, mut candidates) = lists;

    let n = employers.len();
    let m = candidates.len();

    nexus_rt::print!("Matching {} employers with {} candidates... ", n, m);

    let hires = stable_matching(n, employers, candidates, employer_prefs, candidate_prefs);

    nexus_rt::println!("completed.");

    hires
}

Note: inputs default to private unless explicitly declared public. The public inputs/outputs here leak only which hospital each candidate matched with (the hires vector), which is acceptable for auditing the algorithm while keeping preferences private.

3

Host Program

The host program compiles the guest and runs it with the provided preferences (these preferences are private inside the host).

matching/src/main.rs

host main

use nexus_sdk::{
    compile::{cargo::CargoPackager, Compile, Compiler},
    stwo::seq::Stwo,
    ByGuestCompilation, Local, Prover, Viewable,
};
use std::collections::BTreeSet;

type Matches = Vec<Option<usize>>;
type Prefs = (Vec<Vec<usize>>, Vec<Vec<usize>>);
type Lists = (BTreeSet<usize>, BTreeSet<usize>);

const PACKAGE: &str = "guest";

fn main() {
    println!("Compiling guest program...");
    let mut prover_compiler = Compiler::<CargoPackager>::new(PACKAGE);
    let prover: Stwo<Local> =
        Stwo::compile(&mut prover_compiler).expect("failed to compile guest program");

    let n = 10;
    let m = 8;
    assert!(m < n);

    let mut employers = BTreeSet::<usize>::new();
    let mut candidates = BTreeSet::<usize>::new();

    for i in 0..n {
        employers.insert(i);
        if i < m {
            candidates.insert(i);
        }
    }

    let employer_prefs = vec![\
        vec![4, 1, 2, 7, 3, 0, 6, 5],\
        vec![0, 1, 4, 5, 7, 2, 6, 3],\
        vec![3, 7, 4, 6, 2, 0, 5, 1],\
        vec![4, 6, 0, 2, 7, 3, 5, 1],\
        vec![2, 6, 1, 3, 7, 0, 4, 5],\
        vec![1, 4, 5, 3, 7, 0, 6, 2],\
        vec![1, 5, 4, 0, 6, 2, 7, 3],\
        vec![3, 6, 1, 2, 7, 0, 5, 4],\
        vec![7, 5, 3, 4, 1, 6, 2, 0],\
        vec![0, 6, 1, 4, 5, 2, 7, 3],\
    ];

    let candidate_prefs = vec![\
        vec![0, 5, 7, 8, 3, 1, 4, 2, 6, 9],\
        vec![8, 2, 0, 9, 3, 4, 5, 6, 1, 7],\
        vec![3, 6, 4, 0, 5, 9, 7, 8, 2, 1],\
        vec![2, 9, 7, 3, 4, 1, 5, 8, 0, 6],\
        vec![7, 5, 9, 4, 6, 8, 0, 1, 3, 2],\
        vec![4, 1, 7, 6, 2, 9, 8, 0, 5, 3],\
        vec![0, 5, 3, 6, 8, 7, 4, 1, 9, 2],\
        vec![7, 5, 6, 1, 4, 0, 2, 8, 9, 3],\
    ];

    println!("Proving execution of vm...");
    let (view, proof) = prover.prove_with_input::<Prefs, Lists>(
        &(employer_prefs, candidate_prefs),
        &(employers, candidates),
    ).expect("failed to prove program");

    println!(
        ">>>>> Logging\n{}<<<<<",
        view.logs().expect("failed to retrieve debug logs").join("")
    );
    assert_eq!(view.exit_code().expect("failed to retrieve exit code"), nexus_sdk::KnownExitCodes::ExitSuccess as u32);

    let hires = view.public_output::<Matches>().expect("failed to retrieve public output");

    print!("Found matching (employer, candidate): ");
    for i in 0..n {
        if i > 0 {
            print!(", ")
        }
        print!(
            "({}, {})",
            i,
            if hires[i].is_some() {
                hires[i].unwrap().to_string()
            } else {
                "None".to_string()
            }
        );
    }
    println!("\n");

    /// the host program would go on to publish `view` and `proof` publicly.
}

The ranking matrices shown above are random example data for demonstration.

4

Verification

Once the program, its public input/output (view) and the proof are published, any interested party can verify correctness without access to preferences.

verifier snippet

println!("Verifier recompiling guest program...");
let mut verifier_compiler = Compiler::<CargoPackager>::new(PACKAGE);
let path = verifier_compiler.build().expect("failed to (re)compile guest program");

print!("Verifying execution...");
proof.verify_expected_from_program_path::<&str, Lists, Matches>(
  &(employers, candidates),                       // at view.public_input
  nexus_sdk::KnownExitCodes::ExitSuccess as u32,  // at view.exit_code
  &hires,                                         // at view.public_output
  &path,                                          // path to program binary
  &[]                                             // no associated data,
).expect("failed to verify proof");

If the published matching (hires) has been tampered with in a way that violates Gale-Shapley guarantees, verification will fail.

Limitation: a verifier cannot directly confirm that the private preference matrices themselves are the ones originally provided by participants. The zkVM guarantees there exists some private input for which the execution is correct, not that the private input specifically matches an off-chain record. To mitigate this, participants can submit salted hashes of their preferences (with per-participant passphrases) that the guest program includes (hashed) in public output. Each participant can then verify their own preference hash matches what was used in the execution without revealing preferences to others.

5

Conclusion

This walkthrough demonstrates how the Nexus zkVM can provide verifiable transparency for algorithmic decision-making while preserving privacy. Achievements:

• A publicly auditable guest program implementing stable matching.

• Proof generation that keeps preference rankings private.

• A verification mechanism for any party to confirm correct execution.

• A framework balancing individual privacy with institutional accountability.

The approach transforms the medical residency matching process from a “trust us” system to a “verify for yourself” system and can be applied to other algorithmic decision systems (financial algorithms, ML-based hiring/lending/healthcare) where transparency and privacy must coexist.