Secret-Shared Santa 🎅

Welcome to our Hackathon blog post series! This time around it is my turn to write about my project. My name is Franco (also known as 0xThemis) and I am a cryptographic engineer working mostly on - well, almost everything we do in TACEO to be honest. But mostly on the current alphanet and the compiler stuff for coCircom and coNoir. With the introduction out of the way, let's hop into the (in my very biased opinion 😉) best hackathon project of the first annual TACEO hackathon!

Secret Santa and some Austrian Folklore

In case some of you don't know Secret Santa, it is a game played in the US and Europe during Christmas holidays.¹ Each participant secretly draws another person to whom they should give a gift. The identities of the gift-givers (the Secret Santas) remain secret until a pre-defined date, where everyone gets their present from their Secret Santa. There are multiple variations of the game but, at least for the variations that I know of, they all boil down to this core rule although we are focusing on the original game of Secret Santa.

At least in Austria, the game is very prominent among friends, smaller companies, or teams within a company. Additionally, it is also done in families without little children, because in that case, the "Christkind" is doing the gifting, which is the traditional Austrian equivalent of Santa Claus or Father Christmas. Anyways, I promise to stop now with Austrian folklore as long as it is still sweet and innocent and before we start talking about Krampus, a devil that kidnaps bad behaving children and similar "stories for children."

The Secret Santa Experience

In most Secret Santa games that I have been a part of, the drawing of the Santas is somewhat of a problem. If everyone is in the same room, you can do it pretty easily. You just write your name on a sheet, throw it in a hat and let each person draw a name from the hat. If someone draws themself, they redo it. The cryptographer in me wants to start a rant about trust assumptions and how insecure it is to simply trust uncle Bob that he, in fact, didn't draw himself so that he can gift himself a weekend in the spa, but apparently we have to "trust" our friends and family 🙄.

The problem gets harder when not all participants are in close proximity, e.g., in a company that is distributed over multiple countries. In that scenario, you either have to rely on a trusted third party, which in most cases is some website (there are a couple) or someone from the participants has to do the draw.

A website of course needs Email addresses or telephone numbers of the participants to send them who they should give a gift. As the privacy aware people that we are, we usually don't like giving contact information to random web services. Also, we have to trust it again that it performs the shuffling correctly (I mean, it doesn't have stakes in cheating here, but for the sake of the argument, we are cryptographers after all). The other approach is that someone of the participants performs the draw, validates it, and sends out the resulting assignments. Here we have again the problem, that this single person can assign the table just as they like. Additionally, for most people without trust issues the bigger problem is that this person knows every Secret Santa, which is like 90% of the fun of the game.

If you follow up on TACEO blog posts, your alarms should ring already. A trusted third party that operates on sensitive data from the different entities that needs to prove a correct computation? Sounds a lot like Private Shared State to me! ²

Secret-Shared Santa

The next logical evolutionary step (at least for me) of Secret Santa is to MPC-ify it. I was heavily inspired by our Max-Pick Challenge we did during summer and tried to incorporate our learnings from summer. This time around though, we already have our alphanet which we can use for computing coSNARKs!

Also I want to issue a trigger warning for the upcoming sections. I will post screenshots of the Web UI that I puked out with the help of ChatGPT and I am really, really bad (no seriously) at Web Development and making stuff beautiful. So, this is your warning. [Editor's note: I think it's gorgeous.]

In the beginning, a "game master" (this could be a team leader of a company, or just some random person you chose from your friends) creates a new Secret-Shared Santa game by clicking the "create new game" button as shown in the following graphic:

The game master retrieves an invitation code that they then send to all participants of the game. In the picture above, you can see where the Secret Santas may provide their invitation code. After logging in to their MetaMask, the browser generates a random key seed-phrase consisting of 10 characters:

The player needs to write down their seed-phrase (code) and remember it for later, as they need it to decrypt who they drew. More on that later. By clicking the button, the player indicates that they noted their seed-phrase and finalize their registration for the Secret-Shared Santa game.

As soon as all participants retrieved their seed-phrase, we start assigning the Secret Santas. To inspect the state of the game, the players can inspect the following page:

In this specific example, we have four participants. Every participant is identified by their wallet address (initially I planed to put everything on the blockchain, but one week was too little time unfortunately). In the last column of the table, every Santa can determine who they should surprise with a present by following the indicated link. They land on the following page, were they now input their previously noted seed-phrase:

