{ "info": { "author": "Vasyl Paliy", "author_email": "vpaliy97@gmail.com", "bugtrack_url": null, "classifiers": [ "Intended Audience :: Developers", "Operating System :: OS Independent", "Programming Language :: Python", "Programming Language :: Python :: 3", "Programming Language :: Python :: 3.4", "Programming Language :: Python :: 3.5", "Programming Language :: Python :: 3.6" ], "description": "# Merkle Trees\n\nMerkle trees are hash-based data structures used to validate large amounts of data in an efficient manner. This data structure is used to solve the previously time-consuming and computationally expensive problem of keeping data consistent across multiple computers. Prominent uses of a Merkle tree - and its variations- are in peer-to-peer networks such as Bitcoin, Ethereum, Git, and Tor.\n\n\n### Merkle Tree Diagram\n\nThis diagram illustrates a fully balanced Merkle tree. As you can guess from the illustration, the Merkle hash root maintains the integrity of the data. If any of the nodes are changed, or the order of the data items is changed, the Merkle hash root will be completely different. \n\n\n\n\nThis is what an \"artificially\" balanced tree looks like (a tree whose number of leaves is not a power of two):\n\n\n\nWe had to add an empty light-weight node in order to keep it balanced.\nTherefore, when we append a new leaf, we can just replace that empty node and recalculate the hash root.\n\n\n### Merkle Audit Proof\n\nAudit proof lets you verify that a specific data record is included in the database. Usually, the server maintaining the database provides the client with a proof that the record exists in that database. If a Merkle audit proof fails to produce a root hash that matches the Merkle root hash (which is obtained from a trusted authority), it means that the data record is not in the database.\n\nThe diagram below illustrates how you should construct an audit proof:\n\n\n\nIn this example, we need to provide a proof that the record `D` exists in the database.\nSince we already know the hash value of `D` (we can easily compute it), we will need `H-3` in order to compute `D-2`. Now, when we are able to compute `D-2`, we will need to get `D-1` in order to obtain the hash value of `T-1`, and so on...\nYou've got the gist, right? We only need to grab the sibling node and climb up the tree until we've reached the root. [This](https://github.com/vpaliy/merklelib/blob/master/merklelib/merkle.py#L468) implements everything described above.\n\n\n### Merkle Consistency Proof\n\nA Merkle consistency proof lets you verify that any two versions of a database are consistent: that is, the later version includes everything in the earlier version, in the same order, and all new entries come after the entries in the older version.\n\n\n\n## Usage\n\nInstall it:\n\n`pip install merklelib`\n\nor clone it:\n\n```\n$ git clone git clone https://github.com/vpaliy/merklelib.git\n```\n\nThis snippet demonstrates how to build a Merkle tree and verify leaf inclusion:\n\n```python\nimport string\nimport hashlib\n\nfrom merklelib import MerkleTree\n\n# a sample hash function\n# you can also omit it and the default hash function will be used\ndef hashfunc(value):\n return hashlib.sha256(value).hexdigest()\n\n\n# a list of all ASCII letters\ndata = list(string.ascii_letters)\n\n# build a Merkle tree for that list\ntree = MerkleTree(data, hashfunc)\n\n# generate an audit proof the letter A\nproof = tree.get_proof(hashfunc('A'))\n\n# now verify that A is in the tree\n# you can also pass in the hash value of 'A'\n# it will hash automatically if the user forgot to hash it\nif tree.verify_leaf_inclusion('A', proof):\n print('A is in the tree')\nelse:\n exit('A is not in the tree')\n```\n\nOr you may want to perform a consitency check (using `<`, `<=`, `>`, `>=` operators):\n\n(some code will be omitted)\n```python\ntree = MerkleTree(get_data())\n...\n...\n...\nnew_tree = MerkleTree(get_new_data())\n\n# check if the new tree contains the same items\n# and in the same order as the old version\nif tree <= new_tree:\n print('Versions are consistent')\nelse:\n exit('Versions are different')\n```\n\nAlternatively, you can use the `verify_tree_consitency` function for this:\n```python\n\nfrom merkelib import MerkleTree, verify_tree_consistency\n...\n...\n...\n# information that we need to provide\nold_hash_root = old_tree.merkle_hash\nold_tree_size = len(old_tree)\n\n# check if the new tree contains the same items\n# and in the same order as the old version\nif verify_tree_consistency(new_tree, old_hash_root, old_tree_size):\n print('Versions are consistent')\nelse:\n exit('Versions are different')\n```\n\n\nYou can build a Merkle tree and nicely display it in the terminal:\n\n```python\n from merklelib import MerkleTree, beautify\n\n\n transactions = get_transactions(user) # random data\n tree = MerkleTree(transactions)\n\n beautify(tree) # print the tree in the terminal\n```\n\nOutput:\n\n```\ne11a20bae8379fdc0ed560561ba33f30c877e0e95051aed5acebcb9806f6521f\n\u251c\u2500\u2500 862532e6a3c9aafc2016810598ed0cc3025af5640db73224f586b6f1138385f4\n\u2502 \u251c\u2500\u2500 fa13bb36c022a6943f37c638126a2c88fc8d008eb5a9fe8fcde17026807feae4\n\u2502 \u2502 \u251c\u2500\u2500 5feceb66ffc86f38d952786c6d696c79c2dbc239dd4e91b46729d73a27fb57e9\n\u2502 \u2502 \u2514\u2500\u2500 6b86b273ff34fce19d6b804eff5a3f5747ada4eaa22f1d49c01e52ddb7875b4b\n\u2502 \u2514\u2500\u2500 70311d9d203b2d7e4ff70d7fce219f82a4fcf73a110dc80187dfefb7c6e4bb87\n\u2502 \u251c\u2500\u2500 d4735e3a265e16eee03f59718b9b5d03019c07d8b6c51f90da3a666eec13ab35\n\u2502 \u2514\u2500\u2500 4e07408562bedb8b60ce05c1decfe3ad16b72230967de01f640b7e4729b49fce\n\u2514\u2500\u2500 f4685cb09ef9f1c86b2d8f544d89f1c1d3592a3654beb8feecad11e9545e0e72\n \u251c\u2500\u2500 67d62ee831ff99506ce1cd9435351408c3a845fca2dc0f34d085cdb51a37ec40\n \u2502 \u251c\u2500\u2500 4b227777d4dd1fc61c6f884f48641d02b4d121d3fd328cb08b5531fcacdabf8a\n \u2502 \u2514\u2500\u2500 ef2d127de37b942baad06145e54b0c619a1f22327b2ebbcfbec78f5564afe39d\n \u2514\u2500\u2500 ac6621607d32037664f03f92a4aae94d4c97f6bbcf438ff20509311681e6b259\n \u251c\u2500\u2500 e7f6c011776e8db7cd330b54174fd76f7d0216b612387a5ffcfb81e6f0919683\n \u2514\u2500\u2500 7902699be42c8a8e46fbbb4501726517e86b22c56a189f7625a6da49081b2451\n```\n\nYou can also export the output above as an image or a JSON file. This is how you'd do it:\n\n\n```python\n from merklelib import MerkleTree, export\n\n\n transactions = get_transactions(user) # random data\n tree = MerkleTree(transactions)\n\n export(tree, filename='transactions', ext='jpg')\n```\n\nDefault extension is always `.json.` You can also specify an absolute path.\n\nHowever, in order to be able to use the `export` function with images, you may need to install `graphviz` on your machine.\nHere is how you can do that for Mac and Ubuntu:\n\n### Mac\n\n`brew install graphviz`\n\n\n### Ubuntu\n\n`sudo apt-get install graphviz`\n\n\n\n## Benchmark\n\nI have included some basic benchmark code to measure performance. If you want to try it out, simply download the repository with:\n\n```\n$ git clone git clone https://github.com/vpaliy/merklelib.git\n$ cd merklelib\n```\n\nAnd run it with `python3` or `python2` (additional arguments are optional):\n\n```\n$ python3 benchmark --size=2048 -a=8\n\n Building: 0.016072 seconds.\n Appending: 0.000868 seconds.\n Tree size: 637401\n Number of leaves: 2056\n\n Audit proof verification times:\n Average time: 0.00014690807392996172 seconds.\n Total time: 0.304746 seconds.\n Longest time: 0.000325 seconds.\n Shortest time: 5.9e-05 seconds.\n\n Consitency proof verification times (2056 trees):\n Average time: 0.008714925583657588 seconds.\n Total time: 17.925458 seconds.\n Longest time: 0.035517 seconds.\n Shortest time: 9e-05 seconds.\n\n```\n\nThe above test provides the following results:\n - how long it takes to build a Merkle tree.\n - how long it takes append additional leaves.\n - how long it takes to verify every single leaf that is included in the tree.\n - how long it takes to prove that every possible sub-tree of the generated Merkle tree is consistent with the original one\n\n\nYou can also build your own benchmark. Here's a simple one that measure how long it takes to build a Merkle tree with 65536 leaves:\n\n```\n>>> import os\n>>> import timeit\n>>> from merklelib import MerkleTree\n>>> leaves = [os.urandom(2048) for i in range(2**16)]\n>>> def timeav(code, n=20):\n>>> return timeit.timeit(\n... code, setup=\"from __main__ import MerkleTree, leaves\", number=n)/n\n...\n# time taken to build the tree\n>>> print timeav(\"MerkleTree(leaves)\")\n0.70325\n\n```\n\n# Resources\n\n* [Understanding Merkle Trees - Why use them, who uses them, and how to use them](https://www.codeproject.com/Articles/1176140/%2FArticles%2F1176140%2FUnderstanding-Merkle-Trees-Why-use-them-who-uses-t)\n\n* [Certificate Transparency](https://tools.ietf.org/html/rfc6962#section-2.1.2)\n\n* [Merkle Tree Brilliant](https://brilliant.org/wiki/merkle-tree/)\n\n# License\n```\nMIT License\n\nCopyright (c) 2019 Vasyl Paliy\n\nPermission is hereby granted, free of charge, to any person obtaining a copy\nof this software and associated documentation files (the \"Software\"), to deal\nin the Software without restriction, including without limitation the rights\nto use, copy, modify, merge, publish, distribute, sublicense, and/or sell\ncopies of the Software, and to permit persons to whom the Software is\nfurnished to do so, subject to the following conditions:\n\nThe above copyright notice and this permission notice shall be included in all\ncopies or substantial portions of the Software.\n\nTHE SOFTWARE IS PROVIDED \"AS IS\", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR\nIMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,\nFITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE\nAUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER\nLIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,\nOUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE\nSOFTWARE.\n```\n\n\n", "description_content_type": "", "docs_url": null, "download_url": "", "downloads": { "last_day": -1, "last_month": -1, "last_week": -1 }, "home_page": "https://github.com/vpaliy/merkle-trees", "keywords": "", "license": "MIT", "maintainer": "", "maintainer_email": "", "name": "merklelib", "package_url": "https://pypi.org/project/merklelib/", "platform": "", "project_url": "https://pypi.org/project/merklelib/", "project_urls": { "Homepage": "https://github.com/vpaliy/merkle-trees" }, "release_url": "https://pypi.org/project/merklelib/1.0/", "requires_dist": [ "six", "future-fstrings", "anytree" ], "requires_python": ">=2.7", "summary": "Merkle tree and its variations for easier data verification.", "version": "1.0" }, "last_serial": 4671431, "releases": { "1.0": [ { "comment_text": "", "digests": { "md5": "e9941c05668b1fc51aeb3c06fdda67c7", "sha256": "f1b22ac0f21c26d61db1bbb377c368b6222bad62189ec3f9adb58c63d8a13b6b" }, "downloads": -1, "filename": "merklelib-1.0-py2.py3-none-any.whl", "has_sig": false, "md5_digest": "e9941c05668b1fc51aeb3c06fdda67c7", "packagetype": "bdist_wheel", "python_version": "py2.py3", "requires_python": ">=2.7", "size": 19348, "upload_time": "2019-01-08T05:15:11", "url": "https://files.pythonhosted.org/packages/30/bd/f81892ec0e1a264e89058132fce856c87722111e0d7078f0ba0f5df43daf/merklelib-1.0-py2.py3-none-any.whl" }, { "comment_text": "", "digests": { "md5": "6267024f035dafccdf387ed2bda65b16", "sha256": "ad8deb51552fa897f5bac48f13885b260159481cdf12cd1fccafe0b942f0da10" }, "downloads": -1, "filename": "merklelib-1.0.tar.gz", "has_sig": false, "md5_digest": "6267024f035dafccdf387ed2bda65b16", "packagetype": "sdist", "python_version": "source", "requires_python": ">=2.7", "size": 18557, "upload_time": "2019-01-08T05:15:13", "url": "https://files.pythonhosted.org/packages/94/5a/567cbe6c8425b0e625624f79b4f8e975d4d120dd392ec3fe0618fe10ce4e/merklelib-1.0.tar.gz" } ] }, "urls": [ { "comment_text": "", "digests": { "md5": "e9941c05668b1fc51aeb3c06fdda67c7", "sha256": "f1b22ac0f21c26d61db1bbb377c368b6222bad62189ec3f9adb58c63d8a13b6b" }, "downloads": -1, "filename": "merklelib-1.0-py2.py3-none-any.whl", "has_sig": false, "md5_digest": "e9941c05668b1fc51aeb3c06fdda67c7", "packagetype": "bdist_wheel", "python_version": "py2.py3", "requires_python": ">=2.7", "size": 19348, "upload_time": "2019-01-08T05:15:11", "url": "https://files.pythonhosted.org/packages/30/bd/f81892ec0e1a264e89058132fce856c87722111e0d7078f0ba0f5df43daf/merklelib-1.0-py2.py3-none-any.whl" }, { "comment_text": "", "digests": { "md5": "6267024f035dafccdf387ed2bda65b16", "sha256": "ad8deb51552fa897f5bac48f13885b260159481cdf12cd1fccafe0b942f0da10" }, "downloads": -1, "filename": "merklelib-1.0.tar.gz", "has_sig": false, "md5_digest": "6267024f035dafccdf387ed2bda65b16", "packagetype": "sdist", "python_version": "source", "requires_python": ">=2.7", "size": 18557, "upload_time": "2019-01-08T05:15:13", "url": "https://files.pythonhosted.org/packages/94/5a/567cbe6c8425b0e625624f79b4f8e975d4d120dd392ec3fe0618fe10ce4e/merklelib-1.0.tar.gz" } ] }