plonk_original.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Evaluate \n",
    "$ f(x, y) = 2x^2 - x^2y^2 + 3 $\n",
    "\n",
    "$ g_0 = x ⋅ x $ \n",
    "\n",
    "$ g_1 = x ⋅ x $ \n",
    "\n",
    "$ g_2 = y ⋅ y $\n",
    "\n",
    "$ g_3 = g_0 ⋅ 2 $\n",
    "\n",
    "$ g_4 = g_1 ⋅ g_2 $\n",
    "\n",
    "$ g_5 = g_2 - g_4 $\n",
    "\n",
    "$ g_6 = g_5 + 3 $\n",
    "\n",
    "---\n",
    "\n",
    "$ c_0 = a_0 ⋅ b_0 $\n",
    "\n",
    "$ c_1 = a_1 ⋅ b_1 $\n",
    "\n",
    "$ c_2 = a_2 ⋅ b_2 $\n",
    "\n",
    "$ c_3 = a_3 ⋅ 2 $\n",
    "\n",
    "$ c_4 = a_4 ⋅ b_4 $\n",
    "\n",
    "$ c_5 = a_5 - b_5 $\n",
    "\n",
    "$ c_6 = a_6 + 3 $\n",
    "\n",
    "---\n",
    "\n",
    "$ x = a_0 = b_0 = a_1 = b_1 $\n",
    "\n",
    "$ y = a_2 = b_2 $\n",
    "\n",
    "$ g_0 = a_3 = c_0 $\n",
    "\n",
    "$ g_1 = a_4 = c_1 $\n",
    "\n",
    "$ g_2 = b_4 = c_2 $\n",
    "\n",
    "$ g_3 = a_5 = c_3 $\n",
    "\n",
    "$ g_4 = b_5 = c_4 $\n",
    "\n",
    "$ g_5 = a_6 = c_5 $\n",
    "\n",
    "$ g_6 = c_6 $\n",
    "\n",
    "### Gate constrain equation\n",
    "\n",
    "$ g_i = q_{Li}⋅a_i+q_{Ri}⋅b_i+q_{Mi}⋅(a_i⋅b_i)+q_{Ci}+q_{Oi}⋅c_i=0 $\n",
    "\n",
    "$ g_0 = 0⋅a_0 + 0⋅b_0 + 1⋅(a_0⋅b_0) + 0 + (-1)⋅c_0 = 0 $\n",
    "\n",
    "$ g_1 = 0⋅a_1 + 0⋅b_1 + 1⋅(a_1⋅b_1) + 0 + (-1)⋅c_1 = 0 $\n",
    "\n",
    "$ g_2 = 0⋅a_2 + 0⋅b_2 + 1⋅(a_2⋅b_2) + 0 + (-1)⋅c_2 = 0 $\n",
    "\n",
    "$ g_3 = 2⋅a_3 + 0⋅b_3 + 0⋅(a_3⋅b_3) + 0 + (-1)⋅c_3 = 0 $\n",
    "\n",
    "$ g_4 = 0⋅a_4 + 0⋅b_4 + 1⋅(a_4⋅b_4) + 0 + (-1)⋅c_4 = 0 $\n",
    "\n",
    "$ g_5 = 1⋅a_5 + (-1)⋅b_5 + 0⋅(a_5⋅b_5) + 0 + (-1)⋅c_5 = 0 $\n",
    "\n",
    "$ g_6 = 1⋅a_6 + 0⋅b_6 + 0⋅(a_6⋅b_6) + 3 + (-1)⋅c_6 = 0 $\n",
    "\n",
    "**selector vectors**\n",
    "\n",
    "$ g_i = [q_{Li}, q_{Ri}, q_{Mi}, q_{Ci}, q_{Oi}] $\n",
    "\n",
    "$ g_0 = [0, 0, 1, 0, -1] $\n",
    "\n",
    "$ g_1 = [0, 0, 1, 0, -1] $\n",
    "\n",
    "$ g_2 = [0, 0, 1, 0, -1] $\n",
    "\n",
    "$ g_3 = [2, 0, 0, 0, -1] $\n",
    "\n",
    "$ g_4 = [0, 0, 1, 0, -1] $\n",
    "\n",
    "$ g_5 = [1, -1, 0, 0, -1] $\n",
    "\n",
    "$ g_6 = [1, 0, 0, 3, -1] $\n",
    "\n",
    "**let x = 2 y = 3**\n",
    "\n",
    "\n",
    "| Vectors| a | b | c | qLi | qRi | qMi | qCi | qOi |\n",
    "| --- | --- | --- | --- |--- | --- | --- | --- | --- |\n",
    "| gate0 | 2 | 2 | 4 | 0 | 0 | 1 | 0 | -1 |\n",
    "| gate1 | 2 | 2 | 4 | 0 | 0 | 1 | 0 | -1 |\n",
    "| gate2 | 3 | 3 | 9 | 0 | 0 | 1 | 0 | -1 |\n",
    "| gate3 | 4 | 0 | 8 | 2 | 0 | 0 | 0 | -1 |\n",
    "| gate4 | 4 | 9 | 36 | 0 | 0 | 1 | 0 | -1 |\n",
    "| gate5 | 8 | 36 | -28 | 1 | -1 | 0 | 0 | -1 |\n",
    "| gate6 | -28 | 3 | -25 | 1 | 0 | 0 | 3 | -1 |"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import galois\n",
    "from py_ecc.optimized_bls12_381 import add, multiply, G1, G2, neg, pairing, eq, normalize\n",
    "\n",
    "\n",
    "class SRS:\n",
    "    def __init__(self, tau, n = 2):\n",
    "        self.tau = tau\n",
    "        self.tau1 = [multiply(G1, int(tau)**i) for i in range(0, n + 3)]\n",
    "        self.tau2 = multiply(G2, int(tau))\n",
    "\n",
    "    def __str__(self):\n",
    "        s = f\"tau: {self.tau}\\n\"\n",
    "        s += \"\".join([f\"[tau^{i}]G1: {str(normalize(point))}\\n\" for i, point in enumerate(self.tau1)])\n",
    "        s += f\"[tau^{i}]G2: {str(normalize(self.tau2))}\\n\"\n",
    "        return s\n",
    "\n",
    "\n",
    "def new_call(self, at, **kwargs):\n",
    "    if isinstance(at, SRS):\n",
    "        coeffs = self.coeffs[::-1]\n",
    "        result = multiply(at.tau1[0], coeffs[0])\n",
    "        for i in range(1, len(coeffs)):\n",
    "            result = add(result, multiply(at.tau1[i], coeffs[i]))\n",
    "        return result\n",
    "\n",
    "    return galois.Poly.original_call(self, at, **kwargs)\n",
    "\n",
    "galois.Poly.original_call = galois.Poly.__call__\n",
    "galois.Poly.__call__ = new_call"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Setup"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "out = -25\n",
      "roots = [  1  30 177   8 240 211  64 233]\n"
     ]
    },
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "OMP: Info #270: omp_set_nested routine deprecated, please use omp_set_max_active_levels instead.\n"
     ]
    }
   ],
   "source": [
    "x = 2\n",
    "y = 3\n",
    "\n",
    "# 2x^2 - x^2y^2 + 3\n",
    "out = 2*x**2 - x**2*y**2 + 3\n",
    "print(f\"out = {out}\")\n",
    "\n",
    "# We have 7 gates, next power of 2 is 8\n",
    "n = 7\n",
    "n = 2**int(np.ceil(np.log2(n)))\n",
    "assert n & n - 1 == 0, \"n must be a power of 2\"\n",
    "\n",
    "# Prime field p\n",
    "p = 241\n",
    "Fp = galois.GF(p)\n",
    "\n",
    "# Find primitive root of unity\n",
    "omega = Fp.primitive_root_of_unity(n)\n",
    "assert omega**(n) == 1, f\"omega (ω) {omega} is not a root of unity\"\n",
    "\n",
    "roots = Fp([omega**i for i in range(n)])\n",
    "print(f\"roots = {roots}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Witness & Gates"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "a = [2, 2, 3, 4, 4, 8, -28, 0]\n",
      "b = [2, 2, 3, 0, 9, 36, 3, 0]\n",
      "c = [4, 4, 9, 8, 36, -28, -25, 0]\n",
      "ql = [0, 0, 0, 2, 0, 1, 1, 0]\n",
      "qr = [0, 0, 0, 0, 0, -1, 0, 0]\n",
      "qm = [1, 1, 1, 1, 1, 0, 0, 0]\n",
      "qc = [0, 0, 0, 0, 0, 0, 3, 0]\n",
      "qo = [-1, -1, -1, -1, -1, -1, -1, 0]\n",
      "qpi = [0, 0, 0, 0, 0, 0, 0, 0]\n"
     ]
    }
   ],
   "source": [
    "def pad_array(a, n):\n",
    "    return a + [0]*(n - len(a))\n",
    "\n",
    "# witness vectors\n",
    "a = [2, 2, 3, 4, 4, 8, -28]\n",
    "b = [2, 2, 3, 0, 9, 36, 3]\n",
    "c = [4, 4, 9, 8, 36, -28, -25]\n",
    "\n",
    "# gate vectors\n",
    "ql = [0, 0, 0, 2, 0, 1, 1]\n",
    "qr = [0, 0, 0, 0, 0, -1, 0]\n",
    "qm = [1, 1, 1, 1, 1, 0, 0]\n",
    "qc = [0, 0, 0, 0, 0, 0, 3]\n",
    "qo = [-1, -1, -1, -1, -1, -1, -1]\n",
    "qpi = [0, 0, 0, 0, 0, 0, 0]\n",
    "\n",
    "# pad vectors to length n\n",
    "a = pad_array(a, n)\n",
    "b = pad_array(b, n)\n",
    "c = pad_array(c, n)\n",
    "ql = pad_array(ql, n)\n",
    "qr = pad_array(qr, n)\n",
    "qm = pad_array(qm, n)\n",
    "qc = pad_array(qc, n)\n",
    "qo = pad_array(qo, n)\n",
    "qpi = pad_array(qpi, n)\n",
    "\n",
    "print(f\"a = {a}\")\n",
    "print(f\"b = {b}\")\n",
    "print(f\"c = {c}\")\n",
    "print(f\"ql = {ql}\")\n",
    "print(f\"qr = {qr}\")\n",
    "print(f\"qm = {qm}\")\n",
    "print(f\"qc = {qc}\")\n",
    "print(f\"qo = {qo}\")\n",
    "print(f\"qpi = {qpi}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Permutations"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      " w | value  | i      | sigma(i)\n",
      "a0 |      2 |      1 |      1\n",
      "a1 |      2 |     30 |     30\n",
      "a2 |      3 |    177 |    177\n",
      "a3 |      4 |      8 |      4\n",
      "a4 |      4 |    240 |    120\n",
      "a5 |      8 |    211 |     32\n",
      "a6 |    -28 |     64 |    121\n",
      "a7 |      0 |    233 |    233\n",
      "-- | --     | --     | --    \n",
      "b0 |      2 |      2 |      2\n",
      "b1 |      2 |     60 |     60\n",
      "b2 |      3 |    113 |    113\n",
      "b3 |      0 |     16 |     16\n",
      "b4 |      9 |    239 |    226\n",
      "b5 |     36 |    181 |    237\n",
      "b6 |      3 |    128 |    128\n",
      "b7 |      0 |    225 |    225\n",
      "-- | --     | --     | --    \n",
      "c0 |      4 |      4 |      8\n",
      "c1 |      4 |    120 |    240\n",
      "c2 |      9 |    226 |    239\n",
      "c3 |      8 |     32 |    211\n",
      "c4 |     36 |    237 |    181\n",
      "c5 |    -28 |    121 |     64\n",
      "c6 |    -25 |     15 |     15\n",
      "c7 |      0 |    209 |    209\n",
      "\n",
      "\n",
      "--- Cosest ---\n",
      "c0 = [  1  30 177   8 240 211  64 233]\n",
      "c1 = [  2  60 113  16 239 181 128 225]\n",
      "c2 = [  4 120 226  32 237 121  15 209]\n",
      "\n",
      "\n",
      "--- Sigma ---\n",
      "sigma1 = [  1  30 177   4 120  32 121 233]\n",
      "sigma2 = [  2  60 113  16 226 237 128 225]\n",
      "sigma3 = [  8 240 239 211 181  64  15 209]\n"
     ]
    }
   ],
   "source": [
    "def print_sigma(sigma, a, b, c, r):\n",
    "    group_size = len(sigma) // 3\n",
    "    padding = 6\n",
    "\n",
    "    print(f\"{' w'} | {'value':{padding}} | {'i':{padding}} | {'sigma(i)':{padding}}\")\n",
    "\n",
    "    for i in range(0, group_size):\n",
    "        print(f\"a{i} | {a[i]:{padding}} | {r[i]:{padding}} | {r[sigma[i]]:{padding}}\")\n",
    "\n",
    "    print(f\"-- | {'--':{padding}} | {'--':{padding}} | {'--':{padding}}\")\n",
    "\n",
    "    for i in range(group_size, 2 * group_size):\n",
    "        print(f\"b{i - group_size} | {b[i - group_size]:{padding}} | {r[i]:{padding}} | {r[sigma[i]]:{padding}}\")\n",
    "\n",
    "    print(f\"-- | {'--':{padding}} | {'--':{padding}} | {'--':{padding}}\")\n",
    "\n",
    "    for i in range(2 * group_size, 3 * group_size):\n",
    "        print(f\"c{i - 2 * group_size} | {c[i - 2 * group_size]:{padding}} | {r[i]:{padding}} | {r[sigma[i]]:{padding}}\")\n",
    "\n",
    "ai = range(0, n)\n",
    "bi = range(n, 2*n)\n",
    "ci = range(2*n, 3*n)\n",
    "\n",
    "sigma = {\n",
    "    ai[0]: ai[0], ai[1]: ai[1], ai[2]: ai[2], ai[3]: ci[0], ai[4]: ci[1], ai[5]: ci[3], ai[6]: ci[5], ai[7]: ai[7],\n",
    "    bi[0]: bi[0], bi[1]: bi[1], bi[2]: bi[2], bi[3]: bi[3], bi[4]: ci[2], bi[5]: ci[4], bi[6]: bi[6], bi[7]: bi[7],\n",
    "    ci[0]: ai[3], ci[1]: ai[4], ci[2]: bi[4], ci[3]: ai[5], ci[4]: bi[5], ci[5]: ai[6], ci[6]: ci[6], ci[7]: ci[7],\n",
    "}\n",
    "\n",
    "k1 = 2\n",
    "k2 = 4\n",
    "c1_roots = roots\n",
    "c2_roots = roots * k1\n",
    "c3_roots = roots * k2\n",
    "\n",
    "c_roots = np.concatenate((c1_roots, c2_roots, c3_roots))\n",
    "\n",
    "check = set()\n",
    "for r in c_roots:\n",
    "    assert not int(r) in check, f\"Duplicate root {r} in {c_roots}\"\n",
    "    check.add(int(r))\n",
    "\n",
    "sigma1 = Fp([c_roots[sigma[i]] for i in range(0, n)])\n",
    "sigma2 = Fp([c_roots[sigma[i + n]] for i in range(0, n)])\n",
    "sigma3 = Fp([c_roots[sigma[i + 2 * n]] for i in range(0, n)])\n",
    "\n",
    "print_sigma(sigma, a, b, c, c_roots)\n",
    "\n",
    "print(\"\\n\\n--- Cosest ---\")\n",
    "print(f\"c0 = {c1_roots}\")\n",
    "print(f\"c1 = {c2_roots}\")\n",
    "print(f\"c2 = {c3_roots}\")\n",
    "\n",
    "print(\"\\n\\n--- Sigma ---\")\n",
    "print(f\"sigma1 = {sigma1}\")\n",
    "print(f\"sigma2 = {sigma2}\")\n",
    "print(f\"sigma3 = {sigma3}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Gate Polynomials"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "--- Gate Polynomials ---\n",
      "QL = 187x^7 + 38x^6 + 119x^5 + 60x^4 + 70x^3 + 22x^2 + 106x + 121\n",
      "QR = 64x^7 + 8x^6 + x^5 + 211x^4 + 177x^3 + 233x^2 + 240x + 30\n",
      "QM = 57x^7 + 211x^6 + 73x^5 + 211x^4 + 168x^3 + 211x^2 + 184x + 91\n",
      "QC = 24x^7 + 90x^6 + 217x^5 + 151x^4 + 24x^3 + 90x^2 + 217x + 151\n",
      "QO = 240x^7 + 8x^6 + 177x^5 + 30x^4 + x^3 + 233x^2 + 64x + 210\n",
      "QPI = 0\n"
     ]
    }
   ],
   "source": [
    "def to_galois_array(vector, field):\n",
    "    # normalize to positive values\n",
    "    a = [x % field.order for x in vector]\n",
    "    return field(a)\n",
    "\n",
    "def to_poly(x, v, field):\n",
    "    assert len(x) == len(v)\n",
    "    y = to_galois_array(v, field) if type(v) == list else v\n",
    "    return galois.lagrange_poly(x, y)\n",
    "\n",
    "QL = to_poly(roots, ql, Fp)\n",
    "QR = to_poly(roots, qr, Fp)\n",
    "QM = to_poly(roots, qm, Fp)\n",
    "QC = to_poly(roots, qc, Fp)\n",
    "QO = to_poly(roots, qo, Fp)\n",
    "QPI = to_poly(roots, qpi, Fp)\n",
    "\n",
    "print(\"--- Gate Polynomials ---\")\n",
    "print(f\"QL = {QL}\")\n",
    "print(f\"QR = {QR}\")\n",
    "print(f\"QM = {QM}\")\n",
    "print(f\"QC = {QC}\")\n",
    "print(f\"QO = {QO}\")\n",
    "print(f\"QPI = {QPI}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Permutation Polynomials"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "i =   0 -->   1    I1(  1) =   1    I2(  1) =   2    I3(  1) =   4    S1(  1) =   1    S2(  1) =   2    S3(  1) =   8 \n",
      "i =   1 -->  30    I1( 30) =  30    I2( 30) =  60    I3( 30) = 120    S1( 30) =  30    S2( 30) =  60    S3( 30) = 240 \n",
      "i =   2 --> 177    I1(177) = 177    I2(177) = 113    I3(177) = 226    S1(177) = 177    S2(177) = 113    S3(177) = 239 \n",
      "i =   3 -->   8    I1(  8) =   8    I2(  8) =  16    I3(  8) =  32    S1(  8) =   4    S2(  8) =  16    S3(  8) = 211 \n",
      "i =   4 --> 240    I1(240) = 240    I2(240) = 239    I3(240) = 237    S1(240) = 120    S2(240) = 226    S3(240) = 181 \n",
      "i =   5 --> 211    I1(211) = 211    I2(211) = 181    I3(211) = 121    S1(211) =  32    S2(211) = 237    S3(211) =  64 \n",
      "i =   6 -->  64    I1( 64) =  64    I2( 64) = 128    I3( 64) =  15    S1( 64) = 121    S2( 64) = 128    S3( 64) =  15 \n",
      "i =   7 --> 233    I1(233) = 233    I2(233) = 225    I3(233) = 209    S1(233) = 233    S2(233) = 225    S3(233) = 209 \n"
     ]
    }
   ],
   "source": [
    "S1 = to_poly(roots, sigma1, Fp)\n",
    "S2 = to_poly(roots, sigma2, Fp)\n",
    "S3 = to_poly(roots, sigma3, Fp)\n",
    "\n",
    "I1 = to_poly(roots, c1_roots, Fp)\n",
    "I2 = to_poly(roots, c2_roots, Fp)\n",
    "I3 = to_poly(roots, c3_roots, Fp)\n",
    "\n",
    "padding = 3\n",
    "for i in range(0, len(roots)):\n",
    "    s  = f\"i = {i:{padding}} --> {roots[i]:{padding}} \"\n",
    "    s += f\"   I1({roots[i]:{padding}}) = {I1(roots[i]):{padding}} \"\n",
    "    s += f\"   I2({roots[i]:{padding}}) = {I2(roots[i]):{padding}} \"\n",
    "    s += f\"   I3({roots[i]:{padding}}) = {I3(roots[i]):{padding}} \"\n",
    "    s += f\"   S1({roots[i]:{padding}}) = {S1(roots[i]):{padding}} \"\n",
    "    s += f\"   S2({roots[i]:{padding}}) = {S2(roots[i]):{padding}} \"\n",
    "    s += f\"   S3({roots[i]:{padding}}) = {S3(roots[i]):{padding}} \"\n",
    "    print(s)\n",
    "\n",
    "    assert I1(roots[i]) == roots[i], f\"I1({roots[i]}) != {roots[i]}\"\n",
    "    assert I2(roots[i]) == k1 * roots[i], f\"I2({roots[i]}) != {k1 * roots[i]}\"\n",
    "    assert I3(roots[i]) == k2 * roots[i], f\"I3({roots[i]}) != {k2 * roots[i]}\"\n",
    "\n",
    "    assert S1(roots[i]) == sigma1[i], f\"S1({roots[i]}) != {sigma1[i]}\"\n",
    "    assert S2(roots[i]) == sigma2[i], f\"S2({roots[i]}) != {sigma2[i]}\"\n",
    "    assert S3(roots[i]) == sigma3[i], f\"S3({roots[i]}) != {sigma3[i]}\""
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## CRS Construction"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "--- Tau ---\n",
      "172\n"
     ]
    }
   ],
   "source": [
    "def generate_tau(encrypted=False):\n",
    "    return SRS(Fp.Random(), n) if encrypted else Fp.Random()\n",
    "\n",
    "tau = generate_tau()\n",
    "print(f\"--- Tau ---\")\n",
    "print(tau)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Prover"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "--- Vanishing Polynomial ---\n",
      "Zh = x^8 + 240\n"
     ]
    }
   ],
   "source": [
    "def to_vanishing_poly(roots, field):\n",
    "    # Z^n - 1 = (Z - 1)(Z - w)(Z - w^2)...(Z - w^(n-1))\n",
    "    return galois.Poly.Degrees([len(roots), 0], coeffs=[1, -1], field=field)\n",
    "\n",
    "Zh = to_vanishing_poly(roots, Fp)\n",
    "for x in roots:\n",
    "    assert Zh(x) == 0\n",
    "\n",
    "print(\"--- Vanishing Polynomial ---\")\n",
    "print(f\"Zh = {Zh}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Round 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "--- Gate Constraints Polynomial ---\n",
      "G = 114x^25 + 22x^24 + 25x^23 + 103x^22 + 77x^21 + 46x^20 + 71x^19 + 133x^18 + 135x^17 + 218x^16 + 221x^15 + 117x^14 + 18x^13 + 145x^12 + 47x^11 + 130x^10 + 10x^9 + 139x^8 + 236x^7 + 21x^6 + 146x^5 + 50x^4 + 123x^3 + 219x^2 + 223x + 103\n",
      "gate #0 G(1) = 0 --> OK\n",
      "gate #1 G(30) = 0 --> OK\n",
      "gate #2 G(177) = 0 --> OK\n",
      "gate #3 G(8) = 0 --> OK\n",
      "gate #4 G(240) = 0 --> OK\n",
      "gate #5 G(211) = 0 --> OK\n",
      "gate #6 G(64) = 0 --> OK\n",
      "gate #7 G(233) = 0 --> OK\n",
      "i =   0 -->   1    A(  1) =   2    B(  1) =   2    C(  1) =   4 \n",
      "i =   1 -->  30    A( 30) =   2    B( 30) =   2    C( 30) =   4 \n",
      "i =   2 --> 177    A(177) =   3    B(177) =   3    C(177) =   9 \n",
      "i =   3 -->   8    A(  8) =   4    B(  8) =   0    C(  8) =   8 \n",
      "i =   4 --> 240    A(240) =   4    B(240) =   9    C(240) =  36 \n",
      "i =   5 --> 211    A(211) =   8    B(211) =  36    C(211) = 213 \n",
      "i =   6 -->  64    A( 64) = 213    B( 64) =   3    C( 64) = 216 \n",
      "i =   7 --> 233    A(233) =   0    B(233) =   0    C(233) =   0 \n",
      "\n",
      "\n",
      "--- Round 1 ---\n",
      "Round 1 = [GF(86, order=241), GF(68, order=241), GF(214, order=241)]\n",
      "TODO: [A], [B], [C]\n"
     ]
    }
   ],
   "source": [
    "random_b = [Fp.Random() for i in range(0, 9)]\n",
    "\n",
    "bA = galois.Poly(random_b[:2], field=Fp)\n",
    "bB = galois.Poly(random_b[2:4], field=Fp)\n",
    "bC = galois.Poly(random_b[4:6], field=Fp)\n",
    "\n",
    "_A = to_poly(roots, a, Fp)\n",
    "_B = to_poly(roots, b, Fp)\n",
    "_C = to_poly(roots, c, Fp)\n",
    "\n",
    "A = _A + bA*Zh\n",
    "B = _B + bB*Zh\n",
    "C = _C + bC*Zh\n",
    "\n",
    "# gate constraints polynomial\n",
    "# g(x) = a(x)*ql(x) + b(x)*qr(x) + a(x)*b(x)*qm(x) + qc(x) + c(x)*qo(x)\n",
    "G = A*QL + B*QR + A*B*QM + QC + C*QO + QPI\n",
    "\n",
    "print(\"--- Gate Constraints Polynomial ---\")\n",
    "print(f\"G = {G}\")\n",
    "for i in range(0, len(roots)):\n",
    "    print(f\"gate #{i} G({roots[i]}) = {G(roots[i])} --> {'OK' if G(roots[i]) == 0 else 'FAIL'}\")\n",
    "    assert G(roots[i]) == 0, f\"G({roots[i]}) != 0\"\n",
    "\n",
    "assert G % Zh == 0, f\"G(x) % Zh(x) != 0\"\n",
    "\n",
    "padding = 3\n",
    "for i in range(0, len(roots)):\n",
    "    s = f\"i = {i:{padding}} --> {roots[i]:{padding}} \"\n",
    "    s += f\"   A({roots[i]:{padding}}) = {A(roots[i]):{padding}} \"\n",
    "    s += f\"   B({roots[i]:{padding}}) = {B(roots[i]):{padding}} \"\n",
    "    s += f\"   C({roots[i]:{padding}}) = {C(roots[i]):{padding}} \"\n",
    "    print(s)\n",
    "\n",
    "round1 = [A(tau), B(tau), C(tau)]\n",
    "print(\"\\n\\n--- Round 1 ---\")\n",
    "print(f\"Round 1 = {round1}\")\n",
    "print(\"TODO: [A], [B], [C]\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Round 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "\n",
      "--- Accumulator Polynomial ---\n",
      "ACC(x) = 212x^7 + 214x^6 + 222x^5 + 225x^4 + 184x^3 + 61x^2 + 71x + 17\n",
      "bZ = 169x^2 + 232x + 21\n",
      "\n",
      "\n",
      "--- Z Polynomial ---\n",
      "Z(x) = 169x^10 + 232x^9 + 21x^8 + 212x^7 + 214x^6 + 222x^5 + 225x^4 + 184x^3 + 133x^2 + 80x + 237\n",
      "Z(1) = 1\n",
      "Z(30) = 10\n",
      "Z(177) = 52\n",
      "Z(8) = 2\n",
      "Z(240) = 69\n",
      "Z(211) = 119\n",
      "Z(64) = 123\n",
      "Z(233) = 1\n",
      "\n",
      "\n",
      "--- Round 2 ---\n",
      "Round 2 = [GF(22, order=241)]\n",
      "TODO: [Z]\n"
     ]
    }
   ],
   "source": [
    "import sha3\n",
    "\n",
    "def numbers_to_hash(numbers: [int], field) -> int:\n",
    "    \"\"\"Hash a number.\"\"\"\n",
    "    return field(int(sha3.keccak_256(bytes(numbers)).hexdigest(), 16) % field.order)\n",
    "\n",
    "# TODO: calculate beta, gamma from [A], [B], [C]\n",
    "beta = numbers_to_hash(round1 + [0], Fp)\n",
    "gamma = numbers_to_hash(round1 + [1], Fp)\n",
    "\n",
    "_F = (A + I1 * beta + gamma) * (B + I2 * beta + gamma) * (C + I3 * beta + gamma)\n",
    "_G = (A + S1 * beta + gamma) * (B + S2 * beta + gamma) * (C + S3 * beta + gamma)\n",
    "\n",
    "acc_eval = [Fp(1)]\n",
    "for i in range(0, n):\n",
    "    acc_eval.append(\n",
    "        acc_eval[-1] * (_F(roots[i]) / _G(roots[i]))\n",
    "    )\n",
    "assert acc_eval.pop() == Fp(1)\n",
    "ACC = galois.lagrange_poly(roots, Fp(acc_eval))\n",
    "print(\"\\n\\n--- Accumulator Polynomial ---\")\n",
    "print(f\"ACC(x) = {ACC}\")\n",
    "\n",
    "bZ = galois.Poly(random_b[6:9], field=Fp)\n",
    "print(f\"bZ = {bZ}\")\n",
    "Z = bZ * Zh + ACC\n",
    "\n",
    "print(\"\\n\\n--- Z Polynomial ---\")\n",
    "print(f\"Z(x) = {Z}\")\n",
    "\n",
    "for r in roots:\n",
    "    print(f\"Z({r}) = {Z(r)}\")\n",
    "\n",
    "assert Z(roots[0]) == 1\n",
    "assert Z(roots[-1]) == 1\n",
    "\n",
    "round2 = [Z(tau)]\n",
    "print(\"\\n\\n--- Round 2 ---\")\n",
    "print(f\"Round 2 = {round2}\")\n",
    "print(\"TODO: [Z]\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Round 3"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Z(  1) =   1 -> Zω(  1) =  10\n",
      "Z( 30) =  10 -> Zω( 30) =  52\n",
      "Z(177) =  52 -> Zω(177) =   2\n",
      "Z(  8) =   2 -> Zω(  8) =  69\n",
      "Z(240) =  69 -> Zω(240) = 119\n",
      "Z(211) = 119 -> Zω(211) = 123\n",
      "Z( 64) = 123 -> Zω( 64) =   1\n",
      "Z(233) =   1 -> Zω(233) =   1\n",
      "\n",
      "\n",
      "--- Zω Polynomial ---\n",
      "Z(ωx) = 29x^10 + 212x^9 + 21x^8 + 232x^7 + 200x^6 + 88x^5 + 16x^4 + 26x^3 + 164x^2 + 231x + 237\n",
      "\n",
      "\n",
      "--- L1 Polynomial ---\n",
      "L1(x) = 211x^7 + 211x^6 + 211x^5 + 211x^4 + 211x^3 + 211x^2 + 211x + 211\n",
      "L1(1) = 1\n",
      "L1(30) = 0\n",
      "L1(177) = 0\n",
      "L1(8) = 0\n",
      "L1(240) = 0\n",
      "L1(211) = 0\n",
      "L1(64) = 0\n",
      "L1(233) = 0\n",
      "\n",
      "\n",
      "--- T Polynomial ---\n",
      "T(x) = 13x^29 + 226x^28 + 59x^27 + 53x^26 + 13x^25 + 207x^24 + 149x^23 + 63x^22 + 228x^21 + 180x^20 + 103x^19 + 153x^18 + 103x^17 + 112x^16 + 79x^15 + 239x^14 + 208x^13 + 161x^12 + 227x^11 + 198x^10 + 239x^9 + 115x^8 + 206x^7 + 194x^6 + 35x^5 + 189x^4 + 169x^3 + 23x^2 + 214x + 175\n",
      "\n",
      "\n",
      "--- T' ---\n",
      "Tl(x) = 239x^9 + 115x^8 + 206x^7 + 194x^6 + 35x^5 + 189x^4 + 169x^3 + 23x^2 + 214x + 175\n",
      "Tm(x) = 103x^9 + 153x^8 + 103x^7 + 112x^6 + 79x^5 + 239x^4 + 208x^3 + 161x^2 + 227x + 198\n",
      "Th(x) = 13x^9 + 226x^8 + 59x^7 + 53x^6 + 13x^5 + 207x^4 + 149x^3 + 63x^2 + 228x + 180\n",
      "\n",
      "\n",
      "--- Round 3 ---\n",
      "Round 3 = [GF(133, order=241), GF(198, order=241), GF(130, order=241)]\n",
      "TODO: [Tl], [Tm], [Th]\n"
     ]
    }
   ],
   "source": [
    "def shift_poly(poly: galois.Poly, omega: Fp):\n",
    "    coeffs = poly.coeffs[::-1]\n",
    "    coeffs = [c * omega**i for i, c in enumerate(coeffs)]\n",
    "    return galois.Poly(coeffs[::-1], field=poly.field)\n",
    "\n",
    "alpha = numbers_to_hash(round1 + round2, Fp)\n",
    "\n",
    "Zomega = shift_poly(Z, omega=omega)\n",
    "for r in roots:\n",
    "    print(f\"Z({r:3}) = {Z(r):3} -> Zω({r:3}) = {Zomega(r):3}\")\n",
    "\n",
    "print(\"\\n\\n--- Zω Polynomial ---\")\n",
    "print(f\"Z(ωx) = {Zomega}\")\n",
    "\n",
    "L1 = galois.lagrange_poly(roots, Fp([1] + [Fp(0)] * (n - 1)))\n",
    "\n",
    "print(\"\\n\\n--- L1 Polynomial ---\")\n",
    "print(f\"L1(x) = {L1}\")\n",
    "for i, r in enumerate(roots):\n",
    "    print(f\"L1({r}) = {L1(r)}\")\n",
    "    assert L1(r) == (Fp(1) if i == 0 else Fp(0))\n",
    "\n",
    "T0 = G\n",
    "assert T0 % Zh == 0, f\"T0(x) % Zh(x) != 0\"\n",
    "\n",
    "T1 = (_F * Z - _G * Zomega) * alpha\n",
    "assert T1 % Zh == 0, f\"T1(x) % Zh(x) != 0\"\n",
    "\n",
    "T2 = (Z - galois.Poly([1], field=Fp)) * L1 * alpha**2\n",
    "assert T2 % Zh == 0, f\"T2(x) % Zh(x) != 0\"\n",
    "\n",
    "T = (T0 + T1 + T2)\n",
    "assert T % Zh == 0, f\"T(x) % Zh(x) != 0\"\n",
    "\n",
    "for r in roots:\n",
    "    assert T(r) == 0, f\"T({r}) != 0\"\n",
    "\n",
    "T = T // Zh\n",
    "\n",
    "print(\"\\n\\n--- T Polynomial ---\")\n",
    "print(f\"T(x) = {T}\")\n",
    "\n",
    "t_coeffs = T.coeffs[::-1]\n",
    "\n",
    "Tl = galois.Poly(t_coeffs[:n+2][::-1], field=Fp)\n",
    "Tm = galois.Poly(t_coeffs[n+2:2*(n+2)][::-1], field=Fp)\n",
    "Th = galois.Poly(t_coeffs[2*(n+2):][::-1], field=Fp)\n",
    "\n",
    "X_n = galois.Poly.Degrees([n+2, 0], coeffs=[1, 0], field=Fp)\n",
    "X_2n = galois.Poly.Degrees([2*(n+2), 0], coeffs=[1, 0], field=Fp)\n",
    "# make sure that T was split correctly\n",
    "# T = TL + X^n * TM + X^2n * TH\n",
    "assert T == (Tl + X_n * Tm + X_2n * Th)\n",
    "assert T.degree == 3 * n + 5\n",
    "\n",
    "print(\"\\n\\n--- T' ---\")\n",
    "print(f\"Tl(x) = {Tl}\")\n",
    "print(f\"Tm(x) = {Tm}\")\n",
    "print(f\"Th(x) = {Th}\")\n",
    "\n",
    "round3 = [Tl(tau), Tm(tau), Th(tau)]\n",
    "print(\"\\n\\n--- Round 3 ---\")\n",
    "print(f\"Round 3 = {round3}\")\n",
    "print(\"TODO: [Tl], [Tm], [Th]\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Round 4"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "\n",
      "--- R ---\n",
      "R(x) = 142x^10 + 78x^9 + 59x^8 + 152x^7 + 117x^6 + 202x^5 + 108x^4 + 130x^3 + 144x^2 + 118x + 43\n",
      "\n",
      "\n",
      "--- Round 4 ---\n",
      "Round 4 = [GF(5, order=241), GF(209, order=241), GF(75, order=241), GF(140, order=241), GF(79, order=241), GF(202, order=241), GF(45, order=241), GF(33, order=241)]\n"
     ]
    }
   ],
   "source": [
    "zeta = numbers_to_hash(round1 + round2 + round3, Fp)\n",
    "\n",
    "a_zeta = A(zeta)\n",
    "b_zeta = B(zeta)\n",
    "c_zeta = C(zeta)\n",
    "s1_zeta = S1(zeta)\n",
    "s2_zeta = S2(zeta)\n",
    "t_zeta = T(zeta)\n",
    "z_omega_zeta = Zomega(zeta)\n",
    "\n",
    "R = (QM * a_zeta * b_zeta +\n",
    "    QL * a_zeta +\n",
    "    QR * b_zeta +\n",
    "    QO * c_zeta +\n",
    "    QC)\n",
    "R += (Z * \n",
    "    (a_zeta + beta * zeta + gamma) *\n",
    "    (b_zeta + beta * zeta * k1 + gamma) *\n",
    "    (c_zeta + beta * zeta * k2 + gamma) * alpha)\n",
    "R -= (S3 *\n",
    "    (a_zeta + beta * s1_zeta + gamma) *\n",
    "    (b_zeta + beta * s2_zeta + gamma) * alpha * beta * z_omega_zeta)\n",
    "R += Z * L1(zeta) * alpha**2\n",
    "\n",
    "print(\"\\n\\n--- R ---\")\n",
    "print(f\"R(x) = {R}\")\n",
    "\n",
    "r_zeta = R(zeta)\n",
    "\n",
    "round4 = [a_zeta, b_zeta, c_zeta, s1_zeta, s2_zeta, t_zeta, z_omega_zeta, r_zeta]\n",
    "print(\"\\n\\n--- Round 4 ---\")\n",
    "print(f\"Round 4 = {round4}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Round 5"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "X - zeta = x + 158\n",
      "X - ω*zeta = x + 161\n",
      "\n",
      "\n",
      "--- Round 5 ---\n",
      "Round 5 = [GF(100, order=241), GF(60, order=241)]\n",
      "TODO: [Wzeta], [Womega_zeta]\n"
     ]
    }
   ],
   "source": [
    "v = numbers_to_hash(round1 + round2 + round3 + round4, Fp)\n",
    "\n",
    "X_minus_zeta = galois.Poly([1, -zeta], field=Fp)\n",
    "print(f\"X - zeta = {X_minus_zeta}\")\n",
    "\n",
    "Wzeta = (Tl + zeta**(n+2) * Tm + zeta**(2*(n+2)) * Th - t_zeta) + \\\n",
    "        (R - r_zeta) * v + \\\n",
    "        (A - a_zeta) * v**2 + \\\n",
    "        (B - b_zeta) * v**3 + \\\n",
    "        (C - c_zeta) * v**4 + \\\n",
    "        (S1 - s1_zeta) * v**5 + \\\n",
    "        (S2 - s2_zeta) * v**6\n",
    "\n",
    "assert Wzeta % X_minus_zeta == 0, f\"Wzeta(x) % X - zeta != 0\"\n",
    "Wzeta = Wzeta // X_minus_zeta\n",
    "\n",
    "X_minus_omega_zeta = galois.Poly([1, -(omega*zeta)], field=Fp)\n",
    "print(f\"X - ω*zeta = {X_minus_omega_zeta}\")\n",
    "\n",
    "Womega_zeta = (Z - z_omega_zeta)\n",
    "assert Womega_zeta % X_minus_omega_zeta == 0, f\"Womega_zeta(x) % X - ω*zeta != 0\"\n",
    "Womega_zeta = Womega_zeta // X_minus_omega_zeta\n",
    "\n",
    "round5 = [Wzeta(tau), Womega_zeta(tau)]\n",
    "print(\"\\n\\n--- Round 5 ---\")\n",
    "print(f\"Round 5 = {round5}\")\n",
    "print(\"TODO: [Wzeta], [Womega_zeta]\")\n",
    "\n",
    "u = numbers_to_hash(round1 + round2 + round3 + round4 + round5, Fp)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Verifier"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [],
   "source": [
    "qm_exp = QM(tau)\n",
    "ql_exp = QL(tau)\n",
    "qr_exp = QR(tau)\n",
    "qo_exp = QO(tau)\n",
    "qc_exp = QC(tau)\n",
    "qpi_exp = QPI(tau)\n",
    "z_exp = Z(tau)\n",
    "s1_exp = S1(tau)\n",
    "s2_exp = S2(tau)\n",
    "s3_exp = S3(tau)\n",
    "tl_exp = Tl(tau)\n",
    "tm_exp = Tm(tau)\n",
    "th_exp = Th(tau)\n",
    "\n",
    "a_exp = A(tau)\n",
    "b_exp = B(tau)\n",
    "c_exp = C(tau)\n",
    "\n",
    "w_zeta_exp = Wzeta(tau)\n",
    "w_omega_zeta_exp = Womega_zeta(tau)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [],
   "source": [
    "Zh_z = Zh(zeta)\n",
    "L1_z = L1(zeta)\n",
    "t = r_zeta - ((a_zeta + beta * s1_zeta + gamma) * (b_zeta + beta * s2_zeta + gamma) * (c_zeta + gamma) * z_omega_zeta) * alpha - L1_z * alpha**2\n",
    "t /= Zh_z\n",
    "\n",
    "assert t == t_zeta"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [],
   "source": [
    "D_exp = (qm_exp * a_zeta * b_zeta * v +\n",
    "        ql_exp * a_zeta * v +\n",
    "        qr_exp * b_zeta * v +\n",
    "        qo_exp * c_zeta * v +\n",
    "        qc_exp * v)\n",
    "\n",
    "D_exp += (z_exp * (\n",
    "        (a_zeta + beta * zeta + gamma) *\n",
    "        (b_zeta + beta * zeta * k1 + gamma) *\n",
    "        (c_zeta + beta * zeta * k2 + gamma) * alpha * v\n",
    "        + L1_z * alpha**2 * v + u))\n",
    "\n",
    "D_exp -= (s3_exp *\n",
    "        (a_zeta + beta * s1_zeta + gamma) *\n",
    "        (b_zeta + beta * s2_zeta + gamma) * \n",
    "        alpha * beta * z_omega_zeta * v)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [],
   "source": [
    "F_exp = (tl_exp +\n",
    "        tm_exp * zeta**(n+2) +\n",
    "        th_exp * zeta**(2*(n+2)) +\n",
    "        D_exp + \n",
    "        a_exp * v**2 +\n",
    "        b_exp * v**3 +\n",
    "        c_exp * v**4 +\n",
    "        s1_exp * v**5 +\n",
    "        s2_exp * v**6)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [],
   "source": [
    "E_exp = (t_zeta +\n",
    "        v * r_zeta +\n",
    "        v**2 * a_zeta +\n",
    "        v**3 * b_zeta +\n",
    "        v**4 * c_zeta +\n",
    "        v**5 * s1_zeta +\n",
    "        v**6 * s2_zeta +\n",
    "        u * z_omega_zeta)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "\n",
      "--- e1, e2 ---\n",
      "e1 = 146\n",
      "e2 = 146\n"
     ]
    }
   ],
   "source": [
    "e1 = w_zeta_exp + w_omega_zeta_exp * u\n",
    "e2 = (w_zeta_exp * zeta + w_omega_zeta_exp * u * zeta * omega +\n",
    "    F_exp + (E_exp * Fp(p-1)))\n",
    "\n",
    "print(\"\\n\\n--- e1, e2 ---\")\n",
    "print(f\"e1 = {e1 * tau}\")\n",
    "print(f\"e2 = {e2}\")\n",
    "assert e1 * tau == e2"
   ]
  }
 ],
 "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.11.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}