.. DO NOT EDIT. .. THIS FILE WAS AUTOMATICALLY GENERATED BY SPHINX-GALLERY. .. TO MAKE CHANGES, EDIT THE SOURCE PYTHON FILE: .. "api/gallery/structures/timestamps/plot_02_merkle_batching.py" .. LINE NUMBERS ARE GIVEN BELOW. .. only:: html .. note:: :class: sphx-glr-download-link-note :ref:`Go to the end ` to download the full example code or to run this example in your browser via JupyterLite. .. rst-class:: sphx-glr-example-title .. _sphx_glr_api_gallery_structures_timestamps_plot_02_merkle_batching.py: Batching timestamps with a Merkle tree (Bayer, Haber and Stornetta 1993) ======================================================================== Linking every document into a chain costs one record per document. Bayer, Haber and Stornetta batched them: put a round's documents in a Merkle tree and timestamp only the root. Each document keeps a short proof linking it to that root. This is exactly how a block commits to its transactions. What to look for ---------------- One 32-byte root timestamps a thousand documents, and each proof grows only logarithmically. A block's header commits to its transactions the same way. The history behind this experiment: :doc:`/history/structures_breakthroughs`. See :doc:`/exercises/structures` for a worked solution to the exercise. .. GENERATED FROM PYTHON SOURCE LINES 21-23 Timestamp a round of documents with one root -------------------------------------------- .. GENERATED FROM PYTHON SOURCE LINES 23-35 .. code-block:: Python import matplotlib.pyplot as plt import blockchainkit as bk documents = [f"contract {i}".encode() for i in range(1000)] tree = bk.structures.MerkleTree(documents) stamp = bk.structures.BlockHeader(merkle_root=tree.root, height=0, timestamp=1993, difficulty=0) proof = tree.proof(617) assert bk.structures.verify_proof(documents[617], proof, stamp.merkle_root) size = sum(32 for sibling in proof.siblings if sibling is not None) print(f"1000 documents, one root; proof for contract 617: {size} bytes") .. rst-class:: sphx-glr-script-out .. code-block:: none 1000 documents, one root; proof for contract 617: 320 bytes .. GENERATED FROM PYTHON SOURCE LINES 36-38 A block does the same for its transactions ------------------------------------------ .. GENERATED FROM PYTHON SOURCE LINES 38-46 .. code-block:: Python alice = bk.crypto.public_key(7) bob = bk.structures.address(bk.crypto.public_key(11)) payments = tuple( bk.structures.Transaction(alice, bob, 1, n).signed(7, signing_nonce=100 + n) for n in range(5) ) block = bk.structures.Block(transactions=payments, difficulty=0) assert block.merkle_root == bk.structures.MerkleTree(tx.to_bytes() for tx in payments).root .. GENERATED FROM PYTHON SOURCE LINES 47-49 Records needed: one per document, or one per round -------------------------------------------------- .. GENERATED FROM PYTHON SOURCE LINES 49-59 .. code-block:: Python counts = [2**k for k in range(1, 15)] proof_bytes = [32 * (n - 1).bit_length() for n in counts] fig, ax = plt.subplots(figsize=(7, 4)) ax.loglog(counts, counts, "--", label="linked records (one per document)") ax.loglog(counts, [1] * len(counts), "-", label="batched records (one per round)") ax.loglog(counts, proof_bytes, "o-", label="proof bytes per document") ax.set(xlabel="documents per round", title="Batching: one timestamp, logarithmic proofs") ax.legend() fig.tight_layout() .. image-sg:: /api/gallery/structures/timestamps/images/sphx_glr_plot_02_merkle_batching_001.png :alt: Batching: one timestamp, logarithmic proofs :srcset: /api/gallery/structures/timestamps/images/sphx_glr_plot_02_merkle_batching_001.png :class: sphx-glr-single-img .. GENERATED FROM PYTHON SOURCE LINES 60-64 Exercise -------- OpenTimestamps batches documents worldwide into one Bitcoin transaction per round. Estimate the proof length for a round of a million documents. .. rst-class:: sphx-glr-timing **Total running time of the script:** (0 minutes 0.401 seconds) .. _sphx_glr_download_api_gallery_structures_timestamps_plot_02_merkle_batching.py: .. only:: html .. container:: sphx-glr-footer sphx-glr-footer-example .. container:: lite-badge .. image:: images/jupyterlite_badge_logo.svg :target: ../../../../lite/lab/index.html?path=api/gallery/structures/timestamps/plot_02_merkle_batching.ipynb :alt: Launch JupyterLite :width: 150 px .. container:: sphx-glr-download sphx-glr-download-jupyter :download:`Download Jupyter notebook: plot_02_merkle_batching.ipynb ` .. container:: sphx-glr-download sphx-glr-download-python :download:`Download Python source code: plot_02_merkle_batching.py ` .. container:: sphx-glr-download sphx-glr-download-zip :download:`Download zipped: plot_02_merkle_batching.zip ` .. only:: html .. rst-class:: sphx-glr-signature `Gallery generated by Sphinx-Gallery `_