Created
September 26, 2023 08:01
-
-
Save Pratyush/37d0adf060a5b9bd09fa0168c6b3a4f7 to your computer and use it in GitHub Desktop.
Marlin PIOP.ipynb
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| { | |
| "nbformat": 4, | |
| "nbformat_minor": 0, | |
| "metadata": { | |
| "colab": { | |
| "provenance": [], | |
| "authorship_tag": "ABX9TyPsWGTWzjKeH4bBnjmrxZJY", | |
| "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/37d0adf060a5b9bd09fa0168c6b3a4f7/marlin-piop.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>" | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "source": [ | |
| "# Marlin PIOP Tutorial\n", | |
| "\n", | |
| "Let's implement the non-holographic variant of the Marlin PIOP using the `ark_algebra_py` package. We'll start by installing it:" | |
| ], | |
| "metadata": { | |
| "id": "o0Agw_tIZM1-" | |
| } | |
| }, | |
| { | |
| "cell_type": "code", | |
| "execution_count": null, | |
| "metadata": { | |
| "id": "E1QX_uMzYjgs" | |
| }, | |
| "outputs": [], | |
| "source": [ | |
| "!pip install --upgrade ark_algebra_py" | |
| ] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "source": [ | |
| "## Overview of key classes\n", | |
| "\n", | |
| "Now that it's installed, we can play around with it a little. The key classes that we'll be concerned with are `Scalar`, `Domain`, and `Polynomial`. We'll explain some common operations you can perform on these classes below, starting with `Scalar`.\n", | |
| "\n", | |
| "`Scalar` represents an element of a finite field $\\mathbb{F}$. For this tutorial, it doesn't really matter which field we use, but if you're curious, it's the scalar field of the BLS12-381 curve." | |
| ], | |
| "metadata": { | |
| "id": "stJY0MzoZvte" | |
| } | |
| }, | |
| { | |
| "cell_type": "code", | |
| "source": [ | |
| "from ark_algebra_py.ark_algebra_py import Scalar, Polynomial, Domain\n", | |
| "\n", | |
| "a = Scalar(4);\n", | |
| "b = Scalar(2);\n", | |
| "\n", | |
| "print(\"a + b = \", a + b); # we can add...\n", | |
| "print(\"a - b = \", a - b); # ... subtract ...\n", | |
| "print(\"-a = \", -a); # ... negate ...\n", | |
| "print(\"a * b = \", a * b); # ... multiply ...\n", | |
| "print(\"a * a^-1 = \", a * a.inverse()) # ... invert ...\n", | |
| "print(\"random field element = \", Scalar.rand())\n", | |
| "print(\"a ** 3 = \", a ** 3) # ... and exponentiate `Scalar`s." | |
| ], | |
| "metadata": { | |
| "id": "SSjq3ojpZ666" | |
| }, | |
| "execution_count": null, | |
| "outputs": [] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "source": [ | |
| "`Polynomial`s are univariate polynomials over $\\mathbb{F}$." | |
| ], | |
| "metadata": { | |
| "id": "3NF3CJRZbcwE" | |
| } | |
| }, | |
| { | |
| "cell_type": "code", | |
| "source": [ | |
| "# p(X) = 5 + 10 * X + 20 * X**2\n", | |
| "p = Polynomial([Scalar(5), Scalar(10), Scalar(20)])\n", | |
| "q = Polynomial([Scalar(9), Scalar(14)])\n", | |
| "\n", | |
| "print(\"p(5) = \", p.evaluate(Scalar(10))); # we can evaluate...\n", | |
| "print(\"p + q = \", p + q); # ... add ...\n", | |
| "print(\"p - q = \", p + q); # ... subtract ...\n", | |
| "print(\"p * q = \", p * q); # ... multiply ...\n", | |
| "print(\"p / q = \", p / q); # ... divide to get quotient and remainder ...\n", | |
| "print(\"p.degree() = \", p.degree()); # ... and get the degree of polynomials" | |
| ], | |
| "metadata": { | |
| "id": "jxHzVBG2a4vD" | |
| }, | |
| "execution_count": null, | |
| "outputs": [] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "source": [ | |
| "`Domain`s are succinct descriptions of subsets of $\\mathbb{F}$ that support efficient interpolation algorithms, and whose vanishing polynomial can be evaluated succinctly." | |
| ], | |
| "metadata": { | |
| "id": "0l6E8Gv3bgwV" | |
| } | |
| }, | |
| { | |
| "cell_type": "code", | |
| "source": [ | |
| "H = Domain(8); # create a subset of size 8\n", | |
| "\n", | |
| "# Let's try to interpolate a polynomial from the list `a`:\n", | |
| "a = [Scalar(1), Scalar(2), Scalar(3)]\n", | |
| "a_hat = H.interpolate(a);\n", | |
| "\n", | |
| "# Let's check that a_hat takes the correct values over `domain`:\n", | |
| "assert(a_hat.evaluate(H.element(0)) == a[0])\n", | |
| "assert(a_hat.evaluate(H.element(1)) == a[1])\n", | |
| "assert(a_hat.evaluate(H.element(2)) == a[2])\n", | |
| "assert(a_hat.evaluate(H.element(3)) == Scalar(0))\n", | |
| "print(a_hat.divide_by_vanishing_poly(H))\n", | |
| "\n", | |
| "assert(H.evaluate_vanishing_polynomial(H.element(5)) == Scalar(0))\n", | |
| "# We can get the vanishing polynomial\n", | |
| "assert(H.vanishing_polynomial().evaluate(H.element(5)) == Scalar(0))\n", | |
| "print(H.elements())\n", | |
| "assert(H.element(1).square() == H.element(2))" | |
| ], | |
| "metadata": { | |
| "id": "2O4QJ_1pdNdD" | |
| }, | |
| "execution_count": null, | |
| "outputs": [] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "source": [ | |
| "## PIOP for Zerocheck\n", | |
| "\n", | |
| "We'll start simple by trying to construct a PIOP for Zerocheck. Recall that in the Zerocheck problem, the prover is trying to convince the verifier that the evaluations of a polynomial $p$ at all points in a domain $H$ are all $0$.\n", | |
| "\n", | |
| "Let's start by writing out the prover and verifier code:" | |
| ], | |
| "metadata": { | |
| "id": "MSIcYuaQeI0x" | |
| } | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "source": [ | |
| "" | |
| ], | |
| "metadata": { | |
| "id": "St6HTspnIiYS" | |
| } | |
| }, | |
| { | |
| "cell_type": "code", | |
| "source": [ | |
| "def zero_check_prover(p, domain):\n", | |
| " # Your code here\n", | |
| " return { \"p\": p } # return a dictionary of polynomial oracles\n", | |
| "\n", | |
| "\n", | |
| "def zero_check_verifier_query(domain):\n", | |
| " # Your code here\n", | |
| " return { \"p\": r } # Return a dictionary of (oracle_name, query)\n", | |
| "\n", | |
| "def zero_check_decision(domain, queries, evaluations):\n", | |
| " r = queries[\"p\"]\n", | |
| " # Your code here\n", | |
| " return False\n", | |
| "\n", | |
| "# Helper function for later on.\n", | |
| "def eval_at_queries(oracles, queries):\n", | |
| " evaluations = {}\n", | |
| " for (oracle_name, point) in queries.items():\n", | |
| " evaluations[oracle_name] = oracles[oracle_name].evaluate(point)\n", | |
| " return evaluations" | |
| ], | |
| "metadata": { | |
| "id": "mxRo6jzIdY6B" | |
| }, | |
| "execution_count": null, | |
| "outputs": [] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "source": [ | |
| "We want these functions to satisfy completeness...:" | |
| ], | |
| "metadata": { | |
| "id": "KomICJMBgzrV" | |
| } | |
| }, | |
| { | |
| "cell_type": "code", | |
| "source": [ | |
| "# Completeness:\n", | |
| "\n", | |
| "zero = Scalar(0)\n", | |
| "# We'll use a multiple of the vanishing polynomial p(X) = 2 * X^8 - 2\n", | |
| "p = Polynomial([Scalar(-2), zero, zero, zero, zero, zero, zero, zero, Scalar(2)])\n", | |
| "\n", | |
| "oracles = zero_check_prover(p, Domain(8))\n", | |
| "queries = zero_check_verifier_query(H)\n", | |
| "evaluations = eval_at_queries(oracles, queries)\n", | |
| "assert(zero_check_decision(H, queries, evaluations))" | |
| ], | |
| "metadata": { | |
| "id": "eaq8i-eJfxzH" | |
| }, | |
| "execution_count": null, | |
| "outputs": [] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "source": [ | |
| "... and soundness:" | |
| ], | |
| "metadata": { | |
| "id": "PitADn-An6FL" | |
| } | |
| }, | |
| { | |
| "cell_type": "code", | |
| "source": [ | |
| "# Soundness:\n", | |
| "\n", | |
| "zero = Scalar(0)\n", | |
| "# We'll use a polynomial that is *almost* the same as before p(X) = 2 * X^8 - 3\n", | |
| "p = Polynomial([Scalar(-3), zero, zero, zero, zero, zero, zero, zero, Scalar(2)])\n", | |
| "\n", | |
| "oracles = zero_check_prover(p, Domain(8))\n", | |
| "queries = zero_check_verifier_query(H)\n", | |
| "evaluations = eval_at_queries(oracles, queries)\n", | |
| "assert(zero_check_decision(H, queries, evaluations) == False)" | |
| ], | |
| "metadata": { | |
| "id": "2L0q62QrjKEM" | |
| }, | |
| "execution_count": null, | |
| "outputs": [] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "source": [ | |
| "## PIOP for Hadamard Products\n", | |
| "\n", | |
| "With our PIOP for Zerocheck in hand, we're now ready to define our PIOP for Hadamard Product checks. Below is a reminder of what it looks like." | |
| ], | |
| "metadata": { | |
| "id": "bEGgBymYu1xB" | |
| } | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "source": [ | |
| "" | |
| ], | |
| "metadata": { | |
| "id": "lFWyqmdGoYMv" | |
| } | |
| }, | |
| { | |
| "cell_type": "code", | |
| "source": [ | |
| "def hadamard_prover(z_a, z_b, z_c, domain):\n", | |
| " # Your code here\n", | |
| " return {} # return a dictionary of polynomial oracles\n", | |
| "\n", | |
| "def hadamard_verifier_query(domain):\n", | |
| " return {} # Return a dictionary of (oracle_name, query)\n", | |
| "\n", | |
| "def hadamard_decision(domain, queries, evaluations):\n", | |
| " return False" | |
| ], | |
| "metadata": { | |
| "id": "_r7kHKRIrTzM" | |
| }, | |
| "execution_count": null, | |
| "outputs": [] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "source": [ | |
| "Once again, we'll test completeness and soundness with respect to the following R1CS instance:\n", | |
| "\n", | |
| "$$\n", | |
| "A := \\begin{pmatrix}\n", | |
| "0 & 1 & 0 \\\\\n", | |
| "0 & 2 & 0 \\\\\n", | |
| "0 & 3 & 0 \\\\\n", | |
| "\\end{pmatrix};\\;\n", | |
| "B := \\begin{pmatrix}\n", | |
| "0 & 0 & 1 \\\\\n", | |
| "0 & 0 & \\frac12 \\\\\n", | |
| "0 & 0 & \\frac13 \\\\\n", | |
| "\\end{pmatrix};\\;\n", | |
| "C := \\begin{pmatrix}\n", | |
| "1 & 0 & 0 \\\\\n", | |
| "1 & 0 & 0 \\\\\n", | |
| "1 & 0 & 0 \\\\\n", | |
| "\\end{pmatrix};\\;\n", | |
| "$$\n", | |
| "\n", | |
| "$$\n", | |
| "x := 3\n", | |
| "$$" | |
| ], | |
| "metadata": { | |
| "id": "BWFLw3lbvozq" | |
| } | |
| }, | |
| { | |
| "cell_type": "code", | |
| "source": [ | |
| "import numpy as np\n", | |
| "one = Scalar(1)\n", | |
| "two = one.double()\n", | |
| "three = one + two\n", | |
| "half = two.inverse()\n", | |
| "third = three.inverse()\n", | |
| "A = np.array([[zero, one, zero], [zero, two, zero], [zero, three, zero]])\n", | |
| "B = np.array([[zero, zero, one], [zero, zero, half], [zero, zero, third]])\n", | |
| "C = np.array([[one, zero, zero], [one, zero, zero], [one, zero, zero]])\n", | |
| "x = np.array([Scalar(3)])" | |
| ], | |
| "metadata": { | |
| "id": "RxR9PZM0rgfO" | |
| }, | |
| "execution_count": null, | |
| "outputs": [] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "source": [ | |
| "# Completeness:\n", | |
| "w = np.array([three.square(), third])\n", | |
| "z = np.hstack([x, w]).transpose()\n", | |
| "z_a = A @ z\n", | |
| "z_b = B @ z\n", | |
| "z_c = C @ z\n", | |
| "assert(np.multiply(z_a, z_b) == z_c).all()\n", | |
| "\n", | |
| "\n", | |
| "oracles = hadamard_prover(z_a, z_b, z_c, H)\n", | |
| "queries = hadamard_verifier_query(H)\n", | |
| "evaluations = eval_at_queries(oracles, queries)\n", | |
| "assert(hadamard_decision(H, queries, evaluations))" | |
| ], | |
| "metadata": { | |
| "id": "GQxcaJ5WwDhb" | |
| }, | |
| "execution_count": null, | |
| "outputs": [] | |
| }, | |
| { | |
| "cell_type": "code", | |
| "source": [ | |
| "# Soundness:\n", | |
| "w = np.array([three.square(), two])\n", | |
| "z = np.hstack([x, w]).transpose()\n", | |
| "z_a = A @ z\n", | |
| "z_b = B @ z\n", | |
| "z_c = C @ z\n", | |
| "assert(np.multiply(z_a, z_b) != z_c).any()\n", | |
| "\n", | |
| "\n", | |
| "oracles = hadamard_prover(z_a, z_b, z_c, H)\n", | |
| "queries = hadamard_verifier_query(H)\n", | |
| "evaluations = eval_at_queries(oracles, queries)\n", | |
| "assert(hadamard_decision(H, queries, evaluations) == False)" | |
| ], | |
| "metadata": { | |
| "id": "_xwOSN9z12XT" | |
| }, | |
| "execution_count": null, | |
| "outputs": [] | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "source": [ | |
| "## PIOP for Lincheck\n", | |
| "\n", | |
| "Let's now design the PIOP for lincheck, based on the univariate sumcheck lemma. Recall that the latter is a statement of the form\n", | |
| "$$\\sum_{h \\in H} p(h) = \\sigma \\iff \\exists g, q \\in \\mathbb{F}[X] \\text{ s.t. } p(X) = X \\cdot g(X) + \\frac{\\sigma}{|H|} + q(X) v_H(X).$$" | |
| ], | |
| "metadata": { | |
| "id": "sttDX6u82AIs" | |
| } | |
| }, | |
| { | |
| "cell_type": "markdown", | |
| "source": [ |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment