Groth16_implementation.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from functools import reduce\n",
    "from py_ecc.bn128 import G1, G2, bn128_curve, curve_order, multiply, neg, pairing, final_exponentiate\n",
    "from sage.all import *\n",
    "\n",
    "F = GF(curve_order)\n",
    "F_x.<x> = F[] # polynomial over finite field\n",
    "\n",
    "A = Matrix(F, [\n",
    "    [0,0,1,0,0,0,0,0],\n",
    "    [0,0,0,0,1,0,0,0],\n",
    "    [0,0,0,0,0,0,1,0]\n",
    "])\n",
    "\n",
    "B = Matrix(F, [\n",
    "    [0,0,0,1,0,0,0,0],\n",
    "    [0,0,0,0,0,1,0,0],\n",
    "    [0,0,0,0,0,0,0,1]\n",
    "])\n",
    "\n",
    "C = Matrix(F,[\n",
    "    [0,0,0,0,0,0,1,0],\n",
    "    [0,0,0,0,0,0,0,1],\n",
    "    [0,1,0,0,0,0,0,0]\n",
    "])\n",
    "\n",
    "x = F.random_element()\n",
    "y = F.random_element()\n",
    "z = F.random_element()\n",
    "u = F.random_element()\n",
    "l = 2 # public variables index\n",
    "\n",
    "\n",
    "v1 = x * y\n",
    "v2 = z * u\n",
    "out = v1 * v2\n",
    "\n",
    "# create the witness vector\n",
    "witness = vector(F, [1, out, x, y, z, u, v1, v2])\n",
    "\n",
    "assert Matrix(C * witness) == Matrix(A * witness).elementwise_product(Matrix(B * witness))\n",
    "\n",
    "def bn_add(A, B):\n",
    "    return bn128_curve.add(A, B)\n",
    "\n",
    "def trusted_setup(n, m, t_x, U_polys, V_polys, W_polys):\n",
    "    encrypted_G1 = list()\n",
    "    encrypted_G2 = list()\n",
    "    t_x_enc = list()\n",
    "\n",
    "    tau = F.random_element()\n",
    "    pow_of_tau = 1  # tau ** 0\n",
    "\n",
    "    alpha = F.random_element()\n",
    "    beta = F.random_element()\n",
    "    gamma = F.random_element()\n",
    "    delta = F.random_element()\n",
    "    gamma_inv = inverse_mod(gamma, curve_order)\n",
    "    delta_inv = inverse_mod(delta, curve_order)\n",
    "\n",
    "    Alpha1 = multiply(G1, int(alpha))\n",
    "    Beta1 = multiply(G1, int(beta))\n",
    "    Beta2 = multiply(G2, int(beta))\n",
    "    \n",
    "    Gamma2 = multiply(G2, int(gamma))\n",
    "    Delta1 = multiply(G1, int(delta))\n",
    "    Delta2 = multiply(G2, int(delta))\n",
    "    t_x_eval = t_x(tau)\n",
    "\n",
    "    pow_of_tau_C_private = list()\n",
    "    pow_of_tau_C_public = list()\n",
    "\n",
    "    for i in range(0, n):\n",
    "        encrypted_G1.append(multiply(G1, int(pow_of_tau)))\n",
    "        encrypted_G2.append(multiply(G2, int(pow_of_tau)))\n",
    "\n",
    "        if i <= n-2:\n",
    "            t_x_enc.append(multiply(G1, int(pow_of_tau * t_x_eval * delta_inv)))\n",
    "\n",
    "        pow_of_tau = pow_of_tau*tau\n",
    "\n",
    "    U_polys_enc = encrypt_polynomials(U_polys, encrypted_G1)\n",
    "    V_polys_enc = encrypt_polynomials(V_polys, encrypted_G1)\n",
    "    W_polys_enc = encrypt_polynomials(W_polys, encrypted_G1)\n",
    "\n",
    "\n",
    "    for i in range(0, l):\n",
    "        pow_of_tau_C_public.append(multiply(bn_add(bn_add(multiply(U_polys_enc[i], int(beta)), multiply(V_polys_enc[i], int(alpha))), W_polys_enc[i]), gamma_inv))\n",
    "\n",
    "    for i in range(l, m):\n",
    "        pow_of_tau_C_private.append(multiply(bn_add(bn_add(multiply(U_polys_enc[i], int(beta)), multiply(V_polys_enc[i], int(alpha))), W_polys_enc[i]), delta_inv))\n",
    "\n",
    "\n",
    "    return encrypted_G1, encrypted_G2, t_x_enc, Alpha1, Beta1, Beta2, Gamma2, Delta1, Delta2, pow_of_tau_C_public, pow_of_tau_C_private\n",
    "\n",
    "def generate_target_polynomial(n):\n",
    "    # Create a polynomial of the form (x - 1)(x - 2)(x - 3)...(x - n)\n",
    "    x = var('x')\n",
    "    res = F_x(prod([(x - i) for i in range(1, n+1)]))\n",
    "    for i in range(1, n+1):\n",
    "        assert res(i) == 0, \"Invalid target polynom\"\n",
    "    return res\n",
    "\n",
    "def interpolate_polynomials(matrix):\n",
    "    result = list()\n",
    "    for column in matrix.columns():\n",
    "        polynomial = F_x.lagrange_polynomial([(index+1, values) for index, values in enumerate(column)])\n",
    "        result.append(polynomial)\n",
    "    return result\n",
    "\n",
    "def inner_product_polynomials_with_witness(polys, witness):\n",
    "    def mul(x, y): return x * y\n",
    "    def sum(x, y): return x + y\n",
    "    return reduce(sum, map(mul, polys, witness))\n",
    "\n",
    "def inner_product_enc_polynomials_with_witness(polys, witness):\n",
    "    def mul(x, y): return multiply(x, int(y))\n",
    "    return reduce(bn_add, map(mul, polys, witness))\n",
    "\n",
    "def encrypt_polynomials(polynomials, encrypted_points):\n",
    "    encrypted_polynomials = [None] * len(polynomials)\n",
    "    for i, poly in enumerate(polynomials):\n",
    "        if poly != 0:\n",
    "            for j, coeff in enumerate(poly.coefficients(sparse=False)):\n",
    "                encrypted_polynomials[i] = bn_add(encrypted_polynomials[i], multiply(encrypted_points[j], int(coeff)))\n",
    "    return encrypted_polynomials\n",
    "\n",
    "def encrypt_hx_tx(h_x, t_x_enc):\n",
    "    h_x_enc = list()\n",
    "    for index, coeff in enumerate(h_x.coefficients(sparse=False)):\n",
    "        h_x_enc.append(multiply(t_x_enc[index], int(coeff)))\n",
    "    return reduce(bn_add, h_x_enc)\n",
    "\n",
    "t_x = generate_target_polynomial(len(A.rows()))\n",
    "U_polys = interpolate_polynomials(A)\n",
    "V_polys = interpolate_polynomials(B)\n",
    "W_polys = interpolate_polynomials(C)\n",
    "\n",
    "(p_tau_G1, p_tau_G2, t_x_enc, Alpha1, Beta1, Beta2, Gamma2, Delta1, Delta2, pow_of_tau_C_public, pow_of_tau_C_private) = \\\n",
    "    trusted_setup(len(A.rows()), len(A.columns()), t_x, U_polys, V_polys, W_polys)\n",
    "\n",
    "poly1 = inner_product_polynomials_with_witness(U_polys, witness)\n",
    "poly2 = inner_product_polynomials_with_witness(V_polys, witness)\n",
    "poly3 = inner_product_polynomials_with_witness(W_polys, witness)  \n",
    "\n",
    "h_x, remainder = ((poly1 * poly2) - poly3).quo_rem(t_x)\n",
    "assert remainder == 0, \"Division has a remainder\"\n",
    "\n",
    "hx_tx_enc1 = encrypt_hx_tx(h_x, t_x_enc)\n",
    "\n",
    "A1_inner_prod = inner_product_enc_polynomials_with_witness(encrypt_polynomials(U_polys, p_tau_G1), witness)\n",
    "B1_inner_prod = inner_product_enc_polynomials_with_witness(encrypt_polynomials(V_polys, p_tau_G1), witness)\n",
    "B2_inner_prod = inner_product_enc_polynomials_with_witness(encrypt_polynomials(V_polys, p_tau_G2), witness)\n",
    "C1_inner_prod_public = inner_product_enc_polynomials_with_witness(pow_of_tau_C_public, witness[:l])\n",
    "C1_inner_prod_private = inner_product_enc_polynomials_with_witness(pow_of_tau_C_private, witness[l:])\n",
    "\n",
    "r = F.random_element()\n",
    "s = F.random_element()\n",
    "\n",
    "rDelta1 = multiply(Delta1, int(r))\n",
    "sDelta1 = multiply(Delta1, int(s))\n",
    "sDelta2 = multiply(Delta2, int(s))\n",
    "\n",
    "A1 = bn_add(bn_add(A1_inner_prod, Alpha1), rDelta1)\n",
    "B1 = bn_add(bn_add(B1_inner_prod, Beta1), sDelta1)\n",
    "B2 = bn_add(bn_add(B2_inner_prod, Beta2), sDelta2)\n",
    "\n",
    "sA1 = multiply(A1, int(s))\n",
    "rB1 = multiply(B1, int(r))\n",
    "rsDelta1 = multiply(Delta1, int(r*s))\n",
    "C1 = bn_add(bn_add(hx_tx_enc1, C1_inner_prod_private), bn_add(sA1, bn_add(rB1, neg(rsDelta1))))\n",
    "\n",
    "assert final_exponentiate(pairing(B2, A1) ) == final_exponentiate(\n",
    "                    pairing(Beta2, Alpha1) * \\\n",
    "                    pairing(Gamma2, C1_inner_prod_public) * \\\n",
    "                    pairing(Delta2, C1)\\\n",
    "                ), \"Equality fail\"\n",
    "\n",
    "print(\"Success\")"
   ]
  }
 ],
 "metadata": {
  "language_info": {
   "name": "python"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}