R1CSToQAP.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "106c2d76-7769-4260-b7ef-630e81739e92",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'1.26.0'"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "import numpy as np\n",
    "np.__version__"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "bfa1d4bd-8a0f-4009-aa74-56765f770c60",
   "metadata": {},
   "source": [
    "**If you use numpy version 2.0, you may run into issues with overflow.** Consider downgrading to 1.26.0."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "8fe9172d-eb58-4724-809d-605132e956f7",
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "\n",
    "# 1, out, x, y, v1, v2, v3\n",
    "L = np.array([\n",
    "    [0, 0, 1, 0, 0, 0, 0],\n",
    "    [0, 0, 0, 0, 1, 0, 0],\n",
    "    [0, 0, 0, -5, 0, 0, 0],\n",
    "    [0, 0, 0, 0, 0, 0, 1],\n",
    "])\n",
    "\n",
    "R = np.array([\n",
    "    [0, 0, 1, 0, 0, 0, 0],\n",
    "    [0, 0, 0, 0, 1, 0, 0],\n",
    "    [0, 0, 0, 1, 0, 0, 0],\n",
    "    [0, 0, 0, 0, 1, 0, 0],\n",
    "])\n",
    "\n",
    "O = np.array([\n",
    "    [0, 0, 0, 0, 1, 0, 0],\n",
    "    [0, 0, 0, 0, 0, 1, 0],\n",
    "    [0, 0, 0, 0, 0, 0, 1],\n",
    "    [0, 1, 0, 0, 0, -1, 0],\n",
    "])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "fb28b860-50d0-4b1d-ad0f-b9a0613a3fd7",
   "metadata": {},
   "outputs": [],
   "source": [
    "x = 4\n",
    "y = -2\n",
    "v1 = x * x\n",
    "v2 = v1 * v1        # x^4\n",
    "v3 = -5*y * y\n",
    "z = v3*v1 + v2    # -5y^2 * x^2\n",
    "\n",
    "# witness\n",
    "a = np.array([1, z, x, y, v1, v2, v3])\n",
    "\n",
    "assert all(np.equal(np.matmul(L, a) * np.matmul(R, a), np.matmul(O, a))), \"not equal\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "18ebaf66-e9d2-4759-aa2b-d783c3fd4806",
   "metadata": {},
   "outputs": [],
   "source": [
    "from py_ecc.bn128 import curve_order\n",
    "\n",
    "import galois\n",
    "\n",
    "# setting primitive_element=5 prevents galois from having a very slow startup\n",
    "# this only works for the bn128 curve\n",
    "GF = galois.GF(curve_order, primitive_element=5, verify=False)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "04ee4f04-f78e-4244-a348-36a628e92869",
   "metadata": {},
   "source": [
    "## Convert all the negative numbers to their congruent equivalences"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "cf04077f-558c-4e86-884e-89e47eb0aeb3",
   "metadata": {},
   "outputs": [],
   "source": [
    "L = (L + curve_order) % curve_order\n",
    "R = (R + curve_order) % curve_order\n",
    "O = (O + curve_order) % curve_order"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "76d56655-7404-4f57-b4ec-b48efa83852e",
   "metadata": {},
   "source": [
    "## Test our arithmetic circuit again"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "b51a57b2-19de-4424-a9d4-343f94aeb530",
   "metadata": {},
   "outputs": [],
   "source": [
    "L_galois = GF(L)\n",
    "R_galois = GF(R)\n",
    "O_galois = GF(O)\n",
    "\n",
    "x = GF(4)\n",
    "y = GF(-2 + curve_order)\n",
    "v1 = x * x\n",
    "v2 = v1 * v1         # x^4\n",
    "v3 = GF(-5 + curve_order)*y * y\n",
    "out = v3*v1 + v2    # -5y^2 * x^2\n",
    "\n",
    "witness = GF(np.array([1, out, x, y, v1, v2, v3]))\n",
    "\n",
    "assert all(np.equal(np.matmul(L_galois, witness) * np.matmul(R_galois, witness), np.matmul(O_galois, witness))), \"not equal\""
   ]
  },
  {
   "cell_type": "markdown",
   "id": "307c63ca-e057-4db0-8f78-10c63ab60c5d",
   "metadata": {},
   "source": [
    "## Lagrange interpolate the columns"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "2b91585d-a754-4545-833d-d94c6d9fa3e6",
   "metadata": {},
   "outputs": [],
   "source": [
    "def interpolate_column(col):\n",
    "    xs = GF(np.array([1,2,3,4]))\n",
    "    return galois.lagrange_poly(xs, col)\n",
    "\n",
    "# axis 0 is the columns.\n",
    "# apply_along_axis is the same as doing a for loop over the columns and collecting the results in an array\n",
    "U_polys = np.apply_along_axis(interpolate_column, 0, L_galois)\n",
    "V_polys = np.apply_along_axis(interpolate_column, 0, R_galois)\n",
    "W_polys = np.apply_along_axis(interpolate_column, 0, O_galois)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "e4652133-17dc-4c4c-9cc3-7979150e43e7",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[Poly(0, GF(21888242871839275222246405745257275088548364400416034343698204186575808495617))\n",
      " Poly(0, GF(21888242871839275222246405745257275088548364400416034343698204186575808495617))]\n",
      "[Poly(0, GF(21888242871839275222246405745257275088548364400416034343698204186575808495617))\n",
      " Poly(0, GF(21888242871839275222246405745257275088548364400416034343698204186575808495617))]\n",
      "[Poly(0, GF(21888242871839275222246405745257275088548364400416034343698204186575808495617))]\n"
     ]
    }
   ],
   "source": [
    "print(U_polys[:2])\n",
    "print(V_polys[:2])\n",
    "print(W_polys[:1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "6c38a714-01b5-4d8f-a31b-a12c28bb6d67",
   "metadata": {},
   "outputs": [],
   "source": [
    "from functools import reduce\n",
    "\n",
    "def inner_product_polynomials_with_witness(polys, witness):\n",
    "    mul_ = lambda x, y: x * y\n",
    "    sum_ = lambda x, y: x + y\n",
    "    return reduce(sum_, map(mul_, polys, witness))\n",
    "\n",
    "u = inner_product_polynomials_with_witness(U_polys, witness)\n",
    "v = inner_product_polynomials_with_witness(V_polys, witness)\n",
    "w = inner_product_polynomials_with_witness(W_polys, witness)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f40ca143-af1e-48b3-8fea-2fbfbc7f021f",
   "metadata": {},
   "source": [
    "## Compute $h(x)$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "id": "26f66e3b-7523-4ae6-bb5e-72985f93344c",
   "metadata": {},
   "outputs": [],
   "source": [
    "# t = (x - 1)(x - 2)(x - 3)(x - 4)\n",
    "t = galois.Poly([1, curve_order - 1], field = GF) * galois.Poly([1, curve_order - 2], field = GF) * galois.Poly([1, curve_order - 3], field = GF) * galois.Poly([1, curve_order - 4], field = GF)\n",
    "\n",
    "h = (u * v - w) // t"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8d0fcbac-01fb-4d4d-91ef-07316b129762",
   "metadata": {},
   "source": [
    "## Test that the QAP is balanced"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "id": "39d84b90-4885-4a3e-abca-a4fc7979b67d",
   "metadata": {},
   "outputs": [],
   "source": [
    "assert u * v == w + h * t, \"division has a remainder\""
   ]
  }
 ],
 "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.11.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}