Fiat_Shamir_and_Schwartz_Zippel_for_Faster_Emulated_pairings.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "provenance": [],
      "authorship_tag": "ABX9TyPTyHnwgTQuOlSda8sPTxQ5",
      "include_colab_link": true
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "view-in-github",
        "colab_type": "text"
      },
      "source": [
        "<a href=\"https://colab.research.google.com/github/shramee/Fiat-Shamir-and-Schwartz-Zippel-for-Faster-Emulated-pairings/blob/main/Fiat_Shamir_and_Schwartz_Zippel_for_Faster_Emulated_pairings.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "# Fiat-Shamir and Schwartz-Zippel for Faster Emulated Pairings"
      ],
      "metadata": {
        "id": "Pv3cUe9Dqoih"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "## 1. Introduction\n",
        "\n",
        "In the write-up [Faster Extension Field multiplications for Emulated Pairing Circuits](https://hackmd.io/@feltroidprime/B1eyHHXNT#fn3), Feltroid Prime discusses using Schwartz Zippel lemma and Fiat Shamir heuristics to optimize Field multiplications (Sections 1, 2 and 3).\n",
        "\n",
        "Starting with representing $𝔽_{p12}$ (and equivalently $𝔽_{p6}$) as direct extensions in section 1. Then representing multiplication operation as a polynomial in section 2 (equation 1). Finally using Fiat-Shamir and the Schwartz-Zippel lemma in the circuit to verify the computation.\n",
        "\n",
        "$\\begin{equation}\n",
        "{A(x)*B(x) = Q(x)*P(x) + R(x)}\n",
        "\\tag 1\n",
        "\\end{equation}$\n",
        "\n",
        "We will expand on this to apply it to larger computations. To start with we will try to adapt this for exponentiation (equation 2), with a goal of replacing entire final exponentiation.\n",
        "\n",
        "$\\begin{equation}\n",
        "{A(x)^n = Q(x)*P(x) + R(x)}\n",
        "\\tag 2\n",
        "\\end{equation}$"
      ],
      "metadata": {
        "id": "TUjrd4HH6R0z"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "## 2. Challenges\n",
        "\n",
        "### 2.1 Controling polynomial degree\n",
        "\n",
        "As we try to prove the larger computations, exponentiation of an $𝔽_{p12}$ by n, the degree of ${Q(x)}$ grows linearly with n.\n",
        "With a large degree comes increased calldata size and computation costs for hashing each coefficient for Fiat-Shamir. To make things easier we prefer an optimised version for larger computations (equation 3).\n",
        "\n",
        "${A(x)^n = R(x) \\mod P(x)} \\tag{3} $\n",
        "\n",
        "### 2.2 Computation of Fiat-Shamir, $z$\n",
        "\n",
        "Details regarding the computation of Fiat Shamir hueristic are presented here, [Section 3 of FEFMEPC](https://hackmd.io/@feltroidprime/B1eyHHXNT#3-Using-Fiat-Shamir-and-the-Schwartz-Zippel-lemma-in-circuit).\n",
        "To have our evaluations mod ${P(x)}$ we need to reduce our Fiat-Shamir hash, $z$, so that computation of ${P(z)} doesn't require reduction.\n",
        "\n",
        "With ${P(z)}$ for modulo, bitsize of `z` from Fiat Shamir needs to be reduced to $1/(deg P(x))$ of maximum bitsize available for a modulo operation.\n",
        "\n",
        "\n",
        "### 2.3. Size of coefficients\n",
        "\n",
        "The size of the coefficients in bits grows linearly with $n$, the exponent.\n",
        "This can be managed easily by modding, but here's the challenge.\n",
        "1. We need the coefficients modulo curve's prime field $p$. Otherwise the result is not usable for us in pairing.\n",
        "2. The evaluation requires a very specific modulus based on result of Fiat-Shamir otherwise the equation doesn't hold. Let's say we need it mod $z_{P} = P(z)$.\n",
        "\n",
        "So we have the prover provide the coefficients mod $z_{P}*p$\n",
        "This brings the size within twice the permissible integers in the circuit. For typical multiplication operation on a simulated field, this is usually required and available.\n",
        "\n"
      ],
      "metadata": {
        "id": "Hbwj8ZWh6YAJ"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "## 3. Prover and verifier\n",
        "\n",
        "This section expands upon the process described in [Section 3 of FEFMEPC](https://hackmd.io/@feltroidprime/B1eyHHXNT#3-Using-Fiat-Shamir-and-the-Schwartz-Zippel-lemma-in-circuit).\n",
        "\n",
        "### 3.1 Computing Fiat Shamir heuristic\n",
        "\n",
        "Prover and verifier both need to compute this, here's an outline of the process.\n",
        "\n",
        "${z = Hash(A_0, R_0, A_1, R_1, \\cdots, A_{n-1}, R_{n-1})} \\tag 4$\n",
        "\n",
        "1. Hash all coefficients of $A$ and $R$ mod $p$.\n",
        "2. Reduce the $z$ to make sure $z_{P} = P(z)$ doesn't require reduction. For example for BLS12-381, bit size of $z$ should be under $384 / 12 = 32$ bits. Or when using a $F_{P6}$ Torus $384 / 6 = 64$ bits. Assuming support for 384 bit integers.\n",
        "\n",
        "### 3.2 Prover steps\n",
        "\n",
        "* Prover computes the coefficients for $R$ mod $p$.\n",
        "* Prover computes $z$ (Section 3.1) and $z_{P} = P(z)$.\n",
        "* Prover re-computes coefficients for $R$ mod $z_{P}*p$\n",
        "\n",
        "### 3.2 Verifier steps\n",
        "\n",
        "* Receives the coefficients of polynomial $R$ for the computation. The coefficients are provided modulo $z_{P}*p$\n",
        "* Verifier receives the double-precision coefficients and reduces them separately with $z_{P}$ for evaluation and with $p$ to use in the circuit.\n",
        "* Verifier computes $z$ (Section 3.1) from coefficients reduced mod $p$. And also $z_{P} = P(z)$\n",
        "* Verifier evaluates $a_z = A(z) mod z_{P}$ and computes $a_z^n mod z_{P}$.\n",
        "* Now verifier computes $r_z = R(z)$ using coefficients of R mod $z_{P}$\n",
        "* Assert that $a_z = r_z$\n",
        "\n",
        "> *__According to the Schwartz-Zippel Lemma, if R is incorrect, the evaluated polynomials will differ with a very high probability.__*  \n",
        "&ndash; Stolen from https://hackmd.io/@feltroidprime/B1eyHHXNT\n",
        "\n"
      ],
      "metadata": {
        "id": "DGvf-pR96YeG"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "# 4. Working example\n",
        "\n",
        "WIP..."
      ],
      "metadata": {
        "id": "ifLNKG9GJFPN"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "## 4.1 Utilities"
      ],
      "metadata": {
        "id": "AUXgd2PkK3ZI"
      }
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "B3ohT_qlAwGd",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "dde01f96-5f73-4163-cb63-a1fac6297733"
      },
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "[2, 3, 4, 5, 6, 7] [8, 9, 10, 11, 12, 13] [16, 42, 79, 128, 190, 266, 265, 248, 214, 162, 91]\n"
          ]
        }
      ],
      "source": [
        "def multiply_poly(a, b, modulo = None):\n",
        "  \"\"\"Multiplies two polynomials represented as arrays of integer coefficients.\n",
        "\n",
        "  Args:\n",
        "    a: The first polynomial as an array of integer coefficients.\n",
        "    b: The second polynomial as an array of integer coefficients.\n",
        "    modulo: Mod for coefficients\n",
        "\n",
        "  Returns:\n",
        "    The product of the two polynomials as an array of integer coefficients.\n",
        "  \"\"\"\n",
        "\n",
        "  # Get the degree of the polynomials.\n",
        "  degree_a = len(a) - 1\n",
        "  degree_b = len(b) - 1\n",
        "\n",
        "  # Create a new array to store the product.\n",
        "  product = [0] * (degree_a + degree_b + 1)\n",
        "\n",
        "  # Multiply the polynomials.\n",
        "  for i in range(degree_a + 1):\n",
        "    for j in range(degree_b + 1):\n",
        "      product[i + j] += a[i] * b[j]\n",
        "      if (modulo):\n",
        "        product[i + j] = product[i + j] % modulo\n",
        "\n",
        "  # Return the product.\n",
        "  return product\n",
        "\n",
        "def evaluate_poly( poly, x, modulo = None ):\n",
        "  \"\"\"Evaluates a polynomial at x.\n",
        "\n",
        "  Args:\n",
        "    poly: The polynomial as an array of integer coefficients.\n",
        "    x: The second polynomial as an array of integer coefficients.\n",
        "    modulo: To eval mod\n",
        "\n",
        "  Returns:\n",
        "    The product of the two polynomials as an array of integer coefficients.\n",
        "  \"\"\"\n",
        "\n",
        "  eval = 0\n",
        "  # start at x^0\n",
        "  x_ = 1\n",
        "  for (i, a) in enumerate(poly):\n",
        "    eval += (a * x_)\n",
        "    if (modulo):\n",
        "          eval = eval % modulo\n",
        "    # x_ for next i, x^(i - 1)\n",
        "    x_ *= x\n",
        "\n",
        "  return eval"
      ]
    }
  ]
}