STARKS101/STARK101_res/STARK101_Parte1_resuelta.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": [
    "# Parte 1: La Traza y la Extensión de Bajo Grado (Low-Degree Extension)\n",
    "Hoy desarrollaremos un probador STARK para la sucesión de los Cuadrados de Fibonacci sobre un finite field.\n",
    "La sucesión de los Cuadrados de Fibonacci está definida por la relación de recurrencia $a_{n+2} = a_{n+1} ^2 + a_n ^2$.\n",
    "<br>Al final del día, su código producirá una prueba *STARK* que demostrará la siguiente afirmación: <br>**Conozco un elemento del field $X\\in \\mathbb{F}$ tal que el 1023avo elemento de la secuencia de los Cuadrados de Fibonacci que comienza con $1$ y $X$ es $2338775057$**.\n",
    "<br><br>\n",
    "## Las Bases\n",
    "### Clase FieldElement \n",
    "Usaremos nuestra clase `FieldElement` para representar elementos del field.<br> Puedes construir instancias de `FieldElement` a partir de enteros, y luego sumarlos, multiplicarlos, dividirlos, obtener inversos, etc.\n",
    "El field subyacente de esta clase es $\\mathbb{F}_{3221225473}$ ($3221225473 = 3 \\cdot 2^{30} + 1$), todas las operaciones son hechas en módulo 3221225473.\n",
    "<br><br>\n",
    "Pruébalo ejecutando la siguiente celda (shift + enter):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "from field import FieldElement\n",
    "FieldElement(3221225472) + FieldElement(10)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Traza de la secuencia de los Cuadrados de Fibonacci\n",
    "\n",
    "Para empezar, construiremos una lista `a` de longitud 1023, cuyos primeros dos elementos serán objetos FieldElement que representan al 1 y 3141592, respectivamente. Los siguientes 1021 elementos serán la secuencia de los Cuadrados de Fibonacci producida por esos dos elementos. `a` es como denominamos a la secuencia de los Cuadrados de Fibonacci, o, cuando el contexto es claro, la traza. <br>\n",
    "Corrige el siguiente código para definir `a`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "a = [FieldElement(1), FieldElement(3141592)]\n",
    "'TU_CÓDIGO_AQUÍ'"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solución:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "jupyter": {
     "source_hidden": true
    }
   },
   "outputs": [],
   "source": [
    "a = [FieldElement(1), FieldElement(3141592)]\n",
    "while len(a) < 1023:\n",
    "    a.append(a[-2] * a[-2] + a[-1] * a[-1])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Prueba tu código\n",
    "Ejecute la siguiente celda para comprobar que has definido `a` correctamente.<br> Note que esto se hace para verificar, aunque de manera ingenua y no sucinta, ya que repasa la secuencia elemento por elemento, que `a` se ha calculado de forma satisfactoria."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "assert len(a) == 1023, 'La traza debe constar exactamente de 1023 elementos.'\n",
    "assert a[0] == FieldElement(1), 'El primer elemento en la traza debe ser el 1.'\n",
    "for i in range(2, 1023):\n",
    "    assert a[i] == a[i - 1] * a[i - 1] + a[i - 2] * a[i - 2], f'La regla de recursión de los Cuadrados de Fibonacci no se aplica al índice {i}'\n",
    "assert a[1022] == FieldElement(2338775057), 'El último elemento es incorrecto!'\n",
    "print('Éxito!')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Pensando en Polinomios\n",
    "Ahora queremos pensar en la secuencia como la evaluación de algún, todavía desconocido, polinomio $f$ de grado 1022 (debido al Unisolvence Theorem).\n",
    "Elegiremos como dominio algún subgrupo $G \\subseteq \\mathbb{F}^\\times$ de tamaño 1024, por razones que se aclararán más adelante.\n",
    "\n",
    "(Recuerda que $\\mathbb{F}^\\times$ denota el grupo multiplicativo de $\\mathbb{F}$, que obtenemos a partir de $\\mathbb{F}$ omitiendo al cero, con la multiplicación presente en el field. Un subgrupo de tamaño 1024 existe porque $\\mathbb{F}^\\times$ es un grupo cíclico de tamaño $3\\cdot 2^{30}$, de modo que contiene un subgrupo de tamaño $2^i$ para cualquier $0 \\leq i \\leq 30$).\n",
    "### Encontrando un Grupo de Tamaño 1024\n",
    "Si encontramos un elemento $g \\in \\mathbb{F}$ cuyo orden (multiplicativo) es 1024, entonces $g$ generará tal grupo.\n",
    "La clase `FieldElement` proporciona un método estático `generator()` que retorna un elemento que genera $\\mathbb{F}^\\times$ (cuyo orden es $|\\mathbb{F}^\\times|$).\n",
    "1. Úsalo para obtener un generador $g$ de $G$.\n",
    "2. Crea una lista llamada `G` con todos los elementos de $G$, tal que $G[i] := g^i$.\n",
    "\n",
    "*Pista: Cuando $k$ divide a $|\\mathbb{F}^\\times|$, $g^k$ genera un grupo de tamaño $\\frac {|\\mathbb{F}^\\times|}{k}$, y la n-ésima potencia de algún `FieldElement` $x$ puede ser calculada llamando a `x ** n `.*\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Cambia la siguiente línea para que g genere un grupo de tamaño 1024\n",
    "g = FieldElement.generator()\n",
    "# Defina G con los elementos de G tal que G[i] := g ** i\n",
    "G = [] "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solución:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "jupyter": {
     "source_hidden": true
    }
   },
   "outputs": [],
   "source": [
    "g = FieldElement.generator() ** (3 * 2 ** 20)\n",
    "G = [g ** i for i in range(1024)]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Ejecute la siguiente celda para probar tu código. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Comprueba que g y G son correctos.\n",
    "assert g.is_order(1024), 'El generador g es de orden incorrecto.'\n",
    "b = FieldElement(1)\n",
    "for i in range(1023):\n",
    "    assert b == G[i], 'El lugar i-ésimo de G no es igual a la potencia i-ésima de g.'\n",
    "    b = b * g\n",
    "    assert b != FieldElement(1), f'g es de orden {i + 1}'\n",
    "    \n",
    "if b * g == FieldElement(1):\n",
    "    print('Éxito!')\n",
    "else:\n",
    "    print('g es de orden > 1024')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Clase Polynomial\n",
    "Te proporcionaremos una clase llamada `Polynomial`. La forma más sencilla de construir un polinomio es usando la variable `X` (note que es una `X` mayúscula) que representa la variable formal $x$:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from polynomial import X\n",
    "# El polinomio 2x^2 + 1.\n",
    "p = 2*X**2 + 1\n",
    "# Evalúa p en 2:\n",
    "print(p(2))\n",
    "# Escribe un polinomio, por tu cuenta, en la última línea de la celda para visualizarlo\n",
    "p"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Interpolando un Polinomio\n",
    "Nuestro módulo `polynomial` proporciona una función de interpolación de Lagrange, cuyos argumentos son:\n",
    "* x_values: correspondientes a los valores de x. [Lista]\n",
    "* y_values: para los valores de y. [Lista]\n",
    "\n",
    "Retorna el único `Polynomial` de grado < `len(x_values)` que evalúa a `y_values[i]` en `x_values[i]` para todos los valores de i."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Ejecute la siguiente celda para obtener ayuda sobre la función `interpolate_poly`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from polynomial import interpolate_poly\n",
    "interpolate_poly?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Supongamos que `a` contiene los valores de algún polinomio sobre `G` (excepto `G[-1]`, ya que `a` es un elemento más corto).\n",
    "Use `interpolate_poly()` para obtener `f` y conocer su valor en `FieldElement(2)`. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from polynomial import interpolate_poly\n",
    "# Arregla lo siguiente para que v contenga el valor de f en FieldElement(2)\n",
    "# Tenga en cuenta que interpolate_poly puede tardar hasta un minuto en ejecutarse.\n",
    "v = 'TU_CÓDIGO_AQUÍ'"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solución:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "jupyter": {
     "source_hidden": true
    }
   },
   "outputs": [],
   "source": [
    "f = interpolate_poly(G[:-1], a)\n",
    "v = f(2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Ejecute la prueba:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "assert v == FieldElement(1302089273)\n",
    "print('Éxito!')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Evaluando en un dominio más grande\n",
    "La traza, vista como evaluaciones de un polinomio $f$ en $G$, puede ampliarse ahora evaluando $f$ en un dominio mayor, creando así un código de corrección de errores Reed-Solomon.\n",
    "\n",
    "### Cosets\n",
    "Para ello, debemos dedicir un dominio mayor en el que $f$ será evaluado. \n",
    "Trabajaremos con un dominio que es 8 veces mayor que $G$. <br>Una elección natural para tal dominio es tomar algún grupo $H$ de tamaño 8192 (que existe porque 8192 divide a $|\\mathbb{F}^\\times|$), y cambiarlo por el generador de $\\mathbb{F}^\\times$, obteniendo así un [coset](https://en.wikipedia.org/wiki/Coset) de $H$.\n",
    "\n",
    "Crea una lista `H` de los elementos de $H$, y multiplica cada uno de ellos por el generador de $\\mathbb{F}^\\times$ para obtener una lista llamada `eval_domain`. En otras palabras, eval_domain = $\\{w\\cdot h^i | 0 \\leq i <8192  \\}$ para $h$ el generador de $H$ y $w$ el generador de $\\mathbb{F}^\\times$.\n",
    "\n",
    "Pista: Ya sabes cómo obtener $H$ - de forma similar a como obtuvimos $G$ hace unos minutos.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Arregla lo siguiente, asegúrate de que los elementos de H son potencias de su generador en \n",
    "# orden, es decir - H[0] será el 1, H[1] será h (el generador de H), H[2] será el generador de H\n",
    "# al cuadrado, etc.\n",
    "H = 'TU_CÓDIGO_AQUÍ'\n",
    "eval_domain = 'TU_CÓDIGO_AQUÍ'"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solución:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "jupyter": {
     "source_hidden": true
    }
   },
   "outputs": [],
   "source": [
    "w = FieldElement.generator()\n",
    "h = w ** ((2 ** 30 * 3) // 8192)\n",
    "H = [h ** i for i in range(8192)]\n",
    "eval_domain = [w * x for x in H]\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Ejecute la prueba:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "from hashlib import sha256\n",
    "assert len(set(eval_domain)) == len(eval_domain)\n",
    "w = FieldElement.generator()\n",
    "w_inv = w.inverse()\n",
    "assert '55fe9505f35b6d77660537f6541d441ec1bd919d03901210384c6aa1da2682ce' == sha256(str(H[1]).encode()).hexdigest(),\\\n",
    "    'La lista H es incorrecta. H[1] debería ser h (es decir, el generador de H).'\n",
    "for i in range(8192):\n",
    "    assert ((w_inv * eval_domain[1]) ** i) * w == eval_domain[i]\n",
    "print('Éxito!')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Evaluar en un Coset\n",
    "Es hora de usar `interpolate_poly` y `Polynomial.poly` para evaluar sobre el coset. Tenga en cuenta que se implementa de forma ingenua en nuestro módulo de Python, por lo que la interpolación puede tardar hasta un minuto.<br>\n",
    "De hecho, la interpolación y evaluación del polinomio de traza es uno de los pasos más intensos desde el punto de vista computacional del protocolo STARK, incluso cuando se utilizan métodos más eficientes (por ejemplo, FFT)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Define f_eval con las evaluaciones de f en eval_domain.\n",
    "f_eval = 'TU_CÓDIGO_AQUÍ'"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solución:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "jupyter": {
     "source_hidden": true
    }
   },
   "outputs": [],
   "source": [
    "f = interpolate_poly(G[:-1], a)\n",
    "f_eval = [f(d) for d in eval_domain]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Ejecute la prueba:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Prueba usando un hash previamente calculado.\n",
    "from hashlib import sha256\n",
    "from channel import serialize\n",
    "assert '1d357f674c27194715d1440f6a166e30855550cb8cb8efeb72827f6a1bf9b5bb' == sha256(serialize(f_eval).encode()).hexdigest()\n",
    "print('Éxito!')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Compromisos (Commitments)\n",
    "Usaremos [Árboles de Merkle](https://en.wikipedia.org/wiki/Merkle_tree) basados en [Sha-256](https://en.wikipedia.org/wiki/SHA-2) como esquema de compromiso.\n",
    "Una implementación sencilla de esto está disponible en la clase `MerkleTree`.\n",
    "Ejecute la siguiente celda (por el bien de este tutorial, esto sirve como prueba de que todo el cálculo se ha ejecutado correctamente hasta este momento):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from merkle import MerkleTree\n",
    "f_merkle = MerkleTree(f_eval)\n",
    "assert f_merkle.root == '6c266a104eeaceae93c14ad799ce595ec8c2764359d7ad1b4b7c57a4da52be04'\n",
    "print('Éxito!')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Channel\n",
    "Teóricamente, un sistema de prueba STARK es un protocolo de interacción entre dos partes: un probador y un verificador. En la práctica, convertimos este protocolo interactivo en una prueba no interactiva utilizando la [Heurística Fiat-Shamir](https://en.wikipedia.org/wiki/Fiat%E2%80%93Shamir_heuristic). En este tutorial se utilizará la clase `Channel`, que implementa esta transformación. Este channel reemplaza al verificador en el sentido de que el probador enviará datos, y recibirá números aleatorios o instancias aleatorias de FieldElement.\n",
    "\n",
    "Este simple trozo de código instanciará un channel object y envía la raíz de su Árbol de Merkle. \n",
    "Luego, el channel object puede ser llamado para proporcionar números aleatorios o elementos aleatorios del field."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from channel import Channel\n",
    "channel = Channel()\n",
    "channel.send(f_merkle.root)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Finalmente, puedes recuperar la prueba hasta el momento (es decir, todo lo que ha pasado por el channel hasta cierto punto) imprimiendo `Channel.proof`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print(channel.proof)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.10"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}