src/bcho_pcs.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "4e555402-17b0-4912-a593-436a4c962c50",
   "metadata": {},
   "source": [
    "# BCHO PCS"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "32680606",
   "metadata": {
    "vscode": {
     "languageId": "python"
    }
   },
   "outputs": [],
   "source": [
    "from group import DummyGroup\n",
    "from utils import log_2, pow_2\n",
    "from unipolynomial import UniPolynomial\n",
    "from mle2 import MLEPolynomial\n",
    "from kzg10 import Commitment, KZG10Commitment"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "5587bb46-393b-4b8c-9244-44fab1d34e61",
   "metadata": {
    "vscode": {
     "languageId": "python"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Finite Field of size 193"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "F193.<a> = GF(193)\n",
    "R193.<X> = F193[]\n",
    "R193\n",
    "Fp=F193\n",
    "Fp"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "ea7fd6df",
   "metadata": {
    "vscode": {
     "languageId": "python"
    }
   },
   "outputs": [],
   "source": [
    "UniPolynomial.set_scalar(Fp(0), Fp)\n",
    "Commitment.set_scalar(Fp(0))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "d34f0acc-be43-4527-89cc-135387e09e8b",
   "metadata": {
    "vscode": {
     "languageId": "python"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Multivariate Polynomial Ring in X0, X1, X2, X3, X4, X5, X6, X7, X8, X9, Y0, Y1, Y2, Y3, Y4, Y5, Y6, Y7, A0, A1, A2, B0, B1, B2 over Finite Field of size 193"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# For symbolic calculation\n",
    "\n",
    "R_2.<X0, X1, X2, X3, X4, X5, X6, X7, X8, X9, Y0, Y1, Y2, Y3, Y4, Y5, Y6, Y7, A0, A1, A2, B0, B1, B2> = Fp[]; R_2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "9f5d6647",
   "metadata": {
    "vscode": {
     "languageId": "python"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Finite Field in b of size 193^2"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Fp2 = Fp.extension(2, 'b'); Fp2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "c5e73ae6-5dd7-4c05-b8ac-c28f84c84137",
   "metadata": {
    "vscode": {
     "languageId": "python"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(125, True, True)"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "omega = Fp.primitive_element()^3; omega, omega^64 == 1, omega^32 == -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "538d3666",
   "metadata": {
    "vscode": {
     "languageId": "python"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 64, 43, 50, 112, 27, 184, 3, 192, 129, 150, 143, 81, 166, 9, 190]"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "H16 = [(omega^4)^i for i in range(16)]; H16"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "74bfa9c6",
   "metadata": {
    "vscode": {
     "languageId": "python"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 43, 112, 184, 192, 150, 81, 9]"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "H8 = [(omega^8)^i for i in range(8)]; H8"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "aab9dcb1",
   "metadata": {
    "vscode": {
     "languageId": "python"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 112, 192, 81]"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "H4 = [(omega^16)^i for i in range(4)]; H4"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "id": "dfb13756",
   "metadata": {
    "vscode": {
     "languageId": "python"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(5, 6, 193)"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "G1 = DummyGroup(Fp)\n",
    "G1.generator(), G1.exp(2, 3), G1.order(), "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "id": "84908aac",
   "metadata": {
    "vscode": {
     "languageId": "python"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3*X1"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "G1.exp(X1, 3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "id": "ca90ee72",
   "metadata": {
    "vscode": {
     "languageId": "python"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(b, 3*b, 37249, b^2 + 192*b + 5)"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "G2 = DummyGroup(Fp2)\n",
    "Fp2.random_element()\n",
    "G2.generator(), G2.exp(G2.generator(), 3), G2.order(), G2.field.polynomial()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "id": "ed92df1a",
   "metadata": {
    "vscode": {
     "languageId": "python"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(False, 4)"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def is_power_of_two(n):\n",
    "    d = n\n",
    "    k = 0\n",
    "    while d > 0:\n",
    "        d >>= 1\n",
    "        k += 1\n",
    "    if n == 2**(k-1):\n",
    "        return True\n",
    "    else:\n",
    "        return False\n",
    "\n",
    "def next_power_of_two(n):\n",
    "    assert n >= 0, \"No negative integer\"\n",
    "    if is_power_of_two(n):\n",
    "        return n\n",
    "    d = n\n",
    "    k = 0\n",
    "    while d > 0:\n",
    "        d >>= 1\n",
    "        k += 1\n",
    "    return k\n",
    "\n",
    "is_power_of_two(15), next_power_of_two(15)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "id": "33659e21",
   "metadata": {
    "vscode": {
     "languageId": "python"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[0, 1, 1, 0, 0]"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def bits_le_with_width(i, width):\n",
    "    if i >= 2**width:\n",
    "        return \"Failed\"\n",
    "    bits = []\n",
    "    while width:\n",
    "        bits.append(i % 2)\n",
    "        i //= 2\n",
    "        width -= 1\n",
    "    return bits\n",
    "        \n",
    "bits_le_with_width(6, 5)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "53f4f10d",
   "metadata": {},
   "source": [
    "## Polynomial"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "id": "57d45eb7",
   "metadata": {
    "vscode": {
     "languageId": "python"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# \n",
    "#  m = [1]\n",
    "#  m = [1] + [1 * X0, 1 * X1]\n",
    "#  m = m + [1 * X0^2, 1 * X0 * X1, 1 * X1]\n",
    "def mle_eval_from_coeffs(f_coeffs, point):\n",
    "    k = len(point)\n",
    "    n = len(f_coeffs)\n",
    "    assert len(f_coeffs) == 1 << k\n",
    "    \n",
    "    e = Fp(0)\n",
    "    for i in range(n):\n",
    "        i_bits = bits_le_with_width(i, k)\n",
    "        monomial = product([point[j] if i_bits[j] == 1 else 1 for j in range(k)])\n",
    "        e += f_coeffs[i] * monomial\n",
    "    \n",
    "    return e\n",
    "\n",
    "mle_eval_from_coeffs([1, 3, 2, 1], [91, 181]) == Fp((1 + 3*X0 + 2*X1 + 1*X0*X1)(X0=91, X1=181))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "id": "1b77da1b",
   "metadata": {
    "vscode": {
     "languageId": "python"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "X0*X1 + 3*X0 + 2*X1 + 1"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mle_eval_from_coeffs([1, 3, 2, 1], [X0, X1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "id": "3048edc7",
   "metadata": {
    "vscode": {
     "languageId": "python"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def uni_eval_from_coeffs(coeffs, z):\n",
    "    t = Fp(1)\n",
    "    eval = Fp(0)\n",
    "    for i in range(0, len(coeffs)):\n",
    "        eval += coeffs[i] * t\n",
    "        t *= z\n",
    "    return eval\n",
    "\n",
    "uni_eval_from_coeffs([1, 3, 2, 1], 91) == Fp(1 + 3*91 + 2*91^2 + 1*91^3) == Fp(144)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "id": "6780f625",
   "metadata": {
    "vscode": {
     "languageId": "python"
    }
   },
   "outputs": [],
   "source": [
    "def polynomial_division(dividend, divisor):\n",
    "    \"\"\"\n",
    "    Perform univariate polynomial division.\n",
    "\n",
    "    Args:\n",
    "        dividend (list): Coefficients of the dividend polynomial, in descending order of degree.\n",
    "        divisor (list): Coefficients of the divisor polynomial, in descending order of degree.\n",
    "\n",
    "    Returns:\n",
    "        tuple: (quotient, remainder), where quotient and remainder are lists of coefficients.\n",
    "\n",
    "    Raises:\n",
    "        ValueError: If the divisor is zero or of higher degree than the dividend.\n",
    "    \"\"\"\n",
    "    # Remove leading zeros\n",
    "    while dividend and dividend[0] == 0:\n",
    "        dividend = dividend[1:]\n",
    "    while divisor and divisor[0] == 0:\n",
    "        divisor = divisor[1:]\n",
    "\n",
    "    # Check for zero division\n",
    "    if not divisor:\n",
    "        raise ValueError(\"Division by zero polynomial\")\n",
    "\n",
    "    # Check degrees\n",
    "    if len(dividend) < len(divisor):\n",
    "        return [], dividend\n",
    "\n",
    "    # Initialize quotient and remainder\n",
    "    quotient = [0] * (len(dividend) - len(divisor) + 1)\n",
    "    remainder = dividend.copy()\n",
    "\n",
    "    # Perform polynomial long division\n",
    "    for i in range(len(quotient)):\n",
    "        if len(remainder) < len(divisor):\n",
    "            break\n",
    "        \n",
    "        # Compute the next term of the quotient\n",
    "        term = remainder[0] // divisor[0]\n",
    "        quotient[i] = term\n",
    "\n",
    "        # Subtract term * divisor from the remainder\n",
    "        for j in range(len(divisor)):\n",
    "            if j < len(remainder):\n",
    "                remainder[j] -= term * divisor[j]\n",
    "\n",
    "        # Remove leading zero from remainder\n",
    "        while remainder and remainder[0] == 0:\n",
    "            remainder.pop(0)\n",
    "\n",
    "    # Remove trailing zeros from quotient\n",
    "    while quotient and quotient[-1] == 0:\n",
    "        quotient.pop()\n",
    "\n",
    "    return quotient, remainder"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "id": "a1dcc74b",
   "metadata": {
    "vscode": {
     "languageId": "python"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Dividend: [1, 0, 191, 0, 1]\n",
      "Divisor: [1, 1]\n",
      "Quotient: [1, 192, 192, 1]\n",
      "Remainder: []\n"
     ]
    }
   ],
   "source": [
    "# Example usage\n",
    "dividend = [Fp(1), Fp(0), Fp(-2), Fp(0), Fp(1)]  # x^4 - 2x^2 + 1\n",
    "divisor = [Fp(1), Fp(1)]  # x + 1\n",
    "\n",
    "quotient, remainder = polynomial_division(dividend, divisor)\n",
    "\n",
    "print(\"Dividend:\", dividend)\n",
    "print(\"Divisor:\", divisor)\n",
    "print(\"Quotient:\", quotient)\n",
    "print(\"Remainder:\", remainder)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "id": "71f8dbd0",
   "metadata": {
    "vscode": {
     "languageId": "python"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "X^3 + 192*X^2 + 192*X + 1"
      ]
     },
     "execution_count": 20,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(X^4 - 2*X^2 + 1)/(X+1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "id": "abddc0bb",
   "metadata": {
    "vscode": {
     "languageId": "python"
    }
   },
   "outputs": [],
   "source": [
    "kzg10 = KZG10Commitment(G1, G2, 10); "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "id": "71413bf3",
   "metadata": {
    "vscode": {
     "languageId": "python"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, X0, X0^2, X0^3, X0^4, X0^5, X0^6, X0^7, X0^8, X0^9, X0^10]"
      ]
     },
     "execution_count": 22,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "kzg10.setup(secret_symbol=X0, g1_generator=1, g2_generator=1)\n",
    "kzg10.srs\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "id": "afcbebfa",
   "metadata": {
    "vscode": {
     "languageId": "python"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(1, X0)"
      ]
     },
     "execution_count": 23,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "kzg10.h, kzg10.h_s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "id": "a4ef8d5b",
   "metadata": {
    "vscode": {
     "languageId": "python"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(Commitment(X0^2 + 2*X0 + 3), Commitment(X0^2 + 2*X0 + 3))"
      ]
     },
     "execution_count": 24,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "kzg10.commit([3,2,1]), kzg10.commit([3,2,1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "id": "e62d008a",
   "metadata": {
    "vscode": {
     "languageId": "python"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Commitment(X0^2 + 2*X0 + 3)"
      ]
     },
     "execution_count": 25,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "C0 = kzg10.commit([3,2,1]); C0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "id": "5d253965",
   "metadata": {
    "vscode": {
     "languageId": "python"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Commitment(11*X0^2 + 10*X0 + 9)"
      ]
     },
     "execution_count": 26,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "C1 = kzg10.commit([9,10,11]); C1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "id": "034ab2e9",
   "metadata": {
    "vscode": {
     "languageId": "python"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Commitment(12*X0^2 + 12*X0 + 12)"
      ]
     },
     "execution_count": 27,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "C0 + C1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "id": "228571a0",
   "metadata": {
    "vscode": {
     "languageId": "python"
    }
   },
   "outputs": [],
   "source": [
    "W = kzg10.prove_eval([3,2,1], 91, 167)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "id": "0830a810",
   "metadata": {
    "vscode": {
     "languageId": "python"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 29,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "kzg10.verify_eval(C0, W, 91, 167)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "id": "852cef26",
   "metadata": {
    "vscode": {
     "languageId": "python"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "-8296 + 2x + x^2"
      ]
     },
     "execution_count": 30,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "UniPolynomial([93,1]) * UniPolynomial([-91, 1]) + UniPolynomial([167])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "id": "8c7237e8",
   "metadata": {
    "vscode": {
     "languageId": "python"
    }
   },
   "outputs": [],
   "source": [
    "def log_2(x):\n",
    "    \"\"\"\n",
    "    Compute the integer part of the logarithm base 2 of x.\n",
    "\n",
    "    Args:\n",
    "        x (int): The number to compute the logarithm of. Must be a positive integer.\n",
    "\n",
    "    Returns:\n",
    "        int: The floor of the logarithm base 2 of x.\n",
    "\n",
    "    Raises:\n",
    "        ValueError: If x is not a positive integer.\n",
    "    \"\"\"\n",
    "    if not isinstance(x, int) or x <= 0:\n",
    "        raise ValueError(\"x must be a positive integer\")\n",
    "    \n",
    "    result = 0\n",
    "    while x > 1:\n",
    "        x >>= 1  # Bit shift right (equivalent to integer division by 2)\n",
    "        result += 1\n",
    "    return result"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "dfd01fc5",
   "metadata": {},
   "source": [
    "## BCHO PCS\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "id": "69d7ebdc",
   "metadata": {
    "vscode": {
     "languageId": "python"
    }
   },
   "outputs": [],
   "source": [
    "class ProofTranscript:\n",
    "    def __init__(self, field):\n",
    "        self.field = field\n",
    "        self.state = 0  # Initial state\n",
    "    \n",
    "    def absorb(self, element):\n",
    "        \"\"\"\n",
    "        Absorb a field element into the transcript.\n",
    "        \n",
    "        Args:\n",
    "            element: A field element to be absorbed. \n",
    "        \"\"\"\n",
    "        if isinstance(element, int):\n",
    "            element = self.field(element)\n",
    "        elif isinstance(element, sage.rings.integer.Integer):\n",
    "            element = self.field(element)\n",
    "        elif isinstance(element, Commitment):\n",
    "            element = element.value\n",
    "        elif isinstance(element, list):\n",
    "            element = sum(element)\n",
    "        elif not element.parent() == self.field:\n",
    "            raise TypeError(\"Must absorb a field element\")\n",
    "        \n",
    "        # if not isinstance(element, self.field.Element):\n",
    "        #     raise TypeError(\"Must absorb a field element\")\n",
    "        \n",
    "        # Simple hash function: multiply by a prime and add the element\n",
    "        bs = str(element).encode('utf-8')\n",
    "        n = int.from_bytes(bs, 'big')\n",
    "        self.state = (self.state * int(31) + n) % self.field.order()\n",
    "    \n",
    "    def squeeze(self):\n",
    "        \"\"\"\n",
    "        Generate a random field element based on the current state.\n",
    "        \n",
    "        Returns:\n",
    "            A field element.\n",
    "        \"\"\"\n",
    "        # Use the current state to generate a \"random\" field element\n",
    "        self.state = (self.state * 31 + 17) % self.field.order()\n",
    "        return self.field(self.state)\n",
    "    \n",
    "    def clone(self):\n",
    "        new = ProofTranscript(self.field)\n",
    "        new.state = self.state\n",
    "        return new\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "id": "6dc53fa4",
   "metadata": {
    "vscode": {
     "languageId": "python"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 33,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Fp(1).parent() == Fp"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "id": "07b2adf6",
   "metadata": {
    "vscode": {
     "languageId": "python"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<class 'sage.rings.integer.Integer'>"
      ]
     },
     "execution_count": 34,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "type(30)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "id": "b67aee95",
   "metadata": {
    "vscode": {
     "languageId": "python"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Random element 1: 151\n",
      "Random element 2: 66\n",
      "Random element 3: 98\n"
     ]
    }
   ],
   "source": [
    "    \n",
    "transcript = ProofTranscript(Fp)\n",
    "\n",
    "# Absorb some elements\n",
    "transcript.absorb(10)\n",
    "transcript.absorb(20)\n",
    "\n",
    "# Squeeze some randomness\n",
    "r1 = transcript.squeeze()\n",
    "r2 = transcript.squeeze()\n",
    "\n",
    "print(f\"Random element 1: {r1}\")\n",
    "print(f\"Random element 2: {r2}\")\n",
    "\n",
    "# Absorb more elements\n",
    "transcript.absorb(30)\n",
    "\n",
    "# Squeeze more randomness\n",
    "r3 = transcript.squeeze()\n",
    "\n",
    "print(f\"Random element 3: {r3}\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "id": "9365d729",
   "metadata": {
    "vscode": {
     "languageId": "python"
    }
   },
   "outputs": [],
   "source": [
    "def prove_eval_arg_naive(C, f, point, v, transcript):\n",
    "    \"\"\"\n",
    "    C: commitment to f\n",
    "    f: polynomial\n",
    "    point: evaluation point\n",
    "    v: evaluation value\n",
    "    Rng: randomness\n",
    "    \"\"\"\n",
    "    \n",
    "    n = len(f)\n",
    "    k = log_2(n)\n",
    "    if len(point) != k:\n",
    "        raise ValueError(\"Invalid evaluation point, k={}, while len(point)={}\".format(k, len(point)))\n",
    "    if not is_power_of_two(n):\n",
    "        raise ValueError(\"Invalid polynomial length\")\n",
    "    \n",
    "    transcript.absorb(C)\n",
    "    transcript.absorb(point)\n",
    "    transcript.absorb(v)\n",
    "\n",
    "    # Split and fold polynomials\n",
    "    coeffs = f[:]\n",
    "    h_uni_cm_vec = []\n",
    "    h_uni_poly_vec = [coeffs]\n",
    "    for i in range(k):\n",
    "        f_even = coeffs[::2]\n",
    "        f_odd = coeffs[1::2]\n",
    "        coeffs = [Fp(f_even[j] + point[i] * f_odd[j])  for j in range(len(f_even))]\n",
    "        h_cm = kzg10.commit(coeffs)\n",
    "\n",
    "        transcript.absorb(h_cm)\n",
    "\n",
    "        h_uni_poly_vec.append(coeffs)\n",
    "        h_uni_cm_vec.append(h_cm)\n",
    "\n",
    "    print(\"h_uni_cm_vec=\", h_uni_cm_vec)\n",
    "    print(\"h_uni_poly_vec=\", h_uni_poly_vec)\n",
    "    assert coeffs == [Fp(v)]\n",
    "    assert len(coeffs) == 1\n",
    "    print(\"coeffs=\", coeffs)\n",
    "\n",
    "    # Sample randomness and reply evaluations\n",
    "    r = transcript.squeeze()\n",
    "    print(\"r=\", r)\n",
    "    evals_pos = []\n",
    "    evals_neg = []\n",
    "    evals_sq = []\n",
    "    for i in range(k):\n",
    "        poly = h_uni_poly_vec[i]\n",
    "        evals_pos.append(uni_eval_from_coeffs(poly, r))\n",
    "        evals_neg.append(uni_eval_from_coeffs(poly, (-1) * r))\n",
    "        evals_sq.append(uni_eval_from_coeffs(poly, r^2))\n",
    "    \n",
    "    \n",
    "    # DEBUG: verify evaluations\n",
    "    dbg_evals_sq = evals_sq[:] + [v]\n",
    "    for i in range(k):\n",
    "        print(\"i={}, {}\".format(i, dbg_evals_sq[i+1] == (evals_pos[i] + evals_neg[i])/2 + point[i] * (evals_pos[i] - evals_neg[i])/(2*r)))\n",
    "\n",
    "    return (h_uni_cm_vec, evals_pos, evals_neg, evals_sq)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "id": "fae8c370",
   "metadata": {
    "vscode": {
     "languageId": "python"
    }
   },
   "outputs": [],
   "source": [
    "def verify_eval_arg_naive(C, arg, point, v, transcript):\n",
    "    \"\"\"\n",
    "    C: commitment to f\n",
    "    arg: argument to be verified\n",
    "    point: evaluation point\n",
    "    v: evaluation value\n",
    "    transcript: proof transcript\n",
    "    \"\"\"\n",
    "    k = len(point)\n",
    "    n = 1 << k\n",
    "    \n",
    "    transcript.absorb(C)\n",
    "    transcript.absorb(point)\n",
    "    transcript.absorb(v)\n",
    "\n",
    "    h_uni_cm_vec, evals_pos, evals_neg, evals_sq = arg\n",
    "\n",
    "    for i in range(len(h_uni_cm_vec)):\n",
    "        transcript.absorb(h_uni_cm_vec[i])\n",
    "    \n",
    "    r = transcript.squeeze()\n",
    "    \n",
    "    evals_sq.append(v)\n",
    "    verified = True\n",
    "    # Verify evaluations\n",
    "    for i in range(k):\n",
    "        b = evals_sq[i+1] == (evals_pos[i] + evals_neg[i])/2 + point[i] * (evals_pos[i] - evals_neg[i])/(2*r)\n",
    "        print(\"i={}, {}\".format(i, b))\n",
    "        verified = verified and b\n",
    "    if verified:\n",
    "        print(\"✅ Verified!\")\n",
    "    return verified\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "id": "aa0ac880",
   "metadata": {
    "vscode": {
     "languageId": "python"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0"
      ]
     },
     "execution_count": 38,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "transcript = ProofTranscript(Fp); transcript.state"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "id": "e2ac1ccb",
   "metadata": {
    "vscode": {
     "languageId": "python"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Commitment(X0^3 + 2*X0^2 + 3*X0 + 1)"
      ]
     },
     "execution_count": 39,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "ff = [1, 3, 2, 1]\n",
    "ff_cm = kzg10.commit(ff)\n",
    "ff_cm"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "id": "69831638",
   "metadata": {
    "vscode": {
     "languageId": "python"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "h_uni_cm_vec= [Commitment(93*X0 + 81), Commitment(-70)]\n",
      "h_uni_poly_vec= [[1, 3, 2, 1], [81, 93], [123]]\n",
      "coeffs= [123]\n",
      "r= 174\n",
      "i=0, True\n",
      "i=1, True\n"
     ]
    }
   ],
   "source": [
    "arg = prove_eval_arg_naive(ff_cm, [1, 3, 2, 1], point=[91, 181], v=123, transcript=transcript.clone())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "id": "d0deb95f",
   "metadata": {
    "vscode": {
     "languageId": "python"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "135"
      ]
     },
     "execution_count": 41,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "uni_eval_from_coeffs([81, 93], 150)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "id": "05ad877d",
   "metadata": {
    "vscode": {
     "languageId": "python"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "i=0, True\n",
      "i=1, True\n",
      "✅ Verified!\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 42,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "verify_eval_arg_naive(ff_cm, arg, point=[91, 181], v=123, transcript=ProofTranscript(Fp))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3d98022d",
   "metadata": {},
   "source": [
    "## Optimized version"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "id": "bba596fb",
   "metadata": {
    "vscode": {
     "languageId": "python"
    }
   },
   "outputs": [],
   "source": [
    "def prove_eval_arg_opt(C, f, point, v, transcript):\n",
    "    \"\"\"\n",
    "    C: commitment to f\n",
    "    f: polynomial\n",
    "    point: evaluation point\n",
    "    v: evaluation value\n",
    "    Rng: randomness\n",
    "    \"\"\"\n",
    "    \n",
    "    n = len(f)\n",
    "    k = log_2(n)\n",
    "    if len(point) != k:\n",
    "        raise ValueError(\"Invalid evaluation point, k={}, while len(point)={}\".format(k, len(point)))\n",
    "    if not is_power_of_two(n):\n",
    "        raise ValueError(\"Invalid polynomial length\")\n",
    "    \n",
    "    transcript.absorb(C)\n",
    "    transcript.absorb(point)\n",
    "    transcript.absorb(v)\n",
    "\n",
    "    # Split and fold polynomials\n",
    "    coeffs = f[:]\n",
    "    h_uni_cm_vec = []\n",
    "    h_uni_poly_vec = [coeffs]\n",
    "    for i in range(k-1):\n",
    "        f_even = coeffs[::2]\n",
    "        f_odd = coeffs[1::2]\n",
    "        coeffs = [Fp(f_even[j] + point[i] * f_odd[j])  for j in range(len(f_even))]\n",
    "        h_cm = kzg10.commit(coeffs)\n",
    "\n",
    "        transcript.absorb(h_cm)\n",
    "\n",
    "        h_uni_poly_vec.append(coeffs)\n",
    "        h_uni_cm_vec.append(h_cm)\n",
    "\n",
    "    print(\"h_uni_cm_vec=\", h_uni_cm_vec)\n",
    "    print(\"h_uni_poly_vec=\", h_uni_poly_vec)\n",
    "    assert Fp(v) == coeffs[0] + point[k-1] * coeffs[1]\n",
    "    assert len(coeffs) == 2\n",
    "    print(\"coeffs=\", coeffs)\n",
    "\n",
    "    # Sample randomness and reply evaluations\n",
    "    r = transcript.squeeze()\n",
    "    print(\"r=\", r)\n",
    "    evals_pos = []\n",
    "    evals_neg = []\n",
    "    evals_sq = []\n",
    "    for i in range(k):\n",
    "        poly = h_uni_poly_vec[i]\n",
    "        poly_at_r = uni_eval_from_coeffs(poly, r)\n",
    "        poly_at_neg_r = uni_eval_from_coeffs(poly, (-1) * r)\n",
    "        poly_at_r_sq = uni_eval_from_coeffs(poly, r^2)\n",
    "        evals_pos.append(poly_at_r)\n",
    "        evals_neg.append(poly_at_neg_r)\n",
    "        evals_sq.append(poly_at_r_sq)\n",
    "        transcript.absorb(poly_at_r)\n",
    "        transcript.absorb(poly_at_neg_r)\n",
    "        transcript.absorb(poly_at_r_sq)\n",
    "    \n",
    "    print(\"evals_pos=\", evals_pos)\n",
    "    print(\"evals_neg=\", evals_neg)\n",
    "    print(\"evals_sq=\", evals_sq)\n",
    "    \n",
    "    gamma = transcript.squeeze()\n",
    "    # gamma = 1\n",
    "    print(\"gamma=\", gamma)\n",
    "\n",
    "    h_agg = [0] * n\n",
    "    for i in range(n):\n",
    "        for j in range(k):\n",
    "            poly = h_uni_poly_vec[j]\n",
    "            if i < len(poly):\n",
    "                h_agg[i] += poly[i] * (gamma**j)\n",
    "    print(\"h_agg=\", h_agg)\n",
    "    \n",
    "    h_agg_poly_at_r = uni_eval_from_coeffs(h_agg, r)\n",
    "    h_agg_poly_at_neg_r = uni_eval_from_coeffs(h_agg, -r)\n",
    "    h_agg_poly_at_r_sq = uni_eval_from_coeffs(h_agg, r^2)\n",
    "\n",
    "    print(\"h_agg_poly_at_r={}, h_agg_poly_at_neg_r={}, h_agg_poly_at_r_sq={}\".format(h_agg_poly_at_r, h_agg_poly_at_neg_r, h_agg_poly_at_r_sq))\n",
    "\n",
    "    # DEBUG: verify h_agg\n",
    "    assert h_agg_poly_at_r == sum([evals_pos[i]*(gamma**i) for i in range(k)])\n",
    "\n",
    "\n",
    "    # DEBUG: verify evaluations\n",
    "    dbg_evals_sq = evals_sq[:] + [v]\n",
    "    for i in range(k):\n",
    "        print(\"dbg_evals_sq[i+1]={}, interp_and_eval_line(evals_pos[i], evals_neg[i], r, point[i])={}\".format(dbg_evals_sq[i+1], (evals_pos[i] + evals_neg[i])/2 + point[i] * (evals_pos[i] - evals_neg[i])/(2*r)))\n",
    "        print(\"i={}, {}\".format(i, dbg_evals_sq[i+1] == (evals_pos[i] + evals_neg[i])/2 + point[i] * (evals_pos[i] - evals_neg[i])/(2*r)))\n",
    "\n",
    "    interp_poly = UniPolynomial.interpolate([h_agg_poly_at_r, h_agg_poly_at_neg_r, h_agg_poly_at_r_sq], [r, -r, r^2])\n",
    "    print(\"interp_poly=\", interp_poly)\n",
    "    vanishing_poly = UniPolynomial([-r, 1])*UniPolynomial([r, 1]) * UniPolynomial([-r*r, 1])\n",
    "    print(\"vanishing_poly=\", vanishing_poly)\n",
    "\n",
    "    h_agg_poly = UniPolynomial(h_agg)\n",
    "\n",
    "    quo_poly, rem = divmod(h_agg_poly-interp_poly, vanishing_poly)\n",
    "    print(\"quo={}, rem={}\".format(quo_poly, rem))\n",
    "    # assert rem == UniPolynomial([0])\n",
    "    print(\"quo_poly={}\".format(quo_poly))\n",
    "    \n",
    "    g_poly = h_agg_poly - interp_poly\n",
    "    print(\"g_poly=\", g_poly.coeffs)\n",
    "    print(\"rem={}\".format(g_poly % vanishing_poly))\n",
    "    print(\"quo={}\".format(g_poly // vanishing_poly))\n",
    "    \n",
    "    Cq = kzg10.commit(quo_poly.coeffs)\n",
    "    transcript.absorb(Cq)\n",
    "\n",
    "    zeta = transcript.squeeze()\n",
    "    print(\"zeta={}\".format(zeta))\n",
    "    \n",
    "    interp_at_zeta =interp_poly.evaluate(zeta)\n",
    "    print(\"interp_at_zeta={}\".format(interp_at_zeta))\n",
    "    \n",
    "    r_poly = h_agg_poly - UniPolynomial([interp_at_zeta]) - quo_poly * ((zeta - r) * (zeta + r) * (zeta - r*r))\n",
    "    print(\"h_agg_poly - UniPolynomial([interp_at_zeta])=\", h_agg_poly - UniPolynomial([interp_at_zeta]))\n",
    "    print(\"quo_poly * ((zeta - r) * (zeta + r) * (zeta - r*r))=\", quo_poly * ((zeta - r) * (zeta + r) * (zeta - r*r)))\n",
    "    print(\"r_poly=\", r_poly)\n",
    "\n",
    "    print(\"r(zeta)={}\".format(r_poly.evaluate(zeta)))\n",
    "\n",
    "    Cr = kzg10.commit(r_poly.coeffs)\n",
    "\n",
    "    transcript.absorb(Cr)\n",
    "\n",
    "    arg_r_poly_at_zeta =kzg10.prove_eval(r_poly.coeffs, point=zeta, v=0)\n",
    "\n",
    "    # DEBUG: verify r_poly argument\n",
    "    assert kzg10.verify_eval(Cr, arg_r_poly_at_zeta, point=zeta, v=0)\n",
    "\n",
    "    return (h_uni_cm_vec, evals_pos, evals_neg, evals_sq, Cq, arg_r_poly_at_zeta)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "id": "5f5d1686",
   "metadata": {
    "vscode": {
     "languageId": "python"
    }
   },
   "outputs": [],
   "source": [
    "def verify_eval_arg_opt(C, arg, point, v, transcript):\n",
    "    \"\"\"\n",
    "    Verify an optimized evaluation argument proof.\n",
    "\n",
    "    Args:\n",
    "    C: commitment to f\n",
    "    arg: argument to be verified (output of prove_eval_arg_opt)\n",
    "    point: evaluation point\n",
    "    v: claimed evaluation value\n",
    "    transcript: proof transcript\n",
    "    \"\"\"\n",
    "    k = len(point)\n",
    "    n = 1 << k\n",
    "    \n",
    "    transcript.absorb(C)\n",
    "    transcript.absorb(point)\n",
    "    transcript.absorb(v)\n",
    "\n",
    "    print(\"C=\", C)\n",
    "\n",
    "    print(\"arg=\", arg)\n",
    "\n",
    "    h_uni_cm_vec, evals_pos, evals_neg, evals_sq, Cq, Cw = arg\n",
    "\n",
    "    for i in range(len(h_uni_cm_vec)):\n",
    "        transcript.absorb(h_uni_cm_vec[i])\n",
    "    \n",
    "    beta = transcript.squeeze()\n",
    "    print(\"beta=\", beta)\n",
    "\n",
    "    for i in range(k):\n",
    "        transcript.absorb(evals_pos[i])\n",
    "        transcript.absorb(evals_neg[i])\n",
    "        transcript.absorb(evals_sq[i])\n",
    "    \n",
    "    gamma = transcript.squeeze()\n",
    "    print(\"gamma=\", gamma)\n",
    "\n",
    "    Ch = C\n",
    "    for i in range(0, k-1):\n",
    "        Ch = Ch + (gamma**(i+1)) * h_uni_cm_vec[i]\n",
    "    print(\"Ch=\", Ch)\n",
    "    \n",
    "    h_agg_poly_at_beta = sum([evals_pos[i]*(gamma**i) for i in range(k)])\n",
    "    h_agg_poly_at_neg_beta = sum([evals_neg[i]*(gamma**i) for i in range(k)])\n",
    "    h_agg_poly_at_beta_sq = sum([evals_sq[i]*(gamma**i) for i in range(k)])\n",
    "    print(\"h_agg_poly_at_beta={}, h_agg_poly_at_neg_beta={}, h_agg_poly_at_beta_sq={}\".format(h_agg_poly_at_beta, h_agg_poly_at_neg_beta, h_agg_poly_at_beta_sq))\n",
    "\n",
    "    # vanishing_poly = UniPolynomial([-beta, h_agg_poly_at_beta]) * UniPolynomial([beta, h_agg_poly_at_neg_beta]) * UniPolynomial([-beta*beta, h_agg_poly_at_beta_sq])\n",
    "    interp_poly = UniPolynomial.interpolate(\n",
    "        [h_agg_poly_at_beta, h_agg_poly_at_neg_beta, h_agg_poly_at_beta_sq], \n",
    "        [beta, -beta, beta**2])\n",
    "\n",
    "    transcript.absorb(Cq)\n",
    "\n",
    "    zeta = transcript.squeeze()\n",
    "    print(\"zeta={}\".format(zeta))\n",
    "    \n",
    "    # vanishing_poly_at_zeta= vanishing_poly.evaluate(zeta)\n",
    "    interp_at_zeta = interp_poly.evaluate(zeta)\n",
    "    print(\"interp_at_zeta={}\".format(interp_at_zeta))\n",
    "\n",
    "    Cr = Ch - kzg10.commit([interp_at_zeta]) - Cq * ((zeta - beta) * (zeta + beta) * (zeta - beta*beta))\n",
    "\n",
    "    print(\"Cr=\", Cr)\n",
    "    print(\"Cq=\", Cq)\n",
    "\n",
    "    transcript.absorb(Cr)\n",
    "\n",
    "    # Verify r_poly argument\n",
    "    if not kzg10.verify_eval(Cr, Cw, point=zeta, v=0):\n",
    "        return False\n",
    "\n",
    "    # Verify evaluations\n",
    "    evals_sq = evals_sq + [v]\n",
    "    for i in range(k):\n",
    "        if evals_sq[i+1] != (evals_pos[i] + evals_neg[i])/2 + point[i] * (evals_pos[i] - evals_neg[i])/(2*beta):\n",
    "            return False\n",
    "\n",
    "    return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "id": "f8c89c28",
   "metadata": {
    "vscode": {
     "languageId": "python"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "([126, 151], [181, 64])"
      ]
     },
     "execution_count": 45,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "UniPolynomial.polynomial_division_with_remainder([46, 25, 25, 1], [123, 128, 170])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "id": "cc9854bb",
   "metadata": {
    "vscode": {
     "languageId": "python"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "15679 + 34765x + 40748x^2 + 25670x^3"
      ]
     },
     "execution_count": 46,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "UniPolynomial([126, 151]) * UniPolynomial([123, 128, 170]) + UniPolynomial([181, 64])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "id": "5b9bd461",
   "metadata": {
    "vscode": {
     "languageId": "python"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(126 + 151x, 181 + 64x)"
      ]
     },
     "execution_count": 47,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "divmod( UniPolynomial([46, 25, 25, 1]),  UniPolynomial([123, 128, 170]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "id": "1a3c287b",
   "metadata": {
    "vscode": {
     "languageId": "python"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "181 + 64x"
      ]
     },
     "execution_count": 48,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "UniPolynomial([46, 25, 25, 1]) % UniPolynomial([123, 128, 170])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "id": "fed6a8d3",
   "metadata": {
    "vscode": {
     "languageId": "python"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<class 'kzg10.Commitment'>"
      ]
     },
     "execution_count": 49,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "type(ff_cm)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 50,
   "id": "4bbe415e",
   "metadata": {
    "vscode": {
     "languageId": "python"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "h_uni_cm_vec= [Commitment(93*X0 + 81)]\n",
      "h_uni_poly_vec= [[1, 3, 2, 1], [81, 93]]\n",
      "coeffs= [81, 93]\n",
      "r= 177\n",
      "evals_pos= [36, 137]\n",
      "evals_neg= [25, 25]\n",
      "evals_sq= [134, 150]\n",
      "gamma= 107\n",
      "h_agg= [176, 111, 2, 1]\n",
      "h_agg_poly_at_r=27, h_agg_poly_at_neg_r=191, h_agg_poly_at_r_sq=165\n",
      "dbg_evals_sq[i+1]=150, interp_and_eval_line(evals_pos[i], evals_neg[i], r, point[i])=150\n",
      "i=0, True\n",
      "dbg_evals_sq[i+1]=123, interp_and_eval_line(evals_pos[i], evals_neg[i], r, point[i])=123\n",
      "i=1, True\n",
      "interp_poly= 67 + 174x + 65x^2\n",
      "vanishing_poly= 109 + 130x + 130x^2 + x^3\n",
      "quo=1, rem=0\n",
      "quo_poly=1\n",
      "g_poly= [109, 130, 130, 1]\n",
      "rem=0\n",
      "quo=1\n",
      "zeta=143\n",
      "interp_at_zeta=46\n",
      "h_agg_poly - UniPolynomial([interp_at_zeta])= 130 + 111x + 2x^2 + x^3\n",
      "quo_poly * ((zeta - r) * (zeta + r) * (zeta - r*r))= 30\n",
      "r_poly= 100 + 111x + 2x^2 + x^3\n",
      "r(zeta)=0\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "([Commitment(93*X0 + 81)],\n",
       " [36, 137],\n",
       " [25, 25],\n",
       " [134, 150],\n",
       " Commitment(1),\n",
       " Commitment(X0^2 - 48*X0 + 2))"
      ]
     },
     "execution_count": 50,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "arg = prove_eval_arg_opt(ff_cm, [1, 3, 2, 1], point=[91, 181], v=123, transcript=transcript.clone()); arg"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 51,
   "id": "3ab07692",
   "metadata": {
    "vscode": {
     "languageId": "python"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "C= Commitment(X0^3 + 2*X0^2 + 3*X0 + 1)\n",
      "arg= ([Commitment(93*X0 + 81)], [36, 137], [25, 25], [134, 150], Commitment(1), Commitment(X0^2 - 48*X0 + 2))\n",
      "beta= 177\n",
      "gamma= 107\n",
      "Ch= Commitment(X0^3 + 2*X0^2 - 82*X0 - 17)\n",
      "h_agg_poly_at_beta=27, h_agg_poly_at_neg_beta=191, h_agg_poly_at_beta_sq=165\n",
      "zeta=143\n",
      "interp_at_zeta=46\n",
      "Cr= Commitment(X0^3 + 2*X0^2 - 82*X0 - 93)\n",
      "Cq= Commitment(1)\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 51,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "verify_eval_arg_opt(ff_cm, arg, point=[91, 181], v=123, transcript=transcript.clone())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 52,
   "id": "7b38cce5",
   "metadata": {
    "vscode": {
     "languageId": "python"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "X0^3 + 2*X0^2 + 21*X0 - 2"
      ]
     },
     "execution_count": 52,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "gamma=50\n",
    "(X0^3 + 2*X0^2 + 3*X0 + 1) + (93*X0 + 81) * gamma "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 53,
   "id": "e13fddce",
   "metadata": {
    "vscode": {
     "languageId": "python"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(176, 51)"
      ]
     },
     "execution_count": 53,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "uni_eval_from_coeffs([1, 3, 2, 1], 174), uni_eval_from_coeffs([81, 93], 174)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 54,
   "id": "c6277139",
   "metadata": {
    "vscode": {
     "languageId": "python"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<class 'sage.rings.finite_rings.integer_mod.IntegerMod_int'>"
      ]
     },
     "execution_count": 54,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "type(transcript.squeeze())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "b4f20375",
   "metadata": {
    "vscode": {
     "languageId": "python"
    }
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 55,
   "id": "a808413d",
   "metadata": {
    "vscode": {
     "languageId": "python"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "5 + 7x + 9x^2"
      ]
     },
     "execution_count": 55,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "f1 = UniPolynomial([1, 2, 3])\n",
    "f2 = UniPolynomial([4, 5, 6])\n",
    "f3 = f1 + f2\n",
    "f3"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 56,
   "id": "c6c60ea6",
   "metadata": {
    "vscode": {
     "languageId": "python"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "4 + 13x + 28x^2 + 27x^3 + 18x^4"
      ]
     },
     "execution_count": 56,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "f1 = UniPolynomial([1, 2, 3])\n",
    "f2 = UniPolynomial([4, 5, 6])\n",
    "f3 = f1 * f2\n",
    "f3"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 57,
   "id": "8f7554d2",
   "metadata": {
    "vscode": {
     "languageId": "python"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3*X^2 + 2*X + 1"
      ]
     },
     "execution_count": 57,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def poly(cof):\n",
    "    return sum([cof[i] * X^i for i in range(len(cof))])\n",
    "\n",
    "poly([1, 2, 3])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 58,
   "id": "39dffa3e",
   "metadata": {
    "vscode": {
     "languageId": "python"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "18*X^4 + 27*X^3 + 28*X^2 + 13*X + 4"
      ]
     },
     "execution_count": 58,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "poly([1, 2, 3]) * poly([4, 5, 6])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 59,
   "id": "7b8b4f81",
   "metadata": {
    "vscode": {
     "languageId": "python"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(108 + 155x, 148)"
      ]
     },
     "execution_count": 59,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "f1 = UniPolynomial([1, 2, 3])\n",
    "f2 = UniPolynomial([4, 5])\n",
    "divmod(f1, f2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 60,
   "id": "013b5e5e",
   "metadata": {
    "vscode": {
     "languageId": "python"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3*X^2 + 2*X + 1"
      ]
     },
     "execution_count": 60,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(155*X + 108) * poly([4, 5]) + poly([148])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 61,
   "id": "9203d5b4",
   "metadata": {
    "vscode": {
     "languageId": "python"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "24 + 143x + 35x^2 + 183x^3 + x^4"
      ]
     },
     "execution_count": 61,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "z4 = UniPolynomial.vanishing_polynomial([Fp(1), Fp(2), Fp(3), Fp(4)]); z4"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 62,
   "id": "0be32b6a",
   "metadata": {
    "vscode": {
     "languageId": "python"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(169 + 26x + 184x^2 + x^3, 0)"
      ]
     },
     "execution_count": 62,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "z4 // (UniPolynomial([-1, 1])), z4 % (UniPolynomial([-1, 1]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 63,
   "id": "74ef4e1b",
   "metadata": {
    "vscode": {
     "languageId": "python"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(169 + 26x + 184x^2 + x^3, 0)"
      ]
     },
     "execution_count": 63,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "z4.division_by_linear_divisor(Fp(1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 64,
   "id": "efec1738",
   "metadata": {
    "vscode": {
     "languageId": "python"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(169 + 26x + 184x^2 + x^3, 0)"
      ]
     },
     "execution_count": 64,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "divmod(z4, UniPolynomial([-1, 1]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 65,
   "id": "864e7b74",
   "metadata": {
    "vscode": {
     "languageId": "python"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "([169, 26, 184, 1], [])"
      ]
     },
     "execution_count": 65,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "UniPolynomial.polynomial_division_with_remainder([24, 143, 35, 183, 1], [Fp(-1), Fp(1)])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 66,
   "id": "e633ae12",
   "metadata": {
    "vscode": {
     "languageId": "python"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(169 + 26x + 184x^2 + x^3, 0)"
      ]
     },
     "execution_count": 66,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "divmod(z4, UniPolynomial([-1, 1]))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 67,
   "id": "f29aa375",
   "metadata": {
    "vscode": {
     "languageId": "python"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "X^4 + 183*X^3 + 35*X^2 + 143*X + 24"
      ]
     },
     "execution_count": 67,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(X-1)*(X-2)*(X-3)*(X-4)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 68,
   "id": "63e35814",
   "metadata": {
    "vscode": {
     "languageId": "python"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[6, 161, 95, 129]"
      ]
     },
     "execution_count": 68,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "cof = UniPolynomial.compute_coeffs_from_evals_fast([5, 3, 2, 4], [1, 2, 3, 4]); cof"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 69,
   "id": "54224b68",
   "metadata": {
    "vscode": {
     "languageId": "python"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[5, 3, 2, 4]"
      ]
     },
     "execution_count": 69,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "[poly(cof).subs(X=i+1) for i in range(4)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 70,
   "id": "3b401b3b",
   "metadata": {
    "vscode": {
     "languageId": "python"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[5, 3, 2, 4]"
      ]
     },
     "execution_count": 70,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "UniPolynomial.compute_evals_from_coeffs_fast(cof, [1, 2, 3, 4])"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c7f02d71",
   "metadata": {},
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": 71,
   "id": "e772dc36",
   "metadata": {
    "vscode": {
     "languageId": "python"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[100, 77, 0, 21]"
      ]
     },
     "execution_count": 71,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "cof = UniPolynomial.ntt_coeffs_from_evals([5, 3, 2, 4], 2, H4[1]); cof"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 72,
   "id": "7b7ac793",
   "metadata": {
    "vscode": {
     "languageId": "python"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[5, 3, 2, 4]"
      ]
     },
     "execution_count": 72,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "UniPolynomial.ntt_evals_from_coeffs(cof, 2, H4[1])"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "05c53a97",
   "metadata": {},
   "source": [
    "## Optimization \n",
    "\n",
    "1. Prover doesn't need to send $h^{(i)}(\\beta^2)$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 73,
   "id": "d33b6b33",
   "metadata": {
    "vscode": {
     "languageId": "python"
    }
   },
   "outputs": [],
   "source": [
    "## Interpolate two points into a polynomial and evaluate it at X=r\n",
    "#\n",
    "#   f(X) = [(-x, a), (x, b)] -> (a+b)/2 + ((a-b) / (2*x)) * X\n",
    "#\n",
    "#   f(r) = (a+b)/2 + r * (a-b) / (2*x)\n",
    "#\n",
    "# \n",
    "#(evals_pos[i] + evals_neg[i])/2 + point[i] * (evals_pos[i] - evals_neg[i])/(2*r)))\n",
    "\n",
    "\n",
    "def interp_and_eval_line(a, b, r, x):\n",
    "    \"\"\"\n",
    "    Interpolate two points into a polynomial and evaluate it at X=r\n",
    "\n",
    "        f(X) = [(-x, a), (x, b)] -> (a+b)/2 + ((a-b) / (2*x)) * X\n",
    "\n",
    "        f(r) = (a+b)/2 + r * (a-b) / (2*x)\n",
    "    Args:\n",
    "        a (int): The evaluation at -x\n",
    "        b (int): The evaluation at x\n",
    "        r (int): The point at which to evaluate the polynomial\n",
    "        x (int): The x-coordinate of the point\n",
    "\n",
    "    Returns:\n",
    "        int: The result of evaluating the polynomial at X=r\n",
    "    \"\"\"\n",
    "    return ((a + b) / 2 + r * (a - b) / (2 * x))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 74,
   "id": "40a6ced6",
   "metadata": {
    "vscode": {
     "languageId": "python"
    }
   },
   "outputs": [],
   "source": [
    "def prove_eval_arg_opt_opt(C, f, point, v, transcript, debug=0):\n",
    "    \"\"\"\n",
    "    C: commitment to f\n",
    "    f: polynomial\n",
    "    point: evaluation point\n",
    "    v: evaluation value\n",
    "    Rng: randomness\n",
    "    \"\"\"\n",
    "    \n",
    "    n = len(f)\n",
    "    k = log_2(n)\n",
    "    if len(point) != k:\n",
    "        raise ValueError(\"Invalid evaluation point, k={}, while len(point)={}\".format(k, len(point)))\n",
    "    if not is_power_of_two(n):\n",
    "        raise ValueError(\"Invalid polynomial length\")\n",
    "    \n",
    "    transcript.absorb(C)\n",
    "    transcript.absorb(point)\n",
    "    transcript.absorb(v)\n",
    "\n",
    "    # Split and fold polynomials\n",
    "    coeffs = f[:]\n",
    "    h_uni_cm_vec = []\n",
    "    h_uni_poly_vec = [coeffs]\n",
    "    for i in range(k-1):\n",
    "        f_even = coeffs[::2]\n",
    "        f_odd = coeffs[1::2]\n",
    "        coeffs = [Fp(f_even[j] + point[i] * f_odd[j])  for j in range(len(f_even))]\n",
    "        h_cm = kzg10.commit(coeffs)\n",
    "\n",
    "        transcript.absorb(h_cm)\n",
    "\n",
    "        h_uni_poly_vec.append(coeffs)\n",
    "        h_uni_cm_vec.append(h_cm)\n",
    "\n",
    "    if debug > 0: \n",
    "        coeffs = [coeffs[i] + point[k-1] * coeffs[i+1] for i in range(0, len(coeffs), 2)]\n",
    "        print(\"check: fully folded polynomial must be equal to the claimed evaluation: {} = {}\".format(coeffs[0], v))\n",
    "        assert (coeffs[0] == v)\n",
    "        assert len(coeffs) == 1\n",
    "        print(\"coeffs=\", coeffs)\n",
    "        print(\"h_uni_cm_vec=\", h_uni_cm_vec)\n",
    "        print(\"h_uni_poly_vec=\", h_uni_poly_vec)\n",
    "\n",
    "    # Sample randomness and reply evaluations\n",
    "    beta = transcript.squeeze()\n",
    "    print(\"beta=\", beta)\n",
    "    evals_pos = []\n",
    "    evals_neg = []    \n",
    "    evals_sq = []\n",
    "    for i in range(k):\n",
    "        poly = h_uni_poly_vec[i]\n",
    "        poly_at_beta = uni_eval_from_coeffs(poly, beta)\n",
    "        poly_at_neg_beta = uni_eval_from_coeffs(poly, (-1) * beta)\n",
    "        poly_at_beta_sq = uni_eval_from_coeffs(poly, beta^2)\n",
    "        evals_pos.append(poly_at_beta)\n",
    "        evals_neg.append(poly_at_neg_beta)\n",
    "        evals_sq.append(poly_at_beta_sq)\n",
    "        transcript.absorb(poly_at_beta)\n",
    "        transcript.absorb(poly_at_neg_beta)\n",
    "\n",
    "    transcript.absorb(evals_sq[0])\n",
    "\n",
    "    print(\"evals_pos=\", evals_pos)\n",
    "    print(\"evals_neg=\", evals_neg)\n",
    "    print(\"evals_sq=\", evals_sq)\n",
    "\n",
    "    gamma = transcript.squeeze()\n",
    "    \n",
    "    if debug > 0: \n",
    "        print(\"gamma=\", gamma)\n",
    "\n",
    "    h_agg = [0] * n\n",
    "    for i in range(n):\n",
    "        for j in range(k):\n",
    "            poly = h_uni_poly_vec[j]\n",
    "            if i < len(poly):\n",
    "                h_agg[i] += poly[i] * (gamma**j)\n",
    "    if debug > 1: \n",
    "        print(\"h_agg=\", h_agg)\n",
    "    \n",
    "    h_agg_poly_at_beta = uni_eval_from_coeffs(h_agg, beta)\n",
    "    h_agg_poly_at_neg_beta = uni_eval_from_coeffs(h_agg, -beta)\n",
    "    h_agg_poly_at_beta_sq = uni_eval_from_coeffs(h_agg, beta^2)\n",
    "\n",
    "    if debug > 1: \n",
    "        print(\"h_agg_poly_at_beta={}, h_agg_poly_at_neg_beta={}, h_agg_poly_at_beta_sq={}\".format(h_agg_poly_at_beta, h_agg_poly_at_neg_beta, h_agg_poly_at_beta_sq))\n",
    "\n",
    "    # DEBUG: verify h_agg\n",
    "    if debug > 0:\n",
    "        print(\"check: aggregated h(X) must be equal to sum(h_i(X)) at (beta, -beta, beta^2)\")\n",
    "        assert h_agg_poly_at_beta == sum([evals_pos[i]*(gamma**i) for i in range(k)])\n",
    "        assert h_agg_poly_at_neg_beta == sum([evals_neg[i]*(gamma**i) for i in range(k)])\n",
    "        assert h_agg_poly_at_beta_sq == sum([evals_sq[i]*(gamma**i) for i in range(k)])\n",
    "\n",
    "    # DEBUG: verify evaluations\n",
    "    if debug > 0:\n",
    "        dbg_evals_sq = evals_sq[:] + [v]\n",
    "        print(\"dbg_evals_sq=\", dbg_evals_sq)\n",
    "        for i in range(k):\n",
    "            print(\"check: h_{i+1}(r^2) = h_i(r) + h_i(-r))/2 + x_i * (h_i(r) - h_i(-r))/(2*r)\")\n",
    "            print(\"i={}, {}, {}\".format(i, \n",
    "                dbg_evals_sq[i+1], interp_and_eval_line(evals_pos[i], evals_neg[i], point[i], beta)))\n",
    "\n",
    "    h_agg_poly = UniPolynomial(h_agg)\n",
    "    interp_poly = UniPolynomial.interpolate([h_agg_poly_at_beta, h_agg_poly_at_neg_beta, h_agg_poly_at_beta_sq], [beta, -beta, beta^2])\n",
    "    vanishing_poly = UniPolynomial([-beta, 1])*UniPolynomial([beta, 1]) * UniPolynomial([-beta*beta, 1])\n",
    "    g_poly = h_agg_poly - interp_poly\n",
    "    quo_poly, rem = divmod(g_poly, vanishing_poly)\n",
    "\n",
    "    if debug > 0:\n",
    "        # assert rem == UniPolynomial([0])\n",
    "        pass\n",
    "\n",
    "    if debug > 1:\n",
    "        print(\"interp_poly=\", interp_poly)\n",
    "        print(\"vanishing_poly=\", vanishing_poly)    \n",
    "        print(\"quo={}, rem={}\".format(quo_poly, rem))\n",
    "        print(\"quo_poly={}\".format(quo_poly))\n",
    "        print(\"rem={}\".format(rem))\n",
    "        print(\"quo={}\".format(quo_poly))\n",
    "    \n",
    "    Cq = kzg10.commit(quo_poly.coeffs)\n",
    "    transcript.absorb(Cq)\n",
    "\n",
    "    zeta = transcript.squeeze()\n",
    "    print(\"zeta={}\".format(zeta))\n",
    "    \n",
    "    interp_at_zeta =interp_poly.evaluate(zeta)\n",
    "    print(\"interp_at_zeta={}\".format(interp_at_zeta))\n",
    "    \n",
    "    r_poly = h_agg_poly - UniPolynomial([interp_at_zeta]) - quo_poly * ((zeta - beta) * (zeta + beta) * (zeta - beta*beta))\n",
    "    print(\"h_agg_poly - UniPolynomial([interp_at_zeta])=\", h_agg_poly - UniPolynomial([interp_at_zeta]))\n",
    "    print(\"quo_poly * ((zeta - beta) * (zeta + beta) * (zeta - beta*beta))=\", quo_poly * ((zeta - beta) * (zeta + beta) * (zeta - beta*beta)))\n",
    "    print(\"r_poly=\", r_poly)\n",
    "\n",
    "    print(\"r(zeta)={}\".format(r_poly.evaluate(zeta)))\n",
    "\n",
    "    Cr = kzg10.commit(r_poly.coeffs)\n",
    "\n",
    "    transcript.absorb(Cr)\n",
    "\n",
    "    arg_r_poly_at_zeta =kzg10.prove_eval(r_poly.coeffs, point=zeta, v=0)\n",
    "\n",
    "    # DEBUG: verify r_poly argument\n",
    "    if debug > 0:\n",
    "        print(\"check: `r(z)=0` argument must hold\")\n",
    "        assert kzg10.verify_eval(Cr, arg_r_poly_at_zeta, point=zeta, v=0)\n",
    "\n",
    "    return (h_uni_cm_vec, evals_pos, evals_neg, evals_sq[:1], Cq, arg_r_poly_at_zeta)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 75,
   "id": "62221eae",
   "metadata": {
    "vscode": {
     "languageId": "python"
    }
   },
   "outputs": [],
   "source": [
    "def verify_eval_arg_opt_opt(C, arg, point, v, transcript, debug=0):\n",
    "    \"\"\"\n",
    "    Verify an optimized evaluation argument proof.\n",
    "\n",
    "    Args:\n",
    "    C: commitment to f\n",
    "    arg: argument to be verified (output of prove_eval_arg_opt)\n",
    "    point: evaluation point\n",
    "    v: claimed evaluation value\n",
    "    transcript: proof transcript\n",
    "    \"\"\"\n",
    "    k = len(point)\n",
    "    n = 1 << k\n",
    "    \n",
    "    if debug > 1:\n",
    "        print(\"C={}, arg={}, point={}, v={}\".format(C, arg, point, v))\n",
    "\n",
    "    transcript.absorb(C)\n",
    "    transcript.absorb(point)\n",
    "    transcript.absorb(v)\n",
    "\n",
    "    h_uni_cm_vec, evals_pos, evals_neg, evals_sq, Cq, Cw = arg\n",
    "\n",
    "    for i in range(len(h_uni_cm_vec)):\n",
    "        transcript.absorb(h_uni_cm_vec[i])\n",
    "    \n",
    "    beta = transcript.squeeze()\n",
    "    if debug > 1:\n",
    "        print(\"> beta = {}\".format(beta))\n",
    "\n",
    "    for i in range(k):\n",
    "        transcript.absorb(evals_pos[i])\n",
    "        transcript.absorb(evals_neg[i])\n",
    "        evals_sq.append(interp_and_eval_line(evals_pos[i], evals_neg[i], point[i], beta))\n",
    "    transcript.absorb(evals_sq[0])\n",
    "\n",
    "    if debug > 1:\n",
    "        print(\"> evals_sq = {}\".format(evals_sq))\n",
    "    \n",
    "    # 1st check:\n",
    "    if debug > 0:\n",
    "        print(\"🛡️: check if the evaluation f({})={} is correct\".format(point, v))\n",
    "        print(\"    by computing the folded polynomial h_{}({}^2) ?= {}\".format(k, beta, v))\n",
    "        if (evals_sq[-1] == v): \n",
    "            print(\"😀 ✅\")\n",
    "    if not (evals_sq[-1] == v):\n",
    "        return False\n",
    "    \n",
    "    gamma = transcript.squeeze()\n",
    "    if debug > 1:\n",
    "        print(\"> gamma = {}\".format(gamma))\n",
    "\n",
    "    Ch = C\n",
    "    for i in range(0, k-1):\n",
    "        Ch = Ch + (gamma**(i+1)) * h_uni_cm_vec[i]\n",
    "\n",
    "    if debug > 1:\n",
    "        print(\"> Commitment of h(X): Ch={}\".format(Ch))\n",
    "    \n",
    "    # Compute h_agg(beta), h_agg(-beta), h_agg(beta^2)\n",
    "    h_agg_poly_at_beta = sum([evals_pos[i]*(gamma**i) for i in range(k)])\n",
    "    h_agg_poly_at_neg_beta = sum([evals_neg[i]*(gamma**i) for i in range(k)])\n",
    "    h_agg_poly_at_beta_sq = sum([evals_sq[i]*(gamma**i) for i in range(k)])\n",
    "\n",
    "    if debug > 1:\n",
    "        print(\"> h_agg_poly_at_beta={}\".format(h_agg_poly_at_beta))\n",
    "        print(\"> h_agg_poly_at_neg_beta={}\".format(h_agg_poly_at_neg_beta))\n",
    "        print(\"> h_agg_poly_at_beta_sq={}\".format(h_agg_poly_at_beta_sq))\n",
    "\n",
    "    # Interpolate c(X) from three points: \n",
    "    #\n",
    "    #    [(beta, h_agg(beta)), (-beta, h_agg(-beta)), (beta^2, h_agg(beta^2))]\n",
    "\n",
    "    interp_poly = UniPolynomial.interpolate(\n",
    "        [h_agg_poly_at_beta, h_agg_poly_at_neg_beta, h_agg_poly_at_beta_sq], \n",
    "        [beta, -beta, beta**2])\n",
    "\n",
    "    # h_agg(X) - c(X) = q(X) * (X-beta)(X+beta)(X-beta^2)\n",
    "    # \n",
    "    # Receive Cq = Commit(c(X)) \n",
    "    transcript.absorb(Cq)\n",
    "\n",
    "    # Sample randomness\n",
    "    zeta = transcript.squeeze()\n",
    "\n",
    "    if debug > 1:\n",
    "        print(\"> zeta = {}\".format(zeta))\n",
    "    \n",
    "    # vanishing_poly_at_zeta= vanishing_poly.evaluate(zeta)\n",
    "    interp_at_zeta = interp_poly.evaluate(zeta)\n",
    "    vanishing_poly_at_zeta = ((zeta - beta) * (zeta + beta) * (zeta - beta*beta))\n",
    "\n",
    "    print(\"interp_at_zeta={}\".format(interp_at_zeta))\n",
    "\n",
    "    Cr = Ch - kzg10.commit([interp_at_zeta]) - Cq * vanishing_poly_at_zeta\n",
    "\n",
    "    if debug > 1:\n",
    "        print(\"> Cr={}\".format(Cr))\n",
    "        print(\"> Cq={}\".format(Cq))\n",
    "\n",
    "    transcript.absorb(Cr)\n",
    "\n",
    "    # Verify r_poly argument\n",
    "    \n",
    "    # 2. Check if r(z)=0\n",
    "    Cw_verified = kzg10.verify_eval(Cr, Cw, point=zeta, v=0)\n",
    "\n",
    "    if debug > 0:\n",
    "        if Cw_verified: print(\"🛡️: check if r(z)=0 😀 ✅\")\n",
    "        else: print(\"🛡️: check if r(z)=0 😢 ❌\")\n",
    "\n",
    "    if not Cw_verified:\n",
    "        return False\n",
    "\n",
    "    return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 76,
   "id": "b0bc3b1c",
   "metadata": {
    "vscode": {
     "languageId": "python"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "check: fully folded polynomial must be equal to the claimed evaluation: 123 = 123\n",
      "coeffs= [123]\n",
      "h_uni_cm_vec= [Commitment(93*X0 + 81)]\n",
      "h_uni_poly_vec= [[1, 3, 2, 1], [81, 93]]\n",
      "beta= 117\n",
      "evals_pos= [37, 154]\n",
      "evals_neg= [102, 8]\n",
      "evals_sq= [116, 130]\n",
      "gamma= 103\n",
      "check: aggregated h(X) must be equal to sum(h_i(X)) at (beta, -beta, beta^2)\n",
      "dbg_evals_sq= [116, 130, 123]\n",
      "check: h_{i+1}(r^2) = h_i(r) + h_i(-r))/2 + x_i * (h_i(r) - h_i(-r))/(2*r)\n",
      "i=0, 130, 130\n",
      "check: h_{i+1}(r^2) = h_i(r) + h_i(-r))/2 + x_i * (h_i(r) - h_i(-r))/(2*r)\n",
      "i=1, 123, 123\n",
      "zeta=159\n",
      "interp_at_zeta=152\n",
      "h_agg_poly - UniPolynomial([interp_at_zeta])= 86 + 125x + 2x^2 + x^3\n",
      "quo_poly * ((zeta - beta) * (zeta + beta) * (zeta - beta*beta))= 146\n",
      "r_poly= 133 + 125x + 2x^2 + x^3\n",
      "r(zeta)=0\n",
      "check: `r(z)=0` argument must hold\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "([Commitment(93*X0 + 81)],\n",
       " [37, 154],\n",
       " [102, 8],\n",
       " [116],\n",
       " Commitment(1),\n",
       " Commitment(X0^2 - 32*X0 + 55))"
      ]
     },
     "execution_count": 76,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "arg = prove_eval_arg_opt_opt(ff_cm, [1, 3, 2, 1], \n",
    "            point=[91, 181], v=123, transcript=transcript.clone(), debug=1); arg"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 77,
   "id": "ed6cc7db",
   "metadata": {
    "vscode": {
     "languageId": "python"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "🛡️: check if the evaluation f([91, 181])=123 is correct\n",
      "    by computing the folded polynomial h_2(117^2) ?= 123\n",
      "😀 ✅\n",
      "interp_at_zeta=152\n",
      "🛡️: check if r(z)=0 😀 ✅\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 77,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "verify_eval_arg_opt_opt(ff_cm, arg, point=[91, 181], v=123, transcript=transcript.clone(), debug=1)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "SageMath 10.4",
   "language": "sage",
   "name": "sagemath-10.4"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "sage",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.12.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}