Solving the Millionaires Problem¶
In this tutorial, you will learn how to solve the millionaires problem using an MPC function deployed on Carbyne Stack.
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:
The output you see will differ wrt. identifiers and the
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 second_billionaires_net_worth= v result = first_billionaires_net_worth < second_billionaires_net_worth # Epilogue to return the outputs resp = Array(1, sint) resp = 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
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:
 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.
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.