Narcissistic Randomness

Suppose you are in a group of people, and you all want to choose something at random. However, no one in the group trusts anyone else--each member only trusts themselves. How can you generate a random number everyone trusts?

Conceptual Explanation

In the physical world, there are many solutions to this problem. The group could roll dice, flip coins, or draw slips of paper from a hat. These solutions all reuire that everyone in the group trust that some process (e.g. flipping a coin) is random regardless of who executes it. It turns out that with some clever cryptography, we can avoid making that assumption in the digital world! Let's see how.

A Non-Example

First, let's consider an example of what doesn't work. Let's suppose that Alice and Bob are roommates. One of them has to make dinner, but neither of them want to. To be fair, they decide to choose who makes dinner at random:

Alice: Let's flip a coin. I flip; you guess. Loser makes dinner. Agreed?
Bob: Sounds good. Go ahead and flip.
Alice: Okay. I'm flipping, ... and it's heads.
Bob: Yes! I called heads! Looks like you're making dinner tonight.
Alice: Wait a minute; that doesn't work. How do I know you actually called heads?

So that doesn't work. Let's try again, only this time the caller has to call the toss before they know the outcome.

Alice: Okay, let's try again. This time, you have to call the toss before I tell you the outcome.
Bob: Okay fine. I call tails.
Alice: Okay. I'm flipping, ... and it's heads. Looks like you're making dinner!
Bob: Hold up. You're just saying it came up heads so that I lose!

Whoever goes last has the power to control the group's choice, which is not acceptable in a group of paranoid people. We just considered a simple example here, but think about how the same problem would exist for other schemes.

Solution: Commitment Schemes

Here's one solution to this problem of who goes first: have all group members commit to their secret before revealing it. In the coin flip example above, the secrets are Bob's call and the outcome of Alice's flip. Here's how this might work:

Alice: Okay, I have a solution. Here's the SHA-256 hash of my call: 853ad5687e2c182baeee91d09ec990754b45516f242ffc39d34a51808b93942d.
Bob: Hmm okay, this seems interesting. Let's try it! I'm flipping, ... and it's heads.
Alice: I called heads! You can verify like this in your terminal: echo "I call heads. Why didn't we just get a meal plan?" | shasum -a 256
Bob: Fine, I'll make dinner. But you'd better not complain about my cooking!

Here' Alice committed to her choice by reporting the SHA-256 hash of her call. After Bob reports the outcome of the toss, he can verify that Alice really did call heads before the toss by hashing her statement. Importantly though, since SHA-256 hasn't been broken yet, Bob cannot determine Alice's guess from her hash. The hash is a commitment, but it doesn't reveal the secret.

You might be wondering what the bit about meal plans is all about. That's just a bit of randomness to stop Bob from hashing I call heads. and comparing with the hash Alice provided.

Keybase's Strategy

Keybase uses commitment schemes to let groups of people securely make random choices without trusting anyone else in the group. In fact, this guide and the explanation above were based on a Keybase blog post from 2019. Their algorithm works like this:

Each participant generates a random 32-byte secret.
Everyone commits to their secret by publishing the SHA-256 hash of their secret.
Everyone reveals their secrets to the group and checks that everyone else's secrets match their commitments.
Every participant XORs all the secrets together to generate a shared random seed.
Now, everyone can form the same pseudorandom bit sequence seeded with this shared random seed.

We will follow a similar approach, except instead of using the random seed to create a pseudorandom sequence, we'll just use the seed itself. This means that we only have 32 bytes of random bits to work with, but that's plenty for most choices.

Narcissistic Randomness in Practice

Here is a simple web app that implements what I'm calling Narcissistic Randomness. All the computations occur in your browser with JavaScript. I encourage you to look at the source of this page to see how the calculations work.

Generate Secret

The first step is to generate a 32-byte secret. You can click the Generate button to make one or provide your own. Secrets must be base64 encoded.

Generate Commitment Hash

Next, we need to generate a hash of the secret. This will serve as our commitment to the secret we generated above. Click Generate Commitment and send the commitment to the rest of the group.

Collect Commitments and Secrets

Now, it's time to collect everyone's commitments and secrets. First, copy and paste everyone else's commitments below, one commitment per line. Once everyone has done that, you can all share your secrets. Collect these too and paste them below, one secret per line. Make sure the commitments and secrets are in the same order! You can verify that everyone's secret matches their commitment by clicking Verify Commitments below. The result is a list of booleans showing the validity of each commitment-secret pair, in the same order you listed them in the text boxes.

Generate Random Seed from Secrets

Now that we have everyone's secrets and have confirmed their commitments, we can create the random seed. This is a simple bitwise XOR-ing of all the secrets. Click Generate Seed.

Generate a Random Integer

Now that we have a shared random seed, we can choose a random number. Pick a minimum and maximum value below, and generate your number!

To pick a random number, we first determine how many random bits we need to to make a random choice between the specified minimum and maximum values. Then, we take just enough digits from the hex-encoded seed to get that many bits. We drop excess bits and evaluate the remaining bits as a number. If the number is at most min - max, we add it to min to get our final answer. Otherwise, we move on to the next set of digits in the seed.

Acknowledgments

This guide was heavily inspired by Keybase as mentioned above. It makes use of the Stanford Javascript Crypto Library (SJCL) , which is Copyright © 2009-2015, Emily Stark, Mike Hamburg and Dan Boneh at Stanford University, and Bootstrap, which is Copyright © 2011-2021 Twitter, Inc. and Copyright © 2011-2021 The Bootstrap Authors.

This guide is Copyright © 2021 Christopher Skalnik. It was originally developed for a workshop at Stanford Code the Change . It is licensed under a Creative Commons Attribution 4.0 International License .