part2.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Copyright 2019 StarkWare Industries Ltd.<br> Licensed under the Apache License, Version 2.0 (the \"License\"). You may not use this file except in compliance with the License. You may obtain a copy of the License at https://www.starkware.co/open-source-license/ <br> Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an \"AS IS\" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language governing permissions and limitations under the License.*"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Part 2: Constraints\n",
    "\n",
    "- [Video Lecture (youtube)](https://www.youtube.com/watch?v=fg3mFPXEYQY)\n",
    "- [Slides (PDF)](https://starkware.co/wp-content/uploads/2021/12/STARK101-Part2.pdf)\n",
    "\n",
    "In this part, we are going to create a set of constraints over the trace `a`. <br>The constraints will be expressions in the trace's cells that are polynomials (rather than [rational functions](https://en.wikipedia.org/wiki/Rational_function)) if and only if the trace represents a valid computation of the FibonacciSq. <br>\n",
    "<br>\n",
    "We will get there in three steps:\n",
    "1. Start by specifying the constraints we care about (the **FibonacciSq constraints**).\n",
    "2. Translate the FibonacciSq constraints into **polynomial constraints**.\n",
    "3. Translate those into **rational functions** that represent polynomials if and only if the original constraints hold. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Step 1 - FibonacciSq Constraints\n",
    "For `a` to be a correct trace of a FibonacciSq sequence that proves our claim:\n",
    "1. The first element has to be 1, namely $a[0] = 1$.\n",
    "2. The last element has to be 2338775057, namely $a[1022] = 2338775057$.\n",
    "3. The FibonacciSq rule must apply, that is - for every $i<1021$, $a[i+2]=a[i+1]^2+a[i]^2$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Step 2 - Polynomial Constraints\n",
    "Recall that `f` is a polynomial over the trace domain, that evaluates exactly to `a` over $G \\setminus \\{g^{1023}\\}$ where $G=\\{g^i : 0\\leq i\\leq 1023\\}$ is the \"small\" group generated by $g$.<br>\n",
    "\n",
    "We now rewrite the above three constraints in a form of polynomial constraints over `f`:\n",
    "1. $a[0] = 1$ is translated to the polynomial $f(x) - 1$, which evalutes to 0 for $x = g^0$ (note that $g^0$ is $1$). <br>\n",
    "2. $a[1022] = 2338775057$ is translated to the polynomial $f(x) - 2338775057$, which evalutes to 0 for $x = g^{1022}$. <br>\n",
    "3. $a[i+2]=a[i+1]^2+a[i]^2$ for every $i<1021$ is translated to the polynomial $f(g^2 \\cdot x) - (f(g \\cdot x))^2 - (f(x))^2$, which evaluates to 0 for $x \\in G \\backslash \\{g^{1021}, g^{1022}, g^{1023}\\}$. <br><br>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Hands on\n",
    "First, since this is a separate notebook from Part 1, let's run the following piece of code to have all the variables here with their correct values. Note that it may take up to 30 seconds, since it reruns the polynomial interpolation."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 141,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Success!\n"
     ]
    }
   ],
   "source": [
    ":dep stark101-rs = { path = \"stark101\" }\n",
    ":dep sha256 = \"1.1.2\"\n",
    "use stark101_rs::{field::FieldElement, channel::Channel, polynomial::{Polynomial, x}};\n",
    "use stark101_rs::parts::part1();\n",
    "\n",
    "let (a, g, G, h, H, eval_domain, f, f_eval, f_merkle, channel) = part1();\n",
    "println!(\"Success!\");"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "You will obtain each of the three constraints as a quotient of two polynomials, making sure the remainder is the zero polynomial. \n",
    "<br><br>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Step 3 - Rational Functions (That are in Fact Polynomials)\n",
    "\n",
    "Each of the constraints above is represented by a polynomial $u(x)$ that supposedly evaluates to $0$ on certain elements of the group $G$. That is, for some $x_0, \\ldots, x_k \\in G$, we claim that\n",
    "\n",
    "$$u(x_0) = \\ldots = u(x_k) = 0$$\n",
    "\n",
    "(note that for the first two constaints, $k=0$ because they only refer to one point and for the third $k=1021$).\n",
    "\n",
    "This is equivalent to saying that $u(x)$ is divisible, as a polynomial, by all of $\\{(x-x_i)\\}_{i=0}^k$, or, equivalently, by\n",
    "\n",
    "$$\\prod_{i=0}^k (x-x_i)$$\n",
    "\n",
    "Therefore, each of the three constraints above can be written as a rational function of the form:\n",
    "\n",
    "$$\\frac{u(x)}{\\prod_{i=0}^k (x-x_i)}$$\n",
    "\n",
    "for the corresponding $u(x)$ and $\\{x_i\\}_{i=0}^k$. In this step we will construct these three rational functions and show that they are indeed polynomials."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## The First Constraint:\n",
    "\n",
    "In the first constraint, $f(x) - 1$ and $\\{x_i\\} = \\{1\\}$.\n",
    "\n",
    "We will now construct the **polynomial** $p_0(x)=\\frac{f(x) - 1}{x - 1}$, making sure that $f(x) - 1$ is indeed divisible by $(x-1)$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "// First constraint. Construct numer0 and denom0.\n",
    "let numer0: Polynomial = todo!();\n",
    "let denom0: Polynomial = todo!();"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 142,
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "let numer0: Polynomial = f.clone() - FieldElement::one();\n",
    "let denom0: Polynomial = x() - FieldElement::one();"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Convince yourself that $f(x) - 1$ vanishes at $x=1$ by making sure that evaluating this polynomial at $1$ yields $0$:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "todo!(\"You should evaluate f(x) - 1 at x = 1\");"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The fact that $f(x) - 1$ has a root at $1$ implies that it is divisible by $(x - 1)$.\n",
    "Run the following cell to convince yourself that the remainder of `numer0` modulo `denom0` is $0$, and therefore division indeed yields a polynomial:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Polynomial([])"
      ]
     },
     "execution_count": 36,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "numer0.clone() % denom0.clone()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Run the following cell to construct `p0`, the polynomial representing the first constraint, by dividing `numer0` by `denom0`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 143,
   "metadata": {},
   "outputs": [],
   "source": [
    "let p0: Polynomial = numer0 / denom0;"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Run test:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Success!\n"
     ]
    }
   ],
   "source": [
    "assert_eq!(p0(2718), 2509888982);\n",
    "println!(\"Success!\");"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## The Second Constraint\n",
    "\n",
    "Construct the polynomial `p1` representing the  second constraint, $p_1(x)= \\frac{f(x) - 2338775057}{x - g^{1022}}$, similarly: <br>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "// Second constraint.\n",
    "let p1: Polynomial = todo!();"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 144,
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "let numer1: Polynomial = f.clone() - FieldElement::new(2338775057);\n",
    "let denom1: Polynomial = x() - g.pow(1022usize);\n",
    "let p1: Polynomial = numer1 / denom1.clone();"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Run test:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 83,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Success!\n"
     ]
    }
   ],
   "source": [
    "assert_eq!(p1(5772), 232961446);\n",
    "println!(\"Success!\");"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## The Third Constraint - Succinctness\n",
    "\n",
    "The last constraint's rational function is slightly more complicated: <br>\n",
    "\n",
    "\n",
    "$$p_2(x) = \\frac{f(g^2 \\cdot x) - (f(g \\cdot x))^2 - (f(x))^2}{\\prod\\limits_{i=0}^{1020} (x-g^i)}$$\n",
    "\n",
    "whose denominator can be rewritten, so that the entire expression is easier to compute:<br>\n",
    "\n",
    "$$\\frac{f(g^2 \\cdot x) - (f(g \\cdot x))^2 - (f(x))^2}{\\frac{x^{1024} - 1}{(x-g^{1021})(x-g^{1022})(x-g^{1023})}}$$ <br>\n",
    "\n",
    "This follows from the equality\n",
    "\n",
    "$$\\prod\\limits_{i=0}^{1023} (x-g^i) = x^{1024} - 1$$\n",
    "\n",
    "Convince yourself of this equality using the function `prod` that takes a list and computes its product:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "thread '<unnamed>' panicked at 'not yet implemented', src/lib.rs:134:28\n",
      "stack backtrace:\n",
      "   0: _rust_begin_unwind\n",
      "   1: core::panicking::panic_fmt\n",
      "   2: core::panicking::panic\n",
      "   3: <core::panic::unwind_safe::AssertUnwindSafe<F> as core::ops::function::FnOnce<()>>::call_once\n",
      "   4: _run_user_code_14\n",
      "   5: evcxr::runtime::Runtime::run_loop\n",
      "   6: evcxr::runtime::runtime_hook\n",
      "   7: evcxr_jupyter::main\n",
      "note: Some details are omitted, run with `RUST_BACKTRACE=full` for a verbose backtrace.\n"
     ]
    }
   ],
   "source": [
    "// Construct a list `lst` of the linear terms (x-g**i):\n",
    "let lst: Vec<Polynomial> = todo!();\n",
    "// Compute the product of `lst` and see that it is indeed the succinct polynomial x**1024 - 1\n",
    "Polynomial::prod(&lst);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "tags": []
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Polynomial([FieldElement(3221225472), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(0), FieldElement(1)])"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "let lst: Vec<Polynomial> = (0..1024).into_iter().map(|i| x() - g.pow(i)).collect();\n",
    "Polynomial::prod(&lst)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For more information, see our blog post titled [Arithmetization II](https://medium.com/starkware/arithmetization-ii-403c3b3f4355).\n",
    "\n",
    "Let's pause for a moment, and look at a simple example on how polynomials are composed. After that we will generate the third constraint."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Composing Polynomials (a detour)\n",
    "\n",
    "Create the two polynomials $q(x) = 2x^2 +1$, $r(x) = x - 3$:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [],
   "source": [
    "let q: Polynomial = x().pow(2)*2usize + 1;\n",
    "let r = x() - 3usize;"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Composing $q$ on $r$ yields a new polynomial:<br>\n",
    "$q(r(x)) = 2(x-3)^2 + 1 = 2x^2-12x+19$\n",
    "<br>\n",
    "Run the following cell to create a third polynomial `cmp` by composing `q` on `r` and convince yourself that `cmp` is indeed the composition of `q` and `r`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Polynomial([FieldElement(19), FieldElement(3221225461), FieldElement(2)])"
      ]
     },
     "execution_count": 23,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "let cmp = q(r);\n",
    "cmp"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Back to Polynomial Constraints\n",
    "Construct the third constraint `p2` in a similar manner to the construction of `p0` and `p1`, using polynomial composition. Along the way, verify that $g^{1020}$ is a root of the **numerator** while $g^{1021}$ is not."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "let p2: Polynomial = todo!();"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 145,
   "metadata": {
    "tags": []
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Numerator at g^1020 is FieldElement(0)\n",
      "Numerator at g^1021 is FieldElement(230576507)\n"
     ]
    }
   ],
   "source": [
    "let numer_1: Polynomial = f(x() * g.pow(2));\n",
    "let numer_2: Polynomial = f(x() * g).pow(2) * FieldElement::new((-1 + FieldElement::k_modulus() as i128) as usize);\n",
    "let numer_3: Polynomial = f.pow(2) * FieldElement::new((-1 + FieldElement::k_modulus() as i128) as usize);\n",
    "let numer2: Polynomial = numer_1 + numer_2 + numer_3;\n",
    "println!(\"Numerator at g^1020 is {:?}\", numer2.clone()(g.pow(1020)));\n",
    "println!(\"Numerator at g^1021 is {:?}\", numer2(g.pow(1021usize)));\n",
    "let denom2 = (x().pow(1024usize) - 1) / ((x() - g.pow(1021)) * (x() - g.pow(1022)) * (x() - g.pow(1023)));\n",
    "\n",
    "let p2: Polynomial = numer2 / denom2;"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Run test:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Success!\n"
     ]
    }
   ],
   "source": [
    "let p2_degree = p2.degree();\n",
    "assert_eq!(p2.degree(), 1023, \"The degree of the third constraint is {p2_degree} when it should be 1023.\");\n",
    "assert_eq!(p2(31415), 2090051528);\n",
    "println!(\"Success!\");"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Run the following cell to observe the degrees of the constraint polynomials `p0`, `p1` and `p2`, all less than $1024$. This will be important in the next part."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 50,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "deg p0 = 1021\n",
      "deg p1 = 1021\n",
      "deg p2 = 1023\n"
     ]
    }
   ],
   "source": [
    "println!(\"deg p0 = {}\", p0.degree());\n",
    "println!(\"deg p1 = {}\", p1.degree());\n",
    "println!(\"deg p2 = {}\", p2.degree());"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Step 4 - Composition Polynomial\n",
    "Recall that we're translating a problem of checking the validity of three polynomial constraints to checking that each of the rational functions $p_0, p_1, p_2$ are polynomials. <br>\n",
    "\n",
    "Our protocol uses an algorithm called [FRI](https://eccc.weizmann.ac.il/report/2017/134/) to do so, which will be discussed in the next part. <br>\n",
    "In order for the proof to be succinct (short), we prefer to work with just one rational function instead of three. For that, we take a random linear combination of $p_0, p_1, p_2$ called the **compostion polynomial** (CP for short):\n",
    "\n",
    "$$CP(x) = \\alpha_0 \\cdot p_0(x) + \\alpha_1 \\cdot p_1(x) + \\alpha_2 \\cdot  p_2(x)$$ <br>\n",
    "\n",
    "where $\\alpha_0, \\alpha_1, \\alpha_2 $ are random field elements obtained from the verifier, or in our case - from the channel.\n",
    "\n",
    "Proving that (the rational function) $CP$ is a polynomial guarantess, with high probability, that each of $p_0$, $p_1$, $p_2$ are themselves polynomials.\n",
    "\n",
    "In the next part, you will generate a proof for an equivalent fact. But first, let's create `CP` using `Channel.receive_random_field_element` to obtain $\\alpha_i$: <br> \n",
    "   "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "// Note that alpha0, alpha1, alpha2 have to be drawn from the channel in this order.\n",
    "fn get_CP(p1: Polynomial, p2: Polynomial, p3: Polynomial, channel: Channel) -> Polynomial {\n",
    "    todo!();\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 146,
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "fn get_CP(p0: Polynomial, p1: Polynomial, p2: Polynomial, channel: &mut Channel) -> Polynomial {\n",
    "    let alpha0 = channel.receive_random_field_element();\n",
    "    let alpha1 = channel.receive_random_field_element();\n",
    "    let alpha2 = channel.receive_random_field_element();\n",
    "    (p0 * alpha0) + (p1 * alpha1) + (p2 * alpha2)\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Run test:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 138,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Success!\n"
     ]
    }
   ],
   "source": [
    "let mut test_channel: Channel = Channel::new();\n",
    "let cp_test = get_CP(p0, p1, p2, &mut test_channel);\n",
    "let cp_test_degree = cp_test.degree();\n",
    "assert_eq!(cp_test.degree(), 1023, \"The degree of cp is {cp_test_degree} when it should be 1023.\");\n",
    "let expected = cp_test(2439804);\n",
    "assert_eq!(cp_test(2439804), 838767343, \"cp(2439804) = {expected:?}, when it should be 838767343\");\n",
    "println!(\"Success!\");"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Commit on the Composition Polynomial\n",
    "Lastly, we evaluate $cp$ over the evaluation domain (`eval_domain`), build a Merkle tree on top of that and send its root over the channel. This is similar to commiting on the LDE trace, as we did at the end of part 1."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "// Fix this. CP_eval is the evaluation of CP on all the points in domain. For a hint - look at \"Evaluate on a Coset\" on part 1.\n",
    "fn cp_eval(p0: Polynomial, p1: Polynomial, p2: Polynomial, domain: Vec<FieldElement>, channel: &mut Channel) {\n",
    "    let cp = get_CP(p0, p1, p2, channel);\n",
    "    todo!();\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 147,
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "fn cp_eval(p0: Polynomial, p1: Polynomial, p2: Polynomial, domain: Vec<FieldElement>, channel: &mut Channel) -> Vec<FieldElement> {\n",
    "    let cp = get_CP(p0, p1, p2, channel);\n",
    "    domain.into_iter().map(|d| cp(d)).collect()\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Construct a Merkle Tree over the evaluation and send its root over the channel."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "let channel = Channel::new();\n",
    "let cp_merkle = MerkleTree::new(todo!()); // Fix this line\n",
    "channel.send(cp_merkle.root);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 148,
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "use stark101_rs::merkle_tree::MerkleTree;\n",
    "let mut channel = Channel::new();\n",
    "let cp_merkle: MerkleTree = MerkleTree::new(cp_eval(p0, p1, p2, eval_domain, &mut channel));\n",
    "channel.send(cp_merkle.root());"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Test your code:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 150,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Success!\n"
     ]
    }
   ],
   "source": [
    "assert_eq!(cp_merkle.root(), \"26db4de93f69af9591eac0bf224a26f5ffd99d07a325b82ee34381069a205a53\", \"Merkle tree root is wrong.\");\n",
    "println!(\"Success!\");"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Rust",
   "language": "rust",
   "name": "rust"
  },
  "language_info": {
   "codemirror_mode": "rust",
   "file_extension": ".rs",
   "mimetype": "text/rust",
   "name": "Rust",
   "pygment_lexer": "rust",
   "version": ""
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}