maketh.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    " # Maketh\n",
    "This tutorial will guide you through the implementation of a bare-bones cryptocurrency in Python. By the end of this tutorial you will have:\n",
    "- Understood the core concepts of blockchain (in the context of Bitcoin)\n",
    "- Implemented several key blockchain algorithms on a high-level\n",
    "- Built a rudimentary, hackable blockchain (don't worry, you'll hack it yourself first)\n",
    "\n",
    "The currency that you will build today is similar to Bitcoin. As such, I will explain core blockchain concepts in the context of Bitcoin. Since I'll often use specefic examples, certain parts of this guide may not be true for another cryptocurrency or project implemented on a blockchain. The cryptocurrency that you build will feature only the minimal funtionality required to be considered a **local** cryptocurrency. This means that it can only be run on a singular node, and is constrained to, your computer. Consider this tutorial an educational introduction to the various elements that comprise a blockchain:\n",
    "\n",
    "1. Wallets\n",
    "1. Transactions\n",
    "1. Blocks\n",
    "1. Mining\n",
    "1. Consensus\n",
    "\n",
    "We'll start with the smallest elements then work our way to more macro concepts, building incrementally on what we've learned.\n",
    "\n",
    "## Circa 2008\n",
    "Let's start by bringing down most (if not all) major banks across the globe. We'll do this be giving people a way to store money securely on their own computers. We'll call this wizardary a \"wallet,\" as it serves the same purpose as a tangible wallet, that is, to hold money."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 205,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import binascii\n",
    "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",
    "class Wallet(object):\n",
    "    \"\"\" Public key/private 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",
    "        \"\"\" Address is pubic key \"\"\"\n",
    "        return binascii.hexlify(self._public_key.exportKey(format='DER')).decode('ascii')\n",
    "    \n",
    "    def sign(self, message):\n",
    "        \"\"\" Sign a transaction with this wallet \"\"\"\n",
    "        h = SHA.new(message.encode('utf8'))\n",
    "        return binascii.hexlify(self._signer.sign(h)).decode('ascii')\n",
    "    \n",
    "def verify_signature(wallet_address, message, signature):\n",
    "    \"\"\" Check that the provided `signature` corresponds to `message`\n",
    "    signed by the wallet at `wallet_address` \"\"\"\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",
    "# create a new wallet\n",
    "w1 = Wallet()\n",
    "\n",
    "# sign the wallet\n",
    "signature = w1.sign('My first wallet')\n",
    "\n",
    "# verify address\n",
    "assert verify_signature(w1.address, 'My first wallet', signature)\n",
    "\n",
    "# verify address with incorrect signature\n",
    "assert not verify_signature(w1.address, 'rogue message', signature)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## The Sacred Box\n",
    "Consider for a moment that you were worthy enough to be given the Sacred Box. The Sacred Box permits you to lay pieces of paper within its chambers. When you close the Box and shake it, the word on the paper somehow changes to a seemingly gibberish sequence of [alphanumeric](https://en.wikipedia.org/wiki/Alphanumeric) characters.\n",
    "\n",
    "<img src=\"imgs/sacred_box/example_one.png\">\n",
    "\n",
    "For the sake of simplicity, let's attribute the conversion to *magic*. How does the Sacred Box compute the end word? Not a singular human in the world is sure (that's not really true). Despite this, we adore the Sacred Box. As it is Sacred, we *must* not question it, but rather observe. What happens when we put a different word into the Sacred Box? What if we put a recieved output back into the Sacred Box? Let us be guided by the box. Put in the pieces of paper, close the box, and shake it.\n",
    "\n",
    "<img src=\"imgs/sacred_box/example_two.png\">\n",
    "\n",
    "Suprisingly, when given an alphanumeric string of characters (in this case, \"A6XBDEGK\") the Sacred Box cannot determine the original word that was put in it. That is because, in the eyes of the Sacred Box, all inputs are the same (we have much to learn from the Sacred Box). Furthermore, we are now certain that it can **only** convert inputs into gibberish. This is okay. The Sacred Box is sacred, and has endured much, therefore we will always adore it. Notice how putting in a different word converted that word to another seemingly random sequence of characters.  It is important to understand that **whenever the same word is entered into the Sacred Box, the resulting output will always be the same**.\n",
    "\n",
    "### Et tu, Box-te?\n",
    "The Sacred Box is a sham. \n",
    "\n",
    "What if I told you that the Box was based in sound, logical, mathematical reasoning. Would you feel duped? Brace yourselves: our sacred box is just a mathematical [hash function](https://en.wikipedia.org/wiki/Hash_function). \n",
    "\n",
    "Humans are such fickle minded beings.  \n",
    "\n",
    "This box is the most fundamental component of Bitcoin (and most blockchains). Hashes are not a concept unique to Bitcoin or cryptocurrencies. In fact, in computer science, A hash function just serves to map (or \"reformat\") data of an arbitrary size to data of a fixed size. This output is called a digest. Let's see an implementation of this in Python. Luckily for us Python has a package in the Standard Library that includes a number of hash functions."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 206,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CANNABIS: 5de87455cbe2bbf661db741dafc556c656a72512ece65a4182fa18e44bfc56c8\n",
      "DANNABIS: fd0ce5549345e2074a31bc56bbea5017aff686aebc3100dfd3b9218c113acb07\n",
      "CANNABIS: 5de87455cbe2bbf661db741dafc556c656a72512ece65a4182fa18e44bfc56c8\n"
     ]
    }
   ],
   "source": [
    "import hashlib\n",
    "\n",
    "def sha256(data):\n",
    "    \"\"\" Map data to a fixed digest \"\"\"\n",
    "    return hashlib.sha256(data.encode(\"ascii\")).hexdigest()\n",
    "\n",
    "def sacred_box(data):\n",
    "    \"\"\" Return a formatted digest \"\"\"\n",
    "    return \"{}: {}\".format(data, sha256(data))\n",
    "\n",
    "\n",
    "\"\"\" EXAMPLES \"\"\"\n",
    "print(sacred_box(\"CANNABIS\"))\n",
    "\n",
    "# changing even just one character significantly \n",
    "# impacts the resulting digest\n",
    "print(sacred_box(\"DANNABIS\"))\n",
    "\n",
    "# notice how the same input always\n",
    "# returns the same output\n",
    "print(sacred_box(\"CANNABIS\"))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Recall happens when the outputs of the Sacred Box are passed back into it and it is shook again. Now, what would happen if you hash the digest of the word \"CANNABIS\"? Test your theory by trying it in the cell above.\n",
    "\n",
    "---\n",
    "\n",
    "## Transactions\n",
    "Hashes are an essential part of Bitcoin. After seralization, each transaction undergoes two rounds of the same hash function ([sha256](https://en.wikipedia.org/wiki/SHA-2)) that we used in our cryptocurrency to create a **Transaction Identifier (TXID)**. When working with systems of scale, much like Bitcoin, fractions of seconds come into play. A transaction sometimes contains too much data for it to be passed between nodes effectively (too many bits). Bitcoin uses a hash function to remap the data to a fixed length to serve the same general purpose that the blockchain needs. We use hashes because they are one way functions. It is easy to compute the output of a hash funciton given its input, but it is very difficult (read: impossible, probably) to obtain the input of a hash function given the output (the hash function itself cannot compute it). Transactions gain a layer of security and efficiency when we hash its contents.\n",
    "\n",
    "In Bitcoin, transactions are just records that a wallet was decreased of a certain balance and that another wallet was increased of that same balance. This is comprised of:\n",
    "- A spender, who will sign the transaction\n",
    "- A number of inputs, which are other transactions' outputs. The recipient of all those should be the spender's wallet, otherwise you could spend other people's money.\n",
    "- A number of outputs, each of which specify an amount of money and a recipient"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 207,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import json\n",
    "import numpy as np\n",
    "\n",
    "class TransactionInput(object):\n",
    "    \"\"\" An input for a transaction. This points to an output of another transaction \"\"\"\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",
    "    \"\"\" An output for a transaction. This specifies an amount and a recipient (wallet) \"\"\"\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",
    "    \"\"\" Compute the transaction fee by computing the difference between total input and total output \"\"\"\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",
    "        \"\"\" Create a transaction spending money from the provided wallet \"\"\"\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 sha256(json.dumps(self.to_dict()))\n",
    "    \n",
    "# We need to propogate our blockchain with a root \n",
    "# transaction, as all transactions need a parent transaction\n",
    "class GenesisTransaction(Transaction):\n",
    "    \"\"\" This is the first transaction which is a special transaction\n",
    "    with no input and 25 unit output \"\"\"\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",
    "        assert not include_signature, \"Cannot include signature of genesis transaction\"\n",
    "        return super().to_dict(include_signature=False)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Example transaction between Alice and Bob."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 208,
   "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",
    "\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. First, let's send a few more transactions between Alice, Bob, and their friend, Walter."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 209,
   "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",
    "# creating a list of transactions with which to compute the balance\n",
    "transactions = [t1, t2, t3, t4]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now, let's compute the balance of our transactions."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 210,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Alice  has 15.00 units\n",
      "Bob    has 1.00 units\n",
      "Walter has 8.00 units\n"
     ]
    }
   ],
   "source": [
    "def compute_balance(wallet_address, transactions):\n",
    "    \"\"\" Given an address and a list of transactions, computes \n",
    "    the wallet balance of the address \"\"\"\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 units\" % compute_balance(alice.address, transactions))\n",
    "print(\"Bob    has %.02f units\" % compute_balance(bob.address, transactions))\n",
    "print(\"Walter has %.02f units\" % 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",
    "1. You can only spend your money. This means checking that all inputs are owned by the transaction's owner\n",
    "1. Ensure you don't spend more than you have. This is checked by the compute_fee function above."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 211,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import logging\n",
    "\n",
    "def verify_transaction(transaction):\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",
    "    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",
    "\n",
    "t2 = Transaction(\n",
    "    bob,\n",
    "    [TransactionInput(t1, 0)],\n",
    "    [TransactionOutput(walter.address, 10.0)]\n",
    ")\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": 212,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "assert verify_transaction(t1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 213,
   "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": 214,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "assert verify_transaction(t3)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Transactions in Blocks\n",
    "Now that we have :\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",
    "\n",
    "1. Verifying the transactions in the block\n",
    "1. 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. In the same way, the miner can add transactions to redirect the fees from the transactions in the block to whatever address it chooses.\n",
    "\n",
    "## Mining\n",
    "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": 215,
   "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",
    "        \n",
    "print(sha256(message + str(nonce)))\n",
    "\n"
   ]
  },
  {
   "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": 216,
   "metadata": {},
   "outputs": [],
   "source": [
    "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 = sha256(message + nonce)\n",
    "        if digest.startswith(prefix):\n",
    "            return nonce, i\n",
    "        i += 1\n",
    "        \n",
    "\n",
    "import numpy as np\n",
    "import pandas as pd\n",
    "import pylab as pl\n",
    "import string\n",
    "import random\n",
    "import matplotlib\n",
    "%matplotlib inline\n",
    "\n",
    "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": 217,
   "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>0IZ2LCGU0V</th>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>DOGFHHT4P9</th>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>A46ZO7C5R0</th>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>QLJR9N2P23</th>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>V4JC3XRZYB</th>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>R3ZRZO7S3H</th>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>AFD8M7ZW3J</th>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>F5P8FZ2QF7</th>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>YT8W7WYSK2</th>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>NL4YRBU238</th>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>P8VWC6I5TY</th>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>ETW79SYL60</th>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>C4BWBVBAN7</th>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>TWPO07IA3G</th>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>5EK31FTDVW</th>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>CLR5G9CA4G</th>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4ACII8MQT9</th>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>RPY6T35X7S</th>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>S04XGIE8UV</th>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2G0049TJPN</th>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>HYSQ8G0CQH</th>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>VLIJVOMTLO</th>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>Q18LUBVO5I</th>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>ZK1SWDRUAT</th>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>V4Y14J40I2</th>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>U3559T05D8</th>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>TSWEXWYJYF</th>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>LFPETCZ80C</th>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>DIPS9OOGMG</th>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>O713ZYTHN9</th>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>207RSBN59X</th>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>JMNO35J06K</th>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>XKI8JKUY1A</th>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>TO51O5R62W</th>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>VCXMD1G10N</th>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>QN8NQC3V3I</th>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>HP2B0284W0</th>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>HKR6IJ9CTO</th>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>B40TJSLO7F</th>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>KVFRY3UQYF</th>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>KX6K0DP1BX</th>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>VVGS2HRNH4</th>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>NNMU2QNSOL</th>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>5Y40LI8V38</th>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>E78BH3LQ5Q</th>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>80IIQUS4TH</th>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>IAO8TPAQMI</th>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>VAQ5PME3YB</th>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>G95C6LES2Q</th>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>S3STVY7JTM</th>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "      <td>0</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "            1  2  3  4\n",
       "0IZ2LCGU0V  0  0  0  0\n",
       "DOGFHHT4P9  0  0  0  0\n",
       "A46ZO7C5R0  0  0  0  0\n",
       "QLJR9N2P23  0  0  0  0\n",
       "V4JC3XRZYB  0  0  0  0\n",
       "R3ZRZO7S3H  0  0  0  0\n",
       "AFD8M7ZW3J  0  0  0  0\n",
       "F5P8FZ2QF7  0  0  0  0\n",
       "YT8W7WYSK2  0  0  0  0\n",
       "NL4YRBU238  0  0  0  0\n",
       "P8VWC6I5TY  0  0  0  0\n",
       "ETW79SYL60  0  0  0  0\n",
       "C4BWBVBAN7  0  0  0  0\n",
       "TWPO07IA3G  0  0  0  0\n",
       "5EK31FTDVW  0  0  0  0\n",
       "CLR5G9CA4G  0  0  0  0\n",
       "4ACII8MQT9  0  0  0  0\n",
       "RPY6T35X7S  0  0  0  0\n",
       "S04XGIE8UV  0  0  0  0\n",
       "2G0049TJPN  0  0  0  0\n",
       "HYSQ8G0CQH  0  0  0  0\n",
       "VLIJVOMTLO  0  0  0  0\n",
       "Q18LUBVO5I  0  0  0  0\n",
       "ZK1SWDRUAT  0  0  0  0\n",
       "V4Y14J40I2  0  0  0  0\n",
       "U3559T05D8  0  0  0  0\n",
       "TSWEXWYJYF  0  0  0  0\n",
       "LFPETCZ80C  0  0  0  0\n",
       "DIPS9OOGMG  0  0  0  0\n",
       "O713ZYTHN9  0  0  0  0\n",
       "207RSBN59X  0  0  0  0\n",
       "JMNO35J06K  0  0  0  0\n",
       "XKI8JKUY1A  0  0  0  0\n",
       "TO51O5R62W  0  0  0  0\n",
       "VCXMD1G10N  0  0  0  0\n",
       "QN8NQC3V3I  0  0  0  0\n",
       "HP2B0284W0  0  0  0  0\n",
       "HKR6IJ9CTO  0  0  0  0\n",
       "B40TJSLO7F  0  0  0  0\n",
       "KVFRY3UQYF  0  0  0  0\n",
       "KX6K0DP1BX  0  0  0  0\n",
       "VVGS2HRNH4  0  0  0  0\n",
       "NNMU2QNSOL  0  0  0  0\n",
       "5Y40LI8V38  0  0  0  0\n",
       "E78BH3LQ5Q  0  0  0  0\n",
       "80IIQUS4TH  0  0  0  0\n",
       "IAO8TPAQMI  0  0  0  0\n",
       "VAQ5PME3YB  0  0  0  0\n",
       "G95C6LES2Q  0  0  0  0\n",
       "S3STVY7JTM  0  0  0  0"
      ]
     },
     "execution_count": 217,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "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)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 226,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "#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": 219,
   "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>0IZ2LCGU0V</th>\n",
       "      <td>3</td>\n",
       "      <td>42</td>\n",
       "      <td>2385</td>\n",
       "      <td>21090</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>DOGFHHT4P9</th>\n",
       "      <td>9</td>\n",
       "      <td>145</td>\n",
       "      <td>746</td>\n",
       "      <td>746</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>A46ZO7C5R0</th>\n",
       "      <td>42</td>\n",
       "      <td>245</td>\n",
       "      <td>2626</td>\n",
       "      <td>44701</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>QLJR9N2P23</th>\n",
       "      <td>35</td>\n",
       "      <td>104</td>\n",
       "      <td>539</td>\n",
       "      <td>61128</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>V4JC3XRZYB</th>\n",
       "      <td>2</td>\n",
       "      <td>16</td>\n",
       "      <td>14432</td>\n",
       "      <td>38752</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "             1    2      3      4\n",
       "0IZ2LCGU0V   3   42   2385  21090\n",
       "DOGFHHT4P9   9  145    746    746\n",
       "A46ZO7C5R0  42  245   2626  44701\n",
       "QLJR9N2P23  35  104    539  61128\n",
       "V4JC3XRZYB   2   16  14432  38752"
      ]
     },
     "execution_count": 219,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "results.iloc[:5]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 227,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Text(0,0.5,'Iterations')"
      ]
     },
     "execution_count": 227,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAnoAAAFNCAYAAACXPcKEAAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAADl0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uIDIuMS4wLCBo\ndHRwOi8vbWF0cGxvdGxpYi5vcmcvpW3flQAAIABJREFUeJzt3Xu4XWV57/3vzwQVFQElupEAQY0W\nPEWJiNX2dXtAULfoW1Rolaho1GKre9uWqLsFrXRjW2v1rcWiUsAqeKAKRSxSqrJtVQgaEURLxCAR\nhHAUFVDwfv8Yz5KZxTola63Mtcb6fq5rXmvOe5zuMeaYc97recYhVYUkSZL6517DTkCSJEmzw0JP\nkiSppyz0JEmSespCT5Ikqacs9CRJknrKQk+SJKmnLPSkcSQ5Kcm7hrTsJPnHJDcluWCM4b+X5AvD\nyG0ghw8m+dNh5jCbkrwtyYeHncdcl2T7JP+S5JYknxp2PqPNhf00yYYkz27PN9uvkrw4yVVJfprk\niUkeneSbSW5N8oczkX+SZUkqyeLprovmH990zRtJNgDbAw+vqp+12GuAl1fVM4aY2mx4OvAcYOnI\nug6qqo8BHxt5naSA5VW1fjaSSfJK4DVV9fSBHF4/G8uaIIdlwA+A7arqztleXlX9xWwvoycOAR4K\nPHhbvC9balvvp5MZY7/6a+CNVXUGQJKPAF+qqifOVg5JvgT8U1X5j8wCYIue5pvFwJuGncSWSrJo\nCyfZE9gwVpE30/wvX9O0J/BfW1Pkzfa+txWfu2HYE7h0gtfS9FSVDx/z4gFsANYANwI7tdhr6P77\nBVgGFLB4YJov0bVEAbwS+A/gvcDNwBXAb7b4VcB1wKqBaU8CPgicC9wKfBnYc2D4b7RhNwLfA146\natrjgbOBnwHPHmN9Hgac2aZfD7y2xY8AbgfuAn4KvGOMaV8JfKU9P7+t98/a+C9r8RcA69q6/ifw\n+FHb8ijgYuAOugJ6DfD9tq7fAV7cxt17VD43D6zjuwbm+dq2Hje29XrYwLACXg9cDtwEfABIG/bI\ntm1vAa4HPjHO+//DNp+ftsdT6f5Z/d/Ale39OwXYcZzpnwFsBP6kjXsN8CLgecB/tbzfNjD+MXSt\nHnD3vrWq5XE98PaBce81sP1uAD4JPGicPHYGzgI2tW1xFl3L7UT7/R+19+oW4BPAfae73QemvWzg\nPX/SwL55esvxB8AfjpPbO4BfAL9s78kRE70nA9vxiLYdzx9jnpcBLxh4vbht75HcPgX8uG2L84HH\nTPS5Y4r7KZN/f0xpP23jvqKt/w3A29t7+OzB/Qq4T9tmI5/d7wP/Tvc5u70Ne9QY+R9M97n+SZvm\nwIH95NkD4x3DPfffxcCxo5bxd22/eM+odfgX4M3b4rvdx+w+hp6ADx9TfYx8kQH/PPLFx5YXencC\nrwIWAe9qPzYfaF+6B9D94D2gjX9Se/3bbfj7uLu4uj9dcfiq9uX5pPbl/5iBaW8Bnkb3w3ffMdbn\ny8DfA/cFVtD9qD5rINevTLAtNhve1vuRA6+fRPcj+5S2rqva9rvPwLZcB+wObN9iL6H7gb8X8DK6\nH59dx8uHgR8g4Jlt/Z/UttX/x8CPeMvvLGAnYI+2riM/UKfS/Rjeq22Lp4+zzmO9v6+m+9F+OPCA\ntm98dJzpn9He/z8DtqP7wd8EfBzYAXgM3Y/fw9v4x3DPH8oP0R0+8AS6AnnvNvzNwNeApW39/wE4\ndZw8Hgz8DnC/ttxPAZ+dZL+/oL03D6IrhF4/A9v9JcCPgCcDoStk9mzvw0VtO927bdsrgOeOk9+v\nt9Nk78nAdjyF7jO0/Rjz+zPgYwOvnw98d9T8d2jr+7fAulH75GafO6a4nzL598dU99N96Aqoke+N\nv6Hb7549zvYa/dn99TLH+Jzt19bvOS2P3YDfGPx+HOt9Gb1uYyxjP+Bq4F7t9S7Az4GHzsZ3uY9t\n+7DrVvPRnwF/kGTJVkz7g6r6x6q6i65lZHfgnVV1R1V9ga514pED43+uqs6vqjvovuSfmmR3utay\nDW1ed1bVN+haQA4ZmPaMqvqPqvpVVd0+mESbx9OBo6rq9qpaB3yYriVgJrwW+Ieq+npV3VVVJ9MV\nJvsPjPP+qrqqqm4DqKpPVdXVLd9P0LUC7TfF5f0ecGJVfaNtq7fSbatlA+McV1U3V9UPgS/SFbfQ\ntQbtSdeycntVfWUL1vP3gL+pqiuq6qdtuYdO0CX4S+DYqvolcBrdD9r7qurWqrqUrsvs8RMs7x1V\ndVtVfQv4Fl3BB/A6uha+jW39jwEOGSuPqrqhqk6vqp9X1a10LSz/zyTr+f723txI19Iysu2ms91f\nA/xlVV1YnfVVdSVd4bekqt5ZVb+oqivoCtxDJ8lxxFTek2Oq6mcj+94oHwdemOR+7fXvthgAVXVi\ne79GtvMTkuw4MP24nzumtr3GM9X99BDgrIHvjT8FfjWF+U/FEXT5n9vW70dV9d3pzrSqLqArIJ/V\nQofS/QN97XTnreGz0NO8U1WX0LVSrNmKyQe/uEYKnNGxBwy8vmpguT+l6+55GN0X/lOS3DzyoPsR\n+W9jTTuGhwE3th/6EVfS/Yc+E/YE3jIqv93bcsfML8nhSdYNjP9YukJoKh5Glz/w6211A5uvz48H\nnv+cu7fzn9C1KF2Q5NIkr57iMu+x3PZ8Md3JAWO5oRX50N5/7rlPPIDxjbcOewKfGdh2l9F1j90j\njyT3S/IPSa5M8hO67sedJjmebLzlTme7707X9TfansDDRu07bxtrXcYxlfdk3M9GdScUXQb8j1bs\nvZBW6CVZlOS4JN9v225Dm2xwP53sczfZ9hrPVPfTh7H598bP2jJmwnjv2Uw4GXh5e/5y4KOztBxt\nYx6ErfnqaOAbwHsGYiMnLtyP7vgV2Lzw2hq7jzxJ8gC6rrOr6b7Iv1xVz5lg2ppg2NXAg5LsMFDs\n7UHXlTYTrqJruTp2Kvkl2ZOu1eZZwFer6q4k6+h+2DYbdxxX0xUII/O7P10X5aTrU1U/pmuBJMnT\ngX9Lcn7d8wzisXLYbLl02/BONi/etoWrgFdX1X9MYdy3AI8GnlJVP06yAvgmd2/rLbHV250u50eM\nE/9BVS3finzukRObvydLW2yy/elU4DC6xojvDOwLv0t3jNqz6Yq8HemOPRzcdpN97sbbXhN+f2zB\nfnoN3XGtI8u4X1vGTBjvPYMu//sNvJ7ou2+sbfRPwCVJnkCX/2e3KkPNObboaV5qX66fAP5wILaJ\n7gv75e0//1cz/pfiVD0vydOT3Bv4c+DrVXUVXYvio5K8Isl27fHkJHtPPLtf53oV3QkS/yfJfZM8\nnq5b5mMTTzmua+mOiRrxIeD1SZ7Srsl3/yTPT7LDONPfn+7LfxNAklfRtegNzn9p2w5j+TjwqiQr\nktwH+Au6bbVhssSTvCTJSAFwU8vjrjFG3UTXBTa4nqcC/zPJXq0Q/wu6g+S39WU+Pggc2wpmkixJ\ncvA44+5A13J4c5IH0f3TsrW2ervTHSrwR0n2bfvII1v+FwA/SXJUumvkLUry2CRPnmJOM/GenEZ3\nzOwbGOi2pdt2d9C1kN2vzXtLjLu9Jvv+2IL99NPACwa+N97JzP3WfqTl/6wk90qyW5LfaMPW0XWR\nb5dkJZsfRjLa6O8LqmojcCFdS97p43Srax6y0NN89k66AmXQa4E/pvsheAxdMTUdH6f7Ib4R2Jeu\ne5bWCncA3bEsV9N1j72b7uDrqTqM7iDpq4HPAEdX1blbmecxwMmtq+2lVbWWblv8Hd2P0nq6EyrG\nVFXfoWsd/Srdj8Dj6M5QHvHvdMev/TjJ9WNMfx7dsUin07VoPIKpH9P1ZODrSX5Kdxbkm6rqB2Ms\n4+d0x7P9R1vP/YET6X6Yzqc7O/R24A+muNyZ9D663L+Q5Fa6EzOeMs64f0t3Qsf1bbx/3dqFTme7\nV9Wn6Lbnx+lOOvos3ZnCdwH/g+5Yvh+0PD9M13o2FdN+T6rqGrp98Tfp/qEbcQpd1+uP6M4S/toW\nzney7TXR98dU99NLgSPptus1dJ+/jVuS5wT5X0B3Ath76Y6p+zJ3t1D+aVufm+jOhv74WPNo3kd3\nDOlNSd4/ED+Z7rNvt22PjFzeQJIkLWBJfpuuC3dZVc3UCSQaMlv0JEla4JJsR3cx+g9b5PWLhZ4k\nSQtYO7b4ZmBXukML1CN23UqSJPXUrLXoJTkxyXVJLhmIfaJdp2tdkg3t8g0kWZbktoFhHxyYZt8k\n306yPsn7k6TFH5Tk3CSXt787t3jaeOuTXJzkSbO1jpIkSXPZbHbdngQcOBioqpdV1YqqWkF31tM/\nDwz+/siwqnr9QPx4YDWwvD1G5rkGOK9d6+k87r547kED465u00uSJC04s3bB5Ko6P+PcVqa1yr2U\n7r6D40qyK/DAqvpqe30K3U3IP0930cxntFFPprt331Etfkp1fdJfS7JTkl3b6frj2mWXXWrZsjHT\nlSRJmlMuuuii66tq0luBDuvOGL8FXFtVlw/E9kryTborkv/vqvq/dLelGbz+0EbuvlXNQ0eKt6q6\nJslDWnw3Nr8Fzsg0ExZ6y5YtY+3atVu7PpIkSdtMkisnH2t4hd5hdFdPH3ENsEdV3ZBkX+CzSR7D\n2LcEmuzskSlPk2Q1Xfcue+yxx6RJS5IkzSfb/PIqSRYD/y8DVzuvqjuq6ob2/CK6mzY/iq41bunA\n5Evp7iIAcG3r2h3p4r2uxTcycH/SUdNspqpOqKqVVbVyyZJJWz8lSZLmlWFcR+/ZwHfbffWAX98X\nclF7/nC6EymuaF2ztybZvx3XdzhwRpvsTGBVe75qVPzwdvbt/sAtkx2fJ0mS1EezeXmVU+nuVfjo\nJBuTHNEGHcrm3bYAvw1cnORbdDeEfn1V3diGvYHuPovr6Vr6Pt/ixwHPSXI58Jz2GuBs4Io2/oeA\n35/pdZMkSZoPvGBys3LlyvJkDEmSNB8kuaiqVk42nrdAkyRJ6ikLPUmSpJ6y0JMkSeopCz1JkqSe\nstCTJEnqqWHdGUOSJC0Q3aVwh2chX2HEFj1JkjSrqmqrH3sedda0pl/IRR5Y6EmSJPWWhZ4kSVJP\nWehJkiT1lIWeJElST1noSZIk9ZSFniRJUk9Z6EmSJPWUhZ4kSVJPWehJkiT1lIWeJElST1noSZIk\n9ZSFniRJUk9Z6EmSJPWUhZ4kSVJPWehJkiT1lIWeJElST1noSZIk9ZSFniRJUk9Z6EmSJPWUhZ4k\nSVJPWehJkiT11KwVeklOTHJdkksGYsck+VGSde3xvIFhb02yPsn3kjx3IH5gi61PsmYgvleSrye5\nPMknkty7xe/TXq9vw5fN1jpKkiTNZbPZoncScOAY8fdW1Yr2OBsgyT7AocBj2jR/n2RRkkXAB4CD\ngH2Aw9q4AO9u81oO3AQc0eJHADdV1SOB97bxJEmSFpxZK/Sq6nzgximOfjBwWlXdUVU/ANYD+7XH\n+qq6oqp+AZwGHJwkwDOBT7fpTwZeNDCvk9vzTwPPauNLkiQtKMM4Ru+NSS5uXbs7t9huwFUD42xs\nsfHiDwZurqo7R8U3m1cbfksbX5IkaUHZ1oXe8cAjgBXANcB7WnysFrfaivhE87qHJKuTrE2ydtOm\nTRPlLUmSNO9s00Kvqq6tqruq6lfAh+i6ZqFrkdt9YNSlwNUTxK8HdkqyeFR8s3m14TsyThdyVZ1Q\nVSurauWSJUumu3qSJElzyjYt9JLsOvDyxcDIGblnAoe2M2b3ApYDFwAXAsvbGbb3pjth48yqKuCL\nwCFt+lXAGQPzWtWeHwL8extfkiRpQVk8+ShbJ8mpwDOAXZJsBI4GnpFkBV1X6gbgdQBVdWmSTwLf\nAe4Ejqyqu9p83gicAywCTqyqS9sijgJOS/Iu4JvAR1r8I8BHk6yna8k7dLbWUZIkaS6btUKvqg4b\nI/yRMWIj4x8LHDtG/Gzg7DHiV3B31+9g/HbgJVuUrCRJUg95ZwxJkqSestCTJEnqKQs9SZKknrLQ\nkyRJ6ikLPUmSpJ6y0JMkSeopCz1JkqSestCTJEnqKQs9SZKknrLQkyRJ6ikLPUmSpJ6y0JMkSeop\nCz1JkqSestCTJEnqKQs9SZKknrLQkyRJ6ikLPUmSpJ6y0JMkSeopCz1JkqSestCTJEnqKQs9SZKk\nnrLQkyRJ6ikLPUmSpJ6y0JMkSeopCz1JkqSestCTJEnqKQs9SZKknrLQkyRJ6qlZK/SSnJjkuiSX\nDMT+Ksl3k1yc5DNJdmrxZUluS7KuPT44MM2+Sb6dZH2S9ydJiz8oyblJLm9/d27xtPHWt+U8abbW\nUZIkaS6bzRa9k4ADR8XOBR5bVY8H/gt468Cw71fVivZ4/UD8eGA1sLw9Rua5BjivqpYD57XXAAcN\njLu6TS9JkrTgzFqhV1XnAzeOin2hqu5sL78GLJ1oHkl2BR5YVV+tqgJOAV7UBh8MnNyenzwqfkp1\nvgbs1OYjSZK0oAzzGL1XA58feL1Xkm8m+XKS32qx3YCNA+NsbDGAh1bVNQDt70MGprlqnGkkSZIW\njMXDWGiStwN3Ah9roWuAParqhiT7Ap9N8hggY0xek81+qtMkWU3Xvcsee+wxldQlSZLmjW3eopdk\nFfAC4PdadyxVdUdV3dCeXwR8H3gUXWvcYPfuUuDq9vzakS7Z9ve6Ft8I7D7ONJupqhOqamVVrVyy\nZMlMrJ4kSdKcsU0LvSQHAkcBL6yqnw/ElyRZ1J4/nO5Eiital+ytSfZvZ9seDpzRJjsTWNWerxoV\nP7ydfbs/cMtIF68kSdJCMmtdt0lOBZ4B7JJkI3A03Vm29wHObVdJ+Vo7w/a3gXcmuRO4C3h9VY2c\nyPEGujN4t6c7pm/kuL7jgE8mOQL4IfCSFj8beB6wHvg58KrZWkdJkqS5bNYKvao6bIzwR8YZ93Tg\n9HGGrQUeO0b8BuBZY8QLOHKLkpUkSeoh74whSZLUUxZ6kiRJPWWhJ0mS1FMWepIkST1loSdJktRT\nFnqSJEk9ZaEnSZLUUxZ6kiRJPWWhJ0mS1FMWepIkST1loSdJktRTFnqSJEk9ZaEnSZLUUxZ6kiRJ\nPWWhJ0mS1FMWepIkST1loSdJktRTFnqSJEk9ZaEnSZLUUxZ6kiRJPWWhJ0mS1FMWepIkST1loSdJ\nktRTFnqSJEk9ZaEnSZLUUxZ6kiRJPWWhJ0mS1FMWepIkST01q4VekhOTXJfkkoHYg5Kcm+Ty9nfn\nFk+S9ydZn+TiJE8amGZVG//yJKsG4vsm+Xab5v1JMtEyJEmSFpLZbtE7CThwVGwNcF5VLQfOa68B\nDgKWt8dq4HjoijbgaOApwH7A0QOF2/Ft3JHpDpxkGZIkSQvGrBZ6VXU+cOOo8MHAye35ycCLBuKn\nVOdrwE5JdgWeC5xbVTdW1U3AucCBbdgDq+qrVVXAKaPmNdYyJEmSFoxhHKP30Kq6BqD9fUiL7wZc\nNTDexhabKL5xjPhEy9hMktVJ1iZZu2nTpmmtlCRJ0lwzl07GyBix2or4lFXVCVW1sqpWLlmyZEsm\nlSRJmvOGUehd27pdaX+va/GNwO4D4y0Frp4kvnSM+ETLkCRJWjCmVOgl+cskD0yyXZLzklyf5OVb\nucwzgZEzZ1cBZwzED29n3+4P3NK6Xc8BDkiyczsJ4wDgnDbs1iT7t7NtDx81r7GWIUmStGBMtUXv\ngKr6CfACupa0RwF/PNlESU4Fvgo8OsnGJEcAxwHPSXI58Jz2GuBs4ApgPfAh4PcBqupG4M+BC9vj\nnS0G8Abgw22a7wOfb/HxliFJkrRgLJ7ieNu1v88DTq2qG9sl6yZUVYeNM+hZY4xbwJHjzOdE4MQx\n4muBx44Rv2GsZUiSJC0kUy30/iXJd4HbgN9PsgS4ffbSkiRJ0nRNqeu2qtYATwVWVtUvgZ/RXatO\nkiRJc9RUW/QA9gaWJRmc5pQZzkeSJEkzZEqFXpKPAo8A1gF3tfDI3SgkSZI0B021RW8lsE87YUKS\nJEnzwFQvr3IJ8N9mMxFJkiTNrKm26O0CfCfJBcAdI8GqeuGsZCVJkqRpm2qhd8xsJiFJkqSZN6VC\nr6q+nOShwJNb6IKq8v6xkiRJc9hU73X7UuAC4CXAS4GvJzlkNhOTJEnS9Ey16/btwJNHWvHanTH+\nDfj0bCUmSZKk6ZnqWbf3GtVVe8MWTCtJkqQhmGqL3r8mOQc4tb1+GXD27KQkSZLmkie84wvcctsv\nh7b8ZWs+N7Rl77j9dnzr6AOGtvzpmurJGH+c5HeApwEBTqiqz8xqZpIkaU645bZfsuG45w87jaEY\nZpE5E6Z8r9uqOh04fRZzkSRJ0gyasNBL8pWqenqSW+nubfvrQUBV1QNnNTtJkiRttQkLvap6evu7\nw7ZJR5IkSTNlqtfR++hUYpIkSZo7pnqJlMcMvkiyGNh35tORJEnSTJmw0Evy1nZ83uOT/KQ9bgWu\nBc7YJhlKkiRpq0xY6FXV/2nH5/1VVT2wPXaoqgdX1Vu3UY6SJEnaClO9jt5bk+wMLAfuOxA/f7YS\nkyRJ0vRMqdBL8hrgTcBSYB2wP/BV4Jmzl5okSZKmY6onY7wJeDJwZVX9d+CJwKZZy0qSJEnTNtVC\n7/aquh0gyX2q6rvAo2cvLUmSJE3XVG+BtjHJTsBngXOT3ARcPXtpSZIkabqmejLGi9vTY5J8EdgR\n+NdZy0qSJEnTNmnXbZJ7Jblk5HVVfbmqzqyqX2zNApM8Osm6gcdPkrw5yTFJfjQQf97ANG9Nsj7J\n95I8dyB+YIutT7JmIL5Xkq8nuTzJJ5Lce2tylSRJms8mLfSq6lfAt5LsMRMLrKrvVdWKqlpBd3eN\nnwOfaYPfOzKsqs4GSLIPcCjd3TkOBP4+yaIki4APAAcB+wCHtXEB3t3mtRy4CThiJnKXJEmaT6Z6\njN6uwKVJLgB+NhKsqhdOc/nPAr5fVVcmGW+cg4HTquoO4AdJ1gP7tWHrq+oKgCSnAQcnuYzusi+/\n28Y5GTgGOH6auUqSJM0rUy303jFLyz8UOHXg9RuTHA6sBd5SVTcBuwFfGxhnY4sBXDUq/hTgwcDN\nVXXnGONLkiQtGFO6vEpVfRnYAGzXnl8IfGM6C27Hzb0Q+FQLHQ88AlgBXAO8Z2TUsVLaivhYOaxO\nsjbJ2k2bvCygJEnqlykVekleC3wa+IcW2o3uUivTcRDwjaq6FqCqrq2qu9oxgR/i7u7ZjcDuA9Mt\npbu0y3jx64GdkiweFb+HqjqhqlZW1colS5ZMc3UkSZLmlqleMPlI4GnATwCq6nLgIdNc9mEMdNsm\n2XVg2IuBkTN9zwQOTXKfJHvR3W/3ArpWxeXtDNt703UDn1lVBXwROKRNvwo4Y5q5SpIkzTtTPUbv\njqr6xcgJE621bMzu0KlIcj/gOcDrBsJ/mWRFm++GkWFVdWmSTwLfAe4Ejqyqu9p83gicAywCTqyq\nS9u8jgJOS/Iu4JvAR7Y2V0mSpPlqqoXel5O8Ddg+yXOA3wf+ZWsXWlU/pztpYjD2ignGPxY4doz4\n2cDZY8Sv4O6uX0mSpAVpql23a4BNwLfpWtrOrqq3z1pWkiRJmraptuj9QVW9j+4kCQCSvKnFJEmS\nNAdNtUVv1RixV85gHpIkSZphE7boJTmM7g4TeyU5c2DQDsANs5mYJEmSpmeyrtv/pLt48S7cfQFj\ngFuBi2crKUmSJE3fhIVeVV0JXAk8ddukI0mSpJkyWdftrYx9vbwAVVUPnJWsJEmSNG2TtejtsK0S\nkSRJ0sya6lm3kiRJmmcs9CRJknrKQk+SJKmnLPQkSZJ6ykJPkiSppyz0JEmSespCT5Ikqacs9CRJ\nknrKQk+SJKmnLPQkSZJ6ykJPkiSppyz0JEmSespCT5Ikqacs9CRJknrKQk+SJKmnLPQkSZJ6ykJP\nkiSppyz0JEmSespCT5Ikqacs9CRJknpqaIVekg1Jvp1kXZK1LfagJOcmubz93bnFk+T9SdYnuTjJ\nkwbms6qNf3mSVQPxfdv817dps+3XUpIkaXiG3aL336tqRVWtbK/XAOdV1XLgvPYa4CBgeXusBo6H\nrjAEjgaeAuwHHD1SHLZxVg9Md+Dsr44kSdLcMexCb7SDgZPb85OBFw3ET6nO14CdkuwKPBc4t6pu\nrKqbgHOBA9uwB1bVV6uqgFMG5iVJkrQgDLPQK+ALSS5KsrrFHlpV1wC0vw9p8d2Aqwam3dhiE8U3\njhGXJElaMBYPcdlPq6qrkzwEODfJdycYd6zj62or4pvPtCswVwPssccek2csSZI0jwytRa+qrm5/\nrwM+Q3eM3bWt25X297o2+kZg94HJlwJXTxJfOkZ8dA4nVNXKqlq5ZMmSmVgtSZKkOWMohV6S+yfZ\nYeQ5cABwCXAmMHLm7CrgjPb8TODwdvbt/sAtrWv3HOCAJDu3kzAOAM5pw25Nsn872/bwgXlJkiQt\nCMPqun0o8Jl2xZPFwMer6l+TXAh8MskRwA+Bl7TxzwaeB6wHfg68CqCqbkzy58CFbbx3VtWN7fkb\ngJOA7YHPt4ckSdKCMZRCr6quAJ4wRvwG4FljxAs4cpx5nQicOEZ8LfDYaScrSZI0T821y6tIkiRp\nhljoSZIk9ZSFniRJUk9Z6EmSJPWUhZ4kSVJPWehJkiT1lIWeJElST1noSZIk9ZSFniRJUk9Z6EmS\nJPWUhZ4kSVJPWehJkiT1lIWeJElSTy0edgKSJGlu22HvNTzu5DXDTmModtgb4PnDTmOrWehJkqQJ\n3XrZcWw4bv4WO9OxbM3nhp3CtNh1K0mS1FMWepIkST1loSdJktRTFnqSJEk9ZaEnSZLUUxZ6kiRJ\nPWWhJ0mS1FMWepIkST1loSdJktRTFnqSJEk9ZaEnSZLUUxZ6kiRJPWWhJ0mS1FPbvNBLsnuSLya5\nLMmlSd7U4sck+VGSde3xvIFp3ppkfZLvJXnuQPzAFlufZM1AfK8kX09yeZJPJLn3tl1LSZKk4RtG\ni96dwFuqam9gf+DIJPu0Ye+tqhXtcTZAG3Yo8BjgQODvkyxKsgj4AHAQsA9w2MB83t3mtRy4CThi\nW62cJEnSXLHNC72quqaqvtGe3wpcBuw2wSQHA6dV1R1V9QNgPbBfe6yvqiuq6hfAacDBSQI8E/h0\nm/5k4EWzszaSJElz11CP0UtckgJzAAAII0lEQVSyDHgi8PUWemOSi5OcmGTnFtsNuGpgso0tNl78\nwcDNVXXnqLgkSdKCMrRCL8kDgNOBN1fVT4DjgUcAK4BrgPeMjDrG5LUV8bFyWJ1kbZK1mzZt2sI1\nkCRJmtuGUugl2Y6uyPtYVf0zQFVdW1V3VdWvgA/Rdc1C1yK3+8DkS4GrJ4hfD+yUZPGo+D1U1QlV\ntbKqVi5ZsmRmVk6SJGmOGMZZtwE+AlxWVX8zEN91YLQXA5e052cChya5T5K9gOXABcCFwPJ2hu29\n6U7YOLOqCvgicEibfhVwxmyukyRJ0ly0ePJRZtzTgFcA306yrsXeRnfW7Aq6btYNwOsAqurSJJ8E\nvkN3xu6RVXUXQJI3AucAi4ATq+rSNr+jgNOSvAv4Jl1hKUmStKBs80Kvqr7C2MfRnT3BNMcCx44R\nP3us6arqCu7u+pUkSdO0bM3nhp3CUOy4/XbDTmFahtGiJ0mS5pENxz1/aMtetuZzQ13+fOct0CRJ\nknrKQk+SJKmnLPQkSZJ6ykJPkiSppyz0JEmSespCT5Ikqacs9CRJknrKQk+SJKmnLPQkSZJ6ykJP\nkiSppyz0JEmSespCT5Ikqacs9CRJknrKQk+SJKmnLPQkSZJ6avGwE5AkzT9Jhp0CVTXsFKQ5zxY9\nSdIWq6ppPfY86qxpz0PS5Cz0JEmSespCT5Ikqacs9CRJknrKQk+SJKmnLPQkSZJ6ysurSNIC9IR3\nfIFbbvvlUHNYtuZzQ1nujttvx7eOPmAoy5a2NQs9SVqAbrntl2w47vnDTmMohlVgSsNg160kSVJP\nWehJkiT1lF23krQA7bD3Gh538pphpzEUO+wNsDC7rbXw9LbQS3Ig8D5gEfDhqjpuyClJ0pxx62XH\neYyetAD0sus2ySLgA8BBwD7AYUn2GW5WkiRJ21ZfW/T2A9ZX1RUASU4DDga+M9SsJGkOWagtWztu\nv92wU1hwkkxv+ndPb/lVNb0ZzGN9LfR2A64aeL0ReMrokZKsBlYD7LHHHtsmsy30uJMfN+wUhurb\nq7497BTmFfcX95epmm637XR/uGfCQv7xnm98r4anr4XeWN9A99jLquoE4ASAlStXzsm90B8ubQn3\nF20r/nBL80Mvj9Gja8HbfeD1UuDqIeUiSZI0FH0t9C4ElifZK8m9gUOBM4eckyRJ0jbVy67bqroz\nyRuBc+gur3JiVV065LQkSZK2qV4WegBVdTZw9rDzkCRJGpa+dt1KkiQteBZ6kiRJPWWhJ0mS1FMW\nepIkST1loSdJktRTFnqSJEk9ZaEnSZLUU/F+hZ0km4Arh53HHLQLcP2wk9C84L6iLeH+oqlyXxnb\nnlW1ZLKRLPQ0oSRrq2rlsPPQ3Oe+oi3h/qKpcl+ZHrtuJUmSespCT5Ikqacs9DSZE4adgOYN9xVt\nCfcXTZX7yjR4jJ4kSVJP2aInSZLUUxZ6GlOSE5Ncl+SSYeeiuS3J7km+mOSyJJcmedOwc9LclOS+\nSS5I8q22r7xj2Dlp7kuyKMk3k5w17FzmIws9jeck4MBhJ6F54U7gLVW1N7A/cGSSfYack+amO4Bn\nVtUTgBXAgUn2H3JOmvveBFw27CTmKws9jamqzgduHHYemvuq6pqq+kZ7fivdF/Juw81Kc1F1ftpe\nbtceHiiucSVZCjwf+PCwc5mvLPQkzZgky4AnAl8fbiaaq1o33DrgOuDcqnJf0UT+FvgT4FfDTmS+\nstCTNCOSPAA4HXhzVf1k2Plobqqqu6pqBbAU2C/JY4edk+amJC8Arquqi4ady3xmoSdp2pJsR1fk\nfayq/nnY+Wjuq6qbgS/hscAa39OAFybZAJwGPDPJPw03pfnHQk/StCQJ8BHgsqr6m2Hno7kryZIk\nO7Xn2wPPBr473Kw0V1XVW6tqaVUtAw4F/r2qXj7ktOYdCz2NKcmpwFeBRyfZmOSIYeekOetpwCvo\n/tte1x7PG3ZSmpN2Bb6Y5GLgQrpj9LxkhjSLvDOGJElST9miJ0mS1FMWepIkST1loSdJktRTFnqS\nJEk9ZaEnSZLUUxZ6kgQkuatdGubSJN9K8r+S3KsNW5nk/e35fZL8Wxv3ZUl+q02zLsluST69lct/\nZZK/a89flGSfmVs7SQvV4mEnIElzxG3t1lwkeQjwcWBH4OiqWgusbeM9EdhuYNwPAn9dVf/Yhh8y\nA7m8CDgL+M4MzEvSAmaLniSNUlXXAauBN6bzjCRntQLwn4AVrQXvdcBLgT9L8rEky5JcApBkUZK/\nTvLtJBcn+YMW35Bkl/Z8ZZIvDS47yW8CLwT+qi3jEUm+MTB8eRLv/SlpSmzRk6QxVNUVrev2IQOx\n65K8BvijqnoBQJKnAmdV1aeTLBuYxWpgL+CJVXVnkgdNcbn/meTMkXm2ZdySZEVVrQNeBZw0/TWU\ntBDYoidJ48s0pn028MGquhOgqm6cxrw+DLwqySLgZXTdypI0KQs9SRpDkocDdwHXbe0sgLHuMXkn\nd3/33neK8zodOAh4AXBRVd2wlTlJWmAs9CRplCRLgA8Cf1dbf0PwLwCvT7K4zXOk63YDsG97/jvj\nTHsrsMPIi6q6HTgHOB74x3GmkaR7sNCTpM72I5dXAf6NrlB7xzTm92Hgh8DFSb4F/G6LvwN4X5L/\nS9diOJbTgD9O8s0kj2ixj9G1EH5hGjlJWmCy9f+sSpK2lSR/BOxYVX867FwkzR+edStJc1ySzwCP\nAJ457FwkzS+26EmSJPWUx+hJkiT1lIWeJElST1noSZIk9ZSFniRJUk9Z6EmSJPWUhZ4kSVJP/f9x\nqE0RR+2chQAAAABJRU5ErkJggg==\n",
      "text/plain": [
       "<matplotlib.figure.Figure at 0x127437ba8>"
      ]
     },
     "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": [
    "With that, we can mine nononces of varied difficulties."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 221,
   "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.\n",
    "\n",
    "Now we can create a block."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 222,
   "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 = sha256(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": 223,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "genesis_block : 1162dce8ffec3acf13ce61109f121922eee8cceeea4784aa9d90dc6ec0e0fa92 with fee=0\n",
      "block1        : 1175461e273005dcd2510755f1b79fa6d92016430037a6532face0ea65548621 with fee=0.0\n",
      "block2        : 11812dcc657fb9e5862dbc146606ae4dad95c50739dcde5941eda26b7535c01a with fee=1.0\n"
     ]
    }
   ],
   "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\n",
    "\n",
    "\"\"\" EXAMPLE \"\"\"\n",
    "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": 224,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 224,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "verify_block(block1, genesis_block)\n",
    "verify_block(block2, genesis_block)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 225,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Alice  has 15.00 units\n",
      "Bob    has 1.00 units\n",
      "Walter has 59.00 units\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 units\" % 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 units\" % 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 units\" % compute_balance(walter.address, transactions))"
   ]
  }
 ],
 "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.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}