If the Santa forgot or lost the seed-phrase it is game over. Nobody, can retrieve this information for them.³ Luckily, the Santa in our example remembered their seed-phrase and was able to figure out who they should surprise:

What is going on under the hood?

We can finally leave the UI behind and talk about the cool stuff.⁴ First of, we have three actors in Secret-Shared Santa (four if you count the person that create a new Secret-Shared Santa instance):

1. The High-Elf: This is a management server that acts as intermediary for the Santas and the alphanet. It also hosts the frontend and stores the encrypted state of the Secret-Shared Santa game.
2. The Elves: The TACEO MPC alphanet. We list the alphanet as one single actor, even though, of course, it again consists of multiple parties,⁵ but from the point-of-view of the Secret-Shared Santa game, the alphanet is just a single entity.
3. The Secret Santa: A single player that wants to participate in a Secret-Shared Santa game.

The juicy part happens when a Secret Santa wants to participate in the game. The initial creation of the game is rather unspectacular, as it only allocates a database entry and retrieves the public keys of the elves (the MPC-nodes) that will create the different proofs. When the game prompts the Secret Santa to note their key seed-phrase, the browser actually does a little bit of work. First, the browser runs the seed-phrase, along with the wallet address of the Santa retrieved from their MetaMask, through SHA-256 to retrieve a 32-byte seed. We feed this seed then to a ChaCha12-RNG instance and retrieve a random field element $x_i$ on the scalar field of the BN-254 curve, where $i$ indicates the index of the Santa. This $x_i$ serves multiple purposes. First of all, we use it as one-time pad the encrypt the draw for each Santa. The other reason has something to do with how we randomly assign the Santas, but we'll come to that in a minute.

Obviously, this random element $x_i$ is highly sensitive. Therefore, as soon as the Santa is indicating to continue by clicking continue, the browser secret-shares $x_i$ and engages the alphanet for the first time. To enable publicly-auditable MPC, we have to somehow bind the inputs of our private-shared state circuit to the participants. Otherwise the participants would retrieve a proof of the correct circuit, but they would never know if in fact their randomness ($x_i$) was considered during the assignment. Therefore, we let the alphanet create a Pedersen Commitment to $x_i$ and the address of the Secret Santa. The management server stores the proof of the commitment and the secret-shared input (encrypted with the public keys of the MPC-nodes, of course). The circom circuit is rather compact, I'd say:

pragma circom 2.0.0;

include "pedersen.circom";

template SecretSantaCommitment() {
    signal input randomness;
    signal input address;
    signal output commitment[2];
    component pedersen = Pedersen(2);
    pedersen.in[0] <== randomness;
    pedersen.in[1] <== address;
    commitment <== pedersen.out;

}
component main {public [address]} = SecretSantaCommitment();

Listing 1: The SecretSantaCommitment, that uses the Pedersen Commitment circuit from circomlib.

To summarize, the browser generates a human-readable seed-phrase, derives a random element $x_i$ from the seed-phrase and the address of the Secret-Santa. Then it retrieves the public keys of three MPC-nodes from the alphanet, secret-shares $x_i$ and encrypts the shares with the respective public keys. The alphanet computes a Pedersen Commitment of $x_i$ and the address inside a coSNARK and the management server stores the resulting proof, and the encrypted shares of $x_i$ for later use.

Assigning all the Secret-Shared Santas

The high-elf management server keeps track of how many commitments it retrieved for each game. When hitting the threshold of inputs, it invokes the alphanet again. The circuit is still rather small all things considered, consisting of 1,135 constraints. It has $3N$ public inputs, $N$ private inputs, and $N$ outputs (which are in fact public inputs), where $N$ is the amount of Santas that participate in the game. The private input is the random $x_i$ for each Santa and the public inputs are their respective wallet addresses and the Pedersen Commitment (which consists of an $x$ and $y$ coordinate on the BN-254 curve). The output is the encrypted draw.

The first step of the circuit is to recompute the commitments and verifies if they in fact match with the commitments from the Santas, as seen in the following Listing:

    signal input randomness[N];
    signal input addresses[N];
    signal input commitments[N][2];
    signal output draws[N];
    // check that the commitments match
    component pedersen[N];
    for (var i=0;i<N;i++) {
        pedersen[i] = Pedersen(2);
        pedersen[i].in[0] <== randomness[i];
        pedersen[i].in[1] <== addresses[i];
        pedersen[i].out === commitments[i];
    }

