ImPACT-MPC-Intro.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# ImPACT MPC - Secure Multiparty Computation\n",
    "\n",
    "This Jupyter Notebook provides an example of how to use ImPACT's Secure Multiparty Computation (MPC) components. MPC allows groups of people to collaboratively evaluate algebraic functions, but without ever sharing their private data.\n",
    "\n",
    "## What Secure Multiparty Computation (MPC) is\n",
    "\n",
    "Imagine Alice, Bob, and Charlie are three researchers in Wake, Durham, and Orange Counties (respectively). These three people have determined how many bicycle accidents there are in each of their respective counties, and they would like to know what the sum total of bike wrecks is across the three-county Triangle area. The only problem is, each of the researchers considers their number to be private. Alice has no desire whatsoever to reveal the number of accidents she found in Wake county, while Charlie is similarly circumspect about Orange.\n",
    "\n",
    "There are two potential solutions to this Social Science Standoff: agreeing on a Trusted Third Party (TTP), or using some Really Cool Math. The TTP has, historically, been the way this is done. All three researchers agree to trust someone and they share their individual numbers with that honest broker. The TTP, in turns, adds the numbers up and tells everyone what the sum is. This works as long as everyone can agree on a Trusted Third Party to work with and as long as that third party remains faithful to the duties of the position (i.e., \"actually keeps a secret\") and doesn't become compromised, hacked, or subpoenaed. Really Cool Math, on the other hand, is the basis for Multiparty Computation (MPC) and lets the three researchers create a Virtual Trusted Third Party (VTTP) that is immune to some of the weaknesses of the traditional TTP approach.\n",
    "\n",
    "## How to use MPC\n",
    "\n",
    "Fundamentally, MPC is a process for a group of people (A, B, C...) to evaluate a function _func_ (A, B, C...). Everyone will be able to tell what the function evaluates to, but each party will only know what their own input was. Person A will only know the value A, person B will only know the value of B, and so forth.\n",
    "\n",
    "ImPACT (currently) uses the SPDZ/2 software from the Bristol Cryptography Research Group as the MPC \"engine\" for doing the computation. SPDZ/2 is not easy to install and it's not all that obvious how to use it. ImPACT helps on both fronts - the prepackaged Amazon Machine Instance makes it simple to have a running instance of the software and the documentation (including this notebook) gives plenty of examples.\n",
    "\n",
    "### Step 1: Write your function\n",
    "\n",
    "The very first step in MPC is deciding what function you want to evaluate. In this example, we'll take the numbers from our three intrepid researchers and we'll just add them together. The function is written in a subset of Python, and it's a pretty small subset at that. You can't have any loops, the only data types available are numbers and booleans (numbers can be integers or floating point numbers, so that helps), and you have to know exactly how many inputs you'll have. Here's the code to sum our three numbers:\n",
    "\n",
    "```\n",
    "a = sint.get_input_from(0)\n",
    "b = sint.get_input_from(1)\n",
    "c = sint.get_input_from(2)\n",
    "\n",
    "d = a+b+c\n",
    "print_ln('##################### Result is %s', d.reveal())```\n",
    "\n",
    "This function (\"tripleadd.mpc\") takes three numbers (one each from parties 0, 1, and 2), adds them up, and prints the final result. There's nothing unexpected here, but know that we could have thrown some curveballs. For instance, we could say that Alice and Chuck (parties 0 and 2) will have their number taken at face value while Bob has his number doubled before it's added. It's perfectly OK to treat input differently (for instance, one researcher could know the number of drownings while another researcher knows the number of boats, and we could compute the drownings per boat without ever revealing either of the raw inputs).\n",
    "\n",
    "Use Jupyter to take a look at tripleadd.mpc :  https://ec2-18-218-33-24.us-east-2.compute.amazonaws.com:4991/edit/Programs/Source/tripleadd.mpc\n",
    "\n",
    "### Step 2: Compile your function\n",
    "\n",
    "With your function written, you now have to compile it so it can be run. If you're used to Old School programming then you probably know that compilation is the process of converting programs from their \"human readable\" form into something that the computer knows how to run but that looks, to the eye, like an absolutely random spattering of pure chaos. If all you've ever used is Python then know that Python hides this step from you, but it's there anyway.\n",
    "\n",
    "To compile the function:\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Compiling program in /home/ec2-user/SPDZ-2/Programs\n",
      "Default bit length: 32\n",
      "Default security parameter: 40\n",
      "Galois length: 40\n",
      "Compiling file /home/ec2-user/SPDZ-2/Programs/Source/addition.mpc\n",
      "Compiling basic block addition-0--0\n",
      "Processing tape addition-0 with 1 blocks\n",
      "Processing basic block addition-0--0, 0/1, 18 instructions\n",
      "Program requires 1 rounds of communication\n",
      "Program requires 1 invocations\n",
      "Tape register usage: defaultdict(<function <lambda> at 0x7f81bb4a6758>, {'ci': 0, 'sg': 0, 'c': 1, 'cg': 0, 's': 3})\n",
      "modp: 1 clear, 3 secret\n",
      "GF2N: 0 clear, 0 secret\n",
      "Re-allocating...\n",
      "Compile offline data requirements...\n",
      "Tape requires 1 inputs in modp from player 1, 1 inputs in modp from player 0\n",
      "Tape requires prime bit length 0\n",
      "Tape requires galois bit length 0\n",
      "Program requires: {('modp', 'input', 1): 1, ('modp', 'input', 0): 1}\n",
      "Cost: 0\n",
      "Memory size: defaultdict(<function <lambda> at 0x7f81bb4a6668>, {'ci': 8192, 'sg': 8192, 'c': 8192, 'cg': 8192, 's': 8192})\n",
      "Compiling basic block addition-0-memory-usage-1\n",
      "Writing to /home/ec2-user/SPDZ-2/Programs/Schedules/addition.sch\n",
      "Writing to /home/ec2-user/SPDZ-2/Programs/Bytecode/addition-0.bc\n"
     ]
    }
   ],
   "source": [
    "%%bash\n",
    "# change to the SPDZ directory\n",
    "cd /home/ec2-user/SPDZ-2\n",
    "# compile the function. DO NOT INCLUDE THE \".mpc\" FILE EXTENSION\n",
    "#./compile.py tripleadd\n",
    "./compile.py addition\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "...and that compiled tripleadd and saved the results as tripleadd.sch and tripleadd.bc (see the last two lines). The compiled code is _almost_ ready to be run now...\n",
    "\n",
    "### Step 3: Your (collaborators') cooperation is requested\n",
    "\n",
    "There are a few coordinating steps that need to be done now.\n",
    "\n",
    "#### Step 3.1 - Share the function\n",
    "Share the function among all of the researchers and have each one of them compile it.\n",
    "\n",
    "#### Step 3.2 - Get IPs\n",
    "Get the IP address of everyone's server - this can either be names (\"BobLabMachine.med.unc.edu\") or numeric IP addresses (\"152.2.31.249\").\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Step 3.3 - Assign party numbers\n",
    "1. Decide among yourselves who is Party 0, 1, and 2. Remember how SPDZ/2 is capable of handling inputs differently depending on which party they came from? That's why we have to decide who is who, even if everyone is treated exactly the same. And importantly, SPDZ/2 will only print the final output value to Party 0. That's implementation dependent, by the way, and we have a way to share the results securely.\n",
    "1. Put the IP addresses of the parties in /home/ec2-user/parties , and put them in the file in order from Party 0 down through the last party.\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Step 3.4 - Create Encryption \"Keys\"\n",
    "SPDZ/2, and in fact any MPC technique, relies on combining the secret data with carefully constructed \"other information\" in a way that the final output function can still be evaluated but that individual parties can't read each other's inputs. This \"other information\" is an encryption key of a special kind, and different parts of that key are distributed to different parties. The mechanics of how all this happens is Really Cool, but suffice it to say that it takes a huge amount of computation to produce these keys and that it's done ahead of time.\n",
    "\n",
    "Pedantically speaking, MPC doesn't use encryption, it uses \"secret sharing\". The distinction is subtle, and for our purposes moot. I mention it only because parts of the system will refer to \"triples\" instead of \"keys\", and because we're in the academic world and pedantry is what we do...\n",
    "\n",
    "In normal ImPACT MPC use, each researcher would go to a python notebook that calls out to the SPDZ key generator to initiate the key generation process. It takes about 30 minutes. For demonstration and learning purposes, there is already a pre-generated set of keys installed. You should _never_ use these for real data, but it's fine to use them while you're just playing around and learning about the system.\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Step 4: Perform the computation\n",
    "Finally, the good part. We've selected who will be Party 0, Party 1, and so forth. We've got their computer's IP addresses sorted, and we've created encryption keys. We're now ready to add up some numbers!\n",
    "\n",
    "First, let's put our number into this notebook. Each party is responsible for deciding what their individual number is (as always - if it's a collaboration, everyone has to do some of the work, right?) and keeping up with it. Maybe you do a database query and decide there are 1729 bike crashes in your county. Maybe a whole ton statistics completes and you decide that 1729 was the optimum year, in the pre-colonial period at least, to grow pumpkins in Maryland. The sky is the limit here, along with your funding agency and what you can get past your department head, but the point is to come up with the number you'll use as input into the function (tripleadd, remember?).\n",
    "\n",
    "Run one of the following two cells - either this first one which isn't much to look at, or the second one showing how to use some other Really Cool Work (tm) at Renci."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Through some incredibly complicated machinations, compute the secret result that makes up your\n",
    "# contribution to the collaboration. \n",
    "\n",
    "mySecretNumber = 1729"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Or, as alluded to above, use the following cells to run an example of using ICEES, an interface to the NIH-sponsored Data Translator work at Renci for exploratory data analysis."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 58,
   "metadata": {},
   "outputs": [],
   "source": [
    "import urllib.parse\n",
    "import urllib.request\n",
    "import ssl\n",
    "import json\n",
    "\n",
    "url = 'https://icees.renci.org/1.0.0/patient/2010/cohort'\n",
    "requestData = '{\"AvgDailyPM2.5Exposure\":{\"operator\":\">\", \"value\":1}}'\n",
    "requestBytes = bytes(requestData, \"utf-8\")\n",
    "req = urllib.request.Request(url, requestBytes)\n",
    "\n",
    "myssl = ssl.create_default_context();\n",
    "myssl.check_hostname=False\n",
    "myssl.verify_mode=ssl.CERT_NONE\n",
    "\n",
    "with urllib.request.urlopen(req, context=myssl) as response:\n",
    "    httpResult = response.read()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 59,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "First, here's the 'raw' data that came back from the ICEES server. It's a JSON formatted string.\n",
      "\n",
      "b'{\"version\": \"1.0.0\", \"return value\": {\"cohort_id\": \"COHORT:56\", \"size\": 23093}, \"terms and conditions\": \"The Translator Integrated Clinical and Environmental Exposures Service (ICEES) is providing you with Data that have been de-identified in accordance with 45 C.F.R. \\\\u00a7\\\\u00a7 164.514(a) and (b) and that UNC Health Care System (UNCHCS) is permitted to provide under 45 C.F.R. \\\\u00a7 164.502(d)(2). Recipient agrees to notify UNCHCS via NC TraCS in the event that Recipient receives any identifiable data in error and to take such measures to return the identifiable data and/or destroy it at the direction of UNCHCS.\\\\n\\\\nRestrictions on Recipient\\\\u2019s Use of Data. Recipient further agrees to use the data exclusively for the purposes and functionalities provided by the ICEES: cohort discovery; feature-rich cohort discovery; hypothesis-driven queries; and exploratory queries. Recipient agrees to use appropriate safeguards to protect the Data from misuse and unauthorized access or disclosure. Recipient will report to UNCHCS any unauthorized access, use, or disclosure of the Data not provided for by the Service of which Recipient becomes aware. Recipient will not attempt to identify the individuals whose information is contained in any Data transferred pursuant to this Service Agreement or attempt to contact those individuals. Recipient agrees not to sell the Data to any third party for any purpose. Recipient agrees not to disclose or publish the Data in any manner that would identify the Data as originating from UNCHCS. Finally, Recipient agrees to reasonably limit the number of queries to the Service per IP address within a given time interval, in order to prevent rapid \\\\u2018attacks\\\\u2019 on the Service.\\\\n\\\\nWe kindly request that users of this service provide proper attribution for any products (e.g., manuscripts, podium presentations, software) derived from work related to ICEES. Attribution should include acknowledgement of the funder (National Institutes of Health, National Center for Advancing Translational Sciences, Biomedical Data Translator Program [awards OT3TR002020 and OT2TR002514] and Center for Translational Science Program [award UL1TR002489]), UNC Hospitals and Health Care System, and all team members who contributed to the work.\\\\n\"}'\n",
      "\n"
     ]
    }
   ],
   "source": [
    "print(\"First, here's the 'raw' data that came back from the ICEES server. It's a JSON formatted string.\")\n",
    "\n",
    "print(\"\")\n",
    "print (httpResult)\n",
    "print (\"\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 60,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "In cohort COHORT:56 there were 23093 individuals.\n"
     ]
    }
   ],
   "source": [
    "iceesResults = json.loads(httpResult)[\"return value\"]\n",
    "cohortId = iceesResults[\"cohort_id\"]\n",
    "cohortCount = iceesResults[\"size\"]\n",
    "\n",
    "print (\"In cohort \" + cohortId + \" there were \" + str(cohortCount) + \" individuals.\")\n",
    "mySecretNumber = cohortCount"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Then specify your party number and the name of the function to evaluate:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "myPartyNumber = 0\n",
    "#mpcFunction = \"tripleadd\"\n",
    "mpcFunction = \"addition\""
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now, we'll use a \"Jupyter magic\" (that's its real name!) to run a shell command from inside this notebook. The idea is that we'll use mySecretNumber as the \"standard input\" (what we normally would type at the keyboard) to the shell command and we'll capture the \"standard output\" and \"standard error\" (stuff usually printed by the command) into variables where we can look at them."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "%%bash -s $mySecretNumber $myPartyNumber $mpcFunction --out mpcOut --err mpcErr\n",
    "cd /home/ec2-user/SPDZ-2\n",
    "echo $1 | /home/ec2-user/SPDZ-2/Player-Online.x -ip /home/ec2-user/parties $2 $3"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now we can print the output from the command. In our case, we wrote our function to compute so that it printed the output with some nice formatting. It's a convenience for debugging - if we have a complicate formula then we can print all sorts of intermediate results to see what is going on. Just because the function can't have any loops doesn't mean it can't be fairly complicated. If you wanted to do a Taylor series expansion, for instance, you'd have to \"unroll\" the loop and type in enough terms by hand to come close enough to converging. \"No loops\" winds up meaning \"I know ahead of time exactly how many times I'm going to do this\". This is just like, coincidentally, the SAFE component of ImPACT."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "##################### Result is 3458\n",
      "\n"
     ]
    }
   ],
   "source": [
    "print (mpcOut)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "While my own code never produces errors, your's theoretically could. The standard error messages are available in the \"mpcErr\" variable. There will always be a lot of messages, even for a successful run, and any errors aren't always obvious. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 57,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Got list of 3 players from file: \n",
      "    172.31.34.83\n",
      "    172.31.46.182\n",
      "    172.31.44.75\n",
      "ServerSocket is bound on port 5000\n",
      "loading params from: Player-Data/3-128-40/Params-Data\n",
      "MAC Key p = 9713710702708426579646134761687417105\n",
      "MAC Key 2 = 0x821139c82b\n",
      "Opening file Programs/Schedules/tripleadd.sch\n",
      "Number of threads I will run in parallel = 1\n",
      "Number of program sequences I need to load = 1\n",
      "Loading program 0 from Programs/Bytecode/tripleadd-0.bc\n",
      "tripleadd-0 needs more secret gf2n memory, resizing to 8192\n",
      "tripleadd-0 needs more clear gf2n memory, resizing to 8192\n",
      "tripleadd-0 needs more secret gfp memory, resizing to 8192\n",
      "tripleadd-0 needs more clear gfp memory, resizing to 8192\n",
      "tripleadd-0 needs more clear integer memory, resizing to 8192\n",
      "Cost of first tape:\n",
      "  Type p\n",
      "             0 =          0        Triples à           0\n",
      "             0 =          0        Squares à           0\n",
      "             0 =          0           Bits à           0\n",
      "             0 =          0       Inverses à           0\n",
      "             0 =          0     BitTriples à           0\n",
      "             0 =          0 BitGF2NTriples à           0\n",
      "  Type 2\n",
      "             0 =          0        Triples à           0\n",
      "             0 =          0        Squares à           0\n",
      "             0 =          0           Bits à           0\n",
      "             0 =          0       Inverses à           0\n",
      "             0 =          0     BitTriples à           0\n",
      "             0 =          0 BitGF2NTriples à           0\n",
      "Total cost: 0\n",
      "Waiting for thread 0 to be ready\n",
      "\tI am in thread 0\n",
      "Using single-threaded receiving\n",
      "Setting up send to self socket to 127.0.0.1:5000 with id 0x0\n",
      "Setting up client to 172.31.46.182:5001 with id 0x3\n",
      "Setting up client to 172.31.44.75:5002 with id 0x6\n",
      "As a server, waiting for client with id 0x0 to connect.\n",
      "\tSet up player in thread 0\n",
      "Setting up Data_Files in: Player-Data/3-128-40/\n",
      "done\n",
      "Using indirect communication.\n",
      "Opening file Player-Data/Private-Input-0\n",
      "Opening file Programs/Public-Input/tripleadd\n",
      "Opening file Player-Data/Public-Output-0\n",
      "Opening file Player-Data/Private-Output-0\n",
      "Locking for sync of thread 0\n",
      "Compiler: ./compile.py tripleadd\n",
      "Waiting for all clients to finish\n",
      "\tThread 0 terminating\n",
      "0 : MAC Checking\n",
      "\tMC2.number=0\n",
      "\tMCp.number=1\n",
      "Thread 0 timer: 0.000517884\n",
      "Thread 0 wait timer: 6.9108e-05\n",
      "Sent 1 elements in 1 rounds\n",
      "Join timer: 0 0.00289006\n",
      "Finish timer: 0.000324482\n",
      "Process timer: 0.000596264\n",
      "Time = 0.00326683 seconds \n",
      "Summed all shares at once\n",
      "Full broadcast\n",
      "Data sent = 428 bytes in 35 calls,4 bytes per call\n",
      "Num Triples\t= 0 0\n",
      "Num Squares\t= 0 0\n",
      "Num Bits\t= 0 0\n",
      "Num Inverses\t= 0 0\n",
      "Num BitTriples\t= 0 0\n",
      "Num BitGF2NTriples\t= 0 0\n",
      "Num gfp Inputs\t= 1 1 1\n",
      "Num gf2n Inputs\t= 0 0 0\n",
      "Total cost of program:\n",
      "  Type p\n",
      "             0 =          0        Triples à           0\n",
      "             0 =          0        Squares à           0\n",
      "             0 =          0           Bits à           0\n",
      "             0 =          0       Inverses à           0\n",
      "             0 =          0     BitTriples à           0\n",
      "             0 =          0 BitGF2NTriples à           0\n",
      "  Type 2\n",
      "             0 =          0        Triples à           0\n",
      "             0 =          0        Squares à           0\n",
      "             0 =          0           Bits à           0\n",
      "             0 =          0       Inverses à           0\n",
      "             0 =          0     BitTriples à           0\n",
      "             0 =          0 BitGF2NTriples à           0\n",
      "Total cost: 0\n",
      "End of prog\n",
      "Command line: /home/ec2-user/SPDZ-2/Player-Online.x -ip /home/ec2-user/parties 0 tripleadd\n",
      "\n"
     ]
    }
   ],
   "source": [
    "print (mpcErr)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## In Conclusion\n",
    "We've seen a very simple way to use Secure Multiparty Computation to enable collaboration without sharing data. There is a good deal more to ImPACT's use of MPC and encryption methods than we've covered here. In particular, there is an art to writing efficient functions with all kinds of dirty tricks. Avoiding loops is mandatory, but there is \"syntactic sugar\" for faking them. Speed goes down linearly with the number of parties, but there is a \"client-server\" mode that handles huge numbers of users quite well. The algorithm supports \"cheater detection\" - we've set it up where for a 66% chance of detecting malfeasance but that can be set arbitrarily high (99.999...%). There are even times when you should use a 1-element array instead of just a variable. For much more information, see the SPDZ/2 documentation itself.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}