src/Basefold.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "2e744d39-4152-4912-b885-92ee5a024523",
   "metadata": {},
   "source": [
    "## Finite Field\n",
    "\n",
    "$$\n",
    "p = 64 * 3 + 1\n",
    "$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 91,
   "id": "22dfcc22-72f3-433e-8d67-f221505d0520",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Finite Field of size 193"
      ]
     },
     "execution_count": 91,
     "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": 92,
   "id": "690ee006-acb9-4c7a-97ec-0f92e0f92b20",
   "metadata": {},
   "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": 92,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "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": 93,
   "id": "1566f2f0",
   "metadata": {},
   "outputs": [],
   "source": [
    "from field import magic\n",
    "\n",
    "Fp = magic(Fp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 94,
   "id": "3b261982-edd0-470f-b3fd-2f6d4465e2bd",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[0, 1, 1, 0, 0]"
      ]
     },
     "execution_count": 94,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "\n",
    "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)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 95,
   "id": "a81adba5-7a84-40a6-8ce3-0d2e35876d5f",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(False, 4)"
      ]
     },
     "execution_count": 95,
     "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": 96,
   "id": "5ae76d5c-3d64-4354-a81f-99fda3437b30",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "X0*X1 - X0 - X1 + 1"
      ]
     },
     "execution_count": 96,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(1 - X0) * (1 - X1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 97,
   "id": "9d8ea24d-a776-4f0b-9dbe-da8f28302517",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Field([144])"
      ]
     },
     "execution_count": 97,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Fp(((1 - X0) * (1 - X1))(X0=9, X1=19))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 98,
   "id": "30aa9d48-3f31-4bd2-8695-4da4fedd694c",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Field([171])"
      ]
     },
     "execution_count": 98,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Fp((X0 * X1)(X0=9, X1=19))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9cfa0221-000c-4646-9067-d933100e23cb",
   "metadata": {},
   "source": [
    "## Foldable code "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 99,
   "id": "c1a35030-fb57-49d9-9214-c73d7fca1a5b",
   "metadata": {},
   "outputs": [],
   "source": [
    "# m: message\n",
    "# k0: message length of base code\n",
    "# c: blowup factor\n",
    "\n",
    "def rep_encode(m, k0, c):\n",
    "    assert len(m) % k0 == 0, \"len(m): %d is not a multiple of k0: %d\" % (len(m), k0)\n",
    "    code = []\n",
    "    for i in range(0, c*len(m), k0):\n",
    "        for j in range(0, c):\n",
    "            code += m[i:i+k0]\n",
    "    return code"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 100,
   "id": "5cb74f36-9d11-49f7-a83d-1c1d56dda5df",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "([1, 1, 1, 2, 2, 2],\n",
       " [1, 2, 1, 2, 1, 2, 3, 4, 3, 4, 3, 4],\n",
       " [1, 2, 3, 4, 1, 2, 3, 4, 1, 2, 3, 4])"
      ]
     },
     "execution_count": 100,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "rep_encode([1,2],1, 3), rep_encode([1,2,3,4], 2, 3), rep_encode([1,2,3,4], 4, 3)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ce661901-3c64-416d-95e5-44faa37494fb",
   "metadata": {},
   "source": [
    "### Reed-Solomon Code\n",
    "\n",
    "Fix a sequence $\\mathbf{\\alpha} = (\\alpha_1, \\alpha_2, \\ldots, \\alpha_n)$ of $n$ distict elements from $\\mathbf{F}_q$. Map a message $\\mathbf{m} = (m_0, m_1, \\ldots, m_{k_0 - 1})$ with $m_i \\in \\mathbf{F}_q$ to the degree $k_0 - 1$ polynomial.\n",
    "\n",
    "$$\n",
    "\\mathbf{m} \\mapsto f_{\\mathbf{m}}(X)\n",
    "$$\n",
    "\n",
    "where\n",
    "\n",
    "$$\n",
    "f_{\\mathbf{m}}(X) = \\sum_{i = 0}^{k_0 - 1} m_i X^i\n",
    "$$\n",
    "\n",
    "Then\n",
    "\n",
    "$$\n",
    "\\text{RS}_q[\\mathbf{\\alpha}, k_0](\\mathbf{m}) = (f_{\\mathbf{m}}(\\alpha_1), f_{\\mathbf{m}}(\\alpha_2), \\ldots, f_{\\mathbf{m}}(\\alpha_{n}))\n",
    "$$\n",
    "\n",
    "For simplicity, we can choose $\\alpha_1 = 0, \\alpha_2 = 1, \\ldots, \\alpha_{n} = n - 1$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 101,
   "id": "8ec08742-1b45-4e20-b227-f850d7fa0670",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Reed-Solomon code for m = (m_0, ..., m_{k_0 - 1})\n",
    "# alpha: evaluation points\n",
    "# c: blowup factor\n",
    "def rs_encode_single(m, alpha, c):\n",
    "    k0 = len(m)\n",
    "    code = [None] * (k0 * c)\n",
    "    for i in range(k0 * c): \n",
    "        # comput f_m(alpha[i])\n",
    "        code[i] = sum(m[j] * (alpha[i] ** j) for j in range(k0))\n",
    "    return code\n",
    "\n",
    "# Reed-Solomon code for m\n",
    "# m: message\n",
    "# k0: message length of base code\n",
    "# c: blowup factor\n",
    "# default alpha: [0, 1, 2, ... , k0*c - 1]\n",
    "def rs_encode(m, k0, c):\n",
    "    assert len(m) % k0 == 0, \"len(m): %d is not a multiple of k0: %d\" % (len(m), k0)\n",
    "    code = []\n",
    "    alpha = list(range(k0 * c)) # 这里默认 alpha = [0, 1, 2, ... , k0*c - 1]\n",
    "    for i in range(0, c*len(m), k0):\n",
    "        code += rs_encode_single(m[i:i+k0], alpha, c)\n",
    "    return code"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 102,
   "id": "b497c21c-09a2-4a6a-a708-0d0918842761",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "([1, 1, 1, 2, 2, 2],\n",
       " [1, 3, 5, 7, 9, 11, 3, 7, 11, 15, 19, 23],\n",
       " [1, 10, 49, 142, 313, 586, 985, 1534, 2257, 3178, 4321, 5710])"
      ]
     },
     "execution_count": 102,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "rs_encode([1,2],1,3), rs_encode([1,2,3,4], 2, 3), rs_encode([1,2,3,4], 4, 3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 103,
   "id": "882d3926-d8a1-4dc3-baf9-cc975395ebb4",
   "metadata": {},
   "outputs": [],
   "source": [
    "# m: message with length `n`\n",
    "# k0: message length of code `G_0`,  G_0: k0 \\otimes ck0\n",
    "# depth: \n",
    "# c: blowup factor\n",
    "# G_0: an encoding function\n",
    "#      G_0(m, k0, c)\n",
    "# T: RM code table\n",
    "\n",
    "def basefold_encode(m, k0, depth, c, T, G0=rep_encode, debug=False):\n",
    "    if debug: print(\">>> basefold_encode: m={}, k0={}, d={}, blowup_factor={}, T={}\".format(m, k0, depth, c, T))\n",
    "    kd = k0 * 2^depth\n",
    "    blowup_factor = c\n",
    "    assert len(m) == kd, \"len(m): %d != kd: %d\" % (len(m), kd)\n",
    "    assert len(T) == depth, \"len(T): %d != depth: %d\" % (len(T), depth)\n",
    "     \n",
    "    chunk_size = k0\n",
    "    chunk_num = 2^depth\n",
    "    \n",
    "    code = []\n",
    "    for i in range(chunk_num):\n",
    "        chunk = m[i*chunk_size: (i+1)*chunk_size]\n",
    "        chunk_code = G0(chunk, chunk_size, blowup_factor)\n",
    "        code += chunk_code\n",
    "    if debug: print(\">>> basefold_encode: code=\", code)\n",
    "\n",
    "    if depth == 0:\n",
    "        return code\n",
    "\n",
    "    chunk_size = k0 * blowup_factor\n",
    "    if debug: print(\">>> basefold_encode: chunk_size=\", chunk_size)\n",
    "    if debug: print(\">>> basefold_encode: chunk_num=\", chunk_num)\n",
    "\n",
    "\n",
    "    for i in range(0, depth):\n",
    "        table = T[i]\n",
    "        assert len(table) == chunk_size, \"table[{}] != chunk_size, len(table)={}, chunk_size={})\".format(i, len(table), chunk_size)\n",
    "        if debug: print(\">>> basefold_encode: table=\", table)\n",
    "        for c in range(0, chunk_num, 2):\n",
    "            left  = code[    c*chunk_size : (c+1)*chunk_size]\n",
    "            right = code[(c+1)*chunk_size : (c+2)*chunk_size]\n",
    "            if debug: print(\">>> basefold_encode: left={}, right={}\".format(left, right))\n",
    "\n",
    "            for j in range(0, chunk_size):\n",
    "                if debug: print(\">>> basefold_encode: i={}, c={}, j={}\".format(i, c, j))\n",
    "                rhs = right[j] * table[j]\n",
    "                lhs = left[j]\n",
    "                code[(c)*chunk_size + j] = lhs + rhs\n",
    "                code[(c+1)*chunk_size + j] = lhs - rhs\n",
    "        chunk_size = chunk_size * 2\n",
    "        chunk_num = chunk_num // 2\n",
    "    return code"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 104,
   "id": "b809c74e-9019-45fd-99b5-38867cb5e48d",
   "metadata": {},
   "outputs": [],
   "source": [
    "# basefold_encode(m, k0, depth, c, G0, T, debug=False):\n",
    "\n",
    "def basefold_encode_rec(m, k0, depth, c, T, G0=rep_encode, debug=False):\n",
    "    if depth == 0:\n",
    "        assert len(m) == k0, \"len(m): %d != k0: %d\" % (len(m), k0)\n",
    "        return G0(m, k0, c)\n",
    "    \n",
    "    kd = len(m)\n",
    "    half = kd / 2\n",
    "    code_size = c * kd\n",
    "\n",
    "    m_left = m[:half]\n",
    "    m_right = m[half:]\n",
    "    \n",
    "    code_left = basefold_encode_rec(m_left, k0, depth-1, c, T, G0=G0, debug=debug)\n",
    "    print(\"code_left=\", code_left)\n",
    "    code_right = basefold_encode_rec(m_right, k0, depth-1, c, T, G0=G0, debug=debug)\n",
    "    print(\"code_right=\", code_right)\n",
    "\n",
    "    t = T[depth-1]\n",
    "    assert len(t) == code_size/2, \"wrong table size, len(table)={}, code_size={})\".format(len(t), code_size/2)\n",
    "    if debug: print(\"t=\", t)\n",
    "    code_half = kd * c // 2\n",
    "    code = [0 for _ in range(code_half * 2)]\n",
    "    for j in range(code_half):\n",
    "        code[j] = code_left[j] + t[j] * code_right[j]\n",
    "        code[j+code_half] = code_left[j] - t[j] * code_right[j]\n",
    "    return code"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 105,
   "id": "c9fe4583-729c-49ae-b874-74e5115f2a8a",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      ">>> basefold_encode: m=[1, 2], k0=1, d=1, blowup_factor=2, T=[[X0, X1]]\n",
      ">>> basefold_encode: code= [1, 1, 2, 2]\n",
      ">>> basefold_encode: chunk_size= 2\n",
      ">>> basefold_encode: chunk_num= 2\n",
      ">>> basefold_encode: table= [X0, X1]\n",
      ">>> basefold_encode: left=[1, 1], right=[2, 2]\n",
      ">>> basefold_encode: i=0, c=0, j=0\n",
      ">>> basefold_encode: i=0, c=0, j=1\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "[2*X0 + 1, 2*X1 + 1, -2*X0 + 1, -2*X1 + 1]"
      ]
     },
     "execution_count": 105,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "basefold_encode([1, 2], k0=1, depth=1, c=2, T=[[X0, X1]], debug=True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 106,
   "id": "31e027b4-85c5-47b6-8b1f-1e54c2b928b8",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "code_left= [1, 1]\n",
      "code_right= [2, 2]\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "[2*X0 + 1, 2*X1 + 1, -2*X0 + 1, -2*X1 + 1]"
      ]
     },
     "execution_count": 106,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "basefold_encode_rec([1, 2], k0=1, depth=1, c=2, T=[[X0, X1]])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 107,
   "id": "515a054a-4d5d-4382-9be1-e8e767b6c444",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      ">>> basefold_encode: m=[1, 2], k0=1, d=1, blowup_factor=3, T=[[X0, X1, X2]]\n",
      ">>> basefold_encode: code= [1, 1, 1, 2, 2, 2]\n",
      ">>> basefold_encode: chunk_size= 3\n",
      ">>> basefold_encode: chunk_num= 2\n",
      ">>> basefold_encode: table= [X0, X1, X2]\n",
      ">>> basefold_encode: left=[1, 1, 1], right=[2, 2, 2]\n",
      ">>> basefold_encode: i=0, c=0, j=0\n",
      ">>> basefold_encode: i=0, c=0, j=1\n",
      ">>> basefold_encode: i=0, c=0, j=2\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "[2*X0 + 1, 2*X1 + 1, 2*X2 + 1, -2*X0 + 1, -2*X1 + 1, -2*X2 + 1]"
      ]
     },
     "execution_count": 107,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "basefold_encode([1, 2], k0=1, depth=1, c=3, T=[[X0, X1, X2]], debug=True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 108,
   "id": "627d0534-b8a9-425b-b799-92ef3b38f256",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[4*X0*Y0 + 2*X0 + 3*Y0 + 1,\n",
       " 4*X1*Y1 + 2*X1 + 3*Y1 + 1,\n",
       " 4*X2*Y2 + 2*X2 + 3*Y2 + 1,\n",
       " -4*X0*Y3 - 2*X0 + 3*Y3 + 1,\n",
       " -4*X1*Y4 - 2*X1 + 3*Y4 + 1,\n",
       " -4*X2*Y5 - 2*X2 + 3*Y5 + 1,\n",
       " -4*X0*Y0 + 2*X0 - 3*Y0 + 1,\n",
       " -4*X1*Y1 + 2*X1 - 3*Y1 + 1,\n",
       " -4*X2*Y2 + 2*X2 - 3*Y2 + 1,\n",
       " 4*X0*Y3 - 2*X0 - 3*Y3 + 1,\n",
       " 4*X1*Y4 - 2*X1 - 3*Y4 + 1,\n",
       " 4*X2*Y5 - 2*X2 - 3*Y5 + 1]"
      ]
     },
     "execution_count": 108,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "basefold_encode([1,2,3,4], k0=1, depth=2, c=3, T=[[X0, X1, X2], [Y0, Y1, Y2, Y3, Y4, Y5]])"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "60933de8-c663-487e-bf19-8e4c63bac425",
   "metadata": {},
   "source": [
    "## Basefold IOPP\n",
    "\n",
    "$$\n",
    "B^{(monomial)} = (1, \\alpha_0)\\otimes (1, \\alpha_1) \\otimes \\cdots \\otimes (1, \\alpha_{k-1})\n",
    "$$\n",
    "\n",
    "$$\n",
    "B^{(multilinear)} = ((1-\\alpha_0), \\alpha_0)\\otimes ((1-\\alpha_1), \\alpha_1) \\otimes \\cdots \\otimes ((1-\\alpha_{k-1}), \\alpha_{k-1})\n",
    "$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 109,
   "id": "a36267f3-63ef-46b9-a734-09d591245376",
   "metadata": {},
   "outputs": [],
   "source": [
    "def basefold_fri_monomial_basis(vs, table, alpha, debug=False):\n",
    "    assert len(table) == len(vs)/2, \"len(table) is not double len(vs), len(table) = %d, len(vs) = %d\" % (len(table), len(vs))\n",
    "    n = len(vs)\n",
    "    half = n / 2\n",
    "    new_vs = []\n",
    "    left = vs[:half]\n",
    "    right = vs[half:]\n",
    "\n",
    "    for i in range(0, half):\n",
    "        if debug: print(\"(left[i] + right[i])/2=\", (left[i] + right[i])/2)\n",
    "        if debug: print(\"(left[i] + right[i])/2=\", (left[i] + right[i])/2)\n",
    "        new_vs.append((left[i] + right[i])/2 + (alpha) * (left[i] - right[i])/(2*table[i]))\n",
    "    return new_vs"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 110,
   "id": "a25d792e-97fc-4928-a679-c6d31e8087e2",
   "metadata": {},
   "outputs": [],
   "source": [
    "def basefold_fri_multilinear_basis(vs, table, c, debug=False):\n",
    "    assert len(table) == len(vs)/2, \"len(table) is not double len(vs), len(table) = %d, len(vs) = %d\" % (len(table), len(vs))\n",
    "    n = len(vs)\n",
    "    half = n / 2\n",
    "    new_vs = []\n",
    "    left = vs[:half]\n",
    "    right = vs[half:]\n",
    "\n",
    "    for i in range(0, half):\n",
    "        if debug: print(\"(left[i] + right[i])/2=\", (left[i] + right[i])/2)\n",
    "        if debug: print(\"(left[i] + right[i])/2=\", (left[i] + right[i])/2)\n",
    "        new_vs.append((1 - c) * (left[i] + right[i])/2 + (c) * (left[i] - right[i])/(2*table[i]))\n",
    "    return new_vs"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 111,
   "id": "72873034-d48b-4992-9f52-96d23e864626",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[4*X0*X4 + 3*X0 + 2*X4 + 1,\n",
       " 4*X1*X5 + 3*X1 + 2*X5 + 1,\n",
       " -4*X2*X4 + 3*X2 - 2*X4 + 1,\n",
       " -4*X3*X5 + 3*X3 - 2*X5 + 1,\n",
       " -4*X0*X4 - 3*X0 + 2*X4 + 1,\n",
       " -4*X1*X5 - 3*X1 + 2*X5 + 1,\n",
       " 4*X2*X4 - 3*X2 - 2*X4 + 1,\n",
       " 4*X3*X5 - 3*X3 - 2*X5 + 1]"
      ]
     },
     "execution_count": 111,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "pi_0 = basefold_encode([1, 2, 3, 4], k0=1, depth=2, c=2, T=[[X4, X5], [X0, X1, X2, X3]]); pi_0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 112,
   "id": "af4a5765-93a4-4d7a-808b-806eb5e096e4",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[2*X4*A0 + 2*X4 + 2*A0 + 1,\n",
       " 2*X5*A0 + 2*X5 + 2*A0 + 1,\n",
       " -2*X4*A0 - 2*X4 + 2*A0 + 1,\n",
       " -2*X5*A0 - 2*X5 + 2*A0 + 1]"
      ]
     },
     "execution_count": 112,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "pi_1 = basefold_fri_multilinear_basis(pi_0, [X0, X1, X2, X3], A0); pi_1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 113,
   "id": "30df885c-6117-42e3-9ebc-59cd711edf1e",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[2*A0 + A1 + 1, 2*A0 + A1 + 1]"
      ]
     },
     "execution_count": 113,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "pi_2 = basefold_fri_multilinear_basis(pi_1, [X4, X5], A1); pi_2"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "dd2b3006-afe0-471c-aed0-3729f6926464",
   "metadata": {},
   "source": [
    "## Basefold Evaluation Argument\n",
    "\n",
    "$$\n",
    "v = f(\\mathbf{z}) = \\sum_{\\mathbf{b}}f(\\mathbf{b})\\cdot \\tilde{eq}_{\\mathbf{z}}(\\mathbf{b})\n",
    "$$\n",
    "\n",
    "by sumcheck, the statement can be reduced to\n",
    "\n",
    "$$\n",
    "v' \\overset{?}{=} f(\\mathbf{r})\\cdot \\tilde{eq}_{\\mathbf{z}}(\\mathbf{r})\n",
    "$$\n",
    "\n",
    "and we can have the following statement, since the code is linear\n",
    "$$\n",
    "\\mathsf{encode}(v'/\\tilde{eq}_{\\mathbf{z}}(\\mathbf{r})) \\overset{?}{=} \\mathsf{encode}\\big(f(\\mathbf{r})\\big)\n",
    "$$\n",
    "\n",
    "Fortunately, the right hand side is exactly the result of FRI-folding, and the left hand side can be computed by verifier himself."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "62bffed0-da05-4e14-b7eb-04d556c4257d",
   "metadata": {},
   "source": [
    "### More features\n",
    "\n",
    "- Add RS code support for `G0`\n",
    "\n",
    "### TODO\n",
    "\n",
    "- Change Rnd into a transcript that absorbs messages and squeezes challenges.\n",
    "- Change `Proof` into a struct, dict or class\n",
    "- Add inputs validation\n",
    "- Add error messages for `assert`\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 114,
   "id": "ede70a9d-f57c-4966-811f-ff5f625c645c",
   "metadata": {},
   "outputs": [],
   "source": [
    "from mle2 import MLEPolynomial\n",
    "from merkle import MerkleTree\n",
    "\n",
    "def query_phase(transcript, first_tree: MerkleTree, first_oracle, trees: list, oracles: list, num_vars, num_verifier_queries, debug=False):\n",
    "    queries = [transcript.squeeze_byte_challenge() % num_vars for _ in range(num_verifier_queries)]\n",
    "\n",
    "    query_paths = []\n",
    "    # query paths\n",
    "    for q in queries:\n",
    "        num_vars_copy = num_vars\n",
    "        cur_path = []\n",
    "        indices = []\n",
    "        x0 = q\n",
    "        x1 = q - num_vars_copy / 2 if q >= num_vars_copy / 2 else q + num_vars_copy / 2\n",
    "        if x1 < x0:\n",
    "            x0, x1 = x1, x0\n",
    "        \n",
    "        cur_path.append((first_oracle[x0], first_oracle[x1]))\n",
    "        indices.append(x0)\n",
    "        q = x0\n",
    "        num_vars_copy >>= 1\n",
    "\n",
    "        for oracle in oracles:\n",
    "            x0 = q\n",
    "            x1 = q - num_vars_copy / 2 if q >= num_vars_copy / 2 else q + num_vars_copy / 2\n",
    "            if x1 < x0:\n",
    "                x0, x1 = x1, x0\n",
    "            \n",
    "            cur_path.append((oracle[x0], oracle[x1]))\n",
    "            if debug: print(\"x0:\", x0, \"x1:\", x1, \"num_vars:\", num_vars_copy)\n",
    "            if debug: print(\"oracle:\", oracle)\n",
    "            indices.append(x0)\n",
    "            q = x0\n",
    "            num_vars_copy >>= 1\n",
    "        \n",
    "        query_paths.append((cur_path, indices))\n",
    "\n",
    "    # merkle paths\n",
    "    merkle_paths = []\n",
    "    for _, indices in query_paths:\n",
    "        cur_query_paths = []\n",
    "        for i, idx in enumerate(indices):\n",
    "            if i == 0:\n",
    "                cur_query_paths.append(first_tree.get_authentication_path(idx))\n",
    "                if debug: print(\"mp:\", cur_query_paths[-1])\n",
    "                if debug: print(\"commit:\", first_tree.root)\n",
    "                if debug: print(\"idx:\", idx)\n",
    "            else:\n",
    "                cur_tree = trees[i - 1]\n",
    "                assert isinstance(cur_tree, MerkleTree)\n",
    "                cur_query_paths.append(cur_tree.get_authentication_path(idx))\n",
    "                if debug: print(\"mp:\", cur_query_paths[-1])\n",
    "                if debug: print(\"commit:\", first_tree.root)\n",
    "                if debug: print(\"idx:\", idx)\n",
    "        merkle_paths.append(cur_query_paths)\n",
    "\n",
    "    return query_paths, merkle_paths"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 115,
   "id": "09513333",
   "metadata": {},
   "outputs": [],
   "source": [
    "from unipolynomial import UniPolynomial\n",
    "\n",
    "# Define prove\n",
    "# f_code: Encode(f)\n",
    "# f_evals: evaluations of f\n",
    "# us: point\n",
    "# v: f(point) = v\n",
    "# k: number of variables, k = len(u)\n",
    "# T: random code table\n",
    "# blowup_factor: as named\n",
    "# transcript: as named\n",
    "\n",
    "def prove_basefold_evaluation_arg_multilinear_basis(f_code, f_evals, us, v, k, T, blowup_factor, commit, num_verifier_queries, transcript, debug=False):\n",
    "    # TODO: check if the length of f is a power of 2\n",
    "    \n",
    "    n = len(f_evals)\n",
    "    half = n >> 1\n",
    "    assert len(T) == k, \"wrong table size, k={}, len(T)={}\".format(k, len(T))\n",
    "    f_code_copy = f_code[:]\n",
    "    f = f_evals[:]\n",
    "    eq = MLEPolynomial.eqs_over_hypercube(us)\n",
    "    \n",
    "    challenge_vec = []\n",
    "    sumcheck_sum = v\n",
    "    h_poly_vec = []\n",
    "    f_code_vec = []\n",
    "    f_code_trees = []\n",
    "    for i in range(k):\n",
    "        if debug: print(\"sumcheck round {}\".format(i))\n",
    "        f_low = f[:half]\n",
    "        f_high = f[half:]\n",
    "        eq_low = eq[:half]\n",
    "        eq_high = eq[half:]\n",
    "        \n",
    "        # print(\"low={}, high={}\".format(low, high))\n",
    "\n",
    "        h_eval_at_0 = sum([f_low[j] * eq_low[j] for j in range(half)])\n",
    "        h_eval_at_1 = sum([f_high[j] * eq_high[j] for j in range(half)])\n",
    "        h_eval_at_2 = sum([ (2 * f_high[j] - f_low[j]) * (2 * eq_high[j] - eq_low[j]) for j in range(half)])\n",
    "        h_poly_vec.append([h_eval_at_0, h_eval_at_1, h_eval_at_2])\n",
    "        \n",
    "        if debug: print(\"> sumcheck: h=[{},{},{}]\".format(h_eval_at_0, h_eval_at_1, h_eval_at_2))\n",
    "        if debug: print(\"> sumcheck: {} ?= {}\".format(h_eval_at_0 + h_eval_at_1, sumcheck_sum))\n",
    "        \n",
    "        assert h_eval_at_0 + h_eval_at_1 == sumcheck_sum, \"{} + {} != {}\" % (h_eval_at_0, h_eval_at_1, sumcheck_sum)\n",
    "\n",
    "        # Receive a random number from the verifier\n",
    "        alpha = A0 * transcript.squeeze_byte_challenge()\n",
    "        \n",
    "        challenge_vec.append(alpha)\n",
    "\n",
    "        # fold(low, high, alpha)\n",
    "        f = [(1 - alpha) * f_low[i] + alpha * f_high[i] for i in range(half)]\n",
    "        eq = [(1 - alpha) * eq_low[i] + alpha * eq_high[i] for i in range(half)]\n",
    "        if debug: print(\"> sumcheck: f_folded = {}\".format(f))\n",
    "        if debug: print(\"> sumcheck: eq_folded = {}\".format(eq))\n",
    "\n",
    "        # compute the new sum = h(alpha)\n",
    "        sumcheck_sum = UniPolynomial.uni_eval_from_evals([h_eval_at_0, h_eval_at_1, h_eval_at_2], alpha, [Fp(0),Fp(1),Fp(2)])\n",
    "        if debug: print(\"> sumcheck: sumcheck_sum = {}\".format(sumcheck_sum))\n",
    "\n",
    "        if debug: print(\"fri round {}\".format(i))\n",
    "\n",
    "        # # Basefold fri\n",
    "        f_code = basefold_fri_multilinear_basis(f_code, T[k-i-1], alpha, debug=debug)\n",
    "        if debug: print(\"> fri: f_code_folded=\", f_code)\n",
    "        f_code_vec.append(f_code)\n",
    "        f_code_trees.append(MerkleTree(f_code))\n",
    "\n",
    "        # DEBUG: consistency check (invariant)\n",
    "        # Enc(fold(message)) = fold(Enc(message)) \n",
    "        debug_f_folded_code = basefold_encode(m=f, k0=1, depth=k-i-1, c=blowup_factor, G0=rs_encode, T=T[:k-i-1], debug=debug)\n",
    "        if debug: print(\"> fri: enc({})={}\".format(f, debug_f_folded_code))\n",
    "        assert f_code == debug_f_folded_code, \"Enc(fold(message)) != fold(Enc(message))\"\n",
    "\n",
    "        transcript.write_field_elements([h_eval_at_0, h_eval_at_1, h_eval_at_2])\n",
    "        transcript.write_field_elements(f_code)\n",
    "        \n",
    "        half = half >> 1\n",
    "\n",
    "    # DEBUG:\n",
    "    f_eval_at_random = sumcheck_sum/eq[0]\n",
    "    assert rs_encode([f_eval_at_random], k0=1, c=blowup_factor) == f_code, \"❌: Encode(f(rs)) != f_code_0\"\n",
    "    if debug: print(\"end: f_code={}, sum={}, sum/eq={}\".format(f_code, sumcheck_sum, sumcheck_sum/eq[0]))\n",
    "    if debug: print(\"🙈: fold(f_code) == encode(fold(f_eq)/fold(eq(us)))\")\n",
    "\n",
    "    query_paths, merkle_paths = query_phase(transcript, commit, f_code_copy, f_code_trees, f_code_vec, len(f_code_copy), num_verifier_queries, debug)\n",
    "\n",
    "    # return (h_poly_vec, challenge_vec, f_code_vec)\n",
    "    return {\n",
    "        'h_poly_vec': h_poly_vec,\n",
    "        'f_code_vec': f_code_vec,\n",
    "        'challenge_vec': challenge_vec,\n",
    "        'f_code_trees': f_code_trees,\n",
    "        'query_paths': query_paths,\n",
    "        'merkle_paths': merkle_paths\n",
    "    }"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 116,
   "id": "c0a21f2f",
   "metadata": {},
   "outputs": [],
   "source": [
    "from merkle import verify_decommitment\n",
    "from transcript import Transcript\n",
    "\n",
    "def verify_queries(commit, proof, k, num_vars, num_verifier_queries, T, debug=False):\n",
    "    transcript = Transcript()\n",
    "    transcript.write_field_elements(commit.root)\n",
    "\n",
    "    fold_challenges = []\n",
    "    for i in range(k):\n",
    "        fold_challenges.append(A0 * transcript.squeeze_byte_challenge())\n",
    "        transcript.write_field_elements(proof['h_poly_vec'][i])\n",
    "        transcript.write_field_elements(proof['f_code_vec'][i])\n",
    "\n",
    "    queries = [transcript.squeeze_byte_challenge() % num_vars for _ in range(num_verifier_queries)]\n",
    "    # query loop\n",
    "    for q, (cur_path, _), mps in zip(queries, proof['query_paths'], proof['merkle_paths']):\n",
    "        if debug: print(\"cur_path:\", cur_path)\n",
    "        num_vars_copy = num_vars\n",
    "        # fold loop\n",
    "        for i, mp in enumerate(mps):\n",
    "            x0 = q\n",
    "            x1 = q - num_vars_copy / 2 if q >= num_vars_copy / 2 else q + num_vars_copy / 2\n",
    "            if x1 < x0:\n",
    "                x0, x1 = x1, x0\n",
    "                \n",
    "            code_left, code_right = cur_path[i][0], cur_path[i][1]\n",
    "\n",
    "            if i != len(mps) - 1:\n",
    "                table = T[k-i-1]\n",
    "                if debug: print(\"table:\", table)\n",
    "                if debug: print(\"x0:\", x0)\n",
    "                if debug: print(\"x1:\", x1)\n",
    "                f_code_folded = cur_path[i + 1][0 if x0 < num_vars_copy / 4 else 1]\n",
    "                alpha = fold_challenges[i]\n",
    "                if debug: print(\"f_code_folded:\", f_code_folded)\n",
    "                if debug: print(\"expected:\", ((1 - alpha) * (code_left + code_right)/2 + (alpha) * (code_left - code_right)/(2*table[x0])))\n",
    "                if debug: print(\"code_left:\", code_left)\n",
    "                if debug: print(\"code_right:\", code_right)\n",
    "                if debug: print(\"alpha:\", alpha)\n",
    "                assert f_code_folded == ((1 - alpha) * (code_left + code_right)/2 + (alpha) * (code_left - code_right)/(2*table[x0])), \"failed to check multilinear base fri\"\n",
    "\n",
    "            if i == 0:\n",
    "                if debug: print(\"mp:\", mp)\n",
    "                if debug: print(\"commit:\", commit.root)\n",
    "                if debug: print(\"idx:\", x0)\n",
    "                assert verify_decommitment(x0, code_left, mp, commit.root)\n",
    "            else:\n",
    "                if debug: print(\"mp:\", mp)\n",
    "                if debug: print(\"commit:\", proof['f_code_trees'][i - 1].root)\n",
    "                if debug: print(\"idx:\", x0)\n",
    "                assert verify_decommitment(x0, code_left, mp, proof['f_code_trees'][i - 1].root)\n",
    "\n",
    "            num_vars_copy >>= 1\n",
    "            q = x0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 117,
   "id": "0b293993-66d5-4d7b-9d41-4f3ac88b73f4",
   "metadata": {},
   "outputs": [],
   "source": [
    "def verify_basefold_evaluation_arg_multilinear_basis(f_code, commit, proof, us, v, d, k, T, blowup_factor, num_verifier_queries, Rng, debug=False):\n",
    "    # TODO: check if the length of f is a power of 2\n",
    "    \n",
    "    N = len(f_code)\n",
    "    assert k == len(us), \"k != len(us), k = %d, len(us) = %d\" % (k, len(us))\n",
    "    n = 1 << k\n",
    "    assert N == n * blowup_factor, \"N != n * blowup_factor, N = %d, n = %d, blowup_factor = %d\" % (N, n, blowup_factor)\n",
    "    \n",
    "    h_poly_vec = proof['h_poly_vec']\n",
    "    challenge_vec = proof['challenge_vec']\n",
    "    f_code_vec = proof['f_code_vec']\n",
    "    sumcheck_sum = v\n",
    "    half = n >> 1\n",
    "    f_last_code = f_code\n",
    "    eq_evals = MLEPolynomial.eqs_over_hypercube(us)\n",
    "    \n",
    "    for i in range(k):\n",
    "        if debug: print(\"sumcheck round {}\".format(i))\n",
    "        h_evals = h_poly_vec[i]\n",
    "        assert d+1 == len(h_evals), \"d+1 != len(h_evals), d+1 = %d, len(h_evals) = %d\" % (d+1, len(h_evals))\n",
    "\n",
    "        assert sumcheck_sum == h_evals[0] + h_evals[1], \"sumcheck_sum != h_evals[0] + h_evals[1], sumcheck_sum = %d, h_evals[0] = %d, h_evals[1] = %d\" % (sumcheck_sum, h_evals[0], h_evals[1])\n",
    "        # print(\"low={}, high={}\".format(low, high))\n",
    "\n",
    "        alpha = challenge_vec[i]\n",
    "\n",
    "        sumcheck_sum = UniPolynomial.uni_eval_from_evals(h_evals, alpha, [Fp(0),Fp(1),Fp(2)])\n",
    "\n",
    "        eq_low = eq_evals[:half]\n",
    "        eq_high = eq_evals[half:]\n",
    "        if debug: print(\"eq_low={}, eq_high={}\".format(eq_low, eq_high))\n",
    "        eq_evals = [(1-alpha) * eq_low[i] + alpha * eq_high[i] for i in range(half)]\n",
    "\n",
    "        if debug: print(\"fri round {}\".format(i))\n",
    "\n",
    "        table = T[k-i-1]\n",
    "        f_code_folded = f_code_vec[i]\n",
    "        assert len(f_code_folded) == half * blowup_factor, \"len(f_code_folded) != half * blowup_factor, len(f_code_folded) = %d, half = %d, blowup_factor = %d\" % (len(f_code_folded), half, blowup_factor)\n",
    "        code_left = f_last_code[:half*blowup_factor]\n",
    "        code_right = f_last_code[half*blowup_factor:]\n",
    "        if debug: print(\"code_left={}\".format(code_left))\n",
    "        if debug: print(\"code_right={}\".format(code_right))\n",
    "        if debug: print(\"f_code_folded={}\".format(f_code_folded))\n",
    "        if debug: print(\"alpha={}\".format(alpha))\n",
    "        if debug: print(\"table={}\".format(table))\n",
    "        for j in range(half*blowup_factor):\n",
    "            assert f_code_folded[j] == ((1 - alpha) * (code_left[j] + code_right[j])/2 + (alpha) * (code_left[j] - code_right[j])/(2*table[j])), \"failed to check multilinear base fri\"\n",
    "        f_last_code = f_code_folded\n",
    "        half = half >> 1\n",
    "\n",
    "    verify_queries(commit, proof, k, N, num_verifier_queries, T, debug)\n",
    "        \n",
    "    # check the final code\n",
    "    final_code = f_code_vec[i]\n",
    "    assert len(final_code) == blowup_factor, \"len(final_code) != blowup_factor, len(final_code) = %d, blowup_factor = %d\" % (len(final_code), blowup_factor)\n",
    "    for i in range(len(final_code)):\n",
    "        assert final_code[0] == final_code[i], \"final_code is not a repetition code\"\n",
    "    # check f(alpha_vec)\n",
    "    f_eval_at_random = sumcheck_sum/eq_evals[0]\n",
    "    if debug: print(\"f_eval_at_random={}\".format(f_eval_at_random))\n",
    "    if debug: print(\"rs_encode([f_eval_at_random], k0=1, c=blowup_factor)=\", rs_encode([f_eval_at_random], k0=1, c=blowup_factor))\n",
    "    assert rs_encode([f_eval_at_random], k0=1, c=blowup_factor) == f_code_folded, \"❌: Encode(f(rs)) != f_code_0\"\n",
    "    print(\"✅: Verified! fold({}) == encode(fold(f_eq)/fold(eq(us)))\".format(f_code))\n",
    "\n",
    "    return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 118,
   "id": "2c3eab78-ecb4-4331-9648-e3d83543353b",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[Field([4*X0*X4 + 3*X0 + 2*X4 + 1]),\n",
       " Field([4*X1*X5 + 3*X1 + 2*X5 + 1]),\n",
       " Field([-4*X2*X4 + 3*X2 - 2*X4 + 1]),\n",
       " Field([-4*X3*X5 + 3*X3 - 2*X5 + 1]),\n",
       " Field([-4*X0*X4 - 3*X0 + 2*X4 + 1]),\n",
       " Field([-4*X1*X5 - 3*X1 + 2*X5 + 1]),\n",
       " Field([4*X2*X4 - 3*X2 - 2*X4 + 1]),\n",
       " Field([4*X3*X5 - 3*X3 - 2*X5 + 1])]"
      ]
     },
     "execution_count": 118,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "ff = [Fp(1),Fp(2),Fp(3),Fp(4)]\n",
    "ff_code = basefold_encode(m=ff, k0=1, depth=2, c=2, G0=rs_encode, T=[[X4, X5], [X0, X1, X2, X3]]); ff_code"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 119,
   "id": "2ac9afba",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'d7732ef5605e991b2909cb0219410cb35b49f23df6d5c909ecfe2ebacf64ce6d'"
      ]
     },
     "execution_count": 119,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "commit = MerkleTree(ff_code)\n",
    "commit.root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 120,
   "id": "a21869d9-b03a-4ab0-a8ff-f5d73199ede0",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'h_poly_vec': [[Field([181]), Field([24]), Field([88])],\n",
       "  [Field([72*A0^2 + 10*A0 + 6]),\n",
       "   Field([85*A0^2 + 73*A0 - 18]),\n",
       "   Field([-95*A0^2 - 21*A0 - 72])]],\n",
       " 'f_code_vec': [[Field([-10*X4*A0 + 2*X4 - 10*A0 + 1]),\n",
       "   Field([-10*X5*A0 + 2*X5 - 10*A0 + 1]),\n",
       "   Field([10*X4*A0 - 2*X4 - 10*A0 + 1]),\n",
       "   Field([10*X5*A0 - 2*X5 - 10*A0 + 1])],\n",
       "  [Field([89*A0 + 1]), Field([89*A0 + 1])]],\n",
       " 'challenge_vec': [-5*A0, -94*A0],\n",
       " 'f_code_trees': [<merkle.MerkleTree object at 0x12cf61410>,\n",
       "  <merkle.MerkleTree object at 0x12cf6a890>],\n",
       " 'query_paths': [([(Field([4*X1*X5 + 3*X1 + 2*X5 + 1]),\n",
       "     Field([-4*X1*X5 - 3*X1 + 2*X5 + 1])),\n",
       "    (Field([-10*X5*A0 + 2*X5 - 10*A0 + 1]),\n",
       "     Field([10*X5*A0 - 2*X5 - 10*A0 + 1])),\n",
       "    (Field([89*A0 + 1]), Field([89*A0 + 1]))],\n",
       "   [1, 1, 0]),\n",
       "  ([(Field([-4*X3*X5 + 3*X3 - 2*X5 + 1]), Field([4*X3*X5 - 3*X3 - 2*X5 + 1])),\n",
       "    (Field([-10*X5*A0 + 2*X5 - 10*A0 + 1]),\n",
       "     Field([10*X5*A0 - 2*X5 - 10*A0 + 1])),\n",
       "    (Field([89*A0 + 1]), Field([89*A0 + 1]))],\n",
       "   [3, 1, 0]),\n",
       "  ([(Field([4*X0*X4 + 3*X0 + 2*X4 + 1]), Field([-4*X0*X4 - 3*X0 + 2*X4 + 1])),\n",
       "    (Field([-10*X4*A0 + 2*X4 - 10*A0 + 1]),\n",
       "     Field([10*X4*A0 - 2*X4 - 10*A0 + 1])),\n",
       "    (Field([89*A0 + 1]), Field([89*A0 + 1]))],\n",
       "   [0, 0, 0]),\n",
       "  ([(Field([4*X1*X5 + 3*X1 + 2*X5 + 1]), Field([-4*X1*X5 - 3*X1 + 2*X5 + 1])),\n",
       "    (Field([-10*X5*A0 + 2*X5 - 10*A0 + 1]),\n",
       "     Field([10*X5*A0 - 2*X5 - 10*A0 + 1])),\n",
       "    (Field([89*A0 + 1]), Field([89*A0 + 1]))],\n",
       "   [1, 1, 0])],\n",
       " 'merkle_paths': [[['1f2132771bb6da50636e47e8a6008fc2ecca5b006b83f6b0b2f22faa35601254',\n",
       "    'ed60f9862d1b626084c46913fe5068a5ed159fca9c6f4169e5857fb16d1ef86a',\n",
       "    '8113ad78ca72393d3f9f7f40d3a9cd60d98a1c21d0ecef4986ce6cd3b676dfe1'],\n",
       "   ['605df0f4ee68f5753a015f057133f1a4bbe84b0e5b72b866f51bcded9e707d5e',\n",
       "    'f9e67d2a71295f49db627833b5c83e8a20b0b162f002f3529be018da2282a675'],\n",
       "   ['238b8b8cd29a360bfa2bbb1efc136051583ba54573f3211604b8ae084bdaf881']],\n",
       "  [['1f2132771bb6da50636e47e8a6008fc2ecca5b006b83f6b0b2f22faa35601254',\n",
       "    'a3908fce4dba2b186c03c9ae0eab74461227e58dde51b8d1260334f857a0fb69',\n",
       "    'fcdfea9754326f6c9612fc56cfd28f5857d77a9d8449d728fa4f88d901ff1d6c'],\n",
       "   ['605df0f4ee68f5753a015f057133f1a4bbe84b0e5b72b866f51bcded9e707d5e',\n",
       "    'f9e67d2a71295f49db627833b5c83e8a20b0b162f002f3529be018da2282a675'],\n",
       "   ['238b8b8cd29a360bfa2bbb1efc136051583ba54573f3211604b8ae084bdaf881']],\n",
       "  [['1f2132771bb6da50636e47e8a6008fc2ecca5b006b83f6b0b2f22faa35601254',\n",
       "    'ed60f9862d1b626084c46913fe5068a5ed159fca9c6f4169e5857fb16d1ef86a',\n",
       "    'c59d46ec6760e72acf97cfd72202736a9b427ff36a166623842396796992a2f8'],\n",
       "   ['605df0f4ee68f5753a015f057133f1a4bbe84b0e5b72b866f51bcded9e707d5e',\n",
       "    'cb8d4563d9bdb45da5800eb1d3a8b62e1711c0811b5e74714534fe4bccdee12b'],\n",
       "   ['238b8b8cd29a360bfa2bbb1efc136051583ba54573f3211604b8ae084bdaf881']],\n",
       "  [['1f2132771bb6da50636e47e8a6008fc2ecca5b006b83f6b0b2f22faa35601254',\n",
       "    'ed60f9862d1b626084c46913fe5068a5ed159fca9c6f4169e5857fb16d1ef86a',\n",
       "    '8113ad78ca72393d3f9f7f40d3a9cd60d98a1c21d0ecef4986ce6cd3b676dfe1'],\n",
       "   ['605df0f4ee68f5753a015f057133f1a4bbe84b0e5b72b866f51bcded9e707d5e',\n",
       "    'f9e67d2a71295f49db627833b5c83e8a20b0b162f002f3529be018da2282a675'],\n",
       "   ['238b8b8cd29a360bfa2bbb1efc136051583ba54573f3211604b8ae084bdaf881']]]}"
      ]
     },
     "execution_count": 120,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "from transcript import Transcript\n",
    "\n",
    "transcript = Transcript()\n",
    "transcript.write_field_elements(commit.root)\n",
    "proof = prove_basefold_evaluation_arg_multilinear_basis(ff_code, ff, [3,4], 12, 2, [[X4, X5], [X0, X1, X2, X3]], 2, commit, 4, transcript); proof"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 121,
   "id": "1eea29fe-96cc-4596-82fc-649f9fc9ad61",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "✅: Verified! fold([Field([4*X0*X4 + 3*X0 + 2*X4 + 1]), Field([4*X1*X5 + 3*X1 + 2*X5 + 1]), Field([-4*X2*X4 + 3*X2 - 2*X4 + 1]), Field([-4*X3*X5 + 3*X3 - 2*X5 + 1]), Field([-4*X0*X4 - 3*X0 + 2*X4 + 1]), Field([-4*X1*X5 - 3*X1 + 2*X5 + 1]), Field([4*X2*X4 - 3*X2 - 2*X4 + 1]), Field([4*X3*X5 - 3*X3 - 2*X5 + 1])]) == encode(fold(f_eq)/fold(eq(us)))\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 121,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# verify_basefold_evaluation_arg_multilinear_basis(f_code, arg, us, v, d, k, T, blowup_factor, Rng):\n",
    "\n",
    "verify_basefold_evaluation_arg_multilinear_basis(ff_code, commit, proof, us=[3,4], v=12, d=2, k=2, T=[[X4, X5], [X0, X1, X2, X3]], blowup_factor=2, num_verifier_queries=4, Rng=[A1, A0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 122,
   "id": "35033a05",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{'add': 174, 'sub': 97, 'mul': 202, 'div': 70}\n",
      "{'add': 0, 'sub': 0, 'mul': 0, 'div': 0}\n"
     ]
    }
   ],
   "source": [
    "from field import Field\n",
    "\n",
    "print(Field.get_operation_count())\n",
    "Field.reset_operation_count()\n",
    "print(Field.get_operation_count())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 123,
   "id": "315fc5a3",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Finite Field of size 193\n",
      "0\n",
      "1\n",
      "5\n"
     ]
    }
   ],
   "source": [
    "print(Fp.Fp)\n",
    "print(Fp.zero())\n",
    "print(Fp.one())\n",
    "print(Fp.primitive_element())"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "SageMath 9.8",
   "language": "sage",
   "name": "SageMath-9.8"
  },
  "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.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}