7_Reclaiming_Disk_Space_回收硬盘空间.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 7 回收硬盘空间（Reclaiming Disk Space）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 原文与翻译\n",
    "\n",
    "> Once the latest transaction in a coin is buried under enough blocks, the spent transactions before it can be discarded to save disk space. To facilitate this without breaking the block's hash, transactions are hashed in a Merkle Tree **[2][5][7]** , with only the root included in the block's hash. Old blocks can then be compacted by stubbing off branches of the tree. The interior hashes do not need to be stored.\n",
    "> \n",
    "> 如果一枚硬币最近发生的交易发生在足够多的区块之前，那么，这笔交易之前该硬币的花销交易记录可以被丢弃 —— 目的是为了节省磁盘空间。为了在不破坏该区块的哈希的前提下实现此功能，交易记录的哈希将被纳入一个 Merkle 树 **[2][5][7]** 之中，而只有树根被纳入该区块的哈希之中。通过砍掉树枝方法，老区块即可被压缩。内部的哈希并不需要被保存。\n",
    "> \n",
    "> ![merkle_tree_in_7](pics/merkle_tree_in_7.svg)\n",
    "> \n",
    "> A block header with no transactions would be about 80 bytes. If we suppose blocks are generated every 10 minutes, 80 bytes * 6 * 24 * 365 = 4.2MB per year. With computer systems typically selling with 2GB of RAM as of 2008, and Moore's Law predicting current growth of 1.2GB per year, storage should not be a problem even if the block headers must be kept in memory.\n",
    "> \n",
    "> 一个没有任何交易记录的区块头大约是 80 个字节。假设每十分钟产生一个区块，80 字节乘以 6 乘以 24 乘以 365，等于每年 4.2M。截止 2008 年，大多数在售的计算机配有 2GB 内存，而按照摩尔定律的预测，每年会增加 1.2 GB，即便是区块头必须存储在内存之中也不会是什么问题。\n",
    "> \n",
    "> **[2]:** Design of a secure timestamping service with minimal trust requirements Henri Massias, Xavier Serret-Avila, Jean-Jacques Quisquater 20th Symposium on Information Theory in the Benelux (1999-05) http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.13.6228\n",
    "> \n",
    "> **[5]:** Secure names for bit-strings Stuart Haber, W. Scott Stornetta Proceedings of the 4th ACM conference on Computer and communications security - CCS ’97(1997) https://doi.org/dtnrf6 DOI: 10.1145/266420.266430\n",
    "> \n",
    "> **[7]:** Protocols for Public Key Cryptosystems Ralph C. Merkle 1980 IEEE Symposium on Security and Privacy (1980-04) https://doi.org/bmvbd6 DOI: 10.1109/sp.1980.10006"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Python 实现 Merkle Tree\n",
    "\n",
    "【Python 知识点】 点击链接跳转至《自学是门手艺》相应知识点\n",
    "\n",
    "- [函数](https://github.com/selfteaching/the-craft-of-selfteaching/blob/master/Part.2.D.1-args.ipynb)\n",
    "- [类](https://github.com/selfteaching/the-craft-of-selfteaching/blob/master/Part.3.B.2.classes-2.ipynb)\n",
    "- [数据容器](https://github.com/selfteaching/the-craft-of-selfteaching)\n",
    "\n",
    "本实例改自 https://github.com/JaeDukSeo/Simple-Merkle-Tree-in-Python"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "from IPython.display import display, Markdown\n",
    "\n",
    "# 0. Import the needed library\n",
    "import hashlib,json\n",
    "from collections import OrderedDict\n",
    "\n",
    "# 1. Declare the class trees\n",
    "class Jae_MerkTree:\n",
    "\n",
    "    # 2. Initiate the class object\n",
    "    def __init__(self,listoftransaction=None):\n",
    "        self.listoftransaction = listoftransaction\n",
    "        self.past_transaction = OrderedDict()\n",
    "\n",
    "    # 3. Create the Merkle Tree  \n",
    "    def create_tree(self):\n",
    "\n",
    "        # 3.0 Continue on the declaration\n",
    "        listoftransaction = self.listoftransaction\n",
    "        past_transaction = self.past_transaction\n",
    "        temp_transaction = []\n",
    "\n",
    "        # 3.1 Loop until the list finishes\n",
    "        for index in range(0,len(listoftransaction),2):\n",
    "\n",
    "            # 3.2 Get the most left element \n",
    "            current = listoftransaction[index]\n",
    "\n",
    "            # 3.3 If there is still index left get the right of the left most element\n",
    "            if index+1 != len(listoftransaction):\n",
    "                current_right = listoftransaction[index+1]\n",
    "\n",
    "            # 3.4 If we reached the limit of the list then make a empty string\n",
    "            else:\n",
    "                current_right = ''\n",
    "\n",
    "            # 3.5 Apply the Hash 256 function to the current values\n",
    "            current_hash = hashlib.sha256(current.encode())\n",
    "\n",
    "            # 3.6 If the current right hash is not a '' <- empty string\n",
    "            if current_right != '':\n",
    "                current_right_hash = hashlib.sha256(current_right.encode())\n",
    "\n",
    "            # 3.7 Add the Transaction to the dictionary \n",
    "            past_transaction[listoftransaction[index]] = current_hash.hexdigest()\n",
    "\n",
    "            # 3.8 If the next right is not empty\n",
    "            if current_right != '':\n",
    "                past_transaction[listoftransaction[index+1]] = current_right_hash.hexdigest()\n",
    "\n",
    "            # 3.9 Create the new list of transaction\n",
    "            if current_right != '':\n",
    "                temp_transaction.append(current_hash.hexdigest() + current_right_hash.hexdigest())\n",
    "\n",
    "            # 3.01 If the left most is an empty string then only add the current value\n",
    "            else:\n",
    "                temp_transaction.append(current_hash.hexdigest())\n",
    "\n",
    "        # 3.02 Update the variables and rerun the function again \n",
    "        if len(listoftransaction) != 1:\n",
    "            self.listoftransaction = temp_transaction\n",
    "            self.past_transaction = past_transaction\n",
    "\n",
    "            # 3.03 Call the function repeatly again and again until we get the root \n",
    "            self.create_tree()\n",
    "\n",
    "    # 4. Return the past Transaction \n",
    "    def get_past_transacion(self):\n",
    "        return self.past_transaction\n",
    "\n",
    "    # 5. Get the root of the transaction\n",
    "    def get_root_leaf(self):\n",
    "        last_key = list(self.past_transaction.keys())[-1]\n",
    "        return self.past_transaction[last_key]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/markdown": [
       "**First Example - Even number of transaction Merkel Tree**"
      ],
      "text/plain": [
       "<IPython.core.display.Markdown object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/markdown": [
       "**Final root of the tree:** \n",
       "\n",
       "58c89d709329eb37285837b042ab6ff72c7c8f74de0446b091b6a0131c102cfd"
      ],
      "text/plain": [
       "<IPython.core.display.Markdown object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/markdown": [
       "**merkle tree:** \n",
       "\n",
       "{\n",
       "    \"a\": \"ca978112ca1bbdcafac231b39a23dc4da786eff8147c4e72b9807785afee48bb\",\n",
       "    \"b\": \"3e23e8160039594a33894f6564e1b1348bbd7a0088d42c4acb73eeaed59c009d\",\n",
       "    \"c\": \"2e7d2c03a9507ae265ecf5b5356885a53393a2029d241394997265a1a25aefc6\",\n",
       "    \"d\": \"18ac3e7343f016890c510e93f935261169d9e3f565436429830faf0934f4f8e4\",\n",
       "    \"ca978112ca1bbdcafac231b39a23dc4da786eff8147c4e72b9807785afee48bb3e23e8160039594a33894f6564e1b1348bbd7a0088d42c4acb73eeaed59c009d\": \"62af5c3cb8da3e4f25061e829ebeea5c7513c54949115b1acc225930a90154da\",\n",
       "    \"2e7d2c03a9507ae265ecf5b5356885a53393a2029d241394997265a1a25aefc618ac3e7343f016890c510e93f935261169d9e3f565436429830faf0934f4f8e4\": \"d3a0f1c792ccf7f1708d5422696263e35755a86917ea76ef9242bd4a8cf4891a\",\n",
       "    \"62af5c3cb8da3e4f25061e829ebeea5c7513c54949115b1acc225930a90154dad3a0f1c792ccf7f1708d5422696263e35755a86917ea76ef9242bd4a8cf4891a\": \"58c89d709329eb37285837b042ab6ff72c7c8f74de0446b091b6a0131c102cfd\"\n",
       "}"
      ],
      "text/plain": [
       "<IPython.core.display.Markdown object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "# a) Create the new class of Jae_MerkTree\n",
    "Jae_Tree = Jae_MerkTree()\n",
    "\n",
    "# b) Give list of transaction\n",
    "transaction = ['a','b','c','d']\n",
    "\n",
    "# c) pass on the transaction list \n",
    "Jae_Tree.listoftransaction = transaction\n",
    "\n",
    "# d) Create the Merkle Tree transaction\n",
    "Jae_Tree.create_tree()\n",
    "\n",
    "# e) Retrieve the transaction \n",
    "past_transaction = Jae_Tree.get_past_transacion()\n",
    "\n",
    "# f) Get the last transaction and print all \n",
    "display(Markdown(\"**First Example - Even number of transaction Merkel Tree**\"))\n",
    "display(Markdown('**Final root of the tree:** \\n\\n' + Jae_Tree.get_root_leaf()))\n",
    "display(Markdown(\"**merkle tree:** \\n\\n\" + json.dumps(past_transaction, indent=4)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**【小练习】**\n",
    "\n",
    "基于上面的代码，尝试绘制可视化的 Merkle Tree。"
   ]
  }
 ],
 "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.7.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}