Listing 2: Verifies that the inputs in fact are the inputs from the Santas.

Now that we know that the circuit respects the correct randomness of the Santas, we can start the drawing process. The next step is to randomly shuffle the Santas. In a real-world setting this would be the part were everyone throws in their names in a bag and someone gives it a good jiggle. Or on a traditional CPU we kindly ask the OS to produce some random numbers to perform the random shuffling. Unfortunately, inside an MPC/ZK circuit, we can't ask the OS to produce random numbers for us, therefore we need to do something else to shuffle the Santas.

As we already have randomness provided from every Santa, we can simply compute a Poseidon hash of all random elements which results in a seed we can use to shuffle the Santas, as seen in the following code snippet:

    // sample the joint randommnes
    signal seed <== Poseidon(N)(randomness);

    var setup[N];
    for (var i = 0;i<N;i++) {
        setup[i] = i;
    }

    signal shuffeled[N] <== RandomPermutate(N)(seed, setup);

Listing 3: Join the randomness of all Santas with Poseidon. We use the RandomPermute circuit to shuffle the Santas.

The result of the RandomPermute circuit is a random permutation of the values $[1..N]$ called shuffeled. We denote it as $S$. As the resulting Poseidon hash is also secret-shared (we hashed $N$ secret-shared values) the permutation is not only random, but also oblivious, preventing even the MPC-nodes to learn the assignment! The last step of the circuit is to assign every Santa to another Santa. We do this by assigning the Santa with index $S_i$ to $S_{(i+1)\bmod N}$, as seen in the following Listing:

    signal shuffeled_padded[N+1];
    for (var i=0;i<N;i++) {
        shuffeled_padded[i] <== shuffeled[i];
    }
    shuffeled_padded[N] <== shuffeled[0];
    signal draws_acc[N+1][N];
    for (var i=0;i<N;i++) {
        draws_acc[0][i] <== 0;
    }
    for (var i=1;i<N+1;i++) {
        draws_acc[i] <== ArrayWrite(N)(draws_acc[i-1], shuffeled[i-1], shuffeled_padded[i]);
    }
    for (var i = 0;i<N;i++) {
        draws[i] <== draws_acc[N][i] + randomness[i];
    }

The final for loop completes the process by encrypting the drawn indices using a one-time pad, where the encryption key is the randomness associated with each Santa. Since the randomness is secret-shared, no one learns the encrypted values!

Once the proof is validated and each Santa verifies that their randomness was correctly applied, they can decrypt their respective portions of the output using their individual randomness!

Potential Improvements

Since this was a hackathon project with a one-week timeline, I had to prioritize certain aspects while leaving others out. As a result, the project isn't as robust as I'd like. The biggest challenge I face when working on the alphanet is handling the possibility of entities dropping out unexpectedly—something I didn't account for at all during development of Secret-Shared Santa.

Additionally, the game size is hardcoded to a maximum of four Santas, though this should ideally be configurable. Lastly, I had planned to put everything on-chain, but given the one-week timeframe... well, let’s just say time wasn't on my side 😅.

Insights

The most fun I had was building the high-elf management server. We use rust by the way in case you didn't know and for servers we mostly used a mix of axum and tonic. For this hackathon project I had a look at loco-rs, which advertises itself as "Ruby on Rails, but for Rust" 🚂. Even though, loco-rs is still in its infancy, I had a lot of fun building the management server with it. Most things I needed worked out-of-the-box, with only one problem, related to CORS, but apparently this is a known issue. All things considered, although I needed to get familiar with the framework, I think loco-rs helped me quite a lot and sped up my development time. We will for sure consider coming back to it again for future projects!

Conclusion

I had a lot of fun during our Hackathon and even managed to investigate a potential tool for the future in loco-rs! We'll investigate whether we want to launch Secret-Shared Santa for real for Christmas next year so stay tuned for further information about this :)

---

---

Thank you for following our hackathon series! If you'd like to read more about coSNARKs and the rest of the TACEO stack, feel free to check out the docs, chat with us in Discord, and follow for news on X!