Skip to content

Solving the Millionaires Problem

In this tutorial, you will learn how to solve the millionaires problem using an MPC function deployed on Carbyne Stack.

Prerequisites

You need a deployed Carbyne Stack Virtual Cloud and the Carbyne Stack CLI. Please see the Platform Setup Guide and the Deployment Guide for instructions on how to get hold of these.

In addition, this guide assumes that you have the following tools installed:

  • Java 8 (newer versions will not work)

The Billionaires Problem

We use a variation of Andrew Yao's Millionaires' Problem that is the secure multi-party computation problem of deciding which of two millionaires, Alice and Bob, is richer without revealing their actual wealth. Since the conception of the problem, the world has moved on and we better speak today not of two millionaires but of two (completely fictional) billionaires called Jeff and Elon.

In the following, we describe how to solve this problem using Carbyne Stack. To see how things work, let's put ourselves in Elon's shoes.

Providing the Inputs

First, we upload the inputs into the Carbyne Stack Amphora Secret Store. The inputs are the billionaires' net worth in billions. Note that this obviously has to be done in a private way by Jeff and Elon in a real-world setting.

# Create a secret representing Jeff's net worth (note that we work with 
# billion USD here)
export JEFFS_NET_WORTH_ID=$(java -jar cs.jar amphora create-secret 177 -t billionaire=Jeff)

# And another one for Elon
export ELONS_NET_WORTH_ID=$(java -jar cs.jar amphora create-secret 151 -t billionaire=Elon)

We can check the secrets have been created using:

java -jar cs.jar amphora get-secrets

The output should resemble the following:

Note

The output you see will differ wrt. identifiers and the creation-date tag.

ab160f93-3b7e-468f-b687-f9c46fb535f3
    billionaire -> Jeff
    creation-date -> 1630660117946
ef3e867f-9233-46fb-9cde-7a09c99bc32f
    billionaire -> Elon
    creation-date -> 1630660125951

Invoke the Billionaires Function

Elon is eager to see whether he ranks first in the list of the richest people in the world. To check that using the Carbyne Stack platform, a well-known global media company which regularly publishes a list of the richest people in the world came up with the following MP-SPDZ program that does the job:

cat << 'EOF' > billionaires.mpc
# Prologue to read in the inputs
port=regint(10000)
listen(port)
socket_id = regint()
acceptclientconnection(socket_id, port)
v = sint.read_from_socket(socket_id, 2)

# The logic
first_billionaires_net_worth = v[0]
second_billionaires_net_worth= v[1]
result = first_billionaires_net_worth < second_billionaires_net_worth

# Epilogue to return the outputs 
resp = Array(1, sint)
resp[0] = result
sint.write_to_socket(socket_id, resp)
EOF

The program expects two inputs and does a simple comparison between them. The result written as a secret to Amphora at the end of the program is either 1 in case the first input is less than the second or 0 otherwise.

Elon invokes the program using the Ephemeral Serverless Compute Service as follows:

export RESULT_ID=$(cat billionaires.mpc | java -jar cs.jar ephemeral execute \
  -i $JEFFS_NET_WORTH_ID \
  -i $ELONS_NET_WORTH_ID \
  ephemeral-generic.default \
  | tail -n +2 \
  | sed 's/[][]//g')

The CLI spits out a list of identifiers of Amphora Secrets generated by the program. The snippet above extracts the single identifier emitted in this example and stores it in the RESULT_ID shell variable.

Using this identifier Elon can inspect the result of the execution using:

java -jar cs.jar amphora get-secret $RESULT_ID

The output being 0 tells Elon that unfortunately Jeff is still the alpha:

[0]
    creation-date -> 1630661192626
    gameID -> 7899b23c-4509-4ff8-a9ae-d9b59fa77fea

After buying a bunch of the fabulous new (and completely fictional) Carbyne Stack Altcoins and posting a tweet that one of his companies will accept that coin for payments in the future, Elon wants to see whether he is finally in the pole position. He deletes his old and submits his new net worth and triggers the evaluation of the Billionaires Problem logic again using:

java -jar cs.jar amphora delete-secrets $ELONS_NET_WORTH_ID
export ELONS_NET_WORTH_ID=$(java -jar cs.jar amphora create-secret 179 -t billionaire=Elon)
export RESULT_ID=$(cat billionaires.mpc | java -jar cs.jar ephemeral execute \
  -i $JEFFS_NET_WORTH_ID \
  -i $ELONS_NET_WORTH_ID \
  ephemeral-generic.default \
  | tail -n +2 \
  | sed 's/[][]//g')
java -jar cs.jar amphora get-secret $RESULT_ID

This time the execution results in a '1', which creates a pleasantly warm feeling in Elon's chest.

Next Steps

This simple tutorial showcased only a small subset of the Carbyne Stack's capabilities. Feel free to explore the possibilities yourself by playing around with the CLI.

Back to top