17_Blockchain.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. \n",
    "\n",
    "You might want to have a look at the [hacker news](https://news.ycombinator.com/item?id=15945490) discussion about this notebook."
   ]
  },
  {
   "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",
    "\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](#attacks)\n",
    "7. [Majority attack](#majority_attack)\n",
    "8. [Differences with Bitcoin](#differences)"
   ]
  },
  {
   "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": 11,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Requirement already satisfied: pycrypto in /Library/Frameworks/Python.framework/Versions/3.6/lib/python3.6/site-packages (2.6.1)\r\n"
     ]
    }
   ],
   "source": [
    "! pip3 install pycrypto"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "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 SHA256 hash function because it's readily implemented in python. Note that bitcoin uses [two round of SHA256](https://en.bitcoin.it/wiki/Hashcash) instead of one.\n",
    "\n",
    "So our hash function will turn a string of arbitrary length into a fixed-length string of 64 hexadecimal characters. For example :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def sha256(message):\n",
    "    return hashlib.sha256(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": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Found nonce = 32\n",
      "112c38d2fdb6ddaf32f371a390307ccc779cd92443b42c4b5c58fa548f63ed83\n"
     ]
    }
   ],
   "source": [
    "message = 'hello bitcoin'\n",
    "for nonce in range(1000):\n",
    "    digest = sha256(message + str(nonce))\n",
    "    if digest.startswith('11'):\n",
    "        print('Found nonce = %d' % nonce)\n",
    "        break\n",
    "print(sha256(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": 4,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def dumb_hash(message):\n",
    "    \"\"\"\n",
    "    Returns an hexadecimal hash\n",
    "    \"\"\"\n",
    "    return sha256(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": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Took 23 iterations\n",
      "Took 2272 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": 6,
   "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": 7,
   "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": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: right;\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>63140B8TKI</th>\n",
       "      <td>29.0</td>\n",
       "      <td>690.0</td>\n",
       "      <td>13393.0</td>\n",
       "      <td>85887.0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>QXLX0YZGB8</th>\n",
       "      <td>11.0</td>\n",
       "      <td>11.0</td>\n",
       "      <td>207.0</td>\n",
       "      <td>50068.0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>YI92OBKVGF</th>\n",
       "      <td>3.0</td>\n",
       "      <td>196.0</td>\n",
       "      <td>4868.0</td>\n",
       "      <td>23737.0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>6KAA4TGFXE</th>\n",
       "      <td>5.0</td>\n",
       "      <td>735.0</td>\n",
       "      <td>2450.0</td>\n",
       "      <td>154519.0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>ZX3Q2L0645</th>\n",
       "      <td>85.0</td>\n",
       "      <td>197.0</td>\n",
       "      <td>4896.0</td>\n",
       "      <td>14282.0</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "               1      2        3         4\n",
       "63140B8TKI  29.0  690.0  13393.0   85887.0\n",
       "QXLX0YZGB8  11.0   11.0    207.0   50068.0\n",
       "YI92OBKVGF   3.0  196.0   4868.0   23737.0\n",
       "6KAA4TGFXE   5.0  735.0   2450.0  154519.0\n",
       "ZX3Q2L0645  85.0  197.0   4896.0   14282.0"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "results.iloc[:5]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Text(0,0.5,'Iterations')"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAnoAAAFNCAYAAACXPcKEAAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAADl0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uIDIuMi4yLCBo\ndHRwOi8vbWF0cGxvdGxpYi5vcmcvhp/UCwAAIABJREFUeJzt3XuYXXV59//3xwQVFTlIyoOEEKqp\nilijRKTV9ueDiqA+gk9RwSpRUfQptva5bGvQnwUPtNhWrf5qUVQKeAAUqlCkRbQol62IqBE5aIkY\nSiIChqMKKHj//ljfkZ1xZjLJHPZkzft1Xeuate91+N5r7TV73/Ndh0lVIUmSpP55wLATkCRJ0syw\n0JMkSeopCz1JkqSestCTJEnqKQs9SZKknrLQkyRJ6ikLPWkcSU5J8s4htZ0k/5Tk1iSXjjH9D5N8\nfhi5DeTwwSRvHWYOMynJm5N8ZNh5zHVJtk3yL0luT/LpYecz2lw4TpOsTfKsNr7RcZXkhUmuT/KT\nJE9K8pgkq5PcmeRPpiP/JEuTVJKFU90WbX1807XVSLIWeAiwZ1X9tMVeDbysqp4xxNRmwtOBZwOL\nR7Z1UFV9AvjEyOskBSyrqjUzkUySVwCvrqqnD+Twuploa4IclgI/ALapqntnur2q+quZbqMnDgV2\nAR4xG+/L5prt43RTxjiu/g54fVWdA5Dko8BFVbV8pnJI8iXg41XlHzLzgD162tosAN4w7CQ2V5IF\nm7nIHsDasYq86eZf+ZqiPYD/2pIib6aPvS34vRuGPYArJ3gtTU1VOThsFQOwFlgF3ALs0GKvBr7U\nxpcCBSwcWOZLdD1RAK8A/gN4L3AbcC3wuy1+PXATsHJg2VOADwIXAncCXwb2GJj+2DbtFuB7wItH\nLXsicD7wU+BZY2zPI4Fz2/JrgNe0+JHA3cB9wE+At42x7CuAr7Txi9t2/7TN/5IWfz6wum3rfwK/\nPWpfvgm4HLiHrnd/FfD9tq1XAS9s8z5uVD63DWzjOwfW+Zq2Hbe07XrkwLQCXgdc0/L5AJA27dFt\n394O/Bg4c5z3/7/ben7Sht+h+2P1/wWua+/facD24yz/DGAd8Bdt3huAQ4DnAv/V8n7zwPzH0fV6\nwP3H1sqWx4+BtwzM+4CB/bcB+BSw0zh57AicB9wM3NrGF2/iuP+z9l7dDpwJPHiq+31g2asH3vMn\nDxybZ7ccfwD8yTi5vQ34OfCL9p4cOdF7MrAfj2z78eIx1nk18PyB1wtbHiO5fRr4UdsXFwOPn+j3\njkkep2z682NSx2mb9+Vt+zcAb2nv4bMGjyvgQW2fjfzufh/4d7rfs7vbtN8aI/+D6X6v72jLHDhw\nnDxrYL7j+PXjdyFw/Kg2/qEdF+8etQ3nAv93Nj7bHWZ2GHoCDg6THUY+yIB/HvngY/MLvXuBV9L1\nDL6zfdl8oH3oHkD3hfewNv8p7fXvt+nv4/7i6qF0xeEr24fnk9qH/14Dy94OPI3ui+/BY2zPxcA/\nAg8GltN9me0/kOtXJtgXG01v2/3ogddPovuSfWrb1pVt/z1oYF+uBnYHtm2xF9F9wT8AeAndl8+u\n4+XDwBcQsH/b/ie3ffX/MfAl3vI7D9gBWNK2deQL6nS6L8MHtH3x9HG2eaz391V0X9q/CTysHRsf\nG2f5Z7T3/y+Bbei+8G8GPglsBzweuIvu0gAY+4vyw8C2wBPpCuTHtelvAC4BFrft/xBw+jh5PAL4\nA7rLELajK1w+u4nj/tL23uxEVwi9bhr2+4uA9cBTgNAVMnu09+EbbT89sO3ba4HnjJPfr/bTpt6T\ngf14Gt3v0LZjrO8vgU8MvH4ecPWo9W/XtvfvgdWjjsmNfu+Y5HHKpj8/Jnuc7kVXQI18bryH7rh7\n1jj7a/Tv7q/aHOP3bN+2fc9ueewGPHbw83Gs92X0to3Rxr7AD4EHtNc7Az8DdpmJz3KH2R08daut\n0V8Cf5xk0RYs+4Oq+qequo+uZ2R34O1VdU9VfZ6ud+LRA/N/rqourqp76D7kfyfJ7nS9ZWvbuu6t\nqm/R9YC8aGDZc6rqP6rql1V192ASbR1PA95UVXdX1WrgI8ARW7BNYzkK+FBVfa2q7quqU+kKk/0G\n5nl/VV1fVXcBVNWnq+qHLd8z6XqB9p1ke38InFxV32z76hi6fbV0YJ4Tquq2qvpv4CK64ha63qA9\n6HpW7q6qr2zGdv4h8J6quraqftLaPWyCU4K/AI6vql8AZ9B9ob2vqu6sqivperWeOEF7b6uqu6rq\n28C3B+Z9HV0P37q2/ccBh46VR1VtqKqzq+pnVXUnXQ/L/7OJ7Xx/e29uAf6F+/fdVPb7q4G/qaqv\nV2dNVV1HV/gtqqq3V9XPq+paugL3sE3kOGIy78lxVfXTkWNvlE8CL0jykPb6pXRFFgBVdXJ7v0b2\n8xOTbD+w/Li/d0xuf41nssfpocB5A58bbwV+OYn1T8aRdPlf2LZvfVV9d6orrapL6QrIZ7bQYXR/\nQN841XVr+Cz0tNWpqivoeilWbcHigx9cIwXO6NjDBl5fP9DuT+hO9zyS7gP/qUluGxnovkT+x1jL\njuGRwC3ti37EdXR/oU+HPYA3jspv99bumPklOaLd7Tcy/950hdBkPJIuf+BX+2oDG2/PjwbGf8b9\n+/kv6HqULk1yZZJXTbLNX2u3jS+kuzlgLBtakQ/t/efXj4mHMb7xtmEP4DMD++5qutNjv5ZHkock\n+VCS65LcQdezu8Mmricbr92p7Pfd6U79jbYH8MhRx86bx9qWcUzmPRn3d6O6G4quBv5XK/ZeQFf8\nkWRBkhOSfL/tu7VtscHjdFO/d5vaX+OZ7HH6SDb+3Phpa2M6jPeeTYdTgZe18ZcBH5uhdjTLvAhb\nW6tjgW8C7x6Ijdy48BC661dg48JrS+w+MpLkYXSnzn5I90H+5ap69gTL1gTTfgjslGS7gWJvCd2p\ntOlwPV3P1fGTyS/JHnS9Ns8EvlpV9yVZTffFttG84/ghXYEwsr6H0p2i3OT2VNWP6E6jkuTpwBeS\nXFy/fgfxWDls1C7dPryXjYu32XA98Kqq+o9JzPtG4DHAU6vqR0mWA9/i/n29ObZ4v9Pl/Khx4j+o\nqmVbkM+v5cTG78niFtvU8XQ6cDhdZ8RVA8fCS+muUXsWXZG3Pd11joP7blO/d+Ptrwk/PzbjOL2B\n7rrWkTYe0tqYDuO9Z9Dl/5CB1xN99o21jz4OXJHkiXT5f3aLMtScY4+etkrtw/VM4E8GYjfTfWC/\nrP3l/yrG/1CcrOcmeXqSBwLvAC6pquvpehR/K8nLk2zThqckedzEq/tVrtfT3SDx10kenOS36U7L\nfHwL87yR7pqoER8GXpfkqe2ZfA9N8rwk242z/EPpPvxvBkjySroevcH1L277YSynA69MsjzJg4C/\nAr5WVWs3lXiSFyUZKQBubXmMdarr5hYf3M7Tgf+bZM9WiP8V3UXys/2Yjw8Cx7eCmSSLkhw8zrzb\n0fUc3pZkJ7o/WrbUFu93uksF/izJPu0YeXTL/1LgziRvSveMvAVJ9k7ylM3IaarvyRl018z+H1pv\nXrMd3SUIG+iKms19BM64+2tTnx+bcZyeBTx/4HPj7Uzfd+1HW/7PTPKAJLsleWybtpruFPk2SVbQ\nnUIez+jPC6pqHfB1up68s8c5ra6tkIWetmZvpytQBr0G+HO6L4LH0xVTU/FJui/iW4B9aKc2Wi/c\nAXTXsvyQ7vTYu+guvp6sw+kukv4h8Bng2Kr6whbmeRxwajvV9uKquoxuX/wD3ZfSGrobKsZUVVfR\n9Y5+le5L4Al0dyiP+He6Rz78KMmPx1j+C3TXIp1N16PxKCZ/TddTgK8l+QndnX5vaNeFjW7jZ3TX\ns/1H2879gJPpvpguprs79G7gjyfZ7nR6H13un09yJ92NGU8dZ96/p7uh48dtvn/b0kanst+r6tN0\n+/OTdDcdfZbuTuH76K5BXU63T39MVxRuP86qRpvye1JVN9Adi79L9wfdiNPoTr2up7ue8pLNXO+m\n9tdEnx+TPU6vBI6m26830P3+rducPCfI/1K6G8DeS3dN3Ze5v4fyrW17bqW7G/qTY62jeR/dNaS3\nJnn/QPxUut99T9v2yMjjDSRJ0jyW5PfpzirsURYHvWGPniRJ81ySbegeE/QRi7x+sdCTJGkea9cW\n3wbsSndpgXrEU7eSJEk9ZY+eJElST1noSZIk9ZQPTG523nnnWrp06bDTkCRJ2qRvfOMbP66qTf4r\nUAu9ZunSpVx22WXDTkOSJGmTkly36bk8dStJktRbFnqSJEk9ZaEnSZLUUxZ6kiRJPWWhJ0mS1FMW\nepIkST1loSdJktRTFnqSJEk9ZaEnSZLUUxZ6kiRJPeW/QJMkSTMqyVDbr6qhtj9M9uhJkqQZVVVb\nPOzxpvOmtPx8LvLAQk+SJKm3LPQkSZJ6ykJPkiSppyz0JEmSespCT5IkqadmrNBLcnKSm5JcMRA7\nM8nqNqxNsrrFlya5a2DaBweW2SfJd5KsSfL+tHu0k+yU5MIk17SfO7Z42nxrklye5MkztY2SJElz\n2Uz26J0CHDgYqKqXVNXyqloOnA3888Dk749Mq6rXDcRPBF4DLGvDyDpXAV+sqmXAF9trgIMG5j2q\nLS9JkjTvzFihV1UXA7eMNa31yr0YOH2idSTZFXh4VV1S3YNwTgMOaZMPBk5t46eOip9WnUuAHdp6\nJEmS5pVhXaP3e8CNVXXNQGzPJN9K8uUkv9diuwHrBuZZ12IAu1TVDW38R8AuA8tcP84ykiRJ88aw\n/gXa4Wzcm3cDsKSqNiTZB/hsksdPdmVVVUk2+9HXSY6iO73LkiVLNndxSZKkOW3We/SSLAT+N3Dm\nSKyq7qmqDW38G8D3gd8C1gOLBxZf3GIAN46ckm0/b2rx9cDu4yyzkao6qapWVNWKRYsWTXXTJEmS\n5pRhnLp9FvDdqvrVKdkki5IsaOO/SXcjxbXt1OwdSfZr1/UdAZzTFjsXWNnGV46KH9Huvt0PuH3g\nFK8kSdK8MZOPVzkd+CrwmCTrkhzZJh3Gr9+E8fvA5e1xK2cBr6uqkRs5/gj4CLCGrqfvX1v8BODZ\nSa6hKx5PaPHzgWvb/B9uy0uSJM07M3aNXlUdPk78FWPEzqZ73MpY818G7D1GfAPwzDHiBRy9melK\nkiT1jv8ZQ5Ikqacs9CRJknrKQk+SJKmnLPQkSZJ6ykJPkiSppyz0JEmSespCT5Ikqacs9CRJknrK\nQk+SJKmnLPQkSZJ6ykJPkiSppyz0JEmSespCT5Ikqacs9CRJknrKQk+SJKmnLPQkSZJ6ykJPkiSp\npyz0JEmSespCT5Ikqacs9CRJknrKQk+SJKmnLPQkSZJ6ykJPkiSppyz0JEmSespCT5IkqadmrNBL\ncnKSm5JcMRA7Lsn6JKvb8NyBacckWZPke0meMxA/sMXWJFk1EN8zydda/MwkD2zxB7XXa9r0pTO1\njZIkSXPZTPbonQIcOEb8vVW1vA3nAyTZCzgMeHxb5h+TLEiyAPgAcBCwF3B4mxfgXW1djwZuBY5s\n8SOBW1v8vW0+SZKkeWfGCr2quhi4ZZKzHwycUVX3VNUPgDXAvm1YU1XXVtXPgTOAg5ME2B84qy1/\nKnDIwLpObeNnAc9s80uSJM0rw7hG7/VJLm+ndndssd2A6wfmWddi48UfAdxWVfeOim+0rjb99jb/\nr0lyVJLLklx28803T33LJEmS5pDZLvROBB4FLAduAN49y+1vpKpOqqoVVbVi0aJFw0xFkiRp2s1q\noVdVN1bVfVX1S+DDdKdmAdYDuw/MurjFxotvAHZIsnBUfKN1tenbt/klSZLmlVkt9JLsOvDyhcDI\nHbnnAoe1O2b3BJYBlwJfB5a1O2wfSHfDxrlVVcBFwKFt+ZXAOQPrWtnGDwX+vc0vSZI0ryzc9Cxb\nJsnpwDOAnZOsA44FnpFkOVDAWuC1AFV1ZZJPAVcB9wJHV9V9bT2vBy4AFgAnV9WVrYk3AWckeSfw\nLeCjLf5R4GNJ1tDdDHLYTG2jJEnSXDZjhV5VHT5G+KNjxEbmPx44foz4+cD5Y8Sv5f5Tv4Pxu4EX\nbVaykiRJPeR/xpAkSeopCz1JkqSestCTJEnqKQs9SZKknrLQkyRJ6ikLPUmSpJ6y0JMkSeopCz1J\nkqSestCTJEnqKQs9SZKknrLQkyRJ6ikLPUmSpJ6y0JMkSeopCz1JkqSestCTJEnqKQs9SZKknrLQ\nkyRJ6ikLPUmSpJ6y0JMkSeopCz1JkqSestCTJEnqKQs9SZKknrLQkyRJ6ikLPUmSpJ6asUIvyclJ\nbkpyxUDsb5N8N8nlST6TZIcWX5rkriSr2/DBgWX2SfKdJGuSvD9JWnynJBcmuab93LHF0+Zb09p5\n8kxtoyRJ0lw2kz16pwAHjopdCOxdVb8N/BdwzMC071fV8ja8biB+IvAaYFkbRta5CvhiVS0Dvthe\nAxw0MO9RbXlJkqR5Z8YKvaq6GLhlVOzzVXVve3kJsHiidSTZFXh4VV1SVQWcBhzSJh8MnNrGTx0V\nP606lwA7tPVIkiTNK8O8Ru9VwL8OvN4zybeSfDnJ77XYbsC6gXnWtRjALlV1Qxv/EbDLwDLXj7OM\nJEnSvLFwGI0meQtwL/CJFroBWFJVG5LsA3w2yeMnu76qqiS1BXkcRXd6lyVLlmzu4pIkSXParPfo\nJXkF8HzgD9vpWKrqnqra0Ma/AXwf+C1gPRuf3l3cYgA3jpySbT9vavH1wO7jLLORqjqpqlZU1YpF\nixZNw9ZJkiTNHbNa6CU5EPgL4AVV9bOB+KIkC9r4b9LdSHFtOzV7R5L92t22RwDntMXOBVa28ZWj\n4ke0u2/3A24fOMUrSZI0b8zYqdskpwPPAHZOsg44lu4u2wcBF7anpFzS7rD9feDtSX4B/BJ4XVWN\n3MjxR3R38G5Ld03fyHV9JwCfSnIkcB3w4hY/H3gusAb4GfDKmdpGSZKkuWzGCr2qOnyM8EfHmfds\n4Oxxpl0G7D1GfAPwzDHiBRy9WclKkiT1kP8ZQ5Ikqacs9CRJknrKQk+SJKmnLPQkSZJ6ykJPkiSp\npyz0JEmSespCT5Ikqacs9CRJknrKQk+SJKmnLPQkSZJ6ykJPkiSppyz0JEmSespCT5Ikqacs9CRJ\nknrKQk+SJKmnFg47AUmSNLc98W2f5/a7fjG09peu+tzQ2t5+22349rEHDK39qbLQkyRJE7r9rl+w\n9oTnDTuNoRhmkTkdPHUrSZLUUxZ6kiRJPWWhJ0mS1FOTKvSS/E2ShyfZJskXk9yc5GUznZwkSZK2\n3GR79A6oqjuA5wNrgUcDfz5TSUmSJGnqJlvojdyd+zzg01V1+wzlI0mSpGky2cernJfku8BdwP9J\nsgi4e+bSkiRJ0lRNqkevqlYBvwusqKpfAD8FDp7JxCRJkjQ1m3PX7WOBlyQ5AjgU2ORjopOcnOSm\nJFcMxHZKcmGSa9rPHVs8Sd6fZE2Sy5M8eWCZlW3+a5KsHIjvk+Q7bZn3J8lEbUiSJM0nk73r9mPA\n3wFPB57ShhWTWPQU4MBRsVXAF6tqGfDF9hrgIGBZG44CTmxt7wQcCzwV2Bc4dqBwOxF4zcByB26i\nDUmSpHljstforQD2qqranJVX1cVJlo4KHww8o42fCnwJeFOLn9bauCTJDkl2bfNeWFW3ACS5EDgw\nyZeAh1fVJS1+GnAI8K8TtCFJkjRvTPbU7RXA/5imNnepqhva+I+AXdr4bsD1A/Ota7GJ4uvGiE/U\nhiRJ0rwx2R69nYGrklwK3DMSrKoXTKXxqqokm9VLOJ1tJDmK7jQxS5Ysmck0JEmSZt1kC73jprHN\nG5PsWlU3tFOzN7X4emD3gfkWt9h67j8NOxL/UosvHmP+idrYSFWdBJwEsGLFihktOCVJkmbbZB+v\n8mXgu8B2bbi6xbbEucDInbMrgXMG4ke0u2/3A25vp18vAA5IsmO7CeMA4II27Y4k+7W7bY8Yta6x\n2pAkSZo3JnvX7YuBS4EXAS8Gvpbk0EksdzrwVeAxSdYlORI4AXh2kmuAZ7XXAOcD1wJrgA8DfwTQ\nbsJ4B/D1Nrx95MaMNs9H2jLfp7sRgwnakCRJmjcme+r2LcBTquomgPafMb4AnDXRQlV1+DiTnjnG\nvAUcPc56TgZOHiN+GbD3GPENY7UhSZI0n0z2rtsHjBR5zYbNWFaSJElDMNkevX9LcgFwenv9ErpT\nrZIkSZqjJlXoVdWfJ/kD4GktdFJVfWbm0pIkSdJUTbZHj6o6Gzh7BnORJEnSNJqw0Evylap6epI7\ngcHnzIXu/omHz2h2kiRJ2mITFnpV9fT2c7vZSUeSJEnTZbLP0fvYZGKSJEmaOyb7iJTHD75IshDY\nZ/rTkSRJ0nSZsNBLcky7Pu+3k9zRhjuBG/HfikmSJM1pExZ6VfXX7fq8v62qh7dhu6p6RFUdM0s5\nSpIkaQtM9jl6xyTZEVgGPHggfvFMJSZJkqSpmVShl+TVwBuAxcBqYD/gq8D+M5eaJEmSpmKyN2O8\nAXgKcF1V/U/gScBtM5aVJEmSpmyyhd7dVXU3QJIHVdV3gcfMXFqSJEmaqsn+C7R1SXYAPgtcmORW\n4LqZS0uSJElTNdmbMV7YRo9LchGwPfBvM5aVJEmSpmyThV6SBcCVVfVYgKr68oxnJUmSpCnb5DV6\nVXUf8L0kS2YhH0mSJE2TyV6jtyNwZZJLgZ+OBKvqBTOSlSRJkqZssoXeW2c0C0mSJE27yd6M8eUk\newDLquoLSR4CLJjZ1CRJkjQVk3qOXpLXAGcBH2qh3egetSJJkqQ5arIPTD4aeBpwB0BVXQP8xkwl\nJUmSpKmbbKF3T1X9fORFkoVAzUxKkiRJmg6TLfS+nOTNwLZJng18GviXmUtLkiRJUzXZQm8VcDPw\nHeC1wPlV9ZYtaTDJY5KsHhjuSPKnSY5Lsn4g/tyBZY5JsibJ95I8ZyB+YIutSbJqIL5nkq+1+JlJ\nHrgluUqSJG3NJlvo/XFVfbiqXlRVh1bVh5O8YUsarKrvVdXyqloO7AP8DPhMm/zekWlVdT5Akr2A\nw4DHAwcC/5hkQfuPHR8ADgL2Ag5v8wK8q63r0cCtwJFbkqskSdLWbLKF3soxYq+YhvafCXy/qq6b\nYJ6DgTOq6p6q+gGwBti3DWuq6tp2/eAZwMFJAuxPd5cwwKnAIdOQqyRJ0lZlwufoJTkceCmwZ5Jz\nByZtB9wyDe0fBpw+8Pr1SY4ALgPeWFW30j3K5ZKBeda1GMD1o+JPBR4B3FZV944xvyRJ0ryxqQcm\n/ydwA7Az8O6B+J3A5VNpuF039wLgmBY6EXgH3d2872jtvWoqbUwih6OAowCWLPFf+UqSpH6ZsNBr\np1SvA35nBto+CPhmVd3Y2rpxZEKSDwPntZfrgd0HllvcYowT3wDskGRh69UbnH8jVXUScBLAihUr\nfFyMJEnqlQmv0UtyZ7srdvRwZ5I7ptj24Qyctk2y68C0FwJXtPFzgcOSPCjJnsAy4FLg68Cydoft\nA+lOA59bVQVcBBzall8JnDPFXCVJkrY6m+rR224mGk3yUODZdI9qGfE3SZbTnbpdOzKtqq5M8ing\nKuBe4Oiquq+t5/XABXT/d/fkqrqyretNwBlJ3gl8C/joTGyHJEnSXLapa/RmRFX9lO6micHYyyeY\n/3jg+DHi5wPnjxG/lu6uXEmSpHlrso9XkSRJ0lbGQk+SJKmnLPQkSZJ6ykJPkiSppyz0JEmSespC\nT5Ikqacs9CRJknrKQk+SJKmnLPQkSZJ6ykJPkiSppyz0JEmSespCT5Ikqacs9CRJknpq4bATkCRJ\nc9t2j1vFE05dNew0hmK7xwE8b9hpbDELPUmSNKE7rz6BtSdsvcXOVCxd9blhpzAlnrqVJEnqKQs9\nSZKknrLQkyRJ6ikLPUmSpJ6y0JMkSeopCz1JkqSestCTJEnqKQs9SZKknrLQkyRJ6ikLPUmSpJ4a\nWqGXZG2S7yRZneSyFtspyYVJrmk/d2zxJHl/kjVJLk/y5IH1rGzzX5Nk5UB8n7b+NW3ZzP5WSpIk\nDc+we/T+Z1Utr6oV7fUq4ItVtQz4YnsNcBCwrA1HASdCVxgCxwJPBfYFjh0pDts8rxlY7sCZ3xxJ\nkqS5Y9iF3mgHA6e28VOBQwbip1XnEmCHJLsCzwEurKpbqupW4ELgwDbt4VV1SVUVcNrAuiRJkuaF\nYRZ6BXw+yTeSHNViu1TVDW38R8AubXw34PqBZde12ETxdWPEJUmS5o2FQ2z76VW1PslvABcm+e7g\nxKqqJDWTCbQC8yiAJUuWzGRTkiRJs25oPXpVtb79vAn4DN01dje20660nze12dcDuw8svrjFJoov\nHiM+OoeTqmpFVa1YtGjRdGyWJEnSnDGUQi/JQ5NsNzIOHABcAZwLjNw5uxI4p42fCxzR7r7dD7i9\nneK9ADggyY7tJowDgAvatDuS7Nfutj1iYF2SJEnzwrBO3e4CfKY98WQh8Mmq+rckXwc+leRI4Drg\nxW3+84HnAmuAnwGvBKiqW5K8A/h6m+/tVXVLG/8j4BRgW+Bf2yBJkjRvDKXQq6prgSeOEd8APHOM\neAFHj7Ouk4GTx4hfBuw95WQlSZK2UnPt8SqSJEmaJhZ6kiRJPWWhJ0mS1FMWepIkST1loSdJktRT\nFnqSJEk9ZaEnSZLUUxZ6kiRJPWWhJ0mS1FMWepIkST1loSdJktRTFnqSJEk9ZaEnSZLUUxZ6kiRJ\nPWWhJ0mS1FMWepIkST1loSdJktRTFnqSJEk9ZaEnSZLUUxZ6kiRJPWWhJ0mS1FMWepIkST1loSdJ\nktRTFnqSJEk9ZaEnSZLUU7Ne6CXZPclFSa5KcmWSN7T4cUnWJ1ndhucOLHNMkjVJvpfkOQPxA1ts\nTZJVA/E9k3ytxc9M8sDZ3UpJkqThG0aP3r3AG6tqL2A/4Ogke7Vp762q5W04H6BNOwx4PHAg8I9J\nFiRZAHwAOAjYCzh8YD3vaut6NHArcORsbZwkSdJcMeuFXlXdUFXfbON3AlcDu02wyMHAGVV1T1X9\nAFgD7NuGNVV1bVX9HDgDODhJgP2Bs9rypwKHzMzWSJIkzV1DvUYvyVLgScDXWuj1SS5PcnKSHVts\nN+D6gcXWtdh48UcAt1XVvaMlN3miAAAH2UlEQVTikiRJ88rQCr0kDwPOBv60qu4ATgQeBSwHbgDe\nPQs5HJXksiSX3XzzzTPdnCRJ0qxaOIxGk2xDV+R9oqr+GaCqbhyY/mHgvPZyPbD7wOKLW4xx4huA\nHZIsbL16g/NvpKpOAk4CWLFiRU1xsyRJ6q2lqz437BSGYvtttxl2ClMy64Veu4buo8DVVfWegfiu\nVXVDe/lC4Io2fi7wySTvAR4JLAMuBQIsS7InXSF3GPDSqqokFwGH0l23txI4Z+a3TJKkflp7wvOG\n1vbSVZ8bavtbu2H06D0NeDnwnSSrW+zNdHfNLgcKWAu8FqCqrkzyKeAqujt2j66q+wCSvB64AFgA\nnFxVV7b1vQk4I8k7gW/RFZaSJEnzyqwXelX1FbreuNHOn2CZ44Hjx4ifP9ZyVXUt3V25kiRJ85b/\nGUOSJKmnLPQkSZJ6ykJPkiSppyz0JEmSespCT5Ikqacs9CRJknrKQk+SJKmnLPQkSZJ6ykJPkiSp\npyz0JEmSespCT5Ikqacs9CRJknrKQk+SJKmnLPQkSZJ6ykJPkiSppxYOOwFJ0tYnybBToKqGnYI0\n59mjJ0nabFU1pWGPN5035XVI2jQLPUmSpJ6y0JMkSeopCz1JkqSestCTJEnqKQs9SZKknvLxKpI0\nDz3xbZ/n9rt+MdQclq763FDa3X7bbfj2sQcMpW1ptlnoSdI8dPtdv2DtCc8bdhpDMawCUxoGCz1J\nmoe2e9wqnnDqqmGnMRTbPQ5gfha5mn96W+glORB4H7AA+EhVnTDklCRpzrjz6hPs0ZPmgV7ejJFk\nAfAB4CBgL+DwJHsNNytJkqTZ1dcevX2BNVV1LUCSM4CDgauGmpU0xw37/5f6b61m13zt2dp+222G\nncK8M9XPlrxrau3P58+WvhZ6uwHXD7xeBzx19ExJjgKOAliyZMnsZLaZnnDqE4adwlB9Z+V3hp3C\nVmWqx8vep+w9TZlsmanm7/EyeVM9bTvsPwpgfn95b218r4anr4XepFTVScBJACtWrJiTR6FfXNoc\nHi+aLX5xS1uHXl6jB6wHdh94vbjFJEmS5o2+FnpfB5Yl2TPJA4HDgHOHnJMkSdKs6uWp26q6N8nr\ngQvoHq9yclVdOeS0JEmSZlUvCz2AqjofOH/YeUiSJA1LX0/dSpIkzXsWepIkST1loSdJktRTFnqS\nJEk9ZaEnSZLUUxZ6kiRJPWWhJ0mS1FPx/xV2ktwMXDfsPOagnYEfDzsJbRU8VrQ5PF40WR4rY9uj\nqhZtaiYLPU0oyWVVtWLYeWju81jR5vB40WR5rEyNp24lSZJ6ykJPkiSppyz0tCknDTsBbTU8VrQ5\nPF40WR4rU+A1epIkST1lj54kSVJPWehpTElOTnJTkiuGnYvmtiS7J7koyVVJrkzyhmHnpLkpyYOT\nXJrk2+1Yeduwc9Lcl2RBkm8lOW/YuWyNLPQ0nlOAA4edhLYK9wJvrKq9gP2Ao5PsNeScNDfdA+xf\nVU8ElgMHJtlvyDlp7nsDcPWwk9haWehpTFV1MXDLsPPQ3FdVN1TVN9v4nXQfyLsNNyvNRdX5SXu5\nTRu8UFzjSrIYeB7wkWHnsrWy0JM0bZIsBZ4EfG24mWiuaqfhVgM3ARdWlceKJvL3wF8Avxx2Ilsr\nCz1J0yLJw4CzgT+tqjuGnY/mpqq6r6qWA4uBfZPsPeycNDcleT5wU1V9Y9i5bM0s9CRNWZJt6Iq8\nT1TVPw87H819VXUbcBFeC6zxPQ14QZK1wBnA/kk+PtyUtj4WepKmJEmAjwJXV9V7hp2P5q4ki5Ls\n0Ma3BZ4NfHe4WWmuqqpjqmpxVS0FDgP+vapeNuS0tjoWehpTktOBrwKPSbIuyZHDzklz1tOAl9P9\ntb26Dc8ddlKak3YFLkpyOfB1umv0fGSGNIP8zxiSJEk9ZY+eJElST1noSZIk9ZSFniRJUk9Z6EmS\nJPWUhZ4kSVJPWehJEpDkvvZomCuTfDvJG5M8oE1bkeT9bfxBSb7Q5n1Jkt9ry6xOsluSs7aw/Vck\n+Yc2fkiSvaZv6yTNVwuHnYAkzRF3tX/NRZLfAD4JPBw4tqouAy5r8z0JYGDeDwJ/XVUjT+w/dBpy\nOQQ4D7hqGtYlaR6zR0+SRqmqm4CjgNen84wk57UC8OPAU1oP3muBFwPvSPKJJEuTXAGQZEGSv0ty\nRZLLk/xxi69NsnMbX5HkS4NtJ/ld4AXA37Y2HpXkmwPTlw2+lqSJ2KMnSWOoqmuTLAB+YyB2U5JX\nA39WVc8HSPI7wHlVdVaSpQOrOApYCiyvqnuT7DTJdv8zybkj62xt3J5keVWtBl4J/NPUt1DSfGCP\nniTNjGcBH6qqewGq6pYprOsjwCtb4fkSutPKkrRJFnqSNIYkvwncB9w0zau+l/s/ex88yWXOBg4C\nng98o6o2THNOknrKQk+SRkmyCPgg8A+15f8Q/ELgtUkWtnWOnLpdC+zTxv9gnGXvBLYbeVFVdwMX\nACfiaVtJm8FCT5I62448XgX4AvB54G1TWN9HgP8GLk/ybeClLf424H1JLqPrMRzLGcCfJ/lWkke1\n2CeAX7a8JGlSsuV/rEqSZkuSPwO2r6q3DjsXSVsP77qVpDkuyWeARwH7DzsXSVsXe/QkSZJ6ymv0\nJEmSespCT5Ikqacs9CRJknrKQk+SJKmnLPQkSZJ6ykJPkiSpp/5/URQ99rBeMHEAAAAASUVORK5C\nYII=\n",
      "text/plain": [
       "<Figure size 720x360 with 1 Axes>"
      ]
     },
     "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_%28cryptosystem%29).\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": 12,
   "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 transactions. 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": 13,
   "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 transaction. 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": 14,
   "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": 15,
   "metadata": {
    "collapsed": true
   },
   "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": 16,
   "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": 17,
   "metadata": {
    "collapsed": true
   },
   "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",
    "    # Verify a single wallet owns all the inputs\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",
    "    # Call compute_fee here to trigger an assert if output sum is great than input sum. Without this,\n",
    "    # a miner could put such an invalid transaction.\n",
    "    compute_fee(transaction.inputs, transaction.outputs)\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": 18,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "assert verify_transaction(t1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "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": 20,
   "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": 21,
   "metadata": {
    "collapsed": true
   },
   "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": 22,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def verify_block(block, genesis_block, used_outputs=None):\n",
    "    \"\"\"\n",
    "    Verifies that a block is valid :\n",
    "    - Verifies the hash starts with the required amount of ones\n",
    "    - Verifies that the same transaction output isn't used twice\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",
    "        used_outputs: list of outputs used in transactions for all blocks above this one\n",
    "    \"\"\"\n",
    "    if used_outputs is None:\n",
    "        used_outputs = set()\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 that transactions in this block don't use already spent outputs\n",
    "    #\n",
    "    # Note that we could move this in verify_transaction, but this would require some passing the used_outputs\n",
    "    # around more. So we do it here for simplicity\n",
    "    for transaction in block.transactions:\n",
    "        for i in transaction.inputs:\n",
    "            if i.parent_output in used_outputs:\n",
    "                logging.error(\"Transaction uses an already spent output : %s\" % json.dumps(i.parent_output.to_dict()))\n",
    "                return False\n",
    "            used_outputs.add(i.parent_output)\n",
    "    \n",
    "    # Verify ancestors up to the genesis block\n",
    "    if not (block.hash == genesis_block.hash):\n",
    "        if not verify_block(block.ancestor, genesis_block, used_outputs):\n",
    "            logging.error(\"Failed to validate ancestor block\")\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": 23,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "genesis_block : 1162dce8ffec3acf13ce61109f121922eee8cceeea4784aa9d90dc6ec0e0fa92 with fee=0\n",
      "block1        : 117fcd1616a34884c351c65bcca977d3ac0d462ef1123e6db97dec7dfa4040ff with fee=0.0\n",
      "block2        : 11016a28356533b3077bb7d0dfe45ac897bc46212c4aea17dc2b53aba25c1f42 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": 24,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 24,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "verify_block(block1, genesis_block)\n",
    "verify_block(block2, genesis_block)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "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 name=\"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": 26,
   "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",
    "block = Block([tx], ancestor=block2, miner_address=walter.address, skip_verif=True)\n",
    "assert not verify_block(block, 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": 27,
   "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",
    "block = Block([t3, tx], ancestor=block1, miner_address=walter.address, skip_verif=True)\n",
    "assert not verify_block(block, genesis_block)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A signed transaction could also be duplicated, increasing the total coins in circulation."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {},
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "ERROR:root:Transaction uses an already spent output : {\"recipient_address\": \"30819f300d06092a864886f70d010101050003818d0030818902818100a74a90c7d22156b0b5518aaacd8863038ece459d549cbbcfca8e6ef5f9303122721cd7d8715a651a8afe504fc9a2df0e3d228ead2bfc9e249d6128979e58f4200df365f39192a87fe4204428d616d74723bad0f14ecd605d9e947c35900d823c6e66aa01cf4324647665a0e0badefeec761c6eaa3c4588ba7866a8e065435e4d0203010001\", \"amount\": 5.0}\n"
     ]
    }
   ],
   "source": [
    "block = Block([t3, t3, t4], ancestor=block1, miner_address=bob.address, skip_verif=True)\n",
    "assert not verify_block(block, genesis_block)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Majority attack <a name=\"majority_attack\"></a>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The tools built up so-far ensure that the ledger is self-consistent: money is spent by addresses which own that money. However, a flaw remains: given that there isn't a central copy of the ledger, which is to be trusted ? The rule is that you trust the **longest chain**. Let's see what are the limits of this rule."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# Let's start again with the same example transactions and blocks as above\n",
    "alice = Wallet()\n",
    "bob = Wallet()\n",
    "walter = Wallet()\n",
    "\n",
    "genesis_block = GenesisBlock(miner_address=alice.address)\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",
    "block2 = Block([t3, t4], ancestor=block1, miner_address=walter.address)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "So with t4 above, bob sent 8 coins to walter. Let's assume walter is a merchant and he sold bob a nice car in exchange of those 8 coins. Bob now has a car and walter has 8 coins."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Bob is feeling a bit poor and decides he'd rather not have spent those 8 coins in `block2`. He re-writes history a bit, putting a transaction to himself and mines his own block."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "True\n"
     ]
    }
   ],
   "source": [
    "t4_malicious = Transaction(\n",
    "    bob,\n",
    "    [TransactionInput(t2, 0), TransactionInput(t3, 0)],\n",
    "    [TransactionOutput(bob.address, 8.0), TransactionOutput(bob.address, 1.0)]\n",
    ")\n",
    "block2_malicious = Block([t3, t4_malicious], ancestor=block1, miner_address=bob.address)\n",
    "print(verify_block(block2_malicious, genesis_block))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The `block2_malicious` isn't yet accepted by the network as it hasn't surpassed the longest ledger (`block2`).\n",
    "More transactions are made, to be mined in the next block. Bob happens to mine the new block with this last transaction."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "t6 = Transaction(\n",
    "    alice,\n",
    "    [TransactionInput(t2, 1)],\n",
    "    [TransactionOutput(walter.address, 5.0), TransactionOutput(alice.address, 10.0)]\n",
    ")\n",
    "\n",
    "block3_malicious = Block([t6], ancestor=block2_malicious, miner_address=bob.address)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now the rule in Bitcoin is that everybody trust the longest chain. So let's check which one is the longest"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Chain length for block2           : 3\n",
      "Chain length for block3_malicious : 4 \n"
     ]
    }
   ],
   "source": [
    "def chain_length(block):\n",
    "    if block.ancestor is None:\n",
    "        return 1\n",
    "    else:\n",
    "        return 1 + chain_length(block.ancestor)\n",
    "\n",
    "print(\"Chain length for block2           : %d\" % chain_length(block2))\n",
    "print(\"Chain length for block3_malicious : %d \" % chain_length(block3_malicious))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The accepted ledger is now `block3_malicious`, as it is the longest ledger. Bob has successfully re-written the ledger. On the other hand, he still has the car that he got from walter in exchange of the 8 coins, it's just that the transaction where walter received 8 coins isn't considered the truth so walter won't have those 8 coins.\n",
    "\n",
    "This is a 51% or [Majority attack](https://en.bitcoin.it/wiki/Majority_attack). \n",
    "\n",
    "In practice, however, Walter had a head start on computing `block3 = Block([t6], ancestor=block2, miner_address=walter.address)`, and that `block3` would be accepted by the network. Bob would either have to be very lucky and find the correct nonce very quickly, or would have to keep mining blocks slightly faster than Walter to eventually create a longer ledger which incorporates his modified history.\n",
    "\n",
    "There are three interesting things we can learn from this example :\n",
    "- Even with a majority of mining power, an attacker can only change one of his transaction. He can't create money\n",
    "  out of thin air (this would require invalid blocks) or spend other people's money (he wouldn't be able to sign\n",
    "  the transaction).\n",
    "- An expensive proof of work is required to make sure it's costly to create valid blocks. If the proof of work was\n",
    "  trivial, the network would be spammed by concurrent chains and it would never reach a consensus.\n",
    "- The \"trust the longest chain\" rule is the reason why you wait for a number of confirmations before considering\n",
    "  a transaction done. The number of confirmation of a transaction is how many blocks behind the last one a transaction\n",
    "  is. The more confirmations you wait for, the costlier it become for an attacker to change his transaction."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Main differences with Bitcoin <a name=\"differences\"></a>\n",
    "\n",
    "As explained above, the goal is not to have a conformant Bitcoin implementation and therefore many things are not implemented. The most important are :\n",
    "\n",
    "- This uses the wallet public key as its address. Bitcoin uses [more complicated addresses](https://en.bitcoin.it/wiki/Technical_background_of_version_1_Bitcoin_addresses)\n",
    "- Bitcoin uses ECDSA for signature, this uses RSA.\n",
    "- Bitcoin uses two rounds of SHA256, this uses one\n",
    "- Bitcoin transactions use a [scripting language](https://en.bitcoin.it/wiki/Script). Here we just have\n",
    "  simple transactions with one amount per output\n",
    "- Bitcoin requires a way to broadcast blocks to all the nodes. The whole communication part is left out from this    notebook.\n",
    "  See the [Client Node Discovery](https://en.bitcoin.it/wiki/Satoshi_Client_Node_Discovery) and [Protocol documentation](https://en.bitcoin.it/wiki/Protocol_documentation) pages on the bitcoin wiki\n",
    "- Bitcoin uses a [Merkle tree](https://en.wikipedia.org/wiki/Merkle_tree) to save disk space by pruning spent   \n",
    "  transactions.\n",
    "  \n",
    "Thanks to HN users *westurner*, *vinn124*, *ivan_ah* and *magnat* for helping me figure out the main differences.\n",
    "\n",
    "## Security issues\n",
    "\n",
    "In addition to the differences above, there are a number of security issues with this implementation (pointed out by HN user *magnat*) :\n",
    "- Use of floating point arithmetic can lead to many problems (e.g. loss of precisions).\n",
    "- The JSON serialization as implemented here is not reproducible across platforms. For example, two serialization of\n",
    "  the same transaction on two different platforms could produce two different JSON (line endings, keys ordering,   spaces).\n",
    "- The mine method implemented here can loop forever due to integer overflow."
   ]
  }
 ],
 "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.1"
  },
  "varInspector": {
   "cols": {
    "lenName": 16,
    "lenType": 16,
    "lenVar": 40
   },
   "kernels_config": {
    "python": {
     "delete_cmd_postfix": "",
     "delete_cmd_prefix": "del ",
     "library": "var_list.py",
     "varRefreshCmd": "print(var_dic_list())"
    },
    "r": {
     "delete_cmd_postfix": ") ",
     "delete_cmd_prefix": "rm(",
     "library": "var_list.r",
     "varRefreshCmd": "cat(var_dic_list()) "
    }
   },
   "types_to_exclude": [
    "module",
    "function",
    "builtin_function_or_method",
    "instance",
    "_Feature"
   ],
   "window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}