.. DO NOT EDIT.
.. THIS FILE WAS AUTOMATICALLY GENERATED BY SPHINX-GALLERY.
.. TO MAKE CHANGES, EDIT THE SOURCE PYTHON FILE:
.. "api/gallery/structures/merkle/plot_02_duplicate_leaf.py"
.. LINE NUMBERS ARE GIVEN BELOW.

.. only:: html

    .. note::
        :class: sphx-glr-download-link-note

        :ref:`Go to the end <sphx_glr_download_api_gallery_structures_merkle_plot_02_duplicate_leaf.py>`
        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_02_duplicate_leaf.py:


Two lists, one root: the duplicated-leaf ambiguity (CVE-2012-2459)
==================================================================

Bitcoin's Merkle tree pairs an odd node with a copy of itself. So the lists
[a, b, c] and [a, b, c, c] have the same root. In 2012 this let an attacker
send a block with a duplicated transaction: nodes rejected it as invalid and
remembered its hash as bad, so they later refused the valid block with the
same hash. The bug was fixed by checking for the duplication.

What to look for
----------------

Bitcoin's convention gives one root to two different lists. blockchainkit's
tree promotes odd nodes instead and binds the leaf count into the root, so
every list has its own root.

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-25

One root, two lists
-------------------

.. GENERATED FROM PYTHON SOURCE LINES 25-35

.. code-block:: Python

    import matplotlib.pyplot as plt

    import blockchainkit as bk

    honest = [b"coinbase", b"pay Bob", b"pay Carol"]
    mutated = honest + [b"pay Carol"]
    assert bk.structures.bitcoin_merkle_root(honest) == bk.structures.bitcoin_merkle_root(mutated)
    assert bk.structures.MerkleTree(honest).root != bk.structures.MerkleTree(mutated).root
    print("Bitcoin convention:", bk.structures.bitcoin_merkle_root(honest).hex()[:16], "for both lists")





.. rst-class:: sphx-glr-script-out

 .. code-block:: none

    Bitcoin convention: 3b6459144d8e0db1 for both lists




.. GENERATED FROM PYTHON SOURCE LINES 36-38

How many sizes are affected?
----------------------------

.. GENERATED FROM PYTHON SOURCE LINES 38-56

.. code-block:: Python

    ambiguous = []
    for n in range(1, 40):
        leaves = [bytes([i]) for i in range(n)]
        ambiguous.append(
            bk.structures.bitcoin_merkle_root(leaves)
            == bk.structures.bitcoin_merkle_root(leaves + leaves[-1:])
        )
    assert ambiguous == [n % 2 == 1 and n > 1 for n in range(1, 40)]
    fig, ax = plt.subplots(figsize=(8, 2.8))
    ax.bar(range(1, 40), ambiguous, color="#dc2626")
    ax.set(
        xlabel="number of leaves n",
        yticks=[0, 1],
        yticklabels=["distinct", "same root"],
        title="Is [..., x] confusable with [..., x, x]?",
    )
    fig.tight_layout()




.. image-sg:: /api/gallery/structures/merkle/images/sphx_glr_plot_02_duplicate_leaf_001.png
   :alt: Is [..., x] confusable with [..., x, x]?
   :srcset: /api/gallery/structures/merkle/images/sphx_glr_plot_02_duplicate_leaf_001.png
   :class: sphx-glr-single-img





.. GENERATED FROM PYTHON SOURCE LINES 57-63

Exercise
--------
The plot shows the ambiguity for every odd n above 1 (a single leaf is
never paired). Find a length-6 list whose
Bitcoin-style root equals that of a length-8 list. (Hint: duplicate a
whole pair.) Why does binding the count rule out all such cases?


.. rst-class:: sphx-glr-timing

   **Total running time of the script:** (0 minutes 0.137 seconds)


.. _sphx_glr_download_api_gallery_structures_merkle_plot_02_duplicate_leaf.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_02_duplicate_leaf.ipynb
        :alt: Launch JupyterLite
        :width: 150 px

    .. container:: sphx-glr-download sphx-glr-download-jupyter

      :download:`Download Jupyter notebook: plot_02_duplicate_leaf.ipynb <plot_02_duplicate_leaf.ipynb>`

    .. container:: sphx-glr-download sphx-glr-download-python

      :download:`Download Python source code: plot_02_duplicate_leaf.py <plot_02_duplicate_leaf.py>`

    .. container:: sphx-glr-download sphx-glr-download-zip

      :download:`Download zipped: plot_02_duplicate_leaf.zip <plot_02_duplicate_leaf.zip>`


.. only:: html

 .. rst-class:: sphx-glr-signature

    `Gallery generated by Sphinx-Gallery <https://sphinx-gallery.github.io>`_