tutorials/python_PoW.ipynb

{
  "metadata": {
    "celltoolbar": "Raw Cell Format",
    "colab": {
      "collapsed_sections": [],
      "name": "Tutorial_5_PoW.ipynb",
      "provenance": [],
      "toc_visible": true
    },
    "kernelspec": {
      "name": "python",
      "display_name": "Python (Pyodide)",
      "language": "python"
    },
    "language_info": {
      "codemirror_mode": {
        "name": "python",
        "version": 3
      },
      "file_extension": ".py",
      "mimetype": "text/x-python",
      "name": "python",
      "nbconvert_exporter": "python",
      "pygments_lexer": "ipython3",
      "version": "3.8"
    }
  },
  "nbformat_minor": 4,
  "nbformat": 4,
  "cells": [
    {
      "cell_type": "markdown",
      "source": "# Introduction\nThis [Jupyter](https://jupyter.org/) notebook can be run using [colab.research.google.com](https://colab.research.google.com) (see [here](https://colab.research.google.com/notebooks/intro.ipynb) for an intro) or from [jupyter.org/try](https://jupyter.org/try) (select JupyterLab). Alternatively this source file can be downloaded and run locally with [Anaconda](https://docs.anaconda.com/anaconda/navigator/) or directly with Jupyter (Lab|Notebook). Jupyter and Anaconda should be installed in all AUT engineering and computer science labs. I recommend using a web-interface for portability.\n\nThe benefit of using Jupyter is that code snippets can be run live (Python is running in the background).\n\nThe version on Github is static; markdown is rendered but code cannot be executed. All code can be copied and pasted into your favourite text editor or IDE and *should* run with Python 3.x ;)\n\nYou are encouraged to use any programming language you feel comfortable with, this is simply an example using Python (and Jupyter is designed for Python demonstrations).\n\n---",
      "metadata": {
        "colab_type": "text",
        "id": "-1F_WkaPU92j"
      }
    },
    {
      "cell_type": "markdown",
      "source": "# Tutorial: Proof of Work - Mining ",
      "metadata": {
        "colab_type": "text",
        "id": "TKJO15meU92h"
      }
    },
    {
      "cell_type": "markdown",
      "source": "**_Proof of work_** is the unique contribution to the Bitcoin protocol that achieves two aims:\n1. Allows nodes to verify transactions to achieve consensus. In Bitcoin the longest chain is a representation of the most cumulative proof of computational effort expended to date, and the longest chain is the canonical one. A proof of work verification scheme should be reasonably difficult to compute but easy to verfiy. It is difficult to find a hash (as we will see) but comparatively trivial to validate.\n2. Keeps the network secure by aligning incentives. This means it is more profitable to play by the rules than attempt to subvert the network. To earn the block reward your computational effort has to be verified by the network and in a race-condition wasted hashes or time represent lost opportunity cost.\n\nWe have seen in the previous tutorials some of the uses of hashing with the `hashlib` library. Because a standard hash function like `sha256` is random, meaning there is no way to game the system or shortcut the output, it allows equal participation from anyone in the network. If one participant chooses to dedicate all of their computers and resources to hashing, then they are allowed more \"votes\" in the network and will receive proportionally more rewards for their effort.\n\nThis whole process is referred to as _mining_ because it is analagous to gold mining.\n\nSo lets get mining!",
      "metadata": {
        "colab_type": "text",
        "id": "VeDAzJ7HU92k"
      }
    },
    {
      "cell_type": "markdown",
      "source": "### Prepare a block to be mined\nPress `shift-enter` in the cell to run it. You may have to wait for the environment to initialize if this is the first time. There is a status bar above.\n\nThe output will appear directly below the code block.",
      "metadata": {
        "colab_type": "text",
        "id": "irwHMEkuU92k"
      }
    },
    {
      "cell_type": "code",
      "source": "# we will need pickle to turn our block into a byte object\n# sha256 operates one byte at a time\nimport hashlib\nimport pickle\n\n# create a new block using sample values\nblock = {   'timestamp': 1553200425.597771,\n            'transactions': ['a','b','c'],\n            'prev_hash': '00574faf29dbb37a3b12c2f8f5c05cf03c708313d4ad1d5d968cd2438beea104',\n            'merkle_root': 'aa0522a507b6499cb3512494908ac9220',\n        }\n\n# pickle the block\npickled_block = pickle.dumps(block)\nprint(pickled_block)",
      "metadata": {
        "colab": {},
        "colab_type": "code",
        "id": "sl6HqyRQU92l",
        "trusted": true
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": "This block is in byte form (the `'b`) and can now be hashed. Lets see what it looks like.",
      "metadata": {
        "colab_type": "text",
        "id": "tqWmDuOhU92q"
      }
    },
    {
      "cell_type": "code",
      "source": "# hash the block and output a digest of hexidecimal digits\nhashed_block = hashlib.sha256(pickled_block).hexdigest()\nprint(hashed_block)",
      "metadata": {
        "colab": {},
        "colab_type": "code",
        "id": "MJW9gk-RU92q",
        "trusted": true
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": "Every time we hash this same block with sha256 we will get the same unique output. In this case repeated hashing will not change the output. (Why is this important?)\n\nLets introduce a variable that is added to the block. This variable doesn't change the data in the block, but allows for a different hash output. It is a **number** we will use **once**, then hash, test, update, and hash again. This is called a **nonce**.\n\nThis simple example shows how a nonce changes the hash:",
      "metadata": {
        "colab_type": "text",
        "id": "uMvKlzetU92t"
      }
    },
    {
      "cell_type": "code",
      "source": "# choose 16 because a hex output has 16 digits\nfor nonce in range(16):\n    print(str(nonce)+'_block_nonce')",
      "metadata": {
        "colab": {},
        "colab_type": "code",
        "id": "rkjQ5uNRU92t",
        "trusted": true
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": "Now output the hash of the above strings:",
      "metadata": {
        "colab_type": "text",
        "id": "9HkGEyGrU92w"
      }
    },
    {
      "cell_type": "code",
      "source": "for nonce in range(16):  \n    print(hashlib.sha256((str(nonce)+'block_nonce').encode()).hexdigest())",
      "metadata": {
        "colab": {},
        "colab_type": "code",
        "id": "IdGstJILU92w",
        "trusted": true
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": "There should be no pattern to the hashed values above. All that was changed was the nonce. Since a hexidecial number has 16 possible digits (0-9,a-f), there should be a one-sixteenth probability that the first digit of the digest is a `0`. (How many are above?)\n\nWhat is the probability that the first *two* digits are: `00`? \n\n$P($ `00` $)=\\left(\\frac{1}{16}\\right)\\left(\\frac{1}{16}\\right)=\\frac{1}{16^2}=\\frac{1}{256}=0.3906\\%$\n\nSo the probability the first $n$ digits are `0` is:\n\n$P($ `0` $^n)=\\frac{1}{16^n}$\n\nAs the number of zeroes increase, the probability of finding a hash with those leading zeroes goes down. If we are looking for a hash with `00` at the beginning this is called the _target difficulty_. Mining a successful block means finding a hash that is below the target value. One way to do this is to take the hash string and compare the first digit(s).",
      "metadata": {
        "colab_type": "text",
        "id": "xa2n23LSU920"
      }
    },
    {
      "cell_type": "code",
      "source": "# set the number of leading zeroes\ntarget = 1\n\n# loop through the hashes checking each one\nfor nonce in range(16):  \n    hash = hashlib.sha256((str(nonce)+'block_nonce').encode()).hexdigest()\n    print(str(hash))\n    \n    # check the string up to the indexed difficulty and compare\n    # note python string manipulation: '0'*5 = 00000; this is string multiplication\n    if hash[:target] == '0'*target:\n        print('Block Found!')\n        break\n        \n    # end of range condition\n    if nonce == 15: print('Block not found')\n    ",
      "metadata": {
        "colab": {},
        "colab_type": "code",
        "id": "iqG65E_zU921",
        "trusted": true
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": "Our loop breaks after 12 iterations because we've satisfied the condition; in this case finding a single leading zero.\n\n***\n\nUp to this point we have just been hashing a string `'_block_nonce'`. Lets now use our block.",
      "metadata": {
        "colab_type": "text",
        "id": "FU5O6Pw9U924"
      }
    },
    {
      "cell_type": "code",
      "source": "# !!caution!! - setting difficulty too high could result in waiting until the heat death of the universe to find your block\ntarget = 4 # powers of sixteen\nnonce = 1\nblock_found = False\n\n# this will loop until a block is found\nwhile block_found == False:\n    # add a nonce value to the block, here it is prepended\n    work = hashlib.sha256(bytes(nonce) + pickled_block)\n    \n    # check to see if the hash meets the target\n    if work.hexdigest()[:target] == '0'*target:\n        block_found = True\n        \n        # output some data\n        print('Target Difficulty: ' + str(target))\n        print('Nonce: ' + str(nonce))\n        print('Proof-of-work: ' + work.hexdigest())\n        \n    # update the nonce before looping\n    # this ensures the block is different before it is hashed again    \n    nonce += 1\n\n# Change the difficulty value and compare output (and time)\n# you may have to wait 10-20 seconds for output to appear below. ",
      "metadata": {
        "colab": {},
        "colab_type": "code",
        "id": "oa_3Aj3BU924",
        "trusted": true
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": "The nonce indicates how many times the loop was run which is how many `SHA-256` hashes were calculated. When you hear people say that bitcoin mining involves \"solving complex puzzles\" this is what they are referring to. Sidebar: these **aren't puzzles at all!** It is simply an algorithm to manipulate bits and compare to a target condition.\n\n```python\nTarget Difficulty: 4\nNonce: 102591\nProof-of-work: 0000ee2830b3999eec469cc16a81f0eb6a163e84ece694803adaf3392b74804b\n```\n\nAbove I set the difficulty to 4 and can see that the hash was calculated 102,591 times before meeting the condition.",
      "metadata": {
        "colab_type": "text",
        "id": "KOvFdRab8fWS"
      }
    },
    {
      "cell_type": "markdown",
      "source": "### Add a system timer for analysis",
      "metadata": {
        "colab_type": "text",
        "id": "Ryrfese_U927"
      }
    },
    {
      "cell_type": "markdown",
      "source": "Change the difficulty value above and compare the different outputs. Adding a timer can help with the comparison.",
      "metadata": {
        "colab_type": "text",
        "id": "tcRh99qlU928"
      }
    },
    {
      "cell_type": "code",
      "source": "target = 4\nnonce = 1\nblock_found = False\n\n# access the system clock and record the start time\nimport time\nstart = time.time()\nwhile block_found == False:\n    work = hashlib.sha256(bytes(nonce) + pickled_block)\n    if work.hexdigest()[:target] == '0'*target:\n        end = time.time()\n        block_found = True\n        print('Target Difficulty: ' + str(target))\n        print('Nonce: ' + str(nonce))\n        print('Proof-of-work: ' + work.hexdigest())\n        \n        # calculate and print the time; this will output in seconds\n        print('Elapsed time: ' + str(end - start))\n    nonce += 1",
      "metadata": {
        "colab": {},
        "colab_type": "code",
        "id": "W9zlRJdOU928",
        "trusted": true
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": "### Generate random blocks",
      "metadata": {
        "colab_type": "text",
        "id": "HCgzJDuJU92-"
      }
    },
    {
      "cell_type": "markdown",
      "source": "Re-running this will take similar times because we keep hashing the same block with the same nonce. In practice, once a block is found, the miners start mining the next block which contains different transactions. Introducing some random bytes into our block can help you with generating \"new\" blocks to analyse mining and difficulty performance.",
      "metadata": {
        "colab_type": "text",
        "id": "4sZdFEKSU92_"
      }
    },
    {
      "cell_type": "code",
      "source": "# secrets provides access to a secure random number generator. \n# Refer to documentation for what this means. \n# Always be cautious when generating random data for important purposes like keys.\nimport secrets\n# generate random data to append to a block\nrandom_data = secrets.token_bytes(4)\n\ntarget = 4\nnonce = 1\nblock_found = False\nstart = time.time()\nwhile block_found == False:\n    # the block now contains 4 random bytes of data\n    work = hashlib.sha256(bytes(nonce) + pickled_block + random_data)\n    if work.hexdigest()[:target] == '0'*target:\n        end = time.time()\n        block_found = True\n        print('Target Difficulty: '+ str(target))\n        print('Nonce: ' + str(nonce))\n        print('Proof-of-work: ' + work.hexdigest())\n        print('Elapsed time: ' + str(end - start))\n    nonce += 1",
      "metadata": {
        "colab": {},
        "colab_type": "code",
        "id": "Eb0K9yFiU92_",
        "trusted": true
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": "These results should be fresh. Every time you run this block or access `secrets.token_bytes(4)` the block will change.\n\nCompare results I just got:\n```\nTarget Difficulty: 4\nNonce: 276851\nProof-of-work: 000067ddf3ef7837481dc818093aea15bce9e4da166bdfc02e9916040e53cb28\nElapsed time: 37.96086359024048\n\nTarget Difficulty: 4\nNonce: 325\nProof-of-work: 000069a6bb59edfb31d0396c00ce154a295e11f39aba306f82a1425a68a9f91e\nElapsed time: 0.002000093460083008\n```\n\nThis shows the lottery-like nature of using hash functions and target difficulty values. The second set found a proof-of-work in 0.002 s and the first one took 19000 times longer!\n\n---",
      "metadata": {
        "colab_type": "text",
        "id": "mDT8_e-LU93C"
      }
    },
    {
      "cell_type": "markdown",
      "source": "## Probability\nAs more miners come online to try to earn coins (and process transactions) the difficulty must adjust to maintain the blocktime. Without this difficulty adjustment the group with the most hashpower would have already mined all the available coins in any proof of work network, likely causing the value to crash.\n\nThe difficulty set in this tutorial goes up by powers of 16; there is a sixteen-fold increase in time expected to find a block as the leading zeroes go from `0000` to `00000`. (Try with 5 or 6 and see how long you have to wait.) What if you want difficulty to increase only by a factor of two? (See exercise #1)\n\nLets look at the probability of finding a block.",
      "metadata": {
        "colab_type": "text",
        "id": "_MF0iUJi_ZWO"
      }
    },
    {
      "cell_type": "code",
      "source": "# one leading zero to start\ndiff = 1\nprob = 1/16\nprint(prob)",
      "metadata": {
        "colab": {},
        "colab_type": "code",
        "id": "Bp2l-mUqDFiD",
        "trusted": true
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": "diff = 2\nprob = 1/(16**diff)\nprint(prob)",
      "metadata": {
        "colab": {},
        "colab_type": "code",
        "id": "2-QkGHB0DakK",
        "trusted": true
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": "#loop through a range and print the results\n#range(start,stop,step)\nfor diff in range(1,16,1):\n  prob = 1/(16**diff)\n  #formatted to show the relative value\n  print(\"%.20f\" % prob)",
      "metadata": {
        "colab": {},
        "colab_type": "code",
        "id": "sXsYI-x1DnhY",
        "trusted": true
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": "#same as above only stored in an array (python list) to plot\nprob=[]\nfor diff in range(1,11,1):\n  prob.append(1/(16**diff))\nprint(prob)\n",
      "metadata": {
        "colab": {},
        "colab_type": "code",
        "id": "jCWErcjPHO35",
        "trusted": true
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": "#plot using matplotlib\nimport matplotlib.pyplot as plt\nimport numpy as np\n%matplotlib inline\nfig = plt.figure()\nax = fig.add_axes([0,0,1,1])\nax.set_xlabel('difficulty')\nax.set_ylabel('probability')\nax.plot(prob,'r*')\nplt.show()\n",
      "metadata": {
        "colab": {},
        "colab_type": "code",
        "id": "h8rcPjTTENOa",
        "trusted": true
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": "This shows the probability for a single hash to reach our target difficulty: a 6.25% chance to find 1-leading zero. \n\nThe proof of work for Bitcoin block 801276 was:\n`00000000000000000001a5455150df515b3d5900a6320ca46a821d5e046c5530`\n\nThis has 19 leading zeroes! To increase your odds you can (a) use a faster processor (b) use more processors in parallel.\n\n---",
      "metadata": {
        "colab_type": "text",
        "id": "AnfejiO5ODxy"
      }
    },
    {
      "cell_type": "markdown",
      "source": "## Difficulty\nUp to this point we have used the term target difficulty to mean the number of leading bits that are zero in a hexidecimal format. When looking up difficulty on the [web](http://bitcoin.sipa.be/) you will get a different value, for example: the difficulty when the above block was mined was `52,328,312,063,444` (52 trillion).\n\nWhat does this mean? Lets use a smaller set for analogy. Suppose the set size was 100; all integers between 0 and 100 are valid possibilities in our lottery. If the target is set at 5, then any number less than 5 is a winner: 0,1,2,3,4. \nNow, the formula for difficulty is:\n\n$\\text{difficulty}=\\frac{\\text{set size}}{\\text{target}}$\n\nso, $\\text{difficulty}=\\frac{100}{5}=20$. You can think of this as the number of attempts to \"find\" a number less than 5.\n\nThe difficulty is a measure of how many times you need to attempt the lottery to get a winner, as a statistical measure, over time.\n",
      "metadata": {
        "colab_type": "text",
        "id": "p_jrFvbeVtQB"
      }
    },
    {
      "cell_type": "code",
      "source": "# calculate bitcoin's difficulty\n# the maximum number of values that can be output \n# from SHA256 are 2^256 -1, or approximately \n# 0x00000000FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF (in hex)\nset_size = 0x00000000FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF\nprint(set_size)",
      "metadata": {
        "colab": {},
        "colab_type": "code",
        "id": "DvDQpbqVc2pX",
        "trusted": true
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": ".\\\n.\\\n.\\\npause for a moment here to reflect on how big this number is :)\\\n.\\\n.\\\n.",
      "metadata": {}
    },
    {
      "cell_type": "code",
      "source": "# recently found block's proof of work (copied from web for block 801276)\nrecent_PoW = 0x00000000000000000001a5455150df515b3d5900a6320ca46a821d5e046c5530\n# print in decimal\nprint(recent_PoW)",
      "metadata": {
        "colab": {},
        "colab_type": "code",
        "id": "C9fPVH7nhJPV",
        "trusted": true
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": "# calculate difficulty value\ndifficulty = set_size / recent_PoW\nprint(difficulty)",
      "metadata": {
        "colab": {},
        "colab_type": "code",
        "id": "jqt8DBeJhdPd",
        "trusted": true
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": "# Summary",
      "metadata": {
        "colab_type": "text",
        "id": "oQNb2pIcU93C"
      }
    },
    {
      "cell_type": "markdown",
      "source": "In this tutorial we have:<br>\n - added a nonce to our block\n - hashed blocks until they meet a difficulty requirement\n - investigated probabilities using `matplotlib`\n - defined and calculated difficulty\n \nWhat we have __not__ done is:<br>\n - set a target value that is not a power of 16\n - dynamically adjusted target values\n - appended mined blocks to a chain\n \nPython libraries that this code depends on:\n - [hashlib](https://docs.python.org/3/library/hashlib.html)\n - [pickle](https://docs.python.org/3/library/pickle.html)\n - [secrets](https://docs.python.org/3/library/secrets.html)\n - [time](https://docs.python.org/3/library/time.html)\n\nUseful links:\n - [hex to decimal converter](https://www.rapidtables.com/convert/number/hex-to-decimal.html)\n - [matplotlib quick tutorial](https://www.tutorialspoint.com/matplotlib/matplotlib_quick_guide.htm)\n - [bitcoin difficulty](https://en.bitcoin.it/wiki/Difficulty)\n\n ---",
      "metadata": {
        "colab_type": "text",
        "id": "DNjcKdvnU93D"
      }
    },
    {
      "cell_type": "markdown",
      "source": "# Exercises",
      "metadata": {
        "colab_type": "text",
        "id": "a7sz5xcAU93E"
      }
    },
    {
      "cell_type": "markdown",
      "source": "1. Mining difficulty is not only represented by leading zeroes (powers of 16) but by a value (hex number) that is recalculated every 2016 blocks (in Bitcoin). Update your code to include a target difficulty value such that:\n```python\nif hash < target: block_found = True\n```\n2. The calculated difficulty (above) was `171048168593111.78`. Compare this to the difficulty of the network of `52,328,312,063,444`. Why is there this difference between the two? Investigate the block [here](https://blockchair.com/bitcoin/block/00000000000000000001a5455150df515b3d5900a6320ca46a821d5e046c5530).\n\n3. Write a script to modify the difficulty every time a block is found faster than expected (increase difficulty) and readjusts if a block is found slower than expected (decrease difficulty).\n\n4. Calculate the hashpower of your PC and estimate how long it would take to find a block in the [present bitcoin network](https://bitinfocharts.com/comparison/bitcoin-hashrate.html).\n\n5. Can you have a proof of work blockchain with a realtime difficulty adjustment? What are some of the advantages of this setup? Limitiations?",
      "metadata": {
        "colab_type": "text",
        "id": "JEy83VEwU93F"
      }
    }
  ]
}