.. DO NOT EDIT. .. THIS FILE WAS AUTOMATICALLY GENERATED BY SPHINX-GALLERY. .. TO MAKE CHANGES, EDIT THE SOURCE PYTHON FILE: .. "api/gallery/structures/merkle/plot_01_merkle_proofs.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_merkle_plot_01_merkle_proofs.py: Merkle trees: authenticate one item with a short proof (Merkle 1979) ==================================================================== A root commits to an ordered collection. An inclusion proof reveals the sibling digests needed to recompute that root, rather than the full dataset. The verifier must already trust the root by some independent mechanism. What to look for ---------------- Watch a genuine membership proof pass and an altered payment fail. In the size plot, proof length grows much more slowly than the number of records. Read cells in order. An ``assert`` that produces no output has passed. The final exercise asks you to change an input and explain the result. 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 23-36 .. code-block:: Python import matplotlib.pyplot as plt import blockchainkit as bk from blockchainkit.structures.visualizers import plot_merkle_tree, plot_proof_trace leaves = [b"Alice pays Bob", b"Bob pays Carol", b"Carol pays Dave"] tree = bk.structures.MerkleTree(leaves) proof = tree.proof(1) assert bk.structures.verify_proof(leaves[1], proof, tree.root) assert not bk.structures.verify_proof(b"Bob pays Mallory", proof, tree.root) print("Root:", tree.root.hex()) print("Proof:", proof) .. rst-class:: sphx-glr-script-out .. code-block:: none Root: 66f70ae9b2f3e848a49b5cbec27b9f237bb7a2bedb1cbec523441988d8ee78d4 Proof: MerkleProof(index=1, leaf_count=3, siblings=(b'\x17au\x82X/\xf1\x8d,\xc0\xc5\xb2\x0e\xdd\x98*\xfd\xd6\xe5\xc4\xd8\xce\xaf \xdb>\xc5\xeae\xafU7', b'Cv1\xb4\xca\xb8\xb9\x88 \x95:1)i\x07\xe16\x93\xb0\x7fWf\xfb>\x9b\xc8\xd6\xbc\x10U\xf8\x17')) .. GENERATED FROM PYTHON SOURCE LINES 37-41 Shape is part of the commitment ------------------------------- Our convention promotes odd nodes and commits the count into the root. It does not duplicate odd leaves, and is intentionally not Bitcoin's format. .. GENERATED FROM PYTHON SOURCE LINES 41-44 .. code-block:: Python assert tree.root != bk.structures.MerkleTree(leaves + [leaves[-1]]).root print("Last leaf's missing sibling is represented explicitly:", tree.proof(2).siblings[0]) .. rst-class:: sphx-glr-script-out .. code-block:: none Last leaf's missing sibling is represented explicitly: None .. GENERATED FROM PYTHON SOURCE LINES 45-61 .. code-block:: Python sizes = [2**power for power in range(1, 11)] proof_bytes = [] for size in sizes: sample = bk.structures.MerkleTree(str(i).encode() for i in range(size)) proof_bytes.append(sum(32 for sibling in sample.proof(0).siblings if sibling is not None)) fig, ax = plt.subplots(figsize=(7, 4)) ax.plot(sizes, proof_bytes, "o-", label="Sibling hashes only") ax.set( xscale="log", xlabel="Number of leaves", ylabel="Proof digest bytes", title="Logarithmic inclusion proofs", ) ax.legend() fig.tight_layout() .. image-sg:: /api/gallery/structures/merkle/images/sphx_glr_plot_01_merkle_proofs_001.png :alt: Logarithmic inclusion proofs :srcset: /api/gallery/structures/merkle/images/sphx_glr_plot_01_merkle_proofs_001.png :class: sphx-glr-single-img .. GENERATED FROM PYTHON SOURCE LINES 62-67 Exercise -------- Change the leaf index or leaf count in the proof and check verification. Explain why inclusion in a committed list does not establish that a payment was authorized, funded, or finalized by a consensus protocol. .. GENERATED FROM PYTHON SOURCE LINES 69-74 Trace one proof from its leaf to the trusted root ------------------------------------------------- Index 1 is a right child: its sibling goes on the left before hashing. At the next level our node is on the left, so the order reverses. The final step binds the leaf count before comparing with the trusted root. .. GENERATED FROM PYTHON SOURCE LINES 74-80 .. code-block:: Python trace = bk.structures.trace_proof(leaves[1], proof, tree.root) assert trace.valid and [step.side for step in trace.steps] == ["left", "right"] fig, (tree_ax, table_ax) = plt.subplots(2, 1, figsize=(9, 6), height_ratios=[1.2, 1]) plot_merkle_tree(tree, highlight=1, ax=tree_ax) plot_proof_trace(trace, ax=table_ax) fig.tight_layout() .. image-sg:: /api/gallery/structures/merkle/images/sphx_glr_plot_01_merkle_proofs_002.png :alt: Merkle tree (digest prefixes): proof for leaf 1 sends the orange siblings, A Merkle proof is a recipe for reconstructing the root :srcset: /api/gallery/structures/merkle/images/sphx_glr_plot_01_merkle_proofs_002.png :class: sphx-glr-single-img .. rst-class:: sphx-glr-timing **Total running time of the script:** (0 minutes 0.489 seconds) .. _sphx_glr_download_api_gallery_structures_merkle_plot_01_merkle_proofs.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/merkle/plot_01_merkle_proofs.ipynb :alt: Launch JupyterLite :width: 150 px .. container:: sphx-glr-download sphx-glr-download-jupyter :download:`Download Jupyter notebook: plot_01_merkle_proofs.ipynb ` .. container:: sphx-glr-download sphx-glr-download-python :download:`Download Python source code: plot_01_merkle_proofs.py ` .. container:: sphx-glr-download sphx-glr-download-zip :download:`Download zipped: plot_01_merkle_proofs.zip ` .. only:: html .. rst-class:: sphx-glr-signature `Gallery generated by Sphinx-Gallery `_