bitcoin/dumbcoin/dumbcoin.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Dumbcoin - An educational python implementation of a bitcoin-like blockchain"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Introduction <a name=\"introduction\"></a>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This is an experimental notebook that implements most of the concepts of a bitcoin-like blockchain in python.\n",
    "It is **NOT secure** neither a real blockchain and you should **NOT** use this for anything else than educational purposes. \n",
    "\n",
    "Regardless of the financial benefits/drawbacks of bitcoin, the underlying technology is very interesting and the original paper is relatively easy to grasp. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## References\n",
    "\n",
    "I used the [original bitcoin](https://bitcoin.org/bitcoin.pdf) paper as reference as well as [Michael Nielsen's bitcoin explanation](http://www.michaelnielsen.org/ddi/how-the-bitcoin-protocol-actually-works/). The [bitcoin wiki](https://en.bitcoin.it/wiki/Main_Page) is a great technical resource as well.\n",
    "\n",
    "## Table of contents\n",
    "\n",
    "1. [Hash function and mining](#mining)\n",
    "2. [Difficulty](#difficulty)\n",
    "3. [A wallet](#wallet)\n",
    "4. [Transactions](#transactions)\n",
    "5. [Blocks](#block)\n",
    "6. [Attacks](#attack)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# Requires\n",
    "# - pycryptodome (pycrypto for 3.6)\n",
    "# - numpy /scipy / matplotlib\n",
    "# - pandas"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import hashlib\n",
    "import random\n",
    "import string\n",
    "import json\n",
    "import binascii\n",
    "import numpy as np\n",
    "import pandas as pd\n",
    "import pylab as pl\n",
    "import logging\n",
    "%matplotlib inline"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Hash function and mining <a name=\"mining\"></a>\n",
    "\n",
    "So we'll start a little backward and start with the miner implementation.\n",
    "For the example here, we'll use the MD5 hash function because it's readily implemented in python. It is a **BAD** idea to use MD5 anywhere in the real world because it's been broken. But it's faster to compute than SHA256 (the hash used in bitcoin) and it's fine for educational purposes.\n",
    "\n",
    "So our hash function will turn a string of arbitrary length into a fixed-length string of 32 hexadecimal characters. For example :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def md5(message):\n",
    "    return hashlib.md5(message.encode('ascii')).hexdigest()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now, the process of *mining* is : given an arbitrary string $x$, find a nonce such that $hash(x + nonce)$ produces a hash starting with a number of leading ones.\n",
    "\n",
    "For example here, we'll \"mine\" a nonce such that the hash of our message (\"hello bitcoin\") when concatenated with our nonce will have at least 2 leading ones."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Found nonce = 183\n",
      "11c7e55dcf65c341545b3115426a8a7c\n"
     ]
    }
   ],
   "source": [
    "message = 'hello bitcoin'\n",
    "for nonce in range(1000):\n",
    "    digest = md5(message + str(nonce))\n",
    "    if digest.startswith('11'):\n",
    "        print('Found nonce = %d' % nonce)\n",
    "        break\n",
    "print(md5(message + str(nonce)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The more you increase the number of leading ones you require, the harder it becomes (on average) to find a nonce. In bitcoin, this is called the mining difficulty. Note that bitcoin doesn't require a number of leading digits, but instead requires the hash to be below a certain value. But it's the same idea.\n",
    "\n",
    "So let's define two functions that we'll reuse later : one to hash a string and one to mine a nonce for a given string."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def dumb_hash(message):\n",
    "    \"\"\"\n",
    "    An INSECURE hash function that you should not use in the real world.\n",
    "    Returns an hexadecimal hash\n",
    "    \"\"\"\n",
    "    return md5(message)\n",
    "\n",
    "\n",
    "def mine(message, difficulty=1):\n",
    "    \"\"\"\n",
    "    Given an input string, will return a nonce such that\n",
    "    hash(string + nonce) starts with `difficulty` ones\n",
    "    \n",
    "    Returns: (nonce, niters)\n",
    "        nonce: The found nonce\n",
    "        niters: The number of iterations required to find the nonce\n",
    "    \"\"\"\n",
    "    assert difficulty >= 1, \"Difficulty of 0 is not possible\"\n",
    "    i = 0\n",
    "    prefix = '1' * difficulty\n",
    "    while True:\n",
    "        nonce = str(i)\n",
    "        digest = dumb_hash(message + nonce)\n",
    "        if digest.startswith(prefix):\n",
    "            return nonce, i\n",
    "        i += 1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "With that in place, we can mine nonce of varied difficulty :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Took 7 iterations\n",
      "Took 1675 iterations\n"
     ]
    }
   ],
   "source": [
    "nonce, niters = mine('42', difficulty=1)\n",
    "print('Took %d iterations' % niters)\n",
    "\n",
    "nonce, niters = mine('42', difficulty=3)\n",
    "print('Took %d iterations' % niters)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "As you can see in this example, the number of iterations required for a difficulty of 3 is much larger than for a difficulty of 1. Note though that you could get lucky and have a string where the first nonce (0 in our case) would yield the solution. So the difficulty controls the *average* number of tries. We can do a nice plot of that"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Plotting difficulty <a name=\"difficulty\"></a>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For each difficulty level, we'll mine a nonce for a variety of input strings (we'll use 50 in this example). We'll record the average number of iterations required at each difficulty level."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def random_string(length=10):\n",
    "    return ''.join(random.choice(string.ascii_uppercase + string.digits) for _ in range(length))\n",
    "\n",
    "strings = [random_string() for i in range(50)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "levels = range(1, 5)\n",
    "# An array of results with a row for each difficulty and a column for each test string\n",
    "results = pd.DataFrame(index=strings, columns=levels, dtype=np.int)\n",
    "results.fillna(value=0)\n",
    "\n",
    "#results = np.zeros((N_LEVELS, len(strings)), dtype=np.int)\n",
    "for level in levels:\n",
    "    for s in strings:\n",
    "        _, niters = mine(s, difficulty=level)\n",
    "        results[level][s] = niters"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style>\n",
       "    .dataframe thead tr:only-child th {\n",
       "        text-align: right;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: left;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>1</th>\n",
       "      <th>2</th>\n",
       "      <th>3</th>\n",
       "      <th>4</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>96744PVF98</th>\n",
       "      <td>0</td>\n",
       "      <td>688</td>\n",
       "      <td>1830</td>\n",
       "      <td>61777</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>E39PPDT3PY</th>\n",
       "      <td>22</td>\n",
       "      <td>179</td>\n",
       "      <td>15467</td>\n",
       "      <td>15467</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>ZHEAVFMO1A</th>\n",
       "      <td>10</td>\n",
       "      <td>32</td>\n",
       "      <td>11965</td>\n",
       "      <td>170805</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>DROXD3CPQ4</th>\n",
       "      <td>5</td>\n",
       "      <td>169</td>\n",
       "      <td>169</td>\n",
       "      <td>40388</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>9BJ79T1OQ0</th>\n",
       "      <td>2</td>\n",
       "      <td>315</td>\n",
       "      <td>10556</td>\n",
       "      <td>18573</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "             1    2      3       4\n",
       "96744PVF98   0  688   1830   61777\n",
       "E39PPDT3PY  22  179  15467   15467\n",
       "ZHEAVFMO1A  10   32  11965  170805\n",
       "DROXD3CPQ4   5  169    169   40388\n",
       "9BJ79T1OQ0   2  315  10556   18573"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "results.iloc[:5]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "<matplotlib.text.Text at 0x115430588>"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAnsAAAFNCAYAAAB4/6m6AAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAIABJREFUeJzt3Xm0ZGV97vHvYzfBRhsE6RBskCZCVMCIoUUcbq5XHLiB\nK2YFkBgjGoQYiSFZJrEx16AmJJhJ5RoH4sCgMggaCY6IA8skgq2iCGjsSCONIC0goAGk8Xf/2O8J\n1Ydzuqv7DHXOPt/PWrXOrrf28Nu7dlU95917V6WqkCRJUj89ZNQFSJIkaeYY9iRJknrMsCdJktRj\nhj1JkqQeM+xJkiT1mGFPkiSpxwx70iSSnJHkL0e07CR5X5Lbk1wxweO/leTTo6htoIZ3JnndKGuY\nSUlem+Tdo65jrkuyJMm/JLkjyYdGXc94c2E/TbI2ybPb8Eb7VZJfT3JDkh8neVKSxya5MsldSf5g\nOupPsiJJJVk81XXR/OQTr3kjyVpgO2DPqvpJa3s58OKqeuYIS5sJzwCeA+w2tq6DquoDwAfG7icp\nYO+qWjMTxSR5KfDyqnrGQA2vmIllbaKGFcB1wDZVtWGml1dVfzXTy+iJI4BdgEfOxvOypWZ7P92c\nCfarvwN+v6o+CpDkPcDnqmr/maohyeeB91eV/8wsEPbsab5ZBJw46iK2VJJFWzjJHsDaiYLedPO/\nfU3RHsB/bE3Qm+l9byted6OwB3D1Ju5LU1dV3rzNixuwFlgF3AY8orW9HPh8G14BFLB4YJrP0/VI\nAbwU+FfgzcCPgO8CT2vtNwC3AMcMTHsG8E7gEuAu4AvAHgOPP649dhvwbeCocdO+A/g48BPg2ROs\nz6OAi9r0a4DjWvuxwD3A/cCPgTdMMO1LgS+24cvaev+kjf/C1n4YcGVb138DfnnctnwN8A3gXrpe\n/lXAf7Z1vQb49Tbu48fV86OBdfzLgXke19bjtrZejxp4rIBXAN9p9fwjkPbYXm3b3gH8EDhvkuf/\ne20+P263p9L9w/p/gevb83cWsMMk0z8TWAf8aRv3JuAFwK8B/9Hqfu3A+K+n6/2AB/atY1odPwT+\nbGDchwxsv1uB84GdJqljR+BiYD1wexvebTP7/R+35+oO4DzgoVPd7gPTXjvwnP/KwL55YavxOuAP\nJqntDcBPgfvac3Lspp6Tge14bNuOl00wz2uBwwbuL251jNX2IeDmti0uA/bd1OuOIfdTNv/+MdR+\n2sb97bb+twJ/1p7DZw/uV8C2bZuNvXb/E/gs3evsnvbYL01Q/+F0r+s72zSHDOwnzx4Y7/U8eP9d\nDJwybhlva/vF349bh4uAP5qN93ZvM38beQHevA17G3szAz489ubHloe9DcDL6HoI/7J94Pxje+N9\nLt2H3sPb+Ge0+7/aHn8rDwSsh9EFxJe1N9AntQ+AfQamvQN4Ot2H30MnWJ/LgLcDDwX2p/tAe9ZA\nrV/cxLbY6PG23nsN3H8S3QftU9q6HtO237YD2/JKYHdgSWs7ku5D/iHAC+k+gHadrB4GPoSAZ7X1\n/5W2rf4fAx/krb6LgUcAj27rOvYhdQ7dB+JD2rZ4xiTrPNHz+zt0H9y/CDy87RtnTzL9M9vz/+fA\nNnQf+uuBDwJLgX2Bu+lOE4CJPyz/CVgCPJEuJD++PX4i8CVgt7b+7wLOmaSORwK/QXdKwlK68PLP\nm9nvr2jPzU50YegV07DdjwRuBJ4MhC7M7NGeh6+07fRzbdt+F3jeJPX993ba3HMysB3PonsNLZlg\nfn8OfGDg/qHAtePmv7St71uAK8ftkxu97hhyP2Xz7x/D7qf70IWosfeNf6Db7549yfYa/9r972VO\n8Do7sK3fc1ody4HHDb4/TvS8jF+3CZZxIPB94CHt/s7AfwG7zMR7ubfZv3kYV/PRnwOvSrJsK6a9\nrqreV1X30/WQ7A68sarurapP0/VS7DUw/seq6rKqupfujf6pSXan6zVb2+a1oaq+RtcTcuTAtB+t\nqn+tqp9V1T2DRbR5PB14TVXdU1VXAu8GXrIV6zSR44F3VdXlVXV/VZ1JF04OGhjntKq6oaruBqiq\nD1XV91u959H1Bh045PJ+C3hvVX21bauT6LbVioFxTq2qH1XV94DP0QVc6HqF9qDrYbmnqr64Bev5\nW8A/VNV3q+rHbblHb+Lw4H3AKVV1H3Au3YfaW6vqrqq6mq5364mbWN4bquruqvo68PWBcV9B19O3\nrq3/64EjJqqjqm6tqgur6r+q6i66npb/uZn1PK09N7cB/8ID224q2/3lwN9U1Zers6aqrqcLf8uq\n6o1V9dOq+i5dyD16MzWOGeY5eX1V/WRs3xvng8Dzk2zX7r+ILmgBUFXvbc/X2HZ+YpIdBqaf9HXH\ncNtrMsPup0cAFw+8b7wO+NkQ8x/GsXT1X9LW78aq+tZUZ1pVV9CFyINb09F0/0T/YKrz1txg2NO8\nU1XfpOutWLUVkw++eY2FnPFtDx+4f8PAcn9Md+jnUXRv+k9J8qOxG90HyS9MNO0EHgXc1j7sx1xP\n95/6dNgDePW4+nZvy52wviQvaVcBjo2/H10YGsaj6OoH/ntb3crG63PzwPB/8cB2/lO6nqUrklyd\n5HeGXOaDltuGF9NdMDCRW1vQh/b88+B94uFMbrJ12AP4yMC2u5buUNmD6kiyXZJ3Jbk+yZ10PbyP\n2Mz5ZZMtdyrbfXe6w4Dj7QE8aty+89qJ1mUSwzwnk742qrvI6Frg/7TA93y6AEiSRUlOTfKfbdut\nbZMN7qebe91tbntNZtj99FFs/L7xk7aM6TDZczYdzgRe3IZfDJw9Q8vRCHhituark4GvAn8/0DZ2\nMcN2dOezwMbha2vsPjaQ5OF0h9G+T/dm/oWqes4mpq1NPPZ9YKckSwcC36PpDqtNhxvoerBOGaa+\nJHvQ9d4cDPx7Vd2f5Eq6D7eNxp3E9+lCwtj8HkZ3uHKz61NVN9MdUiXJM4DPJLmsHnxl8UQ1bLRc\num24gY0D3Gy4AfidqvrXIcZ9NfBY4ClVdXOS/YGv8cC23hJbvd3pan7MJO3XVdXeW1HPg2pi4+dk\nt9a2uf3pHOA36TokrhnYF15Ed87as+mC3g505z0ObrvNve4m216bfP/Ygv30JrrzXMeWsV1bxnSY\n7DmDrv7tBu5v6r1vom30fuCbSZ5IV/8/b1WFmpPs2dO81N5gzwP+YKBtPd2b9otbD8DvMPkb47B+\nLckzkvwc8BfAl6rqBrqexV9K8ttJtmm3Jyd5/KZn99+13kB30cRfJ3lokl+mO0Tz/q2s8wd050iN\n+SfgFUme0r6z72FJDk2ydJLpH0b3AbAeIMnL6Hr2Bue/W9sOEzkHeFmS/ZNsC/wVcHlVrd1c4UmO\nTDIWAm5vdUx02Gt9ax9cz3OAP0qyZwvjf0V34vxsfwXIO4FTWmgmybIkh08y7lK6HsQfJdmJ7h+X\nrbXV253utIE/TnJA20f2avVfAdyV5DXpvkNvUZL9kjx5C2qa6nNyLt05tL9H69VrltKdjnArXbDZ\n0q/HmXR7be79Ywv20wuAwwbeN97I9H3WvqfVf3CShyRZnuRx7bEr6Q6Xb5NkJd3h5MmMf7+gqtYB\nX6br0btwkkPsmqcMe5rP3kgXUgYdB/wJ3YfBvnSBaio+SPdhfBtwAO0wR+uNey7duS3fpztU9ia6\nE7KH9Zt0J05/H/gIcHJVfWYr63w9cGY77HZUVa2m2xZvo/tgWkN3kcWEquoaul7Sf6f7IHgC3ZXL\nYz5L93UQNyf54QTTf4bu3KQL6Xo2HsPw53g9Gbg8yY/prgA8sZ0nNn4Z/0V3ftu/tvU8CHgv3YfT\nZXRXjd4DvGrI5U6nt9LV/ukkd9FdrPGUScZ9C91FHj9s431yaxc6le1eVR+i254fpLsQ6Z/priC+\nn+6c1P3ptukP6YLhDpPMarwpPydVdRPdvvg0un/qxpxFdxj2RrrzK7+0hfPd3Pba1PvHsPvp1cAJ\ndNv1JrrX37otqXMT9V9Bd1HYm+nOsfsCD/RUvq6tz+10V0l/cKJ5NG+lO6f09iSnDbSfSffa9xBu\nz4x99YEkSVrAkvwq3dGFPcpw0Cv27EmStMAl2YbuK4TebdDrH8OeJEkLWDvX+EfArnSnGahnPIwr\nSZLUY/bsSZIk9ZhhT5Ikqcf8UuVm5513rhUrVoy6DEmSpM36yle+8sOqGupnQw17zYoVK1i9evWo\ny5AkSdqsJNdvfqyOh3ElSZJ6zLAnSZLUY4Y9SZKkHjPsSZIk9ZhhT5IkqccMe5IkST1m2JMkSeox\nw54kSVKPGfYkSZJ6zLAnSZLUY/5cmiRJmlFJRrr8qhrp8kfNnj1JkjSjqmpKtz1ec/GUpl/oDHuS\nJEk9ZtiTJEnqMcOeJElSjxn2JEmSesywJ0mS1GOGPUmSpB4z7EmSJPWYYU+SJKnHDHuSJEk9ZtiT\nJEnqMcOeJElSjxn2JEmSesywJ0mS1GOGPUmSpB4z7EmSJPWYYU+SJKnHDHuSJEk9ZtiTJEnqMcOe\nJElSjxn2JEmSemzGwl6S9ya5Jck3B9p2SnJJku+0vzsOPHZSkjVJvp3keQPtByS5qj12WpK09m2T\nnNfaL0+yYmCaY9oyvpPkmJlaR0mSpLluJnv2zgAOGde2Cri0qvYGLm33SbIPcDSwb5vm7UkWtWne\nARwH7N1uY/M8Fri9qvYC3gy8qc1rJ+Bk4CnAgcDJg6FSkiRpIZmxsFdVlwG3jWs+HDizDZ8JvGCg\n/dyqureqrgPWAAcm2RXYvqq+VFUFnDVumrF5XQAc3Hr9ngdcUlW3VdXtwCU8OHRKkiQtCLN9zt4u\nVXVTG74Z2KUNLwduGBhvXWtb3obHt280TVVtAO4AHrmJeUmSJC04I7tAo/XU1aiWD5Dk+CSrk6xe\nv379KEuRJEmaEbMd9n7QDs3S/t7S2m8Edh8Yb7fWdmMbHt++0TRJFgM7ALduYl4PUlWnV9XKqlq5\nbNmyKayWJEnS3DTbYe8iYOzq2GOAjw60H92usN2T7kKMK9oh3zuTHNTOx3vJuGnG5nUE8NnWW/gp\n4LlJdmwXZjy3tUmSJC04i2dqxknOAZ4J7JxkHd0VsqcC5yc5FrgeOAqgqq5Ocj5wDbABOKGq7m+z\neiXdlb1LgE+0G8B7gLOTrKG7EOToNq/bkvwF8OU23huravyFIpIkSQvCjIW9qvrNSR46eJLxTwFO\nmaB9NbDfBO33AEdOMq/3Au8dulhJkqSe8hc0JEmSesywJ0mS1GOGPUmSpB4z7EmSJPWYYU+SJKnH\nDHuSJEk9ZtiTJEnqMcOeJElSjxn2JEmSesywJ0mS1GOGPUmSpB4z7EmSJPWYYU+SJKnHDHuSJEk9\nZtiTJEnqMcOeJElSjxn2JEmSesywJ0mS1GOGPUmSpB4z7EmSJPWYYU+SJKnHDHuSJEk9ZtiTJEnq\nMcOeJElSjxn2JEmSesywJ0mS1GOGPUmSpB4z7EmSJPWYYU+SJKnHDHuSJEk9ZtiTJEnqMcOeJElS\njxn2JEmSesywJ0mS1GOGPUmSpB4bSdhL8kdJrk7yzSTnJHlokp2SXJLkO+3vjgPjn5RkTZJvJ3ne\nQPsBSa5qj52WJK192yTntfbLk6yY/bWUJEkavVkPe0mWA38ArKyq/YBFwNHAKuDSqtobuLTdJ8k+\n7fF9gUOAtydZ1Gb3DuA4YO92O6S1HwvcXlV7AW8G3jQLqyZJkjTnjOow7mJgSZLFwHbA94HDgTPb\n42cCL2jDhwPnVtW9VXUdsAY4MMmuwPZV9aWqKuCscdOMzesC4OCxXj9JkqSFZNbDXlXdCPwd8D3g\nJuCOqvo0sEtV3dRGuxnYpQ0vB24YmMW61ra8DY9v32iaqtoA3AE8ctpXRpIkaY4bxWHcHel63vYE\nHgU8LMmLB8dpPXU1C7Ucn2R1ktXr16+f6cVJkiTNulEcxn02cF1Vra+q+4APA08DftAOzdL+3tLG\nvxHYfWD63VrbjW14fPtG07RDxTsAt44vpKpOr6qVVbVy2bJl07R6kiRJc8cowt73gIOSbNfOozsY\nuBa4CDimjXMM8NE2fBFwdLvCdk+6CzGuaId870xyUJvPS8ZNMzavI4DPtt5CSZKkBWXxbC+wqi5P\ncgHwVWAD8DXgdODhwPlJjgWuB45q41+d5Hzgmjb+CVV1f5vdK4EzgCXAJ9oN4D3A2UnWALfRXc0r\nSZK04Mx62AOoqpOBk8c130vXyzfR+KcAp0zQvhrYb4L2e4Ajp16pJEnS/OYvaEiSJPXYSHr2JEnS\n/PHEN3yaO+6+b6Q1rFj1sZEsd4cl2/D1k587kmVPF8OeJEnapDvuvo+1px466jJGYlQhczp5GFeS\nJKnHDHuSJEk9ZtiTJEnqMcOeJElSjxn2JEmSesywJ0mS1GOGPUmSpB4z7EmSJPWYYU+SJKnHDHuS\nJEk9ZtiTJEnqMcOeJElSjxn2JEmSesywJ0mS1GOGPUmSpB4z7EmSJPWYYU+SJKnHDHuSJEk9ZtiT\nJEnqMcOeJElSjxn2JEmSesywJ0mS1GOGPUmSpB4z7EmSJPWYYU+SJKnHhgp7Sf4myfZJtklyaZL1\nSV4808VJkiRpaobt2XtuVd0JHAasBfYC/mSmipIkSdL0GDbsLW5/DwU+VFV3zFA9kiRJmkaLNz8K\nABcn+RZwN/B7SZYB98xcWZIkSZoOQ/XsVdUq4GnAyqq6D/gJcPhMFiZJkqSpG7ZnD+BxwIokg9Oc\nNc31SJIkaRoNFfaSnA08BrgSuL81F4Y9SZKkOW3Ynr2VwD5VVTNZjCRJkqbXsFfjfhP4helaaJJH\nJLkgybeSXJvkqUl2SnJJku+0vzsOjH9SkjVJvp3keQPtByS5qj12WpK09m2TnNfaL0+yYrpqlyRJ\nmk+GDXs7A9ck+VSSi8ZuU1juW4FPVtXjgCcC1wKrgEuram/g0nafJPsARwP7AocAb0+yqM3nHcBx\nwN7tdkhrPxa4var2At4MvGkKtUqSJM1bwx7Gff10LTDJDsCvAi8FqKqfAj9NcjjwzDbamcDngdfQ\nXfV7blXdC1yXZA1wYJK1wPZV9aU237OAFwCfaNOM1XwB8LYk8TC0JElaaIb96pUvAN8Clrbbta1t\na+wJrAfel+RrSd6d5GHALlV1UxvnZmCXNrwcuGFg+nWtbXkbHt++0TRVtQG4A3jk+EKSHJ9kdZLV\n69ev38rVkSRJmruG/W3co4ArgCOBo4DLkxyxlctcDPwK8I6qehLdd/atGhyh9cDNeC9cVZ1eVSur\nauWyZctmenGSJEmzbtjDuH8GPLmqbgFov6DxGbpDpFtqHbCuqi5v9y+gC3s/SLJrVd2UZFfglvb4\njcDuA9Pv1tpubMPj2wenWde+F3AH4NatqFWSJGleG/YCjYeMBb3m1i2YdiNVdTNwQ5LHtqaDgWuA\ni4BjWtsxwEfb8EXA0e0K2z3pLsS4oh3yvTPJQe0q3JeMm2ZsXkcAn/V8PUmStBAN27P3ySSfAs5p\n918IfHwKy30V8IEkPwd8F3gZXXg8P8mxwPV0h4upqquTnE8XCDcAJ1TV2Bc7vxI4A1hCd2HGJ1r7\ne4Cz28Uct9FdzStJkrTgDBX2qupPkvwG8PTWdHpVfWRrF1pVV9J9UfN4B08y/inAKRO0rwb2m6D9\nHrrzCyVJkha0oX8bt6ouBC6cwVokSZI0zTYZ9pJ8saqekeQuNr46NnQXzW4/o9VJkiRpSjYZ9qrq\nGe3v0tkpR5IkSdNp2O/ZO3uYNkmSJM0tw359yr6Dd9p31x0w/eVIkiRpOm0y7CU5qZ2v98tJ7my3\nu4Af8MB32kmSJGmO2mTYq6q/bufr/W1Vbd9uS6vqkVV10izVKEmSpK007PfsnZRkR7pfr3joQPtl\nM1WYJEmSpm6osJfk5cCJdL8/eyVwEPDvwLNmrjRJkiRN1bAXaJwIPBm4vqr+F/Ak4EczVpUkSZKm\nxbBh7572E2Qk2baqvgU8dubKkiRJ0nQY9ufS1iV5BPDPwCVJbgeun7myJEmSNB2GvUDj19vg65N8\nDtgB+OSMVSVJkqRpsdmwl2QRcHVVPQ6gqr4w41VJkiRpWmz2nL2quh/4dpJHz0I9kiRJmkbDnrO3\nI3B1kiuAn4w1VtXzZ6QqSZIkTYthw97rZrQKSZIkzYhhL9D4QpI9gL2r6jNJtgMWzWxpkiRJmqqh\nvmcvyXHABcC7WtNyuq9hkSRJ0hw27JcqnwA8HbgToKq+A/z8TBUlSZKk6TFs2Lu3qn46difJYqBm\npiRJkiRNl2HD3heSvBZYkuQ5wIeAf5m5siRJkjQdhg17q4D1wFXA7wIfr6o/m7GqJEmSNC2G/eqV\nV1XVW4F/GmtIcmJrkyRJ0hw1bM/eMRO0vXQa65AkSdIM2GTPXpLfBF4E7JnkooGHlgK3zWRhkiRJ\nmrrNHcb9N+AmYGfg7wfa7wK+MVNFSZIkaXpsMuxV1fXA9cBTZ6ccSZIkTafNHca9i4m/Ty9AVdX2\nM1KVJEmSpsXmevaWzlYhkiRJmn7DXo0rSZKkeciwJ0mS1GPDfqmyJElaoJY+fhVPOHPVqMsYiaWP\nBzh01GVMiWFPkiRt0l3XnsraU+d34NlaK1Z9bNQlTJmHcSVJknpsZGEvyaIkX0tycbu/U5JLknyn\n/d1xYNyTkqxJ8u0kzxtoPyDJVe2x05KktW+b5LzWfnmSFbO9fpIkSXPBKHv2TgSuHbi/Cri0qvYG\nLm33SbIPcDSwL3AI8PYki9o07wCOA/Zut0Na+7HA7VW1F/Bm4E0zuyqSJElz00jCXpLd6M52fPdA\n8+HAmW34TOAFA+3nVtW9VXUdsAY4MMmuwPZV9aWqKuCscdOMzesC4OCxXj9JkqSFZFQ9e28B/hT4\n2UDbLlV1Uxu+GdilDS8HbhgYb11rW96Gx7dvNE1VbQDuAB45jfVLkiTNC7Me9pIcBtxSVV+ZbJzW\nUzfRz7RNdy3HJ1mdZPX69etnenGSJEmzbhQ9e08Hnp9kLXAu8Kwk7wd+0A7N0v7e0sa/Edh9YPrd\nWtuNbXh8+0bTJFkM7ADcOr6Qqjq9qlZW1cply5ZNz9pJkiTNIbMe9qrqpKrarapW0F148dmqejFw\nEXBMG+0Y4KNt+CLg6HaF7Z50F2Jc0Q753pnkoHY+3kvGTTM2ryPaMma8p1CSJGmumUtfqnwqcH6S\nY4HrgaMAqurqJOcD1wAbgBOq6v42zSuBM4AlwCfaDeA9wNlJ1gC30YVKSZKkBWekYa+qPg98vg3f\nChw8yXinAKdM0L4a2G+C9nuAI6exVEmSpHnJX9CQJEnqMcOeJElSjxn2JEmSesywJ0mS1GOGPUmS\npB4z7EmSJPWYYU+SJKnHDHuSJEk9ZtiTJEnqMcOeJElSjxn2JEmSesywJ0mS1GOGPUmSpB4z7EmS\nJPXY4lEXIEmS5r4Vqz426hJGYocl24y6hCkz7EmSpE1ae+qhI13+ilUfG3kN85mHcSVJknrMsCdJ\nktRjhj1JkqQeM+xJkiT1mGFPkiSpxwx7kiRJPWbYkyRJ6jHDniRJUo8Z9iRJknrMsCdJktRjhj1J\nkqQeM+xJkiT1mGFPkiSpxwx7kiRJPWbYkyRJ6jHDniRJUo8Z9iRJknrMsCdJktRjhj1JkqQem/Ww\nl2T3JJ9Lck2Sq5Oc2Np3SnJJku+0vzsOTHNSkjVJvp3keQPtByS5qj12WpK09m2TnNfaL0+yYrbX\nU5IkaS4YRc/eBuDVVbUPcBBwQpJ9gFXApVW1N3Bpu0977GhgX+AQ4O1JFrV5vQM4Dti73Q5p7ccC\nt1fVXsCbgTfNxopJkiTNNbMe9qrqpqr6ahu+C7gWWA4cDpzZRjsTeEEbPhw4t6rurarrgDXAgUl2\nBbavqi9VVQFnjZtmbF4XAAeP9fpJkiQtJCM9Z68dXn0ScDmwS1Xd1B66GdilDS8HbhiYbF1rW96G\nx7dvNE1VbQDuAB457SsgSZI0x40s7CV5OHAh8IdVdefgY62nrmahhuOTrE6yev369TO9OEmSpFk3\nkrCXZBu6oPeBqvpwa/5BOzRL+3tLa78R2H1g8t1a241teHz7RtMkWQzsANw6vo6qOr2qVlbVymXL\nlk3HqkmSJM0po7gaN8B7gGur6h8GHroIOKYNHwN8dKD96HaF7Z50F2Jc0Q753pnkoDbPl4ybZmxe\nRwCfbb2FkiRJC8riESzz6cBvA1clubK1vRY4FTg/ybHA9cBRAFV1dZLzgWvoruQ9oarub9O9EjgD\nWAJ8ot2gC5NnJ1kD3EZ3Na8kSdKCM+thr6q+CEx2ZezBk0xzCnDKBO2rgf0maL8HOHIKZUqSJPWC\nv6AhSZLUY4Y9SZKkHjPsSZIk9ZhhT5IkqccMe5IkST1m2JMkSeoxw54kSVKPGfYkSZJ6zLAnSZLU\nY4Y9SZKkHjPsSZIk9ZhhT5IkqccMe5IkST1m2JMkSeoxw54kSVKPGfYkSZJ6bPGoC5AkzU9JRrr8\nqhrp8qX5wp49SdJWqaqtvu3xmounNL1BTxqeYU+SJKnHDHuSJEk9ZtiTJEnqMcOeJElSjxn2JEmS\nesywJ0mS1GOGPUmSpB4z7EmSJPWYYU+SJKnHDHuSJEk95m/jStIC9cQ3fJo77r5vZMtfsepjI1v2\nDku24esnP3dky5dmk2FPkhaoO+6+j7WnHjrqMkZilEFTmm0expUkSeoxw54kSVKPGfYkSZJ6zHP2\nJEnSjEoy9Xm8aeunraopL38+M+xJ0gK19PGreMKZq0ZdxkgsfTzAwrw4ZRQWetgaNcOeJC1Qd117\nqlfjSgtAr8/ZS3JIkm8nWZNkYf77KkmSFrTe9uwlWQT8I/AcYB3w5SQXVdU1o61MkuaOhdrDtcOS\nbUZdgjRrehv2gAOBNVX1XYAk5wKHA4Y9aRLTcRL1VHhez+wa5SHcFas+tmAPIUuzrc9hbzlww8D9\ndcBTBkdIcjxwPMCjH/3o2atsCz3hzCeMuoSRuuqYq0Zdwrwx1X1lvzP2m6ZKts5U63dfmV1T/edg\nKldXgv8cSMPqc9jbrKo6HTgdYOXKlXP2XcMPMA3LfUWzybAlzQ99vkDjRmD3gfu7tTZJkqQFo89h\n78vA3kl/QFRRAAAEtElEQVT2TPJzwNHARSOuSZIkaVb19jBuVW1I8vvAp4BFwHur6uoRlyVJkjSr\nehv2AKrq48DHR12HJEnSqPT5MK4kSdKCZ9iTJEnqMcOeJElSjxn2JEmSesywJ0mS1GOGPUmSpB4z\n7EmSJPVY/G3DTpL1wPWjrmMO2hn44aiL0Lzh/qJhua9oS7i/PNgeVbVsmBENe9qkJKurauWo69D8\n4P6iYbmvaEu4v0yNh3ElSZJ6zLAnSZLUY4Y9bc7poy5A84r7i4blvqIt4f4yBZ6zJ0mS1GP27EmS\nJPWYYU8TSvLeJLck+eaoa9HclmT3JJ9Lck2Sq5OcOOqaNHcleWiSK5J8ve0vbxh1TZrbkixK8rUk\nF4+6lvnKsKfJnAEcMuoiNC9sAF5dVfsABwEnJNlnxDVp7roXeFZVPRHYHzgkyUEjrklz24nAtaMu\nYj4z7GlCVXUZcNuo69DcV1U3VdVX2/BddG/Ky0dbleaq6vy43d2m3Tx5XBNKshtwKPDuUdcynxn2\nJE2bJCuAJwGXj7YSzWXtsNyVwC3AJVXl/qLJvAX4U+Bnoy5kPjPsSZoWSR4OXAj8YVXdOep6NHdV\n1f1VtT+wG3Bgkv1GXZPmniSHAbdU1VdGXct8Z9iTNGVJtqELeh+oqg+Puh7ND1X1I+BzeH6wJvZ0\n4PlJ1gLnAs9K8v7RljQ/GfYkTUmSAO8Brq2qfxh1PZrbkixL8og2vAR4DvCt0ValuaiqTqqq3apq\nBXA08NmqevGIy5qXDHuaUJJzgH8HHptkXZJjR12T5qynA79N91/3le32a6MuSnPWrsDnknwD+DLd\nOXt+pYY0g/wFDUmSpB6zZ0+SJKnHDHuSJEk9ZtiTJEnqMcOeJElSjxn2JEmSesywJ0lNkvvbV8dc\nneTrSV6d5CHtsZVJTmvD2yb5TBv3hUn+R5vmyiTLk1ywlct/aZK3teEXJNln+tZO0kK1eNQFSNIc\ncnf7GS+S/DzwQWB74OSqWg2sbuM9CWBg3HcCf11VY9/uf8Q01PIC4GLgmmmYl6QFzJ49SZpAVd0C\nHA/8fjrPTHJxC4HvB57cevJ+FzgK+IskH0iyIsk3AZIsSvJ3Sb6Z5BtJXtXa1ybZuQ2vTPL5wWUn\neRrwfOBv2zIek+SrA4/vPXhfkjbFnj1JmkRVfTfJIuDnB9puSfJy4I+r6jCAJE8FLq6qC5KsGJjF\n8cAKYP+q2pBkpyGX+29JLhqbZ1vGHUn2r6orgZcB75v6GkpaCOzZk6SZ82zgXVW1AaCqbpvCvN4N\nvKyFzxfSHWKWpM0y7EnSJJL8InA/cMs0z3oDD7z/PnTIaS4E/jdwGPCVqrp1mmuS1FOGPUmaQJJl\nwDuBt9XW/4j4JcDvJlnc5jl2GHctcEAb/o1Jpr0LWDp2p6ruAT4FvAMP4UraAoY9SXrAkrGvXgE+\nA3waeMMU5vdu4HvAN5J8HXhRa38D8NYkq+l6DidyLvAnSb6W5DGt7QPAz1pdkjSUbP0/rJKk2ZTk\nj4Edqup1o65F0vzh1biSNA8k+QjwGOBZo65F0vxiz54kSVKPec6eJElSjxn2JEmSesywJ0mS1GOG\nPUmSpB4z7EmSJPWYYU+SJKnH/j9rQbbxMcniYAAAAABJRU5ErkJggg==\n",
      "text/plain": [
       "<matplotlib.figure.Figure at 0x115342c50>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "pl.figure(figsize=(10, 5))\n",
    "ax = pl.subplot(111)\n",
    "ax.set_title('Number of iterations to mine a nonce for various difficulty')\n",
    "results.plot.box(showfliers=False, ax=ax)\n",
    "ax.set_xlabel('Difficulty')\n",
    "ax.set_ylabel('Iterations')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# A wallet <a name=\"wallet\"></a>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In bitcoin a wallet is a private/public key pair. If you don't know what public/private key is, you should probably read about [RSA](https://en.wikipedia.org/wiki/RSA_(cryptosystem)).\n",
    "\n",
    "The public key is used to receive transactions and the private key is used to spend money. By signing a transaction with our private key, anybody else can verify the signature using our public key.\n",
    "\n",
    "Note that in bitcoin, the wallet is a little bit more complicated. A wallet is a set of multiple private/public key pairs, and an address is not directly the public key. This ensures better privacy and security, but for dumbcoin, we'll use a single key and use the public key as the address."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import Crypto\n",
    "import Crypto.Random\n",
    "from Crypto.Hash import SHA\n",
    "from Crypto.PublicKey import RSA\n",
    "from Crypto.Signature import PKCS1_v1_5\n",
    "\n",
    "\n",
    "class Wallet(object):\n",
    "    \"\"\"\n",
    "    A wallet is a private/public key pair\n",
    "    \"\"\"\n",
    "    def __init__(self):\n",
    "        random_gen = Crypto.Random.new().read\n",
    "        self._private_key = RSA.generate(1024, random_gen)\n",
    "        self._public_key = self._private_key.publickey()\n",
    "        self._signer = PKCS1_v1_5.new(self._private_key)\n",
    "        \n",
    "    @property\n",
    "    def address(self):\n",
    "        \"\"\"We take a shortcut and say address is public key\"\"\"\n",
    "        return binascii.hexlify(self._public_key.exportKey(format='DER')).decode('ascii')\n",
    "    \n",
    "    def sign(self, message):\n",
    "        \"\"\"\n",
    "        Sign a message with this wallet\n",
    "        \"\"\"\n",
    "        h = SHA.new(message.encode('utf8'))\n",
    "        return binascii.hexlify(self._signer.sign(h)).decode('ascii')\n",
    "    \n",
    "    \n",
    "def verify_signature(wallet_address, message, signature):\n",
    "    \"\"\"\n",
    "    Check that the provided `signature` corresponds to `message`\n",
    "    signed by the wallet at `wallet_address`\n",
    "    \"\"\"\n",
    "    pubkey = RSA.importKey(binascii.unhexlify(wallet_address))\n",
    "    verifier = PKCS1_v1_5.new(pubkey)\n",
    "    h = SHA.new(message.encode('utf8'))\n",
    "    return verifier.verify(h, binascii.unhexlify(signature))\n",
    "\n",
    "\n",
    "# Check that the wallet signing functionality works\n",
    "w1 = Wallet()\n",
    "signature = w1.sign('foobar')\n",
    "assert verify_signature(w1.address, 'foobar', signature)\n",
    "assert not verify_signature(w1.address, 'rogue message', signature)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Doing transactions <a name=\"transactions\"></a>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "To exchange money between wallets, we'll use transcations. A transaction is composed of :\n",
    "- A spender, who will sign the transaction and who's spending his money\n",
    "- A number of inputs, which are other transactions' outputs. The recipient of all those should be the spender's wallet.\n",
    "  Otherwise you could spend other people's money.\n",
    "- A number of outputs, each of which specify an amount of money and a recipient\n",
    "\n",
    "Transactions can also contain a \"transaction fee\" which is an incentive for the miner to include the transaction in a block (more on that later). The fee is just the difference between the total input amount and the total output amount.\n",
    "\n",
    "\n",
    "Since all transactions need a parent, we also need a root in our hierarchy. This will be the *GenesisTransaction*."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class TransactionInput(object):\n",
    "    \"\"\"\n",
    "    An input for a transaction. This points to an output of another transaction\n",
    "    \"\"\"\n",
    "    def __init__(self, transaction, output_index):\n",
    "        self.transaction = transaction\n",
    "        self.output_index = output_index\n",
    "        assert 0 <= self.output_index < len(transaction.outputs)\n",
    "        \n",
    "    def to_dict(self):\n",
    "        d = {\n",
    "            'transaction': self.transaction.hash(),\n",
    "            'output_index': self.output_index\n",
    "        }\n",
    "        return d\n",
    "    \n",
    "    @property\n",
    "    def parent_output(self):\n",
    "        return self.transaction.outputs[self.output_index]\n",
    "    \n",
    "\n",
    "class TransactionOutput(object):\n",
    "    \"\"\"\n",
    "    An output for a transcation. This specifies an amount and a recipient (wallet)\n",
    "    \"\"\"\n",
    "    def __init__(self, recipient_address, amount):\n",
    "        self.recipient = recipient_address\n",
    "        self.amount = amount\n",
    "        \n",
    "    def to_dict(self):\n",
    "        d = {\n",
    "            'recipient_address': self.recipient,\n",
    "            'amount': self.amount\n",
    "        }\n",
    "        return d\n",
    "\n",
    "        \n",
    "def compute_fee(inputs, outputs):\n",
    "    \"\"\"\n",
    "    Compute the transaction fee by computing the difference between total input and total output\n",
    "    \"\"\"\n",
    "    total_in = sum(i.transaction.outputs[i.output_index].amount for i in inputs)\n",
    "    total_out = sum(o.amount for o in outputs)\n",
    "    assert total_out <= total_in, \"Invalid transaction with out(%f) > in(%f)\" % (total_out, total_in)\n",
    "    return total_in - total_out\n",
    "\n",
    "    \n",
    "class Transaction(object):\n",
    "    def __init__(self, wallet, inputs, outputs):\n",
    "        \"\"\"\n",
    "        Create a transaction spending money from the provided wallet\n",
    "        \"\"\"\n",
    "        self.inputs = inputs\n",
    "        self.outputs = outputs\n",
    "        self.fee = compute_fee(inputs, outputs)\n",
    "        self.signature = wallet.sign(json.dumps(self.to_dict(include_signature=False)))\n",
    "        \n",
    "    def to_dict(self, include_signature=True):\n",
    "        d = {\n",
    "            \"inputs\": list(map(TransactionInput.to_dict, self.inputs)),\n",
    "            \"outputs\": list(map(TransactionOutput.to_dict, self.outputs)),\n",
    "            \"fee\": self.fee\n",
    "        }\n",
    "        if include_signature:\n",
    "            d[\"signature\"] = self.signature\n",
    "        return d\n",
    "    \n",
    "    def hash(self):\n",
    "        return dumb_hash(json.dumps(self.to_dict()))\n",
    "    \n",
    "    \n",
    "class GenesisTransaction(Transaction):\n",
    "    \"\"\"\n",
    "    This is the first transaction which is a special transaction\n",
    "    with no input and 25 bitcoins output\n",
    "    \"\"\"\n",
    "    def __init__(self, recipient_address, amount=25):\n",
    "        self.inputs = []\n",
    "        self.outputs = [\n",
    "            TransactionOutput(recipient_address, amount)\n",
    "        ]\n",
    "        self.fee = 0\n",
    "        self.signature = 'genesis'\n",
    "        \n",
    "    def to_dict(self, include_signature=False):\n",
    "        # TODO: Instead, should sign genesis transaction will well-known public key ?\n",
    "        assert not include_signature, \"Cannot include signature of genesis transaction\"\n",
    "        return super().to_dict(include_signature=False)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "With the classes above, we can make transactions between alice and bob."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "alice = Wallet()\n",
    "bob = Wallet()\n",
    "\n",
    "t1 = GenesisTransaction(alice.address)\n",
    "t2 = Transaction(\n",
    "    alice,\n",
    "    [TransactionInput(t1, 0)],\n",
    "    [TransactionOutput(bob.address, 2.0), TransactionOutput(alice.address, 22.0)]\n",
    ")\n",
    "assert np.abs(t2.fee - 1.0) < 1e-5"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In bitcoin, you never store how much you have in your wallet. Instead, you go through the whole chain of transactions to compute how much you have. Let's write a function to do that"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [],
   "source": [
    "alice = Wallet()\n",
    "bob = Wallet()\n",
    "walter = Wallet()\n",
    "\n",
    "# This gives 25 coins to Alice\n",
    "t1 = GenesisTransaction(alice.address)\n",
    "\n",
    "# Of those 25, Alice will spend\n",
    "# Alice -- 5 --> Bob\n",
    "#       -- 15 --> Alice\n",
    "#       -- 5 --> Walter\n",
    "t2 = Transaction(\n",
    "    alice,\n",
    "    [TransactionInput(t1, 0)],\n",
    "    [TransactionOutput(bob.address, 5.0), TransactionOutput(alice.address, 15.0), TransactionOutput(walter.address, 5.0)]\n",
    ")\n",
    "\n",
    "# Walter -- 5 --> Bob\n",
    "t3 = Transaction(\n",
    "    walter,\n",
    "    [TransactionInput(t2, 2)],\n",
    "    [TransactionOutput(bob.address, 5.0)])\n",
    "\n",
    "# Bob -- 8 --> Walter\n",
    "#     -- 1 --> Bob\n",
    "#        1 fee\n",
    "t4 = Transaction(\n",
    "    bob,\n",
    "    [TransactionInput(t2, 0), TransactionInput(t3, 0)],\n",
    "    [TransactionOutput(walter.address, 8.0), TransactionOutput(bob.address, 1.0)]\n",
    ")\n",
    "\n",
    "transactions = [t1, t2, t3, t4]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Alice  has 15.00 dumbcoins\n",
      "Bob    has 1.00 dumbcoins\n",
      "Walter has 8.00 dumbcoins\n"
     ]
    }
   ],
   "source": [
    "def compute_balance(wallet_address, transactions):\n",
    "    \"\"\"\n",
    "    Given an address and a list of transactions, computes the wallet balance of the address\n",
    "    \"\"\"\n",
    "    balance = 0\n",
    "    for t in transactions:\n",
    "        # Subtract all the money that the address sent out\n",
    "        for txin in t.inputs:\n",
    "            if txin.parent_output.recipient == wallet_address:\n",
    "                balance -= txin.parent_output.amount\n",
    "        # Add all the money received by the address\n",
    "        for txout in t.outputs:\n",
    "            if txout.recipient == wallet_address:\n",
    "                balance += txout.amount\n",
    "    return balance\n",
    "\n",
    "print(\"Alice  has %.02f dumbcoins\" % compute_balance(alice.address, transactions))\n",
    "print(\"Bob    has %.02f dumbcoins\" % compute_balance(bob.address, transactions))\n",
    "print(\"Walter has %.02f dumbcoins\" % compute_balance(walter.address, transactions))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We also want to be able to verify that a transaction is valid. This means :\n",
    "\n",
    "- You can only spend your money. This means checking that all inputs are owned by the transaction's owner\n",
    "- Ensure you don't spend more than you have. This is checked by the compute_fee function above"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 63,
   "metadata": {},
   "outputs": [],
   "source": [
    "def verify_transaction(transaction):\n",
    "    \"\"\"\n",
    "    Verify that the transaction is valid.\n",
    "    We need to verify two things :\n",
    "    - That all of the inputs of the transaction belong to the same wallet\n",
    "    - That the transaction is signed by the owner of said wallet\n",
    "    \"\"\"\n",
    "    tx_message = json.dumps(transaction.to_dict(include_signature=False))\n",
    "    if isinstance(transaction, GenesisTransaction):\n",
    "        # TODO: We should probably be more careful about validating genesis transactions\n",
    "        return True\n",
    "    \n",
    "    # Verify input transactions\n",
    "    for tx in transaction.inputs:\n",
    "        if not verify_transaction(tx.transaction):\n",
    "            logging.error(\"Invalid parent transaction\")\n",
    "            return False\n",
    "    \n",
    "    first_input_address = transaction.inputs[0].parent_output.recipient\n",
    "    for txin in transaction.inputs[1:]:\n",
    "        if txin.parent_output.recipient != first_input_address:\n",
    "            logging.error(\n",
    "                \"Transaction inputs belong to multiple wallets (%s and %s)\" %\n",
    "                (txin.parent_output.recipient, first_input_address)\n",
    "            )\n",
    "            return False\n",
    "    \n",
    "    if not verify_signature(first_input_address, tx_message, transaction.signature):\n",
    "        logging.error(\"Invalid transaction signature, trying to spend someone else's money ?\")\n",
    "        return False\n",
    "    \n",
    "    return True\n",
    "\n",
    "\n",
    "t1 = GenesisTransaction(alice.address)\n",
    "# This is an invalid transaction because bob is trying to spend alice's money\n",
    "# (alice was the recipient of the input - t1)\n",
    "t2 = Transaction(\n",
    "    bob,\n",
    "    [TransactionInput(t1, 0)],\n",
    "    [TransactionOutput(walter.address, 10.0)]\n",
    ")\n",
    "# This is valid, alice is spending her own money\n",
    "t3 = Transaction(\n",
    "    alice,\n",
    "    [TransactionInput(t1, 0)],\n",
    "    [TransactionOutput(walter.address, 10.0)]\n",
    ")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 64,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "assert verify_transaction(t1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 65,
   "metadata": {},
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "ERROR:root:Invalid transaction signature, trying to spend someone else's money ?\n"
     ]
    }
   ],
   "source": [
    "assert not verify_transaction(t2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 66,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "assert verify_transaction(t3)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Putting transactions in blocks <a name=\"block\"></a>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now that we have :\n",
    "\n",
    "- A way to define a wallet (as a private/public key pair)\n",
    "- A way to create transactions between wallets\n",
    "- A way to verify transactions (by checking the signature matches\n",
    "\n",
    "What remains is to group transactions into blocks and have miners mine blocks. Mining a block consists of two parts :\n",
    "- Verifying the transactions in the block\n",
    "- Finding a nonce such that the block's hash starts with a number of 0\n",
    "\n",
    "Also, mining generates money by the convention that the first transaction in a block is a GenesisTransaction that gives 25 coins to whatever address the miner chose.\n",
    "In the same way, the miner can add transactions to redirect the fees from the transactions in the block to whatever address it chooses."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 96,
   "metadata": {},
   "outputs": [],
   "source": [
    "BLOCK_INCENTIVE = 25 # The number of coins miners get for mining a block\n",
    "DIFFICULTY = 2\n",
    "\n",
    "\n",
    "def compute_total_fee(transactions):\n",
    "    \"\"\"Return the total fee for the set of transactions\"\"\"\n",
    "    return sum(t.fee for t in transactions)\n",
    "\n",
    "\n",
    "class Block(object):\n",
    "    def __init__(self, transactions, ancestor, miner_address, skip_verif=False):\n",
    "        \"\"\"\n",
    "        Args:\n",
    "            transactions: The list of transactions to include in the block\n",
    "            ancestor: The previous block\n",
    "            miner_address: The address of the miner's wallet. This is where the block\n",
    "                           incentive and the transactions fees will be deposited\n",
    "        \"\"\"\n",
    "        reward = compute_total_fee(transactions) + BLOCK_INCENTIVE\n",
    "        self.transactions = [GenesisTransaction(miner_address, amount=reward)] + transactions\n",
    "        self.ancestor = ancestor\n",
    "        \n",
    "        if not skip_verif:\n",
    "            assert all(map(verify_transaction, transactions))\n",
    "        \n",
    "        json_block = json.dumps(self.to_dict(include_hash=False))\n",
    "        self.nonce, _ = mine(json_block, DIFFICULTY)\n",
    "        self.hash = dumb_hash(json_block + self.nonce)\n",
    "        \n",
    "    def fee(self):\n",
    "        \"\"\"Return transaction fee for this block\"\"\"\n",
    "        return compute_total_fee(self.transactions)\n",
    "    \n",
    "    def to_dict(self, include_hash=True):\n",
    "        d = {\n",
    "            \"transactions\": list(map(Transaction.to_dict, self.transactions)),\n",
    "            \"previous_block\": self.ancestor.hash,\n",
    "        }\n",
    "        if include_hash:\n",
    "            d[\"nonce\"] = self.nonce\n",
    "            d[\"hash\"] = self.hash\n",
    "        return d\n",
    "    \n",
    "    \n",
    "class GenesisBlock(Block):\n",
    "    \"\"\"\n",
    "    The genesis block is the first block in the chain.\n",
    "    It is the only block with no ancestor\n",
    "    \"\"\"\n",
    "    def __init__(self, miner_address):\n",
    "        super(GenesisBlock, self).__init__(transactions=[], ancestor=None, miner_address=miner_address)\n",
    "\n",
    "    def to_dict(self, include_hash=True):\n",
    "        d = {\n",
    "            \"transactions\": [],\n",
    "            \"genesis_block\": True,\n",
    "        }\n",
    "        if include_hash:\n",
    "            d[\"nonce\"] = self.nonce\n",
    "            d[\"hash\"] = self.hash\n",
    "        return d"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Similarly to how we verify transactions, we also need a way to verify blocks :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 129,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def verify_block(block, genesis_block):\n",
    "    \"\"\"\n",
    "    Verifies that a block is valid :\n",
    "    - Verifies the hash starts with the required amount of zeroes\n",
    "    - Verifies all transactions are valid\n",
    "    - Verifies the first transaction in the block is a genesis transaction with BLOCK_INCENTIVE + total_fee\n",
    "    \n",
    "    Args:\n",
    "        block: The block to validate\n",
    "        genesis_block: The genesis block (this needs to be shared by everybody. E.g. hardcoded somewhere)\n",
    "    \"\"\"\n",
    "    # Start by verifying ancestors up to the genesis block\n",
    "    if not (block.hash == genesis_block.hash):\n",
    "        if not verify_block(block.ancestor, genesis_block):\n",
    "            logging.error(\"Failed to validate ancestor block\")\n",
    "            return False\n",
    "    \n",
    "    # Verify hash\n",
    "    prefix = '1' * DIFFICULTY\n",
    "    if not block.hash.startswith(prefix):\n",
    "        logging.error(\"Block hash (%s) doesn't start with prefix %s\" % (block.hash, prefix))\n",
    "        return False\n",
    "    if not all(map(verify_transaction, block.transactions)):\n",
    "        return False\n",
    "    \n",
    "    # Verify the first transaction is the miner's reward\n",
    "    tx0 = block.transactions[0]\n",
    "    if not isinstance(tx0, GenesisTransaction):\n",
    "        logging.error(\"Transaction 0 is not a GenesisTransaction\")\n",
    "        return False\n",
    "    if not len(tx0.outputs) == 1:\n",
    "        logging.error(\"Transactions 0 doesn't have exactly 1 output\")\n",
    "        return False\n",
    "    reward = compute_total_fee(block.transactions[1:]) + BLOCK_INCENTIVE\n",
    "    if not tx0.outputs[0].amount == reward:\n",
    "        logging.error(\"Invalid amount in transaction 0 : %d, expected %d\" % (tx0.outputs[0].amount, reward))\n",
    "        return False\n",
    "    \n",
    "    # Only the first transaction shall be a genesis\n",
    "    for i, tx in enumerate(block.transactions):\n",
    "        if i == 0:\n",
    "            if not isinstance(tx, GenesisTransaction):\n",
    "                logging.error(\"Non-genesis transaction at index 0\")\n",
    "                return False  \n",
    "        elif isinstance(tx, GenesisTransaction):\n",
    "            logging.error(\"GenesisTransaction (hash=%s) at index %d != 0\", tx.hash(), i)\n",
    "            return False\n",
    "    return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 138,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "genesis_block : 11bbd73ea6ac0985b565943ceb2fad65 with fee=0\n",
      "block1        : 1135ffa70d3459434851485fdeaecd19 with fee=0.0\n",
      "block2        : 1164019fecd6db149455950336b5e48c with fee=1.0\n"
     ]
    }
   ],
   "source": [
    "alice = Wallet()\n",
    "bob = Wallet()\n",
    "walter = Wallet()\n",
    "\n",
    "genesis_block = GenesisBlock(miner_address=alice.address)\n",
    "print(\"genesis_block : \" + genesis_block.hash + \" with fee=\" + str(genesis_block.fee()))\n",
    "\n",
    "t1 = genesis_block.transactions[0]\n",
    "t2 = Transaction(\n",
    "    alice,\n",
    "    [TransactionInput(t1, 0)],\n",
    "    [TransactionOutput(bob.address, 5.0), TransactionOutput(alice.address, 15.0), TransactionOutput(walter.address, 5.0)]\n",
    ")\n",
    "t3 = Transaction(\n",
    "    walter,\n",
    "    [TransactionInput(t2, 2)],\n",
    "    [TransactionOutput(bob.address, 5.0)])\n",
    "\n",
    "t4 = Transaction(\n",
    "    bob,\n",
    "    [TransactionInput(t2, 0), TransactionInput(t3, 0)],\n",
    "    [TransactionOutput(walter.address, 8.0), TransactionOutput(bob.address, 1.0)]\n",
    ")\n",
    "\n",
    "block1 = Block([t2], ancestor=genesis_block, miner_address=walter.address)\n",
    "print(\"block1        : \" + block1.hash + \" with fee=\" + str(block1.fee()))\n",
    "\n",
    "block2 = Block([t3, t4], ancestor=block1, miner_address=walter.address)\n",
    "print(\"block2        : \" + block2.hash + \" with fee=\" + str(block2.fee()))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 140,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 140,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "verify_block(block1, genesis_block)\n",
    "verify_block(block2, genesis_block)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 141,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Alice  has 15.00 dumbcoins\n",
      "Bob    has 1.00 dumbcoins\n",
      "Walter has 59.00 dumbcoins\n"
     ]
    }
   ],
   "source": [
    "def collect_transactions(block, genesis_block):\n",
    "    \"\"\"Recursively collect transactions in `block` and all of its ancestors\"\"\"\n",
    "    # Important : COPY block.transactions\n",
    "    transactions = [] + block.transactions\n",
    "    if block.hash != genesis_block.hash:\n",
    "        transactions += collect_transactions(block.ancestor, genesis_block)\n",
    "    return transactions\n",
    "\n",
    "transactions = collect_transactions(block2, genesis_block)\n",
    "\n",
    "# Alice mined 25 (from the genesis block) and gave 5 to bob and 5 to walter\n",
    "print(\"Alice  has %.02f dumbcoins\" % compute_balance(alice.address, transactions))\n",
    "# Bob received 5 from alice and 5 from walter, but then back 8 to walter with a transaction fee of 1\n",
    "print(\"Bob    has %.02f dumbcoins\" % compute_balance(bob.address, transactions))\n",
    "# Walter mined 2 blocks (2 * 25), received 8 from bob and go a transaction fee of 1 on block2\n",
    "print(\"Walter has %.02f dumbcoins\" % compute_balance(walter.address, transactions))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Some attacks <a href=\"attacks\"></a>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now, if our miner (walter) tries to spend bob's money, his block won't verify :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 142,
   "metadata": {},
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "ERROR:root:Invalid transaction signature, trying to spend someone else's money ?\n"
     ]
    }
   ],
   "source": [
    "tx = Transaction(\n",
    "    walter,\n",
    "    [TransactionInput(t4, 1)],\n",
    "    [TransactionOutput(walter.address, 1.0)],\n",
    ")\n",
    "\n",
    "# Note that we have to use skip_verif=True to not trigger the assert in Block's constructor\n",
    "block3 = Block([tx], ancestor=block2, miner_address=walter.address, skip_verif=True)\n",
    "assert not verify_block(block3, genesis_block)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Another possible attack would be for the miner to modify a transaction it include in its block. Again, this won't work"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 144,
   "metadata": {},
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "ERROR:root:Invalid transaction signature, trying to spend someone else's money ?\n"
     ]
    }
   ],
   "source": [
    "# This is a transaction signed by bob\n",
    "tx = Transaction(\n",
    "    bob,\n",
    "    [TransactionInput(t2, 0), TransactionInput(t3, 0)],\n",
    "    [TransactionOutput(walter.address, 8.0), TransactionOutput(bob.address, 1.0)]\n",
    ")\n",
    "# And modified by the miner\n",
    "tx.outputs[0].amount += 4\n",
    "block2 = Block([t3, tx], ancestor=block1, miner_address=walter.address, skip_verif=True)\n",
    "assert not verify_block(block2, genesis_block)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "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.6.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}