sumcheck.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "1d4d1a23-2422-49ed-9ea1-b84a4d6e71cd",
   "metadata": {
    "tags": []
   },
   "source": [
    "# The Sumcheck Protocol"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "c6211495-359d-4a07-a2d1-a9ea2e59a64e",
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List, Tuple, Union\n",
    "from functools import reduce\n",
    "from random import randint\n",
    "from math import log2\n",
    "\n",
    "\n",
    "class FFE:\n",
    "    \n",
    "    element: int\n",
    "    \n",
    "    modulus: int\n",
    "    \n",
    "    def __init__(self, element: int, modulus: int):\n",
    "        self.element = element % modulus\n",
    "        self.modulus = modulus\n",
    "        \n",
    "    def __add__(self, rhs: 'FFE'):\n",
    "        if self.modulus != rhs.modulus:\n",
    "            raise Exception(\"Modulus Mismatch\")\n",
    "        element = (self.element + rhs.element) % self.modulus\n",
    "        return FFE(element, self.modulus)\n",
    "        \n",
    "    def __sub__(self, rhs: 'FFE'):\n",
    "        if self.modulus != rhs.modulus:\n",
    "            raise Exception(\"Modulus Mismatch\")\n",
    "        element = (self.element - rhs.element) % self.modulus\n",
    "        return FFE(element, self.modulus)\n",
    "    \n",
    "    def __mul__(self, rhs: 'FFE'):\n",
    "        if self.modulus != rhs.modulus:\n",
    "            raise Exception(\"Modulus Mismatch\")\n",
    "        element = (self.element * rhs.element) % self.modulus\n",
    "        return FFE(element, self.modulus)\n",
    "    \n",
    "    def __eq__(self, rhs: 'FFE'):\n",
    "        return (self.element == rhs.element) and (self.modulus == rhs.modulus)\n",
    "    \n",
    "    def __str__(self):\n",
    "        return f\"FFE(element: {self.element}, modulus: {self.modulus})\"\n",
    "    \n",
    "    def __repr__(self):\n",
    "        return f\"FFE(element: {self.element}, modulus: {self.modulus})\"\n",
    "    \n",
    "    \n",
    "RANDOM_NUM_MAX = 1_000_000_000\n",
    "\n",
    "class FF:\n",
    "    \n",
    "    modulus: int\n",
    "    \n",
    "    def __init__(self, modulus: int):\n",
    "        self.modulus = modulus\n",
    "        \n",
    "    def new(self, element: int) -> FFE:\n",
    "        return FFE(element, self.modulus)\n",
    "    \n",
    "    def zero(self) -> FFE:\n",
    "        return self.new(0)\n",
    "    \n",
    "    def one(self) -> FFE:\n",
    "        return self.new(1)\n",
    "    \n",
    "    def random_value(self) -> FFE:\n",
    "        return FFE(randint(0, RANDOM_NUM_MAX), self.modulus)\n",
    "        \n",
    "\n",
    "class Linear_Polynomial:\n",
    "    \n",
    "    evaluations: List[FFE]\n",
    "    \n",
    "    num_of_vars = 1\n",
    "    \n",
    "    ff: FF\n",
    "    \n",
    "    def __init__(self, ff: FF, evaluations: List[FFE]):\n",
    "        if len(evaluations) != 2:\n",
    "            raise Exception(\"Invalid evaluations\")\n",
    "        self.evaluations = evaluations\n",
    "        self.ff = ff\n",
    "        \n",
    "    def evaluate(self, x: FFE) -> FFE:\n",
    "        evaluations = self.evaluations.copy()\n",
    "        eval_1 = evaluations[0]\n",
    "        eval_2 = evaluations[1]\n",
    "        return (eval_1 - (eval_1 * x)) + (eval_2 * x)\n",
    "    \n",
    "    def __str__(self):\n",
    "        return f\"Linear Polynomial({self.evaluations})\"\n",
    "    \n",
    "    def __repr__(self):\n",
    "        return f\"Linear Polynomial({self.evaluations})\"\n",
    "    \n",
    "    def __add__(self, rhs: 'Linear_Polynomial'):\n",
    "        if (self.num_of_vars != rhs.num_of_vars):\n",
    "            raise Exception(\"Invalid Operation\")\n",
    "        new_evals = [(x + y) for (x, y) in zip(self.evaluations, rhs.evaluations)]\n",
    "        new_poly = Linear_Polynomial(self.ff, new_evals)\n",
    "        return new_poly\n",
    "\n",
    "    \n",
    "class Multilinear_Polynomial:\n",
    "    \n",
    "    evaluations: List[FFE]\n",
    "    \n",
    "    num_of_vars: int\n",
    "        \n",
    "    ff: FF\n",
    "    \n",
    "    def __init__(self, ff: FF, evaluations: List[FFE], num_of_vars: int):\n",
    "        self.ff = ff\n",
    "        if num_of_vars < 2:\n",
    "            raise Exception(\"Invalid number of variables\")\n",
    "        num_of_evaluation_points = 2 ** num_of_vars\n",
    "        length_of_evaluation_points = len(evaluations)\n",
    "        if length_of_evaluation_points == num_of_evaluation_points:\n",
    "            self.num_of_vars = num_of_vars\n",
    "            self.evaluations = evaluations\n",
    "        elif length_of_evaluation_points < num_of_evaluation_points:\n",
    "            padding = [ff.zero() for _ in range(num_of_evaluation_points - length_of_evaluation_points)]\n",
    "            evaluations = evaluations + padding\n",
    "            self.evaluations = evaluations\n",
    "            self.num_of_vars = num_of_vars\n",
    "        else:\n",
    "            self.evaluations = evaluations[:num_of_evaluation_points]\n",
    "            self.num_of_vars = num_of_vars\n",
    "            \n",
    "    def __str__(self):\n",
    "        return f\"Multilinear_Polynomial({self.evaluations})\"\n",
    "    \n",
    "    def __repr__(self):\n",
    "        return f\"Multilinear_Polynomial({self.evaluations})\"\n",
    "    \n",
    "    def __add__(self, rhs: 'Multilinear_Polynomial'):\n",
    "        if (self.ff.modulus != rhs.ff.modulus) or (self.num_of_vars != rhs.num_of_vars):\n",
    "            raise Exception(\"Invalid Operation\")\n",
    "        new_evals = [(x + y) for (x, y) in zip(self.evaluations, rhs.evaluations)]\n",
    "        new_poly = Multilinear_Polynomial(self.ff, new_evals, self.num_of_vars)\n",
    "        return new_poly\n",
    "    \n",
    "    def __mul__(self, rhs: 'Multilinear_Polynomial'):\n",
    "        if (self.ff.modulus != rhs.ff.modulus) or (self.num_of_vars != rhs.num_of_vars):\n",
    "            raise Exception(\"Invalid Operation\")\n",
    "        new_evals = []\n",
    "        for x in self.evaluations:\n",
    "            for y in rhs.evaluations:\n",
    "                new_evals.append(x * y)\n",
    "        new_poly = Multilinear_Polynomial(self.ff, new_evals, self.num_of_vars ** 2)\n",
    "        return new_poly\n",
    "    \n",
    "    @staticmethod\n",
    "    def get_pairing_index(var_index: int, num_of_vars: int):\n",
    "        if var_index < 0 or var_index > num_of_vars - 1:\n",
    "            raise Exception(\"Invalid variable index\")\n",
    "        num_of_evals = 2 ** num_of_vars\n",
    "        offset = num_of_evals // (2 ** (var_index + 1))\n",
    "        indices = list(range(num_of_evals))\n",
    "        pairs = []\n",
    "        for i in range(num_of_evals // 2):\n",
    "            start = indices[0]\n",
    "            stop = start + offset\n",
    "            pair = (start, stop)\n",
    "            indices.remove(start)\n",
    "            indices.remove(stop)\n",
    "            pairs.append(pair)\n",
    "        return pairs\n",
    "    \n",
    "    @staticmethod\n",
    "    def decrease_indexes_and_vars(indexes: List[int], variables: List[int]) -> Tuple[List[int], List[int]]:\n",
    "        return (list(map(lambda x: x - 1, indexes[1:])),  variables[1:])\n",
    "\n",
    "    def single_partial_evaluate(self, var_index: int, var: FFE) -> Union[Linear_Polynomial, 'Multilinear_Polynomial']:\n",
    "        pairs = self.get_pairing_index(var_index, self.num_of_vars)\n",
    "        \n",
    "        new_points = []\n",
    "        \n",
    "        for pair in pairs:\n",
    "            y_1 = self.evaluations[pair[0]]\n",
    "            x_2 = self.ff.one()\n",
    "            y_2 = self.evaluations[pair[1]]\n",
    "            slope = y_2 - y_1\n",
    "            c = y_2 - (slope * x_2)\n",
    "            value = (slope * var) + c\n",
    "            new_points.append(value)\n",
    "        \n",
    "        if len(new_points) == 2:\n",
    "            return Linear_Polynomial(self.ff, new_points)\n",
    "        else:\n",
    "            num_of_vars = log2(len(new_points))\n",
    "            return Multilinear_Polynomial(self.ff, new_points, int(num_of_vars))\n",
    "        \n",
    "    def partial_evaluate(self, indexes: List[int], variables: Tuple[FFE]):\n",
    "        if len(indexes) != len(variables):\n",
    "            raise Exception(\"length of indexes should be equal to length of variables\")\n",
    "        if len(variables) > self.num_of_vars - 1:\n",
    "            raise Exception(\"invalid number of variables\")\n",
    "                    \n",
    "        new_poly = self.single_partial_evaluate(indexes[0], variables[0])\n",
    "        new_indexes, new_variables = self.decrease_indexes_and_vars(indexes, variables)\n",
    "        \n",
    "        if len(new_indexes) == 0:\n",
    "            return new_poly\n",
    "        else:\n",
    "            return new_poly.partial_evaluate(new_indexes, new_variables)\n",
    "    \n",
    "    def evaluate(self, variables: Tuple[FFE]):\n",
    "        if len(variables) != self.num_of_vars:\n",
    "            raise Exception(\"Wrong number of variables\")\n",
    "        linear_poly = self.partial_evaluate([i for i in range(self.num_of_vars - 1)], variables[:self.num_of_vars - 1])\n",
    "        return linear_poly.evaluate(variables[-1])\n",
    "\n",
    "\n",
    "\n",
    "class SumCheck_Protocol:\n",
    "    \n",
    "    @staticmethod\n",
    "    def sum(poly: Multilinear_Polynomial):\n",
    "        return reduce(lambda x, y: x + y, poly.evaluations)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8a8dcd1a-4b2e-4f7f-9733-5c2e027d2d8c",
   "metadata": {
    "tags": []
   },
   "source": [
    "## Walkthrough of the Sumcheck Protocol"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6e7c82b7-5c84-4f28-a556-b388f3dccc34",
   "metadata": {
    "tags": []
   },
   "source": [
    "#### Setup\n",
    "\n",
    "GOAL: A prover wants to prove to the verifier the sum of a polynomial over the boolean hypercube\n",
    "\n",
    "Polynomial: $f(x, y, z) = x + y + z + 7$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "7ca2f1a7-6e7a-40d8-ad2f-36c6e3e8766a",
   "metadata": {},
   "outputs": [],
   "source": [
    "ff = FF(17)\n",
    "evaluations = [ff.new(7), ff.new(8), ff.new(8), ff.new(9), ff.new(8), ff.new(9), ff.new(9), ff.new(10)]\n",
    "mult_1 = Multilinear_Polynomial(ff, evaluations, 3)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "17424fee-bfa2-49cd-98da-741de0800947",
   "metadata": {
    "tags": []
   },
   "source": [
    "#### STEP 1:\n",
    "The prover computes the sum of the polynomial over the boolean hypercube and sends to the verifier"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "39c8fbad-0abd-4150-be5e-5ec73c090df8",
   "metadata": {},
   "outputs": [],
   "source": [
    "sum_check = SumCheck_Protocol()\n",
    "h = sum_check.sum(mult_1)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "012492aa-c457-423b-ba41-eb0b35744a46",
   "metadata": {
    "tags": []
   },
   "source": [
    "#### STEP 2: \n",
    "\n",
    "The prover computes a polynomial $g_1(x)$ and sends to the verifier $$g_1(x) = f(x, 0, 0) + f(x, 0, 1) + f(x, 1, 0) + f(x, 1, 1)$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "582386f1-28bc-4eb5-ba45-e30658b42bcc",
   "metadata": {},
   "outputs": [],
   "source": [
    "poly_1 = mult_1.partial_evaluate([1, 2], (ff.zero(), ff.zero())) ## f(x, 0, 0)\n",
    "poly_2 = mult_1.partial_evaluate([1, 2], (ff.zero(), ff.one())) ## f(x, 0, 1)\n",
    "poly_3 = mult_1.partial_evaluate([1, 2], (ff.one(), ff.zero())) ## f(x, 1, 0)\n",
    "poly_4 = mult_1.partial_evaluate([1, 2], (ff.one(), ff.one())) ## f(x, 1, 1)\n",
    "poly_5 = poly_1 + poly_2 + poly_3 + poly_4 ## f(x) = f(x, 0, 0) + f(x, 0, 1) + f(x, 1, 0) + f(x, 1, 1)\n",
    "g_1_of_x = poly_5"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4e14a661-c99e-496c-9df5-5b1b69b8db94",
   "metadata": {
    "tags": []
   },
   "source": [
    "#### STEP 3:\n",
    "\n",
    "The verifier stores $g_1(x)$ as $s_1(x)$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "id": "dec85013-2438-4af2-afc7-a08d77b3ef0d",
   "metadata": {},
   "outputs": [],
   "source": [
    "s_1_of_x = g_1_of_x"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8f167971-dfb5-4125-a979-351f742225f7",
   "metadata": {
    "tags": []
   },
   "source": [
    "#### STEP 4:\n",
    "\n",
    "The verifier checks that $h == s_1(0) + s_1(1)$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "id": "8e480cad-0436-4a12-890b-be22589aebea",
   "metadata": {},
   "outputs": [],
   "source": [
    "x = s_1_of_x.evaluate(ff.zero())\n",
    "y = s_1_of_x.evaluate(ff.one())\n",
    "assert h == x + y, \"Invalid proof\""
   ]
  },
  {
   "cell_type": "markdown",
   "id": "bd07b921-c2f9-4856-a5ae-73125635ec74",
   "metadata": {
    "tags": []
   },
   "source": [
    "#### STEP 5:\n",
    "\n",
    "The verifier generates a random value $r_1$ and sends to the prover"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "id": "23dcb9e8-6f55-45ab-a6da-d55be794d444",
   "metadata": {},
   "outputs": [],
   "source": [
    "r1 = ff.random_value()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "be61908d-cd48-4ccc-be91-fb9ec275ceb8",
   "metadata": {
    "tags": []
   },
   "source": [
    "#### STEP 6:\n",
    "\n",
    "The prover computes $g_2(y) = f(r_1, y, 0) + f(r_1, y, 1)$ and sends to the verifier"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "id": "8247a088-2c76-4234-97fe-8db994d831d1",
   "metadata": {},
   "outputs": [],
   "source": [
    "poly_1 = mult_1.partial_evaluate([0, 2], (r1, ff.zero())) ## f(r1, y, 0)\n",
    "poly_2 = mult_1.partial_evaluate([0, 2], (r1, ff.one())) ## f(r1, y, 1)\n",
    "poly_3 = poly_1 + poly_2 ## f(y) = f(r1, y, 0) + f(r1, y, 1)\n",
    "g_2_of_y = poly_3"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c1dcb1a7-388d-4a12-8c9e-765b463c360c",
   "metadata": {
    "tags": []
   },
   "source": [
    "#### STEP 7:\n",
    "\n",
    "The verifier stores $g_2(y)$ as $s_2(y)$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "id": "42738a23-4450-45cf-868c-6f141fe77ca0",
   "metadata": {},
   "outputs": [],
   "source": [
    "s_2_of_y = g_2_of_y"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e086ba10-a992-46ad-bec8-efa2c87c5801",
   "metadata": {
    "tags": []
   },
   "source": [
    "#### STEP 8:\n",
    "\n",
    "The verifier checks that $s_1(r_1) == s_2(0) + s_2(1)$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "id": "57d8ed7f-9f09-403c-a020-cfdb38ed0cc8",
   "metadata": {},
   "outputs": [],
   "source": [
    "x = s_1_of_x.evaluate(r1)\n",
    "y = s_2_of_y.evaluate(ff.zero())\n",
    "z = s_2_of_y.evaluate(ff.one())\n",
    "assert x == y + z, \"Invalid proof\""
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e6adb037-b872-4eb7-87c5-39ed6ff30456",
   "metadata": {
    "tags": []
   },
   "source": [
    "#### STEP 9:\n",
    "\n",
    "The verifier generates a random value $r_2$ and sends to the prover"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "id": "a4f854e6-cecd-486b-979f-6d44ebaa8446",
   "metadata": {},
   "outputs": [],
   "source": [
    "r2 = ff.random_value()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5dca491d-b08a-4e89-b31e-3f2cc6b878be",
   "metadata": {
    "tags": []
   },
   "source": [
    "#### STEP 10:\n",
    "\n",
    "The prover computes $g_3(z) = f(r_1, r_2, z)$ and sends to the verifier"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "id": "7cb260da-1397-4b35-825f-a6bbf3f0e58c",
   "metadata": {},
   "outputs": [],
   "source": [
    "poly_1 = mult_1.partial_evaluate([0, 1], (r1, r2)) ## f(r1, r2, z)\n",
    "g_3_of_z = poly_1"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d5de5a8a-51f1-4845-aeed-a1b7591d20b2",
   "metadata": {
    "tags": []
   },
   "source": [
    "#### STEP 11:\n",
    "\n",
    "The verifier stores $g_3(z)$ as $s_3(z)$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "id": "7833a75c-4593-4624-a7c3-b1e05504b351",
   "metadata": {},
   "outputs": [],
   "source": [
    "s_3_of_z = g_3_of_z"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "51cb7b08-c4ee-4198-b711-08072def254b",
   "metadata": {
    "tags": []
   },
   "source": [
    "#### STEP 12:\n",
    "\n",
    "The verifier checks that $s_2(r2) == s_3(0) + s_3(1)$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "id": "d4cb916c-6d56-47a2-945d-4a519e43554a",
   "metadata": {},
   "outputs": [],
   "source": [
    "x = s_2_of_y.evaluate(r2)\n",
    "y = s_3_of_z.evaluate(ff.zero())\n",
    "z = s_3_of_z.evaluate(ff.one())\n",
    "assert x == y + z, \"Invalid proof\""
   ]
  },
  {
   "cell_type": "markdown",
   "id": "69f65ef3-b80f-43f2-a2c3-9b91b0e8608b",
   "metadata": {
    "tags": []
   },
   "source": [
    "#### STEP 13:\n",
    "\n",
    "The verifier generates a random value $r_3$ and sends to the prover"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "id": "c1627dbf-f750-4168-88fd-e5207e36d9ff",
   "metadata": {},
   "outputs": [],
   "source": [
    "r3 = ff.random_value()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "630e6262-eeb9-4349-97ac-106729f016a6",
   "metadata": {
    "tags": []
   },
   "source": [
    "#### STEP 14:\n",
    "\n",
    "The prover computes $f(r_1, r_2, r_3)$ and sends to the verifier"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "id": "f7e6be5c-46d8-429a-9446-5d2a4b5dd7e0",
   "metadata": {},
   "outputs": [],
   "source": [
    "evaluation = mult_1.evaluate((r1, r2, r3))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "59affb5e-58b5-4e03-945f-0db2dae01c93",
   "metadata": {
    "tags": []
   },
   "source": [
    "#### LAST STEP:\n",
    "\n",
    "The verifier checks that $s_3(r_3) == f(r_1, r_2, r_3)$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 50,
   "id": "01758dce-c4ac-46ae-b8dd-301636c690eb",
   "metadata": {},
   "outputs": [],
   "source": [
    "x = s_3_of_z.evaluate(r3)\n",
    "assert x == evaluation, \"Invalid proof\""
   ]
  },
  {
   "cell_type": "markdown",
   "id": "61f94d72-e9d8-45eb-b7f5-77a7fc0367fc",
   "metadata": {
    "tags": []
   },
   "source": [
    "## Applications of the the Sumcheck Protocol"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "467ac419-b8a9-4e0f-b1a5-270e4584a58f",
   "metadata": {
    "tags": []
   },
   "source": [
    "### Interactive Proof(IP) for Matrix Multiplication(`MatMult`) Using the Sumcheck Protocol\n",
    "\n",
    "The best known algorithm for `MatMult` runs in $O(n^{2.37286})$ but it's not pratical. \n",
    "\n",
    "Check it out [here](https://arxiv.org/abs/2010.05846).\n",
    "\n",
    "We also showed how to check that product matrix `A.B == C` using the Freivalds Algorithm shown above.\n",
    "\n",
    "Here, we would show how to make the checking an IP using the Sumcheck Protocol.\n",
    "\n",
    "That is, the prover wants to prove to the verifier that he knows a matrix C such that product matrix of `A` and `B` equals `C`.\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 54,
   "id": "989c390a-a10e-4f7d-83d9-e3961b89ddbd",
   "metadata": {},
   "outputs": [],
   "source": [
    "from math import log2\n",
    "from functools import reduce\n",
    "\n",
    "def generate_n_by_n_matrix(n):\n",
    "    \n",
    "    res = []\n",
    "    \n",
    "    for _ in range(n):\n",
    "        row = [ff.random_value() for _ in range(n)]\n",
    "        res.append(row)\n",
    "        \n",
    "    return res\n",
    "\n",
    "\n",
    "def matrix_product(ff: FF, A: List[List[FFE]], B: List[List[FFE]]):\n",
    "    n = len(A)\n",
    "    # Initialize an n x n matrix with zeros for the result\n",
    "    C = [[ff.zero()] * n for _ in range(n)]\n",
    "    \n",
    "    # Perform matrix multiplication\n",
    "    for i in range(n):\n",
    "        for j in range(n):\n",
    "            for k in range(n):\n",
    "                C[i][j] += A[i][k] * B[k][j]\n",
    "    \n",
    "    return C\n",
    "\n",
    "def matrix_to_one_dim_list(x: List[List[FFE]]):\n",
    "    \n",
    "    res = []\n",
    "    \n",
    "    for row in x:\n",
    "        res += row\n",
    "        \n",
    "    return res\n",
    "\n",
    "\n",
    "class MulOfLinearPoly:\n",
    "    \n",
    "    a: Linear_Polynomial\n",
    "    \n",
    "    b: Linear_Polynomial\n",
    "    \n",
    "    def __init__(self, a: Linear_Polynomial, b: Linear_Polynomial):\n",
    "        if a.num_of_vars != b.num_of_vars:\n",
    "            raise Exception(\"Invalid inputs\")\n",
    "            \n",
    "        if len(a.evaluations) != 2:\n",
    "            raise Exception(\"Invalid inputs\")\n",
    "            \n",
    "        if a.ff.modulus != b.ff.modulus:\n",
    "            raise Exception(\"Invalid inputs\")\n",
    "            \n",
    "        self.a = a\n",
    "        self.b = b\n",
    "        \n",
    "    def __str__(self):\n",
    "        return f\"({self.a}, {self.b})\"\n",
    "    \n",
    "    def __repr__(self):\n",
    "        return f\"({self.a}, {self.b})\"\n",
    "    \n",
    "    def evaluate(self, x: FFE) -> FFE:\n",
    "        val_1 = self.a.evaluate(x)\n",
    "        val_2 = self.b.evaluate(x)\n",
    "        return val_1 * val_2\n",
    "\n",
    "\n",
    "class MulOfMultilinearPoly:\n",
    "    \n",
    "    \"\"\"\n",
    "    This represents of the multiplication of two multilinear polynomials.\n",
    "    \n",
    "    The can be partially evaluated at opposite ends(that is, A(X_1, b)B(b, X_2)) and \n",
    "    summed over the boolean hypercube\n",
    "    \"\"\"\n",
    "    \n",
    "    a: Multilinear_Polynomial\n",
    "    \n",
    "    b: Multilinear_Polynomial\n",
    "    \n",
    "    num_of_vars: int\n",
    "    \n",
    "    ff: FF\n",
    "        \n",
    "    def __init__(self, a: Multilinear_Polynomial, b: Multilinear_Polynomial):\n",
    "        if a.num_of_vars != b.num_of_vars:\n",
    "            raise Exception(\"Invalid inputs\")\n",
    "            \n",
    "        if a.ff.modulus != b.ff.modulus:\n",
    "            raise Exception(\"Invalid inputs\")\n",
    "        \n",
    "        self.ff = a.ff\n",
    "        self.a = a\n",
    "        self.b = b\n",
    "        self.num_of_vars = a.num_of_vars\n",
    "        \n",
    "    def __str__(self):\n",
    "        return f\"({self.a}, {self.b})\"\n",
    "    \n",
    "    def __repr__(self):\n",
    "        return f\"({self.a}, {self.b})\"\n",
    "    \n",
    "    def partial_evaluate_opposite(self, x1: List[FFE], x2: List[FFE]):            \n",
    "        if len(x1) != len(x2):\n",
    "            raise Exception(\"Invalid inputs\")\n",
    "            \n",
    "        if len(x1) != (self.num_of_vars // 2):\n",
    "            raise Exception(\"Invalid input length\")\n",
    "        \n",
    "        a = self.a.partial_evaluate([i for i in range(self.num_of_vars // 2)], x1)\n",
    "        b = self.b.partial_evaluate([i + (self.num_of_vars // 2) for i in range(self.num_of_vars // 2)], x2)\n",
    "        return MulOfMultilinearPoly(a, b)\n",
    "    \n",
    "    def partial_evaluate(self, indexes: List[int], variables: Tuple[FFE]):\n",
    "        a = self.a.partial_evaluate(indexes, variables)\n",
    "        b = self.b.partial_evaluate(indexes, variables)\n",
    "        if len(a.evaluations) == 2 and len(b.evaluations) == 2:\n",
    "            return MulOfLinearPoly(a, b)\n",
    "        return MulOfMultilinearPoly(a, b)\n",
    "    \n",
    "    def evaluate(self, variables: Tuple[FFE]):\n",
    "        eval_1 = self.a.evaluate(variables)\n",
    "        eval_2 = self.b.evaluate(variables)\n",
    "        return eval_1 * eval_2\n",
    "     \n",
    "    def sum(self):\n",
    "        res = self.ff.zero()\n",
    "        for (x, y) in zip(self.a.evaluations, self.b.evaluations):\n",
    "            res = res + (x * y)\n",
    "        return res\n",
    "    \n",
    "    \n",
    "class AddOfMulOfLinearPoly:\n",
    "    \n",
    "    polynomials: List[MulOfLinearPoly]\n",
    "    \n",
    "    def __init__(self, polynomials: List[MulOfLinearPoly]):\n",
    "        self.polynomials = polynomials\n",
    "        \n",
    "    def evaluate(self, x: FFE) -> FFE:\n",
    "        evaluations = [linear_poly.evaluate(x) for linear_poly in self.polynomials]\n",
    "        return reduce(lambda x, y: x + y, evaluations)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "59e4838b-007b-40bc-94ac-6fd4c2fa83a8",
   "metadata": {
    "tags": []
   },
   "source": [
    "#### Walkthrough of the Sumcheck Protocol for MatMult\n",
    "\n",
    "Protocol overview:\n",
    "\n",
    "- There are three $n$ by $n$ matrices $A$, $B$ and $C$ such that the product $A.B$ equals $C$ and the prover wants to prove this to the verifier\n",
    "- Firstly, we have to convert each of the matrix to a multilinear polynomial such that:$$\\{0, 1\\}^{\\log_2 n} \\times \\{0, 1\\}^{\\log_2 n}  \\to \\mathbb{F}$$That way, we have a multilinear polynomial with $\\log_2 n + \\log_2 n$ variables where the left half of the variable represent the row and the right half represent the column of the matrix in binary and the evaluation at that variable is the value at the index in the matrix. For example: When $n = 4$, then $\\log_2 n = 2$ $$M = \n",
    "\\begin{bmatrix}\n",
    "0 & 1 & 2 & 3 \\\\[0.3em]\n",
    "4 & 5 & 6 & 7 \\\\[0.3em]\n",
    "8 & 9 & 10 & 11 \\\\[0.3em]\n",
    "12 & 13 & 14 & 15 \n",
    "\\end{bmatrix}$$The multilinear polynomial for this matrix is as follows:\n",
    "$$\\tilde M(0, 0, 0, 0) = 0\\\\ \\tilde M(0, 0, 0, 1) = 1\\\\ \\tilde M(0, 0, 1, 0) = 2\\\\ \\tilde M(0, 0, 1, 1) = 3\\\\ \\tilde M(0, 1, 0, 0) = 4\\\\ \\tilde M(0, 1, 0, 1) = 5\\\\ \\tilde M(0, 1, 1, 0) = 6\\\\ \\tilde M(0, 1, 1, 1) = 7\\\\ \\tilde M(1, 0, 0, 1) = 8\\\\ \\tilde M(1, 0, 0, 1) = 9\\\\ \\tilde M(1, 0, 1, 0) = 10\\\\ \\tilde M(1, 0, 1, 1) = 11\\\\ \\tilde M(1, 1, 0, 0) = 12\\\\ \\tilde M(1, 1, 0, 1) = 13\\\\ \\tilde M(1, 1, 1, 0) = 14\\\\ \\tilde M(1, 1, 1, 1) = 15$$\n",
    "\n",
    "- Now, we have converted from a checking matrices to checking of polynomials:$$\\tilde C(x, y) = \\sum_{b \\in \\{0, 1\\}^{\\log_2n}} \\tilde A(x, b).\\tilde B(b, y)$$ where $x, y \\in \\{0, 1\\}^{\\log_2 n}$. (*check out how product of $n$ by $n$ matrices works to understand the expression better*)\n",
    "\n",
    "- Lastly, before the sumcheck the verifier generates values $r_1, r_2 \\in \\mathbb{F}^{log_2 n}$ to compute $\\tilde C(r_1, r_2) = \\sum_{b \\in \\{0, 1\\}^{\\log_2n}} \\tilde A(r_1, b).\\tilde B(b, r_2)$. This is an IP for evaluating $\\tilde C(r_1, r_2)$. This also gives us a new polynomial $g(z) = \\tilde A(r_1, z).\\tilde B(z, r_2)$ that we would be performing the sumcheck protocol on."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9970fcaa-8564-4827-9575-55a1f20f0325",
   "metadata": {
    "tags": []
   },
   "source": [
    "##### STEP 1:\n",
    "\n",
    "Define the matrix, convert to a multilinear extension"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 58,
   "id": "9d149974-8b6e-4b12-8d51-5424c13a3fc1",
   "metadata": {},
   "outputs": [],
   "source": [
    "n = 16\n",
    "\n",
    "log_n = int(log2(n))\n",
    "\n",
    "ff = FF(17)\n",
    "\n",
    "A = generate_n_by_n_matrix(n)\n",
    "\n",
    "B = generate_n_by_n_matrix(n)\n",
    "\n",
    "num_of_vars = log_n + log_n\n",
    "\n",
    "evaluations_a = matrix_to_one_dim_list(A)\n",
    "multi_poly_A = Multilinear_Polynomial(ff, evaluations_a, num_of_vars)\n",
    "\n",
    "evaluations_b = matrix_to_one_dim_list(B)\n",
    "multi_poly_B = Multilinear_Polynomial(ff, evaluations_b, num_of_vars)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f4bbd64a-a64c-4480-9437-0bdfc9b4d1b5",
   "metadata": {
    "tags": []
   },
   "source": [
    "##### STEP 2:\n",
    "\n",
    "Compute $\\tilde C(r_1, r_2) = \\sum_{b \\in \\{0, 1\\}^{\\log_2n}} \\tilde A(r_1, b).\\tilde B(b, r_2)$ as an IP for evaluation and also the initial sum that would be sent to the verifier.\n",
    "###### Steps:\n",
    "- Compute $\\tilde A(r_1, b)$ be partially evaluating at $r_1$\n",
    "- Compute $\\tilde B(b, r_2)$ be partially evaluating at $r_2$\n",
    "- Compute $g(b) = \\tilde A(r_1, b) .\\tilde B(b, r_2)$\n",
    "- Compute the sum of $g(b)$ over the boolean hypercube"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 61,
   "id": "5ae3088a-398c-47ed-a799-03d6a58210d9",
   "metadata": {},
   "outputs": [],
   "source": [
    "r1 = [ff.random_value() for _ in range(log_n)]\n",
    "\n",
    "r2 = [ff.random_value() for _ in range(log_n)]\n",
    "\n",
    "mom_poly_1 = MulOfMultilinearPoly(multi_poly_A, multi_poly_B)\n",
    "\n",
    "mom_poly_2 = mom_poly_1.partial_evaluate_opposite(r1, r2)\n",
    "\n",
    "h = mom_poly_2.sum()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "dd8eae13-11f2-449c-bf66-cf8cfdbde5f6",
   "metadata": {
    "tags": []
   },
   "source": [
    "##### STEP 3:\n",
    "\n",
    "The prover computes a polynomial $g_1(x)$ and sends to the verifier. $$g_1(x) = g(x, 0, 0, 0) + g(x, 0, 0, 1) + g(x, 0, 1, 0) + g(x, 0, 1, 1) + g(x, 1, 0, 0) + g(x, 1, 0, 1) + g(x, 1, 1, 0) + g(x, 1, 1, 1)$$\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 64,
   "id": "ff198e34-3f2b-40fd-a22e-a7fe7663191b",
   "metadata": {},
   "outputs": [],
   "source": [
    "poly_1 = mom_poly_2.partial_evaluate([1, 2, 3], (ff.zero(), ff.zero(), ff.zero())) # g(x, 0, 0, 0)\n",
    "poly_2 = mom_poly_2.partial_evaluate([1, 2, 3], (ff.zero(), ff.zero(), ff.one())) # g(x, 0, 0, 1)\n",
    "poly_3 = mom_poly_2.partial_evaluate([1, 2, 3], (ff.zero(), ff.one(), ff.zero())) # g(x, 0, 1, 0)\n",
    "poly_4 = mom_poly_2.partial_evaluate([1, 2, 3], (ff.zero(), ff.one(), ff.one())) # g(x, 0, 1, 1)\n",
    "poly_5 = mom_poly_2.partial_evaluate([1, 2, 3], (ff.one(), ff.zero(), ff.zero())) # g(x, 1, 0, 0)\n",
    "poly_6 = mom_poly_2.partial_evaluate([1, 2, 3], (ff.one(), ff.zero(), ff.one())) # g(x, 1, 0, 1)\n",
    "poly_7 = mom_poly_2.partial_evaluate([1, 2, 3], (ff.one(), ff.one(), ff.zero())) # g(x, 1, 1, 0)\n",
    "poly_8 = mom_poly_2.partial_evaluate([1, 2, 3], (ff.one(), ff.one(), ff.one())) # g(x, 1, 1, 1)\n",
    "\n",
    "g_1_of_x = AddOfMulOfLinearPoly([poly_1, poly_2, poly_3, poly_4, poly_5, poly_6, poly_7, poly_8])"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9c6caeab-dbe8-4859-8b4e-31136d66a5e5",
   "metadata": {},
   "source": [
    "##### STEP 4:\n",
    "\n",
    "The verifier stores $g_1(x)$ as $s_1(x)$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 67,
   "id": "0e8f5c7d-6176-4cab-b0cc-9438832114d2",
   "metadata": {},
   "outputs": [],
   "source": [
    "s_1_of_x = g_1_of_x"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cf2bbf2d-cffb-4a68-a5a0-a9dd24f40379",
   "metadata": {
    "tags": []
   },
   "source": [
    "##### STEP 5:\n",
    "\n",
    "The verifier checks that $h == s_1(0) + s_1(1)$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 70,
   "id": "153b2c75-1376-4c65-bb58-7e010e63158b",
   "metadata": {},
   "outputs": [],
   "source": [
    "x = s_1_of_x.evaluate(ff.zero())\n",
    "y = s_1_of_x.evaluate(ff.one())\n",
    "assert h == x + y, \"Invalid proof\""
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4ba3cbbb-885f-450c-b302-8773a0699787",
   "metadata": {},
   "source": [
    "##### STEP 6:\n",
    "\n",
    "The verifier generates a random value $r_1$ and sends to the prover"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 73,
   "id": "2c1528bc-eeca-4269-ada4-b4cea078606a",
   "metadata": {},
   "outputs": [],
   "source": [
    "r1 = ff.random_value()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e3ae10a6-d119-452a-831d-ef8894962920",
   "metadata": {},
   "source": [
    "##### STEP 7:\n",
    "\n",
    "The prover computes $g_2(y) = g(r_1, y, 0, 0) + g(r_1, y, 0, 1) + g(r_1, y, 1, 0) + g(r_1, y, 1, 1)$ and sends to the verifier"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 76,
   "id": "21ac28ca-cc88-4101-a0d9-6d9430cf71e2",
   "metadata": {},
   "outputs": [],
   "source": [
    "poly_1 = mom_poly_2.partial_evaluate([0, 2, 3], (r1, ff.zero(), ff.zero())) # g(r1, y, 0, 0)\n",
    "poly_2 = mom_poly_2.partial_evaluate([0, 2, 3], (r1, ff.zero(), ff.one())) # g(r1, y, 0, 1)\n",
    "poly_3 = mom_poly_2.partial_evaluate([0, 2, 3], (r1, ff.one(), ff.zero())) # g(r1, y, 1, 0)\n",
    "poly_4 = mom_poly_2.partial_evaluate([0, 2, 3], (r1, ff.one(), ff.one())) # g(r1, y, 1, 1)\n",
    "\n",
    "g_2_of_y = AddOfMulOfLinearPoly([poly_1, poly_2, poly_3, poly_4])"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c8339a39-3bec-4b54-a68f-0f35a3d7d7b9",
   "metadata": {},
   "source": [
    "##### STEP 8:\n",
    "\n",
    "The verifier stores $g_2(y)$ as $s_2(y)$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 79,
   "id": "2824f18c-bf56-475a-8cfa-e9f3c31fa28b",
   "metadata": {},
   "outputs": [],
   "source": [
    "s_2_of_y = g_2_of_y"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a74d906a-4091-48e5-aab1-540573f13bc4",
   "metadata": {},
   "source": [
    "##### STEP 9:\n",
    "\n",
    "The verifier checks that $s_1(r_1) == s_2(0) + s_2(1)$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 82,
   "id": "1f41872c-5da0-4396-b018-88f516aee1e5",
   "metadata": {},
   "outputs": [],
   "source": [
    "x = s_1_of_x.evaluate(r1)\n",
    "y = s_2_of_y.evaluate(ff.zero())\n",
    "z = s_2_of_y.evaluate(ff.one())\n",
    "assert x == y + z, \"Invalid proof\""
   ]
  },
  {
   "cell_type": "markdown",
   "id": "cf9a6336-802e-4262-b3b8-0fe8768b7dd9",
   "metadata": {},
   "source": [
    "##### STEP 10:\n",
    "\n",
    "The verifier generates a random value $r_2$ and sends to the prover"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 85,
   "id": "75ed1ff1-7325-4fac-83f6-4d88fb6c93db",
   "metadata": {},
   "outputs": [],
   "source": [
    "r2 = ff.random_value()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d5b9ad8c-50e2-40fd-a97d-5cf5858fe0f7",
   "metadata": {},
   "source": [
    "##### STEP 11:\n",
    "\n",
    "The prover computes $g_3(w) = g(r_1, r_2, w, 0) + g(r_1, r_2, w, 1)$ and sends to the verifier"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 88,
   "id": "22fb66de-b1c5-454a-a41b-a914105125c2",
   "metadata": {},
   "outputs": [],
   "source": [
    "poly_1 = mom_poly_2.partial_evaluate([0, 1, 3], (r1, r2, ff.zero())) # g(r1, r2, w, 0)\n",
    "poly_2 = mom_poly_2.partial_evaluate([0, 1, 3], (r1, r2, ff.one())) # g(r1, r2, w, 1)\n",
    "\n",
    "g_3_of_w = AddOfMulOfLinearPoly([poly_1, poly_2])"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7002a1cc-fc3e-404e-9f82-7dfc8aab411b",
   "metadata": {},
   "source": [
    "##### STEP 12:\n",
    "\n",
    "The verifier stores $g_3(w)$ as $s_3(w)$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 91,
   "id": "eee54c26-c2d3-4177-b6c7-5400922ed1e0",
   "metadata": {},
   "outputs": [],
   "source": [
    "s_3_of_w = g_3_of_w"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "91c1a428-2005-41a5-b85f-c2bc8106a2fe",
   "metadata": {},
   "source": [
    "##### STEP 13:\n",
    "\n",
    "The verifier checks that $s_2(r_2) == s_3(0) + s_3(1)$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 94,
   "id": "2156f7c2-e625-485f-b33c-1a4ba0a5aff9",
   "metadata": {},
   "outputs": [],
   "source": [
    "x = s_2_of_y.evaluate(r2)\n",
    "y = s_3_of_w.evaluate(ff.zero())\n",
    "z = s_3_of_w.evaluate(ff.one())\n",
    "assert x == y + z, \"Invalid proof\""
   ]
  },
  {
   "cell_type": "markdown",
   "id": "35cc0b03-5d70-4aa5-853b-854c9d2d75db",
   "metadata": {},
   "source": [
    "##### STEP 14:\n",
    "\n",
    "The verifier generates a random value $r_3$ and sends to the prover"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 97,
   "id": "5aa1f651-72bf-4669-a768-141aa2d96db6",
   "metadata": {},
   "outputs": [],
   "source": [
    "r3 = ff.random_value()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1e7785b4-b455-4a43-9a4e-8a8e44d34648",
   "metadata": {},
   "source": [
    "##### STEP 15:\n",
    "\n",
    "The prover computes $g_4(z) = g(r_1, r_2, r_3, z)$ and sends to the verifier"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 100,
   "id": "9a2ec6c8-6484-4d40-beda-c6f291f029b1",
   "metadata": {},
   "outputs": [],
   "source": [
    "poly_1 = mom_poly_2.partial_evaluate([0, 1, 2], (r1, r2, r3)) # g(r1, r2, r3, z)\n",
    "\n",
    "g_4_of_z = poly_1"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e9195ddb-9b7c-4281-aa74-76a6deba81ad",
   "metadata": {},
   "source": [
    "##### STEP 16:\n",
    "\n",
    "The verifier stores $g_4(z)$ as $s_4(z)$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 103,
   "id": "94cfb542-15a8-43ab-9a7d-8479944f85a0",
   "metadata": {},
   "outputs": [],
   "source": [
    "s_4_of_z = g_4_of_z"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b31d07ca-06d3-4739-829a-b26a3355769f",
   "metadata": {},
   "source": [
    "##### STEP 17:\n",
    "\n",
    "The verifier checks that $s_3(r_3) == s_4(0) + s_4(1)$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 106,
   "id": "46253469-d826-4cda-9e50-ffd76ce5d8c3",
   "metadata": {},
   "outputs": [],
   "source": [
    "x = s_3_of_w.evaluate(r3)\n",
    "y = s_4_of_z.evaluate(ff.zero())\n",
    "z = s_4_of_z.evaluate(ff.one())\n",
    "assert x == y + z, \"Invalid proof\""
   ]
  },
  {
   "cell_type": "markdown",
   "id": "317cc21e-dda5-40f5-b340-8b2e0ad50771",
   "metadata": {},
   "source": [
    "##### STEP 18:\n",
    "\n",
    "The verifier generates a random value $r_4$ and sends to the prover"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 109,
   "id": "9ae07597-a8b5-4027-9918-d55e248aa667",
   "metadata": {},
   "outputs": [],
   "source": [
    "r4 = ff.random_value()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6aaa699b-a7c3-40e8-813a-5f8dedd149ea",
   "metadata": {},
   "source": [
    "##### STEP 19\n",
    "\n",
    "The prover computes $g(r_1, r_2, r_3, r_4)$ and sends to the verifier"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 112,
   "id": "3cbfe8b2-0693-4228-b149-c4072b7be4c3",
   "metadata": {},
   "outputs": [],
   "source": [
    "evaluation = mom_poly_2.evaluate((r1, r2, r3, r4))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0440865c-d5e9-4dbf-b204-a40ff6a27d7a",
   "metadata": {},
   "source": [
    "##### LAST STEP:\n",
    "\n",
    "The verifier checks that $s_4(r_4) == g(r_1, r_2, r_3, r_4)$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 115,
   "id": "f8d1de53-19b9-4b5c-a5ef-50dd0b25e860",
   "metadata": {},
   "outputs": [],
   "source": [
    "x = s_4_of_z.evaluate(r4)\n",
    "assert x == evaluation, \"Invalid proof\""
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f677327d-c7c9-46b4-865b-7c16304225d0",
   "metadata": {
    "tags": []
   },
   "source": [
    "### Interactive Proof(IP) for Counting Triangles"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3c671f14-c227-43cf-9465-6c7a1a6e5d73",
   "metadata": {},
   "source": [
    "The counting triangle problem is simply a problem of checking how many 3-cycled vertices we have in a graph i.e how many set of vertices form a triangle."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 119,
   "id": "69d3ac6d-d14d-46a0-896d-18efe6dc35fe",
   "metadata": {
    "tags": []
   },
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAApQAAAHzCAYAAACe1o1DAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjguMywgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy/H5lhTAAAACXBIWXMAAA9hAAAPYQGoP6dpAAB8DElEQVR4nO3ddXzVZePG8Q8LujtHd6l0KCUlAhtIt4CAdAqC9YioGyEtUgLScBY0SEmzoYwG6Y7RsMHq/P6Y8Ht4QAV2tvucs+v9eu11ZJx9vxfGvHbf3/u+E1mtVisiIiIiIq/JxXQAEREREXFsKpQiIiIiEisqlCIiIiISKyqUIiIiIhIrKpQiIiIiEisqlCIiIiISKyqUIiIiIhIrKpQiIiIiEisqlCIiIiISKyqUIiIiIhIrKpQiIiIiEisqlCIiIiISKyqUIiIiIhIrKpQiIiIiEisqlCIiIiISKyqUIiIiIhIrKpQiIiIiEisqlCIiIiISKyqUIiIiIhIrKpQiIiIiEisqlCIiIiISKyqUIiIiIhIrKpQiIiIiEisqlCIiIiISKyqUIiIiIhIrKpQiIiIiEisqlCIiIiISK26mA4iIiP2xWuHGDQgNhfBwSJwYkieHTJkgUSLT6UTE3qhQiogIISGwaRPs2wd798a83r///PtSpYIyZaB8+ZjXmjUhY8b4zysi9iWR1Wq1mg4hIiLxz2qF3bth8mRYvBgiI8HNLeb13zx5n5sbtGwJPXtChQoavRRJqFQoRUQSIH9/GDECDh16+RL5d558fcmSMHIkNGpku5wi4hhUKEVEEpCbN6F3b1i4EFxcIDradtd+cr1WrWDiRMiQwXbXFhH7pkIpIpJA+PlBly5w5w5ERcXdfVxdIW1amDEDPD3j7j4iYj+0bZCIiJOzWmHUKPDygtu347ZMQsz1b9+Oud+338bcX0Scm0YoRUScmNUKn34K331nLsOwYfDNN1qwI+LMNEIpIuLEvv3WbJm0lwwiErc0Qiki4qT8/GKmne2Fnx80bmw6hYjEBRVKEREndPMmFC4Mt27ZxzOMLi6QLh0cP67V3yLOSFPeIiJOqHfvmNXc9lAmIWY7oTt3oE8f00lEJC5ohFJExMn4+9v3dj3+/tr8XMTZqFCKiDgRqxVKlYIjR2y7abmtuLhA8eIQHKxV3yLORFPeIiJOZPfumOMU7bFMQkyugwdhzx7TSUTEllQoRUScyOTJMWdrv747QB+gEpAVSALkAGoCy4HYT2q5ucXkFBHnoSlvEREnERIC2bJBZGRsrnISeAOoCBQA0gPXgRV/vXYFfopdUGJK5ZUrkDFjrC8lInYgVj/HioiI/di0KbZlEiAvMaOU//u/h/vElMzpQF+geKzuEhkJmzdDs2axuoyI2AlNeYuIOIl9+2I73Q3gyovHGlIBdf/665OxvQlubjF5RcQ5qFCKiDiJPXtsMUL5dx4Bm4BEQLFYXy0yEvbujfVlRMROaMpbRMQJWK3w+++2vOId4AcgmphnJ1cDF4AvgII2uUNQUExubR8k4vi0KEdExAlcvw5ZstjyimeJeZ7yCXdgFDCQmFFK27h2DTJnttnlRMQQTXmLiDiB0FBbXzEPMVsERQJngP8Aw4Gmf33ONsLCbHYpETFIhVJExAmEh8fVlV2JKZdDgZGALzErvW3j8WObXUpEDFKhFBFxAokTx8dd6vz1usVmV0ySxGaXEhGDVChFRJxA8uTxcZfLf73abj1nsmQ2u5SIGKRCKSLiBDJlglSpbHGl/cDdF3z+FvDpX39d3xY3IlWqmNwi4vi0bZCIiBNIlAjeegu2bo3tlX4GZgA1gNxACuAcsAp4QMyinNaxvQkAZctqyyARZ6FCKSLiJCpUgB07Yru5+QfEjFDuBn4DQok5z7sq0B5oiS22DXJzg/LlY30ZEbETKpQiIk6iTBlbnJRT9a+PuBUZGZNXRJyDNjYXEXESISGQLZuVyEj7n0d2c4MrVyBjRtNJRMQWtChHRMQJ3Lt3j59/Ho27uwWIMB3nH7m5QcuWKpMizkSFUkTEgV2+fJmhQ4eSK1cuPv30U2rWPEbMMYn2KzISevY0nUJEbEmFUkTEAR09epTOnTuTJ08epk6dSvfu3Tlz5gwrVgynZElwsdPv7i4uUKpUzAIiEXEeeoZSRMRBWK1WduzYgbe3NytWrCB79uz069ePjz76iDRp0jx9X0AANG5sMOi/8PeHRo1MpxARW7LTn2FFROSJ6OhofH19qVKlCm+//TanTp1i9uzZnDlzhsGDBz9TJiGmrLVqBa6uhgL/DVdXaN1aZVLEGWmEUkTETj169Ih58+YxevRoTpw4wTvvvMPgwYN57733cPmXOe2bN6FwYbh9G6Kj4ynwP3BxgXTp4PhxyJDBdBoRsTWNUIqI2Jnbt28zatQo8uTJQ7du3ShZsiS7d+9m69atvP/++/9aJiGmtM2YYR9lEmJyzJypMinirDRCKSJiJ86fP8+4ceOYPn06kZGRdOzYkYEDB1KwYMHXvuaoUTB8uA1DxiLHsGGmU4hIXFGhFBEx7MCBA/j4+LBw4UJSp05Nz5496dWrF1myZIn1ta3WmEL57bc2CPqahg2Db77Rud0izkyFUkTEAKvVyubNm/H29mbdunV4eHgwcOBAPvzwQ1KmTGnje8F338Gnn8Y8yxg/0+BRgCvDht1j1KjU8XFDETFIz1CKiMSjyMhIFi9eTLly5ahVqxbXrl1j/vz5nDx5kj59+ti8TELMyOCwYeDnF7MwJq5Xf7u6Qrp0iUif/kM2bqzNo0eP4vaGImKcCqWISDwIDQ1l8uTJFCpUiJYtW5IuXTrWr1/P77//TuvWrXF3j/vTbRo3jlll3bx5zK9tvfn5k+u1aAEnT7qwdm0PDhw4QLdu3dBkmIhzU6EUEYlDN27c4Msvv8TDw4M+ffpQoUIF9u3bx4YNG6hduzaJ4vnBwgwZYMGCmNHK4sWffDZ2Z3+7ucW8Fi8es2n5/PmQPj2UK1eOmTNnMnfuXMaNGxere4iIfdMzlCIiceDUqVOMHTuW2bNnkyhRIjp37kz//v3Jmzev6WhPWa0wa9ZhunTZh6trW6KiXHB3h4iX6JdubjFncru7Q8uWMWdzly//4oU3n3zyCaNHj2b16tXUrVvX9n8QETFOhVJExIaCgoLw8fFh2bJlpE+fnj59+vDxxx+TwU43YBw6dCizZs3i4MEr/PabK0FBEBgIQUFw//7z70+VCsqWjSmPZcpAjRqQMeM/3yMqKopGjRqxY8cO9u7dS6FCheLmDyMixqhQiojEktVqZd26dXh7e7N582by58/PoEGD6NChA8mSJTMd729ZrVYKFSpE9erVmT59+v/8Hty4AWFh8PgxJEkCyZJBpkyvt/3P3bt3qVChAgB79ux57rhIEXFseoZSROQ1RUREMG/ePEqXLk39+vV58OABS5cu5fjx43Tv3t2uyyTA4cOHOXnyJE2aNHnu9xIlgsyZIXduKFQo5jVz5tffSzJNmjQEBARw9epVWrduTVRUVCzTi4g9UaEUEXlF9+/fZ+zYseTPn5/27duTK1cutmzZwp49e/jggw9wjet9eWzEYrGQOnVqatasGS/3K1SoEIsXL2bt2rUMt4fje0TEZjTlLSLykq5evcqECROYMmUKDx8+pE2bNgwaNIgSJUqYjvZa3njjDYoXL878+fPj9b5jxoxh0KBBzJ8/n9atW8frvUUkbqhQioj8i+PHjzN69Gjmzp1LkiRJ6NatG3379iVnzpymo722U6dOUaBAAZYtW0bTpk3j9d5Wq5UOHTqwdOlStm3bRtmyZeP1/iJieyqUIiJ/Y+fOnfj4+ODv70/WrFnp27cv3bp1I23atKajxdro0aP57LPPCAkJIUWKFPF+/0ePHlGtWjUuXbpEYGAg2bJli/cMImI7eoZSROS/REdHExAQQNWqValSpQrHjh1jxowZnDlzhk8++cQpyiTEPD9Zr149I2USIGnSpPj6+hIdHU3Tpk15/PixkRwiYhsqlCIiwOPHj5k5cybFixencePGJEqUCH9/fw4fPsyHH35IkiRJTEe0mcuXL7Nr164Xru6OT9mzZ8fX15fff/+dHj166HhGEQemQikiCdqdO3f47rvvyJMnD127dqVIkSLs2LGDbdu20ahRI1xsfeC1HfDz88PNzY3333/fdBQqVKjA9OnTmT17NhMmTDAdR0Rek56hFJEE6eLFi/zwww9MmzaN8PBwOnTowMCBAylcuLDpaHHu3XffxdXVlXXr1pmO8tSgQYMYN24ca9eupXbt2qbjiMgrUqEUkQTl4MGDjB49mgULFpAyZUo+/vhjevfuTdasWU1Hixc3b94kS5YsTJ48mW7dupmO81RUVBQNGjRg79697N27lwIFCpiOJCKvQIVSRJye1Wpl69ateHt7s2bNGnLlykX//v3p0qULqVKlMh0vXv388898+OGHXL582e5K9O3bt6lQoQJubm7s3r2b1KlTm44kIi/J+R4OEhH5S1RUFEuXLqVChQrUqFGDixcvMm/ePE6dOkX//v0TXJkE8PX1pUqVKnZXJgHSpUtHQEAAly5dom3btkRHR5uOJCIvSYVSRJxOWFgYU6dOpXDhwjRv3pxUqVKxdu1agoODadu2Le7u7qYjGvHgwQPWrVtnfHX3PylSpAgLFy5k5cqVfPbZZ6bjiMhLcjMdQETEVm7evMnkyZOZOHEit27dolmzZixevJgyZcqYjmYX1qxZw+PHj/Hy8jId5R+99957fPfdd3zyySeUKlWKFi1amI4kIv9Cz1CKiMM7c+YM48aNY+bMmVitVj788EMGDBhAvnz5TEezK61ateLEiRPs27fPdJR/ZbVaadeuHRaLhe3bt/PWW2+ZjiQi/0CFUkQc1u+//46Pjw9LliwhXbp09O7dm549e5IxY0bT0ezOo0ePyJQpE0OHDmX48OGm47yUsLAw3nnnHa5evUpQUBBZsmQxHUlE/oaeoRQRh2K1Wlm/fj3vvvsuZcqUYc+ePUyYMIHz58/zxRdfqEz+jY0bN/LgwQO7fn7yfyVLlgxfX18iIiJ0PKOInVOhFBGHEBERwfz583nzzTepW7cud+7cYfHixZw4cYKePXuSPHly0xHtmsVioUiRIhQtWtR0lFeSM2dOfH19CQwMpFevXjqeUcROqVCKiF178OAB48ePp0CBArRt25Zs2bKxadMmAgMDad68OW5uWlv4byIjI/H393eo0cn/VqlSJaZNm8aMGTOYPHmy6Tgi8gL6TiwidunatWtMnDiRKVOmcP/+fVq1asWgQYMoVaqU6WgOZ9u2bdy8edNhCyVAx44dCQ4Opl+/fhQrVoyaNWuajiQi/0WLckTErpw4cYIxY8YwZ84c3N3d6dq1K/369cPDw8N0NIfVu3dvAgICOHv2LIkSJTId57VFRkby3nvvsW/fPgIDA7WKX8SOqFCKiF3YvXs3Pj4++Pr6kjlzZvr27Uv37t1Jly6d6WgOLTo6Gg8PD5o1a8a4ceNMx4m1W7duUb58eZImTcquXbsS5GlHIvZIz1CKiDHR0dGsXLmSd955h0qVKnHo0CF++uknzp49y7Bhw1QmbSAwMJBLly459HT3f0ufPj0BAQGcP3+edu3a6XhGETuhQiki8e7x48fMnj2bkiVL0rBhQyIjI/H19eXo0aN06dKFpEmTmo7oNCwWC5kzZ6Zy5cqmo9hMsWLFWLBgAQEBAXz55Zem44gIKpQiEo/u3r2Lj48P+fLl48MPP6RAgQJs376dnTt34unpiYuLviXZktVqxWKx4Onpiaurq+k4NvX+++/zzTff8PXXX7N06VLTcUQSPD1DKSJx7tKlS4wfP54ff/yRx48f065dOwYOHOhweyI6moMHD1KqVCnWrl1L3bp1TcexOavVSuvWrQkICGDHjh288cYbpiOJJFgqlCISZw4fPszo0aOZP38+yZMnp3v37vTp04fs2bObjpYgfPXVV4wbN47r16+TOHFi03HiRGhoKG+//TYhISEEBgaSOXNm05FEEiQVShGxKavVyrZt2/Dx8WHlypXkyJGD/v3707VrV1KnTm06XoJSunRpSpUqxbx580xHiVMXLlygbNmyFC5cmF9//dVpy7OIPdMDSyJiE1FRUVgsFipVqkS1atU4c+YMc+bM4fTp0wwcOFBlMp6dPHmSAwcOOM3q7n+SK1cuLBYLu3fvpk+fPqbjiCRIKpQiEithYWFMmzaNIkWK0LRpU5IlS8aqVas4ePAg7du312iRIb6+viRLlswpn518kSpVqjB16lSmTZvG1KlTTccRSXB09KKIvJZbt24xZcoUJkyY8PRYv/nz51O+fHnT0YSY7YLq1atH8uTJTUeJN507dyY4OJg+ffpQtGhRqlevbjqSSIKhZyhF5JWcPXuWcePGMXPmTKKioujUqRMDBgygQIECpqPJXy5dukTOnDmZN28ebdu2NR0nXkVERFCvXj2Cg4MJDAwkb968piOJJAia8haRl7J//37atGlDgQIF+OWXXxg4cCDnzp1jypQpKpN2xs/PDzc3N95//33TUeKdu7s7S5YsIU2aNDRu3JgHDx6YjiSSIGiEUkT+ltVqZePGjfj4+LB+/Xpy587NwIED+fDDD0mRIoXpePI3atWqhbu7O2vXrjUdxZhDhw5RqVIl6tSpw9KlS7Vpvkgc039hIvKcyMhIFi1aRJkyZahduzY3btxg4cKFnDx5kt69e6tM2rGQkBC2bt2aIFZ3/5MSJUrwyy+/YLFY+Prrr03HEXF6KpQi8tTDhw+ZOHEiBQsWpFWrVmTKlIkNGzawb98+WrZsiZub1vHZuxUrVhAdHU3jxo1NRzGucePGfP3113z55ZdYLBbTcUScmqa8RYTr168zadIkJk+ezN27d2nRogWDBw/WUXYOqGHDhty9e5fffvvNdBS7YLVaadGiBatWrWLXrl2UKlXKdCQRp6RCKZKAnTx5kjFjxvDzzz/j4uJC165d6d+/P7lz5zYdTV7D/fv3yZgxI99//z39+vUzHcduPHz4kKpVq3Lnzh0CAwPJmDGj6UgiTkdT3iIJ0N69e2nWrBmFChXCYrEwYsQILly4wA8//KAy6cBWr15NeHg4Xl5epqPYlRQpUuDn58fDhw9p1qwZERERpiOJOB0VSpEEwmq1snr1aqpXr06FChUIDg5m6tSpnD17luHDh5M+fXrTESWWLBYLZcqU0Q8FL5A7d26WL1/Ojh07NHorEgdUKEWcXHh4OHPmzKFkyZI0aNCAR48esXz5co4ePUq3bt1IliyZ6YhiA48ePWLVqlUJfnX3P3n77beZNGkSU6ZM4aeffjIdR8SpaMmmiJO6d+8eP/30Ez/88AOXLl3i/fffZ+rUqVStWpVEiRKZjic2tmHDBh4+fKhC+S8++ugjgoOD6dmzJ0WKFOGdd94xHUnEKWhRjoiTuXLlCuPHj2fq1KmEhYXRpk0bBg0aRPHixU1HkzjUqVMn9uzZw5EjR0xHsXsRERHUqVOHQ4cOERQUpEcERGxAU94iTuLYsWN06dKFPHnyMGXKFLp168aZM2eYPXu2yqSTi4iIICAgQKOTL8nd3Z2lS5eSMmVKGjduzMOHD01HEnF4KpQiDm7Hjh00btyYokWLsmbNGkaOHMmFCxfw9vYmR44cpuNJPPjtt9+4deuWCuUryJgxI/7+/pw8eZJOnTqhyTqR2FGhFHFA0dHR+Pn5UblyZapWrcrJkyeZNWsWp0+fZvDgwaRJk8Z0RIlHFouF3Llz8+abb5qO4lBKlSrFvHnzWLp0Kd98843pOCIOTYVSxIE8evSI6dOnU7RoUby8vHBzc2PFihUcPHiQTp06kSRJEtMRJZ5FR0fj6+tLkyZNtNjqNXh5efHll1/y2Wef4e/vbzqOiMPSohwRB3D79m2mTp3KhAkTuH79Ol5eXgwePJiKFSuajiaG7dq1i8qVK7Nt2zaqVq1qOo5Dio6Opnnz5qxbt45du3ZRokQJ05FEHI4KpYgdO3/+PD/88AM//fQTkZGRdOzYkQEDBlCoUCHT0cRODB48mHnz5nHp0iVcXV1Nx3FYDx48oEqVKty/f5/AwEAyZMhgOpKIQ9GUt4gdOnDgAO3atSN//vz8/PPP9OvXj3PnzvHjjz+qTMpTVqsVi8WCp6enymQspUyZEn9/f+7fv0/z5s11PKPIK1KhFLETVquVTZs2Ua9ePUqXLs1vv/3G6NGjOX/+PCNHjiRLliymI4qdOXDgAKdPn9bqbhvJkycPy5Yt47fffmPgwIGm44g4FBVKEcMiIyNZsmQJ5cqVo1atWly9epVffvmFkydP0rdvX1KmTGk6otgpi8VC2rRpqV69uukoTqNatWpMmDCBiRMnMnPmTNNxRByGjl4UMSQ0NJTZs2czduxYTp8+Ta1atVi3bh21a9fWal15KRaLhYYNG5I4cWLTUZxKjx49CA4OpkePHhQpUoQqVaqYjiRi97QoRySehYSEMGnSJCZNmsTt27dp3rw5gwcP5q233jIdTRzIiRMnKFy4ML6+vnh6epqO43TCw8N59913OX78OIGBgXh4eJiOJGLXNOUtEk9Onz5Nr1698PDwwNvbm9atW3Py5EkWLlyoMimvzNfXl+TJk1OnTh3TUZxS4sSJWbZsGUmTJsXT05PQ0FDTkUTsmkYoReJYUFAQPj4+LFu2jPTp09O7d28+/vhjMmbMaDqaOLCKFSuSM2dOli1bZjqKU9u/fz9VqlShYcOGLFy4UI+jiPwNjVCKxAGr1cratWupWbMm5cqVIygoiEmTJnHu3Dk+//xzlUmJlYsXL7Jnzx6t7o4Hb7zxBnPmzGHx4sV89913puOI2C0VShEbioiIYN68eZQuXZr69evz4MEDli5dyokTJ+jRowfJkyc3HVGcgJ+fH+7u7jRo0MB0lAThgw8+4LPPPmP48OGsWLHCdBwRu6QpbxEbuH//PjNmzGDcuHFcuHCB9957j8GDB1OtWjVNkYnN1axZk6RJk7J69WrTURKM6OhomjZtysaNG9m9ezfFihUzHUnErqhQisTC1atXmTBhAlOnTuXBgwe0bt2aQYMGUbJkSdPRxEmFhISQJUsWpk2bRpcuXUzHSVDu379PpUqVePToEXv37iV9+vSmI4nYDU15i7yG48eP07VrV3Lnzs3EiRPp3Lkzp0+fZs6cOSqTEqcCAgIAaNSokeEkCU+qVKkICAjg9u3btGjRgsjISNORROyGRihFXsGuXbvw9vbG39+fLFmy0LdvX7p3707atGlNR5ME4v333+fBgwds2bLFdJQEa9OmTdSpU4fevXszbtw403FE7IJGKEX+RXR0NAEBAVStWpXKlStz9OhRpk+fztmzZxk6dKjKpMSbe/fusWHDBq3uNqxmzZr88MMP/PDDD/z888+m44jYBRVKkb/x+PFjZs6cSfHixWncuDEA/v7+HDlyhM6dO5MkSRLDCSWhWb16NeHh4Xh5eZmOkuD17NmTLl260K1bN3bt2mU6johxmvIW+R937txh2rRpjB8/nqtXr9K4cWMGDx5M5cqVTUeTBK558+acPXuWvXv3mo4ixBzPWLNmTU6ePElQUBA5c+Y0HUnEGI1Qivzl4sWLDBo0CA8PDz7//HMaNGjAkSNH8PX1VZkU48LCwli9erWmu+1I4sSJWb58OYkTJ8bT05OwsDDTkUSMUaGUBO/QoUN06NCBvHnzMmPGDHr16sXZs2eZPn06RYoUMR1PBIANGzbw8OFDFUo7kyVLFvz8/Dhy5AhdunRBk36SUKlQSoJktVrZsmULDRo0oGTJkmzatAlvb28uXLjAqFGjyJYtm+mIIs+wWCwUL16cQoUKmY4i/+Ott95i9uzZLFiwAB8fH9NxRIxwMx1AJD5FRUXh6+uLt7c3gYGBlCxZkrlz59KyZUvc3d1NxxN5oYiICAICAujVq5fpKPI3WrRowYEDBxg6dCglSpTgvffeMx1JJF5phFIShLCwMKZOnUrhwoVp1qwZKVOmZM2aNQQHB9OuXTuVSbFrW7du5fbt25rutnNff/0177//Pq1ateLo0aOm44jEK63yFqd28+ZNpkyZwsSJE7l58yYffPABgwcPpmzZsqajiby0jz/+mLVr13Lq1CmdDW/n7t27R6VKlYiIiGDPnj2kS5fOdCSReKERSnFKZ8+epU+fPnh4ePDtt9/SrFkzTpw4weLFi1UmxaFER0fj6+tLkyZNVCYdQOrUqfH39yckJIRWrVoRFRVlOpJIvFChFKfy+++/06pVKwoUKMCCBQsYPHgw586dY/LkyeTPn990PJFXtnv3bq5evarpbgdSoEABlixZwq+//sonn3xiOo5IvFChFIdntVpZv349tWvXpkyZMuzZs4fx48dz/vx5vvzySzJlymQ6oshrs1gsZM2alYoVK5qOIq/g3XffZcyYMYwZM4a5c+eajiMS57TKWxxWREQES5cuxdvbm+DgYMqUKcOiRYto2rQpbm76V1scn9VqxWKx4OnpiYuLfv53NH369CE4OJiPPvqIwoULU6FCBdORROKMvkOJw3nw4AHjx4+nQIECtGnThqxZs7Jx40YCAwNp0aKFyqQ4jeDgYM6cOaPpbgeVKFEipk6dyltvvYWXlxeXL182HUkkzqhQisO4du0aI0aMwMPDg0GDBvHOO++wf/9+1q5dS82aNbVgQZyOxWIhbdq0VK9e3XQUeU1JkiTBYrHg6uqKl5cXjx49Mh1JJE6oUIrd+/PPP+nevTu5c+fmhx9+oGPHjpw6dYp58+ZRunRp0/FE4ozFYqFRo0baJ9XBZc2aFT8/Pw4cOMBHH32k4xnFKalQit3as2cPTZs2pXDhwvj6+vL5559z4cIFxo4di4eHh+l4InHq+PHjHD58WNPdTqJMmTLMmjWLefPmMXbsWNNxRGxOD5uJXYmOjmb16tV4e3uzbds2ChUqxLRp02jXrh1JkyY1HU8k3vj6+pI8eXLq1KljOorYSKtWrQgODmbIkCGUKFGCunXrmo4kYjM6KUfsQnh4OAsWLMDHx4cjR45QsWJFhgwZQqNGjXB1dTUdTyTelS9fnty5c7N06VLTUcSGoqKiaNy4Mdu3b2fv3r0UKlTIdCQRm9CUtxh19+5dfHx8yJs3L506dSJ//vxs27aNnTt34uXlpTIpCdL58+cJDAzUdLcTcnV1Zf78+WTLlo1GjRpx9+5d05FEbEKFUoy4dOkSQ4YMwcPDg+HDh1OvXj2OHDlCQEAAVatW1YptSdD8/PxInDgxDRo0MB1F4kCaNGnw9/fn2rVrOp5RnIamvCVeHTlyhNGjR/PLL7+QLFkyevToQZ8+fciePbvpaCJ2o3r16qRIkYJVq1aZjiJxaP369dSvX59Bgwbx/fffm44jEisaoZQ4Z7Va2bZtGw0bNqR48eKsX7+eb7/9lgsXLvDdd9+pTIr8l+vXr7Nt2zZNdycAderUwcfHB29vb+bPn286jkisaJW3xJmoqCj8/f3x9vZmz549FC9enJ9//plWrVqROHFi0/FE7FJAQAAAjRo1MpxE4kP//v0JDg6mS5cuFCpUiHLlypmOJPJaNOUtNhcWFsbcuXMZM2YMf/75J9WqVWPIkCHUr19fz0aK/Iv33nuPsLAwNm/ebDqKxJNHjx5RvXp1Lly4QFBQENmyZTMdSeSVacpbbObWrVt888035MmThx49elCqVCl2797Nli1beO+991QmRf7F3bt3+fXXXzXdncAkTZoUi8UCQJMmTXQ8ozgkFUqJtXPnztGvXz88PDz4+uuvadKkCcePH2fZsmVUqFDBdDwRh7Fq1SoiIiLw9PQ0HUXiWfbs2fHz8+OPP/6gR48eOp5RHI4Kpby2/fv306ZNG/Lnz8/cuXMZMGAA58+fZ+rUqRQsWNB0PBGHY7FYKF++PLly5TIdRQwoV64cM2bM4Oeff2b8+PGm44i8Ei3KkVditVrZtGkT3t7erF+/nty5czN27Fg+/PBDUqZMaTqeiMMKDQ1lzZo1fP7556ajiEFt27YlODiYgQMHUrx4cWrXrm06kshL0QilvJTIyEgWLVpEmTJlePfdd7lx4wYLFizg5MmT9OnTR2VSJJbWr19PaGgoXl5epqOIYd999x116tShRYsW/Pnnn6bjiLwUrfKWf/Tw4UNmzZrF2LFjOXv2LLVr12bIkCHUqlVLi2xEbKh9+/b88ccfHDx40HQUsQN37tyhQoUKuLq6snv3blKnTm06ksg/0gilvNCNGzf44osv8PDwoH///lSuXJnff/+d9evX8+6776pMithQeHg4K1as0OpueSpt2rQEBARw+fJl2rRpo+MZxe6pUMozTp48yccff4yHhwejR4+mXbt2nDx5kvnz5/Pmm2+ajifilLZs2cKdO3dUKOUZhQsXZuHChaxatYrPPvvMdByRf6RCKQAEBgbSrFkzChcuzLJlyxg+fDjnz5/nhx9+IE+ePKbjiTg1i8VCvnz5KFWqlOkoYmfq16/P999/z7fffsuiRYtMxxH5W1rlnYBZrVbWrFmDj48PW7ZsoUCBAkyePJkOHTqQLFky0/FEEoSoqCj8/Pxo166dHiWRFxo0aBAHDhzgww8/pGDBgpQpU8Z0JJHnaIQyAQoPD2fu3LmUKlWKBg0aEBoayrJlyzh27Bjdu3dXmRSJR7t27eLatWua7pa/lShRIn766SeKFy+Op6cnV69eNR1J5DkqlAnIvXv3GDNmDPny5aNDhw7kzp2brVu3snv3bpo2bYqrq6vpiCIJjsViIVu2bDpVSv5RsmTJ8PPzIzIykqZNm/L48WPTkUSeoUKZAFy5coVhw4bh4eHBsGHDqF27NocOHWLlypW88847mmYTMcRqteLr64uXlxcuLvp2LP8sR44c+Pr6EhQURM+ePXU8o9gVPUPpxI4dO8bo0aOZN28eSZIkoXv37vTt25ccOXKYjiYixBxfevbsWU13y0urWLEiP/30Ex07dqR06dL07t3bdCQRQIXSKe3YsQNvb28CAgLIli0bX3/9Nd26dSNNmjSmo4nIf7FYLKRPn5533nnHdBRxIB06dCA4OJj+/ftTrFgxatWqZTqSiE7KcRbR0dEEBATg4+PDzp07KVq0KIMHD6Z169YkSZLEdDwReYHixYtTvnx5Zs+ebTqKOJjIyEjee+899u3bx969e8mfP7/pSJLAJeiHdqxWuH4dzp6FEydiXq9fj/m8o3j06BEzZsygWLFieHl54erqyooVKzh06BCdOnVSmRSxU8eOHePIkSOa7pbX4ubmxuLFi0mfPj2NGzfm/v37piNJApegprxDQmDTJti3D/bujXl90X+DqVJBmTJQvnzMa82akDFj/Of9J7dv3+bHH39k/PjxXL9+HU9PT2bPnk2lSpVMRxORl+Dr60uKFCmoXbu26SjioNKlS0dAQAAVKlSgXbt2WCwWLe4SY5x+yttqhd27YfJkWLwYIiPBzS3m9d88eZ+bG7RsCT17QoUKYHJR9JPTa6ZPn05ERAQdOnRg4MCBFCpUyFwoEXll5cqVI1++fCxevNh0FHFwq1atomHDhgwfPpyvv/7adBxJoJy6UPr7w4gRcOjQy5fIv/Pk60uWhJEjoVEj2+V8GQcOHGD06NEsXLiQlClT0rNnT3r37k2WLFniN4iIxNr58+fJnTs3ixYtokWLFqbjiBP47rvvGDZsGEuWLKFZs2am40gC5JSF8uZN6N0bFi4EFxeIjrbdtZ9cr1UrmDgRMmSw3bX/l9VqZcuWLXh7e7N27Vo8PDzo378/nTt3JlWqVHF3YxGJU+PHj2fIkCGEhITov2WxCavVSps2bfDz82PHjh28+eabpiNJAuN0hdLPD7p0gTt3ICoq7u7j6gpp08KMGeDpadtrR0ZGYrFY8Pb2Zt++fZQqVYohQ4bQvHlz3N3dbXszEYl31apVI3Xq1KxYscJ0FHEioaGhvP3229y4cYOgoCAyZ85sOpIkIE7z9K7VCqNGgZcX3L4dt2USYq5/+3bM/b791jYrw0NDQ5kyZQqFCxemRYsWpE2blnXr1rF//37atGmjMiniBK5du8a2bdu0ultsLnny5Pj5+REeHk7Tpk0JDw83HUkSEKcolFYrfPopDB8e82tbTnH/kyf3eXLv1y2VISEhfPXVV+TOnZvevXtTvnx59u3bx6+//kqdOnV0NKKIEwkICMDFxYWGDRuajiJOKFeuXFgsFvbu3Uvv3r11PKPEG6eY8h416v/LpOkcw4a9/PtPnz7N2LFjmTVrFgCdO3dmwIAB5M2bN44Siohp9evXJzw8nI0bN5qOIk5s1qxZdO7cmcmTJ/Pxxx+bjiMJgMMXSj+/mGlne+HnB40b//N79u3bh4+PD0uXLiV9+vT07t2bjz/+mIz2ttmliNjUnTt3yJw5M+PGjaNnz56m44iT69u3L1OmTGHDhg1Ur17ddBxxcg5dKG/ehMKF4dYt+zjdxsUF0qWD48efX/1ttVpZv3493t7ebNq0iXz58jFo0CA6dOhA8uTJzQQWkXg1f/582rZty8WLF8mRI4fpOOLkIiMjqVevHvv37ycwMFCzXxKnHPoZyt69Y1Zz20OZhJhnKu/cgT59/v9zERER/PLLL7zxxhvUq1ePe/fusWTJEk6cOEGPHj1UJkUSEIvFQsWKFVUmJV48OZ4xbdq0NG7cmAcPHpiOJE7MYQulv3/MPpNxvZr7VUVFwYIFsHhxKOPGjSN//vy0a9eOHDlysHnzZvbu3UuzZs1wdXU1HVVE4lFoaChr1qzR6m6JVxkyZMDf358zZ87Qvn17ouNr1aokOA455W21QqlScORI/K3ofhWJEkWTKNEREiV6kzZtWjNo0CBKlixpOpaIGOTr60uTJk34888/KVCggOk4ksAEBATg6enJ559/zpdffmk6jjghhyyUu3ZB5cqmU/w7P79rNG6soxFFBNq1a0dwcDAHDhwwHUUSqG+++YYRI0awbNkymjZtajqOOBmHnPKePDnmbG175uYGy5apTIoIhIeHs2LFCk13i1GffvopzZs3p3379gQHB5uOI07G4UYoQ0IgWzaIjIzNVS4BS4HVwDHgKpAeqAIMASrENiYQUyqvXAHtBiSSsK1bt4569eoRHBxMqVKlTMeRBOzhw4dUrVqV27dvExgYSKZMmUxHEifhcCOUmzbFtkwCTAT6A6eB2sBAoCrgD1QGlsT2BkBMzs2bbXIpEXFgFouF/Pnz61lqMS5FihT4+/sTGhpKs2bNiIiIMB1JnITDFcp9+2wx3V0e+A04CcwEvgWWAZsBV6AH8Di2N8HNLSaviCRcUVFR+Pn50aRJEx2jKnbBw8MDi8XCzp076du3r+k44iQcrlDu2WOLEcomwNsv+PzbQA3gFnAwtjchMhL27o31ZUTEge3cuZPr16/r+UmxK1WrVmXy5MlMnTqVadOmmY4jTsDOl7Y8y2qF33+P67u4//Vqm781QUExuTUwIZIwWSwWsmfPTvny5U1HEXlG165dCQ4OplevXhQtWpR33nnHdCRxYA61KOf6dcgSpwunzwOFgHTARWKmv2Pv2jXInNkmlxIRB2K1WsmTJw8NGzZk0qRJpuOIPCciIoK6dety8OBBgoKCyJ07t+lI4qAcaso7NDQurx4BtCPm2UlvbFUmAcLCbHYpEXEgv//+O+fPn9d0t9gtd3d3lixZQqpUqWjUqBEPHz40HUkclEMVyvDwuLpyNPAhMQt1uhJTLG3ncezX94iIA7JYLKRPn15TiWLXMmbMiL+/P6dOnaJjx4440MSl2BGHKpSJE8fFVa3ElMhfgLbAjza/Q5IkNr+kiDgAi8VC48aNcbP3kxgkwStZsiTz5s1j2bJljBw50nQccUAOVSiTJ7f1FaOBzsAsoBXwM3HxtyRZMptfUkTs3NGjRzl27Jimu8VheHl58dVXX/H555/j5+dnOo44GIcqlJkyQapUtrpaNNAFmA20AOZhy+cmn0iRIor06aNsfl0RsW8Wi4WUKVPy7rvvmo4i8tJGjBhB06ZNadeuHYcOHTIdRxyIQ63yBqheHbZuje1VnoxM/gw0AxYQNzsoRQNbSJq0ASVKlKBUqVJPP0qWLElGncko4rTKlClDwYIFWbRokekoIq/kwYMHVKlShfv37xMYGEiGDBlMRxIH4HCF8pNPYOzY2G5u/iXwFZAS6MuLy6Qn8EZsboKbm5UPPjhPhQq+HDhwgAMHDnDo0CEe/7VKJ3v27M+UzFKlSlG4cGESx83DoiIST86ePUvevHlZvHgxzZs3Nx1H5JWdPXuWcuXKUbJkSdatW4e7u/u/f5EkaA5XKJcsgRYtYnuVjsCcf3nP7L/eFztLlkCzZv//68jISE6ePPm0YD75OHfuHBCzhUPRokWfK5pZs2bVsW0iDmLcuHEMGzaMGzdukMp2z+mIxKvffvuNWrVq0b17dyZOnGg6jtg5hyuUISGQLZstjl+Me25ucOUKvMzM9p07dzh48OAzJfPgwYNP9wTLmDEjpUqVonTp0k9LZrFixUiaNGkc/ylE5FW9/fbbpEuXjoCAANNRRGLlxx9/pEePHkyfPp0uXbqYjiN2zOEKJUDbtrB4sX2XSjc3aNkS5s17/WtER0dz5syZ50YzT506hdVqxcXFhcKFCz83mpkrVy6NZooYcvXqVbJnz86sWbPo2LGj6TgisdajRw9mzpzJpk2bqFq1quk4YqccslDu2gWVK5tO8e927YKKFW1/3QcPHnD48OHniuadO3cASJMmzXMls0SJEqRMmdL2YUTkGdOmTaNnz55cu3ZNixnEKYSHh1O7dm2OHTtGYGAgHh4epiOJHXLIQmm1QunScPgwREebTvM8FxcoUQL274f4Gii0Wq1cvHiRAwcOEBwc/LRkHj9+nOi//iblz5//acF8MnWeN29eXFwcavcoEbtWt25doqKi+PXXX01HEbGZGzduUK5cOdKnT8/27dtJbvuNocXBOWShBAgIgMaNTaf4e/7+0KiR6RTw6NEjjhw58sxIZnBwMCEhIQCkSJGCkiVLPrelUdq0ac0GF3FAt2/fJnPmzIwfP56PP/7YdBwRmwoODqZy5co0bNiQhQsX6tEqeYbDFkqA1q1jVlFH2dG+4a6uMavQ5883neTvWa1Wrl279tyU+ZEjR4iIiADAw8PjuWnzggUL6gg5kX8wb9482rdvz6VLl8iePbvpOCI2t3z5cj744AO++eYbPv30U9NxxI44dKG8eRMKF4bbt+1j6tvFBdKlg+PHwREfnYqIiOD48ePPjWZevnwZgCRJklC8ePHnimamTJkMJxexD15eXly7do2dO3eajiISZ7744gu+/vpr/P39adiwoek4YicculAC+PmBl5fpFP/Pz8++p+JfR0hIyHNbGh06dIhHjx4BkC1btudKZpEiRbRBuyQoDx8+JGPGjHz99dcMGjTIdByROBMdHc0HH3zAr7/+yu7duylWrJjpSGIHHL5QAowaBcOHm04Rk2PYMNMp4kdUVNQLN2g/e/YsAG5ubi/coD1btmx67kac0pOpwJMnT5I/f37TcUTi1IMHD6hUqRJhYWHs3buX9OnTm44khjlFobRaYwrlt9+ayzBsGHzzTfyt6rZXd+/e5dChQ88VzQcPHgCQIUOG50pm8eLFSZYsmeHkIrHTpk0bDh8+zP79+01HEYkXZ86coVy5crz55pusWbNGz9gncE5RKCGmVH73HXz6acyzjPHzTGUU4Mq338LQofFxP8cUHR3N2bNnnyuZJ0+efLpBe6FChZ4rmh4eHhrNFIcQHh5OpkyZGDhwIJ9//rnpOCLxZvPmzdSuXZtevXrxww8/mI4jBjlNoXzC3x86d4Y7d+J29berK7i7PyAiogNbtw6gSpUqcXczJ/Xw4cMXbtB++/ZtAFKnTv3CDdp1NrLYm7Vr11K/fn0OHjxIiRIlTMcRiVeTJ0+mV69ezJo1i06dOpmOI4Y4XaGEmNXfvXvDwoW2H618cr3WrWHMmHBatIg5PSAoKIhcuXLZ7kYJlNVq5dKlS8+VzGPHjhH1108I+fLle65o5s+fXxu0izEfffQRW7Zs4fjx4xpVlwTHarXSrVs35syZw5YtW6hUqZLpSGKAUxbKJ/z94bPP4ODBmLO1Y3P295OvL1kSRo78/03Ln5wekCFDBrZt26bTA+LIo0ePOHbs2DOnAAUHB3Pjxg0AkidP/sIN2tOlS2c4uTi7qKgosmXLxocffsh3331nOo6IEeHh4dSqVYs///yToKAgcubMaTqSxDOnLpQQ82zlnj0weTIsWhRTCt3d4a/9u//RkxLp7g4tW0LPnlC+/PMLb3R6gDl/t0F7eHg4ALly5XpuNLNQoUJ6eFxs5rfffqNatWrs2bOH8uXLm44jYsz169cpW7YsmTNnZtu2bVpsmcA4faH8byEhsHkzBAVBYGDM6/37z78vVSooWzamPJYpAzVqQMaM/3ztZcuW0axZM0aNGsWwhLJ3kJ2KiIjgxIkTzxXNixcvAjEbtBcrVuy5opk5c2bDycUR9evXj+XLl3Pu3Dk9diEJ3v79+6lcuTKenp7Mnz9fAywJSIIqlP/LaoUbNyAsDB4/hiRJIFkyyJTp9bb/+fzzzxk5cqROD7BTt27derpB+5Op80OHDhEWFgZAlixZKF269HMbtCdJksRwcrFXVquV3Llz4+npyYQJE0zHEbELS5YsoUWLFnz33Xd88sknpuNIPEnQhdLWoqOjadq0KRs3btTpAQ4iKiqKU6dOPTeaeebMGSBmg/YiRYo8N5qZPXt2/eQtBAUFUa5cOTZv3kz16tVNxxGxGyNGjGDUqFGsWLGCBg0amI4j8UCF0sbu379P5cqVefToEXv27NHpAQ7q3r17L9yg/f5fz0ikT5/+hRu0a1FWwvLpp58yffp0rly5oudyRf5LdHQ0Xl5ebNmyhd27d1O0aFHTkSSOqVDGgdOnT1OuXDneeustnR7gRKxWK+fOnXuuZJ44cQKr1UqiRIkoWLAgpUqVembqPHfu3BrNdEJWq5UiRYrw9ttvM2PGDNNxROzOvXv3qFy5MuHh4ezZs0e7bjg5Fco4smnTJurUqUPv3r0ZN26c6TgSh0JDQ1+4QfutW7cASJUq1Qs3aE+dOrXh5BIbR44coXjx4qxatYr33nvPdBwRu3Tq1CnKly9P2bJlWbVqlQZYnJgKZRyaNGkSvXv3Zvbs2XTs2NF0HIlHVquVy5cvv3CD9si/NkTNmzfvCzdod3V1NZxeXsbIkSPx9vbmxo0bWrgl8g82btxI3bp16du3L2PGjDEdR+KICmUcslqtfPTRR8ydO1enBwgAjx8/5tixY88VzatXrwKQLFkySpQo8bRgli5dmpIlS+pZXDv01ltvUaRIERYsWGA6iojdmzBhAn379mXOnDm0b9/edByJAyqUcezJ6QEnT54kKCiIHDlymI4kduj69evPlczDhw8/3aA9Z86cL9yg3d3d3XDyhOnMmTPky5ePpUuX8sEHH5iOI2L3rFYrXbp0Yf78+WzdupUKFSqYjiQ2pkIZD56cHpAlSxZ+++03nR4gLyUyMvKFG7RfuHABgMSJE79wg/YsWbIYTu78xo4dy/Dhw7lx4wYpU6Y0HUfEITx+/JiaNWty5swZAgMDNcDiZFQo48kff/xBlSpV8PLy4pdfftGqX3ltt2/ffrpB+5OPgwcPEhoaCkDmzJmfK5lFixYladKkhpM7j6pVq5IxY0b8/PxMRxFxKFevXqVcuXJky5aNrVu3aoDFiahQxqPFixfTsmVLvv/+e4YMGWI6jjiR6OhoTp8+/cwpQAcOHOD06dMAuLq6vnCD9hw5cuiHm1d05coVcuTIwc8//6xnwURew759+6hatSoffPABc+fO1fcgJ6FCGc+GDx/Ot99+y8qVK7XViMS5+/fvv3CD9nv37gGQLl26F27QniJFCsPJ7dePP/5I7969uXbtmhZLibymhQsX0rp1a3x8fBg0aJDpOGIDKpTxLDo6Gk9PT7Zu3cqePXsoUqSI6UiSwFitVs6fP//CDdqjo6NJlCgRBQoUeK5o5smTBxcXF9PxjatTpw5Wq5UNGzaYjiLi0IYNG4a3tzerVq2iXr16puNILKlQGnDv3j0qVapEZGQku3fv1ukBYhfCwsI4cuTI04L5ZOr85s2bAKRMmZKSJUs+cwpQyZIlE9QG7bdu3SJLlixMmDCBHj16mI4j4tCioqJo3Lgx27dvZ8+ePRQuXNh0JIkFFUpDTp06Rbly5ShfvjyrVq3SZtZil6xWK1euXHluNPPo0aNPN2jPkyfPc6OZBQoUcMp/p+fOnUvHjh25dOkS2bJlMx1HxOHdu3ePihUrEh0dze7du0mbNq3pSPKaVCgN+vXXX6lXrx79+vVj9OjRpuOIvLTw8PAXbtB+5coVAJImTfrMBu1PPjJkyGA4eex4enpy48YNduzYYTqKiNP4888/KV++PBUrVmTlypVO+cNoQqBCadj48ePp16+fTg8Qp3Djxg0OHjz4zErzw4cP8/jxYwCyZ8/+zClApUqVonDhwg6xQfuDBw/IlCkTI0eOZODAgabjiDiV9evXU79+fQYOHIi3t7fpOPIaVCgNs1qtdO7cmQULFvDbb79Rvnx505FEbCoyMpI///zzudHM8+fPA+Du7v63G7Tb03Yiy5Yto1mzZpw6dYp8+fKZjiPidMaNG8eAAQOYN28ebdu2NR1HXpEKpR14/PgxNWrU4OzZswQFBZE9e3bTkUTi3J07d164QfvDhw8ByJQp03Mls1ixYsY2aG/dujVHjx7ljz/+MHJ/EWdntVrp1KkTixYtYtu2bZQrV850JHkFKpR24snpAdmzZ2fr1q061UQSpOjoaM6cOfNMyQwODubUqVNAzAbthQoVeqZkli5dmpw5c8bpaObjx4/JlCkTgwcP5rPPPouz+4gkdI8ePaJ69epcuHCBoKAgLX5zICqUduTJ6QHNmjVjzpw5djXdJ2LSgwcPXrhB+927dwFImzbtc6OZJUqUsNkG7atXr6ZBgwYcOnSI4sWL2+SaIvJiV65coWzZsuTKlYstW7ZogMVBqFDamSenB4wePVoP/ov8A6vVyoULF54rmcePH3+6QXv+/PmfK5p58+Z95Q3au3TpwrZt2zh27Jh+0BOJB4GBgbz99tu0bNmS2bNn6787B6BCaYeGDh2Kj48Pq1evpm7duqbjiDiUsLAwjh49+ty0eUhICAApUqSgZMmSz5TMkiVL/u3+d5GRkWTLlo0uXbrw7bffxuOfRCRhmz9/Pm3btmXs2LH079/fdBz5FyqUdui/Tw/Yu3cvhQoVMh1JxKFZrVauXr36wg3aIyIiAPDw8HjmFKAnG7Rv376dGjVqsHfvXi0SEIlnQ4YMYcyYMaxZs4Y6deqYjiP/QIXSTt29e5eKFStitVrZs2cPadKkMR1JxOmEh4dz/Pjx54rm5cuXgZgN2lOlSsXDhw8ZOXLk08KZMWNGw8lFEoaoqCgaNmzIrl272Lt3LwULFjQdSf6GCqUde3J6QKVKlVixYoVODxCJJyEhIRw8eJD9+/czYsQIUqZMyb1793j06BEA2bJle+7ZzCJFipA4cWLDyUWcz507d6hYsSIuLi7s2rVLAyx2SoXSzj05PWDQoEF8//33puOIJCh79+6lQoUKbNmyhapVq3Ly5MlnTgE6cOAA586dA8DNzY2iRYs+cwpQqVKlyJo1qxYUiMTSiRMnKF++PFWrVsXf318DLHZIhdIBjB07loEDB/LLL7/Qpk0b03FEEoyhQ4cya9Ysrly58rf/A7t79+4LN2h/8OABABkzZnzhBu3JkiWLzz+KiMNbu3YtDRo0YMiQIVogZ4dUKB2A1WqlY8eOLFmyhG3btlG2bFnTkUScntVqpVChQlSvXp3p06e/0tdGR0dz9uzZ557NPHnyJFarFRcXl+c2aC9VqhQeHh4azRT5B6NHj2bw4MEsWLCAVq1amY4j/0WF0kE8OT3g4sWLBAYG6vQAkTh26NAhSpYsyerVq6lfv75Nrvnw4UMOHz78dCujJ0Xzzp07AKRJk+aZLY1Kly5NiRIlSJkypU3uL+LorFYr7du3Z9myZWzfvp0yZcqYjiR/UaF0IJcvX6ZcuXJ4eHiwefNmnR4gEof+85//MGbMGK5fv06SJEni7D5Wq5WLFy++cIP2qKgogBdu0J4vX75X3qBdxBmEhYVRrVo1rly5QmBgIFmzZjUdSVChdDhPTg9o1aoVs2bN0vSYSBx54403KF68OPPnzzdy/0ePHr1wg/YbN24AkDx58hdu0J4uXTojeUXi06VLlyhXrhx58uRh8+bNcfpDn7wcFUoH9Msvv9CuXTvGjRtHv379TMcRcTqnTp2iQIECLFu2jKZNm5qO84xr1649N5p55MgRwsPDAciVK9dzo5mFChXCzc3NcHIR29qzZw/VqlWjTZs2zJgxQwMshqlQOqjBgwczduxY1q5dS+3atU3HEXEqo0eP5rPPPiMkJIQUKVKYjvOvIiIiXrhB+6VLlwBIkiQJxYsXf65oZsqUyXBykdiZO3cuHTp0YPz48fTp08d0nARNhdJBRUVF8f7777Nnzx727t1LgQIFTEcScRqVK1cmS5Ys+Pr6mo4SKzdv3nxuS6NDhw4RFhYGQNasWV+4QbumD8WRDBw4kPHjx7Nu3Tpq1aplOk6CpULpwO7cuUOFChVwdXVl9+7dpE6d2nQkEYd3+fJlcuTIwdy5c2nXrp3pODYXFRXFqVOnnhvNPHPmDBCzQXuRIkWeWWleqlQpsmXLpilFsUuRkZE0aNCAwMBAAgMDyZ8/v+lICZIKpYM7fvw4FSpU4O2338bPz0+nB4jE0pQpU+jbty/Xr19PUAtc7t2799xo5oEDB55u0J4hQ4YXbtCePHlyw8lF4Pbt21SoUAF3d3d27dqlARYDVCidwJo1a2jQoAFDhw5l1KhRpuOIOLR3330XV1dX1q1bZzqKcdHR0Zw7d+65kvnnn38+3aC9YMGCzxXN3LlzazRT4t2xY8eoUKEC1apVw8/PT9tqxTMVSifh4+PDkCFDWLhwIS1btjQdR8Qh3bp1i8yZMzN58mS6detmOo7dCg0NfbpB+39vaXT79m0AUqdO/cItjVKlSmU4uTi71atX8/777/Ppp58ycuRI03ESFBVKJ/Hk9IDly5ezfft23nrrLdORRBzOnDlz6NSpE5cvX9Zmya/IarVy+fLl504BOnbs2NMN2vPly/fCDdr1qI7Y0vfff8/QoUNZvHgxzZs3Nx0nwVChdCJhYWG88847XL16laCgILJkyWI6kohDady4Mbdu3WLbtm2moziNx48fP7dB+4EDB7h27RoQs0F7iRIlnhvNTJ8+veHk4qisVitt27bF19eXHTt28Oabb5qOlCCoUDqZS5cuUbZsWfLly8emTZu0/YfIS3rw4AEZM2bk22+/pX///qbjOL1r1649twjo8OHDTzdoz5kz5ws3aHd3dzecXBxBWFgYb7/9NtevXycoKIjMmTObjuT0VCid0O7du6lWrRrt2rVj+vTpejhe5CUsXbqU5s2bc+bMGfLkyWM6ToIUERHBn3/++cxzmQcOHODixYsAJE6cmGLFij3dyujJh8qCvMjFixcpW7YsBQsWZOPGjSROnNh0JKemQumk5syZQ8eOHZkwYQK9e/c2HUfE7rVq1YoTJ06wb98+01Hkf9y6deuFG7SHhoYCkCVLludGM4sWLaoZGmHXrl1Ur16dDh06MG3aNA2wxCEVSic2YMAAJkyYoNMDRP7Fo0ePyJQpE0OHDmX48OGm48hLiIqK4vTp0889m3n69GkAXF1dn9mg/clHjhw5VCoSmNmzZ/Phhx8yadIkevbsaTqO01KhdGKRkZG899577Nu3j8DAQPLly2c6kohdWrVqFe+//z5HjhyhaNGipuNILNy/f59Dhw49VzTv3bsHQLp06Z47Bah48eLaoN3J9evXj0mTJrFhwwZq1KhhOo5TUqF0crdv36Z8+fIkSZKEXbt2aR84kRfo3LkzO3fu5OjRo6ajSBywWq1/u0F7dHQ0iRIl+tsN2rU5tnOIjIykfv36/PHHHwQGBpI3b17TkZyOCmUCcPToUSpUqEDNmjWxWCz6BinyXyIjI8maNSvdunXjm2++MR1H4lFoaChHjhx5boP2W7duAZAqVaoXbtCuY/0c061btyhfvjzJkiVj586dGmCxMRXKBGLVqlU0bNiQ4cOH8/XXX5uOI2I3Nm/eTM2aNQkKCqJMmTKm44hhVquVK1euPDeaefToUSIjIwHIkyfPMyWzdOnS5M+fXxu0O4AjR45QsWJFatWqxfLlyzXAYkMqlAnId999x7Bhw1iyZAnNmjUzHUfELvTu3ZuAgADOnj2rxRryt8LDwzl27NgzpwAdOHCAq1evApAsWbIXbtCeIUMGw8nlf61YsYLGjRvz2Wef8dVXX5mO4zRUKBMQq9VKmzZt8Pf3Z8eOHbzxxhumI4kYFR0djYeHB82aNWPcuHGm44gDun79+gs3aH/8+DEAOXLkeO7ZzMKFC2uDdsNGjRrF8OHDWbZsGU2bNn3lr7da4cYNCA2F8HBInBiSJ4dMmSCh/lyqQpnAhIaG8vbbbxMSEkJgYKA2BJYEbc+ePVSsWJHffvuNt99+23QccRKRkZHPbND+5OP8+fMAuLu7U6xYseeKps6Pjz9Wq5VWrVqxYsUKdu7cSenSpf/x/SEhsGkT7NsHe/fGvN6///z7UqWCMmWgfPmY15o1IWPGOPpD2BkVygTowoULlCtXTqcHSIL3ySef8PPPP3P58mU9/yZx7vbt20+3NHoydX7w4MGnG7Rnzpz5hRu0J02a1HBy5xQaGkrVqlW5desWgYGBZMqU6Znft1ph926YPBkWL4bISHBzi3n9N0/e5+YGLVtCz55QoYJzj16qUCZQO3fupEaNGnTs2JEff/xRz45JgmO1WilUqBA1a9Zk2rRppuNIAhUdHf3CDdpPnToFxGzQXrhw4eeKZs6cOfV92wYuXLhA2bJlKVKkCBs2bHg6wOLvDyNGwKFDL18i/86Try9ZEkaOhEaNbBTezqhQJmCzZs2ic+fOTJ48mY8//th0HJF4dfDgQUqVKsXatWupW7eu6Tgiz3jw4MELN2i/e/cuAGnTpn2uZJYoUYIUKVIYTu54duzYQY0aNejcuTMjR06ld29YuBBcXCA62nb3eXK9Vq1g4kRwtvVaKpQJXN++fZkyZQobNmygevXqpuOIxJuvvvqKcePGcf36dT32IQ7BarVy4cKFZ6bMDxw4wIkTJ55u0J4/f/5nTgEqVaoUefLk0fY4/2LGjBl07bqSFCkW8uhRMqKi4u5erq6QNi3MmAGennF3n/imQpnARUZGUq9ePfbv36/TAyRBKV26NCVLluSXX34xHUUkVsLCwl64QfvNmzcBSJky5Qs3aE+TJo3h5PbBaoVvv4XhwwGigLh/nvrJaOWoUTB0qHM8W6lCKdy8eZMKFSqQPHlydu7cScqUKU1HEolTJ0+epGDBgixfvpwmTZqYjiNic1arlatXr75wg/aIiAgAcufO/dy0ecGCBRPUAjWrFT79FL77zlyGYcPgm28cv1SqUAoAhw8fpmLFitSuXZtly5ZpekScmo+PD1988QU3btzQM2eSoISHh3P8+PHnps2vXLkCQNKkSSlevPgzpwCVLFmSjE66982oUU9GJs3nGDbMdIrYUaGUpwICAvD09OTzzz/nyy+/NB1HJM5UqlSJbNmyYbFYTEcRsQs3btx44Qbtjx49AiB79uwv3KDdkZ8/9vMDLy/TKf6fnx80bmw6xetToZRnfPPNN4wYMeK1Tw8QsXeXLl0iZ86czJs3j7Zt25qOI2K3IiMjOXny5HPT5ufOnQNiNmgvWrToCzdot/ctjW7ehMKF4datmGlv01xcIF06OH7ccVd/q1DKM6xWKy1btmTlypXs2rWLUqVKmY4kYlOTJ0+mX79+3Lhxg7Rp05qOI+Jw7ty588ItjR4+fAhAxowZnyuZxYsXt6sN2lu3hiVLiNPV3K/K1RVatID5800neT0qlPKchw8fUrVqVW7fvv3C0wNEHFmtWrVwd3dn7dq1pqOIOI3o6GjOnDnzwg3arVYrLi4uL9ygPVeuXPE+munvb9/b9fj7O+bm5yqU8kLnz5+nbNmyFCtWjA0bNuDu7m46kkishYSEkDVrVqZMmcJHH31kOo6I03vw4AGHDx9+rmjeuXMHgDRp0rxwg/a42m3EaoVSpeDIEdtuWm4rLi5QvDgEBzveqm8VSvlb27dvp2bNmnTp0oUpU6aYjiMSa7Nnz6Zz585cuXKFLFmymI4jkiBZrVYuXrz4XMk8fvw4UX/NQT/ZoP2/P/LlyxfrHUh27YLKlW3xp4hbu3ZBxYqmU7waFUr5R9OnT+ejjz7ixx9/pFu3bqbjiMRKw4YNuXv3Lr/99pvpKCLyPx49evTCDdpDQkIASJEixQs3aH+VZ6HbtoXFi2N3Nvf/CwS+AHYB4UBxoB/QOlZXdXODli1h3rzY5otfKpTyr3r16sW0adPYuHEj77zzjuk4Iq/l/v37ZMyYke+//55+/fqZjiMiL8FqtXLt2rXnRjOPHDnydIN2Dw+PF27Q7ubm9sy1QkIgWzZblcktQF0gMdASSANYgDPAN8Cnsbq6mxtcuQKOtP2nCqX8q4iICOrWrcvBgwcJCgoid+7cpiOJvLLFixfTsmVLzp49q3+HRRxcRETE0w3a//vj0qVLACRJkuSZDdpLlSrFmTPl6No1tQ3uHgkUAS4SMzr55l+fvw9UAo4DR4CCsbrLkiXQrFmsLhGvVCjlpYSEhFC+fHlSpUrFzp07dbqIOJwWLVpw6tQpgoKCTEcRkThy8+ZNDh48+MwpQIcOHfprg/bvgAFAbBeZridmdLITMOt/fm8xMSOWw4BRr30HNzcYONDskZCvyu3f3yISs6+Yv78/lSpVomPHjixZssTuN64VeeLRo0esWrWKTz+N3TSUiNi3DBkyUL16dapXr/70c1FRUZw8eZImTdJx5Igtas+Wv17rvOD3nnxua6zuEBkJe/fG6hLxTgc2y0srWbIk8+bNY9myZYwcOdJ0HJGXtmHDBh4+fEiTJk1MRxGReObq6kqhQoW5cCEzYIuBkD//en3RlHY6ION/vef1BQXZxyk+L0uFUl6Jl5cXX331FZ9//jl+fn6m44i8FIvFQtGiRSlSpIjpKCJiwI0bcP++ra5296/XNH/z+6n/6z2v7/79mNyOQoVSXtmIESNo2rQp7dq149ChQ6bjiPyjiIgIAgICNDopkoCFhppO8HrCwkwneHkqlPLKXFxc+Pnnn8mXLx+NGjXi5s2bpiOJ/K3ffvuNW7duqVCKJGDh4ba82pORyb8bhbzH349evprHj21ymXihQimvJWXKlPj7+3P//n2aNWv2dD8wEXtjsVjInTs3b7755r+/WUScUuLEtrzak2cnX/Sc5G0ghNhuGfREkiQ2uUy8UKGU15YnTx6WL1/Otm3bGDBggOk4Is+Jjo7G19eXJk2aaFcCkQQseXJbXq3aX6/rX/B76//nPbGTLJlNLhMvVCglVt555x0mTpzIpEmTmDFjhuk4Is/Ys2cPV65c0XS3SAKXKROkSmWrq9UC8gELgP3/9fn7wNfE7MjYMdZ3SZUqJrejUKGUWOvevTvdu3fn448/Zvv27abjiDxlsVjIkiULlSpVMh1FRAxKlAjeestWV3MDZgDRwNvAR8AgoDRwGPgSKBTru5QtG5PbUahQik2MHz+eSpUq0bRpU86fP286jghWqxWLxYKnpyeurq6m44iIYRUqxJxAYxs1gO1AVWAJMAXIAPwCDI/11d3coHz5WF8mXqlQik0kTpyYZcuWkSxZMjw9PQl11D0axGkcOHCA06dPa7pbRAAoUybmBBrbKQ+sAe4AoUAg0MYmV46MjMnrSFQoxWYyZcqEv78/x48f58MPP0THxItJFouFtGnTPnMEm4gkXDVr2nKEMm65uUGNGqZTvBoVSrGp0qVLM3fuXBYvXsy3335rOo4kYBaLhYYNG5LYtvuFiIiDCg09T4ECQYB9b3Pn5gYtW0LGjKaTvBoVSrG5pk2b8vnnnzNixAhWrFhhOo4kQH/++SeHDh3SdLeIcODAAdq1a0f+/Pm5ePFTwN10pH8UGQk9e5pO8epUKCVOfPHFF3h6etKmTRuOHDliOo4kML6+viRPnpw6deqYjiIiBlitVjZt2kS9evUoXbo0v/32G6NHj+byZQslS4KLnbYfFxcoVSpmAZGjSWTVg24SRx48eEClSpUICwtj7969pE+f3nQkSSAqVqxIzpw5WbZsmekoIhKPIiMjWb58OT4+Puzbt4/SpUszePBgmjdvjrt7zMhkQAA0bmw46D/w94dGjUyneHV22tHFGaRMmZKAgADu3LlDixYtiLTt8jqRF7p48SJ79uzRdLdIAhIaGsrkyZMpVKgQLVu2JG3atKxbt44//viDNm3aPC2TEFPWWrUCe9tNzNUVWrd2zDIJKpQSx/LmzcvSpUvZvHkzgwYNMh1HEgA/Pz/c3d1p0KCB6SgiEsdCQkL48ssv8fDwoE+fPlSoUIF9+/bx66+/UqdOnb89cnXiREib1n6mvl1cYvJMmGA6yeuzk7+V4sxq1KjB+PHjGT9+PLNnzzYdR5ycxWLh3XffJU2aNKajiEgcOX36NL169cLDwwNvb29at27NyZMnWbhwIW+9xJE4GTLAjBkQHR0PYV9CdDTMnBmTy1GpUEq8+Pjjj+natSvdu3dn165dpuOIkwoJCWHr1q2a7hZxUkFBQbRo0YKCBQuyePFihg4dyvnz55kwYQJ58+Z9pWt5esI338RNzlc1apR9P9f5MrQoR+JNeHg4tWrV4s8//yQoKIicOXOajiROZtasWXTt2pUrV66QOXNm03FExAasVivr1q3D29ubzZs3ky9fPgYNGkSHDh1Injx5LK8Nw4eDyW2Thw2LKbaOdG73i2iEUuJN4sSJWb58OYkTJ8bT05OwsDDTkcTJWCwW3n77bZVJEScQERHBvHnzKF26NPXr1+f+/fssWbKEEydO0KNHj1iXSYgpcd98EzNCCPH3TOWT+3z7bcy9Hb1MggqlxLPMmTPj7+/PkSNH6Ny5s45nFJu5d+8eGzZs0HS3iIO7f/8+48aNI3/+/LRv356cOXOyefNm9u7dS7NmzXC18fLsRIliRgn9/CBdurhf/e3qGnMfPz8YOjRu7xWfVCgl3r355pv8/PPPLFy4EG9vb9NxxEmsXr2a8PBwvLy8TEcRkddw9epVPv30Uzw8PBgyZAg1atTgwIEDrF69murVq//tim1badwYjh+H5s1jfm3r0con12vRAk6ccPxnJv+XnqEUY0aMGMGoUaNYsWKFtniRWGvevDlnz55l7969pqOIyCs4fvw4o0ePZu7cuSROnJhu3brRt29fcuXKZSyTvz989hkcPBhztnZstlF+8vUlS8LIkY67z+S/UaEUY6Kjo/Hy8mLLli3s3r2bokWLmo4kDiosLIxMmTIxYsQIhjrTHJKIE9u1axfe3t74+/uTJUsW+vbtS/fu3UmbNq3paEDMgp09e2DyZFi0KKYUurtDRMS/f+2TEunuDi1bxpzNXb68czwr+XdUKMWoe/fuUalSJcLDw9m7dy/p0qUzHUkcUEBAAI0bN+b48eMUKlTIdBwR+RvR0dGsXLkSb29vduzYQeHChRk8eDBt27YlSZIkpuP9rZAQ2LwZgoIgMDDm9f7959+XKhWULRtTHsuUgRo1IGPG+M9rggqlGHfq1CnKlStHuXLlWLVqFW5ubqYjiYPp2LEjQUFBHDp0yHQUEXmBx48f88svvzB69GiOHTtGlSpVGDJkCO+//z4u9nJczSuwWuHGDQgLg8ePIUkSSJYMMmVy7lHIf+J4/xTF6eTPn5+lS5eyceNGPvnkE9NxxMFEREQQEBCg1d0idujOnTt8//335M2bl65du1KkSBF27NjB9u3badSokUOWSYgpjZkzQ+7cUKhQzGvmzAm3TAJoKEjsQq1atRg7dix9+/aldOnStG/f3nQkcRBbt27l9u3bKpQiduTixYv88MMP/PTTTzx+/Jj27dszcOBAihQpYjqaxBEVSrEbvXv3Jjg4mI8++ojChQtToUIF05HEAVgsFvLmzUvp0qVNRxFJ8A4dOoSPjw8LFiwgRYoU9OrVi969e5MtWzbT0SSO6RlKsSuPHz+mZs2anDlzhsDAQHLkyGE6ktix6OhocuTIQevWrRkzZozpOCIJktVqZevWrfj4+LB69Wpy5sxJ//796dq1K6lSpTIdT+KJYz68IE4rSZIkLF++HFdXV7y8vHQ8o/yj3bt3c/XqVU13ixgQFRXFsmXLqFChAjVq1OD8+fPMnTuX06dPM2DAAJXJBEaFUuxO1qxZ8fPz4+DBg3z00Uc6nlH+lsViIWvWrFSqVMl0FJEEIywsjKlTp1K4cGGaNWtGypQpWbNmDQcOHKBdu3a4u7ubjigG6BlKsUtlypRh1qxZtG7dmtKlSzNo0CDTkcTOWK1WLBYLnp6eDrtSVMSR3Lx5kylTpjBx4kRu3rzJBx98wKJFiyhbtqzpaGIHVCjFbrVq1YoDBw7wySefUKJECerVq2c6ktiR4OBgzpw5o+lukTh29uxZxo4dy8yZM7FarXTq1IkBAwaQP39+09HEjmhRjti1qKgoGjduzPbt29mzZw+FCxc2HUnsxOeff87EiRO5fv26pthE4sDvv/+Oj48PS5cuJW3atPTq1YuePXuSKVMm09HEDqlQit27e/cuFStWJDo6mj179tjNOa9iVokSJShTpgxz5swxHUXEaVitVjZs2ICPjw+//vorefPmZeDAgXTq1InkyZObjid2TA8eid1LkyYNAQEBXL9+nVatWhEVFWU6khh2/PhxDh8+rOluERuJiIhgwYIFvPnmm9StW5fbt2+zaNEiTpw4Qc+ePVUm5V+pUIpDKFiwIIsXL2b9+vUMGzbMdBwxzNfXl+TJk1OnTh3TUUQc2oMHDxg/fjwFChSgTZs2ZM2alY0bNxIYGEiLFi1wc9NSC3k5mvIWhzJu3DgGDBjAvHnzaNu2rek4Ykj58uXJnTs3S5cuNR1FxCFdu3aNiRMnMmXKFO7du0erVq0YNGiQTpyS16ZCKQ7lyQrDRYsWsW3bNsqVK2c6ksSz8+fPkzt3bhYsWECrVq1MxxFxKH/++Sdjxozh559/xs3Nja5du9KvXz9y585tOpo4OBVKcTiPHj2ievXqXLhwgaCgIJ0Rm8BMmDCBwYMHc+PGDVKnTm06johD2LNnD97e3vj6+pIpUyb69u1Ljx49SJcunelo4iRUKMUhXblyhbJly5IrVy62bNlC0qRJTUeSeFK9enVSpEjBqlWrTEcRsWvR0dGsXr0aHx8ffvvtNwoVKsSgQYNo166dvmeKzWlRjjikbNmy4efnx/79++nevbuOZ0wgrl+/zrZt27S6W+QfhIeH8/PPP1OyZEkaNmxIeHg4FouFI0eO0LVrV5VJiRMqlOKwypUrx8yZM5kzZw4//PCD6TgSDwICAgBo1KiR4SQi9ufu3bv4+PiQN29eOnXqRP78+dm2bRs7d+7Ey8sLV1dX0xHFiWnKWxzekCFDGDNmDGvWrNE2Mk7uvffeIywsjM2bN5uOImI3Ll26xPjx45k2bRphYWG0a9eOQYMGUbRoUdPRJAFRoRSHFxUVRcOGDdm1axd79+6lYMGCpiNJHLh79y6ZMmVizJgx9O7d23QcEeOOHDnC6NGj+eWXX0iWLBk9evSgT58+ZM+e3XQ0SYBUKMUp3Llzh4oVK5IoUSJ2795NmjRpTEcSG1uwYAFt2rTh/Pnz5MqVy3QcESOsVivbt2/H29ublStXkiNHDvr370/Xrl2164EYpWcoxSmkTZsWf39/rly5Qps2bXQ8oxOyWCyUL19eZVISpKioKCwWC5UqVeKdd97hzJkz/Pzzz5w+fZqBAweqTIpxKpTiNAoXLsyiRYtYs2YNI0aMMB1HbCg0NJQ1a9ZodbckOGFhYUybNo2iRYvStGlTkiZNysqVKzlw4AAdOnQgceLEpiOKACqU4mTq1avH999/z3fffcfChQtNxxEbWb9+PaGhoXh5eZmOIhIvbt26xTfffEOePHno0aMHpUqVYvfu3WzZsoUGDRrg4qL/fYt90TOU4nSsVivt27dn2bJlbN++nTJlypiOJLHUvn17/vjjDw4ePGg6ikicOnfuHOPGjWPGjBlERkbSqVMnBgwYoMWGYvdUKMUphYWFUa1aNa5cuUJgYCBZs2Y1HUleU3h4OFmyZKFPnz589dVXpuOIxIng4GB8fHxYtGgRqVOnplevXvTq1YvMmTObjibyUjRmLk4pWbJk+Pr6EhUVRZMmTXj8+LHpSPKatmzZwp07d/T8pDgdq9XKxo0bqVu3Lm+88Qbbt29n7NixnD9/nv/85z8qk+JQVCjFaeXIkQNfX19+//13Pv74Yx3P6KAsFgv58uWjVKlSpqOI2ERkZCSLFi2iTJkyvPvuu9y4cYMFCxZw8uRJ+vTpQ8qUKU1HFHllKpTi1CpUqMBPP/3ErFmzmDhxouk48oqioqLw8/OjSZMmJEqUyHQckVh5+PAhEydOpGDBgrRq1YqMGTOyYcMG9u3bR6tWrXBzczMdUeS16d9ecXrt27cnODiYAQMGULx4cWrVqmU6kryk3bt3c+3aNU13i0O7ceMGkyZNYtKkSdy9e5cWLVpgsVh48803TUcTsRktypEEITIykgYNGhAYGEhgYCD58+c3HUlewsCBA1m4cCEXL17UNinicE6ePMnYsWOZPXs2Li4udO3alX79+pEnTx7T0URsToVSEozbt29ToUIF3N3d2bVrl06WsHNWq5V8+fLx3nvvMXnyZNNxRF5aYGAg3t7eWCwWMmTIQJ8+fejRowcZMmQwHU0kzuhHfkkw0qVLh7+/PxcuXKBt27ZER0ebjiT/YP/+/Zw9e1bT3eIQrFYrq1evpkaNGpQvX579+/czefJkzp07x4gRI1QmxempUEqCUrRoURYuXMjKlSv5/PPPTceRf2CxWEifPj3vvPOO6Sgifys8PJy5c+dSqlQpGjRoQGhoKMuWLePYsWN0796dZMmSmY4oEi9UKCXBadCgAd9++y3ffPMNS5YsMR1H/obFYqFRo0a4u7ubjiLynHv37jFmzBjy589Phw4dyJ07N1u3bmX37t00bdoUV1dX0xFF4pWeoZQEyWq10rZtW3x9fdmxY4dWW9qZY8eOUbRoUQICAmjYsKHpOCJPXblyhQkTJjB16lRCQ0Np06YNgwYNonjx4qajiRilQikJVlhYGG+//TbXr18nMDCQLFmymI4kf3kyghwSEkLSpElNxxHh2LFjjB49mnnz5pEkSRK6d+9O3759yZEjh+loInZBhVIStIsXL1K2bFkKFCjApk2bSJw4selIApQrV458+fKxePFi01EkgduxYwfe3t4EBASQLVs2+vXrR7du3UiTJo3paCJ2Rc9QSoKWM2dOfH19CQwMpFevXjqe0Q6cP3+eoKAgre4WY6Kjo/Hz86NKlSpUrVqVP//8k1mzZnHmzBmGDBmiMinyAiqUkuBVqlSJH3/8kenTpzNlyhTTcRI8X19fEidOzHvvvWc6iiQwjx49YsaMGRQrVgwvLy9cXV1ZsWIFhw4dolOnTiRJksR0RBG7paMXRYBOnToRHBxM3759KVasGDVq1DAdKcGyWCzUqVOHVKlSmY4iCcTt27f58ccfGT9+PNevX8fT05PZs2dTqVIl09FEHIaeoRT5S2RkJPXr1+ePP/5g79695MuXz3SkBOfatWtky5aNmTNn0qlTJ9NxxMmdP3+eH374genTpxMREUGHDh0YOHAghQoVMh1NxOGoUIr8l1u3blG+fHmSJUvGzp07NUoWz6ZPn06PHj24evUqGTNmNB1HnNTBgwfx8fFh4cKFpEyZkp49e9K7d2/t9CASCyqUIv/j8OHDVKxYkXfffZfly5fj4qJHjeNL/fr1CQ8PZ+PGjaajiJOxWq1s2bIFb29v1q5di4eHB/3796dz5876wVHEBvR/SpH/Ubx4cRYsWIC/vz9fffWV6TgJxp07d9i4caNWd4tNRUZGsmTJEsqXL0/NmjW5fPkyv/zyCydPnqRfv34qkyI2okIp8gINGzZk5MiR/Oc//2H58uWm4yQIq1atIiIiAk9PT9NRxAmEhoYyZcoUChcuTIsWLUiTJg3r1q1j//79tGnTRkd6itiYprxF/obVaqVVq1asWLGCnTt3Urp0adORnFrTpk25fPkyu3btMh1FHFhISAiTJ09m0qRJ3Lp1i+bNmzN48GDeeust09FEnJoKpcg/CA0NpWrVqty6dYvAwEAyZcpkOpJTCg0NJWPGjHz55ZcMGTLEdBxxQKdPn2bs2LHMmjULgM6dOzNgwADy5s1rOJlIwqApb5F/kDx5cvz8/AgLC+ODDz4gPDzcdCSntG7dOsLCwvDy8jIdRRzMvn37aNmyJQULFmTx4sUMHTqU8+fPM3HiRJVJkXikQinyLzw8PFi+fDm7du2ib9++puM4JYvFQsmSJSlYsKDpKOIArFYr69ato1atWpQtW5bAwEAmTZrEuXPn+Pzzz7XllIgBKpQiL6Fq1apMmTKFH3/8kR9//NF0HKcSHh7OihUrtLpb/lVERAS//PILb7zxBvXq1ePevXssWbKEEydO0KNHD5InT246okiCpaMXRV5Sly5dCA4Opnfv3hQtWpRq1aqZjuQUNm/ezN27d1Uo5W89ePCAGTNmMHbsWC5cuED9+vUZP3481apVI1GiRKbjiQhalCPySiIiIqhbty4HDx4kMDCQPHnymI7k8Lp168bGjRv5888/VQ7kGVevXmXixIlMmTKFBw8e0Lp1awYNGkTJkiVNRxOR/6FCKfKKbt68Sbly5UiVKhU7duwgZcqUpiM5rKioKLJnz06HDh3w9vY2HUfsxPHjxxkzZgxz587F3d2djz76iH79+pErVy7T0UTkb+gZSpFXlCFDBvz9/Tl16hQdO3YkOjradCSHtXPnTq5fv67pbgFg165dNGnShKJFi7JixQq+/PJLLly4wJgxY1QmReycCqXIayhZsiS//PILy5cvZ+TIkabjOCyLxUL27NkpX7686ShiSHR0NCtWrODtt9+mcuXKHDlyhOnTp3P27FmGDh1K2rRpTUcUkZegQinymjw9PfnPf/7DF198ga+vr+k4DsdqtWKxWPDy8sLFRd+KEprHjx8za9YsihcvTqNGjbBarfj5+XHkyBE6d+5MkiRJTEcUkVegZyhFYsFqtdK8eXPWrFnDrl27tFjgFezbt4+yZcuyceNGatasaTqOxJM7d+4wbdo0xo8fz5UrV2jcuDGDBw+mSpUqpqOJSCyoUIrE0sOHD6lSpQp3794lMDBQmyq/pOHDh/Pjjz9y7do13Ny0g5mzu3jxIuPHj2fatGk8fvyY9u3bM3DgQIoUKWI6mojYgAqliA2cO3eOsmXLUqJECdavX4+7u7vpSHavaNGiVKpU6enZy+KcDh06xOjRo5k/fz4pUqTg448/pnfv3mTLls10NBGxIT24JGIDuXPnZvny5Wzfvp3+/fubjmP3jh49yrFjx7S620lZrVa2bt1KgwYNKFmyJBs3buT777/nwoULjBo1SmVSxAmpUIrYyDvvvMOkSZOYPHky06dPNx3HrlksFlKmTMm7775rOorYUFRUFMuXL6dixYpUr16d8+fPM3fuXE6dOsWAAQNIlSqV6YgiEkf04JKIDXXr1o3g4GB69uxJ0aJFqVq1qulIdslisdCgQQOSJk1qOorYQFhYGHPmzGHMmDGcPHmSGjVqsHr1aurVq6fTj0QSCD1DKWJjERER1K5dmyNHjhAUFISHh4fpSHbl7Nmz5M2bl8WLF9O8eXPTcSQWbt68yZQpU5g4cSI3b96kadOmDB48mHLlypmOJiLxTFPeIjbm7u7O0qVLSZ48OY0bN+bhw4emI9kVX19fkiRJQv369U1Hkdd09uxZ+vbti4eHB6NGjaJZs2acOHGCJUuWqEyKJFAaoRSJI8HBwVSuXJkGDRqwePFiTf395e233yZdunQEBASYjiKv6I8//sDHx4clS5aQNm1aevXqRc+ePcmUKZPpaCJimEYoReJI6dKlmTt3LkuXLmXUqFGm49iFq1evsmPHDq3udiBWq5UNGzZQu3Zt3nrrLXbv3s0PP/zAuXPn+PLLL1UmRQRQoRSJU02bNuWLL75gxIgRGpED/P39cXFxoWHDhqajyL+IjIxkwYIFvPXWW9SpU4dbt26xaNEiTpw4Qa9evUiRIoXpiCJiRzTlLRLHoqOj+eCDD9iwYQO7d++mePHipiMZU7duXaKiovj1119NR5G/8eDBA2bOnMm4ceM4d+4cdevWZciQIdSoUUOPbYjI31KhFIkHDx48oHLlyjx8+JC9e/eSIUMG05Hi3e3bt8mcOTPjx4/n448/Nh1H/sf169eZOHEikydP5t69e7Rq1YpBgwZRunRp09FExAFoylskHqRMmRJ/f3/u3r1LixYtiIyMNB0p3q1cuZLIyEg8PT1NR5H/cvLkSXr06EHu3LkZN24cHTp04NSpU8ybN09lUkRemgqlSDzJmzcvy5YtY+vWrQwcONB0nHhnsVioVKkS2bNnNx1FgD179vDBBx9QqFAhLBYLn332GefPn2fcuHHkzp3bdDwRcTAqlCLxqHr16owfP54JEyYwa9Ys03HizcOHD1m7dq1WdxsWHR3NqlWrqFatGhUrVuTAgQP8+OOPnDt3jk8//ZT06dObjigiDkpHL4rEsx49ehAcHEz37t0pXLgwVapUMR0pzq1bt45Hjx7h5eVlOkqCFB4ezoIFCxg9ejSHDx+mYsWKWCwWGjVqhKurq+l4IuIEtChHxIDw8HDeffddjh8/TlBQELly5TIdKU61bduWQ4cOsX//ftNREpR79+7x008/8cMPP3Dp0iUaNmzIkCFDqFKlilZsi4hNacpbxIDEiROzbNkykiZNiqenJ6GhoaYjxZnw8HBWrFih6e54dPnyZT755BNy5crFp59+St26dTl8+DABAQFUrVpVZVJEbE6FUsSQzJkz4+/vz9GjR+ncuTPOOlmwadMm7t27p0IZD44cOcKHH35Injx5+PHHH+nevTtnz55l5syZFCtWzHQ8EXFiKpQiBr3xxhvMmTOHRYsW8f3335uOEycsFgsFCxZM0Bu6xyWr1cq2bdto2LAhxYsXZ926dYwaNYoLFy7w/fffa1W9iMQLFUoRw5o1a8aIESP49NNPWblypek4NhUVFYWfnx9NmjTRNKuNRUVF4evrS+XKlXnnnXc4c+YMP//8M2fOnGHQoEGkTp3adEQRSUBUKEXswFdffUWjRo1o3bo1R48eNR3HZnbs2MGNGzc03W1Djx494qeffqJYsWI0adKEJEmSsHLlSg4cOECHDh1InDix6YgikgBplbeInbh//z6VKlXi8ePH7N27l3Tp0pmOFGv9+vVj+fLlnDt3DhcX/fwaG7dv32bq1KlMmDCB69ev06RJEwYPHkyFChVMRxMR0QiliL1IlSoV/v7+3Lp1yymOZ7RarVgsFry8vFQmY+H8+fP079+fXLly8Z///AcvLy+OHz/OsmXLVCZFxG7ou7yIHcmfPz9Llixh06ZNDBkyxHScWNm3bx8XLlzQdPdrCg4Opm3btuTLl485c+bQv39/zp07x9SpUylYsKDpeCIiz1ChFLEztWrVYty4cYwbN445c+aYjvPaLBYLGTNmpGrVqqajOAyr1crGjRupW7cub7zxBtu3b2fs2LGcP3+er7/+mixZspiOKCLyQjp6UcQO9erVi+DgYD766CMKFy5MxYoVTUd6JVarleXLl9O4cWPc3PRt5t9ERkaybNkyfHx8+P3333njjTdYsGABzZo1098/EXEIGqEUsUOJEiVi8uTJlC1bFi8vLy5dumQ60is5evQoJ06c0HT3v3j48CGTJk2iYMGCtGrVigwZMrB+/Xp+//13WrVqpTIpIg5DhVLETiVJkgSLxYKbmxuenp6EhYWZjvTSLBYLqVKlolatWqaj2KUbN27wxRdf4OHhQb9+/ahUqRK///4769evp3bt2tqzU0QcjrYNErFz+/bto2rVqjRt2pR58+Y5RNl46623KFKkCAsWLDAdxa6cOnWKsWPHMmvWLFxcXOjSpQv9+/cnT548pqOJiMSKRihF7FyZMmWYPXs28+fPZ/To0abj/KszZ87wxx9/aLr7vwQGBtK8eXMKFSrE0qVLGT58OOfPn2f8+PEqkyLiFPSAjogDaNmyJQcOHOCTTz6hRIkS1K9f33Skv+Xr60vSpEmpV6+e6ShGWa1W1q5di4+PD5s3byZ//vxMnjyZDh06kCxZMtPxRERsSlPeIg4iOjqaxo0b89tvv7Fnzx6KFCliOtILVa1alYwZM+Ln52c6ihHh4eEsWrSI0aNHc/DgQcqVK8cnn3yCp6cnrq6upuOJiMQJTXmLOAgXFxfmz59Pjhw5aNy4MXfu3DEd6TlXrlxh586deHl5mY4S7+7fv8/YsWPJnz8/HTp0wMPDgy1btrBnzx6aNm2qMikiTk2FUsSBpE6dGn9/f65fv06rVq2IiooyHekZ/v7+uLi40LBhQ9NR4s2VK1cYNmwYuXLlYujQodSqVYuDBw+ycuVKqlWr5hCLqEREYktT3iIOaP369dSvX58BAwbg4+NjOs5TderUwWq1smHDBtNR4tyxY8cYPXo08+bNI0mSJHTr1o2+ffuSM2dO09FEROKdRihFHFCdOnUYM2bM00JjD27dusXmzZudfnX3jh078PT0pGjRoqxevZqvv/6aCxcu4OPjozIpIgmWVnmLOKi+ffsSHBxM165dKVy4MOXLlzeaZ+XKlURFReHp6Wk0R1yIjo5mxYoVeHt7s3PnTooWLcrMmTNp06YNSZIkMR1PRMQ4TXmLOLDHjx9TvXp1zp07R1BQENmzZzeWxdPTkxs3brBjxw5jGWzt8ePHzJs3j9GjR3P8+HGqVq3KkCFDaNCgAS4umuAREXlC3xFFHNiT4xldXFzw8vLi0aNHRnI8ePCAdevWOc109507d/juu+/IkycPH330EcWKFWPnzp1s27aNhg0bqkyKiPwPfVcUcXDZsmXD19eX4OBgunXrholJh7Vr1/Lo0SOH3y7owoULDBw4kFy5cvHll1/SqFEjjh07hsVioVKlSqbjiYjYLT1DKeIEypUrx8yZM2nbti2lS5dmwIAB8Xp/i8XCG2+8Qb58+eL1vrZy8OBBfHx8WLhwISlTpqRPnz707t2brFmzmo4mIuIQVChFnESbNm04cOAAgwcPpnjx4tStWzde7vv48WNWrlzJ4MGD4+V+tmK1WtmyZQs+Pj6sWbOGXLly4ePjQ+fOnUmVKpXpeCIiDkVT3iJOZNSoUdSrV48WLVpw4sSJeLnnxo0buX//vsM8PxkVFcXSpUspX748NWvW5NKlS8ybN49Tp07Rr18/lUkRkdegQiniRFxdXVmwYAFZs2alUaNG3L17N87vabFYKFSoEMWKFYvze8VGaGgoU6ZMoVChQjRv3pzUqVOzdu1a9u/fT9u2bXF3dzcdUUTEYalQijiZNGnSEBAQwNWrV2nduvVrH89otcL163D2LJw4EfN6/XrM55+IjIzE39+fJk2a2O0RgyEhIXz11Vfkzp2b3r17U65cOYKCgti4cSN169a129wiIo5Ez1CKOKFChQqxaNEiGjRowPDhw/nuu+/+9WtCQmDTJti3D/bujXm9f//596VKBWXKQPnykDTpcUJCrHY53X3mzBnGjh3LzJkzAejcuTP9+/d32IVDIiL2TBubizixMWPGMGjQIObPn0/r1q2f+32rFXbvhsmTYfFiiIwEN7eY13/z/++LoG1bN3r2TESFCmB6wG/fvn34+PiwdOlS0qdPT69evejZsycZM2Y0G0xExImpUIo4MavVSocOHVi6dCnbtm2jbNmyT3/P3x9GjIBDh16+RP6dJ19fsiSMHAmNGtkg/CuwWq2sX78eHx8fNm7cSL58+Rg4cCAdO3YkefLk8RtGRCQBUqEUcXKPHj2iWrVqXLp0icDAQBInzkbv3rBwIbi4QHS07e715HqtWsHEiZAhg+2u/SIREREsWbIEHx8fgoODKVu2LEOGDKFJkya4urrG7c1FROQpFUqRBODy5cuULVuW1KnbExLyLXfuJOI11+q8FFdXSJsWZswAT0/bX//BgwfMmDGDcePGcf78eerXr8+QIUOoVq2aFtmIiBigQimSAFit8PHHF/jxx1xANPGxwcOT0cpRo2DoUNs8W3nt2jUmTJjA1KlTuX//Pq1atWLQoEGUKlUq9hcXEZHXpkIp4uSsVvj0U3iJhd5xZtgw+Oab1y+VJ06cYMyYMcyZMwd3d3c++ugj+vXrR65cuWwbVEREXosKpYiTGzUKhg83nSImx7Bhr/Y1u3fvxtvbGz8/PzJnzkzfvn3p3r076dKli5uQIiLyWlQoRZyYnx94eZlO8f/8/KBx439+T3R0NKtWrcLb25vt27dTqFAhBg8eTNu2bUmaNGm85BQRkVejQinipG7ehMKF4datZ0+3McXFBdKlg+PHX7z6+/Hjx8yfP5/Ro0dz9OhRKleuzJAhQ2jYsCEuLjrUS0TEnum7tIiT6t0b7tyxjzIJMQt07tyBPn2e/fzdu3fx9vYmb968dO7cmUKFCrF9+3Z27NhB48aNVSZFRByARihFnJC/f9xs12Mr/v5QpswlfvjhB6ZNm8bjx49p3749AwcOpEiRIqbjiYjIK1KhFHEyViuUKgVHjth203JbSZTIStq0F7l/Pz8pUiSnR48e9OnTh2zZspmOJiIir0mFUsTJ7NoFlSubTvHv+vRZyMiR75MqVSrTUUREJJbcTAcQEduaPDn2Z3PHNTc3K7dutUJdUkTEOWiEUsSJhIRAtmy2KJO/ANuAfcBBIByYDXSM7YWfcnODK1cgY0abXVJERAzR8kkRJ7Jpk61GJkcAPwHngLh5tjEyEjZvjpNLi4hIPFOhFHEi+/bFjPzF3gzgLHAD6G6LCz7HzS0mr4iIOD49QyniRPbssdUI5bu2uMg/ioyEvXvj/DYiIhIPNEIp4iSsVvj9d9MpXk1QkP1svC4iIq9PhVLESdy4Affvm07xau7fj8ktIiKOTYVSxEmEhppO8HrCwkwnEBGR2FKhFHES4eGmE7yex49NJxARkdhSoRRxEokTm07wepIkMZ1ARERiS4VSxEkkT246wetJlsx0AhERiS0VShEnkSkTDneUYapUMblFRMSxqVCKOIlEieCtt0yneDVly8bkFhERx6aNzUWcSIUKsGOHLTY3nwFs/+uvD/7X57b89deef328Pjc3KF8+VpcQERE7oUIp4kTKlLHVSTnbgTn/87kdf30A5CG2hTIyMiaviIg4vkRWq86pEHEWISGQLZutSmXccnODK1cgY0bTSUREJLb0DKWIE8mYEVq0iClr9szNDVq2VJkUEXEWKpQiTqZnT/sfoYyMjMkpIiLOQVPeIk7GaoXSpeHwYYiONp3meS4uUKIE7N+vFd4iIs5CI5QiTiZRIhg50j7LJMTk+vprlUkREWeiQinihBo1glatwNXVdJJnubpC69Yx+URExHloylvESd28CYULw+3b9jFa6eIC6dLB8eOQIYPpNCIiYksaoRRxUhkywIwZ9lEmISbHzJkqkyIizkiFUsSJeXrCN9+YThFj1Cho3Nh0ChERiQsqlCJObtiwmA/TGYYONZtBRETijgqliJNLlChmlHLUqJhfu8TTf/VP7vPttzH31qpuERHnpUU5IgmIvz907gx37kBUVNzdx9UV0qaNeWZS09wiIs5PI5QiCUjjxjGrrJs3j/m1rUcrn1yvRQs4cUJlUkQkoVChFElgMmSABQvAzw+KF4/5XGzP/n7y9cWLx4yCzp8P6dPH7poiIuI4NOUtkoBZrbBnD0yeDIsWxZyx7e4OERH//rVubv///pYtY87mLl9ez0qKiCREKpQiAkBICGzeDEFBEBgY83r//vPvS5UKypaNKY9lykCNGpAxY/znFRER+6FCKSIvZLXCjRsQFgaPH0OSJJAsGWTKpFFIERF5lgqliIiIiMSKFuWIiIiISKyoUIqIiIhIrKhQioiIiEisqFCKiIiISKyoUIqIiIhIrKhQioiIiEisqFCKiIiISKyoUIqIiIhIrKhQioiIiEisqFCKiIiISKyoUIqIiIhIrKhQioiIiEisqFCKiIiISKyoUIqIiIhIrKhQioiIiEisqFCKiIiISKyoUIqIiIhIrKhQioiIiEisqFCKiIiISKyoUIqIiIhIrKhQioiIiEisqFCKiIiISKyoUIqIiIhIrKhQioiIiEisqFCKiIiISKyoUIqIiIhIrKhQioiIiEis/B8UTQ1Sc0ptIgAAAABJRU5ErkJggg==",
      "text/plain": [
       "<Figure size 640x480 with 1 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "import networkx as nx\n",
    "import numpy as np\n",
    "import matplotlib.pyplot as plt\n",
    "\n",
    "adj_matrix = np.array([[0, 1, 1, 1],\n",
    "                       [1, 0, 1, 1],\n",
    "                       [1, 1, 0, 1],\n",
    "                       [1, 1, 1, 0],\n",
    "                      ])\n",
    "\n",
    "G_from_matrix = nx.from_numpy_array(adj_matrix)\n",
    "\n",
    "nx.draw(G_from_matrix, with_labels=True, node_color='blue', edge_color='black', node_size=1000, font_size=14)\n",
    "\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9fb0c365-a912-4212-8634-270db9960a6c",
   "metadata": {},
   "source": [
    "The code above displays a graph with 4 vertices and forms 4 unique triangles: $\\{0, 1, 2, 0\\}, \\{1, 0, 2, 1\\}, \\{2, 1, 3, 2\\}, \\{3, 0, 2, 3\\}$\n",
    "\n",
    "The formula for counting triangles in an undirected graph represented as an adjancency matrix is as follows:$$\\triangle := \\dfrac{1}{6}\\sum_{i, j, k} A_{i, j}.A_{j, k}.A_{i, k} = \\dfrac{1}{6}\\sum_{i, j, k} (A)^2_{i, j}.A_{i, j}$$\n",
    "\n",
    "In this IP, the *prover* counts the the number of triangles and proves that to the *verifier*. The prover converts $A$ and $A^2$ to multilinear polynomials using the same methods as in the IP for MatMul above, computes the sum as shown in the formula and runs the sumcheck protocol to convince the verifier of the validity of the sum. For simplicity, we would remove $\\dfrac{1}{6}$ from the formula."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 122,
   "id": "b31959dc-0885-4ba0-a397-11f078c95a96",
   "metadata": {},
   "outputs": [],
   "source": [
    "def generate_adjacent_matrix(n: int):\n",
    "    \n",
    "    res = []\n",
    "    \n",
    "    for _ in range(n):\n",
    "        row = [randint(0, 1) for _ in range(n)]\n",
    "        res.append(row)\n",
    "        \n",
    "    return res\n",
    "\n",
    "\n",
    "def adjecency_matrix_to_ffe(a: List[List[int]], ff: FF):\n",
    "    res = []\n",
    "    for row in a:\n",
    "        ffe_row = [ff.new(val) for val in row]\n",
    "        res.append(ffe_row)\n",
    "    return res"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "751938da-164c-4ea5-87b8-f652f7a74f12",
   "metadata": {},
   "source": [
    "#### Step 1\n",
    "\n",
    "Define the matrix, multiply matrices and convert to a multilinear extension"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 125,
   "id": "335b0f3e-51f8-461e-8242-2c0a9e43154e",
   "metadata": {},
   "outputs": [],
   "source": [
    "n = 4\n",
    "\n",
    "log_n = int(log2(n))\n",
    "\n",
    "num_of_vars = log_n + log_n\n",
    "\n",
    "prime = 541\n",
    "\n",
    "ff = FF(prime)\n",
    "\n",
    "A = adjecency_matrix_to_ffe(generate_adjacent_matrix(4), ff) ## matrix A\n",
    "\n",
    "A_square = matrix_product(ff, A, A) ## matrix A^2\n",
    "\n",
    "evaluations_a = matrix_to_one_dim_list(A)\n",
    "\n",
    "multi_poly_A = Multilinear_Polynomial(ff, evaluations_a, num_of_vars) ## f(x, y)\n",
    "\n",
    "evaluations_a_square = matrix_to_one_dim_list(A_square)\n",
    "\n",
    "multi_poly_A_square = Multilinear_Polynomial(ff, evaluations_a_square, num_of_vars) ## m(x, y)\n",
    "\n",
    "mul_of_A_and_A_square = MulOfMultilinearPoly(multi_poly_A, multi_poly_A_square) ## g(x, y) = f(x, y).m(x, y)\n",
    "\n",
    "h = mul_of_A_and_A_square.sum() ## number of triangles"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ef078fbc-f617-4826-a0f0-5fe5df1c4ddf",
   "metadata": {},
   "source": [
    "#### Step 2\n",
    "    \n",
    "The prover computes a polynomial $g_1(x)$ and sends to the verifier. $$g_1(x) = g(x, 0, 0, 0) + g(x, 0, 0, 1) + g(x, 0, 1, 0) + g(x, 0, 1, 1) + g(x, 1, 0, 0) + g(x, 1, 0, 1) + g(x, 1, 1, 0) + g(x, 1, 1, 1)$$\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 128,
   "id": "483b9fb0-ba10-4701-a44b-4d7d0630f83a",
   "metadata": {},
   "outputs": [],
   "source": [
    "poly_1 = mul_of_A_and_A_square.partial_evaluate([1, 2, 3], (ff.zero(), ff.zero(), ff.zero())) # g(x, 0, 0, 0)\n",
    "poly_2 = mul_of_A_and_A_square.partial_evaluate([1, 2, 3], (ff.zero(), ff.zero(), ff.one())) # g(x, 0, 0, 1)\n",
    "poly_3 = mul_of_A_and_A_square.partial_evaluate([1, 2, 3], (ff.zero(), ff.one(), ff.zero())) # g(x, 0, 1, 0)\n",
    "poly_4 = mul_of_A_and_A_square.partial_evaluate([1, 2, 3], (ff.zero(), ff.one(), ff.one())) # g(x, 0, 1, 1)\n",
    "poly_5 = mul_of_A_and_A_square.partial_evaluate([1, 2, 3], (ff.one(), ff.zero(), ff.zero())) # g(x, 1, 0, 0)\n",
    "poly_6 = mul_of_A_and_A_square.partial_evaluate([1, 2, 3], (ff.one(), ff.zero(), ff.one())) # g(x, 1, 0, 1)\n",
    "poly_7 = mul_of_A_and_A_square.partial_evaluate([1, 2, 3], (ff.one(), ff.one(), ff.zero())) # g(x, 1, 1, 0)\n",
    "poly_8 = mul_of_A_and_A_square.partial_evaluate([1, 2, 3], (ff.one(), ff.one(), ff.one())) # g(x, 1, 1, 1)\n",
    "\n",
    "g_1_of_x = AddOfMulOfLinearPoly([poly_1, poly_2, poly_3, poly_4, poly_5, poly_6, poly_7, poly_8])"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7f0c2ade-0860-4659-82a9-4269a337e5ab",
   "metadata": {},
   "source": [
    "##### STEP 4:\n",
    "\n",
    "The verifier stores $g_1(x)$ as $s_1(x)$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 131,
   "id": "96a04198-58d3-4c7c-89f1-1da8a551ba8c",
   "metadata": {},
   "outputs": [],
   "source": [
    "s_1_of_x = g_1_of_x"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0e6e7851-2901-4d7e-97d1-358081dc4775",
   "metadata": {
    "tags": []
   },
   "source": [
    "##### STEP 5:\n",
    "\n",
    "The verifier checks that $h == s_1(0) + s_1(1)$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 134,
   "id": "f9e4ec07-3d6d-450a-a61e-33786a219531",
   "metadata": {},
   "outputs": [],
   "source": [
    "x = s_1_of_x.evaluate(ff.zero())\n",
    "y = s_1_of_x.evaluate(ff.one())\n",
    "assert h == x + y, \"Invalid proof\""
   ]
  },
  {
   "cell_type": "markdown",
   "id": "fd504c05-07b6-416f-9342-7c4f04350f7f",
   "metadata": {},
   "source": [
    "##### STEP 6:\n",
    "\n",
    "The verifier generates a random value $r_1$ and sends to the prover"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 137,
   "id": "fa1bcf0c-2abe-42af-96d5-acd5317cb9b7",
   "metadata": {},
   "outputs": [],
   "source": [
    "r1 = ff.random_value()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "794dd6f9-9661-42f7-b7d2-37c5d947e9ba",
   "metadata": {},
   "source": [
    "##### STEP 7:\n",
    "\n",
    "The prover computes $g_2(y) = g(r_1, y, 0, 0) + g(r_1, y, 0, 1) + g(r_1, y, 1, 0) + g(r_1, y, 1, 1)$ and sends to the verifier"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 140,
   "id": "089a1d6c-0896-497e-aea3-778564d0e5fe",
   "metadata": {},
   "outputs": [],
   "source": [
    "poly_1 = mul_of_A_and_A_square.partial_evaluate([0, 2, 3], (r1, ff.zero(), ff.zero())) # g(r1, y, 0, 0)\n",
    "poly_2 = mul_of_A_and_A_square.partial_evaluate([0, 2, 3], (r1, ff.zero(), ff.one())) # g(r1, y, 0, 1)\n",
    "poly_3 = mul_of_A_and_A_square.partial_evaluate([0, 2, 3], (r1, ff.one(), ff.zero())) # g(r1, y, 1, 0)\n",
    "poly_4 = mul_of_A_and_A_square.partial_evaluate([0, 2, 3], (r1, ff.one(), ff.one())) # g(r1, y, 1, 1)\n",
    "\n",
    "g_2_of_y = AddOfMulOfLinearPoly([poly_1, poly_2, poly_3, poly_4])"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9862cf1c-35eb-4743-908b-bd297bf03253",
   "metadata": {},
   "source": [
    "##### STEP 8:\n",
    "\n",
    "The verifier stores $g_2(y)$ as $s_2(y)$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 143,
   "id": "b4653b83-2215-4432-ad95-f488413bbf10",
   "metadata": {},
   "outputs": [],
   "source": [
    "s_2_of_y = g_2_of_y"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4768276d-063f-4d5b-8738-ec70190712ad",
   "metadata": {},
   "source": [
    "##### STEP 9:\n",
    "\n",
    "The verifier checks that $s_1(r_1) == s_2(0) + s_2(1)$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 146,
   "id": "0d06550e-7e42-48ab-ba9b-a7f6a9cc9df6",
   "metadata": {},
   "outputs": [],
   "source": [
    "x = s_1_of_x.evaluate(r1)\n",
    "y = s_2_of_y.evaluate(ff.zero())\n",
    "z = s_2_of_y.evaluate(ff.one())\n",
    "assert x == y + z, \"Invalid proof\""
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9b00c079-5fdb-431f-ab5b-3e4d01c289c6",
   "metadata": {},
   "source": [
    "##### STEP 10:\n",
    "\n",
    "The verifier generates a random value $r_2$ and sends to the prover"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 149,
   "id": "012e8387-510a-45c0-9623-5f43e0595b6f",
   "metadata": {},
   "outputs": [],
   "source": [
    "r2 = ff.random_value()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4dcbfe0f-3bcf-4cb9-865e-0d818379fc5d",
   "metadata": {},
   "source": [
    "##### STEP 11:\n",
    "\n",
    "The prover computes $g_3(w) = g(r_1, r_2, w, 0) + g(r_1, r_2, w, 1)$ and sends to the verifier"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 152,
   "id": "a73c999a-b4da-4d24-ba49-81e078ea3982",
   "metadata": {},
   "outputs": [],
   "source": [
    "poly_1 = mul_of_A_and_A_square.partial_evaluate([0, 1, 3], (r1, r2, ff.zero())) # g(r1, r2, w, 0)\n",
    "poly_2 = mul_of_A_and_A_square.partial_evaluate([0, 1, 3], (r1, r2, ff.one())) # g(r1, r2, w, 1)\n",
    "\n",
    "g_3_of_w = AddOfMulOfLinearPoly([poly_1, poly_2])"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f9ba693f-ade4-4901-82b3-82d08cffde2c",
   "metadata": {},
   "source": [
    "##### STEP 12:\n",
    "\n",
    "The verifier stores $g_3(w)$ as $s_3(w)$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 155,
   "id": "30a0b8f0-733f-4f97-95e1-2db9d0750c6c",
   "metadata": {},
   "outputs": [],
   "source": [
    "s_3_of_w = g_3_of_w"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9ad98910-5cec-4423-8330-dc26515461ff",
   "metadata": {},
   "source": [
    "##### STEP 13:\n",
    "\n",
    "The verifier checks that $s_2(r_2) == s_3(0) + s_3(1)$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 158,
   "id": "59ce3cb3-a37f-4043-8211-fc3bb3037430",
   "metadata": {},
   "outputs": [],
   "source": [
    "x = s_2_of_y.evaluate(r2)\n",
    "y = s_3_of_w.evaluate(ff.zero())\n",
    "z = s_3_of_w.evaluate(ff.one())\n",
    "assert x == y + z, \"Invalid proof\""
   ]
  },
  {
   "cell_type": "markdown",
   "id": "65972572-29b8-4171-967e-9a2719482000",
   "metadata": {},
   "source": [
    "##### STEP 14:\n",
    "\n",
    "The verifier generates a random value $r_3$ and sends to the prover"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 161,
   "id": "96314778-53e2-458a-8bef-2ee3d74940f3",
   "metadata": {},
   "outputs": [],
   "source": [
    "r3 = ff.random_value()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "672e4dc2-f145-485e-9ae2-a4a0f90949d4",
   "metadata": {},
   "source": [
    "##### STEP 15:\n",
    "\n",
    "The prover computes $g_4(z) = g(r_1, r_2, r_3, z)$ and sends to the verifier"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 164,
   "id": "60055e45-0bd8-4dc8-ae94-3b19d463232b",
   "metadata": {},
   "outputs": [],
   "source": [
    "poly_1 = mul_of_A_and_A_square.partial_evaluate([0, 1, 2], (r1, r2, r3)) # g(r1, r2, r3, z)\n",
    "\n",
    "g_4_of_z = poly_1"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "117738ef-c809-481d-9ffb-cd61b1378e79",
   "metadata": {},
   "source": [
    "##### STEP 16:\n",
    "\n",
    "The verifier stores $g_4(z)$ as $s_4(z)$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 167,
   "id": "fd6a8dac-f346-43af-97f2-d394454101f7",
   "metadata": {},
   "outputs": [],
   "source": [
    "s_4_of_z = g_4_of_z"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "46693eaf-5d7f-464e-837d-f39e7211f4c5",
   "metadata": {},
   "source": [
    "##### STEP 17:\n",
    "\n",
    "The verifier checks that $s_3(r_3) == s_4(0) + s_4(1)$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 170,
   "id": "2b057cae-8866-411c-be37-91780f1888f9",
   "metadata": {},
   "outputs": [],
   "source": [
    "x = s_3_of_w.evaluate(r3)\n",
    "y = s_4_of_z.evaluate(ff.zero())\n",
    "z = s_4_of_z.evaluate(ff.one())\n",
    "assert x == y + z, \"Invalid proof\""
   ]
  },
  {
   "cell_type": "markdown",
   "id": "83a2650c-3f0b-4a8c-928d-b956a525a91e",
   "metadata": {},
   "source": [
    "##### STEP 18:\n",
    "\n",
    "The verifier generates a random value $r_4$ and sends to the prover"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 173,
   "id": "6225bf2e-1df3-448a-bdbc-7b9262cdb1db",
   "metadata": {},
   "outputs": [],
   "source": [
    "r4 = ff.random_value()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e421ed93-e05c-4279-80b6-b081aabeb435",
   "metadata": {},
   "source": [
    "##### STEP 19\n",
    "\n",
    "The prover computes $g(r_1, r_2, r_3, r_4)$ and sends to the verifier"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 176,
   "id": "34742f8c-5306-42ed-b7c3-85a4089515e8",
   "metadata": {},
   "outputs": [],
   "source": [
    "evaluation = mul_of_A_and_A_square.evaluate((r1, r2, r3, r4))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "bddb8486-2769-4042-b377-7b6d770429d4",
   "metadata": {},
   "source": [
    "##### LAST STEP:\n",
    "\n",
    "The verifier checks that $s_4(r_4) == g(r_1, r_2, r_3, r_4)$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 179,
   "id": "15969753-0b4b-415f-8bb4-e054fbd73b79",
   "metadata": {},
   "outputs": [],
   "source": [
    "x = s_4_of_z.evaluate(r4)\n",
    "assert x == evaluation, \"Invalid proof\""
   ]
  },
  {
   "cell_type": "markdown",
   "id": "406393bc-8dcf-40cc-9960-4ef2559a2b73",
   "metadata": {},
   "source": [
    "### The GKR Protocol"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 252,
   "id": "3377e524-16f7-4bc2-ab70-75e7a70cbced",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[FFE(element: 3, modulus: 17), FFE(element: 7, modulus: 17), FFE(element: 7, modulus: 17), FFE(element: 7, modulus: 17), FFE(element: 13, modulus: 17), FFE(element: 13, modulus: 17)]\n"
     ]
    }
   ],
   "source": [
    "from enum import Enum, auto\n",
    "\n",
    "\n",
    "class OP(Enum):\n",
    "    \n",
    "    ADD = auto()\n",
    "    \n",
    "    MUL = auto()\n",
    "\n",
    "\n",
    "class Gate:\n",
    "    \n",
    "    operation: OP\n",
    "    \n",
    "    def __init__(self, operation: OP):\n",
    "        self.operation = operation\n",
    "        \n",
    "    def evaluate(self, input_a: FFE, input_b: FFE):\n",
    "        if self.operation == OP.ADD:\n",
    "            return input_a + input_b\n",
    "        elif self.operation == OP.MUL:\n",
    "            return input_a * input_b\n",
    "        else:\n",
    "            raise Exception(\"Invalid operation\")\n",
    "\n",
    "        \n",
    "class Layer:\n",
    "    \n",
    "    gates: List[Gate]\n",
    "    \n",
    "    layer_length: int\n",
    "    \n",
    "    def __init__(self, gates: List[Gate]):\n",
    "        self.layer_length = len(gates)\n",
    "        self.gates = gates\n",
    "        \n",
    "        \n",
    "class Circuit:\n",
    "    \n",
    "    layers: List[Layer]\n",
    "    \n",
    "    def __init__(self, layers: List[Layer]):\n",
    "        self.layers = layers\n",
    "        \n",
    "        \n",
    "    def evaluate(self, inputs: List[FFE]):\n",
    "        if len(inputs) // 2 != len(self.layers[-1].gates):\n",
    "            raise Exception(\"Invalid Input length\")\n",
    "        \n",
    "        evaluations = []\n",
    "        \n",
    "        for i in range(0, len(inputs), 2):\n",
    "            input_a = inputs[i]\n",
    "            \n",
    "            input_b = inputs[i + 1]\n",
    "            \n",
    "            layer = self.layers[-((i + 1) // 2)]\n",
    "            \n",
    "            for gate in layer.gates:\n",
    "                evaluation = gate.evaluate(input_a, input_b)\n",
    "                evaluations.append(evaluation)\n",
    "                \n",
    "                \n",
    "        print(evaluations)\n",
    "    \n",
    "    \n",
    "layer_0 = Layer([Gate(OP.ADD)])\n",
    "\n",
    "layer_1 = Layer([Gate(OP.MUL), Gate(OP.MUL)])\n",
    "\n",
    "layer_2 = Layer([Gate(OP.ADD), Gate(OP.ADD), Gate(OP.ADD)])\n",
    "\n",
    "layers = [layer_0, layer_1, layer_2]\n",
    "\n",
    "circuit = Circuit(layers)\n",
    "\n",
    "ff = FF(17)\n",
    "\n",
    "inputs = [ff.one(), ff.new(2), ff.new(3), ff.new(4), ff.new(5), ff.new(6)]\n",
    "\n",
    "circuit.evaluate(inputs)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 234,
   "id": "48bde3af-3aa2-49ff-a3fc-a8a6bf0bacad",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 234,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "test_list = [1, 2, 3]\n",
    "\n",
    "test_list[-3]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "fb9e7b11-35ed-4ac5-ac78-dd1a71a11848",
   "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.11.8"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}