getting-started/5-minute-tutorial.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 5-minute-tutorial: Cryptimeleon Math\n",
    "\n",
    "Cryptimeleon Math is a library supplying the mathematical basics for cryptography (usually elliptic curve/pairing-based).\n",
    "\n",
    "To give you some insight into the library, let's implement the well-known Pedersen commitment scheme over an elliptic curve as an example. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Setup 🔨\n",
    "\n",
    "Let's include the Cryptimeleon Math library and set up the secp256k1 elliptic curve group. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%maven org.cryptimeleon:math:3.0.1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import org.cryptimeleon.math.structures.groups.elliptic.nopairing.Secp256k1;\n",
    "import org.cryptimeleon.math.structures.groups.lazy.LazyGroup;\n",
    "import org.cryptimeleon.math.structures.groups.*;\n",
    "\n",
    "Group group = new Secp256k1(); //this is a LazyGroup which evaluates group operations lazily (see later)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A `Group` plays the role of the set $\\mathbb{G}$. It has a `size()` and a bunch of useful methods to instantiate its `GroupElement`s."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "var n = group.size();\n",
    "System.out.println(\"group size() = \" + n);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now let's set up the public parameters for the Pedersen commitment: two random group elements $g,h\\in\\mathbb{G}$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "var g = group.getUniformlyRandomNonNeutral(); \n",
    "var h = group.getUniformlyRandomNonNeutral(); "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "`g` and `h` are `GroupElement`s. Their most important methods are `op(...)` (for the group operation) and `pow(...)` (for exponentiation/scalar multiplication). "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### `GroupElement`s are lazy 😴\n",
    "Let's look at the group elements:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "System.out.println(g);\n",
    "System.out.println(h);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Most operations concerning group elements in Math are lazy, i.e. they are only evaluated when necessary (and we consider `toString()` not to be necessary but rather a debugging tool). This has a bunch of advantages that we'll get to later. When working with `g` and `h`, this doesn't really change anything - though their values are not yet known, you can pretend that they are (when they are needed, they will be computed transparently). "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Precomputation 🔮\n",
    "`g` and `h` are fixed and publicly known and we'll later compute lots of expressions of the form $C = g^m\\cdot h^r$. To speed that up, we can invest some time and memory to do some precomputation _now_. \n",
    "Thankfully, this is very easy to do: "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "g.precomputePow();\n",
    "h.precomputePow();\n",
    "System.out.println(\"Precomputation done.\");"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Future computations `g.pow(...)` and `h.pow(...)` will benefit from precomputation.\n",
    "\n",
    "<small>_As a side-effect, the values of `g` and `h` have been explicitly computed and can now be printed by `println()` above. You can now see that they indeed look like elliptic curve points._</small> "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Committing 😱\n",
    "\n",
    "### Choosing a message 📝\n",
    "Now let's commit to a message $m$. For Pedersen commitments, $m$ lives in $\\mathbb{Z}_n$ (because exponents are to be interpreted modulo the group order $n$). We can get the appropriate $\\mathbb{Z}_n$ object from the group:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "var zn = group.getZn();"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Similar to how a `Group` is a structure that has `GroupElement`s, `zp` is a structure that contains `ZnElement`s. \n",
    "\n",
    "We can now instantiate our message $m$, which will be a `ZnElement`, in any of the following ways:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "var m = zn.valueOf(23).mul(42); //simply the number 23*42 (mod p)\n",
    "System.out.println(m);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "var m = zn.getUniformlyRandomElement(); //a random number in Zn\n",
    "System.out.println(m);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import org.cryptimeleon.math.structures.rings.zn.HashIntoZn;\n",
    "\n",
    "var m = new HashIntoZn(zn).hash(\"We attack at midnight! ⚔️\"); //the hash of the given String into Zn\n",
    "System.out.println(m);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Computing the commitment 🎲\n",
    "\n",
    "Now that we have $m$, let's compute the Pedersen commitment, which is\n",
    "$$ C = g^m\\cdot h^r$$\n",
    "for a random $r\\in\\mathbb{Z}_n$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "var r = zn.getUniformlyRandomElement();\n",
    "var C = g.pow(m).op(h.pow(r));\n",
    "System.out.println(C);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### On automatic multiexponentiation 🤖\n",
    "\n",
    "One advantage of the `LazyGroup` approach is that after calling `g.pow(m)`, that value is not immediately computed. This allows us to compute $C$ as a multiexponentiation behind the scenes, i.e. more efficiently than computing $g^m$ and $h^r$ separately and then multiplying them.\n",
    "\n",
    "This is done automatically when the value of $C$ is needed. We can force computation of $C$ by calling `computeSync()` for the sake of illustration."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "C.computeSync() //computes the value of C and blocks the caller until it's done."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The committer can now transmit $C$ to the verifier, who won't learn anything from it ($C$ is uniformly random in $\\mathbb{G}$) but will be assured that we cannot later change our mind about $m$.\n",
    "\n",
    "For this transmission, we'd have to talk about serialization. Very roughly: every `GroupElement` is able to represent itself as a `Representation`, which is safe to send, and its corresponding `Group` is able to undo this process."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "C.getRepresentation()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "group.restoreElement(C.getRepresentation()).equals(C)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For more information on serialization, see [our documentation regarding `Representation`s](https://cryptimeleon.org/docs/representations.html)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Verifying the commitment 🕵️\n",
    "\n",
    "When we've additionally given $m,r$ to the verifier, they can now check whether $m,r$ is a valid opening for $C$ by checking the following equation:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "g.pow(m).op(h.pow(r)).equals(C)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Note that here, $g^m\\cdot h^r$ is also automatically computed as multiexponentiation."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "... and that's already it for implementing the Pedersen commitment scheme."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Bonus: Parallelizing 🦑\n",
    "\n",
    "Another advantage of the `LazyGroup` approach is that it makes group computations easily parallelizable. Consider the following code snippet where we'll compute a whole bunch of commitments:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "List<GroupElement> commitments = new ArrayList<>();\n",
    "\n",
    "for (int i=0;i<500;i++) {\n",
    "    var commitment = g.pow(i).op(h.pow(zn.getUniformlyRandomElement())).compute();\n",
    "        //compute() returns immediately but starts computing the concrete value on a background thread.\n",
    "    commitments.add(commitment); //what we add to the list here could technically be compared to a Future<GroupElement>\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "As a result, the code above doesn't really run a any group computations itself and hence returns very quickly. \n",
    "All the commitments will be computed on other threads concurrently in the background, utilizing all your CPU cores. \n",
    "\n",
    "You can go on working with all the commitments as you wish (no need to consider whether they're done computing yet). Calls that require the result of the internal computations above may block until the result is there. \n",
    "\n",
    "Conceptually, calling `compute()` or `computeSync()` doesn't have any effect semantically, so for the sake of writing _correct_ code, you'll never have to use them (semantically they are `return this;` operations). But if you want to write _fast_ code, calling `compute()` on some values may enable concurrency and speed things up."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# ... what's next? 🎉\n",
    "\n",
    "If you're still curious about the library, consider our [pairing tutorial](https://cryptimeleon.org/getting-started/pairing-tutorial.html), where we go through some advanced examples for the library."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Java",
   "language": "java",
   "name": "java"
  },
  "language_info": {
   "codemirror_mode": "java",
   "file_extension": ".jshell",
   "mimetype": "text/x-java-source",
   "name": "Java",
   "pygments_lexer": "java",
   "version": "11.0.12+7"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}