part1.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": {
    "tags": []
   },
   "source": [
    "# Part 1: Trace and Low-Degree Extension\n",
    "\n",
    "- [Video Lecture (youtube)](https://www.youtube.com/watch?v=Y0uJz9VL3Fo)\n",
    "- [Slides (PDF)](https://starkware.co/wp-content/uploads/2021/12/STARK101-Part1.pdf)\n",
    "\n",
    "Today we will develop a STARK prover for the FibonacciSq sequence over a finite field.\n",
    "The FibonacciSq sequence is defined by the recurrence relation $a_{n+2} = a_{n+1} ^2 + a_n ^2$.\n",
    "<br>By the end of the day, your code will produce a *STARK* proof attesting to the following statement: <br>**I know a field element $X\\in \\mathbb{F}$ such that the 1023rd element of the FibonacciSq sequence starting with $1, X$ is $2338775057$**.\n",
    "<br><br>\n",
    "## The Basics\n",
    "### FieldElement class\n",
    "We use our `FieldElement` struct to represent field elements.<br> You can construct values of type `FieldElement` from integers, and then add, multiply, divide, get inverse, and so on.\n",
    "The underlying field of this class is $\\mathbb{F}_{3221225473}$ ($3221225473 = 3 \\cdot 2^{30} + 1$), so all operations are done modulo 3221225473.\n",
    "<br><br>\n",
    "Try it by running the following cell (shift + enter):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 276,
   "metadata": {},
   "outputs": [],
   "source": [
    ":dep stark101-rs = { path = \"stark101\" }\n",
    ":dep sha256 = \"1.1.2\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 277,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The result is: FieldElement(9)\n"
     ]
    }
   ],
   "source": [
    "use stark101_rs::field::*;\n",
    "println!(\"The result is: {:?}\", FieldElement::new(3221225472) + FieldElement::new(10));"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## FibonacciSq Trace\n",
    "\n",
    "To start, let's construct a vector `a` of length 1023, whose first two elements will be FieldElement objects representing 1 and 3141592, respectively. The next 1021 elements will be the FibonacciSq sequence induced by these two elements. `a` is called the trace of FibonacciSq, or, when the context is clear, the trace. <br>\n",
    "Correct the code below to fill `a`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 278,
   "metadata": {},
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "thread '<unnamed>' panicked at 'not yet implemented: Put your code here', src/lib.rs:160:1\n",
      "stack backtrace:\n",
      "   0: _rust_begin_unwind\n",
      "   1: core::panicking::panic_fmt\n",
      "   2: <unknown>\n",
      "   3: <unknown>\n",
      "   4: evcxr::runtime::Runtime::run_loop\n",
      "   5: evcxr::runtime::runtime_hook\n",
      "   6: evcxr_jupyter::main\n",
      "note: Some details are omitted, run with `RUST_BACKTRACE=full` for a verbose backtrace.\n"
     ]
    }
   ],
   "source": [
    "let mut a = vec![FieldElement::new(1), FieldElement::new(3141592)];\n",
    "todo!(\"Put your code here\");"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution (click to the ... to unhide):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 279,
   "metadata": {
    "tags": []
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "()"
      ]
     },
     "execution_count": 279,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "let mut a = vec![FieldElement::new(1), FieldElement::new(3141592)];\n",
    "let mut n = 2usize;\n",
    "while a.len() < 1023 {\n",
    "    a.push(a[n-2] * a[n-2] + a[n-1] * a[n-1]);\n",
    "    n += 1;\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Test Your Code\n",
    "Run the next cell to test that you have filled `a` correctly.<br> Note that this is in fact a **verifier**, albeit very naive and non-succinct one, as it goes over the sequence, element by element, making sure it is correct."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 280,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Success!\n"
     ]
    }
   ],
   "source": [
    "assert_eq!(a.len(), 1023, \"The trace must consist of exactly 1023 elements.\");\n",
    "assert_eq!(a[0], FieldElement::new(1), \"The first element in the trace must be the unit element.\");\n",
    "for i in 2..1023 {\n",
    "    assert_eq!(a[i], a[i - 1] * a[i - 1] + a[i - 2] * a[i - 2], \"The FibonacciSq recursion rule does not apply for index {i}\");\n",
    "}\n",
    "assert_eq!(a[1022], FieldElement::new(2338775057), \"Wrong last element!\");\n",
    "println!(\"Success!\");"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Thinking of Polynomials\n",
    "We now want to think of the sequence as the evaluation of some, yet unknown, polynomial $f$ of degree 1022 (due to the Unisolvence Theorem).\n",
    "We will choose the domain to be some subgroup $G \\subseteq \\mathbb{F}^\\times$ of size 1024, for reasons that will become clear later.\n",
    "\n",
    "(Recall that $\\mathbb{F}^\\times$ denotes the multiplicative group of $\\mathbb{F}$, which we get from $\\mathbb{F}$ by omitting the zero element with the induced multiplication from the field. A subgroup of size 1024 exists because $\\mathbb{F}^\\times$ is a cyclic group of size $3\\cdot 2^{30}$, so it contains a subgroup of size $2^i$ for any $0 \\leq i \\leq 30$).\n",
    "### Find a Group of Size 1024\n",
    "If we find an element $g \\in \\mathbb{F}$ whose (multiplicative) order is 1024, then $g$ will generate such a group.\n",
    "The struct `FieldElement` provides a method `generator()` which returns an element that generates $\\mathbb{F}^\\times$ (whose order is $|\\mathbb{F}^\\times|$).\n",
    "1. Use it to obtain a generator $g$ for $G$.\n",
    "2. Create a vec called `G` with all the elements of $G$, such that $G[i] := g^i$.\n",
    "\n",
    "*Hint: When $k$ divides $|\\mathbb{F}^\\times|$, $g^k$ generates a group of size $\\frac {|\\mathbb{F}^\\times|}{k}$, and the n-th power of some `FieldElement` $x$ can be computed by calling `x ** n `.*\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 281,
   "metadata": {},
   "outputs": [],
   "source": [
    "// Change the following line so that g will generate a group of size 1024\n",
    "let g = FieldElement::generator();\n",
    "// Fill G with the elements of G such that G[i] := g ** i\n",
    "let G: Vec<FieldElement> = vec![]; "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 282,
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "let g = FieldElement::generator().pow(3 * 2usize.pow(20));\n",
    "let G: Vec<FieldElement> = (0..1024).into_iter().map(|i| g.pow(i)).collect();"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Run the next cell to test your code. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 283,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Success!\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "()"
      ]
     },
     "execution_count": 283,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "// Checks that g and G are correct.\n",
    "assert!(g.is_order(1024), \"The generator g is of wrong order.\");\n",
    "let mut b = FieldElement::one();\n",
    "for i in 0..1023 {\n",
    "    assert_eq!(b, G[i], \"The i-th place in G is not equal to the i-th power of g.\");\n",
    "    b = b * g;\n",
    "    let wrong_order = i + 1;\n",
    "    assert!(b != FieldElement::one(), \"g is of order {wrong_order}\");\n",
    "}    \n",
    "if b * g == FieldElement::one() {\n",
    "    println!(\"Success!\");\n",
    "} else {\n",
    "    println!(\"g is of order > 1024\");\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Polynomial class\n",
    "We provide you with a struct called `Polynomial`. The simplest way to construct a `Polynomial` is by using the function **x()**  which represents the formal variable $x$:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 284,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "FieldElement(9)\n"
     ]
    }
   ],
   "source": [
    "use stark101_rs::polynomial::*;\n",
    "// The polynomial 2x^2 + 1.\n",
    "let p: Polynomial = 2*x().pow(2) + 1;\n",
    "// Evaluate p at 2:\n",
    "println!(\"{:?}\", p(2));"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Interpolating a Polynomial\n",
    "Our `Polynomial` datatype provides a Lagrange interpolation method, whose arguments are:\n",
    "* x_values: x-values of G that the polynomial's values for them is known. &[FieldElement]\n",
    "* y_values: the corresponding y-values. &[FieldElement]\n",
    "\n",
    "It returns the unique `Polynomial` of degree < `x_values.len()` instance that evaluates to `y_values[i]` on `x_values[i]` for all i."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Suppose that `a` contains the values of some polynomial over `G` (except for `G[-1]`, since `a` is one element shorter).\n",
    "Use `Polynomial::interpolate()` to get `f` and get its value at `FieldElement::new(2)`. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 285,
   "metadata": {},
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "thread '<unnamed>' panicked at 'not yet implemented: Put your code here.', src/lib.rs:162:1\n",
      "stack backtrace:\n",
      "   0: _rust_begin_unwind\n",
      "   1: core::panicking::panic_fmt\n",
      "   2: <unknown>\n",
      "   3: <unknown>\n",
      "   4: evcxr::runtime::Runtime::run_loop\n",
      "   5: evcxr::runtime::runtime_hook\n",
      "   6: evcxr_jupyter::main\n",
      "note: Some details are omitted, run with `RUST_BACKTRACE=full` for a verbose backtrace.\n"
     ]
    }
   ],
   "source": [
    "// Fix the following so that you create a variable called v that will contain the value of f at FieldElement(2)\n",
    "// Note that Polynomial::interpolate may take up to a minute to run.\n",
    "todo!(\"Put your code here.\");"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 286,
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "let xs: Vec<FieldElement> = G.into_iter().rev().skip(1).rev().collect();\n",
    "let f: Polynomial = Polynomial::interpolate(&xs, &a);\n",
    "let v = f(2);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Run test:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 287,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Success!\n"
     ]
    }
   ],
   "source": [
    "assert_eq!(v, FieldElement::new(1302089273));\n",
    "println!(\"Success!\");"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Evaluating on a Larger Domain\n",
    "The trace, viewed as evaluations of a polynomial $f$ on $G$, can now be extended by evaluating $f$ over a larger domain, thereby creating a **Reed-Solomon error correction code**.\n",
    "\n",
    "### Cosets\n",
    "To that end, we must decide on a larger domain on which $f$ will be evaluated. \n",
    "We will work with a domain that is 8 times larger than $G$. <br>A natural choice for such a domain is to take some group $H$ of size 8192 (which exists because 8192 divides $|\\mathbb{F}^\\times|$), and shift it by the generator of $\\mathbb{F}^\\times$, thereby obtaining a [coset](https://en.wikipedia.org/wiki/Coset) of $H$.\n",
    "\n",
    "Create a vec called `H` of the elements of $H$, and multiply each of them by the generator of $\\mathbb{F}^\\times$ to obtain a vec called `eval_domain`. In other words, eval_domain = $\\{w\\cdot h^i | 0 \\leq i <8192  \\}$ for $h$ the generator of $H$ and $w$ the generator of $\\mathbb{F}^\\times$.\n",
    "\n",
    "Hint: You already know how to obtain $H$ - similarly to the way we got $G$ a few minutes ago.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 288,
   "metadata": {},
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "thread '<unnamed>' panicked at 'not yet implemented', src/lib.rs:160:23\n",
      "stack backtrace:\n",
      "   0: _rust_begin_unwind\n",
      "   1: core::panicking::panic_fmt\n",
      "   2: core::panicking::panic\n",
      "   3: <unknown>\n",
      "   4: <unknown>\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": [
    "// Fix the following, make sure that the the element of H are powers of its generator (let's call it h) in \n",
    "// order, that is - H[0] will be the unit (i.e 1), H[1] will be h (H's generator), H[2] will be H's\n",
    "// generator squared (h^2), etc.\n",
    "let h: FieldElement = todo!();\n",
    "let H: Vec<FieldElement> = todo!();\n",
    "let eval_domain: Vec<FieldElement> = todo!();"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 289,
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "let w = FieldElement::generator();\n",
    "let exp = (2usize.pow(30) * 3) / 8192;\n",
    "let h = w.pow(exp);\n",
    "let H: Vec<FieldElement> = (0..8192).into_iter().map(|i| h.pow(i)).collect(); \n",
    "let eval_domain: Vec<FieldElement> = H.into_iter().map(|x| w * x).collect();"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Run test:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 290,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Success!\n"
     ]
    }
   ],
   "source": [
    "let field_generator = FieldElement::generator();\n",
    "let w_inverse = w.inverse();\n",
    "\n",
    "for i in 0..8192 {\n",
    "    assert_eq!((w_inverse * eval_domain[1]).pow(i) * field_generator, eval_domain[i]);\n",
    "}\n",
    "println!(\"Success!\");"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Evaluate on a Coset\n",
    "Time to use `interpolate` and `eval` to evaluate over the coset. Note that it is implemented fairely naively in our Rust module, so interpolation may take some seconds.<br>\n",
    "Indeed - interpolating and evaluating the trace polynomial is one of the most computationally-intensive steps in the STARK protocol, even when using more efficient methods (e.g. FFT)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 291,
   "metadata": {},
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "thread '<unnamed>' panicked at 'not yet implemented', src/lib.rs:162:28\n",
      "stack backtrace:\n",
      "   0: _rust_begin_unwind\n",
      "   1: core::panicking::panic_fmt\n",
      "   2: core::panicking::panic\n",
      "   3: <unknown>\n",
      "   4: <unknown>\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": [
    "// Fill f_eval with the evaluations of f on eval_domain.\n",
    "let f_eval: FieldElement = todo!();"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 292,
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "let G_values: Vec<FieldElement> = (0..1024).into_iter().map(|i| g.pow(i)).collect();;\n",
    "let x_values: Vec<FieldElement> = G_values.into_iter().rev().skip(1).rev().collect();\n",
    "let interpolated_f: Polynomial = Polynomial::interpolate(&x_values, &a);\n",
    "let interpolated_f_eval: Vec<FieldElement> = eval_domain.into_iter().map(|d| interpolated_f.clone().eval(d)).collect();"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Run test:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 300,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Success!\n"
     ]
    }
   ],
   "source": [
    "// Test against a precomputed hash.\n",
    "use sha256::digest;\n",
    "let hashed = digest(format!(\"{:?}\", interpolated_f_eval));\n",
    "assert_eq!(\"d78b6a5f70e91dd8fa448f628528434dbfaf3caefab0a26519e1f2d8ac992f23\".to_string(), hashed);\n",
    "println!(\"Success!\");"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Commitments\n",
    "We will use [Sha256](https://en.wikipedia.org/wiki/SHA-2)-based [Merkle Trees](https://en.wikipedia.org/wiki/Merkle_tree) as our commitment scheme.\n",
    "A simple implementation of it is available to you in the `MerkleTree` class.\n",
    "Run the next cell (for the sake of this tutorial, this also serves as a test for correctness of the entire computation so far):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 294,
   "metadata": {},
   "outputs": [],
   "source": [
    "//from merkle import MerkleTree\n",
    "//f_merkle = MerkleTree(f_eval)\n",
    "//assert f_merkle.root == '6c266a104eeaceae93c14ad799ce595ec8c2764359d7ad1b4b7c57a4da52be04'\n",
    "//print('Success!')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Channel\n",
    "Theoretically, a STARK proof system is a protocol for interaction between two parties - a prover and a verifier. In practice, we convert this interactive protocol into a non-interactive proof using the [Fiat-Shamir Heuristic](https://en.wikipedia.org/wiki/Fiat%E2%80%93Shamir_heuristic). In this tutorial you will use the `Channel` class, which implements this transformation. This channel replaces the verifier in the sense that the prover (which you are writing) will send data, and receive random numbers or random `FieldElement` instances.\n",
    "\n",
    "This simple piece of code instantiates a channel object, sends the root of your Merkle Tree to it. \n",
    "Later, the channel object can be called to provide random numbers or random field elements."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 295,
   "metadata": {},
   "outputs": [],
   "source": [
    "///from channel import Channel\n",
    "//channel = Channel()\n",
    "//channel.send(f_merkle.root)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Lastly - you can retrieve the proof-so-far (i.e., everything that was passed in the channel up until a certain point) by printing the member `Channel.proof`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 296,
   "metadata": {},
   "outputs": [],
   "source": [
    "//print(channel.proof)"
   ]
  }
 ],
 "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
}