Zero Knowledge Proofs Tutorial.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "fd2306b1",
   "metadata": {},
   "outputs": [],
   "source": [
    "import random"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "acf53c74",
   "metadata": {},
   "source": [
    "# Introduction\n",
    "\n",
    "Bob, knows a given value `x`, and wants to prove to Alice that he knows `x`, without revealing to Alice what `x` is.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "15457633",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "6"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "#Privately known variables (only known by Bob)\n",
    "x = 6\n",
    "x"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f5e1125a",
   "metadata": {},
   "source": [
    "# Part A - Bob is an Honest Actor\n",
    "\n",
    "For Part A, assume Bob is an honest actor, and actually does know the value of `x`.\n",
    "\n",
    "## 1. Public One-Way Function\n",
    "\n",
    "Our example begins with a publicly known, one-way function.\n",
    "\n",
    "A common example of a one-way function are hashes.\n",
    "\n",
    "Suppose `f(x)` is any hash function, such as SHA-256, applied to the input of `x`. It is easy to take a given value of `x` and produce the hash: `f(x)`.\n",
    "\n",
    "However, it is very difficult to take the hash, `f(x)`, and solve for the pre-hashed input `x`. In practice, the function can only be performed in one-way.\n",
    "\n",
    "For more on hashes: https://en.wikipedia.org/wiki/Cryptographic_hash_function\n",
    "\n",
    "---\n",
    "\n",
    "In our example, we'll use `f(x) = (g ** x) % p` as another one-way function.\n",
    "\n",
    "When given values for `x`, `g`, and `p`, it is simple to calculate `f(x)`.\n",
    "\n",
    "But when given `f(x)`, `g`, and `p`, and asked to solve for `x`, there is no quick answer.\n",
    "\n",
    "The one-way nature of this function is based on the discrete logarithm problem. There is no known efficient method to compute discrete logarithms in general (i.e. to solve for `x` in this equation). Solving for `x` requires resorting to a brute force method, guessing different values of `x` until one works.\n",
    "\n",
    "For more on discrete logarithm problem: https://en.wikipedia.org/wiki/Discrete_logarithm\n",
    "\n",
    "---\n",
    "\n",
    "In Python we can express the syntax `(g ** x) % p` as simply `pow(g, x, p)`.\n",
    "\n",
    "The function `pow()` is built in to Python, no imports required, and is used in practice because it is more efficient for large numbers than separately performing the power and modulus operations.\n",
    "\n",
    "`pow(g, x, p) == (g ** x) % p`\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4cfa6ac5",
   "metadata": {},
   "source": [
    "## 2. Public Inputs Other Than `x`\n",
    "\n",
    "The values `g` and `p` are also publicly known, since all that matters is that `x` is kept secret, so that Bob can prove he knows `x` without `x` itself being revealed.\n",
    "\n",
    "The security in this case does not rely on keeping `g` or `p` secret, it relies on the computational difficulty of the discrete logarithm problem.\n",
    "\n",
    "In other words, even when given `g`, `p`, and the ouput `pow(g, x, p)`, it's computationally difficult (virtually impossible) to solve for `x`.\n",
    "\n",
    "---\n",
    "\n",
    "In a real-world scenario, to ensure appropriate levels of security, the values for `g` and `p` would follow certain criteria:\n",
    "- `p`:  a very large prime number. All else equal, the larger the prime number, the harder it is to brute force a solution\n",
    "- `g`: a chosen primitive root modulo `p`. This property also ensures a large enough problem space, making it secure against brute-force attacks\n",
    "\n",
    "For more on primitive root modulo n: https://en.wikipedia.org/wiki/Primitive_root_modulo_n\n",
    "\n",
    "In this tutorial, to keep things simple, we'll abide by these same contraints but use a much, much smaller value for `p` than would be advisable for a real-world situation."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "9d364fca",
   "metadata": {},
   "outputs": [],
   "source": [
    "#Publicly known variables (known by Bob, Alice, and everyone else)\n",
    "p = 23 # must be prime\n",
    "g = 5 # must be primitive root modulo p\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "49227fba",
   "metadata": {},
   "source": [
    "## 3. Bob Sends Result `fx` to Alice\n",
    "\n",
    "To begin the process of proving that he knows the value of `x` to Alice, without revealing the value of `x` itself, Bob sends the output of the one-way function to Alice.\n",
    "\n",
    "In other words, Alice now knows:\n",
    "- `g`\n",
    "- `p`\n",
    "- `fx`\n",
    "\n",
    "But still does not know `x`, because of the one-way nature of `fx = pow(g, x, p)`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "83a25f39",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "8"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "fx = pow(g, x, p)\n",
    "fx"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a7dc5a2e",
   "metadata": {},
   "source": [
    "## 4. Bob Privately Picks a Random Integer `r`\n",
    "\n",
    "Bob privately/securely generates a random integer bewteen 0 and `p-1`, called `r`. He does *not* share `r` with Alice, or anyone else.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "1b70ff1f",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "22"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def pick_private_random_int(p):\n",
    "    r = random.randint(0, p - 1)\n",
    "    return r\n",
    "\n",
    "r = pick_private_random_int(p)\n",
    "r"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f7999bd1",
   "metadata": {},
   "source": [
    "## 5. Bob Calculates `u` and Sends to Alice\n",
    "\n",
    "Bob applies the public one-way function, replacing `x` with the random number `r`, and sends the result, `u`, to Alice.\n",
    "\n",
    "It's important to note that Bob submits a given value of `u` to Alice *before* Alice generates a challenge in the next step.\n",
    "\n",
    "In Part B, we'll see how this order of steps is critical to validating that Bob is being honest about knowing `x`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "356ef98c",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def calculate_u(g, r, p):\n",
    "    u = pow(g, r, p)\n",
    "    return u\n",
    "\n",
    "u = calculate_u(g, r, p)\n",
    "u"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f5a6a61d",
   "metadata": {},
   "source": [
    "## 6. Alice Generates a Challenge `e`\n",
    "\n",
    "Alice randomly generates a challenge, `e`, as either 0 or 1 and sends it to Bob.\n",
    "\n",
    "Again, as mentioned in Step 5 above, it's significant that this challenge occurs *after* Bob has already submitted a value of `u` to Alice."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "0e92876d",
   "metadata": {},
   "outputs": [],
   "source": [
    "def generate_challenge():\n",
    "    e = random.randint(0, 1)\n",
    "    return e"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3be8fa52",
   "metadata": {},
   "source": [
    "## 7. Bob Responds With `v` Depending on the Challenge\n",
    "\n",
    "Bob responds with `v`, which depends on the challenge `e` from Alice. You may notice that `v` is only a function of `x` when `e` is 1.\n",
    "\n",
    "In other words, whenever `e` is 0, Bob doesn't need to know `x` to return `v`. He could be lying about knowing `x`, so why bother ever using `e` of 0?\n",
    "\n",
    "The reason to allow `e` to be 0 is that if both Bob knew ahead of time that `e` will always be 1, it's possible he could submit values of `u` and `v` that would look correct, just by knowing `f(x)`, even if he doesn't know `x` itself.\n",
    "\n",
    "We'll see this play out in Part B in more detail. For now, keep in mind that the difficult to anticipate what `e` will be means Bob can not fake a valid response with a 100% chance of success."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "f27096a1",
   "metadata": {},
   "outputs": [],
   "source": [
    "def respond_to_challenge(e,r,x):\n",
    "    if e == 1:\n",
    "        v = r + x\n",
    "    else:\n",
    "        v = r\n",
    "        \n",
    "    return v"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b70a0340",
   "metadata": {},
   "source": [
    "## 8. Alice Verifies the Proof\n",
    "\n",
    "Alice can then verify the proof, based on the value of `e` she provided.\n",
    "\n",
    "---\n",
    "\n",
    "If `e` is 0, she asserts that the `u` value Bob provided is equal to `pow(g, v, p)`.\n",
    "\n",
    "The reason for this is straightforward. Since when `e` is 0, if Bob is honest, he will have responded with `v = r`.\n",
    "\n",
    "Thus `u = pow(g, v, p) = pow(g, r, p)`.\n",
    "\n",
    "If Bob is honest, then he will have published a value of `u` calculated as `u = pow(g, r, p)`, so Alice can easily ensure that the values of `u` and `v` which Bob provided do indeed work out.\n",
    "\n",
    "---\n",
    "\n",
    "If `e` is 1, the math is a bit more complex.\n",
    "\n",
    "Why should `(u * fx) % p = pow(g, v, p)`?\n",
    "\n",
    "If Bob is honest, `u` is calculated as `pow(g, r, p)` and `fx` is calculated as `pow(g, x, p)`.\n",
    " \n",
    "We can therefore rewrite `(u * fx) % p` as:\n",
    "\n",
    "`(pow(g, r, p) * pow(g, x, p)) % p`\n",
    "\n",
    "And without getting too deep into the mathematics itself, we can rewrite this simplified as:\n",
    "\n",
    "`pow(g, r + x, p)`\n",
    "\n",
    "Recall though, that in the case when `e` is 1, if Bob is honest, `v = r + x`, so we express this as:\n",
    "\n",
    "`pow(g, v, p)`\n",
    "\n",
    "Thus, when `e` is 1 and if Bob is honest, `(u * fx) % p` is just another way to write `pow(g, v, p)`, so if these two expressions are not equivalent, then Bob is not being honest.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "7234d134",
   "metadata": {},
   "outputs": [],
   "source": [
    "def verify_proof(e,u,g,v,p,fx):\n",
    "    if e == 0:\n",
    "        assert u == pow(g, v, p), \"Failed when e=0, we caught Bob lying about knowing x!\"\n",
    "    else:\n",
    "        assert (u * fx) % p == pow(g, v, p), \"Failed when e=1, we caught Bob lying about knowing x!\"\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "073a355c",
   "metadata": {},
   "source": [
    "## 9. Repeat Steps 4-8 Multiple Times\n",
    "\n",
    "Steps 4-8 are repeated multiple times, because if only conducted once, it is possible that Bob is a bad actor and just happened to correctly guess whether `e` will be 0 or 1, and prepared a response that *always* works if `e` is 0 (or a response that *always* works if `e` is 1).\n",
    "\n",
    "In other words, if only conducted once, there is a 50% chance that Bob is lying and he just happened to guess `e` correctly, so there is a 50% chance he can get away with appearing to know `x` even though he only knows `f(x)`. Conceptually, this would be like faking he knows a private key, while only actually knowing a public key.\n",
    "\n",
    "If this process is repeated 10 times though, there is only a `0.5 ** 10` chance (less than a 0.1% chance) of him correctly guessing `e` and lying each time. The process can be repeated any number of times until Alice feels confident enough that Bob has proved to her that he is being honest about knowing `x`.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "id": "a4a7d99d",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "No assert failures! Bob is honest!\n"
     ]
    }
   ],
   "source": [
    "for i in range(0,10):\n",
    "    r = pick_private_random_int(p)\n",
    "    u = calculate_u(g, r, p)\n",
    "    e = generate_challenge()\n",
    "    v = respond_to_challenge(e,r,x)\n",
    "    verify_proof(e,u,g,v,p,fx)\n",
    "    \n",
    "print('No assert failures! Bob is honest!')"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "41f74f91",
   "metadata": {},
   "source": [
    "What we've done so far is construct an \"interactive proof\", since it requires Bob and Alice to go back and forth several times for Alice to have confidence in Bob's proof that he knows `x`.\n",
    "\n",
    "You may have heard of the term SNARK, which stands for \"Succinct Non-interactive ARguments of Knowledge\".\n",
    "\n",
    "Notice how SNARKs are \"non-interactive\". The proof we have constructed so far is a zero knowledge proof, but it is not a SNARK in part because it is interactive. We'll look at making this non-interactive in Part C.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ba98e05f",
   "metadata": {},
   "source": [
    "# Part B: Bob is a Bad Actor\n",
    "\n",
    "Before making our proof non-interactive, we still have to answer the question: \"what if Bob is lying?\"\n",
    "\n",
    "Perhaps Bob does not actually know `x`, the private secret, but knows `fx`, the public output of `pow(g, x, p)`.\n",
    "\n",
    "In this case, it's possible Bob could manipulate a value of `u` such that if `e` is 1, the check passes even without knowing `x`."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "fc242e39",
   "metadata": {},
   "source": [
    "## B.1 Generate `u` From `fx`\n",
    "\n",
    "In order to fool Alice, Bob could calculate `u` as `g^r mod p / f(x)` instead of as `g^r mod p`.\n",
    "\n",
    "This involves finding the multiplicative inverse of `fx mod p`.\n",
    "\n",
    "For more on multiplicative inverse: https://en.wikipedia.org/wiki/Modular_multiplicative_inverse\n",
    "\n",
    "We'll assume Bob is a powerful bad actor who can calculate this in order to attempt to fake the proof, though in practice this will not be easy for Bob."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "id": "cdfd2d3c",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "13"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def bad_actor_calculate_u(g, r, p, fx):\n",
    "    fx_inverse = pow(fx, -1, p)\n",
    "    u = (pow(g, r, p) * fx_inverse) % p\n",
    "    \n",
    "    return u\n",
    "\n",
    "bad_u = bad_actor_calculate_u(g, r, p, fx)\n",
    "bad_u"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "63e8e942",
   "metadata": {},
   "source": [
    "## B.2 Set `v` to `r`\n",
    "\n",
    "Bob, the bad actor, can respond with `v = r`, instead of `v = r + x`, because their `bad_u` value will pass Alice's validation check regardless of the value of `x`.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "id": "f4760dc0",
   "metadata": {},
   "outputs": [],
   "source": [
    "def bad_actor_respond_to_challenge(r):\n",
    "    v = r\n",
    "    return v"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7268a729",
   "metadata": {},
   "source": [
    "## B.3 When `e` is 1, Bob Passes the Checks\n",
    "\n",
    "When `e` is 1, Bob's `u` generated from `bad_actor_calculate_u()`, passes the `verify_proof()` checks (without needing to know `x`).\n",
    "\n",
    "Note in the below code block that Bob is able to pass the checks despite never using `x` as an input to prepare what he submits to Alice. Neither `u` nor `v` incorporate `x` in any way, thus Bob is able to successfully lie and pass the check without actually needing to know `x`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "id": "1f1003d0",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "No assert failures! Bob appears to be honest but he is a bad actor!\n"
     ]
    }
   ],
   "source": [
    "r = pick_private_random_int(p)\n",
    "u = bad_actor_calculate_u(g, r, p, fx) # The bad actor function is used\n",
    "e = 1 # Not randomizing `e` here to show Bob can successfully lie when `e` is 1\n",
    "v = bad_actor_respond_to_challenge(r) # The bad actor function is used\n",
    "\n",
    "verify_proof(e,u,g,v,p,fx)\n",
    "    \n",
    "print('No assert failures! Bob appears to be honest but he is a bad actor!')\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c5afbf74",
   "metadata": {},
   "source": [
    "## B.4 If Bob Knows `e` Ahead of Time, He Passes All Checks\n",
    "\n",
    "If Bob can successfully lie when `e` is 1, then why not just always use 0 for `e`?\n",
    "\n",
    "Because if Bob *knows* that `e` will always be 0, he can prepare for that.\n",
    "\n",
    "In fact, you may recall that earlier in Part A, Step 7, we asked the exact opposite question, \"why bother ever using `e` of 0?\"\n",
    "\n",
    "As you can see, always using either `e` of 0, or `e` of 1, each has its own problems.\n",
    "\n",
    "Bob can not be able to anticipate what `e` will be ahead of time, otherwise we can successfully lie.\n",
    "\n",
    "Notice in the below code block, `e` is generated first, allowing Bob to react to how we submits a value of `u`. This simulates Bob knowing `e` ahead of time.\n",
    "\n",
    "If Bob can guess `e` ahead of time, whether by luck or by a failure on Alice's part to sufficiently randomize `e`, then he can get away with lying regardless of the value of `e`.\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "id": "6d542341",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "No assert failures! Bob appears to be honest but he is a bad actor!\n"
     ]
    }
   ],
   "source": [
    "for i in range(0,10):\n",
    "    r = pick_private_random_int(p)\n",
    "    e = generate_challenge()\n",
    "    # Note how the challenge `e` is generated *before* Bob shares `u`, allowing him to tailor how he responds\n",
    "    # Also note that Bob never needs to use `x` itself to prepare `u` or `v`, he can do this without knowing `x`\n",
    "    if e == 0:\n",
    "        u = calculate_u(g, r, p)\n",
    "    else:\n",
    "        u = bad_actor_calculate_u(g, r, p, fx)\n",
    "        \n",
    "    v = bad_actor_respond_to_challenge(r)\n",
    "    \n",
    "    verify_proof(e,u,g,v,p,fx)\n",
    "    \n",
    "print('No assert failures! Bob appears to be honest but he is a bad actor!')\n",
    "    "
   ]
  },
  {
   "cell_type": "markdown",
   "id": "38413719",
   "metadata": {},
   "source": [
    "## B.5 Checks Must be Repeated, With `e` Shared After `u` for Bob to Fail\n",
    "\n",
    "In order to be confident that we can catch Bob's lie, checks must be repeated multiple times, `e` must be randomized, and `u` must be shared *after* `e` is randomized.\n",
    "\n",
    "Please note that the below cell *should have an AssertionError* this is the expected and desired outcome.\n",
    "\n",
    "The AssertionError is indicating the proof verification failed when Bob was a bad actor and was lying about knowing `x`, which is exactly what we want to occur.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "id": "92fbc238",
   "metadata": {},
   "outputs": [
    {
     "ename": "AssertionError",
     "evalue": "Failed when e=0, we caught Bob lying about knowing x!",
     "output_type": "error",
     "traceback": [
      "\u001b[1;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[1;31mAssertionError\u001b[0m                            Traceback (most recent call last)",
      "\u001b[1;32m~\\AppData\\Local\\Temp\\ipykernel_19496\\2455878826.py\u001b[0m in \u001b[0;36m<module>\u001b[1;34m\u001b[0m\n\u001b[0;32m      4\u001b[0m     \u001b[0me\u001b[0m \u001b[1;33m=\u001b[0m \u001b[0mgenerate_challenge\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m      5\u001b[0m     \u001b[0mv\u001b[0m \u001b[1;33m=\u001b[0m \u001b[0mbad_actor_respond_to_challenge\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mr\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[1;32m----> 6\u001b[1;33m     \u001b[0mverify_proof\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0me\u001b[0m\u001b[1;33m,\u001b[0m\u001b[0mu\u001b[0m\u001b[1;33m,\u001b[0m\u001b[0mg\u001b[0m\u001b[1;33m,\u001b[0m\u001b[0mv\u001b[0m\u001b[1;33m,\u001b[0m\u001b[0mp\u001b[0m\u001b[1;33m,\u001b[0m\u001b[0mfx\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m\u001b[0;32m      7\u001b[0m \u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m      8\u001b[0m \u001b[0mprint\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;34m'No assert failures! Bob appears to be honest but he is a bad actor!'\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n",
      "\u001b[1;32m~\\AppData\\Local\\Temp\\ipykernel_19496\\3435920725.py\u001b[0m in \u001b[0;36mverify_proof\u001b[1;34m(e, u, g, v, p, fx)\u001b[0m\n\u001b[0;32m      1\u001b[0m \u001b[1;32mdef\u001b[0m \u001b[0mverify_proof\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0me\u001b[0m\u001b[1;33m,\u001b[0m\u001b[0mu\u001b[0m\u001b[1;33m,\u001b[0m\u001b[0mg\u001b[0m\u001b[1;33m,\u001b[0m\u001b[0mv\u001b[0m\u001b[1;33m,\u001b[0m\u001b[0mp\u001b[0m\u001b[1;33m,\u001b[0m\u001b[0mfx\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m      2\u001b[0m     \u001b[1;32mif\u001b[0m \u001b[0me\u001b[0m \u001b[1;33m==\u001b[0m \u001b[1;36m0\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[1;32m----> 3\u001b[1;33m         \u001b[1;32massert\u001b[0m \u001b[0mu\u001b[0m \u001b[1;33m==\u001b[0m \u001b[0mpow\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mg\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mv\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mp\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m,\u001b[0m \u001b[1;34m\"Failed when e=0, we caught Bob lying about knowing x!\"\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m\u001b[0;32m      4\u001b[0m     \u001b[1;32melse\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m      5\u001b[0m         \u001b[1;32massert\u001b[0m \u001b[1;33m(\u001b[0m\u001b[0mu\u001b[0m \u001b[1;33m*\u001b[0m \u001b[0mfx\u001b[0m\u001b[1;33m)\u001b[0m \u001b[1;33m%\u001b[0m \u001b[0mp\u001b[0m \u001b[1;33m==\u001b[0m \u001b[0mpow\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mg\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mv\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mp\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m,\u001b[0m \u001b[1;34m\"Failed when e=1, we caught Bob lying about knowing x!\"\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n",
      "\u001b[1;31mAssertionError\u001b[0m: Failed when e=0, we caught Bob lying about knowing x!"
     ]
    }
   ],
   "source": [
    "for i in range(0,10):\n",
    "    r = pick_private_random_int(p)\n",
    "    u = bad_actor_calculate_u(g, r, p, fx)\n",
    "    e = generate_challenge()\n",
    "    v = bad_actor_respond_to_challenge(r)\n",
    "    verify_proof(e,u,g,v,p,fx)\n",
    "    \n",
    "print('No assert failures! Bob appears to be honest but he is a bad actor!')"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2f90c9df",
   "metadata": {},
   "source": [
    "# Part C: A Non-Interactive Zero Knowledge Proof\n",
    "\n",
    "So far in this tutorial, Alice has been able to verify, to a very high degree of confidence, that Bob does in fact know the value of `x`, without Bob having to reveal `x` itself.\n",
    "\n",
    "In other words, Bob has been able to prove that he knows `x` while giving Alice \"zero knowledge\" about `x`.\n",
    "\n",
    "However, the obvious drawback with the proof so far is that it requires a repeated back and forth between Bob and Alice (interactive proof). Ideally, Bob could create a proof that anyone could validate, without the need for going back and forth, or even directly communicating with Bob at all (non-interactive proof).\n",
    "\n",
    "---\n",
    "\n",
    "In the interactive case, repeating the proof multiple times with randomized challenges added an element that made it hard for a bad actor to predict how to fake an appropriate response.\n",
    "\n",
    "The question then becomes, how do we retain this \"hard to predict how to fake an appropriate response\" trait of our proof, without relying on multiple random challenges as the source of that difficulty.\n",
    "\n",
    "Instead of using repeated randomized challenges, we can use a hash to generate the challenge.\n",
    "\n",
    "Since, as we already know, the outcome of a hash is extremely hard to predict given an input, a hash makes it effectively impossible for a bad actor to pre-calculate a response that will \"game\" the output of the hash.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "id": "25e531ea",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "66943969713086776032173464195394550745560523545004192271047021628614662158183"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "import random\n",
    "import hashlib\n",
    "\n",
    "# Bob publishes f(x)\n",
    "fx = pow(g, x, p)\n",
    "\n",
    "# Bob picks random number r\n",
    "r = random.randint(0, p - 1)\n",
    "\n",
    "# Bob calculates u\n",
    "u = pow(g, r, p)\n",
    "\n",
    "# Bob calculates `e` as the hash of `u`\n",
    "# Note how `e` is an extremely large number\n",
    "# This makes it exceptionally difficult for a bad actor to find a `u` that hashes to a given `e`\n",
    "e = int(hashlib.sha256(str(u).encode()).hexdigest(), 16)\n",
    "e"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "id": "bcae430c",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "66943969713086776032173464195394550745560523545004192271047021628614662158183"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Bob calculates `v`\n",
    "v = (r + e * x) % (p - 1)\n",
    "\n",
    "# Bob shares `v` and `u` with Alice\n",
    "\n",
    "# Alice calculates her own `e` value by hashing `u`\n",
    "e_alice = int(hashlib.sha256(str(u).encode()).hexdigest(), 16)\n",
    "e_alice"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "id": "25e9f8b5",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "No assert failures! Bob is honest!\n"
     ]
    }
   ],
   "source": [
    "# Alice ensures that the values of `e` `u` and `v` satisfy the proof\n",
    "assert pow(g, v, p) == (u * pow(fx, e_alice, p)) % p, \"Failed, we caught Bob lying about knowing x!\"\n",
    "\n",
    "print('No assert failures! Bob is honest!')"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "fe718883",
   "metadata": {},
   "source": [
    "With the above approach, Bob can prepare and publish the proof ahead of time, and anyone, at anytime, can verify the proof without multiple rounds required, and without ever needing to directly interact with Bob.\n",
    "\n",
    "We have successfully modified our proof to be a non-interactive proof.\n",
    "\n",
    "---\n",
    "\n",
    "In theory, Bob could try to cheat by privately choosing different values of `u` until finding one that products a hash `e` which would pass the check, and then only share that `u` value he knows will work.\n",
    "\n",
    "In practice however, this would essentially require a brute force attack that would be extremely difficult for two reasons.\n",
    "\n",
    "1. The hash function H (e.g., SHA-256) produces outputs that appear random and are spread over a large range (from 0 to 2^256 - 1, to be precise). Therefore, Bob has no way to predict what `e` will be for a given `u`, and finding a suitable `u` by trial and error would take an enormous amount of time and computation power.\n",
    "\n",
    "2. The proof verification that Alice performs is itself a one-way function. Even if Bob knows `e`, `g`, `p`, and `fx`, finding an `x` that makes the proof check hold true runs into the discrete logarithm problem we previously discussed. And without knowing `x`, Bob has no efficient way to find a suitable `v`, since `v` is directly dependent on the value of `x`.\n",
    "\n",
    "Therefore, while it's theoretically possible for Bob to cheat by choosing a suitable `u`, in practice this would be computationally infeasible unless he knows `x` - which is exactly what the protocol is designed to verify in the first place.\n",
    "\n",
    "---\n",
    "\n",
    "A note on SNARKS:\n",
    "\n",
    "At this point we now understand the core concepts of zero knowledge proofs, and have a working example of a very simplistic non-interactive zero knowledge proof. In practice, the (very) simple proof in this tutorial is still very far from being a SNARK, both in terms of complexity and performance.\n",
    "\n",
    "Succinct Non-interactive ARguments of Knowledge (SNARKs) are a specific type of zero knowledge proof. 'Succinct' means the proofs are small in size and can be verified quickly. While it's technically possible to create a Python implementation of a SNARK, transforming our current tutorial into a SNARK is nontrivial would go well beyond basic Python and involves a deep understanding of cryptography techniques and number theory.\n",
    "\n",
    "In a nutshell, to make a zero knowledge proof into a SNARK, we'd need to adopt cryptographic pairings and elliptic curve operations, or alternatively use arithmetic circuits, to create an argument system where the proof size is small (succinct) and the verification is fast.\n",
    "\n",
    "For more about these topics: https://en.wikipedia.org/wiki/Elliptic-curve_cryptography\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "23a01274",
   "metadata": {},
   "source": [
    "# Appendix"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e674d1f3",
   "metadata": {},
   "source": [
    "## I. Why does `p` need to be very large?\n",
    "\n",
    "In our tutorial, we chose a `p` value for a simple demonstration of the core concepts. But in practice, if this were a real-world zero knowledge proof, `p` would need to be very large to ensure proper security.\n",
    "\n",
    "In not, it would be easy to brute force attack (essentially guess `x` by trial-and-error), which means anyone could figure out what `x` is, which would undo the entire purpose of the proof in the first place: to keep `x` secret.\n",
    "\n",
    "In the below, you can see just how quick and easy it would be for an attacker to figure out the secret value of `x` when using the actual `p` value we used in our tutorial."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "id": "909f4c01",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Checking if x is equal to:  0\n",
      "Checking if x is equal to:  1\n",
      "Checking if x is equal to:  2\n",
      "Checking if x is equal to:  3\n",
      "Checking if x is equal to:  4\n",
      "Checking if x is equal to:  5\n",
      "Checking if x is equal to:  6\n",
      "Cracked the secret, x is equal to:  6\n",
      "Wall time: 85.4 µs\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "6"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%%time\n",
    "def brute_force_method(fx, g, p):\n",
    "    for x in range(p):\n",
    "        print('Checking if x is equal to: ', x)\n",
    "        if pow(g, x, p) == fx:\n",
    "            print('Cracked the secret, x is equal to: ', x, )\n",
    "            return x\n",
    "    return None\n",
    "\n",
    "brute_force_method(fx, g, p)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "8586fe26",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "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.9.13"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}