KZG Polynomial Commitment Scheme - Solved.ipynb

kzg-polynomial-commitment-scheme-solved.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "provenance": [],
      "authorship_tag": "ABX9TyPrjrv3rr6QJANGC3i/uE/S",
      "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/gist/Pratyush/919a79ece229b1c9ef304857cf2f42b9/kzg-polynomial-commitment-scheme-solved.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "# KZG Polynomial Commitment\n",
        "\n",
        "$\\newcommand{\\ck}{\\mathsf{ck}}$\n",
        "$\\newcommand{\\vk}{\\mathsf{rk}}$\n",
        "$\\newcommand{\\cm}{\\mathsf{cm}}$\n",
        "$\\newcommand{\\Setup}{\\mathsf{Setup}}$\n",
        "$\\newcommand{\\Commit}{\\mathsf{Commit}}$\n",
        "$\\newcommand{\\Open}{\\mathsf{Open}}$\n",
        "$\\newcommand{\\Verify}{\\mathsf{Verify}}$\n",
        "There are four algorithms in the KZG Polynomial Commitment Scheme:\n",
        "\n",
        "* $\\Setup(1^\\lambda, d) \\to (\\ck, \\vk)$.\n",
        "* $\\Commit(\\ck, p) \\to \\cm$.\n",
        "* $\\Open(\\ck, p, z) \\to (\\pi, v)$.\n",
        "* $\\Verify(\\vk, \\cm, z, v, \\pi) \\to b \\in \\{0, 1\\}$\n",
        "\n",
        "Let's construct these one-by-one."
      ],
      "metadata": {
        "id": "uEiot_oceA5l"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "## Setup and introduction to groups\n",
        "\n",
        "We'll begin by installing `ark_algebra_py` as before, and will then go over the bilinear group APIs"
      ],
      "metadata": {
        "id": "u96I3gJ5h-sJ"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "!pip install --upgrade ark_algebra_py"
      ],
      "metadata": {
        "id": "ASq6EaEmh48a"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "### Group APIs\n",
        "\n",
        "We'll use *additive* notation for our group operations. So, instead of writing $g^x \\cdot g^y$, we'll write $x \\cdot G + y \\cdot G$."
      ],
      "metadata": {
        "id": "dhqsf2tFiTxu"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "from ark_algebra_py.ark_algebra_py import G1, G2, Pairing, GT, Scalar, Polynomial\n",
        "\n",
        "G = G1();\n",
        "a = Scalar(4);\n",
        "b = Scalar(2);\n",
        "\n",
        "# We can multiply the generator by scalar field elements\n",
        "aG = a * G\n",
        "bG = b * G;\n",
        "\n",
        "print(\"a + b = \", aG + bG); # we can add...\n",
        "print(\"a - b = \", aG - G); # ... subtract ...\n",
        "print(\"a + -a = \", aG + -aG) # ... negate ...\n",
        "print(\"a.double() = \", aG.double()) # ... and double points."
      ],
      "metadata": {
        "id": "Fo5N4b1EiX9j"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "The same API works for $\\mathbb{G}_2$ elements as well, so we won't cover it here. Let's focus on pairings next."
      ],
      "metadata": {
        "id": "Ofw6qQoJkcxk"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "G = G1();\n",
        "a = Scalar(4);\n",
        "b = Scalar(2);\n",
        "\n",
        "H = G2(); # The generator of G2 is usually denoted as H.\n",
        "\n",
        "# We can multiply the generator by scalar field elements\n",
        "aG = a * G\n",
        "bH = b * H;\n",
        "\n",
        "assert(Pairing.pairing(aG, bH) == Pairing.pairing(G, H)**8)\n",
        "assert(Pairing.pairing(b * G, a * H) == Pairing.pairing(G, H)**8)"
      ],
      "metadata": {
        "id": "iXodqGpQk8nT"
      },
      "execution_count": 5,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "## KZG Setup\n",
        "\n",
        "Recall that the setup algorithm looks like the following:\n",
        "\n",
        "\n",
        "$\\Setup(1^\\lambda, d) \\to (\\ck, \\vk)$:\n",
        "\n",
        "1. Sample $\\tau \\gets \\mathbb{F}_p$.\n",
        "2. Set $\\ck := (G, \\tau G, \\dots, \\tau^d G)$.\n",
        "3. Set $\\vk := (G, H, \\tau H)$.\n",
        "4. Output $(\\ck, \\vk)$."
      ],
      "metadata": {
        "id": "pmDZan8QnJkx"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "def setup(degree):\n",
        "  tau = Scalar.rand()\n",
        "  ck = [tau**i * G1() for i in range(0, degree + 1)]\n",
        "  rk = (G1(), G2(), tau * G2())\n",
        "  return (ck, rk)"
      ],
      "metadata": {
        "id": "xB1FJZwRn1Hw"
      },
      "execution_count": 51,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "## KZG Commit\n",
        "\n",
        "Recall that the commit algorithm looks like the following:\n",
        "\n",
        "\n",
        "$\\Commit(\\ck, p) \\to \\cm$:\n",
        "\n",
        "1. Output $\\cm := \\sum_{i = 0}^d p_i \\tau^i G$.\n"
      ],
      "metadata": {
        "id": "xtqic8vaoTzh"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "def commit(ck, polynomial):\n",
        "  # hint: use `zip` function\n",
        "  # hint: `polynomial.coefficients()` will return a list of `polynomial`'s coefficients\n",
        "  cm = G1.identity()\n",
        "  for (p_i, G_i) in zip(polynomial.coefficients(), ck):\n",
        "    cm = cm + p_i * G_i;\n",
        "  return cm"
      ],
      "metadata": {
        "id": "kbD02qJtoQgF"
      },
      "execution_count": 52,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "Let's benchmark how long this takes for a moderate degree polynomial."
      ],
      "metadata": {
        "id": "xz9Ti1dusJLZ"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "(ck, rk) = setup(2**15)\n",
        "\n",
        "poly = Polynomial([Scalar(i) for i in range(0, 2**15 + 1)])\n",
        "print(poly.degree()) # Should be 2^15\n",
        "\n",
        "import time;\n",
        "start = time.perf_counter();\n",
        "cm = commit(ck, poly)\n",
        "end = time.perf_counter();\n",
        "print(end - start)"
      ],
      "metadata": {
        "id": "3yVFjKUosk6p"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "This seems kinda slow, no? Let's speed things up by using multiscalar multiplication via the `msm` method on $\\mathbb{G}_1$ elements."
      ],
      "metadata": {
        "id": "--wXU18VtJtQ"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "def commit_fast(ck, polynomial):\n",
        "  cm = G1.msm(ck, polynomial.coefficients())\n",
        "  return cm"
      ],
      "metadata": {
        "id": "4dDV_-EUs0om"
      },
      "execution_count": 54,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "Let's benchmark `commit_fast`."
      ],
      "metadata": {
        "id": "RgsnoUawt19s"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "start = time.perf_counter();\n",
        "cm = commit_fast(ck, poly)\n",
        "end = time.perf_counter();\n",
        "print(end - start)"
      ],
      "metadata": {
        "id": "jMBG4cdgt6E_"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "## KZG Open\n",
        "\n",
        "\n",
        "Recall that the opening algorithm looks like the following:\n",
        "\n",
        "\n",
        "$\\Open(\\ck, p, z) \\to (\\pi, v)$:\n",
        "\n",
        "1. Compute evaluation $v := p(z)$.\n",
        "2. Compute quotient $q(X) := \\frac{p(X) - v}{X - z}$.\n",
        "3. Compute proof $\\pi := \\Commit(\\ck, q)$.\n",
        "4. Output $(\\pi, v)$.\n"
      ],
      "metadata": {
        "id": "Dn3CD2V54z2B"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "def open(ck, polynomial, point):\n",
        "  # hint: `Polynomial.X()` construct the polynomial with just the `X` variable\n",
        "  # hint: `Polynomial.constant(c) constructs the constant polynomial\n",
        "  evaluation = polynomial.evaluate(point)\n",
        "  numerator = polynomial - Polynomial.constant(evaluation)\n",
        "  denom = Polynomial.X() - Polynomial.constant(point)\n",
        "  (q, r) = numerator/denom\n",
        "  assert(r == Polynomial.zero())\n",
        "  proof = commit_fast(ck, q)\n",
        "  return (proof, evaluation)"
      ],
      "metadata": {
        "id": "MV3MsHTf5hlG"
      },
      "execution_count": 56,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "## KZG Verify\n",
        "\n",
        "\n",
        "Recall that the verifier's algorithm looks like the following:\n",
        "\n",
        "\n",
        "$\\Verify(\\vk, \\cm, z, v, \\pi) \\to b \\in \\{0, 1\\}$:\n",
        "\n",
        "1. Check $e(\\cm - v G, H) \\overset?= e(\\pi, \\tau H - z H)$\n"
      ],
      "metadata": {
        "id": "JnsBj8cJ56LV"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "def verify(rk, cm, point, evaluation, proof):\n",
        "  (G, H, tauH) = rk\n",
        "  lhs = Pairing.pairing(cm - evaluation * G, H)\n",
        "  rhs = Pairing.pairing(proof, tauH - point * H)\n",
        "  return lhs == rhs"
      ],
      "metadata": {
        "id": "LIFoNaQS6avJ"
      },
      "execution_count": 57,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "## Completeness\n",
        "\n",
        "Now let's check that our algorithms work!"
      ],
      "metadata": {
        "id": "S5if6wwAAO_x"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "poly = Polynomial([Scalar(i) for i in range(0, 2**15 + 1)])\n",
        "cm = commit_fast(ck, poly)\n",
        "\n",
        "point = Scalar(100)\n",
        "\n",
        "(proof, evaluation) = open(ck, poly, point);\n",
        "assert(verify(rk, cm, point, evaluation, proof))"
      ],
      "metadata": {
        "id": "22JcJ_SpAWtx"
      },
      "execution_count": 58,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "## Soundness\n",
        "\n",
        "Now let's check that we reject incorrect claims!"
      ],
      "metadata": {
        "id": "1QUy2rt3AOyN"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "poly = Polynomial([Scalar(i) for i in range(0, 2**15 + 1)])\n",
        "cm = commit_fast(ck, poly)\n",
        "\n",
        "point = Scalar(100)\n",
        "\n",
        "(proof, _) = open(ck, poly, point);\n",
        "# We'll use an incorrect evaluation\n",
        "\n",
        "evaluation = Scalar(0)\n",
        "assert(verify(rk, cm, point, evaluation, proof) == False)"
      ],
      "metadata": {
        "id": "FmvQwjIoEKOw"
      },
      "execution_count": 59,
      "outputs": []
    }
  ]
}