Blockchain.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<div style=\"text-align: right\">Paul Novaes<br>August 2018</div> \n",
    "\n",
    "# Blockchain\n",
    "\n",
    "This notebook explains the basics of Blockchain by giving a simplified implementation that captures the most important concepts.\n",
    "\n",
    "A blockchain is a list of blocks, each one containing a piece of data. The blockchain is distributed (replicated) across nodes in a peer-to-peer network. Blocks can be appended to the blockchain, but cannot be removed or tampered, as long as more than 50% of the computational power belongs to honest parties.\n",
    "\n",
    "## Block\n",
    "\n",
    "In Blockchain, a block is a record that has some data and the hash of the previous block in the chain. This way, blocks are ordered, by date of insertion, within the blockchain."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import hashlib\n",
    "\n",
    "class BasicBlock:\n",
    "    def __init__(self, data, previous_block_hash):\n",
    "        self.data = data\n",
    "        self.previous_block_hash = previous_block_hash\n",
    "\n",
    "    def get_hash(self):\n",
    "        record = self.data + self.previous_block_hash\n",
    "        return hashlib.sha256(record.encode()).hexdigest()\n",
    "    \n",
    "    def __str__(self):\n",
    "        return 'data: ' + self.data \\\n",
    "             + '\\nprevious_block_hash: ' + self.previous_block_hash \\\n",
    "             + '\\nhash: ' + self.get_hash()\n",
    "    \n",
    "    def __eq__(self, other):\n",
    "        # This is not entirely correct but good enough for our needs.\n",
    "        return self.get_hash() == other.get_hash()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Genesis Block\n",
    "\n",
    "The initial block of the blockchain is called the genesis block and does not have a previous block."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Genesis Block:\n",
      "\n",
      "data: The Times 03/Jan/2009 Chancellor on brink of second bailout for banks\n",
      "previous_block_hash: n/a\n",
      "hash: 6b6e12db2b97827a703cac00af905fd696aae093089f79a1be1d711e74b06397\n"
     ]
    }
   ],
   "source": [
    "genesis_data = 'The Times 03/Jan/2009 Chancellor on brink of second bailout for banks'\n",
    "genesis_previous_block_hash = 'n/a'\n",
    "basic_genesis_block = BasicBlock(genesis_data, genesis_previous_block_hash)\n",
    "\n",
    "print(\"Genesis Block:\\n\")\n",
    "print(basic_genesis_block)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Chain\n",
    "\n",
    "A chain, or blockchain, is an array of blocks that starts with a genesis block and such that the \"previous_block_hash\" field of block at index $i + 1$ matches the hash of block at index $i$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "class BasicChain:\n",
    "    def __init__(self, genesis_block):\n",
    "        self.blocks = [genesis_block]\n",
    "        \n",
    "    def add_block(self, block):\n",
    "        if block.previous_block_hash != self.blocks[-1].get_hash():\n",
    "            print('Cannot add block:')\n",
    "            print('hash:', self.blocks[-1].get_hash())\n",
    "            print('previous_block_hash:', block.previous_block_hash)\n",
    "            return\n",
    "        self.blocks.append(block)\n",
    "\n",
    "    def __str__(self):\n",
    "        chain_str = 'Blockchain:\\n'\n",
    "        i = 0\n",
    "        for block in self.blocks:\n",
    "            chain_str += '\\nblock ' + str(i)\n",
    "            chain_str += '\\n' + str(block) + '\\n'\n",
    "            i += 1\n",
    "        return chain_str"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For example:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Blockchain:\n",
      "\n",
      "block 0\n",
      "data: The Times 03/Jan/2009 Chancellor on brink of second bailout for banks\n",
      "previous_block_hash: n/a\n",
      "hash: 6b6e12db2b97827a703cac00af905fd696aae093089f79a1be1d711e74b06397\n",
      "\n",
      "block 1\n",
      "data: Hello\n",
      "previous_block_hash: 6b6e12db2b97827a703cac00af905fd696aae093089f79a1be1d711e74b06397\n",
      "hash: a6c7a932f965a1995340021e5bbedcbf21a8ed212784f03deb2bc75368e0de63\n",
      "\n",
      "block 2\n",
      "data: Hola\n",
      "previous_block_hash: a6c7a932f965a1995340021e5bbedcbf21a8ed212784f03deb2bc75368e0de63\n",
      "hash: fc2c10ae7cfa361ae6515b650a0d264ccadb554e6f4d894fdb6cbf9af6c6122a\n",
      "\n"
     ]
    }
   ],
   "source": [
    "basic_chain = BasicChain(basic_genesis_block)\n",
    "\n",
    "block_0 = basic_chain.blocks[0]\n",
    "block_1 = BasicBlock('Hello', block_0.get_hash())\n",
    "block_2 = BasicBlock('Hola', block_1.get_hash())\n",
    "\n",
    "basic_chain.add_block(block_1)\n",
    "basic_chain.add_block(block_2)\n",
    "\n",
    "print(basic_chain)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Chain Validation\n",
    "\n",
    "Whoever has a blockchain can (and should) validate it to make sure it is correct."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "def validate_basic_chain(chain, genesis_block):\n",
    "    block_count = len(chain.blocks)\n",
    "    if block_count == 0:\n",
    "        print('Empty chain!')\n",
    "        return False\n",
    "    block_0 = chain.blocks[0]\n",
    "    if block_0 != genesis_block:\n",
    "        print('Incorrect genesis block!')\n",
    "        print(block_0)\n",
    "        print(genesis_block)\n",
    "        return False\n",
    "    for i in range(1, len(chain.blocks)):\n",
    "        if chain.blocks[i - 1].get_hash() != chain.blocks[i].previous_block_hash:\n",
    "            print('Incorrect chaining!')\n",
    "            return False\n",
    "    return True"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For example:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "validate_basic_chain(basic_chain, basic_genesis_block)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "But if we try to change the data:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Incorrect chaining!\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "basic_chain.blocks[1].data = 'Bonjour'\n",
    "validate_basic_chain(basic_chain, basic_genesis_block)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Chain tampering\n",
    "\n",
    "Unfortunately, it is possible to tamper a chain by recomputing hashes:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Blockchain:\n",
      "\n",
      "block 0\n",
      "data: The Times 03/Jan/2009 Chancellor on brink of second bailout for banks\n",
      "previous_block_hash: n/a\n",
      "hash: 6b6e12db2b97827a703cac00af905fd696aae093089f79a1be1d711e74b06397\n",
      "\n",
      "block 1\n",
      "data: Bonjour\n",
      "previous_block_hash: 6b6e12db2b97827a703cac00af905fd696aae093089f79a1be1d711e74b06397\n",
      "hash: cc60dbae9dec5a899a5cd0abc2c16df3d3b97f846dbfb753a7030a968efb94b3\n",
      "\n",
      "block 2\n",
      "data: Hello\n",
      "previous_block_hash: cc60dbae9dec5a899a5cd0abc2c16df3d3b97f846dbfb753a7030a968efb94b3\n",
      "hash: 4bf40e3a1d3ef04d0800abf4ca7301e86b450b266682a6caf5d4a9af4e90d954\n",
      "\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "basic_chain.blocks[1].data = 'Bonjour'\n",
    "basic_chain.blocks[1].previous_block_hash = basic_chain.blocks[0].get_hash()\n",
    "basic_chain.blocks[2].data = 'Hello'\n",
    "basic_chain.blocks[2].previous_block_hash = basic_chain.blocks[1].get_hash()\n",
    "print(basic_chain)\n",
    "validate_basic_chain(basic_chain, basic_genesis_block)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Block and Chain Revisited\n",
    "\n",
    "To make it more difficult to tamper a chain, we want to make producing valid blocks more difficult.\n",
    "\n",
    "To produce a valid block one has to compute a hash but this is straightforward. But, because the hash used in Blockchain (SHA-256) is a one-way function, finding a block with a given hash is very difficult.\n",
    "\n",
    "Blockchain adds to the data and previous_block_hash fields of a block another field called 'nonce'. One can choose any value for nonce as long as the hash of the block (that includes these 3 fields) starts with a given number of 0's.\n",
    "\n",
    "To produce a valid block, one has to find such a value of nonce. This is an arbitrary, seemingly vacuous, problem whose only goal is to make producing valid blocks more difficult."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Block(BasicBlock):\n",
    "    def __init__(self, data, previous_block_hash, nonce):\n",
    "        BasicBlock.__init__(self, data, previous_block_hash)\n",
    "        self.nonce = nonce\n",
    "\n",
    "    def compute_hash(data, previous_block_hash, nonce):\n",
    "        record = data + previous_block_hash + str(nonce)\n",
    "        return hashlib.sha256(record.encode()).hexdigest()\n",
    "    \n",
    "    def get_hash(self):\n",
    "        return Block.compute_hash(self.data, self.previous_block_hash, self.nonce)\n",
    "\n",
    "    def __str__(self):\n",
    "        block_str = BasicBlock.__str__(self)\n",
    "        return block_str + '\\nnonce: ' + str(self.nonce)\n",
    "        \n",
    "class Chain(BasicChain):\n",
    "    def __init__(self, genesis_block, difficulty = 5):\n",
    "        BasicChain.__init__(self, genesis_block)\n",
    "        self.blocks = [genesis_block]\n",
    "        self.difficulty = difficulty\n",
    "        \n",
    "def validate_chain(chain, genesis_block):\n",
    "    validated = validate_basic_chain(chain, genesis_block)\n",
    "    if not validated:\n",
    "        return False\n",
    "    zeroes = ''.zfill(chain.difficulty)\n",
    "    for block in chain.blocks:\n",
    "        if block.get_hash()[:chain.difficulty] != zeroes:\n",
    "            print('Incorrect nonce!')\n",
    "            return False\n",
    "    return True        "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Mining\n",
    "\n",
    "Anybody, with enough computing power and/or luck, can solve the hashing problem and produce a legal block. This a called __mining__ because typically it requires a big deal of computational power and energy."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Blockchain:\n",
      "\n",
      "block 0\n",
      "data: The Times 03/Jan/2009 Chancellor on brink of second bailout for banks\n",
      "previous_block_hash: n/a\n",
      "hash: 0000081aa36c9517b5676ff853ec4ebeca9dd19dd8499785a5589593950c8a90\n",
      "nonce: 361742\n",
      "\n",
      "block 1\n",
      "data: Hello\n",
      "previous_block_hash: 0000081aa36c9517b5676ff853ec4ebeca9dd19dd8499785a5589593950c8a90\n",
      "hash: 00000f20e356a372d6ca7c498c472437b16e12b612dc803f25055dd29a54a96e\n",
      "nonce: 1904167\n",
      "\n",
      "block 2\n",
      "data: Hola\n",
      "previous_block_hash: 00000f20e356a372d6ca7c498c472437b16e12b612dc803f25055dd29a54a96e\n",
      "hash: 000008887b16f14d555708b9151735d053d671439af4f036a471dc045534dbb9\n",
      "nonce: 237019\n",
      "\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def compute_nonce(data, previous_block_hash, difficulty = 5):\n",
    "    nonce = 0\n",
    "    zeroes = ''.zfill(difficulty)\n",
    "    while True:\n",
    "        hash = Block.compute_hash(data, previous_block_hash, nonce)\n",
    "        if hash[:difficulty] == zeroes:\n",
    "            return nonce\n",
    "        nonce += 1\n",
    "        \n",
    "def mineBlock(chain, data):\n",
    "    previous_block_hash = chain.blocks[-1].get_hash()\n",
    "    nonce = compute_nonce(data, previous_block_hash)\n",
    "    return Block(data, previous_block_hash, nonce)\n",
    "\n",
    "nonce = compute_nonce(genesis_data, genesis_previous_block_hash)\n",
    "genesis_block = Block(genesis_data, genesis_previous_block_hash, nonce)\n",
    "chain = Chain(genesis_block)\n",
    "\n",
    "block_0 = chain.blocks[0]\n",
    "\n",
    "chain.add_block(mineBlock(chain, 'Hello'))\n",
    "chain.add_block(mineBlock(chain, 'Hola'))\n",
    "\n",
    "print(chain)\n",
    "\n",
    "validate_chain(chain, genesis_block)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Distributed Chain\n",
    "\n",
    "In Blockchain, the chain is typically distributed (replicated) across a __peer-to-peer network__. Anybody in the network can read and validate the chain. Anybody can participate in the mining process too, in proportion to their computation power.\n",
    "\n",
    "Data is added to the chain by the first miner to solve the hashing problem for that piece of data. Once a miner has mined a block, they distribute the block to the other nodes in the network. These nodes verify that the block is valid and they add it to their own chain.\n",
    "\n",
    "At any moment, chains across the network are nearly identical. The last block, or sometimes the last few blocks, may be different, because the nodes may receive validated block in different orders. When this happens, and a node discovers in the network a longer chain, they switch to that longer chain. The longer chain which, by construction, is the most expensive to produce, is considered to be the valid one. Blockchain is said to be based on __proof of work__. Eventually shorter chains die out and consensus is achieved.\n",
    "\n",
    "This means that dishonest nodes, without at least 50% of the computational power, cannot tamper the chain, and honest nodes can trust the data in the blockchain, esp. data that is not right at the end of the blockchain."
   ]
  }
 ],
 "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.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}